In a decentralized network, such as a peer-to-peer or a spontaneous network, a significant trust factor for a peer is to gain a sufficient level of certainty on the other peers’ real identity. In this paper we evaluate a proposed peer identification protocol that was designed for such environments and operates based on iterated challenge-response exchanges among peers. For this purpose, we introduce a new attack against this protocol and use the birthday paradox to model the number of operations until the proposed attack is successful. The modeling process, which results in the estimation of the upper bound effort for this successful attack, gives way to the definition of enhancements for the identification protocol. As a result, we define a new identification protocol based on multiple integer challenge-responses that, though not being a cryptographic protocol, represents for an attacker a challenge harder than breaking a symmetric cryptographic key by brute force attack. Our proposed attack shows how to break the GCP protocol without any previous knowledge on target secret information.