The atmosphere of Mars is over 95% CO2[1] which I imagine could support the propagation of bacteria. The Moon doesn't have much of an atmosphere at all (a trillionth of what the Earth has).[2]
The minerals they could get from soil, but without nitrogen they can't make proteins. The atmosphere of mars is 2.7% nitrogen, but I'm not convinced that that is enough for nitrogen fixation to work.
