When the input size in a PRF is larger than the output and many inputs will generate the same output, but why AES-256 in CTR mode is considered safe?

alpominth

3/3/24, 3:25 AM

I know that if the input size in a pseurandom-function is larger than its output, many different inputs will generate the same output by the Pigeonhole principle (I also read an article related to that).

AES with 256-bits key size in CTR mode will generate many equal outputs per IV across all the possible keys of such a key space, because the IV capped to 128-bits, smaller than the key size.

Why this is not considered when taking in account the security of AES-256 in CTR mode?

If many keys will generate the same output, couldn't an adversary find a matching output in less than 2^256 tries (AES-256 key space)?

1 + 0

aes

ctr

pseudo-random-function

Score:3

Crypto

DannyNiu

3/3/24, 4:31 AM

AES-256 is a keyed permutation, which is different from PRF. I see your misunderstanding may be rooted in the following -

Even if one matching input-output pair exist for 2 keys, there are vastly many pairs that don't match under these 2 keys (as well as for different keys).
Being a permutation, the total number of possibilities of combination is calculated from the factorial operator as $255!$, which is (again) vastly greater than $2^{256}$.

And lastly, as to "finding a matching output in less than 2^256 tries", you need mathematical relationships and formulas to do that, and establishing and solving for one takes more effort to just perform a brutal-force search. For example, there was the suspicion that AES was breakable under "Extended Sparse Linearization" (XSL) attack, but later it was found to be impractical.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: When the input size in a PRF is larger than the output and many inputs will generate the same output, but why AES-256 in CTR mode is considered safe?

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.