1
$\begingroup$

Is there a way to generate thousands of PGP keys at a very very fast rate?

I am generating thousands of 3072-bit PGP keys looking like part of a personal research project. Obviously, this is a very slow, CPU intensive activity. I have turned off strong randomization with the --debug-quick-random, am generating them using --batch and maxed out all of my personal CPUs. But this is still not fast enough.

Is there a way to generate perhaps thousands of keys very rapidly? My goal is to get a 16-bit hash collision on the KeyID. I know this is entirely impractical for real security, this is mostly for research purposes. I have not reviewed the GnuPG code, but I am trying to avoid writing any code just yet.

Thanks!

$\endgroup$
3
  • 3
    $\begingroup$ Do you require to have RSA keys? ECC keys can be generated much faster, and they're supported in the more recent versions of GPG. $\endgroup$ Feb 22, 2019 at 11:29
  • $\begingroup$ Do you need your own or could you use the (32-bit) ones already found? $\endgroup$ Feb 23, 2019 at 2:22
  • $\begingroup$ I believe the pqRSA paper gives some information on optimizing batch prime number generation. $\endgroup$
    – forest
    Feb 23, 2019 at 10:06

2 Answers 2

4
$\begingroup$

To generate keys faster than you are doing right now probably requires to add a faster source of random numbers to your system. You could look at the extensions available in your CPU and checking if they are enabled or not on your system.


If you are only interested in looking for collision on key ID, you'd probably proceed differently.

fingerprint = hash(public_key)

public_key = timestamp + public_key_data

Therefore:

fingerprint = hash(timestamp + public_key_data)

There's a script that manipulate only the timestamp looking for a collision. https://github.com/micahflee/trollwot

$\endgroup$
2
  • $\begingroup$ +1 for the idea of changing only the timestamp! $\endgroup$
    – fgrieu
    Feb 22, 2019 at 8:41
  • 3
    $\begingroup$ RSA key generation is slow. When the input is an ordinary PRNG (as is the case with gpg --debug-print-random, as opposed to using Linux's /dev/random), the RNG is not the limiting factor, it's the (pseudo-)primality tests. $\endgroup$ Feb 22, 2019 at 13:40
2
$\begingroup$

Yes.

As rightly pointed in the first answer, we can make keys with identical public-key parameters but a different timestamp, which makes computing a fingerprint very fast. That seems by far the fastest/best to create collisions.

We create $k\ge2$ keys (say 16), compute fingerprints with varying timestamps, find a collision, and check that they are not with the same key (which as probability $1/k$). We can use the techniques in Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999 to make that search with only little memory, and several independent devices (or independent data streams in SIMD/GPU computing).

In retrospect, PGP/GPG key fingerprint should have used a purposely slow hash rather than plain SHA-1. At least, something like PBKDF2; nowadays we'd use Argon2(id?), or Balloon Hashing.

I previously came up with speedup techniques, which are not useful for the task at hand. They RIP there.

$\endgroup$
6
  • $\begingroup$ I liked the "other speedup techniques". I'm glad they're still in the revision history. $\endgroup$
    – ddddavidee
    Feb 22, 2019 at 9:36
  • $\begingroup$ It's not clear to me that there would be more value in using argon2 or whatever than in simply ditching the notion of short key ids in favour of consistently using full key fingerprints. $\endgroup$ Feb 23, 2019 at 16:35
  • $\begingroup$ @Squeamish Ossifrage: full key fingerprints are SHA-1 hashes. That's vulnerable to collision (not preimage, fortunately). $\endgroup$
    – fgrieu
    Feb 23, 2019 at 18:11
  • $\begingroup$ @fgrieu It's not clear to me that collision attacks on PGP key fingerprints are relevant as PGP is more or less intended to be used by humans! $\endgroup$ Feb 23, 2019 at 18:50
  • $\begingroup$ @Squeamish Ossifrage Show two colliding keys to a human that is not a cryptographer and s/he wont trust fingerprints anymore. $\endgroup$
    – fgrieu
    Feb 23, 2019 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.