2
$\begingroup$

In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about DES algorithm the authors say that:

"In a good cipher system, each bit of the ciphertext should depend on all bits of the plaintext"

Since it's not said why, are you able to explain it to me ? Thanks

$\endgroup$

1 Answer 1

3
$\begingroup$

"In a good cipher system, each bit of the ciphertext should depend on all bits of the plaintext"

This property is also called the "avalanche effect" and is usually an explicit design guidance when designing novel block ciphers whereby flipping any input bit gives about a 50% chance to also flipping all output bits, ensuring maximal dependence of all outputs bits on all input bits.

The standard (formal) security definition of a block cipher is that of a pseudo-random permutation where an efficient, probabilistic adversary has to distinguish whether they're looking at a fully random permutation (where each unique requests gets a random previously unseed response sampled on request) or at the keyed permutation with an unknown key.

It is widely believed that modern ciphers like AES satisfy the above definition.

Now if not every bit of the output depends on the input, you can find two distinct inputs that give related outputs, something that wouldn't happen for an ideal permutation and allowing an adversary to find out whether they're looking at the non-ideal permutation.

The practical application could for example be a bias in the output where one bit doesn't e.g. depend on the least significant bit of the input. Then when you're using the cipher in counter mode you'd get that bit to be the same twice in a row, leaking information about the plaintext at these points, like with a reused one-time-pad.

$\endgroup$
1
  • $\begingroup$ Thanks so much. Are you able to explain more clearly the sentence "Now if not every bit of the output depends on the input, you can find two distinct inputs that give related outputs"? $\endgroup$
    – AleWolf
    Oct 16, 2019 at 13:08

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.

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