Comment by seanalltogether
10 hours ago
Quick 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?
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.
> It's not that 4 isn't a valid seed (though insanely unlikely)
I have an insanely unlikely unique car licence plate number to sell you.
> Essentially impossible if it were randomly selected.
You would say the same of any seed I gave you. You've just artificially assigned this number with some sort of emotional importance.
There are several very practical reasons (and not emotional) reasons to expect that "4" is the result of bad implementation.
I can think any number of programming mistakes that will result in a supposed (pseudo-)random number generator to be be biased to very small numbers. I have made such mistakes myself.
By any reasonable estimate, the probability of randomly picking a number below 256 is MUCH smaller than the probability of someone having made a mistake.
1 reply →
If you cherry-pick that statement in isolation you're technically correct. But in practice the whole comment you're replying to is actually correct, in this case if you saw the number four, one would be correct in concluding that's unlikely and searching other low digit numbers, the proof of that is that it happened here.
1 reply →
They had multiple keys and 7 of the keys were numbers less than 256.
1 reply →
I don't see why you would get downvoted for that. You're right.
It just happened that that particular number got the attention of a human, which was luck. But in terms of statistics, this number was not less likely than another one.
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 also acts as a test case. "Hey seed-generator, give me a random number between 0 and a gazillion." "Does 4 sound good?" "No, it sounds like you're obviously broken."
In theory, all values would be equally random. In practice, some results are exceedingly more likely to occur when something's wrong with the algorithm.
While any given outcome of flipping a coin randomly N times is equally likely, if that series looks like [heads, heads, heads, heads, ...], then there's probably something other than pure random affecting the output.
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.
It seems that somebody / something only created a single byte of randomness for each certificate.
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₂.