We should be paranoid, but mostly that we might be not worrying about the right things.
1. There's this proof that a trapdoored symmetric cipher is equivalent to a public key system (there's a link in the metzdowd thread somewhere). No one seems to have figured out how to build a public key system with anything close to the efficiency of AES.
2. The specification of AES itself isn't that large. It's not minimal, but neither does it seem to have large arbitrary-looking constants. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
The NIST Dual-EC DRBG fails on both counts: 1. it is based on an obvious public key system, and 2. it recommends the use of large arbitrary constants that could easily be a trapdoor.
Now is it possible that NSA occasionally intentionally fails to backdoor a NIST standard in order to help us underestimate how often they succeed? Can we ever develop a coherent threat model with the possibility of this kind of adversary?
But really we need to ask some the folks older than I am. It would be a good question for the randombit or metzdowd crypography lists. Also, I'll tweet at Bellovin.
Edit: https://twitter.com/marshray/status/376600321637638144
That assumption was not taken for granted back in the 90's. It was only with years of cryptanalysis of AES (which had had resistance to known plaintext an explicit design goal) that designers felt comfortable with things like CTR mode.
In practice, we've learned that the block ciphers are by far the strongest part of the system, and it's the block cipher modes that provide the weakness for attackers.
IMHO this is the type of poisoned knowledge that the US spies should be blamed for.