Stability of running on rough terrain depends on the propagation of perturbations due to the ground. We consider stability within the sagittal plane and model the dynamics of running as a two-dimensional body with an alternating aerial and stance phase. Stance is modeled as a passive, impulsive collision followed by an active, impulsive push-off that compensates for collisional losses. Such a runner has infinitely many strategies to maintain periodic gaits on flat ground. However, these strategies differ in how perturbations due to terrain unevenness are propagated. Instabilities manifest as tumbling (orientational instability) or failing to maintain a steady speed (translational instability). We find that open-loop strategies that avoid sensory feedback are sufficient to maintain stability on step-like terrains with piecewise flat surfaces that randomly vary in height. However, these open-loop runners lose orientational stability on rough terrains whose slope and height vary randomly. Only by avoiding tangential collisions is orientational stability recovered. Tangential collisions may be avoided through leg-retraction to match foot and ground speed at touch down. By analyzing the propagation of perturbations, we derive a single dimensionless parameter that governs stability and guides the design and control of both biological and robotic runners.