Is AES distinguishable if the attacker has an decryption oracle?

Question

Let the following game be given:

G^IND-CCA':

1. Prepare a key k <- KeyGen(1^Kappa)
2. Choose a hidden bit h <- {0, 1} uniformly random
3. Prepare a decryption oracle O_Dec. Given a cipher text c, it returns the decryption m
4. Prepare a one-time oracle O_Test. When called with m_0, m_1, it will return the encryption of m_h. Call it c*
5. Call the attacker with input 1^Kappa, O_Dec, O_Test and await a guess h'.
6. If O_Dec was ever called with the output of O_Test, randomly accept or reject.
7. If h = h' then accept else reject

My lecturer claims that there exists a polynomial time attacker with a non-negligible advantage for AES.

We have seen that obviously, a deterministic scheme is never IND-CPA secure since you can just ask for the encryption of both m_0 and m_1. But since we don't have access to an encryption oracle, we have to find cipher texts != c* that somehow reveal information when being decrypted.

I just don't see any structure in the encryption/decryption that might help us.

Since there is no mode of operation given. Just textbook AES for one block

Answer 1

Someone gave me the solution:

Attacker A:

1. Decrypt a random Bitstring c using O_Dec and get m
2. Call O_test with m and another random bitstring m'
3. Return 1

If the hidden h = 0 (which happens 50% of the time), we win/lose randomly since O_Dec was called with the value returned by O_test. If h = 1, we always win. So all in all, we win 75% of the time, which is obviously non-negligible