If you were guessing valid tokens why would DoSing be more valuable to you than use of the token?

Bypassing rate limits and amplification, presumably. Just generate a huge list of keys and push once to attack many services at once with the whole set.

what about the birthday paradox however? i.e. the attacker doesn’t need to brute force a specific key, but just any key... I guess for AWS the search space is still huge enough for it not to be a problem still (but didn’t do the math)

I believe AWS secrets are 240 bits. That is a pretty massive space. I don't know how many active secrets are out there, but I think someone would need to get very lucky to collide before the attack was noticed and stopped.

Other partner's secrets may be more susceptible.

Edit: I did not consider the paired access key which is another 70 or so bits. I think you'd need to collide on both to make someone have a bad day.

You need to guess both to use them, but you only need to guess the secret to get it revoked. GitHub does not check that the corresponding access key is somewhere in the repo too before taking action. You are right about this being impractical though.

Ah ok. I wasn't sure how that part worked.

seems like you could just log in directly at that rate