AES-CTR vulnerability to cryptographic oracle

Question

I am new to cryptographic issues and from what I googled so far I could not retrieve the information I need.

Consider the use of AES-128 in CTR mode.
Let M be the set of possible plaintexts, for example M can be all the bytes sequences of a length lesser or equal than a specific integer n.
Let K be the private key and S_K the symmetric ciphering/deciphering function.
Given an IV i and a plaintext p, we have (I see the initial counter value as an IV there) :

c = S_K(p,i)

And symmetrically :

p = S_K(c,i)

If an attacker has access to an oracle O that can perform the decryption, given a specific ciphertext :

∀m, i ∈ M, O(m) = S_K(m, i), where i is an arbitrary IV, fed by the attacker

In other words, the attacker has access to a system that can encrypt/decrypt data using the private key K, which he wants to break (obviously, only the oracle system knows the key, the attacker can only use the system to encrypt/decrypt messages).

I would like to know to what leaks about the plaintext and/or the private key this kind of oracle can lead. Are these leaks critical ?

---

EDIT :

The counter is made according to the RFC3686 pattern : $(NONCE|CNT)$.
The $CNT$ part of the counter is 8-byte long and the counter is incremented once every 16 bytes.
A given $NONCE$, which is also 8-byte long, is never used twice. Finally, $n$ can be from a few kilobytes to a few megabytes. But since an overflow will occur only if $n \geq 2^{128}$, there is no overflow.
The attacker has access to both the ciphertext and the counter scheme used to build it (the NONCE + the pure counter value). With the oracle, he can obviously decrypt the ciphertexts he intercepted. To sum up, here is what the attacker knows :

1. The ciphertexts
2. The counter scheme used to generate the ciphertexts
3. The corresponding plaintexts (because he can feed the oracle with the good (ciphertext, counter scheme) couple)

Answer 1

I am assuming that $n$ is small enough that the counter never rolls over and repeats, and that the IV is chosen randomly from the space of all possible IVs.

The length of the plaintext is leaked, but that is leaked by the ciphertext anyways.

The plaintext for a given ciphertext is leaked as the attacker can feed that in to the oracle.

AFAIK, however, nothing about the key is ever leaked by this oracle.

Answer 2

In general, CTR mode is not secure against chosen-ciphertext attacks. (The same goes for the other classic block cipher modes of operation too; to get security against chosen-ciphertext attacks, you need authenticated encryption.)

In your stated attack scenario, the attacker can obviously use the decryption oracle to decrypt any ciphertexts they intercept, which (assuming there are indeed no limitations on the attacker's access to the decryption oracle) is as good as having the key. Since this is kind of a boring scenario (the attacker always wins and there's nothing we can do about it), I'll assume that there are at least some messages that the attacker would like to decrypt, but for which they cannot directly query the decryption oracle.

For example, the attacker might only have access to the decryption oracle up to some time limit ("lunchtime attack"), but would like to decrypt messages intercepted after this time limit. Unfortunately, with CTR mode (or any synchronous stream cipher), the attacker can still do this if they can predict (with reasonable accuracy) the nonces used for future messages: for each likely future nonce, they can ask for the decryption of a message consisting of a long sequence of null bytes using that nonce. This will give them the raw keystream corresponding to that nonce, which they can then save for later, allowing them to decrypt any future message encrypted using that nonce.

Making the nonces unpredictable thwarts this particular attack, but still does not provide full IND-CCA2 security since the cipher remains malleable. To make CTR mode non-malleable, you'll need to combine it with a message authentication code using the encrypt-then-MAC construction (i.e. first encrypt the message using CTR mode, then calculate the MAC for the IV + ciphertext).

Note that including the IV in the MAC calculation is essential; if you don't, the attacker can just intercept any legitimate message, change its IV, submit it to the decryption oracle and XOR the returned plaintext with the ciphertext to get the keystream for that IV.