Fast and Secure Immunization Against Adaptive Man-in-the-Middle Impersonation

We present a simple method for constructing identification schemes resilient against impersonation and man-in-the-middle attacks. Though zero-knowledge or witness hiding protocols are known to withstand attacks of the first kind, all such protocols previously proposed suffer from a weakness observed by Bengio et al.: a malicious verifier may simply act as a moderator between the prover and yet another verifier, thus enabling the malicious verifier to pass as the prover.We exhibit a general class of identification schemes that can be efficiently and securely transformed into identification schemes withstanding an adaptive man-in-the-middle attacker. The complexity of the resulting (witness hiding) schemes is roughly twice that of the originals. Basically, any three-move, public coin identification scheme that is zero knowledge against the honest verifier and that is secure against passive impersonation attacks, is eligible for our transformation. This indicates that we need only seemlingly weak cryptographic intractability assumptions to construct a practical identification scheme resisting adative man-in-the-middle impersonation attacks. Moreover, the required primitive protocols can efficiently be constructed under the factoring or discrete logarithm assumptions.