Given a known IV and a small part of the key (not enough to use brute force) is there are any way to break CBC encryption with only one cipher text?


A known IV doesn't help: it's meant to be public.

Even if you know a part of the key then there's still no attack that's easier than trying all possible keys. Knowing a part of the key merely makes the set of possible keys smaller.

Knowing even a large amount of plaintext and ciphertext doesn't help to recover the key. As long as you haven't fully found the key, having access to plaintext-ciphertext pairs doesn't help recover the key more quickly. And knowing part of the key does not help to generate new valid plaintext/ciphertext pairs.

So leaking a small part of the key does not weaken the system. The problem with leaking a small part of the key is that when this happens, it's usually difficult to ensure that only a small enough part of the key is leaked, where small enough means “so that my adversaries can't brute-force the key”.

Note that, as Luis Casillas points out, here I'm assuming that the underlying block cipher is an ideal cipher, which is a good enough assumption for block ciphers that are used in practice. (Not in theory though — related key attacks do exist on AES, for example, but they're theoretical: they still require an unfeasible amount of computation). See Luis Casillas's answer for a more correct explanation.

  • $\begingroup$ It sounds to me like you're implicitly assuming the block cipher is an ideal cipher, and not just a PRP. $\endgroup$ – Luis Casillas Jul 26 '17 at 8:40
  • $\begingroup$ @LuisCasillas In other words, I'm assuming that the cipher has no related key attack? Or is there more to it? $\endgroup$ – Gilles Jul 26 '17 at 15:30

This isn't the sort of question that can be answered generically. When we analyze the security of CBC, we assume that the block cipher is a pseudorandom permutation (PRP). The PRP definition says, roughly:

  • If: The key is chosen at random;
  • And: The key is kept completely secret from the adversary;
  • Then: A probabilistic polynomial-time adversary cannot tell the PRP apart from a random permutation with more than negligible chance of success.

But this definition tells us nothing about how the PRP behaves when the adversary has partial knowledge of the key (i.e., when the second premise is violated). Put in other terms, a PRP may optionally resist attacks in such a scenario, but is not required to.

If we made a stronger assumption—that the block cipher is an ideal cipher—we would be able to say that there's no attack better than brute force. But such an assumption is not common, since the weaker PRP assumption is sufficient for confidentiality modes like CBC.

So we just can't say much about the problem you've posed other than it completely depends on the details of the specific block cipher you use, and an attack in your scenario wouldn't necessarily count as a red flag against the block cipher.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.