Forgery attack on OCB

Question

When using same nonce in OCB mode of authenticated encryption, how forgery attack can be done?

Answer 1

To obtain the tag, OCB xors the plaintext blocks and encrypts them. Thus a sufficient condition for a forgery is finding another plaintext with the same xor as an existing plaintext.

Consider a known plaintext attack where the attacker obtained (plaintext, ciphertext) pairs for two messages encrypted using the same key and nonce. The attacker picks between the two known blocks at each position, attempting to produce the same xor of the plaintexts.

This leads to a system of 128 linear equations, one equation for each bit in the tag. These equation constrain the attackers choice of blocks. If the messages are long enough so that the system of equations isn't overdetermined, they can solve that system of equations efficiently via standard linear algebra. If the plaintext were linearly independent, messages 128 blocks in length would suffice. In practice they're not, so you need more blocks, but I expect that increase to be modest.