3
$\begingroup$

I am new to algorithim randomness and confused at I guess a basic level question. Is it common for any cryptographic algorithim to have repetitions in its output i.e.let say 34 and D8 are two consective bytes which are repeting at random intervals.

I have got an encrypted file and it has 34 D8 at line 5 and then same sequence at line 903 and then again at 1002. File has total 1500 lines.

This also goes for other byte sequences. Is there any safe threshold in which there shouldn't be any repetition? I am asking it generally for any good encryption algorithim (AES 256, AES 128, Triple DES etc.)

$\endgroup$
3
  • 2
    $\begingroup$ Hi! What's the size of the entire file in bytes? $\endgroup$
    – Paul Uszak
    Aug 20, 2019 at 10:16
  • $\begingroup$ Its about 100~300 MBs. Please suggest how much recurrence is normal for such sizes of files or if file is within 100 MB. $\endgroup$
    – aneela
    Aug 20, 2019 at 10:46
  • 1
    $\begingroup$ We're pattern finding beings. Staring at any data will show you a pattern, even if it is fully (pseudo) random. Just seeing some repetition does not mean that the data is not random. So if you see any pattern, try and explain why it is there (because it certainly can be there if any algorithm is incorrect or implemented incorrectly). And run tests if you doubt the randomness itself. $\endgroup$
    – Maarten Bodewes
    Aug 20, 2019 at 15:50

1 Answer 1

2
$\begingroup$

One of the features of a good encryption is that the cipher text should be indistinguishable from pseudo random. That means that it'll look like output from a good random number generator. Since there are only 256 possible values for any byte, of course they will repeat if you've got 300 million of them.

Repeats tend to occur at the rate of $1 \over 256^n$ where $n$ is the number of bytes within the tuple you're looking for. So you'd expect $L \over 256^n$ number of $n$ length tuples in a randomish file of length $L$. For example, {6, 6, 6} should occur ~18 times.

Is there any safe threshold in which there shouldn't be any repetition?

From the above, you must have repetitions otherwise the cipher text wouldn't be very good and it would in no way resemble random. {6, 6, 6} may not have occurred 18 times (check for yourself with a hex editor). It may have occurred 20 times. That's random again, and it can vary within expected (but squidgy) bounds.

We can obtain the probability $P$ of a certain sequence occurrence randomly via a chi-squared test. We would view the cipher text as suspicious if $P < 0.01$. There's a more grown up example of looking for repeat sequences in section 2.7 of NIST's A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. The example there looks for "000000001", resulting in $P$ = 0.344154, which is a pass.

Consider though that this only tests the computational indistinguishability of the cipher text. We've expect that to be virtually perfect if you've used the correct algorithms/library. It can't test the inherent security aspects of say, constantly reusing an IV.

$\endgroup$
3
  • 2
    $\begingroup$ Looking at the values of a TRNG as they are being created can sometimes be a mistake... you might introduce bias. "Oh, too much repetition, let me start over." $\endgroup$
    – Patriot
    Aug 20, 2019 at 13:27
  • 1
    $\begingroup$ May be worthwhile to note that, with a random sequence, we sort of expect "odd-looking" random subsequences, like incredibly long repetitions or similar. I.e. for a given crypto algorithm, if it's generating random-ish (i.e. looks & is roughly evenly distributed) output, we expect that there will be an input which results in an output that's just 34 D8 bytes repeating for the entire 100MB. It's not likely, it's practically guaranteed that there's an input which will result in that output. If the encryption is good, we'll never be able to figure out which input, but there is one. $\endgroup$
    – Delioth
    Aug 20, 2019 at 20:49
  • $\begingroup$ Don't you mean indistinguishable from random? $\endgroup$
    – forest
    Aug 21, 2019 at 23:03

Your Answer

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

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