The security of global navigation satellite systems draws attention increasingly, and authentication mechanisms for civilian services seem very effective in thwarting malicious behavior. For example, the Galileo E1 Open Service introduces navigation message authentication. Authentication, as well as encryption at navigation message or spreading code level, can prevent spoofing attacks, but do not preclude replay attacks. In this work, we consider a type of strong replay attacks, distance-decreasing attacks, against cryptographically protected GNSS signals. Distance-decreasing attack enhance an attacker's capability of allowing it to mislead the victim receiver that the GNSS signals arrive earlier than true signals. We analyze the instantiation and the effects of the distance-decreasing attacks on unprotected GNSS signals, on navigation message authenticated signals, and on spreading-code encrypted signals. We discuss different strategies that the attacker can adopt to introduce the least bit errors to the re-transmitted signals and avoid being detected at the victim receiver. We provide evaluation results of distance-decreasing attacks on unprotected signals and authenticated navigation message signals, based on different strategies and configurations, and we sketch countermeasures to the different strategies.