Score:-1

Crypto

Do all numbers have all the same chances to be returned using a CSPRNG?

Angelo M.

11/19/23, 7:01 PM

Given a range of numbers, e.g. [1, 2^256], does each number have the same chances to be picked by a CSPRNG, which are 1 in 2^256?

My concern is that truly random number generators do have this feature, but it's not always secure in cryptography (I presume), because numbers such as 741 in such a large range that is [1, 2^256] are not secure.

If that's true, do CSPRNG skip certain sub-ranges? Like, in our example [1, 2^32], because they're considered insecure? If that's also true, isn't this like beating the air, because now the attacker will know to skip these sub-ranges?

2 + 10

randomness

poncho

11/19/23, 9:01 PM

Why would a random 256 bit value that happens to be 741 not be secure, compared to (say) 4787985879261692769246529503049509767911957330519830813409881797811302? If the adversary is guessing randomly, the latter is just as probable as the former...

Angelo M.

11/19/23, 10:07 PM

@poncho, but not as secure.

poncho

11/19/23, 10:11 PM

Why "not as secure"? If you are worried about attacks that search for small values, why aren't you equally concerned about attacks that search for values around 4787985879261692769246529503049509767911957330519830813409881797811302? Both attacks succeed with equal likelihood, and hence neither is a greater threat than the other.

Angelo M.

11/20/23, 10:30 AM

@poncho, I'm not saying that large number is secure enough (I don't know how you generated), but if it was chosen randomly from [1, 2^256], then it's more secure in comparison with 741, because the latter comes from a range of numbers that is provably known to have been searched.

swineone

3/12/24, 11:50 PM

If you modify your CSPRNG so as to skip a sub-range, say $[1, 2^{32}]$, then you're introducing a bias, as the probability of generating numbers in that range becomes 0, while in the original CSPRNG it was, however vanishingly small (concretely, $2^{-224}$), still possible -- and identical to that of any other $2^{32}$-sized subrange. Please explain why you think introducing a bias would be an upgrade, rather than a downgrade, of the security of the original CSPRNG.

Angelo M.

3/14/24, 10:11 AM

@swineone, I don't argue that introducing bias would do good, I'm just asking, would you feel confident for using 741 as your private key? Or 11111....1111? At the same time these keys have been generated either deliberately or by software testing?

swineone

3/14/24, 12:49 PM

Define “deliberately” — I thought you were talking about random processes. What I’m confident about is that in a true, unbiased RNG, such keys would “never” be generated — as in, all computers in the world could continuously generate private keys until the heat death of the universe and the chances are still beyond unlikely that they would ever generate a 10-bit private key such as 741. Thus I do not worry about this ever happening.

swineone

3/14/24, 1:10 PM

Let’s say a computer takes 1 us to generate a private key (a lower bound, surely). Let’s say there are 100 cores in each computer (an upper bound), and there are 1 trillion computers in the world (an upper bound), and our window of time of interest is 1 trillion years (an upper bound). There are less than 100 million seconds in a year. That adds up to $10^{40}$ private keys generated over the life of the universe. The chance of generating a 256-bit private key with leading 224 zero bits is less than $10^{-67}$. Are you still worried?

Angelo M.

3/14/24, 5:55 PM

It's not a matter of chances. It's a matter of thinking. Would you want a number that doesn't look random? It might be random, but would you accept 1 as a random number, if you were to choose between 1 and a trillion? I wouldn't, because 1 is a number that is "looked first". I would neither want 1,111,111,111 for obvious reasons. People try out these deliberately. For example, there are bots that constantly search for potentially "easy to guess" keys, like from a range between 1 and 2^32.

swineone

3/14/24, 8:00 PM

Yes it’s a matter of chances. Why worry about something that will never happen? But feel free to make your CSPRNGs slower, biased and potentially introduce side channels that, unlike the stuff you’re worrying about, lead to actual attacks. The crypto community simply does not share your concerns, as you can see from other comments and answers, because they’re effectively impossible.

Score:3

Crypto

poncho

11/19/23, 9:10 PM

If that's true, do CSPRNG skip certain sub-ranges?

It's not true. In addition, even if it were true in some use cases, how is the CSPRNG supposed to know that are the weak values for any specific use case? Instead, the CSPRNG just supplies random bits, and if the application needs to avoid certain patterns (e.g. an all-0 value for use as a multiplier in ECC), the application can test for that and reject it.

So, no, CSPRNGs do not skip any sub-ranges.

+ 0

Score:2

Crypto

user105136

11/19/23, 7:23 PM

Statistically speaking, probability, that truly random number generated from range [1, 2^256] will be smaller, than 2^32 (as given in your example) , is 2^(-224), so negligible.

You can view truly random number generator as perfect coin, you flip that coin 256 times, write 0 when head lands, write 1 when tail lands, and you will have 256 bit binary number (that you can then transform to decimal). For that number to be smaller than 2^32, it would mean you would have to get heads at least 224 times in row, which will "never" happen.

+ 1

kelalaka

11/20/23, 10:38 AM

Welcome to cryptography.se we have Latex mathjax enabled in our site.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Do all numbers have all the same chances to be returned using a CSPRNG?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.