I have studied the design of block ciphers like DES and AES.

I know the actual algorithms, but I don't intuitively "grok" the most important property of them:

The most important property, is that if you have the key and the ciphertext, you can calculate easily the plaintext, but if you have the plaintext and ciphertext, you cannot easily calculate the key.

That is, the block cipher is a function $$f(P,K)= C$$ and the essential property is that the inverse w.r.t. P is very easily caclulated, but the inverse w.r.t. K is not.

I don't intuitively understand why this assymmetry is true, even though I know how to actually do the decryption algorithm. Is there an intuitive explanation of this asymmetry?

  • 4
    $\begingroup$ The reason for this asymmetry is that the algorithms were designed that way. $\endgroup$
    – fkraiem
    Sep 6 '18 at 18:03
  • $\begingroup$ @fkraiem, I hope you're joking $\endgroup$
    – user56834
    Sep 7 '18 at 3:22

If you had a block cipher with this property, it would necessarily be insecure!

The most basic requirement for a block cipher is to be a pseudorandom function (PRF). In the game that defines security of PRFs, the attacker gets to choose input blocks $x_1, x_2, \ldots$ and gets back responses $y_1, y_2, \ldots$. It should be hard to distinguish whether the $y_i$'s are uniformly random or have the form $y_i = F(k,x_i)$ for a random (secret) key $k$.

Suppose your block cipher was ``key-invertible'' in the way you describe. Here's an attack against the PRF security of the block cipher. Ask for some $x_1$ and get back $y_1$. Now you do this key inversion process and you can learn (a candidate) key $k'$. Then you can make one more query on $x_2$ and get back $y_2$. If $y_2 = F(k',x_2)$ then you guess that you are getting outputs of the PRF; otherwise you guess that you are getting random responses.

This attack completely breaks PRF security. It assumes that the key-inversion process is perfectly correct --- that is, given $x$ and $y = F(k,x)$ for unknown $k$, you can always compute that exact $k$. Even if you assume the key-inversion procedure is not always correct (e.g., maybe there are two keys that satisfy $F(k,x) = F(k',x)$ so sometimes you get it wrong), It seems likely to me that this attack can be extended.


If you examine a cipher such as AES or any other key-alternating cipher, you will notice they break down into two major steps:

  • Addition (exclusive-or) of the key material with the message block
  • Application of a publicly known, invertible, confusing and diffusing transformation

Which in notation looks like: $$c \leftarrow F(p \oplus k) \oplus k$$

and that sequence is repeated many times.

If you don't know the correct value for $k$, then you simply cannot apply the key addition/removal step. It's that simple.

You could pick some random $k$ instead. If you use an incorrect key, you will get back another "plaintext", but it is not the plaintext that the correct key would reveal (and is probably simply a random block of bits).

Other ciphers might function in a slightly different manner, but the principle is more or less the same: Without the information of the key, you can't apply the transformation.

  • 1
    $\begingroup$ This doesnt answer my question. My question is, why is $F(p \oplus k) \oplus k$ invertible w.r.t. $p$, (when $k$ is known), but not easily invertible w.r.t. $k$ (when $p$ is known)? $\endgroup$
    – user56834
    Sep 7 '18 at 3:25
  • $\begingroup$ @Programmer2134 The inverse of $F(p \oplus k) \oplus k$ is $F^{-1}(c \oplus k) \oplus k$. Do you see why evaluating this expression without $k$ is not possible, and why knowing $p, c$ is not enough to evaluate it either? $\endgroup$
    – Ella Rose
    Sep 7 '18 at 3:31
  • $\begingroup$ That is the inverse w.r.t $p$, not w.r.t. $k$ $\endgroup$
    – user56834
    Sep 7 '18 at 10:14
  • 1
    $\begingroup$ @Programmer2134 because $F$ is (highly) non-linear in this description (i.e. for all $a,b:F(a\oplus b)\neq F(a)\odot F(b)$ for any operation $\odot$ and standard XOR $\oplus$). $\endgroup$
    – SEJPM
    Sep 7 '18 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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