Why does NIST want 112-bit security from 128-bit key size for lightweight cryptography?

Question

In NIST's Submission Requirements and Evaluation Criteria for the Lightweight Cryptography Standardization Process document it is stated that:

3.1 AEAD (Authenticated Encryption with Associated Data) Requirements

An AEAD algorithm shall not specify key lengths that are smaller than 128 bits. Cryptanalytic attacks on the AEAD algorithm shall require at least $\mathbf{2^{112}}$ computations on a classical computer in a single-key setting. If a key size larger than 128 bits is supported, it is recommended that at least one recommended parameter set has a key size of 256 bits, and that its resistance against cryptanalytical attacks is at least $\mathbf{2^{224}}$ computations on a classical computer in a single-key setting (The bolds are mine!)

• Why does the NIST require 112-bit security from at least a 128-bit key on AEAD?
• From the security perspective, they should require 128-security. Any attack that reduces 128-bit security can lead to more attacks. What is the rationale behind this requirement?

And similarly for the hash functions;

3.2 Hash Function Requirements

Cryptanalytic attacks on the hash function shall require at least $\mathbf{2^{112}}$ computations on a classical computer. The hash function shall not specify output sizes that are smaller than 256 bits. (The bolds are mine!)

From the values, we can hint that they consider the collision resistance. Similar questions;

• Why does NIST require 112-bit security from 256-bit hash functions?
• What is the rationale behind this requirement?

Answer 1

From the security perspective, they should require 128-security.

Why?

NIST has a requirement for a minimum security strength of 112 bits for all things cryptographic, at least for the present. You see it everywhere in their documents. For example, in Transitioning the Use of Cryptographic Algorithms and Key Lengths it says

For the Federal Government, a security strength of at least 112 bits is required at this time for applying cryptographic protection (e.g., for encrypting or signing data). Note that prior to 2014, a security strength of at least 80 bits was required for applying these protections, and the transitions in this document reflect this change to a required security strength of at least 112 bits.

Apparently, the cryptographers at NIST believe that 112 bits of security is sufficient for now. 128 bits is coming though.

SP 800-57, Part 1 includes a transition to a security strength of 128 bits in 2030; in some cases, the transition would be addressed by an increase in key sizes.

Do note that this is their minimum requirement for the US Federal government, your requirements may be different.

Answer 2

Single target with bitcoin miners

We can approximate the reasoning with Bitcoin miner and hashcat comparisons. Bitcoin miner can reach $\approx 2^{92}$ double SHA256 per year. They are using various computing platform that includes CPUs, GPUs, ASICs.

For a rough comparison, assume that the peak is achieved with Nvidia RTX 2080 and

• KeePass 1 is using AES with 6000 iterations and that can reach $k = 152.1$ kH/s.
• Hasmode 1410 uses SHA256 and can achieve $t = 5380.8$ MH/s.

$ratio = t/k = 35376.7 \approx 2^{15}$ and with double SHA256 that is $2^{16}$

To sum up; a power like the collective bitcoin miners can reach $2^{118}$ per year. This is beyond the security requirement. One can argue that ordinary people are not the target to break. A counter-argument is then why secure at all.

Multi-target attack

The real threat is still coming from the multi-target attack. With known-plaintext with different encryption keys than with a multi-target attack, you can find some keys faster.

For $t$ targets by using Oechslin's rainbow tables, and $p\geq n^2$ ways parallelized machine, the expected cost of recovering the first of $t$ keys is $2^{112}/t$, the expected time is that of $2^{112}/np$ sequential evaluations of algorithm. The total expected cost for breaking all of the $t$ keys is still close to $2^{112}$.

If $t$ is a billion target and one can run $p =2^{16}$ parallel machines than the cost of finding the first key is $2^{73}$ and the time is $2^{64}$ and this is quite achievable. Depending on the case, compromising one of the network users may compromise all.

This is why we say use AES256, not AES128.

Note that this answer is written in order to see that the 112 is not far away from 3-word agencies. It seems like the DES, with money one can search the key

And keep in mind that there is a difference between searching 122 bits and having 112-bit of security from 128 bits. The above search attacks may not execute the pure 112 bit instead they need to search within 128 bits. in any case, the multi-target attack still the problem!

Or, the history doubles $$112 = 56 \cdot 2$$