Re: Check for revocation certificates before running apt-get?

[Florian Weimer <fw@deneb.enyo.de>]

* Kurt Roeckx:

> On Sun, Dec 15, 2013 at 03:15:03AM +0000, adrelanos wrote:
>> > When you implement this, please ensure it isn't vulnerable to any
>> > duplicate-keyid problems:
>> > 
>> > http://debian-administration.org/users/dkg/weblog/105
>> 
>> Damn, I wasn't aware of the latest news that long key ids are now also
>> insecure. Thank you for educating me.
>
> I think this really shouldn't suprise someone, and I think
> we've really been saying this for like 10 years.  Please note
> that the "long key" is the last 64 bit of the fingerprint,
> not the whole 160 bit of the SHA-1.

It's even worse.  For v3 keys, the long key ID consists of the lowest
64 bits of the modulus.  If the long key ID happens to be odd, you
just have to generate a prime which is congruent 1 modulo 2**64, and
another prime that is congruent the desired long key ID, which is not
that much work (it's about as expensive as regular key generation).
For even key IDs, this wouldn't work if GnuPG has additional checks,
but I doubt it.

Here's an example RSA modulus colliding with one of my keys:

p = a9df775e62100ec6c2b458cb5729993233d513545d680ed1f90f6bf308414fe31d9d66ec36868bd6d4beb7fa93a1b02cf932f4ca8f43fe10b23f4275a1608ea884a4a4a7d2918c78230127f0e3311eecc165145e88a5053daa4c573a8e7499b9664353f3eb0225f2c499e26a0624bb8d7797b5f8b93f23f20000000000000001
q = 62a70bf7a9a2f67616d364445798ba57af4674473d0d6b4fe9921f3da54fb8c4ead803998f0a1ad0f712822d119c5397741e5c295c1a272b81939d81bdbfe0c1f29004b016238a5a78e7d0aba031cd6d308da89ff71f5a17fa8a6a5abdcb8dab42b7f3bb581ccc331c1e7768972885a1ecfc8dc84210d67863a9c78a56a3416b
n = 41766469f16a012af9a4b368b51556f597eb2be0230df06596acbfa58bd3ff67be6d507b259528c1ebad126f8fe7d1d30244cae74c63173edddcd7476ba7209da6d7fc98e7c754d19c40e1146df1e2c98cd7120aba95ccf03879f71f2b3cd1740c3b5e547d752289ee289956c59bae11f238d7c9731ab3ff61797a2b159f2345ec881913ab428d373e336cec9f1f2ee9ebae65e98c2f704b42ad091c0b6f554d8da9ec7e9f7b0d5dc2f022471525f2b7a676617923c4cc0df1072db5ad75af76e8db6f83fce0721adfff47c8373ff62f9a26634fff78d172a41b7246d17a1cb4974c6252c2d2b6d9e09c682565393cf41bef6b81e6ab4e9e63a9c78a56a3416b

import java.math.BigInteger;
import java.util.Random;

public class Primes {
    public static void main(String[] args) {
        if (args.length != 2) {
            System.err.println("usage: BITS REMAINDER-MOD-64");
            System.exit(1);
        }
        int bits = Integer.parseInt(args[0]);
        if (bits < 65) {
            System.err.println("bit count must be larger than 64");
        }
        BigInteger remainder = new BigInteger(args[1], 16);
        if (remainder.signum() < 0) {
            System.err.println("remainder must not be negative");
            System.exit(1);
        }
        if (!remainder.testBit(0)) {
            System.err.println("remainder must be odd");
            System.exit(1);
        }
        BigInteger delta = BigInteger.ONE.shiftLeft(64);
        BigInteger candidate = new BigInteger(bits, new Random());
        candidate = candidate.shiftRight(64).shiftLeft(64).or(remainder);
        while (!candidate.isProbablePrime(18)) {
            candidate = candidate.add(delta);
        }
        System.out.println(candidate.toString(16));
    }
}