Mellisa O'Neil tested Xoroshiro128+ with 512 terabytes (2^49 bytes) of data. And finally it failed. Would AES fail PractRand with enough data?

When we can expect that AES will fail? Maybe with $2^{64}$ of data?

  • 3
    $\begingroup$ I don't know if PractRand can handle so much data, but I don't expect AES (assuming CTR mode) to fail around 2^64: the only statistical anomaly I know about is that there will be no duplicate outputs, but detecting this would require 2^64 memory (and more than 2^64 data, for confidence). There may be some statistical anomalies nobody knows about, but nobody knows about them, and seems unlikely that a general-purpose test will detect them. I don't know how did xoroshiro128+ last so long: its least significant output bit is a LFSR of period 128. $\endgroup$ Aug 30 at 3:35
  • $\begingroup$ @thedefault. has shown a bit of an issue with your question: AES is a block cipher and is therefore restricted to a 128 bit output for a 128 bit input. So specifying the mode of operation is really required CFB-8 or AES-CBC may have rather different characteristics than AES-CTR. For AES-CTR we'd have to assume e.g. a 128-bit counter suppose. Generally we would expect AES to last a long time given the correct mode, but these tests may fail at different times given different seeds. $\endgroup$
    – Maarten Bodewes
    Aug 30 at 7:39
  • $\begingroup$ @thedefault. I was wrong. She tested Xoroshiro128+ with discarded the entire low 32 bits: pcg-random.org/posts/xoroshiro-fails-truncated.html $\endgroup$
    – Tom
    Aug 30 at 21:09
  • $\begingroup$ @MaartenBodewes I thought about feeding AES just numbers: 1,2,3,... and so on. I forgot to write about it. $\endgroup$
    – Tom
    Aug 30 at 21:11
  • $\begingroup$ That would be the key stream of AES in counter mode, assuming that the key is not reused for separate streams. $\endgroup$
    – Maarten Bodewes
    Aug 31 at 11:47

Of course $AES_{K_1} \oplus AES_{K_2}$ will pass as that's a pseudorandom function. One $AES$ isn't meant to be. But how can you prove that empirically?

PractRand is written by one guy (sorry Chris). It's not used in the mainstream literature. TRNG's are principally validated using dieharder or NIST STS. Randomness has been well studied but PractRand hasn't. Therefore you can't rely on some arbitrary code to disprove much researched mathematics.

And these suites aren't that clever anyway. RC4 passes all of them, and the Twister passes 95% of them, yet... And consider the huge flaws in diehard, but we still use it. Therefore Tom, the question is kinda moot.

  • 1
    $\begingroup$ The second paragraph seems completely absurd to me. PractRand doesn't become any worse at detecting non-random input because it is not used in the mainstream literature. What does 'PractRand hasn't been studied' mean and how does "you can't use it to disprove much researched mathematics" follow from that? (and what stops me from using some arbitrary code to disprove much researched mathematics? AES probably won't fail any randomness test in a reasonable amount of time, but if it did, that would, obviously, mean that it is broken) $\endgroup$ Aug 30 at 14:19
  • $\begingroup$ @Paul Uszak Quite many authors use PractRand to evaluate the randomness of their generators. I thought it is now one of the best, most modern testers. What's more, they wrote at pracrand.sourceforge.net, that Dieharder is heavily overdated: "Pretty bad at the moment, but some parts show the potential to be very good with a little more work. The command line interface can be very convenient for scripting. I was unable to build it on win32. The default test set is particularly awful. Several tests have false-positive issues." $\endgroup$
    – Tom
    Aug 30 at 21:20
  • $\begingroup$ @Paul Uszak how do you know that xoring two AES should pass and one AES may not? $\endgroup$
    – Tom
    Aug 30 at 21:28
  • $\begingroup$ @Tom See crypto.stackexchange.com/q/75535/23115. It takes two (plus) of them to create a proper non distinguishable PRF, but people don't generally do that. $\endgroup$
    – Paul Uszak
    Aug 31 at 11:43

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.