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 Answer 1


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

  1. 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).

  2. 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.


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.