On Dec 27, 2016, at 10:35 AM, Niels Möller nisse@lysator.liu.se wrote:
I don't recall all details of UMAC; it's some years since I wrote it. But the way I understand it, it works by computing a relatively weak low-complexity function of the expanded key and message. IIRC, L1 is a plain linear convolution, and L2 is some kind of polynomial evaluation. And then to hide the low-complexity structure from the attacker, a value derived from the key and nonce is XORed to the tag at the end. Looking at the code, that final "whitening" is the only use of the nonce I see.
So basically,
umac(key, nonce, msg) = F(key, msg) ^ AES(pdf_key, nonce)
where F(key, msg) is a low-complexity function. So if you compute
t0 = umac(key, nonce, "foo") t1 = umac(key, nonce, "foobar")
then
t0 XOR t1 = F(key, "foo") ^ F(key,"foobar")
which looks a bit too well structured, and defeats the whitening step. I can't tell if it leads to practical attacks, but I wouldn't be suprised of a few of these would let the attacker derive the parts of the expanded key corresponding to the suffix, and then forge additional messages with identical tag.
Ok, I see. Given that the nonce is only folded in with XOR at the last stage of generating the digest, I can see how it’d be a problem to ever generate two digest values with the same PDF key and nonce, independent of what was going on with the other function which operated on the message. If F() is good enough, knowing the XOR of F() on two different messages (even if one is a prefix of another) still shouldn’t tell you much, but the AES pad (and any additional strength it provides) has essentially been removed entirely in this case.
This definitely raises questions about whether it would ever make sense to support either snapshot_digest() or copy() for UMAC. For my specific use case in AsyncSSH, I can get by without either. I was only trying to support these to be compatible with PEP 452, but perhaps that’s not a good idea in this case.