potential hazards of Protect-America act

Steven M. Bellovin smb at cs.columbia.edu
Thu Jan 31 01:28:36 UTC 2008


On Wed, 30 Jan 2008 17:03:04 -0800
Warren Kumari <warren at kumari.net> wrote:

> Disclaimer: I'm sitting in a meeting that is making me grumpy and
> this is one of my pet-peeves... I keep hearing people making the
> assertion that MD5 is "broken" -- this is not completely true. Yes,
> there have been collisions found -- yes, I can easily (and quickly)
> generate 2 inputs that generate the same output...
> 
> What is not trivial is for you to generate another input that will
> generate (eg): 0x56f39544ebca88f261f2087dab3d7e61 or, given
> 0x56f39544ebca88f261f2087dab3d7e61 to figure out what input I
> provided.
> 
> There was a brief flurry of media attention around the time of
> Vlastimil's tiunneling work saying "MD5 Broken!!!". Many people (not
> necessarily anyone on the list) just read the sensationalist
> headlines with no understanding as to what had been accomplished...
> 
>   As with any tool, you need to understand the capabilities and
> limitations before using it.

Yes, I know precisely what the attack on MD5 means; I've even published
a paper on some aspects of it.

The context in the article we're talking about is a discussion of the
quality of the FBI's surveillance systems.  The FBI's own documents
mention the use of MD5; see, for example,
http://www.eff.org/files/filenode/061708CKK/073007_dcs03.pdf .  I
assert that the context mentioned there does indeed run afoul of the
vulnerability.  Specifically, MD5 is being used to log received files
in a surveillance system.  So -- suppose I'm a bad guy and I think the
FBI is monitoring my traffic.  I create two files, one perhaps
incriminating and one not, with the same MD5 hash.  The FBI arrests me
and uses the intercepted file as evidence.  I tell the judge that the
evidence was tampered with; as proof, I show my file that has the same
MD5 hash.  I then assert that the FBI and the NSA colluded to find a
preimage -- "everyone" knows that NSA can do such things -- and
complain to the judge.  Or let's turn it around.  The FBI prepares two
documents with a collision, one of interest to me and the other
incriminating.  A undercover agent sends me the first one, which I
save.  I'm arrested -- and the FBI lab substitutes in the second file.
The logs will still match, but I'm being convicted based on faked
evidence.  Or I just tell the judge that that's what the FBI did.

Ever since Dobbertin's partial attack on MD5 in 1996, it's been very
clear that one should not use it for new applications, and that one
should phase it out of most older ones (HMAC-MD5 is an exception).  I
assert that continuing to use it in the DCS-3000 is not justifiable,
especially because the FBI is operating in an adversarial environment.

So -- I assert that when we complained about MD5 in our recent article,
we knew exactly what we were saying and got our facts and our analysis
precisely right.
> 
> Once again, this is one of those things that just pushes my buttons,
> sorry if I went off on a rant...
> 
> W
> 
> P.S: Yes thanks, I am feeling better now :-)
> 
I hope I haven't ruined that.


		--Steve Bellovin, http://www.cs.columbia.edu/~smb



More information about the NANOG mailing list