3
$\begingroup$

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?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Maarten Bodewes♦ Dec 29 '18 at 15:08
  • $\begingroup$ 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? $\endgroup$ – wojteo Dec 29 '18 at 15:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Maarten Bodewes♦ Dec 29 '18 at 15:55
  • $\begingroup$ 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 $\endgroup$ – wojteo Dec 29 '18 at 16:02
  • 1
    $\begingroup$ 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. $\endgroup$ – Maarten Bodewes♦ Dec 29 '18 at 16:05
3
$\begingroup$

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.

|improve this answer
$\endgroup$
3
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ This interesting but deep discussion about the quality of randomness validation software has been moved to chat. $\endgroup$ – Maarten Bodewes♦ Dec 30 '18 at 8:22

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.