The SIV mode of operation result in data leakage with small messages (<= blocksize) when the authentication part of the key is discovered and how to get data from CMAC

[klondike <klondike () xiscosoft es>]

Hi guys,

After some small research I found that at times (when the authentication
key is known and the amount of authenticated data is smaller or equal to
the block size) it can be possible to recover data from CMAC, this
vulnerability can affect in a similar way to the AES SIV mode of operation.

For those of you not familiar with cryptographycal notation:
* M is the message authenticated.
* E_K() means encrypt a block
* D_K() means decrypt a block
* 0^n is a block made only of zeros
* dbl is a shift and a conditional xor

Let's see how CMAC works in these particular cases:
If the block has size 16:
CMAC_K(M) = E_K(0^n⊕k1⊕M) = E_K(k1⊕M)

If it has size smaller than 15:
CMAC_K(M) = E_K(0^n⊕k2⊕(M|10^m)) = E_K(k2⊕M)

Here k1 and k2 can be derived as follows:
k1 = dbl(E_K(0^n))
k2 = dbl(k1)

Thus an attacker with the authentication key may obtain the block for a
CMACED message M' as follows:
* Get k1 and k2
* The block will be either k1⊕D_K(M') or unpad(k2⊕D_K(M')) If the size
of M' is known then this can be done with a 100% reliability otherwise
it can be either of the two.

Now let's go with SIV:
With a small block basically we get the following data (I'm obviating
the authenticated data info since S can be generated when the attacker
knows it):
CMAC_K(CMAC_K(0^n)⊕_end M) if |M| = blocksize or CMAC_K(CMAC_K(0^n)⊕
M10*) if |M| < blocksize

Since in both cases CMAC_K acts over a single whole block it will
generate this:
CMAC_K(CMAC_K(0^n)⊕_end M) = E_K(k1⊕CMAC_K(0^n)⊕_end M')

Since we have got K we can generate CMAC_K(0^n), k1 and use D_K thus we
first break the CMAC:
D_K(E_K(k1⊕CMAC_K(0^n)⊕_end M)) = k1⊕CMAC_K(0^n)⊕_end
k1⊕CMAC_K(0^n)⊕(k1⊕CMAC_K(0^n)⊕_end M) = 0^n ⊕_end M

And then we retrieve M:
0^n ⊕_end (0^n ⊕_end M) = M

We can also know the size of M since it is the size of the rest of the
message (minus the first blocksize bits) thus we can recover M and
remove the padding (which means doing the appropriate ⊕_end).

So how do we solve it:

1. For CMAC:
Use the CMAC result as key to encrypt a known block (for example 0^n)
thus we can define CMAC2 as:
CMAC2(M) = E_CMAC(M) (0^n)

For SIV we can use the other half of the key thus:
CMAC2* = E_kc(CMAC*(A1,..An,M))
Then operate as normal using CTR with the result of the CMAC2* as IV.

Cheers!
Francisco Blas Izquierdo Riera (klondike)

PD: Take this as a draft, there may be typos and such in this e-mail
hopefully the paper won't have them.
PD2: Keep in mind that CMAC and SIV as they are are perfectly fine in
some scenarios, yet when you expect the attacker getting access to the
key (or the key part) used for authentication they can give problems at
times as shown here.

Attachment: signature.asc
Description: OpenPGP digital signature

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/