We point out that violation of Lorentz invariance affects the interaction of high-energy photons with the Earth's atmosphere and magnetic field. In a certain parameter region this interaction becomes suppressed and the photons escape observation, passing through the atmosphere without producing air showers. We argue that a detection of photon-induced air showers with energies above 1019 eV, implying the absence of suppression as well as the absence of photon decay, will put tight double-sided limits on Lorentz violation in the sector of quantum electrodynamics. These constraints will be by several orders of magnitude stronger than the existing ones and will be robust against any assumptions about the astrophysical origin of the detected photons.