5

More weak keys? 32768 weak keys can be downloaded for analysis, but are there more? Three times as many?

There is much information about DSA-1571-1 openssl -- predictable random number generator. There are even several websites to download weak DSA keys, or blacklisted key fingerprint hashes.

The presentation Predictable PRNG In The Vulnerable Debian OpenSSL Package - The What And The How says that the PRNG depended not just on the current process ID, but also on the host architecture and "internal state". Later in the presentation, a reference is made to "(2^15 − 1) × 3 keys". 32768 (2^15) keys is the most DSA keys I have found. (See https://hdm.io/tools/debian-openssl/debian_ssh_dsa_1024_x86.tar.bz2)

Are there other weak DSA keys due to this PRNG problem? If so, are they due to host architecture and "internal state"? What are these other keys? Can they be generated from the known set of 32768?

rickhg12hs
  • 163
  • 6
  • Remember that a DSA or ECDSA key used to sign on an affected system (more than a handful of times) can have been compromised even though the key itself was generated correctly (on another system or before the bug) and is not 'weak'. – dave_thompson_085 Nov 22 '16 at 14:46
  • @dave_thompson_085: Yeah, where is the list of R values from the (R,S) pair of the DSA signature made on an affected system? – rickhg12hs Nov 22 '16 at 16:39
  • 1
    The possible R values for defectively-random k depend on the key parameters (p,q,g) which in theory can be shared but in practice are usually generated anew and different for each DSA key, thus I don't think you're going to find any precomputed set. For ECDSA people almost always use a few standard curves, so those would be possible, although I don't know of any. – dave_thompson_085 Nov 24 '16 at 05:54

1 Answers1

2

If so, are they due to host architecture ...

Yup.

From the talk: "times three, because there are three combinations between endianness and bitness".

From the Debian wiki (archived here): (text reformatted by me)

The broken version of OpenSSL was being seeded only by process ID.

Due to differences between endianness and sizeof(long), the output was architecture-specific:

  • little-endian 32bit (e.g. i386),
  • little-endian 64bit (e.g. amd64, ia64),
  • big-endian 32bit (e.g. powerpc, sparc).

PID 0 is the kernel and PID_MAX (32768) is not reached when wrapping, so there were 32767 possible random number streams per architecture.

This is (2^15-1)*3 or 98301.

.

Can they be generated from the known set of 32768?

Dunno. Don't think so. Debian has packages for them: (text reformatted by me)

Scope of the blacklists

The current official blacklists (in openssh-blacklist) cover RSA-2048 and DSA-1024 keys as generated on 32-bit little-endian, 64-bit little-endian and 32-bit big-endian systems. That's sufficient to cover users who used the default key length, but not if some of your users decided they wanted a longer keylength.

For non-default keys, see openssh-blacklist-extra which contains RSA-1024, RSA-4096, and (an empty) DSA-2048 for all three architectures.

StackzOfZtuff
  • 17,783
  • 1
  • 50
  • 86
  • Excellent answer. So, it looks like we have complete blacklists of signatures for weak DSA keys, but not a complete list of weak keys due to the Debian openssl bug. Or are all the DSA weak keys available somewhere? – rickhg12hs Nov 21 '16 at 22:15
  • @rickhg12hs: Yes. The PRNG could have been to used to create keys with weird and uncommon key lengths for example. So if you have a 2323 bit RSA key somewhere, then I don't think anyone will have bothered to waste the CPU cycles on generating all 98301 of those. So they won't be on any blacklist. – StackzOfZtuff Nov 22 '16 at 06:16
  • I'm also looking for DSA signatures created with the Debian predictable RNG. There is a similarly limited number of R values in the (R,S) pair (the signature) even if the key was generated properly. Has anyone made a list of these R values? – rickhg12hs Nov 22 '16 at 16:35
  • @rickhg12h: Dunno. Try asking over at [CryptoSE](http://crypto.stackexchange.com/) maybe. – StackzOfZtuff Nov 22 '16 at 20:02