The following is a short summary of the attacks on OCB2 in Cryptography.
This is more applied than other answers, but still fits the question fairly well, and has the fun detail that we were only saved from what could have possibly been the most devastating practical failure of cryptography by a patent.
In Cryptography, a common proof technique is that of proofs by reduction. These are essentially "constructive" proofs of implications, which take the general form
Scheme $\Pi$ has property $P\implies$ scheme $F(\Pi)$ has property $Q$.
What "constructive" here means is the combination of
- Preserving Running Time: Any algorithm $A$ for breaking property $Q$ of $F(\Pi)$ may be transformed into an algorithm $A'$ for breaking property $P$ of $\Pi$, such that the running times of $A$ and $A'$ are similar, and
- Preserving Advantage: For $A$ and $A'$ as above, if $A$ only breaks property $Q$ with some probability $p$, then $A'$ breaks property $P$ with some probability $p'$ not too much smaller than $p$.
Reductions are perhaps the core proof technique in cryptography.
Relevant to the discussion below is their usage in symmetric encryption.
Here, one starts with
- a block cipher $\Pi$, roughly encryption for "fixed-length" (e.g. 128 bits) inputs, which
- satisfies a weak security property $P$ (typically "Indistinguishabillity under Chosen Plaintext Attack", or IND-CPA. At a high level, this models passive adversaries, which may choose messages $m$ to be encrypted, and view the resulting ciphertexts that are transmitted, but may not modify these ciphertexts in any way),
and produces
a general encryption scheme $F(\Pi)$, which may encrypt messages of arbitrary (not a priori bounded) length, which
satisfies a strong security property $Q$ (for example, in IND-CCA2, one allows an adversary to arbitrarily modify the aformentioned ciphertexts).
For symmetric encryption, the above are typically called "block cipher modes of operation". One often needs not only a transformation $F$ that takes as input a block cipher $\Pi$, but additionally an auxiliary scheme $\Gamma$ called a "Message Authentication Code". I won't discuss this detail further though.
There are many popular modes of operation. The OCB modes have similar performance to "classical" modes, while achieving a stronger security property known as authenticated encryption with associated data (AEAD).
An AEAD cipher takes as input two messages $(m, d)$, where
- the message $m$ is kept private (along the lines of IND-CCA2 mentioned above), while
- the data $d$ is publicly transmitted, but "authenticated", so an adversary who attempts to modify this (public) data will be caught.
This can be useful when messages $m$ require public components for processing. For example, the data $d$ may contain the ID of which key should be used to decrypt the message. Such data must be public, but should also not be able to be tampered with.
Over roughly a decade, Phil Rogaway developed the OCB Modes (OCB1, OCB2, OCB3) of operation.
They have been very popular. OCB2 was an ISO standard (until the attack referred to below), and (a variant of) OCB3 continues to be one (only OCB2 is known to have a flawed security proof).
OCB3 was selected as a "winner" of the CAESAR competition (a competition run by cryptographers to select a portfolio of cryptographic recommendations for future usage by standardization committees).
These schemes all had reduction-based proofs of security.
This doesn't mean that the schemes are secure, but it should mean that the only "real" way to attack them is to attack their base components $\Pi$, rather than their transformation $F(\Pi)$.
In 2018, Inoue and Minematsu found a simple attack on OCB2, that attacked the transformation $F$ rather than the components $\Pi$. This is to say that Rogaway's proof was wrong.
The way it was wrong may be described simply in a high-level way.
Roughly speaking (and perhaps in a post-hoc way, with knowledge of the attack), for OCB2 one may split $F = G\circ H$ into two parts.
- First, one shows that $H(\Pi)$ produces what is known as a tweakable block cipher from a block cipher $\Pi$, and
- Then, one shows that $G(\Pi')$ maps a tagged tweakable block cipher to an AEAD scheme.
This is to say that there was a small mismatch between the post-condition of $H$ and pre-condition of $G$.
This small gap lead to a complete failure in the proof, in the sense that OCB2 admitted efficient, near-complete breaks in security, even for secure "base" schemes $\Pi$.
This was missed by several standardization bodies, and many cryptographers (as of 2024, the OCB2 paper has nearly 600 citations).
As mentioned previously, this attack thankfully didn't have much practical impact. Despite OCB2 having many practical benefits compared to competing schemes, Rogaway patented the scheme, and had various licenses for it, namely
- Free usage in open-source software,
- Paid licenses available in commercial non-military software.
This was not enough for cryptographic library authors (see some discussion here) to widely adopt the OCB modes.
So, the presence of the patents deterred adoptions of OCB modes, which saved us from OCB2 failing — despite its security proof.