NTT, Ruhr-Universität Bochum and Kobe University develop a new cryptanalytic technique to improve the design of lightweight ciphers for IoT
-- The research result gets accepted at a conference organized by the International Association of Cryptologic R

Tokyo, December 1, 2016 ENippon Telegraph and Telephone Corporation (NTT), jointly with Ruhr-Universität Bochum and with Kobe University, has developed a new cryptanalytic technique that helps improve the design and security of lightweight symmetric-key ciphers, which are considered to play an active part in the IoT era. Most of the previous cryptanalysis assumes unrealistic scenarios where adversaries have chances of obtaining encrypted data of plaintext they deliberately choose, in terabytes. In contrast, the new cryptanalytic technique, when applied to several existing (lightweight) ciphers, recovers part of plaintext from encrypted data of smaller than one kilobyte, under the condition that either the plaintext contains repetition or the same plaintext gets encrypted multiple times. The new technique can be used to greatly improve the design of lightweight ciphers and to re-evaluate the security of other existing symmetric-key ciphers. The research result has been selected as "Invited to the Journal of Cryptology", meaning one of the top three papers accepted at Asiacrypt 2016 (held in Hanoi, Vietnam, starting December 4), a prestigious conference organized by the International Association of Cryptologic Research.

1.Background

Cryptographic techniques can be classified into two different categories. The first category includes "information-theoretically secure" systems, which are secure against adversaries that have infinite, unbounded computational power. The second category includes "computationally secure" systems, which are secure against adversaries that have limited, bounded computational power, e.g. using all existing computers on the earth for ten years. While information-theoretically secure systems have the advantage of remaining secure irrespective of the progress of computer technology, these systems have the disadvantage of requiring a secret key whose length is at least that of the message to be encrypted. Because of this disadvantage, information-theoretically secure systems are considered to be impractical except for cases where the highest security must be guaranteed, such as military or diplomatic uses. On the other hand, computationally secure systems can reduce the key size down to about 128 bits, though none of these systems have been proven unconditionally secure.

The computationally secure systems are further classified into two categories. The first category includes systems with "reduction" security, which means that they are proven secure based on the assumption about the hardness of some mathematical problems or about the computational security of other "smaller" systems, typically used as part of the original systems. The second category includes cryptographic primitives, which themselves are expected to be computationally secure. The systems with reduction security remain secure unless the assumptions get invalidated or the proofs are found to be wrong. On the other hand, the cryptographic primitives enhance their credibility by first making their specification open to the public and then withstanding various types of cryptanalysis by a number of researchers for a long period of time. For example, today the symmetric-key cipher Camellia, a cryptographic primitive jointly developed by NTT and Mitsubishi Electric, has established its credibility by withstanding numerous attempts of cryptanalysis for more than fifteen years.

Most of the cryptographic primitives are based on an iterative structure inside, and the internal iterative unit is called a round. For example, Camellia with a 128-bit key has eighteen rounds and AES with a 256-bit key has fourteen rounds. Usually, a fewer number of rounds implies less security. Once a new cryptographic primitive is published, attempts are done with various types of known, existing cryptanalytic techniques. Resistance to each type of cryptanalysis is examined by reducing the number of rounds. For example, previous attempts show that it is hard to cryptanalyze AES for more than four rounds using ordinary differential cryptanalysis. This implies that AES with a 256-bit key should be secure against ordinary differential cryptanalysis, because it has fourteen rounds according to the specification.

Any computationally secure system can be broken by a brute-force attack, or an exhaustive key search. A cryptographic primitive is considered to be "theoretically broken" if cryptographers find a way to recover part of unknown plaintext or the whole key using computational power less than the exhaustive key search. For example, AES with a 256-bit key is considered to be theoretically broken, because cryptographers have found a way to recover the key using an advanced cryptanalytic technique called the boomerang attack, under the unrealistic scenario where four different keys having relations convenient for the adversary are simultaneously used and the adversary is given 2^99.5 blocks (a block is 128 bits) of encrypted data for messages that the adversary choose, the adversary given computational power of executing AES 2^99.5 times. If a new cryptographic primitive is found to withstand all known, existing cryptanalytic techniques, then cryptographers try to devise new types of cryptanalysis and apply them to the new primitive. Thus, a new cryptographic primitive establishes its credibility by withstanding old and new various cryptanalytic techniques such as differential cryptanalysis and the boomerang attack.

2.Key facts

Linear cryptanalysis was published in 1993 and applied to DES which was essentially the world standard at that time, demonstrating a first break of DES by a computer. Linear cryptanalysis was applied to numerous cryptographic primitives as a generic cryptanalytic technique, and cryptographic primitives newly developed after the publication of linear cryptanalysis were required to be provided with evidence of resistance to linear cryptanalysis. Linear cryptanalysis, as the name suggests, linearly approximates nonlinear behavior of cryptographic primitives. It has been a long-standing open problem whether it is possible to devise a similar type of cryptanalysis using nonlinear (quadratic or higher) approximation rather than linear. There was a previous attempt in 1995 where nonlinear approximation was used to analyze input and output parts of a cryptographic primitive, but no previous attempts succeeded in cryptanalyzing an entire cryptographic primitive. Our new cryptanalytic technique, the nonlinear invariant attack, gives an answer to the open problem for the first time.

In the paper, the nonlinear invariant attack is applied to SCREAM, iSCREAM and Midori64. SCREAM and iSCREAM are symmetric-key schemes submitted to CAESAR, a competition to evaluate authenticated encryption (symmetric-key ciphers equipped with integrity check). Midori64 is a symmetric-key cipher published at Asiacrypt 2015. The key idea of the attack is to identify a quadratic (hence nonlinear) invariant quantity associated with the nonlinear component of the cipher called sbox and then to observe that the sum of each sbox output remains unchanged also through the linear part of the cipher where a binary orthogonal matrix is used. When the attack is applied to SCREAM and iSCREAM, 32 bits of plaintext are instantly recovered from 33 blocks (one block is 128 bits) of encrypted data, under the condition that the secret key be one of the 2^96 special keys out of the entire 2^128 key space. When applied to Midori64, for example in the CTR (counter) mode, 32 bits of plaintext are instantly recovered from 33 blocks (one block is 64 bits) of encrypted data for 2^64 special keys out of the entire 2^128 key space. Most of the previous cryptanalysis assumes unrealistic scenarios where adversaries have chances of obtaining encrypted data of plaintext they deliberately choose, in terabytes. In contrast, the new cryptanalytic technique, when applied to these symmetric-key primitives, recovers part of unknown plaintext only from encrypted data of smaller than one kilobyte under certain realistic conditions on the plaintext space.

3.Future plans

NTT Secure Platform Laboratories continue to re-evaluate the security of other existing ciphers by applying the nonlinear invariant attack and to pursue cryptanalytic techniques for developing secure cryptographic algorithms.

The academic paper describing the nonlinear invariant attack in detail is presented at Asiacrypt 2016, a prestigious, peer-reviewed conference organized by the International Association of Cryptologic Research. The paper is awarded "Invited to the Journal of Cryptology," meaning it was one of the top three papers accepted at the conference.

Major research results by NTT Labs for cryptographic primitives

• 2016 Nonlinear invariant attack
• 2015 Theoretical cryptanalysis of MISTY1 using division property
• 2009 Theoretical preimage-attack on the cryptographic hash algorithm MD5
• 2000 Development of 128-bit block cipher Camellia
• 1987 Development of 64-bit block cipher FEAL-8

Camellia
An algorithm developed jointly by NTT and Mitsubishi Electric in 2000. It is standardized and selected by various organizations, including CRYPTREC "e-Government Recommended Ciphers List," ISO/IEC 18033-3 and RFC 3713. It is available to the public as part of open source software, such as Linux, FreeBSD and OpenSSL.

CTR mode
A mode of operation for encryption using a symmetric-key block cipher. It is widely used and standardized, for example in "e-Government Recommended Ciphers List" by CRYPTREC and in SP 800-38A by the National Institute of Standards and Technology (NIST).

Invited to the Journal of Cryptology
A paper that has been invited for submission with promised acceptance to the Journal of Cryptology, the academic journal in cryptography published by the International Association of Cryptologic Research. Three papers from Asiacrypt 2016 have been selected as "Invited to the Journal of Cryptology."