GnuPG patch: long fingerprints using PGP biometric word lists

[Paul Crowley]

Detlef Lannert <lannert-gpgspam@lannert.rz.uni-duesseldorf.de> writes:
> As a compromise you could convert the fingerprint into a base-26
> number coded as letters and pronounced according to the "Alpha-Bravo-
> Charly" alphabet already mentioned in this thread. OK, that's still
> 35 words instead of 20 with the NAI wordlist (or 40 hexadecimal
> digits). But the words are well-known to far more people around the
> world. And they are shorter.

In practice 20 words would be enough; an attacker wishing to generate
a keypair that matched such a fingerprint would have to generate an
expected 2^94 keypairs before finding a match.

I contend that this raises no internationalisation issues since
Alpha-Bravo-Charlie is an international standard.  I certainly can't
see that ABCDEF are more international when used to represent hex than
they are as letters.

We can make this even more effective by making the fingerprint, say,
16 numbered groups of 6 letters.  Rather than asking me to read the
whole lot out, though, GPG will prompt me to read, say, three randomly
selected groups.

Now the work for an attacker wanting to be certain their key will pass
this test is 26^(16*6) ~= 2^451.  They could try and cut down this
work and produce a key that matches in only some groups, say the first
four, and hope you only ask for groups within that "lucky subset".
Here's how the attacker's chances go:

3 matches: work 75.4786319096 , probability of success 0.00178571428571
4 matches: work 101.9808305 , probability of success 0.00714285714286
5 matches: work 128.920434403 , probability of success 0.0178571428571
6 matches: work 156.248603594 , probability of success 0.0357142857143
7 matches: work 183.93666873 , probability of success 0.0625
8 matches: work 211.969382038 , probability of success 0.1
9 matches: work 240.341945348 , probability of success 0.15
10 matches: work 269.05915683 , probability of success 0.214285714286
11 matches: work 298.136264256 , probability of success 0.294642857143
12 matches: work 327.601936971 , probability of success 0.392857142857
13 matches: work 357.505014998 , probability of success 0.510714285714
14 matches: work 387.930045728 , probability of success 0.65
15 matches: work 419.039574633 , probability of success 0.8125
16 matches: work 451.242212942 , probability of success 1.0

Now, 2^90 is generally considered a sufficient workfactor to render an
attack impractical.  That's generous, since generating a keypair is
much more expensive than testing a keyguess against a secret key
cipher.  Certainly, generating a key that has a better than 1% chance
of passing this challenge will be more expensive than brute-forcing
IDEA.  But anyway, if you're really paranoid, you might worry that the
NSA will devote all of their acres of supercomputers to generating a
key that has less than a 1 in 500 chance of passing.  In that case,
ask GPG for *four* challenges, and suddenly their work looks like
this:

4 matches: work 101.9808305 , probability of success 0.000549450549451
5 matches: work 128.920434403 , probability of success 0.00274725274725
6 matches: work 156.248603594 , probability of success 0.00824175824176
7 matches: work 183.93666873 , probability of success 0.0192307692308
8 matches: work 211.969382038 , probability of success 0.0384615384615
9 matches: work 240.341945348 , probability of success 0.0692307692308
10 matches: work 269.05915683 , probability of success 0.115384615385
11 matches: work 298.136264256 , probability of success 0.181318681319
12 matches: work 327.601936971 , probability of success 0.271978021978
13 matches: work 357.505014998 , probability of success 0.392857142857
14 matches: work 387.930045728 , probability of success 0.55
15 matches: work 419.039574633 , probability of success 0.75
16 matches: work 451.242212942 , probability of success 1.0

This gives us much better leverage of "work for the verifiers" against
"work for the attacker".

If our attackers are allowed to do things like record our voices and
try and stitch together convincing-sounding readings, then the
protocol we use over the phone has to be carefully worked out, but I
think the fundamental idea is sound.
-- 
  __
\/ o\ sig@paul.cluefactory.org.uk
/\__/ http://www.cluefactory.org.uk/paul/