Insecure Instantiations of Random Oracles in Password-Based Key Exchange Protocols

摘要

Protocols for Password-based Authenticated Key Exchange (PAKE) allow users to generate a shared secret key from their easy-to-remember passwords but at the same time have to protect the user's passwords from the notorious dictionary attacks. PAKE protocols often use a hash function that maps user passwords into elements of the underlying cyclic group G generated by an arbitrary fixed element g∈G. Such a hash function is usually modelled as a random oracle G in proofs of security of protocols. One obvious way of instantiating the random oracle G is to use a random oracle H: {0, 1} *→Z_q and then define G(.) = g~H(.). However, we argue that this obvious instantiation of G is likely to result in a critical vulnerability for most of PAKE protocols. In the present research, we provide a strong evidence in support of this argument by showing that two popular protocols-Bresson two-party PAKE protocol and Abdalla and Pointcheval's three-party PAKE protocol-become susceptible to an offline dictionary attack as soon as G is instantiated as G (.) = g~H(.). Our result suggests that designers of PAKE protocols should clearly specify how G can be securely instantiated for their protocols in order to prevent protocol implementers from employing an insecure instantiation of G.