A Small Subgroup Attack for Recovering Ephemeral Keys in Chang and Chang Password Key Exchange Protocol

Abstract — Three-party authenticated key exchange protocol is an important cryptographic technique in the secure communication areas. Recently Chang and Chang proposed a novel three party simple key exchange protocol and claimed the protocol is secure, efficient and practical. Unless their claim, a key recovery attack is proposed on the above protocol by recovering the ephemeral keys. One way of recovering the ephemeral key is to solve the mathematical hard Discrete Logarithm Problem (DLP). The DLP is solved by using a popular Pohlig-Hellman method in the above key recovery attack. In the present study, a new method based on the small subgroup attack to solve the DLP is discussed to recover the ephemeral keys. Computation of DLP is carried out by two stages, such as the prior-computation and DLP computation. The prior-computation is performed on off-line and the DLP computation is performed on on-line. The method is analyzed on a comprehensive set of experiments and the ephemeral keys are recovered in reduced time. Also, the key recovery attack on Chang and Chang password key exchange protocol is implemented by using the new method to recover the ephemeral key. Index Terms — Ephemeral key, Key recovery attack, Chang and Chang password key exchange protocol