Score:1

Crypto

Can AES fail PractRand?

Tom

12/30/22, 12:16 AM

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?

144

1 + 5

aes

random-number-generator

the default.

12/30/22, 3:35 AM

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.

Maarten Bodewes

12/30/22, 7:39 AM

@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.

Tom

12/30/22, 9:09 PM

@thedefault. I was wrong. She tested Xoroshiro128+ with discarded the entire low 32 bits: https://www.pcg-random.org/posts/xoroshiro-fails-truncated.html

Tom

12/30/22, 9:11 PM

@MaartenBodewes I thought about feeding AES just numbers: 1,2,3,... and so on. I forgot to write about it.

Maarten Bodewes

12/31/22, 11:47 AM

That would be the *key stream* of AES in counter mode, assuming that the key is not reused for separate streams.

Thorham

9/17/23, 3:21 AM

@the default - PractRand tests 64 bit values, and AES-CTR will certainly produce duplicate 64 bit values.

Score:0

Crypto

Paul Uszak

12/30/22, 1:04 PM

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.

0 + 4

the default.

12/30/22, 2:19 PM

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)

Tom

12/30/22, 9:20 PM

@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 http://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."

Tom

12/30/22, 9:28 PM

@Paul Uszak how do you know that xoring two AES should pass and one AES may not?

Paul Uszak

12/31/22, 11:43 AM

@Tom See https://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.