Hasty Pudding cipher

Hasty Pudding Cipher
General
Designers	Richard Schroeppel
First published	June 1998
Cipher detail
Key sizes	Variable
Block sizes	Variable

Last updated November 20, 2024

The Hasty Pudding cipher (HPC) is a variable-block-size block cipher designed by Richard Schroeppel, which was an unsuccessful candidate in the competition for selecting the U.S. Advanced Encryption Standard (AES). It has a number of unusual properties for a block cipher: its input block size and key length are variable, and it includes an additional input parameter called the "spice" for use as a secondary, non-secret key. The Hasty Pudding cipher was the only AES candidate designed exclusively by U.S. cryptographers.^[1]^[2]

The cipher

The Hasty Pudding cipher consists of 5 different sub-ciphers:^[5]

HPC-Tiny	0–35 bits
HPC-Short	36–64 bits
HPC-Medium	65-128 bits
HPC-Long	129–512 bits
HPC-Extended	513+ bits

The Hasty Pudding cipher algorithms all use 64-bit words internally. The cipher is designed to run on 64-bit machines, which can easily perform simple operations on 64-bit words.

Key expansion

The Hasty Pudding cipher can take a key of any number of bits for any one of the five subciphers. The cipher itself uses a key table of 16,384 bits (256 64-bit words). To derive the key table from the key, the key expansion function uses the following algorithm:^[5]

The first three words, KX[0], KX[1], KX[2] are set based on constants, the sub-cipher, and the length of the key. KX[1] is computed with a multiplication; the other operations involved are an addition and a bit shift.
Each successive word, KX[i] is determined from the three previous words by an efficient recursive formula.
The key bits are XORed into the bits of the key table, starting at KX[0], until all the key bits are used. (Keys longer than 8,192 bits use a more complicated procedure.)
Several passes over the key table are made. Each time, a "stirring function" is applied to each word of the key table, in sequence. The stirring function uses eight internal variables, and uses 14 logical bit operations, 5 bit shifts, and 14 additions / subtractions. Each use of the stirring function modifies one word in the key table, based on its previous value, the values of certain other words, and the internal variables of the stirring function. (3 total passes is the default.)

Encryption and decryption

Each of the subciphers uses a different algorithm, but there are certain similarities. Three inputs are used to determine the ciphertext: the plaintext (in several 64-bit words plus one "fragment"), the spice (eight 64-bit words, with default value 0), and the key table. The operations within the cipher consist of stirring, which combines internal variables in various ways with values from the key table and spice at regular intervals. HPC-Short uses two fixed permutations in addition, and HPC-Tiny consists of many special sub-cases.

Decryption involves undoing the steps of encryption one by one. Many operations are easily undone (e.g. s₀ = s₀ + s₁ is undone by computing s₀ = s₀ − s₁). Other operations are more complex to undo. Some of the ideas involved include:

An operation like x = x ⊕ (x >> 17) is undone by a two-step process: (1) x = x ⊕ (x >> 17), followed by (2) x = x ⊕ (x >> 34).
The cipher uses value-dependent lookups into the key table. These can be undone, since the lookup depends only on the last 8 bits of a variable, and when it becomes necessary to look up the value from the key table in decryption, the last 8 bits of the value at a certain earlier point in the computation are predictable, even when those operations cannot all be undone without the key table value. For instance, if the lookup of k is based on the last 8 bits of x, then when we want to undo a step like x = x ⊕ (k << 8), we can look up k by noting that the last 8 bits of x are unchanged by this operation.

The Hasty Pudding cipher can also be used to encrypt values in a range that do not translate to strings with an integral number of bits; for instance, it can encrypt a number from 0 to N by producing another number from 0 to N. It does this by using the smallest subcipher that can handle the input as a bit string, and applying it to the input as a bit string, repeatedly, until the output is in the proper range.^[5]

Performance

Schroeppel claimed that the Hasty Pudding cipher was the fastest AES candidate on a 64-bit architecture;^[6] Schroeppel claimed that it was twice as fast as its nearest competitor, DFC, and three times as fast as the other candidates, and that its performance on a 32-bit machine was adequate.^[6] Comments from others did not support this view; for instance, Schneier et al.'s analysis ranked the Hasty Pudding cipher 4th best (376 cycles) on a 64-bit machine, although for Rijndael and Twofish, the performance was only estimated.^[7] On a 32-bit Pentium, Hasty Pudding encryption was rated by Schneier et al. at 1600 clock cycles, 10th best out of the 15 candidates.^[7] Schneier et al., and Schroeppel, noted that the speed of the cipher would be significantly impacted on a 32-bit machine because of its heavy use of 64-bit operations, particularly bit shifts.^[3]^[7]

The Hasty Pudding cipher's key setup was rated as relatively slow; 120000 cycles on a Pentium.^[7]

The cipher was criticized for its performance on smartcards. Specifically, some comments pointed out the difficulty of keeping over 2KB of RAM for the key table.^[8]

Further work

There have been relatively few results on attacking the Hasty Pudding cipher. Early in the AES process, David Wagner noted that relatively large classes of Hasty Pudding keys were equivalent in that they led to the same key table.^[9] This was expanded upon by D'Halluin et al., who noted that for 128-bit keys, approximately 2¹²⁰ keys are weak keys that each have 2³⁰ equivalent keys each.^[10] In response to this attack, Schroeppel modified the key expansion algorithm to include one additional step.^[5]

Despite the relative lack of cryptanalysis, the Hasty Pudding cipher was criticized for its hard-to-understand design and its lack of grounding in research results.^[9]^[11] Schroeppel has offered a bottle of Dom Pérignon champagne to the best paper presenting progress on the Hasty Pudding cipher.^[3] It did not make the second round of consideration for AES.^[12]

The Hasty Pudding cipher is considered the first tweakable block cipher.^[13]

Related Research Articles

The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.

Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date for smaller files. It is recommended Blowfish should not be used to encrypt files larger than 4GB in size, Twofish should be used instead.

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

In cryptography, the International Data Encryption Algorithm (IDEA), originally called Improved Proposed Encryption Standard (IPES), is a symmetric-key block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. The algorithm was intended as a replacement for the Data Encryption Standard (DES). IDEA is a minor revision of an earlier cipher, the Proposed Encryption Standard (PES).

The Advanced Encryption Standard (AES), the symmetric block cipher ratified as a standard by National Institute of Standards and Technology of the United States (NIST), was chosen using a process lasting from 1997 to 2000 that was markedly more open and transparent than its predecessor, the Data Encryption Standard (DES). This process won praise from the open cryptographic community, and helped to increase confidence in the security of the winning algorithm from those who were suspicious of backdoors in the predecessor, DES.

In cryptography, an initialization vector (IV) or starting variable is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation.

<span class="mw-page-title-main">Block cipher mode of operation</span> Cryptography algorithm

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

<span class="mw-page-title-main">CAST-128</span> Block cipher

In cryptography, CAST-128 is a symmetric-key block cipher used in a number of products, notably as the default cipher in some versions of GPG and PGP. It has also been approved for Government of Canada use by the Communications Security Establishment. The algorithm was created in 1996 by Carlisle Adams and Stafford Tavares using the CAST design procedure.

In modern cryptography, symmetric key ciphers are generally divided into stream ciphers and block ciphers. Block ciphers operate on a fixed length string of bits. The length of this bit string is the block size. Both the input (plaintext) and output (ciphertext) are the same length; the output cannot be shorter than the input – this follows logically from the pigeonhole principle and the fact that the cipher must be reversible – and it is undesirable for the output to be longer than the input.

<span class="mw-page-title-main">Serpent (cipher)</span>

Serpent is a symmetric key block cipher that was a finalist in the Advanced Encryption Standard (AES) contest, in which it ranked second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen.

MARS is a block cipher that was IBM's submission to the Advanced Encryption Standard process. MARS was selected as an AES finalist in August 1999, after the AES2 conference in March 1999, where it was voted as the fifth and last finalist algorithm.

<span class="mw-page-title-main">DEAL</span> Block cipher

In cryptography, DEAL is a symmetric block cipher derived from the Data Encryption Standard (DES). Its design was presented by Lars Knudsen at the SAC conference in 1997, and submitted as a proposal to the AES contest in 1998 by Richard Outerbridge.

Salsa20 and the closely related ChaCha are stream ciphers developed by Daniel J. Bernstein. Salsa20, the original cipher, was designed in 2005, then later submitted to the eSTREAM European Union cryptographic validation process by Bernstein. ChaCha is a modification of Salsa20 published in 2008. It uses a new round function that increases diffusion and increases performance on some architectures.

In cryptography, Galois/Counter Mode (GCM) is a mode of operation for symmetric-key cryptographic block ciphers which is widely adopted for its performance. GCM throughput rates for state-of-the-art, high-speed communication channels can be achieved with inexpensive hardware resources.

bcrypt is a password-hashing function designed by Niels Provos and David Mazières, based on the Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt to protect against rainbow table attacks, bcrypt is an adaptive function: over time, the iteration count can be increased to make it slower, so it remains resistant to brute-force search attacks even with increasing computation power.

In cryptography, format-preserving encryption (FPE), refers to encrypting in such a way that the output is in the same format as the input. The meaning of "format" varies. Typically only finite sets of characters are used; numeric, alphabetic or alphanumeric. For example:

The following outline is provided as an overview of and topical guide to cryptography:

<span class="mw-page-title-main">Twofish</span> Block cipher

In cryptography, Twofish is a symmetric key block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard contest, but it was not selected for standardization. Twofish is related to the earlier block cipher Blowfish.

A biclique attack is a variant of the meet-in-the-middle (MITM) method of cryptanalysis. It utilizes a biclique structure to extend the number of possibly attacked rounds by the MITM attack. Since biclique cryptanalysis is based on MITM attacks, it is applicable to both block ciphers and (iterated) hash-functions. Biclique attacks are known for having weakened both full AES and full IDEA, though only with slight advantage over brute force. It has also been applied to the KASUMI cipher and preimage resistance of the Skein-512 and SHA-2 hash functions.

The 3-subset meet-in-the-middleattack is a variant of the generic meet-in-the-middle attack, which is used in cryptology for hash and block cipher cryptanalysis. The 3-subset variant opens up the possibility to apply MITM attacks on ciphers, where it is not trivial to divide the keybits into two independent key-spaces, as required by the MITM attack.

References

↑ Eli Biham, A Note on Comparing the AES Candidates , April 1999, public comment on AES.
↑ Susan Landau, Communications Security for the Twenty-first Century: The Advanced Encryption Standard , Notices of the AMS, vol. 47, number 4, 2000.
1 2 3 Rich Schroeppel and Hilarie Orman, An Overview of the Hasty Pudding Cipher, July 1998.
↑ iscgar/hasty-pudding on GitHub.
1 2 3 4 Schroeppel, Rich (June 1998), Hasty Pudding Cipher Specification (revised May 1999 ed.), archived from the original on 2011-07-17, retrieved 2009-06-10
1 2 Rich Schroeppel, The Hasty Pudding Cipher: One Year Later , accessed 9-01-2008
1 2 3 4 Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, and Niels Ferguson, Performance Comparison of the AES Submissions , The Second AES Candidate Conference, 1999.
↑ Emanoil Daneliuc, Public comment on AES candidates, February 1999.
1 2 David Wagner, Equivalent keys for HPC, rump session talk at the 2nd AES Conference, Rome, March 1999.
↑ Carl D'Halluin, Gert Bijnens, Bart Preneel, and Vincent Rijmen, Equivalent Keys of HPC , Advances in Cryptology — Proceedings of ASIACRYPT 1999, 1999.
↑ Olivier Baudron, Henri Gilbert, Louis Granboulan, Helena Handschuh, Antoine Joux, Phong Nguyen, Fabrice Noilhan, David Pointcheval, Thomas Pornin, Guillaume Poupard, Jacques Stern, and Serge Vaudenay, Report on the AES Candidates , Second AES Conference, March 1999.
↑ James Nechvatal, Elaine Barker, Lawrence Bassham, William Burr, Morris Dworkin, James Foti, and Edward Roback, Report on the Development of the Advanced Encryption Standard (AES) , NIST official release, October 2, 2000.
↑ Moses Liskov, Ronald Rivest, and David Wagner, Tweakable Block Ciphers, in Advances in Cryptology — Proceedings of CRYPTO '02, 2002.