On Wed, Mar 27, 2013 at 1:29 PM, Niels Möller nisse@lysator.liu.se wrote:
Do you think the current function could provide information on the plaintext? From a quick look it is not obvious to me, but I haven't checked thoroughly.
The poly_hash function clearly has data-dependent timing. If it is useful for the attacker, I don't know.
I see what you mean; i was checking only the poly64 part. Indeed there is an additional evaluation of the poly64 when m >= some size. In the description it is like that: if (m >= maxwordrange) then y = (k * y + marker) mod p y = (k * y + (m - offset)) mod p else y = (k * y + m) mod p end if
which doesn't look to provide much, but the time spent it seems it could be used to distinguish text consisting of 0xfffffffff, to text that is other than that. I don't know how practical is that because the overall instructions needed for an evaluation of poly64() are very few, but still looks like an issue. It could be fixed by adding an additional evaluation of poly64 (i.e., do an additional multiplication on the else case), but it looks it is going to affect negatively the performance of all cases except 0xffffffffff. I don't know if the expression y = (k * y + marker) mod p y = (k * y + (m - offset)) mod p
can be optimized to a single evaluation by using a separate poly64 function for it (that would be fine if the difference is just one or two multiplications more than the original poly64).
Note that the current limit on the code is 16MB messages per tag, not per key, so it is oversufficient for all practical uses of a MAC (which is not the same as a hash).
I consider handling of large files to be an important application of any MAC. When encrypting a large file (typical cases: session key derived from a passphrase, or random session key encrypted with RSA), the session key should always include a MAC key for authenticating the data.
Encryption of big data is seldom happening on a single run. If there is a bit flip on the hard disk all the data are gone (decryption and mac will fail for all) and so is any possibility of recovery. I'd expect data to be encrypted in chunks (i think gpg and the other hard disk encryption tools work like that). In any case if you consider that limitation, a stopper, I could check it further.
regards, Nikos