Tweaking the Hasty Pudding Cipher Abstract I propose to add one statement to the inner loop of the Key Expansion Stirring Function for HPC. [Key Expansion maps the user-supplied variable-length key into a fixed-sized Key Expansion Array.] The new code does additional mixing in the Stirring Function, fixing an equivalent-key problem discovered by David Wagner. The extra code slows Key Expansion by 3%. Encryption and decryption routines are unchanged. The Problem: Equivalent Keys David Wagner [1,2] has discovered that a small fraction of the keys in HPC are equivalent. This result has been extended by Carl D'Halluin, Gert Bijnens, Bart Preneel, and Vincent Rijmen [3], to determine the exact conditions for equivalent keys. Keys are equivalent when they produce the same Key Expansion Array. [The encryption and decryption routines never see the actual user key-- their behavior is controlled by the kxa.] About 1/256 of the possible 128-bit keys for HPC are grouped into equivalence classes of about 2^32 keys each. Within an equivalence class, each key has roughly 32 free-choice bits, whose value doesn't affect the derived Key Expansion array. Similar results hold for 192- and 256-bit keys. Longer keys have a larger percentage of equivalent keys. Each subcipher (HPC-Tiny, -Short, etc.) has different sets of equivalent keys. It is possible for a user to deliberately compute equivalent keys. This violates one of the security statements for the Hasty Pudding Cipher, that finding equivalent keys is infeasible. This also violates two implicit requirements: Changing any key bit should change about 50% of the bits in the Key Expansion Array, and changing the key in any way should produce different encryptions. Analysis The Hasty Pudding Cipher processes user-supplied variable-length keys into a fixed-size Key Expansion Array, kxa, of 256 64-bit words. The kxa is pseudo-randomly initialized, based on the subcipher number and the key length. The key is xored into (the first half of) the kxa, and a stirring function is run to randomize the kxa. The processing is supposed to be a hashing expansion, creating random keying material for the encryption stage. In the Hasty Pudding Cipher's Key Expansion Stirring Function, the first statement of the inner loop is s0 ^= ( kxa[ i ] ^ kxa[ (i+83) & 255 ] ) + kxa[ s0 & 255 ] The developing Key Expansion Array, kxa[], is referenced three times to create a "random" modification to the current Mixing State (s0...s7). After further mixing steps, but with no additional kxa[] inputs, a value computed from the Mixing State (s2+s6) is stored into kxa[i] (overwriting the original value). The equivalent-key problem arises when s0 & 255 = i, which makes the first and third kxa references fetch the same word. When this happens, any bit position which is 1 in the middle kxa reference, and also the high-order bit position, can be either 0 or 1 in kxa[i], without affecting the value of the right-hand-side expression which is xored into s0. The low 8 bits of s0 will match i about 1/256 of the time, and when this happens about half of the bits in the word kxa[i] (about 32) will become "free choice", not affecting the value of the RHS. In the first pass of the Stirring Function, kxa values are overwritten without being further used, so their only affect on the final kxa array is through s0. It happens that the first word of the key isn't affected by this problem, but all subsequent words are vulnerable. This means that 1/256th of 128-bit keys are equivalent, with roughly 2^32 equivalent keys; that 2/256 of 192-bit keys are equivalent with roughly 2^32 equivalent keys, and 1/65536 of 192-bit keys are equivalent with 2^64 equivalent keys. The situation worsens for longer keys, and very long keys (>8192 bits) are more likely than not to have equivalents. The proportion of equivalents is small: a 8192 bit key may have perhaps 2^32 or 2^64 equivalents. Nevertheless, this violates a desired cipher property, that changing a single bit of key changes the encryption. The Solution: Additional Mixing Input from the KXA To fix this problem, I will add one line of code to the inner loop of the Key Expansion Stirring Function for HPC. The extra code slows Key Expansion by 3%, a negligible amount. It adds one instruction to the Stirring Function inner loop on the Alpha, and two instructions on the Pentium. The problem arises because kxa[i] makes no other contribution to the mixing state (s0...s7) of the key expansion. This suggests a simple repair. The line of code s2 += kxa[i] is inserted directly after the line discussed above. The subsequent instructions assure that the resulting modifications to s2 are thoroughly mixed into the Mixing State (s0...s7), and thence into the Key Expansion Array. (This is established by tracing the effect of a bit-change in kxa[i] through the mixing process. I also made empirical computer tests.) The extra execution time and code size is negligible. The encryption and decryption parts of the cipher are unchanged, so the times and analysis for encryption and decryption remain valid. The revised specification is supplied below. One new line has been inserted. (Note: The specification refers to the Key Expansion Array as KX[].) The change to the Key Expansion routine completely changes all the cipher test values, so a new set of values must be computed. References [1] David Wagner, private email message, March 13, 1999. [2] David Wagner, "Equivalent Keys in HPC", presented at the rump session, AES2, Rome, March 22, 1999. [3] Carl D'Halluin, Gert Bijnens, Bart Preneel, Vincent Rijmen, "Equivalent keys of HPC", http://www.esat.kuleuven.ac.be/~rijmen/ pub99.html [4] The Hasty Pudding Cipher, http://www.cs.arizona.edu/~rcs/hpc Rich Schroeppel, Puddingmeister rcs@cs.arizona.edu May 14, 1999