Computational indistinguishability and example of non polynomial algorithm

The wikipedia page on computational indistinguishability says that two ensembles are not distinguishable if "any non-uniform probabilistic polynomial time algorithm A" cannot tell them apart. To help me better understand the definition, I searched for an example of an algorithm that did not fit the above restriction---in particular a non polynomial time algorithm---that could differentiate between two computational indistinguishable ensembles. Rather to my surprise, I found none, so I ask, could anyone provide me with an example of one?

-
Brute force on the input of algorithm $A$? But otherwise I suspect the algorithm would be highly dependent on the underlying cryptographic primitive, the simplest example is RSA where integer factorization is subexponential (but not polynomial) but this isn't a great example, being public-key and all. – Thomas Feb 21 at 19:58
Another example is this: distinguish between a stream of output from Blowfish-CTR and AES-CTR (or generally two block ciphers with different block sizes in CTR mode). An algorithm can distinguish them without even touching the keys, using the birthday paradox, with complexity $\approx 2^{32}$, which is not polynomial-time (is exponential) but far better than brute-force. – Thomas Feb 21 at 20:15

I am not a complexity theorist, but I believe this fits the requirements.

The best known algorithms for factoring are superpolynomial time algorithm so they are not polynomial time. An example of something th superpolynomial time algorithm could distinguish are outputs from the Blum-Blum-Shub PRNG.

-

Here are two examples of attack algorithms that are not polynomial-time:

• Exhaustive search. Consider an algorithm that iteratively enumerates all possible keys, and checks to see if it seems to be correct. The running time of this algorithm is non polynomial: for a $b$-bit key, it will take $2^b$ steps of computation, which is larger than any polynomial of $b$.

• Factoring. The running time of the state-of-the-art factoring algorithms is larger than any polynomial of $b$, where $b$ represents the number of bits of the number you want to factor. For instance, the running time of some factoring algorithms is something like $2^{\sqrt{b}}$, which grows faster than any polynomial function of $b$. As far as we know right now, there's no way to factor integers in polynomial time.

The definition you are considering only concerns itself with attack algorithms whose running time is a polynomial, so the above two attacks are considered out of scope (they're not considered a "break" of the cryptosystem).

Edit 2/22: In the context of distinguishing two probability distributions, if you want a natural example, try exhaustive keysearch: to distinguish AES-CTR output from true random, one algorithm might try all possible $2^{128}$ keys to see if any of them match the observed value from the distribution, and output 1 if it matches, else 0. This algorithm does distinguish the two probability distributions, but it takes exponential time. (Strictly speaking, we should make this a $b$-bit key so that we can apply asymptotic running time, but whatever, hopefully you get the idea.)

P.S. If this gets to be a bit much and you need a study break, don't miss Eric Hughes' infamous advice on How to Give a Math Lecture at a Party (lyrics).

-