-1
$\begingroup$

I read a lot of stuffs about entropy/randomness. But what if a random generator (either digits or strings) once output a "human" patern ?

I know it is very unlikely to happen, but if a random code pin generator generates a "1 2 3 4 " pin code, what would we say ? It would be generated by a random generator (or considered), but unfortunately, this is not as random as we expect it to be ?

I know it is a strange issue but I am curious to hear someone about a random ouput which is doesn't look random.

$\endgroup$
  • 3
    $\begingroup$ The very first thing to realize is that randomness is not a property of any particular output sequence. The sequence "1234" is neither random nor predictable, it's meaningless to refer to it as random. Rather, randomness is a property of the process used to generate them. Once you understand that, things begin to seem less paradoxal. $\endgroup$ – Thomas Nov 28 '14 at 15:03
  • $\begingroup$ Thanks nice answer ! I understand the importance of the "process", but what if this process output a human pattern ? Do we accept that because we respect the "random process" ? That's a different question I guess, but I am curious about it. $\endgroup$ – crypto-learner Nov 28 '14 at 15:07
  • 1
    $\begingroup$ What do you mean by "what if"? (Yeah, well, it could happen. So what?) I honestly can't tell what your question is. Are you looking for a discussion, or do you have a specific technical question you are looking for an answer to? "What would we say?" is not a specific technical question. $\endgroup$ – D.W. Nov 30 '14 at 7:01
  • $\begingroup$ Can’t help myself, but this question makes me point to this $\endgroup$ – e-sushi Nov 30 '14 at 13:05
  • $\begingroup$ @DW Please accept that there may be "non english" user on this website, so my english may not be as perfect as you wish. An exemple of what I was wondering, we often read for One Time Pad : should be random AND never reuse. It can not be truely random if you remove "already use pad" from possible pad. $\endgroup$ – crypto-learner Dec 31 '14 at 13:46
3
$\begingroup$

Short answer / tl;dr: Yes, that can occur, but it is no problem most cases.

The sequence "1234" would be a perfectly normal output for a generator which ouputs a pattern of 4 numbers from 0 to 9. If every possible sequence has the same probability of being used as output (called being uniformly distributed), than "1234" is as likely as "7392" or even "0000". The amount of possible sequences is $10^4 = 10000 \approx 2^{13}$, ca. 13 bits.

But what if we know that an attacker would start guessing the sequence at "0000" and increment it with every next guess? The sequence "0010" would only take 10 tries to be guessed. We could generate a sequence and reject it if it is under "1000". It would take at least 1000 guesses for every sequence for the attacker. But what if he oder she knows that we do this? Starting with "1000" and not "0000" would be no problem and we have reduced the overall space of outputs by 1000. That's not good. We removed 10% of our initial key space. Even if we accept this, 10000 or 9000 possibilities is not enough for nearly every kind of attack.

What if we have a better random output? Something like "bA3-)#kjeGER3s!H"? That is a random sequence of 16 characters. The generator is uniformly distributed and has this possible characters: All lower and upper case letters, numbers from 0 to 10, and the special characters /?'!#",.;:%&=()[]{}<>-_ and the dollar sign. All in all $26+26+10+25 = 87$ possibilities. With a sequence of 16 characters that are $87^{16} \approx 10^{31} \approx 2^{103}$, ca. 103 bits. Used as a key for a block cipher it should be secure against any attack, even from the NSA or any other government agency. (I will not go into the details here, that has nothing to do with the question.)

The bad part is, what if our sequence is now something like "aaaaaaaaaaaaaaaa"? Trying every character, repeated 16 times, is nothing special. It can be done in a matter of milliseconds. (Using a good key derivation function would help, but that is not the point.) We could reject every "suspicious looking" sequence and repeat the generation of the sequence. If we remove some more things like "secretpassword11" we would lose some bits entropy, but 80 bits (very pessimistic estimate) is still high enough.
Should we do this? Well, why should we? The chance of getting (randomly) one of this $2^{23}$ of $2^{103}$ possibilities is near 0. ($\frac{2^{23}}{2^{103}} \approx 10^{-24}$) We would have to generate millions of sequences to have the slight possibility to get one of this "bad numbers". And always remember: The attacker could adapt his or hers attack and not even test for this special numbers.

Getting "human" output can occur. It just happens and is even expected. That's one of the fundamental problems of evaluating random number generators. "Is the output 0000 now okay or is my generator broken?" - We can't answer this. Yes, it could be okay, or your generator is broken. We don't know.

All in all you don't have to worry about this. On small ranges you have other problems than that and with bigger ranges the statistical probability is small enough to occur nearly never.

Other topics than cryptography: Never reduce the input range if you do scientific research with uniformly distributed numbers of a bigger range! You would distort the output statistics and thereby make your whole work unusable.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thanks for your anwser ! I still wonder why online bank often limit user password with 6 digits (short range : 10^6). Maybe the system block when several fails occured, limiting brute force, maybe it is because they have anti-robot interface with only digits, where you click for entering password. $\endgroup$ – crypto-learner Nov 28 '14 at 23:41
  • 1
    $\begingroup$ @crypto-learner: Commercial companies are a special case. It's hard to change the whole system over a year. Altering the cryptographic system has to be made carefully. Even a small bug could be devastating. Also banks are not known to be the fastest on the technology background. Oh, and my bank did use normal password fields in their online banking system, but you could (or had to) use upper and lower case letters. $\endgroup$ – Nova Nov 28 '14 at 23:51
  • $\begingroup$ clearly true ("hard to change over a year"). What is sure, in my little contry (france ^^), banks use "not normal"/"limited" password field ! $\endgroup$ – crypto-learner Nov 29 '14 at 0:21

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