Join Log in
Score:1
avatar Crypto

Generate unique random values for unqiue input values

pk flag
VSB

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.

53
0 + 0
aes
Score:1
Paul Uszak avatar Crypto
cn flag
Paul Uszak

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.

0 + 0
fgrieu avatar
ng flag
fgrieu
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}$.
0
Reply
Paul Uszak avatar
cn flag
Paul Uszak
@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...
0
Reply
fgrieu avatar
ng flag
fgrieu
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](https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Output_feedback_(OFB)).
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.