There was an interesting paper by Peter Gutmann, provocatively titled “Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog”, which I was led to from an article in “The Register”. One useful takeaway from this: if you hear a claim that some Quantum Computer has factored a product of 2 primes, ask how close those two prime factors were to each other :-) (That’s the simplest “Stunt Cryptography” trick discussed in the paper, but there’s more).
According to the Register article, Gutmann says Quantum Computers (which he calls “physics experiments”), have not managed to factor any number greater than 21 without cheating.
The cheat that is easiest to describe, consists of using 2 primes that are very close to each other. Since computing the square root of an integer (however large) is trivial, this allows an easy brute force search starting from that square root! (The article also mentions that this is why standards such as FIPS 186 require that they differ by at least 100 bits). This does not even use Shor’s algorithm, so how does it prove anything at all?
The actual paper of course has several other examples (some of which I even understood!), and section 7 of the paper lists a set of simple rules to prevent this kind of cheating. Most telling is the comment that “It should be noted here that all of these sleight-of-hand and stunt values are trivially factorised by Fermat’s method on a Raspberry Pi or similar.”
Some interesting quotes (again, quite provocative):
Gutmann also mentions that a lot of the money being spent on PQC would be better spent on fixing existing problems. This part of his rant comes from his vast experience, awesomely shown in his 2014 book, “Engineering Security”, a truly mammoth work at 814 pages, with both scary as well as funny examples peppered throughout. While some of the examples in that book may not have stood the test of time, the general principles shown still apply. (Sadly!)
But enough bad news; I’ll end with some funny examples from his book.
(on subjecting users to error messages): “Something that you never knew existed has failed in a manner that you’ll probably never understand, click OK to continue”.
(speaking of a very hard-in-practice attack): “However if you don’t address the issue then someone will publish a conference paper saying that you’re vulnerable (a so-called conference-paper attack) so it’s a good idea to try and defend against it anyway”
(on threat modelling): “So how do you build a realistic threat model for your application? The traditional way to do this, if it was done at all, was to sit down and think up attacks until you got bored (often ones that your application defended against anyway) and then declare victory. If you have non-security geeks doing the threat modelling then many attacks get missed or mis-identified, and if you have security geeks involved then they tend to focus on attacks like sending a server custom-crafted messages that take advantage of the unusual mathematical properties of specially-formatted PKCS #1 message padding in RSA-encrypted data blocks and ignore the fact that the server’s private-key file is world-readable and indexed by Google.”
Picture credit: https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf, slide 21.