1
$\begingroup$

Imagine I have a 1000000 bit sequence that is considered random ( ie the output of a TRNG).

Now imagine I 'double' that sequence : I concatenate the same sequence 2 times : " my 1000000 bits "concat" my same 1000000 bits "

Can we say that the resulting sequence is random ?? ( note that if someone know the construction structure of the concatenated sequence can know the bit 1000001 and following ones as they are the same ones as the beginning ones...)

I have been testing some setups like the one exposed with NIST test suite and seem to show the resulting sequence is random ( anyway im no real expert in NIST test suite so maybe I'm missing some crucial point)

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Remember, the NIST test does not give an authoritative determination that a bit sequence is "cryptographically random"; actually, no automated test can do that. Instead, all it can say is "it acts like random to the specific statistical tests I tried" $\endgroup$
    – poncho
    Commented Feb 1, 2017 at 20:30
  • $\begingroup$ Yes, that's completely true. My worries are that a sequence constructed like that will be extremely insecure from a cryptographic standpoint but seem to pass random tests... $\endgroup$
    – Hector Buelta
    Commented Feb 1, 2017 at 20:36
  • $\begingroup$ This is true; this is one good reason not to rely solely on these randomness tests. Against an (alleged) CSPRNG, well, the RNG has to be really broken for these tests to detect anything. Against a raw entropy source, it can be better, however I generally assume that no raw entropy source is really fully random (e.g. there are always biases in there somewhere), and I look for ways to estimate the minentropy (so I know how much of that entropy output I would need to give to my trusted CSPRNG, and then we're good to go). Other people have different opinions about that, though... $\endgroup$
    – poncho
    Commented Feb 1, 2017 at 20:46
  • $\begingroup$ @Poncho,Christian and Luis : yes, your reasonings are sound and actually very good. But imagine someone 'offering/selling" sequences like that ( or even with a not so easy doubling scheme, but repeating bits anyway...) claiming true randomnes....how can one trust/reject them on an objective basis? $\endgroup$
    – Hector Buelta
    Commented Feb 1, 2017 at 20:57
  • 1
    $\begingroup$ I'll simplify your construction. I'll flip a coin, yielding a single bit - a 1 or a 0. That bit is random. I'll now repeat that bit 1000000 times. Is the resulting bitstring random? ;-) $\endgroup$
    – Thomas M. DuBuisson
    Commented Feb 1, 2017 at 23:39

4 Answers 4

Reset to default
3
$\begingroup$

Intuitively your sequence is not random so I'll not go there.

Rather I'll address why you might think that it is, based on the NIST test suite. From my experience, the suite's implementation is not very reliable (AKA rubbish). I'm sure the math is good, but it's the 3rd party implementations that are suspect. I'm not sure which code you're running, I couldn't get the de faco NIST source code to compile properly. The NIST documentation is useless even though it runs to 100's pages. So you're left with Fred's own implementation from GitHub, written in someone's spare time between watching the football. Considering the sophistication of the statistics knowledge required to code and test such software, I'm extremely dubious as to NIST test results.

Clearly my doubts are well founded if your non random test sample passed NIST, especially section 3.12 (Approximate Entropy Test). The test should have calculated an entropy of 4 bits /byte and vigorously waved a large red flag spitting out an extreme p value. Most people do not know how to correctly use Shannon's log (Px) formula for entropy, and either NIST or Fred are amongst them. Respectfully, you may not have configured the tests correctly either I guess. NIST is extremely difficult which is why you can't find any command line examples of it's use on the Internet.

One of the simplest randomness tests is compression. A truly random sequence is incompressible. Use a good quality compressor like 7z or fp8 (avoid zip as that fails like NIST does). When you compress your sample file, you'll see it reduces to half size. Ergo, it's not random.

Improve this answer
$\endgroup$
1
  • $\begingroup$ YES !! isolating the Aproximate Entropy Test and playing with a 'doubled sequence' and also testing other doubling sequences with not so trivial schemes led to a fail ( p-value=0) , where the original ( non doubled) sequence pass the test ( p-value=0,36). Also compressing the double sequence with off-hte-shelf tools ( gzip) showed compressibility which is a proof of redundancy... $\endgroup$
    – Hector Buelta
    Commented Feb 2, 2017 at 20:38
6
$\begingroup$

Remember, sequences themselves are not random or not; the process for generating the sequence is random or not. The question is: is your repeated sequence compatible with the hypothesis that its source is random?

Given a uniform random bit generator, the chance that it will generate any one sequence of $n$ consecutive bits is $2^{-n}$. The chance that, given that the previous $n$ bits were $x$, a random bit generator will proceed to produce $x$ again as its next $n$ bits is also $2^{-n}$. So in your case with $n = 10^6$ the chance that a random bit generator is $2^{-10^6}$—a crazy small number. If we observed such a sequence, then, we would reject the hypothesis that the bit generator is random with near certainty.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I like this answer! Given a primitive example: A binary random generator outputs a single 0. You concatenate it to 00; is that still random? What about 000? You get the idea: The longer the sequence the less likely it is to be random. 1010 could still be a concatenation of 10 twice, or it could be truly random. And so on... But actually for the original question: Isn't it necessary to repeat the experiment one more time at least? I mean: "anything is possible once (at the first time)" $\endgroup$
    – U. Windl
    Commented Apr 17 at 21:01
3
$\begingroup$

In a truly random 2000000 bit sequence, the probability that the the first bit and the 1000001st bit are equal is only $0.5$; in the sequences generated by your doubling method, the probability is $1$. Hence, your sequences are not truly random.

They might still pass several randomness tests. Passing such a test does not imply that the generated sequences are random; only failing such a test means that the sequence is not random. In fact, you have just devised a (simple) test that your sequences do not pass: The first bit and the 1000001st bit should be different with some positive probability.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ To be honest, most strong CSPRNGs tend to fail more restrictive randomness tests from time to time. It's not because CSPRNG are weak, but tests just have their expectations of randomness... $\endgroup$
    – axapaxa
    Commented Feb 2, 2017 at 2:16
  • 1
    $\begingroup$ @axapaxa This is true, but the crucial difference is the "from time to time". If sequences are generated such that they are guaranteed to fail a certain test (as the ones generated as in the question), then either the generator is not strong, or the test is nonsense. $\endgroup$
    – Christian Matt
    Commented Feb 2, 2017 at 21:57
1
$\begingroup$

I'd like to propose an additional way to think about this problem: The randomness of a string can be stated in terms of bits of entropy. In the example, the RNG generates 1000000 bits of entropy. If you concatenate the same 1000000 bits of entropy to itself, you still have 1000000 bits of entropy, as the second 1000000 bits was not generated randomly.

So the answer is yes, concatenating a random bit string to itself can still be considered random, but ONLY as random as the original bit string.

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.