1
$\begingroup$

Why does it matter what kind of random number generation is used during key generation?

E.g. this answer states 7-8 words selected truly at random make a strong password. My problem's with the "truly" here. My thinking is - whatever key I chose with whatever random number generator, the information isn't available afterwards and an attacker can never know which random number generator I used, so he cannot use that to break the key. On the other hand, I can use "just count up" or a super sophisticated hardware generator and both might come up with "12345678" as a key. Of course, an attacker would start with trying keys like "111111" or "3456789", so he will break "12345678" earlier than, say, "93298762", but "using a good random number generator" or "selecting truly randomly" does not mean I cannot get "12345678" as key.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ For things like PIN's there is an additional check in case that the chosen PIN is indeed likely to be guessed (and in addition, if it is a PIN that is easy to recognize by somebody that is shouldersurfing). However, a symmetric key should have 128 bits or more of entropy. In that case the chance that you would choose such a number is abysmally small. And for an attacker to just check for that kind of number if they know that a random process is used would not make much sense. $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 29, 2019 at 20:59
  • $\begingroup$ I'm not sure if it would be useful for passwords, but generally some kind of quality requirements are implemented (choosing symbols and such). Human's are terribly bad random number generators, and if an attacker would assume that at least part of the passwords would be human generated, it would give the attacker significant advantage (oh dear, that last sentence derailed, but you get what I'm saying I suppose). $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 29, 2019 at 21:02
  • 2
    $\begingroup$ "selecting truly randomly" does not mean I cannot get "12345678" as key." But you get it with probability 10^{-8} and such "regular" strings are rare $\endgroup$
    – kodlu
    Commented Dec 29, 2019 at 23:43
  • $\begingroup$ "and an attacker can never know which random number generator I used" Why do you believe that? There are many random number failures over the years: Debian OpenSSL being one very prominent example. Also, keys don't need to be random, they need to be unpredictable. Random is one way to achieve that, but there are other ways. $\endgroup$
    – Swashbuckler
    Commented Dec 30, 2019 at 2:01
  • $\begingroup$ Passwords and words are not keys. That really has to be emphasized. The difference is, what kind of requirements you put on the entropy compared to the "length" (and possibly the encoding). Also: Fixed strings have 0 entropy. Looking at specific ones is pretty much useless when looking at entropy. $\endgroup$
    – tylo
    Commented Jan 1, 2020 at 15:13

2 Answers 2

Reset to default
2
$\begingroup$

When humans generate random key, there is some bias. For instance, in your example "93298762" there are only 2 turning points where as normally there should be 4 (you can argue that it is a single sequence and it is not long enough to seriously speak about statistics, but nevertheless...)

Even if an attacker does not know what generator you used, it makes sense for him to check first (after dictionary) the keys that a human would generate. This reduces essentially the entropy and thus the resources needed to brute-force the key. That's why it is important that generator has much entropy.

In cases where a human participation is possible, like password generation, a good generator will eliminate keys that have relatively high probability to be generated by a human (dictionary keys, keys with human specific anomalies). That's why when such generator generates a key "12345678" it would eliminate it and proceed with generating until the likelihood with human generated keys is below some threshold.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could you expand upon what you mean by the expected number of 'turning points' in the context of randomness? Does this refer to the strength of keys? $\endgroup$
    – mikerover
    Commented Dec 30, 2019 at 0:16
  • 1
    $\begingroup$ The number of turning points in a random sequence of n elements is expected to be 2/3x(n-2). In this example a sequence of 8 elements should have 4 turning points, where as it has only 2: element "2" at position 3 and element "9" at position 4. $\endgroup$
    – mentallurg
    Commented Dec 30, 2019 at 0:28
0
$\begingroup$

Being truly random is necessary in certain situations; for example during part of a key exchange protocol, where a permanent master key is used to encrypt less expensive session keys to send over.

If the process of key generation were to be "deterministic", an adversary could otherwise guess the next session key that we'll use, or perhaps even manipulate the user into selecting a session key of their choosing.

EDIT: As an aside, take pseudorandom generation. All that is required in order to discover and reproduce a pseudorandom sequence is the algorithm used to generate it and the initial seed. Therefore, the entire sequence of numbers is only as powerful as the 'randomly' chosen parts - but a given seed will always determine the same pseudorandom number!

See:

Random V Pseudorandom

GENERATION AND TESTING OF RANDOM NUMBERS FOR CRYPTOGRAPHIC APPLICATIONS

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.