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= 40ericsson....@dmarc.ietf.org> 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 <d...@cr.yp.to> > *Date: *Friday, 29 August 2025 at 19:47 > *To: *tls@ietf.org <tls@ietf.org> > *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 -- tls@ietf.org > To unsubscribe send an email to tls-le...@ietf.org > _______________________________________________ > TLS mailing list -- tls@ietf.org > To unsubscribe send an email to tls-le...@ietf.org > -- Sophie Schmieg | Information Security Engineer | ISE Crypto | sschm...@google.com
_______________________________________________ TLS mailing list -- tls@ietf.org To unsubscribe send an email to tls-le...@ietf.org
