Recent observations of tsunami shadows, i.e., extended darker strips on the ocean surface along a front of a weak tsunami off Oahu, Hawaii, suggest that tsunamis in the deep ocean may be remotely detected through changes in ocean surface roughness. In this paper, physical mechanisms responsible for the formation of tsunami shadows are considered. The hypothesis that the change in surface roughness is due to an air-sea interaction is examined. Using an eddy-viscosity model for the average Reynolds stresses in turbulent flow, a theory is developed to model tsunami-induced perturbations in the atmospheric boundary layer. It is demonstrated that in the lowest tens of centimeters of the atmosphere, tsunami-induced perturbations of the mean wind velocity are much greater than current velocities in the water and can be comparable to the unperturbed wind velocity. Enhancement of tsunami-induced wind velocity perturbations compared to currents in the tsunami wave occurs because of a generation of a viscous wave in the air by a coherent elevation of large expanses of the ocean surface in the tsunami wave. The ratio of the maximum wind velocity perturbation to the amplitude of the current velocity approximately equals (πD/4$kappa$2λ) ln2 ($kappa$u*λ/2πcz0), where $kappa$ is the von K¿rm¿n constant, u* is the friction velocity of a background wind, z0 is the roughness length of the ocean surface, D is ocean depth, and λ and c are the tsunami wavelength and velocity, respectively. The results are shown to be robust with respect to a choice of a closure model for Reynolds stresses. Dependence of the tsunami-induced atmospheric perturbations on background wind velocity and direction, tsunami period and amplitude, and ocean depth is studied. Implications of the theoretical predictions on the feasibility of a satellite-based system relying on radars and/or microwave radiometers for early tsunami warning are discussed.