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
    $\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$ – Ruben De Smet Feb 22 at 11:29
  • $\begingroup$ Do you need your own or could you use the (32-bit) ones already found? $\endgroup$ – dave_thompson_085 Feb 23 at 2:22
  • $\begingroup$ I believe the pqRSA paper gives some information on optimizing batch prime number generation. $\endgroup$ – forest Feb 23 at 10:06
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$
  • $\begingroup$ +1 for the idea of changing only the timestamp! $\endgroup$ – fgrieu Feb 22 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$ – Gilles Feb 22 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$
  • $\begingroup$ I liked the "other speedup techniques". I'm glad they're still in the revision history. $\endgroup$ – ddddavidee Feb 22 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$ – Squeamish Ossifrage Feb 23 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 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$ – Squeamish Ossifrage Feb 23 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 at 19:01

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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