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)

$\endgroup$
  • 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 Feb 1 '17 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 Feb 1 '17 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 Feb 1 '17 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 Feb 1 '17 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 Feb 1 '17 at 23:39
2
$\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.

$\endgroup$
  • $\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 Feb 2 '17 at 20:38
5
$\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.

$\endgroup$
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.

$\endgroup$
  • 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 Feb 2 '17 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 Feb 2 '17 at 21:57
0
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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