Round Constants
Round constants in hash functions, including those that use the sponge construction, serve several important purposes:
-
Symmetry Breaking: Round constants are used to break the symmetry of the state during the permutation process. Without these constants, each round would be identical, and certain patterns or structures in the input could propagate through the rounds unchanged. The constants ensure that each round is unique, preventing these patterns from surviving the hashing process.
-
Avoiding Fixed Points: A fixed point is when a certain input to the hash function results in the same output (e.g., ). Round constants help to avoid such scenarios, which could weaken the hash function's security.
-
Preventing Slide Attacks: In cryptography, a slide attack is a type of attack that takes advantage of repeating patterns within the rounds of a cryptographic algorithm. Round constants mitigate this risk by ensuring that each round of the permutation is distinct.
-
Diffusion: They contribute to the diffusion property of the hash function by ensuring that the input bits are spread across the resulting hash value, making the output look random.
-
Resisting Cryptanalysis: By carefully choosing the round constants, designers can protect against specific cryptanalytic attacks that exploit the mathematical structure of the permutation function.
Grain LSFR
Some of the most common types of round constants are linear feedback shift registers (LFSRs). Grain LFSR (Linear Feedback Shift Register) is a critical component in the Grain family of stream ciphers, which includes Grain v0, Grain v1, and Grain-128 and has been historically used to generate round constants. This family of ciphers is designed for hardware applications and aims to maintain low hardware cost. The Grain LFSR, along with a Nonlinear Feedback Shift Register (NFSR) and a nonlinear filtering function, forms the basis of these ciphers.
The LFSR in Grain provides a minimum period for the keystream, ensuring a certain level of security against attacks that exploit short periods. It operates on linear feedback principles, where the output is determined by a linear combination of previous bits in the register. This linear combination is defined by a feedback polynomial. The LFSR's role is to guarantee certain statistical properties and the non-repeating nature of the keystream.
In contrast, the NFSR, which works alongside the LFSR, introduces nonlinearity into the system. This nonlinearity is crucial for cryptographic strength, as linear systems are generally easier to attack. The NFSR's output, along with the LFSR's output, is processed through a nonlinear filtering function to produce the final keystream bit.
The specific construction and operation of the LFSR in Grain vary slightly between its different versions (v0, v1, and 128), primarily in terms of the length of the register and the feedback polynomial used. However, the underlying principle of providing a predictable, yet cryptographically secure, sequence of bits remains constant across all versions.
Importance of Round Constants
The following paper is a great resource on the importance of round constants in cryptographic algorithms
Briefly, the paper highlights the following points:
Impact of Round Constants on Security: The authors demonstrate that the round constants significantly influence a cipher's resistance to invariant attacks. They establish that the rational canonical form of the linear layer and the choice of round constants are crucial factors. Particularly, if the linear layer's invariant factors are few, round constants can be selected to ensure resistance to invariant attacks regardless of the S-box layer.
Recommendations for Selecting Round Constants: The authors suggest specific strategies for choosing round constants to maximize security. This includes analyzing the linear layer's structure and selecting constants that ensure a high degree of resistance. The paper provides mathematical methodologies and practical examples to help designers choose optimal round constants.
Algorithmic Tools for Analysis: They offer algorithmic approaches to evaluate the security of given ciphers against invariant attacks. These tools are used to analyze popular ciphers like Skinny-64, Prince, and Mantis7, demonstrating their effectiveness in proving or disproving resistance to such attacks.
Notes on Slide attacks
The slide attack is a form of cryptanalysis that targets ciphers believed to be strengthened by increasing the number of rounds. This attack renders the number of rounds in a cipher irrelevant. It focuses on analyzing and exploiting weaknesses in the cipher's key schedule, especially when keys repeat cyclically. The slide attack operates by breaking the cipher into identical permutation functions (denoted F) defined by the key schedule. The attacker collects numerous plaintext-ciphertext pairs to identify a 'slid pair', which, once found, compromises the cipher due to its vulnerability to known-plaintext attacks.