[TLS] Re: Concerns about the current draft.

[Sophie Schmieg <[e-mail]>]

Yes, technically you can parallelize Grover's you just lose the quadratic
speedup, so it is not a very appealing tradeoff.

As for multiuser attacks, those only apply in a situation where the same
plaintext is encrypted with a block cipher by multiple users. In other
words, the attack only applies to deterministic modes such as AES-CMAC,
AES-SIV or AES-ECB. And I do indeed not recommend using AES128-CMAC,
AES128-SIV, or AES128-ECB (or AES256-ECB for that matter), in order to
account for multiuser attacks. For the usage in TLS in particular, the IV
is the xor of the sequence number and a per connection static IV, so
multiuser attacks do not apply.

On Fri, Aug 29, 2025 at 11:17 AM John Mattsson <john.mattsson=
[e-mail]> wrote:

> Sophie Schmieg wrote:
> > As Bas mentioned, there is currently no indication that Grover's
> algorithm can practically break AES-128 any time soon.
> Completely agree.
>
> >Grover's algorithm is inherently sequential, and cannot be parallelized,
>
> Cannot be _*effectively*_ parallelized would be a more theoretically
> correct statement. But practically, Grover’s algorithm will never be used
> for breaking AES-128. Quantum computers will also remain much slower and
> much more expensive than classical computers. Anybody claiming Grover's
> algorithm is a threat to any cryptography should provide detailed
> calculation of the cost, size, and time. With realistic assumptions you end
> up with result like “a huge cluster of one billion CRQCs (according to one
> estimate costing one billion USD each) would take a million years of
> uninterrupted calculation to find a single AES-128 key” or “require
> qubits covering the surface area of the Moon”.
>
> https://datatracker.ietf.org/liaison/1942/
>
> https://www.youtube.com/watch?v=eB4po9Br1YY&t=3227s
>
>
> John
>
> *From: *D. J. Bernstein <[e-mail]>
> *Date: *Friday, 29 August 2025 at 19:47
> *To: *[e-mail] <[e-mail]>
> *Subject: *[TLS] Re: Concerns about the current draft.
>
> Sophie Schmieg writes:
> > Grover's algorithm is inherently sequential, and cannot be
> > parallelized, making the standard approach of throwing more compute at
> > the problem to scale up infeasible.
>
> One can split the search space across many parallel quantum processors
> and run a smaller Grover search on each part of the space, as noted in,
> e.g.,
> https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Farxiv.org%2Fabs%2Fquant-ph%2F0309123&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7Ce91ec897b40744e464bc08dde72429dd%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638920864700657440%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=haVw1vVYALl5qAbq7VJPRciy2fAjPgrA0NEuAVbxyiY%3D&reserved=0
> <https://arxiv.org/abs/quant-ph/0309123> from Grover and Rudolph.
>
> To some extent it's possible to combine this with multi-target attacks.
> See
> https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fcr.yp.to%2Fpapers.html%23groverrho&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7Ce91ec897b40744e464bc08dde72429dd%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638920864700717818%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=CK8nBl6TfEM5LwY%2Fznl7KgJjT0x4dNiUG4IeSL7xf4s%3D&reserved=0
> <https://cr.yp.to/papers.html#groverrho>.
>
> Even without quantum computers, 2^40-target attacks against AES-128 are
> already a feasible computation today for large-scale attackers. One can
> try to stop these attacks by having every AES-128 application randomize
> every input block, but we keep seeing people screw this up. This is the
> sort of thing that _probably_ ends up working for TLS, but it's fragile,
> and the broader habit of tolerating this sort of fragility is certainly
> a big factor in the problems that we _have_ seen in TLS.
>
> I agree that the Grover speedup compared to non-quantum searches comes
> from the number of serial iterations carried out on each processor, and
> meanwhile this has to fight against the quantum-computation overhead---
> which could end up as 2^30 or 2^40; we don't know yet. But this doesn't
> makes AES-128 a safe option: on the contrary, tolerating AES-128 will
> end up compromising the confidentiality of some user data.
>
> > confirmed the infeasibility of Grover's in at least the
> > medium term of several decades to centuries
>
> I see no basis for this claim.
>
> > the reason for ECC + lattice based hybrids are becoming less
> > compelling with every day that passes in which lattices do not get
> > broken
>
> One of the talks at Crypto 2025 last week said that none of the Kyber
> parameters meet their claimed security levels.
>
> ---D. J. Bernstein
>
> _______________________________________________
> TLS mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
> _______________________________________________
> TLS mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>


-- 

Sophie Schmieg | Information Security Engineer | ISE Crypto |
[e-mail]