alt Hacker NewsQuick question for the crypto experts. I thought that the goal of a true random number generator was that all values between 0 and MAXCOUNT are equally likely, and therefore all private keys between those values are equally likely. Is this not true? If people are going to attempt to brute force your key, don't you want the floor to start at 0? If the floor is higher, won't the brute force start higher too?
Replies
Imagine you have a 3 digit PIN code. That’s 1,000 options to brute force. If you remove 000-009 as “too weak”, you still have 99% of the search space available. These numbers scale favorably as the private key size gets bigger.
In short, raising the floor doesn’t really hurt the search space meaningfully.
It seems that somebody / something only created a single byte of randomness for each certificate.
You are technically correct, the best kind of correct! Though I have a feeling we'll never see a 384-bit CSRNG generate 352 0-bits in a row in this Universe's lifetime.
That said, a sanity check on the value somewhere in the code would indeed have prevented this.
Yes, what matters is the size of the range, not the bounds on the range. Also keep in mind that in some cases private keys are not uniformly sampled from a range of integers; for example RSA keys, which are sampled from prime numbers.
More generally, it is common to sample a bit string and use that as a seed for a PRG, from which the private key is generated. So in that case the range is [0, 2^k] and what matters is the quality of the randomness. Unfortunately high-quality randomness is not always available, especially for embedded devices and rack-mounted "appliances."
IIRC in RSA the key, a prime number, is selected between 2^(bits-1) and 2^bits, or iow it always starts with a 1₂.
It's not that 4 isn't a valid seed (though insanely unlikely) it's that once I know your values weren't picked randomly because I guessed one of them I can easily figure out the others.
In this case one cert gets defeated and you go the odds of that number being that low are 2^-384. Essentially impossible if it were randomly selected. It's much more likely you didn't choose that at random so I start guessing a bunch of other low numbers for your other certificates and find them quickly.