# How many encryptions are needed before OpenPGP key privacy is violated?

According to an excellent answer describing the pitfalls of key privacy in OpenPGP:

Theoretically, an all-zero key ID can be used as a way to discourage traffic analysis, but this is not a complete solution. For instance, with RSA keys, the packet still contains an integer between 0 and n-1, with n being the RSA modulus, with a fairly uniform distribution. Thus, observing many messages can yield, statistically, the first (most significant) few bytes of that modulus, which can be used to discriminate recipients from each other.

For an RSA key with an $$n$$-bit modulus, how many messages must be encrypted with that public key before it can be distinguished from $$k$$ other keys of the same size with non-negligible probability?

• Is the question OpenPGP specific? If so, we must be considering a variation of OpenPGP where the ID of the sender no longer is disclosed in clear, as is the case normally (that's mentioned in the beginning of the quote). While we are at changing OpenPGP, we can consider a variation of the key generation procedure where the say 256 high-order bits of the public modulus $n$ are fixed to a haphazard constant, which makes RSA cryptograms indistinguishable from each others. – fgrieu May 17 at 5:19
• @fgrieu Most OpenPGP implementations support a zeroed key ID, including GnuPG and OpenPGP.js. – forest May 17 at 20:44

## 1 Answer

I'll leave alone the OpenPGP spec, and consider the problem of identifying among $$k$$ public keys $$(n_i,e_i)$$ the RSA public key $$(n_j,e_j)$$ used to encrypt $$m$$ messages per RSA with proper encryption padding. The only way is by examining the $$m$$ cryptograms $$c_\ell$$, which essentially are indistinguishable from uniformly random in $$[0,n_j)$$ (I assume the $$c_\ell$$ are computed with no countermeasure to foil identification attempts, except in last section).

An identification algorithm can use two facts:

1. If $$n_i\le\max c_\ell$$ , that rules out $$i=j$$.
2. The mean $$x=\frac1m\sum c_\ell$$ , which the attacker should compute, has Bates distribution, with mean $$(n_j-1)/2$$, standard deviation $$(n_j-1)/\sqrt{12m}$$. That distribution quickly becomes close to normal when $$m$$ increases, and the 68-95-99.7% rule quickly becomes applicable.

I think the optimum attacker's strategy in practice is to pick $$j$$ as $$i$$ with $$n_i/2$$ closest to $$x$$ among the $$n_i$$ surviving test 1. It's possible to estimate the confidence in a guess by computing $$t_i=\lvert n_i/2-x\rvert\sqrt{12m}/n_i$$ for the values of $$i$$ with $$n_i/2$$ the closest to $$x$$: the higher $$t_i$$, the less likely $$i$$ is (ignoring information obtained from other $$n_i$$): $$t_i>1$$ with 32% probability, $$t_i>2$$ with 5% probability, $$t_i>3$$ with 0.3% probability.

To go deeper in the analysis, we need an idea of the distribution of the $$n_i$$.

By making the say 256 high-order bits of the $$n_i$$ equal at generation time (fixed to some haphazard constant), which is easy and does not harm RSA security or interoperability, we could make identification hopeless.

For a common generation method with the prime factors $$p_i$$ and $$q_i$$ of $$n_i$$ independent and roughly uniform in $$[2^{(b-1)/2},2^{b/2}]$$ where $$b$$ is the bit size of $$n_i$$ (e.g. $$b=3072$$), I think an attacker would need $$m$$ in the order of a few times $$k^2$$ for a good success rate, and significantly more to conclude with good success rate and confidence for most users. Keys with the highest $$n_j$$ tend to be easier to guess correctly, because rule 1 prunes best, and there tends to be less other keys with nearby $$n_i$$. The second effect also makes keys with the lowest $$n_j$$ easier to guess than those in the center of the pack: those with the high byte in [0xB0,0xC1] (for $$b$$ multiple of 8) tend to be the most resistant to guessing, while giving no strong sign they have been chosen for this purpose.

All this is amenable to simulation and detailed analysis. I called for help. In the desert so far.

Update: this comment by Squeamish Ossifrage points a relevant paper: Jean Paul Degabriele, Victoria Fehr, Marc Fischlin, Tommaso Gagliardoni, Felix Günther, Giorgia Azzurra Marson, Arno Mittelbach and Kenneth G. Paterson: Unpicking PLAID - A Cryptographic Analysis of an ISO-standards-track Authentication Protocol, in proceedings of SSR 2014. Start with section 3.1 Tracing Cards via Shill-Key Ciphertexts.

I'm told a simple and clearly correct countermeasure to foul identification attempts even if we don't want to change pre-existing $$n_i$$ of the same bit size $$b$$: pick the first RSA cryptogram below $$2^{b-1}$$. Adversaries will be facing a uniformly random integer in $$[0,2^{b-1})$$.