# An adversary does know the block cipher key and some bits of the message and the cipher (same length as key). Does this help him to find pairs? (ECB)

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)

Brute-force:
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?

• Are you asking about generic attacks against an ideal cipher or specific properties of AES-like ciphers?
– forest
Jun 10, 2022 at 1:13
• @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 Jun 12, 2022 at 13:41