2022.07.31 13:06:04 (1553698503460671488) from Daniel J. Bernstein:
It's easy for people to issue security warnings _after_ systems are broken. What takes much more work is _proactively_ analyzing risks deeply enough to issue meaningful warnings _before_ systems are broken. Here's a 2021 example, disputing the "case for SIKE" security analysis. https://twitter.com/hashbreaker/status/1387779717370048518
2022.07.31 13:12:05 (1553700018799779840) from Daniel J. Bernstein:
How is it possible that in 2021 there were "recent advances in torsion-point attacks" vs SIKE, while in 2022 one can find claims that there was "no attack progress" against SIDH/SIKE for a decade? There's an important lesson here about metrics for attack advances. Let me explain.
2022.07.31 13:19:45 (1553701949299572736) from Daniel J. Bernstein:
There are some famous long-standing algorithmic problems for which there have been many attack advances and extensive evidence regarding how the advances developed. Let's take (non-quantum!) factorization as an example highlighted and studied by Gauss and many other researchers.
2022.07.31 13:30:37 (1553704683339784194) from Daniel J. Bernstein:
How do we measure whether a factorization algorithm is better than previous algorithms? This is an important question. We don't want useless ideas to produce excitement for the attacker or fear for the defender; at the same time, we need to recognize and encourage useful ideas.
2022.07.31 13:35:30 (1553705910693859329) from Daniel J. Bernstein:
So, okay, let's pull out the computer and try factoring random n-bit RSA moduli pq with many different factorization algorithms for various sizes of n. This immediately gives interesting information: one can easily see Pollard rho beating trial division, MPQS beating QS, etc.
2022.07.31 13:44:13 (1553708107355762691) from Daniel J. Bernstein:
If algorithm X factors random RSA moduli faster than all previous algorithms then certainly X is an advance. This is a useful metric. But let's look at what goes wrong if we take this as the _only_ metric, dismissing any factoring algorithms that don't reduce RSA security levels.
2022.07.31 13:48:32 (1553709191876857857) from Daniel J. Bernstein:
Pollard's p-1 algorithm established speed records for factoring _occasional_ integers. Basically, pq is vulnerable when p-1 or q-1 is a product of very small primes. It's easy to show that n-bit RSA moduli pq are extremely unlikely to be vulnerable to this unless n is very small.
2022.07.31 13:59:01 (1553711829712457729) from Daniel J. Bernstein:
In other words, Pollard's p-1 algorithm doesn't apply to worst-case factorization. But it inspired followups replacing p-1 (from the multiplicative group) with other functions of p (from other groups). In particular, it inspired Lenstra's ECM (using elliptic-curve groups).
2022.07.31 14:03:56 (1553713069242454016) from Daniel J. Bernstein:
ECM _does_ apply (under conjectures backed by extensive evidence) to the worst case. It's a tremendously powerful attack against RSA moduli. For (say) RSA-1024, NFS is (conjecturally) even faster, but modern versions of NFS save time using ECM as a "cofactorization" subroutine.
2022.07.31 14:13:27 (1553715460184494085) from Daniel J. Bernstein:
Should Pollard's p-1 algorithm have been dismissed because it was useful only for occasional numbers? Of course not. The algorithm was setting speed records for some factorization problems. Algorithms for general problems are often outgrowths of algorithms for special cases.
2022.07.31 14:19:26 (1553716968586285056) from Daniel J. Bernstein:
Is it interesting that the selected SIKE parameters maintained their security level (aside from small VoW inner-loop improvements) for a decade? Definitely. But using that as the only metric is a mistake. Torsion-point attacks were ripping more and more SIKE parameters to shreds.
2022.07.31 14:44:57 (1553723387851067392) from Daniel J. Bernstein:
At first glance the new SIKE attack looks like a spectacular advance. But the previous work was important too! People leaping from "SIKE is maintaining its security level" to "there is no progress in SIKE attacks" were making a mistake, misextrapolating from a limited metric.
2022.07.31 15:10:52 (1553729909670809600) from Daniel J. Bernstein:
There's more to say about how to measure special cases and use this for cryptographic risk assessment. But the starting point is to recognize that _ignoring_ special-case attacks, such as Pollard's p-1 method or previous torsion-point attacks, is a dangerous oversimplification.
2021.04.29 16:44:02 (1387779717370048518) from Daniel J. Bernstein:
Agreeing with main points in 3, 4, 6, 10 in https://eprint.iacr.org/2021/543. More objections to 2, 5, 7, 9. Most important dispute is regarding risk management, 1+8. Recent advances in torsion-point attacks have killed a huge part of the SIKE parameter space, far worse than MOV vs ECDLP.