Where does the energy come from to lower the temperature of a brine solution?
The minimum temperature reached should be −21 °C at 29 % NaCl. Initially suppose that the ice,  water and water vapour are at 0 °C in a thermally insulated container. Say point A in the figure and some salt is now added.
However, the mixture is now not at equilibrium, and some ice melts and dissolves some salt. The resulting solution is now too concentrated to be in equilibrium with the ice so more ice melts, diluting the solution and so more ice melts. At the same time the temperature of the whole system spontaneously falls until after sufficient salt is added a temperature of −21 °C is reached.
This is the eutetic point (point E) and equilibrium has been reached. The temperature falls because for a phase change to occur the ice uses the heat of fusion it needs to melt by drawing that much heat from its surroundings.
Many other salts can be used instead of NaCl, such as ammonium chloride and calcium chloride.

Figure 1. Crude phase diagram of the ice/water/salt mixture.