Given a $N$-bit AES or similar block cipher with his $N$-bit key $k$.
We can encrypt a $N$-bit message $m$ to a $N$-bit cipher $c$ and decrypt it again. $$E(m,k) = c$$ $$D(c,k) = m$$ An adversary does know $n_m$ bits of the message, $n_c$ bits of the cipher and different to most applications also the full key $k$.
He want to find pairs $(m\leftrightarrow c)$ which match the $n_m$ and $n_c$ bits on their related side.
Q: Can he find them significant faster than with brute force?

Further nodes:
The AES/block cipher is in ECB-mode - it does always use the same known key $k$.
It's length-perceiving encryption - $m,c,k$ all have bit length $N$
The bit location of the known bits is also know (e.g. could be the first $n_m$ bits of the message and last $n_c$ bits of the cipher)

The number of different messages with those $n_m$ target bit is $2^{\displaystyle N-n_m}$. At the cipher side it's $2^{\displaystyle N-n_c}$.
The brute force method would start at the side with less values and encrypt (or decrypt) all possible values and check if the result matches the target bits.

Assuming uniform distribution the mean number of matches will only be $2^{\displaystyle N -n_m -n_c}$ pairs.
Can the adversary make use of this and test significant less values than with the described brute force method?

Bonus question:
In case the adversary can make use of this would it be more secure it the leaked information is distributed among all bits of $m$ or $c$?
E.g. instead of the $n_m$ bits only a module residue $r_m \equiv m \bmod 2^{\displaystyle n_m}$ is known to the adversary. Or can he also make use of that?

  • $\begingroup$ Are you asking about generic attacks against an ideal cipher or specific properties of AES-like ciphers? $\endgroup$
    – forest
    Jun 10, 2022 at 1:13
  • $\begingroup$ @forest (comment updated) To be more specific I'm asking about a 192-bit block and key size Rijndael (in ECB mode). The adversary who knows the source code, the run time variables and the used key want to find pairs of $m$ and $c$ with the target $n_m$, $n_c$ bits as quick and as many as possible. It's related to this question $\endgroup$
    – J. Doe
    Jun 12, 2022 at 13:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.