AES is the dominant algorithm used for symmetric encryption, the kind of encryption in which the same key is used to encrypt and decrypt data. Notably, the ChaCha20, a faster alternative, already replaced AES in some protocols, but with less scrutiny.
The speed of ChaCha20 comes from the fact that it is an ARX cipher, meaning that it only uses three kinds of software-friendly operations: modular addition, rotations and exclusive or (XOR). Such ciphers are known to be vulnerable to rotational cryptanalysis attacks.
The full ChaCha20 design can be divided into a pure ARX permutation, which we will refer to as the ChaCha20 permutation, plus the injection of constants. This last operation was included to overcome vulnerabilities such as rotational attacks. Until recently, no one had formally investigated the limitation of the ChaCha permutation itself with respect to rotational cryptanalysis.
Now, researchers at Technology Innovation Institute Cryptography Research Center, in collaboration with the Politecnico di Torino (Italy), have quantified the susceptibility of the ChaCha permutation to rotational cryptanalysis attacks. Dr. Emanuele Bellini, Principal Cryptographer at TII, said: “We wanted a formal study clarifying the mathematical properties of the ChaCha20 permutation concerning rotational cryptanalysis. The results were surprising.” In addition to Bellini, other collaborators include Rusydi Makarim from TII and Stefano Barbero from Politecnico di Torino.
Speed is crucial since cryptographic algorithms tend to get repeated frequently, therefore a minor improvement could lead to significant savings in time. However, ChaCha20 is much newer, and more research will be required to see if it can provide the same level of protection as AES against a wide variety of cryptographic attacks. In the future, such research could pave the way for the broader adoption of ChaCha20 as an alternative to AES.
Faster but less studied
Cryptographic security systems are often composed of multiple types of ciphers to provide different kinds of data protection. ChaCha20 is a widely used stream cipher that helps protect banks, ATM transactions, and the transport layer security (TLS) of the Internet.
AES is the most common type of block cipher because it has been extensively studied and its risks cataloged in considerable detail. Consequently, it has been standardized by the US National Institute of Standards and Technology (NIST) and is baked into most commercial symmetrical encryption systems. The standardization helped encourage hardware optimized to speed up these calculations.
As a result, commercial AES hardware provides an edge over other kinds of cryptographic systems. But ChaCha20 is faster when running on standard hardware since it comprises three basic operations that are less complex than those used in AES.
Susceptible to rotational cryptanalysis
Cryptographers constantly investigate different approaches for probing important algorithms for vulnerabilities. The two main techniques for measuring stream ciphers are linear and differential cryptanalysis. Linear techniques attempt to find biases in the correlation between the input and output in a certain number of rounds of the symmetric cipher. On the other hand, differential techniques attempt to find biases in the correlation between plaintext differences and the corresponding ciphertext differences. Usually, these differences are computed with respect to the XOR operation.
Rotational cryptanalysis is a newer technique that explores differences with respect to the rotation operation. With rotational cryptanalysis, cryptographers explore more complicated variants of simple operations like substituting each letter in a message with the following letter in the alphabet.
“There are some ciphers for which differential cryptanalysis is better and some in which rotational cryptanalysis is better, and this depends on the operations the cipher uses,” said Bellini. “The ChaCha20 permutation and in general ARX ciphers include operations that are more vulnerable to rotational cryptanalysis.”
He notes that it is essential to distinguish this core permutation operation from the rest of the actual ChaCha20 implementation. Additional countermeasures have been adopted that protect against known rotational cryptanalysis techniques.
Shining a light on the core
All cryptographic ciphers are built in an iterated way in which the same function, called round, is repeated multiple times. The ChaCha20 round is repeated 20 times. Cryptographers cannot break the full cipher for all rounds, so they analyze a reduced version of the algorithm with fewer rounds. For example, the best-known key recovery attack on ChaCha20 can retrieve a key after 6 rounds of the 20. In other words, the full ChaCha20 implementation still has a buffer of 14 rounds of iterations to protect against known attacks.
An important security property that a cipher must have, is that its behavior should be indistinguishable from that of a random function with the same input and output size. The TII researchers found that the ChaCha20 permutation component does not behave as a random permutation for 17 rounds out of 20. This research does not rule out ChaCha20’s value as a stream cipher because of the aforementioned countermeasures. However, it does rule out the use of the core ChaCha20 permutation for permutation-based cryptography. This cryptographic field attempts to build symmetric encryption primitives by starting with the core permutation.
“Until now, no one has used ChaCha20 permutation in permutation-based cryptography,” Bellini said. “Our finding would suggest that this is not a good idea. We have ruled out ChaCha20 permutation as a candidate for permutation-based cryptography.”
More research required
Although ChaCha20 shows promise, Bellini cautions that more research is required to provide researchers with the level of confidence they have in AES. “ChaCha20 has received considerably less attention, which makes sense because AES is more widely used,” he said.
He believes it is essential to conduct more research on the countermeasures baked into the ChaCha20 stream cipher. Bellini said, “There are some countermeasures, but they have been defined heuristically. We want to prove that the countermeasures used in ChaCha20 are actually providing the intended security.”
ChaCha operations
This diagram illustrates the flow of operations in one quarter of ChaCha20 round, the so-called quarter round. The yellow represents modular additions, blue represents XOR operations, and the green represents the rotation operations. The XOR and rotation operations make the core ChaCha20 permutation most vulnerable to rotational cryptanalysis, while the modular addition operations protect it from rotational cryptanalysis. The quarter round is completed 80 times for the full implementation with 20 rounds.
