outer@utcsri.UUCP (Richard Outerbridge) (04/04/85)
About a year ago a flurry of papers were published discussing techniques
for forming Modification Detection Codes (MDC's), also called Compressed
Encodings, to be used with the DEA as message authenticators. The upshot
was that none of the methods proposed - except multiple key encryption -
was free from subtle and damning flaws. In particular, the method touted
by a proposed FIPS (plaintext XOR sum suffixed to plaintext and chain
encrypted) was awful. The next simplest method, plaintext linear addition
summed mod 2**32, was also subject to peculiar weaknesses. It was thought
that carry-around addition (i.e. addition mod (2**32)-1) might work, and
quadratic residue chaining of the plaintext was also suggested. It was all
up in the air, because one of the attacks ("meet-in-the-middle", based on
the birthday paradox) suggested that even if an acceptable method was
found, if the MDC were only 64-bits wide then 'authentic' forgeries could
be constructed with probability 0.63 using time & space of O(2**32).
Notice that the purpose of an MDC is to prevent forgery even by someone who
has access to the keys - as opposed to MAC authentication, which depends on
key secrecy. CBC MAC authentication is an accepted standard, and seems to
be dependable - given key secrecy and trusted users.
Does anyone know what the current status of the question is? Has a new
method of MDC calculation emerged as a potential standard?
--
Richard Outerbridge <outer@utcsri.UUCP> (416) 961-4757
Payload Deliveries: N 41 39'36", W 79 23'42", Elev. 106.47m.gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (04/10/85)
> be constructed with probability 0.63 using time & space of O(2**32).
What does O(2**32) mean?jbn@wdl1.UUCP (04/16/85)
It means ``on the order of two to the thirty-second power''. This number is only about four billion, so a brute force attack is quite feasible.