From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Cryptography / Computer science   
WikiProject icon This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the quality scale.
 ???  This article has not yet received a rating on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science.


This page is wrong; no one in cryptography calls all universal-hash-function-based MACS "UMAC." UMAC is a specify one of these: (talk) 05:16, 29 April 2010 (UTC)

I was fooled at first (UMAC is good), but this looked to simple. This is broken! But having this using the UMAC name can be dangerous. --RogerJL (talk) 10:50, 8 March 2011 (UTC)

I should drop the intro -- Nroets 23:31, 8 Jun 2005 (UTC)

Explaining an edit that I made: hashing (for instance, by evaluating a polynomial over a finite field) followed by one-time pad is not a secure MAC. For instance, the attacker might twiddle the lowest-order bit of the input. This will add (or subtract) 1 to the output, which has a 50% chance of just twiddling the low-order bit there. That would commute with the one-time pad, so the attacker can just twiddle the low-order bit of the MAC also, and he forges a message with probability 1/2. To make the MAC secure, you need a pseudorandom function. -- bitwiseshiftleft

If the attacker twiddle the lowest bit of the plaintext (or input as you call it), it will change roughly half the bits in the output of the dot product (what you call a polynomial). For example if your finite field is MOD 7 and your secret hash function is f(x)=x * 5 MOD 7 and the next value from your OTP is Y, then f(0) XOR Y and f(1) XOR Y will differ in 2 bits. -- Nic Roets 18:30, 7 May 2007 (UTC)

Reviewing the source - for short messages the complete key won't be used. For example a three byte message will only use the first three bytes of the key - effectively limiting the keyspace to 24 bits... My gut feeling is that all bytes in the key should always be used. Padding message with zeroes will not help as the r1, r2, r3 will never be modified -> i.e. same output will be produced. Article should mention padding (to same size as key) and its pitfalls (do not use only zeroes) --RogerJL (talk) 23:57, 7 March 2011 (UTC)

You are right in the sense that an attacker can take any message, append zeros at the end and use the old MAC. However, since most message formats either contain a length field, or are the serialization of some structure / object, this is not a concern.
If you want to pad, then zeros will work perfectly well. The guarantee still holds: The probability of an attacker correctly guessing the MAC is one in 224. -- Nic Roets (talk) 01:41, 8 March 2011 (UTC)

That was not my concern! My concern is that if you can intercept a short message (<=3 bytes). You can find the tree first letters of the true password by brute force. Once you have found them wait for slightly longer message (4..6 bytes). Break the next tree letters... repeat... If you can intercept two short messages then NO padding will help, nor will any nonce. As they only contributes to xoring with a constants. After the key is broken any message can be forged... --RogerJL (talk) 09:08, 8 March 2011 (UTC)

It is even worse! If you can intercept two messages that only differ in one triplet. Then all the other triplets can be viewed as a constant. And you can break the secret key for the differing section. --RogerJL (talk) 10:50, 8 March 2011 (UTC)

Did you consider the "nonce" ? The caller must initialize result[0], result[1] and result[2] with 3 secret bytes. Ideally those 3 bytes should come from a one time pad. If they come from an OTP, then an attacker observing every message and every MAC will learn absolutely nothing about "secret". -- Nic Roets (talk) 21:05, 8 March 2011 (UTC)

Unless you change nonce for EVERY (different) message this crypto will easily broken. I have source that breaks it. To break it you do not need to know the start values for the result array. You have to ensure that atleast two things differ for EVERY message - start value is one, each block that differs is another. With two differences you have 2^24*2^24=2^48 values to work through using brute force. To process all 2^24 takes less than 4 s on my computer - and I see lots of optimization potential in the code. One second per group of 2^24 is not at all unrealistic, you can probably do a lot better. — Preceding unsigned comment added by RogerJL (talkcontribs) 08:14, 9 March 2011 (UTC)

I change the nonce every time. In fact I use up 24 bits of my OTP for every message I send. So 24 MB of flash will only last one million messages. The message are numbered and the OTP index is calculated from them. The message number need not be included in the UMAC calculation. It is good practice to check that the message numbers from the sender will always increase, but this requirement can be relaxed if the messages contain a secure timestamp.
XORing with f(nonce) is effectively "encrypting the hash". If the encryption is good, then an attacker can learn nothing about the hash. -- Nic Roets (talk) 01:13, 11 March 2011 (UTC)

The original publication[edit]

This is the original publication by Carter & Wegman : [1] —Preceding unsigned comment added by Nroets (talkcontribs) 11:12, 28 April 2009 (UTC)