18
$\begingroup$

OCB2 is proposed by Rogaway, Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC , and it is standardized in ISO/IEC 19772:2009. The author also provided a proof by security reductions, that is, a break of OCB2 implies the break of the underlying block cipher.

However, Akiko Inoue and Kazuhiko Minematsu describe practical forgery attacks against OCB2.

  1. How does the attack work (on a high level)?
  2. Why did the proof by security reduction fail?
  3. What are the implications?
$\endgroup$
4
  • 2
    $\begingroup$ twitter.com/hashbreaker/status/1057791485016526848 $\endgroup$
    – ddddavidee
    Nov 1, 2018 at 10:37
  • 2
    $\begingroup$ If djb is freaking out then I will too. Thank goodness Rogaway’s patent prevented widespread adoption of OCB. $\endgroup$
    – rmalayter
    Nov 1, 2018 at 11:03
  • $\begingroup$ wasnt OCB2 ditched for OCB3 (now called OCB) years ago? $\endgroup$ Nov 1, 2018 at 16:15
  • 3
    $\begingroup$ OCB2 was created in 2003 and OCB3 in 2011. That's 8 years of use, slightly more than the time OCB3 is out (according to Wikipedia) OCB2 has been standardized at multiple places as well, including in an ISO standard that hasn't been withdrawn it seems. I would definitely make sure that OCB doesn't mean OCB2 in some contexts. If it is still in standards documents then it hasn't exactly been "ditched", just succeeded. $\endgroup$
    – Maarten Bodewes
    Nov 1, 2018 at 16:42

1 Answer 1

21
$\begingroup$

How does the attack work (on a high level)?

It's an unfortunate consequence of how the pad of the last encryption block is computed. The pad can essentially be used to both eliminate the block cipher operation for a chosen ciphertext's decryption (allowing the attacker to determine the plaintext) and the pad can be used as the tag in this attack. It's quite incredible.

The attack crafts a special initial plaintext, sends it to an encryption oracle, receives a ciphertext and tag, modifies both of those, and then sends them to a decryption oracle which accepts the modified tag for the modified ciphertext (hence, a successful forgery).

The modified ciphertext (which is submitted to the decryption oracle) will have it's block cipher operations cancelled out in decryption. See the paper for details on how this works. The gist of the idea is that the pad used for the last (and only block) has the same block cipher operation in it as the ciphertext block. Said another way, the pad and the ciphertext are both the results of data xored with the block cipher called on the same input. Since the pad is xor-ed with the ciphertext block, we essentially eliminate the only operation requiring knowledge of the secret key, so we now know what the plaintext will be.

The correct tag for the modified ciphertext turns out to be the pad from the original encryption oracle call. This pad is simply the last block of the initial plaintext, which was sent to the encryption oracle, xor-ed with the last block of ciphertext that the oracle outputs. So a forgery takes exactly one encryption oracle call.

I highly recommend reading the paper for details, I've tried to keep all the math out of this since you asked for high level, but the magic is really in how the plaintext is crafted and how the ciphertext is modified in a way that the corresponding tag can be deduced by the attacker.

Why did the proof by security reduction fail?

The security reduction failed because of a subtlety in how XEX (xor encrypt xor) and XE (xor encrypt) were combined into XEX* for OCB2 mode. The issue is that, even if the encryption function (e.g. the block cipher) is information theoretically secure (think a uniform random permutation), XEX* is not.

There is an issue with what the adversary is, by definition, allowed to do in the security proof of OCB2. The adversary is assumed to be tag-respecting, i.e. it can only query the encryption and decryption oracle with certain parameters to XEX*, but the construction of OCB2 actually violates this tag-respecting property in a very subtle way. I again will refer you to the paper for details, the proof is a bit complex and there's no good way to thoroughly give it without re-rewriting it.

The solution to enforcing this tag-respecting property is rather simple, which is to use XEX to generate the padding used in the last block, rather than XE.

What are the implications?

This break is very specific to OCB2, down to how it uses XEX*. OCB1 and OCB3 are not affected. Use of the ISO spec of OCB2 should be discontinued. For deployments using OCB2 that need to path a quick fix, the solution mentioned above of using XEX rather than XE for the padding of the last block should suffice. The authors call this modification OCB2f and assert that the security bounds claimed for OCB2 are in fact now correct.

I've tried to answer in readable fashion without getting into all of the technical details (which would amount to re-writing the paper), but the best way to really understand the attack and its impact is to read the paper and grok the math behind how the attack works, and how it violates the assumptions that were made in the original security proof.

$\endgroup$

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.