You can steal them from Rust Birds on the Mountain where you find Desh, I believe... Oh well, wherever they are, if you find Rust Birds, you can steal Phoenix Downs from them.