Multiple issues in GPG documentation

[Robert J. Hansen]

> Number 1 is a bad idea. Some services still support legacy ciphers for
> backwards comparability.

I disagree; I think #1 is essential. If I don't know what cipher suites 
the recipient supports, I have no way of knowing whether secure 
communications are even possible. Knowing what the recipient supports is 
essential -- as is keeping one's own set of supported ciphers to a 
known-strong set. The intersection of "what am I willing to use?" and 
"what does the recipient support?" results in a set of mutually 
agreeable ciphers, of which any one may be chosen.

(This has an analogue in the algorithmic analysis and design community, 
where it's called the Stable Marriage Problem. GnuPG's algorithm for 
choosing which cipher to use is straight out of the weighted-preference 
SMP. https://en.wikipedia.org/wiki/Stable_matching_problem

The stable marriage problem is a variant of the stable matching problem. 
And yes, I'm right about it being an instance of stable marriage, and 
that stable matching is the wrong way to think about it. And no, here is 
the wrong place to argue with me on it, because (a) you'll be wrong and 
(b) you'll be off-topic. Discussion about how GnuPG implements the SMP 
is quite okay, though!)

> I think that is a bit technical for an FAQ. Quantum computing is still
> an active field of research, and it will likely be quite some time
> before current algorithms are broken.

If ever.

While in graduate school I did a fair bit of research into quantum 
computing. I'm in no way still current on the state of quantum 
engineering -- that's improved by leaps and bounds since I last looked 
at it -- but the limitations of quantum mathematics are a little more 
solid in their foundations.

Breaking RSA by brute force requires what, 5n logical qubits for each 
bit of the modulus? Something like that. So breaking RSA-2048 with a 
quantum computer requires a minimum 10kqb ensemble. (*Minimum*. A 
logical qubit normally requires many more qubits for error correction. A 
10n or 15n parameter is not unreasonable.) Our current ensembles are a 
minute fraction of that. Nobody knows how to scale it up.

As of ... what, two years ago, I think ... Arqit Networks, a UK-based 
quantum cryptography firm, told me they expected RSA-2048 to be 
susceptible to Shor's algorithm within five years. I pointed out this 
would require doubling the current state-of-the-art in ensemble size 
every 78 days for five years straight. In the time since, I don't think 
the ensemble size has doubled more than once.

RSA-2048 is under much greater risk from cloud computing and the general 
number field sieve than it is from quantum computing.

(Friends don't let friends generate new RSA-2048 keys, incidentally. I'm 
not kidding about the cloud and GNFS risks.)

For symmetric computing it's just as ridiculous. Grover's algorithm lets 
you search a database of N entries in root-N time. This means a 128-bit 
cipher with 2**128 possible keys can be brute-forced in 2**64 time. 
Assuming you've got the science fiction technology needed to implement 
Grover's, okay, 128-bit ciphers might be breakable.

So what? This is why we use 256-bit ciphers like AES, Camellia, and 
Twofish. Yes, Grover's reduces the effective keyspace to 'merely' 
2**128. That's still a completely impractical amount of computation: 
brute-forcing that would require (*require*: we can prove this using 
thermodynamics) you to liberate more heat than a nuclear bomb. This 
would have dire implications for your data center, so no, we're not 
particularly worried about quantum algorithms attacking modern 256-bit 
ciphers.

> The worry about quantum computers is because of their theoretical
> ability to efficiently perform integer factorization and solve the
> discrete logarithm problem [4].

If anyone is wondering how they can tackle two different kinds of 
cryptographic problems simultaneously --

They're not really all that different. They're both instances of the 
hidden subgroup problem as applied to finite Abelian groups. You can 
convert one into the other in polynomial time.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_signature.asc
Type: application/pgp-signature
Size: 236 bytes
Desc: OpenPGP digital signature
URL: <https://lists.gnupg.org/pipermail/gnupg-users/attachments/20250913/32c7b00f/attachment.sig>