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?

Question

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)?

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.