9
$\begingroup$

In an article about NIST Post-quantum Standardization project I read about the security criteria of the proposed schemes and there was this table (Level I lowest security, level V highest):

Level I: At least as hard to break as AES-128 (exhaustive key search)

Level II: At least as hard to break as SHA-256 (collision search)

Level III: At least as hard to break as AES-192 (exhaustive key search)

Level IV: At least as hard to break as SHA-384 (collision search)

Level V: At least as hard to break as AES-256 (exhaustive key search)

If I understand it correctly, then (in classical way, not using quantum computers and the Grover's algorithm) for exhaustive key seach on AES-128 we need to go through $2^{128}$ possibilities and in collision search of SHA-256 we need to go through $2^{128}$ possibilities to find a collision (thx to the Birthday paradox).

So my question is - how does the security Level I and Level II differ? And the same - why is security of AES-192 lower than security of SHA-384.

$\endgroup$
0

1 Answer 1

18
$\begingroup$

This is due to the Brassard et al.'s method on hash functions. That has $\mathcal{O}(\sqrt[3]{n})$ attack time for n-bit hash function where as the Grover's method has $\mathcal{O}(\sqrt{n})$-time.

  • Level I: At least as hard to break as AES-128 $\mathcal{O}(\sqrt{2^{128}}) = \mathcal{O}(2^{64})$ - by Grover
  • Level II: At least as hard to break as SHA-256 $\mathcal{O}(\sqrt[3]{2^{256}}) \approx \mathcal{O}(2^{85})$ - by Brassard et al.
  • Level III: At least as hard to break as AES-192 $\mathcal{O}(\sqrt{2^{192}}) = \mathcal{O}(2^{96})$ - by Grover
  • Level IV: At least as hard to break as SHA-384 $\mathcal{O}(\sqrt[3]{2^{384}}) = \mathcal{O}(2^{128})$ - by Brassard et al.
  • Level V: At least as hard to break as AES-256 $\mathcal{O}(\sqrt{2^{256}}) = \mathcal{O}(2^{128})$ by Grover

The space-time comparisons of the two quantum hash collisions methods.

\begin{array} {|c|c|}\hline & \text{time} & \text{space} \\ \hline \text{Grover} & \mathcal{O}(\sqrt{n}) & \mathcal{O}(\log{n}) \\ \hline \text{Brassard et al.} & \mathcal{O}(\sqrt[3]{n}) & \mathcal{O}(\sqrt[3]{n}) \\ \hline \end{array}

Bernstein has a nice article "Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete" about comparison with parallelized van Oorschot–Wiener. You can also read Squeamish Ossifrage's answer.

$\endgroup$
5
  • 8
    $\begingroup$ Note that, while this answer is correct (in that this is the reasoning used by NIST, and are provable lower bounds), it's not clear if attacks with this listed work effort is achievable. Attacking AES128 with Grover's in $2^{64}$ time requires circa $2^{64}$ successive AES evaluations; that may not be achievable in a reasonable time (and similar results against AES192 is certainly not achievable). As for Brassard, the attack requires a huge Quantum circuit, and if you have the budget for it, implementing multiple SHA circuits would give faster results (if increase the number of SHA comps) $\endgroup$
    – poncho
    Oct 22, 2019 at 13:26
  • $\begingroup$ What would be the cost of mounting such a computer to run Grover's algorithm on i.e AES-128? Moreover, what would be the time expectancy to have such a prepared quantum computer? I know these questions cannot be answerd with a concrete reference as it's something that doesn't exist, yet but I'd like to know your opinion. $\endgroup$
    – kub0x
    Oct 22, 2019 at 16:12
  • 1
    $\begingroup$ Now we have comparative equality between IV and V. Some explanation why that is happening and why AES-256 is considered to be more secure than SHA-384 seems required for understanding the levels. $\endgroup$
    – Maarten Bodewes
    Oct 22, 2019 at 17:16
  • 3
    $\begingroup$ @MaartenBodewes it is hidden under the Big-Oh constants. Brassard $r$-to-one functions after only $O((N/r)^{(1/3)})$, in general the $r$ is omitted due to being constant. $\endgroup$
    – kelalaka
    Oct 22, 2019 at 17:45
  • 3
    $\begingroup$ @kub0x: some imponderables with the cost of breaking AES-128: how much does a QC cost? How many AES evaluations can a QC perform in the allowed time frame of the attack? And, these do not interact in the obvious manner; if a QC can perform $2^{50}$ AES evaluations in a year (and you need the attack to succeed in a year), then you'll need $2^{28}$ (not $2^{14}$) Quantum Computers to do a full key space search... $\endgroup$
    – poncho
    Oct 23, 2019 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.