Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 ?
share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks, great help. –  yawn Jan 26 '12 at 9:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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