Re: The Pointlessness of the MD5 "attacks"

[Ben Laurie]

Adam Back wrote:
Is this the case?  Can't we instead start with code C and malicious C'
and try to find a collision on H(C||B) == H(C'||B') after trying 2^64
B values we'll find such a collision by the birthday principle.
Indeed, but that is not the attack suggested.
Now we can have people review and attest to the correctness of code C,
and then we can MITM and change surrepticiously with C'.
And with only 2^64 effort. Let me know when you're done.
Adam
On Wed, Dec 15, 2004 at 08:44:03AM +, Ben Laurie wrote:
Adam Back wrote:
Well the people doing the checking (a subset of the power users) may
say "I checked the source and it has this checksum", and another user
may download that checksum and be subject to MITM and not know it.
You are missing the point - since the only way to make this trick work 
is to include a very specific chunk of 64 bytes with a few bits flipped 
(or not), the actual malicious code must be present anyway and triggered 
by the flipped bits. So, all of these attacks rely on the code not being 
inspected or being sufficiently cunning that inspection didn't help. 
And, if that's the case, the attacks work without any MD5 trickery.



--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Cryptography Research wants piracy speed bump on HD DVDs

[R.A. Hettinga]

The Register


 Biting the hand that feeds IT

The Register » Internet and Law » Digital Rights/Digital Wrongs »


Cryptography Research wants piracy speed bump on HD DVDs
By Faultline (peter at rethinkresearch.biz)
Published Wednesday 15th December 2004 11:49 GMT

Analysis Just about a year from today, if not sooner, if we believe the
outpourings of both the DVD Forum and the Blu-Ray Disc Association, we will
be able to go out to the shops and buy blue laser, high definition, high
density DVDs in two completely different designs. We will also be able to
buy the players and recorders by then, as well as studio content from
virtually every major studio in the world, on one or the other system.

If you believe the hype, DVD manufacturers will likely have to buy in two
types of DVD manufacturing equipment. Households will have to buy two DVD
players. Consumers will have to buy one PC with one type of high density
DVD player and buy another separate player to read the other format of disk.
We neither believe the hype, nor understand the argument between the two
formats. Surely a single format is better for everyone, but it appears not.
Every round of format wars that have gone on since the original VHS Betamax
wars, has been split, and the result a draw, and it looks like this one
will be too.

In the end the devices are likely to be virtually identical. The Sony-
Panasonic-Philips camp that inspired the Blu-ray version may have slightly
more capacity on their discs, that's the official view right now, but it
might change. They also have devices out right now and have had them for
over a year, but they are very expensive, up at around $2,000 and are not
the volume versions that will be able to play pre-recorded material.
Eventually these devices will be about 10 per cent more than DVD players
are now.

The DVD Forum backed Toshiba and NEC technology may be slightly cheaper for
studios to manufacture, but then again we only have the word of Toshiba on
that, and most DVD producers seem set on supporting both.

The disks need to play on PCs, as well as DVDs and games consoles, and it
is unlikely that anyone is going to shoot themselves in the foot by making
a disc that is incompatible with any of these devices.

So Microsoft's VC 9 codec has to be supported, as does the prevalent MPEG2
and H.264 codecs, and nobody is planning to argue the toss about the
quality of sound from Dolby. So there is a chance that all of the software
on top of these disks is going to be identical.

In the end all of the Blu-ray manufacturers are still in the DVD Forum, and
given that the Blu-ray leaders make about 90 per cent of the worlds DVD
players and that half of the studios have backed the DVD Forum standard,
their players may well end up playing both formats. The early consumers may
well be asking "What's the difference" a year from now having little clue
as to how different the two technologies are, under the "hood."

But what if they each choose a different way to protect the content on
their disks? How much danger would that put the two groups in?

The Content Scrambling System of the DVD has come in for a lot of criticism
over the years, as piracy has become relatively rampant. It was designed
more or less as a speed bump to put off anyone other than the professional
pirate. But then along came the internet, and it has become possible for
anyone to download CSS circumvention or to read up, on various websites,
how to go about it. The speed bump has been somewhat flattened and it needs
reinforcement in the next technology.

So it falls to these same companies to build something for the studios that
will be rather harder and more persuasive, to act as a hurdle against
piracy for these new DVDs. In fact an organization called Advanced Access
Content System (AACS), formed back in July by such notables as IBM, Intel,
Microsoft, Panasonic, Sony, Toshiba, Disney and Warner Brothers has come
together in order to create a decent speed bump against piracy that should
last at least for the next decade, a decade during which broadband lines
improve to the point where it will be child's play to download even a high
definition movie.

The definition of what is required has been very clear from the studios.
They want a system that has the ability for the security logic to be
renewed and which should also have some form of forensic marking in order
to help track pirates.

At the heart of this protection system will be the safety of the revenue of
all the major studios, which now get way in excess of 50 per cent of any
given film's revenues from DVD sales.

Faultline talked over such a system with its authors this week, who are
optimistic about its bid to become the new, but more sophisticated CSS for
the next generation DVD disk.

Cryptographic Research's senior security architect, who also mockingly
refers to himself as "chief anti-pirate" is Carter Laren, and Crypt

Re: The Pointlessness of the MD5 'attacks'

[Tim Dierks]

On Wed, 15 Dec 2004 08:51:29 +, Ben Laurie <[EMAIL PROTECTED]> wrote:
> People seem to be having a hard time grasping what I'm trying to say, so
> perhaps I should phrase it as a challenge: find me a scenario where you
> can use an MD5 collision to mount an attack in which I could not mount
> an equally effective attack without using an MD5 collision.

Here's an example, although I think it's a stupid one, and agree with
you that the MD5 attack, as it's currently known to work, isn't a
material problem (although it's a clear signal that one shouldn't use
MD5):

I send you a binary (say, a library for doing AES encryption) which
you test exhaustively using black-box testing. The library is known
not to link against any external APIs (in fact, perhaps it's
implemented in a language and runtime with a decent security sandbox
model, e.g., Java). You then incorporate it into your application and
sign the whole thing with MD5+RSA to vouch for its accuracy.

I incorporate several copies of a suitable MD5 collision block in my
library, so one of them will be at the correct 64-byte block boundary.
I can then modify bits inside of my library, which car checked by the
library code and cause it to change the functionality of the library,
yet the signature will still verify.

This would be pretty easy to do as a proof-of-concept, but I don't
have the time.

- Tim


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: The Pointlessness of the MD5 "attacks"

[Jay Sulzberger]

On Tue, 14 Dec 2004, Ben Laurie wrote:
Ondrej Mikle wrote:
On Tue, 14 Dec 2004 14:43:24 +, Ben Laurie <[EMAIL PROTECTED]> wrote:
But the only way I can see to exploit this would be to have code that
did different things based on the contents of some bitmap. My contention
is that if the code is open, then it will be obvious that it does
"something bad" if a bit is tweaked, and so will be suspicious, even if
the "something bad" is not triggered in the version seen.

There are many ways to obfuscate code so tha it will seem innocent,
see for example International Obfuscated C Code Contest
(http://www.ioccc.org/main.html).
That does not make it seem innocent, it makes it seem incomprehensible.
No.  The C library, running on hardware without serious defenses, is
sufficiently obscure, that one more possibility of spoofing makes things
worse.

It can be based on variable
modification using buffer overflows, integer overflows, strange side
effects of expression evaluation, etc.
I agree, but you do not need MD5 attacks to achieve these things.
Yes, but having a crack for a crypto hash makes all these things easier.

Another possibility for an attacker is the use of deliberate and very
rare race conditions, which only attacker knows how to trigger. Race
conditions are very difficult to discover. Cf. Linux ptrace race
condition 
(http://archives.neohapsis.com/archives/bugtraq/2001-10/0135.html).
It's been there in kernels 2.2.0 - 2.2.19 and 2.4.0 to 2.4.9. It
allowed for local privilege escalation. Took quite a long time to
discover it, even though it was open source code. Quite a long time
for opportunity, if we assumed an attacker would do similar attack
deliberately.
Again, MD5 does not improve these attacks.
It can help disguise such attacks.

So, to exploit this successfully, you need code that cannot or will not
be inspected. My contention is that any such code is untrusted anyway,
so being able to change its behaviour on the basis of embedded bitmap
changes is a parlour trick.

That's true in theory, but it's different in real world. Take
Microsoft software as an example. Many banks use their software (and
sometimes even military). I don't think that all of them reviewed
Microsoft's source code (I guess only a few, if any at all). There was
an incident of a worm attacking ATMs.
No, and they are therefore vulnerable to Microsoft. Note that MD5 is not 
required for Microsoft to attack them.
Again, the MD5 crack helps.  Here one attack is obvious: third parties may
more easily make substitutions of code.

Another example, Enigma was being sold after WW 2, but the Allies knew
it could be broken. The purchasers did not. Same as when US army sold
some radio communications that used frequency hopping to Iraq during
1980's. US knew that it could be broken ("just in case...").
And MD5 helps with this how?
Cheers,
Ben.
The MD5 crack helps here in several ways.  Perhaps the most important is
that if MD5 is thought to be uncracked, that simple MD5 checking might be
considered so safe that no second check is used, at points where a second
and third check would help, thus opening up a possible avenue of attack.
Indeed, even before MD5 was widely known to be cracked, competent security
folk often recommended that several hashes be used since in most
applications the cost of computing hashes is small.  One point to remember
is that the published cracks are likely only a small part of the cracks
known to well funded professionals.  The parallel to the case of the weak
Enigmas is that many people buying the weak Enigmas thought they were
uncracked, else they would not have bought them.  Despite the recent
published MD5 cracks, it is clear that the most interesting cracks of MD5
are as yet unpublished.
oo--JS.
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: The Pointlessness of the MD5 "attacks"

[John Kelsey]

>From: Ben Laurie <[EMAIL PROTECTED]>
>Sent: Dec 14, 2004 9:43 AM
>To: Cryptography <[EMAIL PROTECTED]>
>Subject: The Pointlessness of the MD5 "attacks"

>Dan Kaminsky's recent posting seems to have caused some excitement, but 
>I really can't see why. In particular, the idea of having two different 
>executables with the same checksum has attracted attention.

>But the only way I can see to exploit this would be to have code that 
>did different things based on the contents of some bitmap. My contention 
>is that if the code is open, then it will be obvious that it does 
>"something bad" if a bit is tweaked, and so will be suspicious, even if 
>the "something bad" is not triggered in the version seen.

>So, to exploit this successfully, you need code that cannot or will not 
>be inspected. My contention is that any such code is untrusted anyway, 
>so being able to change its behaviour on the basis of embedded bitmap 
>changes is a parlour trick. You may as well have it ping a website to 
>find out whether to misbehave.

So, are you sure there can never be a program which allows such an exploit?  
I've seen programs that had embedded components (state machines in particular) 
which were not easily human-readable, and had themselves been generated by 
computer.  And even large graphics, sound, or video sequences can really change 
the meaning of a program's actions in some ways; those might be susceptible to 
the requirements of the attack.  I agree it's hard to see how to exploit the 
existing MD5 collision attacks in programs that would look innocent, but I 
don't see what makes it *impossible*.  

Then you have data files, as Adam Back mentioned, which are often not human 
readable, but you'd still like to know if the signature on them is valid, or if 
they've been changed surreptitiously since the last time they were checked 
over.  

Finally, I'm very skeptical that the attacks that have been found recently are 
the best or only ones that can be done.
Do we have any special reason to think that there will never be a way to adapt 
the attack to be able to slip something plausible looking into a C program?  
Once your hash function starts allowing collisions, it really just becomes a 
lot less valuable.  

>Cheers,
>Ben.

--John

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: The Pointlessness of the MD5 "attacks"

[Ben Laurie]

Adam Back wrote:
Well the people doing the checking (a subset of the power users) may
say "I checked the source and it has this checksum", and another user
may download that checksum and be subject to MITM and not know it.
Or I could mail you the source and you would check it with checksum
and compare checksum to web site.
Or somone could just go ahead and change the source without changing
the checksum or any of the changlog / cvs change notification stuff
and people would not think there is a change to review.
>
Some of this scenarios will likely work some of the time against
users.
You are missing the point - since the only way to make this trick work 
is to include a very specific chunk of 64 bytes with a few bits flipped 
(or not), the actual malicious code must be present anyway and triggered 
by the flipped bits. So, all of these attacks rely on the code not being 
inspected or being sufficiently cunning that inspection didn't help. 
And, if that's the case, the attacks work without any MD5 trickery.

Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: The Pointlessness of the MD5 "attacks"

[Adam Back]

Is this the case?  Can't we instead start with code C and malicious C'
and try to find a collision on H(C||B) == H(C'||B') after trying 2^64
B values we'll find such a collision by the birthday principle.

Now we can have people review and attest to the correctness of code C,
and then we can MITM and change surrepticiously with C'.

Adam

On Wed, Dec 15, 2004 at 08:44:03AM +, Ben Laurie wrote:
> Adam Back wrote:
> >Well the people doing the checking (a subset of the power users) may
> >say "I checked the source and it has this checksum", and another user
> >may download that checksum and be subject to MITM and not know it.
>
> You are missing the point - since the only way to make this trick work 
> is to include a very specific chunk of 64 bytes with a few bits flipped 
> (or not), the actual malicious code must be present anyway and triggered 
> by the flipped bits. So, all of these attacks rely on the code not being 
> inspected or being sufficiently cunning that inspection didn't help. 
> And, if that's the case, the attacks work without any MD5 trickery.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: The Pointlessness of the MD5 "attacks"

[Bill Frantz]

On 12/14/04, [EMAIL PROTECTED] (Ben Laurie) wrote:

>Dan Kaminsky's recent posting seems to have caused some excitement, but 
>I really can't see why. In particular, the idea of having two different 
>executables with the same checksum has attracted attention.
>
>But the only way I can see to exploit this would be to have code that 
>did different things based on the contents of some bitmap. My contention 
>is that if the code is open, then it will be obvious that it does 
>"something bad" if a bit is tweaked, and so will be suspicious, even if 
>the "something bad" is not triggered in the version seen.
>
>So, to exploit this successfully, you need code that cannot or will not 
>be inspected. My contention is that any such code is untrusted anyway, 
>so being able to change its behaviour on the basis of embedded bitmap 
>changes is a parlour trick. You may as well have it ping a website to 
>find out whether to misbehave.

One scenario that might form an attack is to take code which is normally 
distributed in executable form, for example RPMs, and make it possible to have 
two different programs that pass the same signature check.  Given that someone 
has arranged to have the doppleganger blocks generated as part of the output of 
the compiler, different binaries can later be injected into the distribution 
system without a signature verification failure.

Cheers - Bill

-
Bill Frantz| The first thing you need when  | Periwinkle 
(408)356-8506  | using a perimeter defense is a | 16345 Englewood Ave
www.pwpconsult.com | perimeter. | Los Gatos, CA 95032

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: The Pointlessness of the MD5 "attacks"

[Ben Laurie]

Bill Frantz wrote:
On 12/14/04, [EMAIL PROTECTED] (Ben Laurie) wrote:

Dan Kaminsky's recent posting seems to have caused some excitement,
but I really can't see why. In particular, the idea of having two
different executables with the same checksum has attracted
attention.
But the only way I can see to exploit this would be to have code
that did different things based on the contents of some bitmap. My
contention is that if the code is open, then it will be obvious
that it does "something bad" if a bit is tweaked, and so will be
suspicious, even if the "something bad" is not triggered in the
version seen.
So, to exploit this successfully, you need code that cannot or will
not be inspected. My contention is that any such code is untrusted
anyway, so being able to change its behaviour on the basis of
embedded bitmap changes is a parlour trick. You may as well have it
ping a website to find out whether to misbehave.

One scenario that might form an attack is to take code which is
normally distributed in executable form, for example RPMs, and make
it possible to have two different programs that pass the same
signature check.  Given that someone has arranged to have the
doppleganger blocks generated as part of the output of the compiler,
different binaries can later be injected into the distribution system
without a signature verification failure.
Indeed, but what's the point? If you control the binary, just distribute 
the malicious version in the first place.

People seem to be having a hard time grasping what I'm trying to say, so 
perhaps I should phrase it as a challenge: find me a scenario where you 
can use an MD5 collision to mount an attack in which I could not mount 
an equally effective attack without using an MD5 collision.

So, for example, in the scenario above, the attacker has control of a 
binary in which he can insert arbitrary content. Clearly, in his place, 
I can simply distribute malware without any MD5 collisions.

Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: The Pointlessness of the MD5 "attacks"

[Ben Laurie]

Adam Back wrote:
I thought the usual attack posited when one can find a collision on a
source checksum is to make the desired change to source, then tinker
with something less obvious and more malleable like lsbits of a UI
image file until you find your collision on two input source packages.
Quite so, but the "desired change to source" is either not visible, or 
suspicious. If it's not visible, then just make it malicious. And if 
it's suspicious then it shouldn't be run.

Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: The Pointlessness of the MD5 "attacks"

[Adam Back]

Well the people doing the checking (a subset of the power users) may
say "I checked the source and it has this checksum", and another user
may download that checksum and be subject to MITM and not know it.

Or I could mail you the source and you would check it with checksum
and compare checksum to web site.

Or somone could just go ahead and change the source without changing
the checksum or any of the changlog / cvs change notification stuff
and people would not think there is a change to review.

Some of this scenarios will likely work some of the time against
users.

Adam

On Tue, Dec 14, 2004 at 11:21:13PM +, Ben Laurie wrote:
> Adam Back wrote:
> >I thought the usual attack posited when one can find a collision on a
> >source checksum is to make the desired change to source, then tinker
> >with something less obvious and more malleable like lsbits of a UI
> >image file until you find your collision on two input source packages.
> 
> Quite so, but the "desired change to source" is either not visible, or 
> suspicious. If it's not visible, then just make it malicious. And if 
> it's suspicious then it shouldn't be run.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]