3
$\begingroup$

I read that brute force attacks against a plaintext encrypted in OCB with unkown key and IV has approximately the same complexity as an attack where only the key is unknown.

  1. Why is that ?
  2. Is there a description of this attack ? If not, could you give me a hint on how this attack might work ?
$\endgroup$
4
$\begingroup$

Ok, here is one possible sketch of a brute-force style attack against OCB, which doesn't assume you know the nonce. It takes 512 trial decryptions for every key tested, so it's a bit more expensive than, say, a brute-force attack on CBC, but only by a constant factor.

Let us assume that:

  • you have an encrypted message that is $16n+15$ bytes long
  • that you know the last 15 bytes of the plaintext
  • and there's another block $P_n$ that you have enough information that you can recognize it if we decrypt it properly.

If we look at the OCB processing of the last 15 bytes, we have:

$C_{last} = P_{last} \oplus Trunc( E(K, \Delta_{last} ))$

where $Trunc$ is a function that chops off the last byte. So, we know the first 15 bytes of $E(K, \Delta_{last})$, namely $C_{last} \oplus P_{last}$.

To test a value of $K$, we iterate through all 256 possible values of the last byte $B$, and compute

$\Delta_{last} = D(K, (C_{last} \oplus P_{last}) || B)$

From each $\Delta_{last}$ value, we compute the corresponding $\Delta_{n}$ value (which is a $GF(2^{128})$ multiplication, so that's easy), and then compute:

$P_n = \Delta_{n} \oplus D(K, C_n \oplus \Delta_n)$

and check if that is a plausible plaintext value.

Once we have a plausible values for $K$ and $\Delta_i$, we can check the authentication tag to validate the decryption.

Once we have all that, we can also recover the nonce that was used to encrypt the message; this may be useful if related nonces were used to encrypt other messages with the same key.

Now, obviously this attack can be improved if we can get a plaintext message which is $128n+127$ bits long; that is unlikely in practice.

$\endgroup$

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.