# How close is AES to random oracle model?

I'm wondering if there are any guarantees about AES's randomness in comparison to Random Oracle, but I couldn't find any papers nor publications about it.

Let's say I have a blackbox B which for any input returns either encryption or random data

B(input){
if(hasBeenEncryptedBefore(input)){
fail();
}
with prob. 0.5 returns: "truly random bits from ROM" OR "f(input)"
}


where:

f(input){
IV := randomIV();
key := getKey();
return IV, AES_ENC(IV, key, input);
}


let's assume that getKey() returns the same key for each encyption and randomIV() returns truly random bits from ROM

Is the adversary interacting with B able to determine whether the result comes from ROM or AES?

• AES by itself is a block cipher, or keyed pseudo-random permutation. As such it is deterministic. Are you considering a specific scheme that makes it random? If not, then maybe that's the issue? – Maarten Bodewes Dec 29 '18 at 15:08
• If I'm interacting with blackblox by giving it input and getting in response Truly Random data or encryption of my input with random seeds, would I be able to distinguish in which way blackbox behaves? – wojteo Dec 29 '18 at 15:46
• AES uses a key, not a seed. It is possible to build a secure PRNG, such as DRBG-CTR that does use a seed. If seeded well, it should be indistinguishable from random (well, actually, it might provide a better distribution than most TRNG's). I would link to the DRBG (deterministic random bit generator) but NIST is in government shutdown at the moment. – Maarten Bodewes Dec 29 '18 at 15:55
• I made mistake: by seed I meant randomly generated key. I'm looking for publications that'd describe AES as indistinguishable from random oracle in experiment such as mine – wojteo Dec 29 '18 at 16:02
• Yeah, but if you just use AES - the block cipher - with a single random key then you can just send two identical plaintext blocks to distinguish it from a random oracle. If you use a different random key each time then it will be indistinguishable, but you would need as much key information as required to generate pseudo-random output. That's why you need to use AES in some kind of scheme, which you haven't specified. – Maarten Bodewes Dec 29 '18 at 16:05

The closest that I can think of is the XORP construction which is proven indifferentiable from a random oracle with optimal security bound recently. To connect to AES, you still need to instantiate random permutations via fixed-key AES.

Like all PRNGs (pseudo random number generators), there can be no guarantee of randomness, so therefore no statement to that effect can exist. However, reasonable randomness for a given application can often be demonstrated.

Following up on Daniel Lemire's work: I used 254 p-values (30 corrected) obtained from each of over 512 TestU01 BigCrush results on high and low 32-bits (forward, reversed and byte reversed) of the 64-bit output to perform a (work-in-progress) meta-analysis of AES in counter mode (seeded using SplitMix). I find no evidence that suggest any issues with AES, however BigCrush (thus my meta-analysis) has its limitations.

I believe others (perhaps Vigna/Blackman) have performed Hamming Weight Dependency analysis on it to over a petabyte, but cannot find documentation.

Wikipedia has an AES article with information on security, which is a related topic.

• This interesting but deep discussion about the quality of randomness validation software has been moved to chat. – Maarten Bodewes Dec 30 '18 at 8:22