4 ms·

> Its a "reordering" of the sequence. That's it. Technically a PRNG state sequence could also have distinct loops, returning a reordering of only a subset of t

> Its a "reordering" of the sequence. That's it. Technically a PRNG state sequence could also have distinct loops, returning a reordering of only a subset of the sequence for any given seed. For example, `return state += 2;` would return two separate sequences for odd or even seeds. We know that a PRNG with N bits of state must necessarily repeat after 2^N invocations, but it requires further proof that a given PRNG will not repeat at smaller intervals. > For example: the sequence: {AES(0, key), AES(1, key), AES(2, key)... AES(2^128, key), AES(0, key)...} is a cryptographically secure random number generator. The sequence will loop after its 128 bits of state are exhausted. In light of the above, is it possible to prove this (through some property of AES)? (Also, we can't really prove that AES, or any other current algorithm, is cryptographically secure. Tomorrow, a new cryptanalysis technique could be revealed which breaks it.)

dragontamer 5y ago
> We know that a PRNG with N bits of state must necessarily repeat after 2^N invocations, but it requires further proof that a given PRNG will not repeat at smaller intervals. Yes, that's somewhat important for "smaller" 64-bit or 128-bit states. But at 512-bit states, the "average loop" is 2^256 (birthday paradox), so no one really cares at that point. We can see that Mersenne Twister is overprovisioned: 19937 bits of state and all 2^19937 visited in some order. But in practice, 64-bits worth of cycles (18-quintrillion) is sufficient for single-threaded simulations, and 128-bits is sufficient for multithreaded simulations. > In light of the above, is it possible to prove this (through some property of AES)? Yeah. AES is a block cipher that maps 128 bit blocks into "encrypted" 128-bit blocks. The reverse-AES (I'll call it unAES in this post) provides us the 1-to-1 unmapping as well. Meaning unAES(AES(0, key), key) == 0. unAES(AES(1, key), key) == 1. unAES(AES(2, key), key) == 2. (Etc. etc. for all possible 2^128 blocks) By the pidgeon-hole principle, we have 2^128 blocks associated with AES-encrypted blocks (named AES(0, key), AES(1, key)... AES(2^128-1, key)), and 2^128 blocks associated with our plaintexts (0, 1, 2, 3... 2^128-1). The only way all 2^128 map to each other is through a 1-to-1 bijection. Or in another way: AES(X, key) == AES(Y, key) if-and-only-if X == Y. This is because deAES(AES(X, key), key) == deAES(AES(Y, key), key) if-and-only if X == Y. Done. We know the AES-crypto method therefore only "loops" after 2^128, exploring the entire state-space. 2^128 possible inputs, 2^128 possible outputs, pigeonhole principle. QED, done.
dragontamer 5y ago
> (Also, we can't really prove that AES, or any other current algorithm, is cryptographically secure. Tomorrow, a new cryptanalysis technique could be revealed which breaks it.) Yeah, "Cryptographically secure" just means "according to currently published literature, no one has yet found a correlation between bits that leads to a faster than a 2^128 attack on the key" Tomorrow, it might be broken. But AES has been around for a while, so its unlikely to break tomorrow. IIRC, the furthest anyone has gotten is like breaking 4-rounds of AES (out of 8).

dragontamer 5y ago

> We know that a PRNG with N bits of state must necessarily repeat after 2^N invocations, but it requires further proof that a given PRNG will not repeat at smaller intervals. Yes, that's somewhat important for "smaller" 64-bit or 128-bit states. But at 512-bit states, the "average loop" is 2^256 (birthday paradox), so no one really cares at that point. We can see that Mersenne Twister is overprovisioned: 19937 bits of state and all 2^19937 visited in some order. But in practice, 64-bits worth of cycles (18-quintrillion) is sufficient for single-threaded simulations, and 128-bits is sufficient for multithreaded simulations. > In light of the above, is it possible to prove this (through some property of AES)? Yeah. AES is a block cipher that maps 128 bit blocks into "encrypted" 128-bit blocks. The reverse-AES (I'll call it unAES in this post) provides us the 1-to-1 unmapping as well. Meaning unAES(AES(0, key), key) == 0. unAES(AES(1, key), key) == 1. unAES(AES(2, key), key) == 2. (Etc. etc. for all possible 2^128 blocks) By the pidgeon-hole principle, we have 2^128 blocks associated with AES-encrypted blocks (named AES(0, key), AES(1, key)... AES(2^128-1, key)), and 2^128 blocks associated with our plaintexts (0, 1, 2, 3... 2^128-1). The only way all 2^128 map to each other is through a 1-to-1 bijection. Or in another way: AES(X, key) == AES(Y, key) if-and-only-if X == Y. This is because deAES(AES(X, key), key) == deAES(AES(Y, key), key) if-and-only if X == Y. Done. We know the AES-crypto method therefore only "loops" after 2^128, exploring the entire state-space. 2^128 possible inputs, 2^128 possible outputs, pigeonhole principle. QED, done.

dragontamer 5y ago

> (Also, we can't really prove that AES, or any other current algorithm, is cryptographically secure. Tomorrow, a new cryptanalysis technique could be revealed which breaks it.) Yeah, "Cryptographically secure" just means "according to currently published literature, no one has yet found a correlation between bits that leads to a faster than a 2^128 attack on the key" Tomorrow, it might be broken. But AES has been around for a while, so its unlikely to break tomorrow. IIRC, the furthest anyone has gotten is like breaking 4-rounds of AES (out of 8).