Exploiting physical layer characteristics to enhance or complement authentication strength in wireless networks has been attracting research attention recently. Existing physical layer authentication mechanisms mainly tackle single-hop communications. In this paper, we propose two physical layer challenge-response authentication mechanisms for wireless networks with relay. One mechanism, named PHY-CRAMR, is an extension of the existing PHY-CRAM protocol. It fully utilizes the randomness, reciprocity, and location decorrelation features of the wireless fading channel to hide/encrypt the challenge response messages at the physical layer, and is immune to outside attacks with a trusted relay. The other novel mechanism, named PHY-AUR, exploits randomness, coherence, and location decorrelation properties of wireless fading channel to securely convey the product of the channel state information on consecutive links and uses the fading channel to encrypt challenge and response messages. PHY-AUR is immune to both outside and inside attacks with an untrusted relay. Both PHY-CRAMR and PHY-AUR adopt OFDM technique to modulate the authentication key and challenge-response messages on subcarriers. Physical layer pilots and preambles are eliminated to prevent an attacker from gaining knowledge about the channel state information, and as a result prevent the authentication key from being revealed to untrusted attackers. We analyze the security strength of both mechanisms and conduct extensive simulations to evaluate them. It shows that both PHY-CRAMR and PHY-AUR can achieve both a high successful authentication rate and low false acceptance rate, and the performance improves as the signal to noise ratio (SNR) increases.