Attack algorithm on a key generation method

Attack algorithm on a keystore-based secret key generation method

Seungjae Chae, Young-Sik Kim, Jong-Seon No, and Young-Han Kim

A new attack algorithm is proposed for a secure key generation and management method introduced by Yang and Wu. It was previously claimed that the key generation method of Yang and Wu using a keystore seed was information-theoretically secure and could solve the long-term key storage problem in cloud systems, thanks to the huge number of secure keys that the keystone seed can generate. Their key generation method, however, is considered to be broken if an attacker can recover the keystore seed. The proposed attack algorithm in this paper reconstructs the keystore seed of the Yang–Wu key generation method from a small number of collected keys. For example, when t=5 and l=2^7, it was previously claimed that more than 253 secure keys could be generated, but the proposed attack algorithm can reconstruct the keystone seed based on only 84 collected keys. Hence, the Yang–Wu key generation method is not information-theoretically secure when the attacker can gather multiple keys and a critical amount of information about the keystone seed is leaked.