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.