Lecture Notes in Computer Science vol:1716 pages:29-42
ASIACRYPT 1999 date:November 14-18, 1999
This paper presents a weakness in the key schedule of the AES candidate HPC (Hasty Pudding Cipher). It is shown that for the HPC version with a 128-bit key, 1 in 256 keys is weak in the sense that it has 2(30) equivalent keys. An efficient algorithm is proposed to construct these weak keys and the corresponding equivalent keys. If a weak key is used, it can be recovered by exhaustive search trying only 2(89) keys on average. This is an improvement by a factor of 2(38) over a normal exhaustive key search, which requires on average 2(127) attempts. The weakness also implies that HPC cannot be used in standard constructions for hash functions based on block ciphers. The analysis is extended to HPC with a 192-bit key and a 256-bit key, with similar results. For some other key lengths, all keys are shown to be weak. An example of this is the HPC variant with a 56-bit user key and block length of 128 bits, which can be broken in 2(31) attempts on average.