Structured peer-to-peer (P2P) overlays rely on consistent and robust key-based routing to support large-scale network applications such as multicast and global-scale storage. We identify the main attack in these networks as a form of P2P identity theft, where a malicious node in the path of a message claims it is the desired destination node. Attackers can hijack route and lookup requests to forge and destroy data to disrupt applications. We propose a solution where nodes sign proof-of-life certificates for partial node ids and distribute them to randomly chosen proof managers in the network. Source nodes can evade attackers by requesting proofs from multiple proof managers. Analysis and simulation show the approach is effective and imposes storage and communication costs that grow logarithmically with network size.