1
$\begingroup$

I'm going to generate unique random values based per a range of unique input values.

In other words I have range of input values which these numbers are part of a series (like a range of serial numbers which are increasing one by one) and there are no duplicate values among them. I want to generate random values based per each of input values which there should not be any duplicate values in output values.

The first thing which came to my mind was using standard block ciphers such as AES since they are injective and if the input of this function have no duplicate values it is guaranteed that its output are not duplicate as well.

So my concern is this method to generate (pseudo-)random values can be secure enough?

E.g. if somebody have 1000 input consecutive (plaintext) values and 1000 output values (ciphertexts) per these input value, can he/she predict the output random value for 1001th input value? In other words is it possible for an attacker to model this pseudo-random generator mathematically to generate new random values without having the key used inside AES block cipher?

I know that there are some standard for "KDF"s such as those defined in NIST SP-800 series however the uniqueness for random values is not a concern over there (if I'm not mistaking) but this is a concern in my target application.

$\endgroup$

1 Answer 1

1
$\begingroup$

Of course it is secure enough. Stand back and think of the consequences if it wasn't: By looking at 1000 encryptions, if you could then predict the 1001th without knowing the key, you would have broken AES.

Your construct is in fact a commonly recognised method of turning a block cipher into a stream cipher as:-

prng

Whilst there are issues of the Birthday effect for output spaces approaching $2^{64}$ bits, just 1000's of them will be indistinguishable from random. And unique.

$\endgroup$
3
  • $\begingroup$ Yes. On the last paragraph: because AES is a bijection, iterating AES is not subject to the birthday effect, as iterating a hash would be. Probability of having fallen into a cycle starting from a random point after $2^{64}$ iterations is about $2^{-64}$. $\endgroup$
    – fgrieu
    Oct 6, 2021 at 13:01
  • $\begingroup$ @fgrieu The opposite of the Birthday effect? Lack of Birthday effect? Birthlessness? I was looking for the wording that there should be collisions in a properly (pseudo) random output. The reason AES PRNG is distinguishable... $\endgroup$
    – Paul Uszak
    Oct 6, 2021 at 13:20
  • 1
    $\begingroup$ AES encryption for a fixed key is a permutation of a set of $k=2^{128}$ elements. There are $k!$ permutations of such $k$ elements. For any fixed starting point, for any $\ell$ in $[1,k]$, exactly $(k-1)!=k!/k$ of these permutations have a cycle of length $\ell$ when starting from said point. Thus, for a random permutation and starting from a random point, the cycle length $\ell$ is uniformly distributed on $[1,k]$. And the expected (average) cycle length is $(k+1)/2$. That's useful for DES in OFB mode. $\endgroup$
    – fgrieu
    Oct 6, 2021 at 16:00

Your Answer

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

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