How are NIST Security strength in terms of classical gates specified in PQC project derived?

Question

For the NIST PQC standardization project, the computational resources to break are specified by NIST as :-

1. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 128-bit key (e.g. AES128)
2. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 256-bit hash function (e.g.SHA256/ SHA3-256)
3. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 192-bit key (e.g.AES192)
4. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 384-bit hash function (e.g.SHA384/ SHA3-384)
5. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 256-bit key (e.g. AES 256).

Which they then list out in terms of gate counts as:

• AES-128: 2^170/MAXDEPTH quantum gates or 2^143 classical gates
• SHA3-256: 2^146 classical gates
• AES-192: 2^233/MAXDEPTH quantum gates or 2^207 classical gates
• SHA3-384: 2^210 classical gates
• AES-256: 2^298/MAXDEPTH quantum gates or 2^272 classical gates
• SHA3-512: 2^274 classical gates

The quantum gate counts seems to have been produced from this paper: [M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwandt, Applying Grover’s algorithm to AES: quantum resource estimates, in T. Takagi, editor, Post-Quantum Cryptography, Lect. Notes in Comput. Sci. vol. 9606, Springer, pp. 9–43 (2016)].

But they don't give a reference to how classical gates counts are being derived.

Answer 1

Although references are not give, it's not hard to construct an approximation to the figures. The smallest gate counts necessary to implement AES and SHA3 are an open area of research, and some variation is inevitable.

For the AES counts, this represents an exhaustive "brute force" attack on the key space. For 128-bit keys, evaluating the cipher on the full key space will take $2^{128}$ encryption operations with an expected tome to success of $2^{127}$. The grain of sand implementation of AES required $3400$ gate equivalents, which if looped over for ten rounds would be roughly $34000\approx 2^{15}$ gate equivalents. This suggest that the figure $143=128+15$ is not unreasonable. Likewise for 192-bit keys (12 rounds, $40800\approx 2^{15.3}$ GE) $207=192+15$ and for 256-bits keys (14 rounds, $47600\approx 2^{15.5}$ GE) $272=256+16$ feels about right.

For the SHA3 gate counts, we expect to require $\sqrt{\pi H/2}$ hash function evaluations where $H$ is the hash function output size. This is roughly $2^{128.3}$ for level 2, $2^{192.3}$ for level 4, $2^{256.3}$ for level 6. Bernstein quotes a $47434$ GE implementation of Keccak-256, which over 24 rounds would give $2^{19.1}$ gates. The figure 147.4 feels close enough to 148.