MD5CRK is now LIVE
Jean-Luc Cooke
First talked about here in sci.crypt and picked up on slashdot.org
(http://www.md5crk.com/official_golive.php).
We have gone live. Press release:
(http://www.md5crk.com/official_golive.php)
Cheers,
JLC
--
WinTerMiNator
"Jean-Luc Cooke" <jlc...@engsoc.org> a écrit dans le message de
news:c1vlkt$s8n$1...@driftwood.ccs.carleton.ca...
I think MD5 weakness (birthday attack) can be demonstrated mathematically;
no use to do a large scale brute force attack. See a mathematical
explanation here (in French):
http://www.chez.com/winterminator/birthday.pdf.
Regards,
--
Michel Nallino aka WinTerMiNator
http://www.chez.com/winterminator
(Internet et sécurité: comment surfer en paix)
http://www.gnupgwin.fr.st
(GnuPG pour Windows)
Adresse e-mail: http://www.cerbermail.com/?vdU5HHs5WG
Jean-Luc Cooke
> I think MD5 weakness (birthday attack) can be demonstrated mathematically;
> no use to do a large scale brute force attack. See a mathematical
> explanation here (in French):
> http://www.chez.com/winterminator/birthday.pdf.
Agreed...but why is the amazon.com /ebay.comsite protected using md5 signatures?
We need to bully people around to help them get a clue.
JLC
--
Gregory G Rose
I won't run a precompiled binary on our machines,
but the FAQ guide on how to get source doesn't
tell me the password that sourceforge wants. I
don't do much of this; maybe you think it's common
knowledge, but it isn't to me...
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
David Wagner
>WinTerMiNator <m...@privacy.net> wrote:
>> I think MD5 weakness (birthday attack) can be demonstrated mathematically;
>
Perhaps because a 2^64 level of security is good enough for Amazon/EBay?
I guess if you are able to find a collision in MD5 by assembling enough
computing power cheaply, you'll have proven that assumption wrong, of course.
Gregory G Rose
David Wagner <daw-u...@taverner.cs.berkeley.edu> wrote:
>I guess if you are able to find a collision in MD5 by assembling enough
>computing power cheaply, you'll have proven that assumption wrong, of course.
"Thirteen days, and still no sight of land!"
"Have we started again?"
-- Monty Python.
James Vanns
sticking this in a cron job over night or something. Or can it run as
a daemon and just use idle time?
Jim
Jean-Luc Cooke <jlc...@engsoc.org> wrote in message news:<c1vlkt$s8n$1...@driftwood.ccs.carleton.ca>...
Francois Grieu
> if someone were to invest the $100,000USB required
> to build an MD5 machine (that find collisions on MD5)
> they could forge digital signatures, circumvent password
> systems and tamper with sensitive, protected documents
> without detection.
Finding collisions on MD5 does NOT help to attack
"password systems" based on MD5.
And it helps against "digital signatures" and "tampering
with sensitive, protected documents without detection" only
inasmuch as one can partialy chose the documents that are
signed.
François Grieu
Volker Hetzer
"Francois Grieu" <fgr...@micronet.fr> schrieb im Newsbeitrag news:fgrieu-C360AA....@news.fu-berlin.de...
a different document.
Lots of Greetings!
Volker
WinTerMiNator
"David Wagner" <d...@taverner.cs.berkeley.edu> a écrit dans le message de
news:c20hsb$jvs$1...@agate.berkeley.edu...
> Jean-Luc Cooke wrote:
> >WinTerMiNator <m...@privacy.net> wrote:
> >> I think MD5 weakness (birthday attack) can be demonstrated
mathematically;
> >
> >Agreed...but why is the amazon.com /ebay.comsite protected using md5
signatures?
>
> Perhaps because a 2^64 level of security is good enough for Amazon/EBay?
Or maybe, simply because if they use MD5 as a hash algorithm for digital
X509 certificate, they are not in the situation where birthday attack can
apply, and they have (concerning MD5) full 128 bits protection!
The major risk with MD5 is more due to the fact it has been partially
cracked, and so, as a hash algorithm, should be discarded for SHA1, RipeMD,
SHA2...
Jean-Luc Cooke
Good password systems like /etc/shadow and PAM use a proper salting
technique which makes a collision attack a little less practical - agreed.
But many "roll your own" password systems used in online sites and such
don't do things correctly.
JLC
--
Jean-Luc Cooke
> In article <c1vlkt$s8n$1...@driftwood.ccs.carleton.ca>,
> Jean-Luc Cooke <jlc...@engsoc.org> wrote:
> >http://www.md5crk.com/
> >
> >First talked about here in sci.crypt and picked up on slashdot.org
> >(http://www.md5crk.com/official_golive.php).
> >
> >We have gone live. Press release:
> > (http://www.md5crk.com/official_golive.php)
> I won't run a precompiled binary on our machines,
> but the FAQ guide on how to get source doesn't
> tell me the password that sourceforge wants. I
> don't do much of this; maybe you think it's common
> knowledge, but it isn't to me...
Doc has been changed. Just hit enter, no password needed.
JLC
--
Jean-Luc Cooke
> I don't suppose the source is available to us is it? I don't mind
> sticking this in a cron job over night or something. Or can it run as
> a daemon and just use idle time?
http://www.md5crk.com/?sec=howhelp
The process runs in nice(-19) always.
Cheers,
JLC
> Jean-Luc Cooke <jlc...@engsoc.org> wrote in message news:<c1vlkt$s8n$1...@driftwood.ccs.carleton.ca>...
> > http://www.md5crk.com/
> >
> > First talked about here in sci.crypt and picked up on slashdot.org
> > (http://www.md5crk.com/official_golive.php).
> >
> > We have gone live. Press release:
> > (http://www.md5crk.com/official_golive.php)
> >
> > Cheers,
> >
> > JLC
> >
> > --
--
Francois Grieu
Jean-Luc Cooke <jlc...@engsoc.org> wrote:
> Francois Grieu <fgr...@micronet.fr> wrote:
> > Finding collisions on MD5 does NOT help to attack
> > "password systems" based on MD5.
>
> Good password systems like /etc/shadow and PAM use a proper salting
> technique which makes a collision attack a little less practical
> - agreed.
Salting is not what I was thinking of. My point is that the attack
attempted finds 2 messages with the same hash, and this is of no help
to find one message with a given hash. In most scenarios (including
passwords) the later is what the attacker wants to do.
François Grieu
Jean-Luc Cooke
> Salting is not what I was thinking of. My point is that the attack
> attempted finds 2 messages with the same hash, and this is of no help
> to find one message with a given hash. In most scenarios (including
> passwords) the later is what the attacker wants to do.
And if the attacker has a way of giving you a document A which they've
crafted another document B which has the same MD5 hash, then you're in
trouble.
And in the example of a contract, digital vertificate, and comprimized
code, this is exacatly what someone will do. Attack the item *before*
it is in your hands.
JLC
--
Francois Grieu
Jean-Luc Cooke <jlc...@engsoc.org> wrote:
> Francois Grieu <fgr...@micronet.fr> wrote:
> > Salting is not what I was thinking of. My point is that the attack
> > attempted finds 2 messages with the same hash, and this is of no help
> > to find one message with a given hash. In most scenarios (including
> > passwords) the later is what the attacker wants to do.
>
> And if the attacker has a way of giving you a document A which they've
> crafted another document B which has the same MD5 hash, then you're in
> trouble.
Agreed, or course; it was envisionned in my earlier post:
>>>> Finding collisions on MD5 does NOT help to attack
>>>> "password systems" based on MD5.
>>>> And it helps against "digital signatures" and "tampering
>>>> with sensitive, protected documents without detection" only
>>>> inasmuch as one can partialy chose the documents that are
>>>> signed.
> And in the example of a contract, digital certificate, and
> comprimized code, this is exacatly what someone will do.
> Attack the item *before* it is in your hands.
We agree that a collision does not help against a password system.
In the case of a contract, the attack won't work on a document
in plain text, RTF, vanilla HTML: it requires the use of some
programming language (e.g. Postscript) in the document viewer.
Also the attack will be detectable by an expert examining the
two disputed documents, and if who prepared the document is
irrefutable, this party will be in a rather embarassing position.
(Stating who prepared the contract in the MD5-hashed portion
of the document does not help to prevent the attack, though).
In the case of digitaly signed code, an adversary who can choose
a portion of the code (which is necessary to take advantage of an
MD5 collision) can in many real life situations plant malicious code
with a hard-to-find trigger that the procedures leading to code
signing will fail to detect. If the adversary can "pull the trigger"
after validation, she can mount an attack without the capability
of an MD5 collision.
In summary, the practical usefullness of being able to find an MD5
collision is much lower than of a preimage attack. When MD5CRK
will suceed, the result won't reduce to nothing the security given
by MD5; it however will make it easier to mount attacks everyone
(thinking about the problem) know are feasible now.
François Grieu
Jean-Luc Cooke
> > comprimized code, this is exacatly what someone will do.
> > Attack the item *before* it is in your hands.
> We agree that a collision does not help against a password system.
> In the case of a contract, the attack won't work on a document
> in plain text, RTF, vanilla HTML: it requires the use of some
> programming language (e.g. Postscript) in the document viewer.
> Also the attack will be detectable by an expert examining the
> two disputed documents, and if who prepared the document is
> irrefutable, this party will be in a rather embarassing position.
> (Stating who prepared the contract in the MD5-hashed portion
> of the document does not help to prevent the attack, though).
Why not text, rtf or HTML? Read van Oorschoot's paper:
http://www.scs.carleton.ca/~paulv/papers/acmccs94.pdf
Text:
Yours,
Jane Doe <jane.{random text}@mycompany.com>
HTML:
<!-- ... random text to alter ... -->
I'm sure RTF has a comment mode as well. And using ' ', '\r' ,'\t',
'\n' as an alphabet, you can use white space 4-letter alphabet
encoding.
> In the case of digitaly signed code, an adversary who can choose
> a portion of the code (which is necessary to take advantage of an
> MD5 collision) can in many real life situations plant malicious code
> with a hard-to-find trigger that the procedures leading to code
> signing will fail to detect. If the adversary can "pull the trigger"
> after validation, she can mount an attack without the capability
> of an MD5 collision.
> In summary, the practical usefullness of being able to find an MD5
> collision is much lower than of a preimage attack. When MD5CRK
> will suceed, the result won't reduce to nothing the security given
> by MD5; it however will make it easier to mount attacks everyone
> (thinking about the problem) know are feasible now.
And if someone has constructed a $100K van Oorschoot device today, would
you make that same statement?
JLC
--
Francois Grieu
Jean-Luc Cooke <jlc...@engsoc.org> wrote:
>>> And in the example of a contract, digital certificate, and
>>> comprimized code, this is exacatly what someone will do.
>>> Attack the item *before* it is in your hands.
>
>> We agree that a collision does not help against a password system.
>
>> In the case of a contract, the attack won't work on a document
>> in plain text, RTF, vanilla HTML: it requires the use of some
>> programming language (e.g. Postscript) in the document viewer.
>> Also the attack will be detectable by an expert examining the
>> two disputed documents, and if who prepared the document is
>> irrefutable, this party will be in a rather embarassing position.
>> (Stating who prepared the contract in the MD5-hashed portion
>> of the document does not help to prevent the attack, though).
>
> Why not text, rtf or HTML? Read van Oorschoot's paper:
> http://www.scs.carleton.ca/~paulv/papers/acmccs94.pdf
I think you refer to this part:
# Now suppose we have a message m that we would like our
# adversary to digitally sign, but he is not willing to do so.
# A simple attack on the hash function can help to acquire the
# desired signature as follows [25]. Choose some other
# message m' that the adversary is willing to sign. Find
# several ways to modify each of m and m' that do not alter
# their respective semantic meaning (e.g., adding extra spaces
# or making small changes in wording). The combinations of
# message modifications lead to many versions of a message,
# all of which have essentially the same meaning. Then hash
# the different versions of m and m' until we find two versions
# that give the same hash result. The adversary will sign the
# version of m', and we can move the signature to m. This
# attack requires O(n^(1/2)) time and space, where n = |R|.
Note the "all of which have essentially the same meaning", which
clearly indicates the attack is of no direct practical value,
unless some "interpreter" expands the effect of the change
(this is easy with postscript, javascript, word with macros..)
> Text:
> Yours,
> Jane Doe <jane.{random text}@mycompany.com>
This one is clever: you are using the email adressing system
as the interpreter, so that the change will address the email
to the wrong mailbox. Still it remains theoretical, because
the random text would need to contain about 128 bits of
randomness, that is like 18 random-looking characters.
Clearly whoever chose BOTH email addresses is an accomplice
of the attacker.
Also, note that unless MD5CRK is setup right from the start
to produce messages colliding with text in this particular
format, the collision MD5CRK will exhibit won't help to
perform this attack.
BTW, how EXACTLY are the colliding messages MD5CRK will
produce structured? I get they will contain a 32 character
segment of random letters among the 16 most frequent english
letters, but what is there before this segment, and
immediatly after up to the next 64 bytes multiple?
It would be more demonstrative to your point if all was
printable ASCII, and chosen to be viewable by some standard
process, producing widely different display (say on a web
browser with javascript enabled). This is easy, but must be
setup before starting the attack.
>> In summary, the practical usefullness of being able to
>> find an MD5 collision is much lower than of a preimage
>> attack. When MD5CRK will suceed, the result won't reduce
>> to nothing the security given by MD5; it however will
>> make it easier to mount attacks everyone (thinking about
>> the problem) know are feasible now.
>
> And if someone has constructed a $100K van Oorschoot device
> today, would you make that same statement?
Yes. Anyone relying on the difficulty to find MD5 collision
is making a mistake. In many practical cases, MD5 users are
not making this mistake. This includes
- using MD5 in password systems.
- publishing thru a trusted channel the MD5 hash of an
executable one distribute thru an untrusted channel,
after one has compiled it from trusted sources and
libraries on a trusted system.
In both cases, one is using the difficulty to find an MD5
preimage (original first preimage, or second preimage),
which is NOT endangered by the kind of attack MD5CRK is
performing (though it is possibly challengable by other
means).
I do acknowledge that using MD5 in a digital signature
system is a bad idea, at least because the system (even
if safe) risks discredit. And that MD5CRK will make this
even clearer.
My point is that <http://www.md5crk.com/?sec=howinsecure>
oversells the significance of the effort:
% MD5CRK "does not directly attack any file, program or
% password program - that would be irresponsible."
Fact is the method MD5CRK uses DOES NOT help break a
password system based on MD5, or produce a file with the
same MD5 hash as an existing file but different content.
% payXXX "relies on the MD5 algorithm to prove
% to your web browser that it is in fact" payXXX
AFAIK, the method MD5CRK uses DOES NOT help pose
as payXXX in the system used.
François Grieu
Jean-Luc Cooke
> I do acknowledge that using MD5 in a digital signature
> system is a bad idea, at least because the system (even
> if safe) risks discredit. And that MD5CRK will make this
> even clearer.
> My point is that <http://www.md5crk.com/?sec=howinsecure>
> oversells the significance of the effort:
> % MD5CRK "does not directly attack any file, program or
> % password program - that would be irresponsible."
> Fact is the method MD5CRK uses DOES NOT help break a
> password system based on MD5, or produce a file with the
> same MD5 hash as an existing file but different content.
> % payXXX "relies on the MD5 algorithm to prove
> % to your web browser that it is in fact" payXXX
> AFAIK, the method MD5CRK uses DOES NOT help pose
> as payXXX in the system used.
I never claim to be trying to attack a live system. And yes, this is
for demonstration purposes only. As any attack on a cryptosystem has
been for the past 20 years (think DC on DES, the d.net DES challanges,
the RSA challanges - none were of "live" use. But it got the point
across).
I am trying to raise awareness that MD5 shouldn't be used because if
someone has the $100K to do so, many people would be at risk. I can see
wew are agreed on this at least.
JLC
--
Francois Grieu
Jean-Luc Cooke <jlc...@engsoc.org> wrote:
> Francois Grieu <fgr...@micronet.fr> wrote:
> > I do acknowledge that using MD5 in a digital signature
> > system is a bad idea, at least because the system (even
> > if safe) risks discredit. And that MD5CRK will make this
> > even clearer.
>
> > My point is that <http://www.md5crk.com/?sec=howinsecure>
> > oversells the significance of the effort:
>
> > % MD5CRK "does not directly attack any file, program or
> > % password program - that would be irresponsible."
>
> > Fact is the method MD5CRK uses DOES NOT help break a
> > password system based on MD5, or produce a file with the
> > same MD5 hash as an existing file but different content.
>
> > % payXXX "relies on the MD5 algorithm to prove
> > % to your web browser that it is in fact" payXXX
>
> > AFAIK, the method MD5CRK uses DOES NOT help pose
> > as payXXX in the system used.
>
> I never claim to be trying to attack a live system.
This is not my point. My point is that even if MD5CRK wanted
to do so, it COULD NOT attack any deployed password system,
or forge an SSL certificate.
Why? An ideal hash functions has 3 properties [*]:
1) preimage resistance
2) 2nd-preimage resistance
3) collision resistance
Password systems rely on property 1.
SSL certificates rely on property 2.
MD5CRK and the $100K machine you cite break property 3 of MD5,
but do NOT, and CAN NOT, attack it's properties 1 or 2.
> I am trying to raise awareness that MD5 shouldn't be used
> because if someone has the $100K to do so, many people would
> be at risk. I can see we are agreed on this at least.
We agree on the first of these three lines, at least for systems
that need to make users confident they are secure.
Fact is most users of MD5 are NOT vulnerable to the attack this
$100K machine allows. But shareholders of payXXX indeed are at
risk that customers of payXXX have less confidence in payXXX's
system after MD5CRK, because said customers do not quite grasp
the distinction between collision resistance and 2nd-preimage
resistance; or infer that if payXXX uses an outdated hash,
payXXX may have other, serious weakness.
I maintain that
<http://www.md5crk.com/?sec=whatismd5>
is misleading, as is citing companies using MD5
<http://www.md5crk.com/?sec=whatismd5>
without stating that the overall system these companies use
is NOT vulnerable to the kind of attack MD5CRK attempts.
François Grieu
[*] see the Handbook of Applied Cryptography, section 9.2.2
<http://www.cacr.math.uwaterloo.ca/hac/about/chap9.pdf>
Francois Grieu
Jean-Luc Cooke <jlc...@engsoc.org> wrote:
> Francois Grieu <fgr...@micronet.fr> wrote:
> > I do acknowledge that using MD5 in a digital signature
> > system is a bad idea, at least because the system (even
> > if safe) risks discredit. And that MD5CRK will make this
> > even clearer.
>
> > My point is that <http://www.md5crk.com/?sec=howinsecure>
> > oversells the significance of the effort:
>
> > % MD5CRK "does not directly attack any file, program or
> > % password program - that would be irresponsible."
>
> > Fact is the method MD5CRK uses DOES NOT help break a
> > password system based on MD5, or produce a file with the
> > same MD5 hash as an existing file but different content.
>
> > % payXXX "relies on the MD5 algorithm to prove
> > % to your web browser that it is in fact" payXXX
>
> > AFAIK, the method MD5CRK uses DOES NOT help pose
> > as payXXX in the system used.
>
> I never claim to be trying to attack a live system.
This is not my point. My point is that even if MD5CRK wanted
to do so, it COULD NOT attack any deployed password system,
or forge an SSL certificate.
Why? An ideal hash functions has 3 properties [*]:
1) preimage resistance
2) 2nd-preimage resistance
3) collision resistance
Password systems rely on property 1.
SSL certificates rely on property 2.
MD5CRK and the $100K machine you cite break property 3 of MD5,
but do NOT, and CAN NOT, attack it's properties 1 or 2.
> I am trying to raise awareness that MD5 shouldn't be used
> because if someone has the $100K to do so, many people would
> be at risk. I can see we are agreed on this at least.
We agree on the first of these three lines, at least for systems
that need to make users confident they are secure.
Fact is most users of MD5 are NOT vulnerable to the attack this
$100K machine allows. But shareholders of payXXX indeed are at
risk that customers of payXXX have less confidence in payXXX's
system after MD5CRK, because said customers do not quite grasp
the distinction between collision resistance and 2nd-preimage
resistance; or infer that if payXXX uses an outdated hash,
payXXX may have other, serious weakness.
I maintain that
<http://www.md5crk.com/?sec=howinsecure>
Jean-Luc Cooke
> This is not my point. My point is that even if MD5CRK wanted
> to do so, it COULD NOT attack any deployed password system,
> or forge an SSL certificate.
> Why? An ideal hash functions has 3 properties [*]:
> 1) preimage resistance
> 2) 2nd-preimage resistance
> 3) collision resistance
> Password systems rely on property 1.
> SSL certificates rely on property 2.
> MD5CRK and the $100K machine you cite break property 3 of MD5,
> but do NOT, and CAN NOT, attack it's properties 1 or 2.
Let's consider this theorical senario:
- I generate a certificate for md5crk.com with a 128bit portion which I
can alter at will without changing the end-user expirience of the
certificate
- I generate a certificate for www.paypal.com with a 128bit portion which
I can alter at will without changing the end-user expirience of the
certificate
- I produce a collision using these two certs as my template.
- I send md5crk.com to VeriSign to be signed.
- I splice the md5crk.com signature to my fake www.paypal.com
certificate.
Would this all be done with "attacking property 3" ?
--
Jean-Luc Cooke
> That's the attack Schneier describes in his book and suggests that, as
> a defense, you always alter some insignificant detail before you sign
> anything submitted by someone else.
>
> I don't know if Verisign does this. If not, they're not using MD5 for
> what it was designed and are only getting resilience to attacks that
> cannot perform more than 2^64 operations rather than attacks that
> cannot perform more than 2^128 operations.
If they are not doing this, that is correct. If you examine certs issued
by VeriSign, you'll see they are not.
A quick fix to this would be:
a) Don't use MD5, but SHA-1 (SHA-256 is not in all browsers yet)
b) Change the X509 standard to use HMAC with a Salt stored in a new field
in the cert:
signature = RSAEncrypt(privateKey, HMAC(Salt, Data))
Where HMAC is either HMAC-MD5 or HMAC-SHA1. Yes you could just use
Hash(Salt CAT Data), but might as well do things properly.
c) Less drasticly breaking every browser: Add a OU=<randomtext> to the
DN of the cert you're issuing. X509 certs can have more then 1 OU=
tag.
(a) requires NO change to current processes.
(b) is very drastic and will break everything.
(c) would be best and can be done right now with a small change to current
cert issuing practices
JLC
--
Paul Rubin
> - I generate a certificate for md5crk.com with a 128bit portion which I
> can alter at will without changing the end-user expirience of the
> certificate
Sure, you can alter the 128 bit portion at will, but the 128 bit
portion is a hash of an RSA public key, which means that you have to
generate a new RSA public key to change the hash. RSA key generation
is quite slow.
In other regards your trick is very clever and effective. Maybe if
DSA certs were more widely deployed in browsers, it would even be
dangerous.
Francois Grieu
Jean-Luc Cooke <jlc...@engsoc.org> wrote:
> Let's consider this theorical senario:
> - I generate a certificate for md5crk.com with a 128bit
> portion which I can alter at will without changing the
> end-user expirience of the certificate
> - I generate a certificate for www.paypal.com with a
> 128bit portion which I can alter at will without
> changing the end-user expirience of the certificate
> - I produce a collision using these two certs as my
> template.
> - I send md5crk.com to VeriSign to be signed.
> - I splice the md5crk.com signature to my fake
> www.paypal.com certificate.
>
> Would this all be done with attacking collision resistance?
Yes. Your latest post acted like an eye-opener to me.
I mean it. My reasoning on why SSL certificates would be
out of reach of MD5CRK, or simimar, was incorrect.
As you show, SSL certificates are vulnerable to certain
form of message collision attacks. I now have to dive into
the details of the format of SSL certs to try determine
if they are vulnerable, or not, to Paul van Oorschot and
Michael Wiener's attack, or simple extensions thereof.
Until that's done, and maybe after, I'm no longer sure
SSL certificates based on MD5 are safe.
BTW, unless I am badly mistaken in the other direction,
Paul van Oorschot and Michael Wiener's attack can be
extended, with only a doubling of the effort, to find
MD5-colliding messages with entirely chosen and
different beginning, provided
- the messages are of the same length
- one is willing to tolerate about 128 bits of
randomness in the last 512 bits block where the
(padded) messages differ.
Again, my apologies; and thanks for showing me the
light.
Francois Grieu
David Wagner
>Jean-Luc Cooke <jlc...@engsoc.org> writes:
>> - I generate a certificate for md5crk.com with a 128bit portion which I
>> can alter at will without changing the end-user expirience of the
>> certificate
>
>Sure, you can alter the 128 bit portion at will, but the 128 bit
>portion is a hash of an RSA public key, which means that you have to
>generate a new RSA public key to change the hash. RSA key generation
>is quite slow.
I'm not so sure. If I'm allowed to choose the public exponent, then RSA
key generation is very fast. Pick n once, then choose lots of different
exponents e and hash each of them. I can wait until after I know which
one gives me a collision to compute the private exponent d.
Paul Rubin
> >Sure, you can alter the 128 bit portion at will, but the 128 bit
> >portion is a hash of an RSA public key, which means that you have to
> >generate a new RSA public key to change the hash. RSA key generation
> >is quite slow.
>
> I'm not so sure. If I'm allowed to choose the public exponent, then RSA
> key generation is very fast. Pick n once, then choose lots of different
> exponents e and hash each of them. I can wait until after I know which
> one gives me a collision to compute the private exponent d.
You're going to send two different cert requests to Verisign with the
same n and hope they don't notice? Other than that, good point.
Jean-Luc Cooke
> Yes. Your latest post acted like an eye-opener to me.
> I mean it. My reasoning on why SSL certificates would be
> out of reach of MD5CRK, or simimar, was incorrect.
> As you show, SSL certificates are vulnerable to certain
> form of message collision attacks. I now have to dive into
> the details of the format of SSL certs to try determine
> if they are vulnerable, or not, to Paul van Oorschot and
> Michael Wiener's attack, or simple extensions thereof.
> Until that's done, and maybe after, I'm no longer sure
> SSL certificates based on MD5 are safe.
> BTW, unless I am badly mistaken in the other direction,
> Paul van Oorschot and Michael Wiener's attack can be
> extended, with only a doubling of the effort, to find
> MD5-colliding messages with entirely chosen and
> different beginning, provided
> - the messages are of the same length
> - one is willing to tolerate about 128 bits of
> randomness in the last 512 bits block where the
> (padded) messages differ.
I would agree, since the 128bit state would be the same into the last
md5-compress function. Back in the day when I tried to "latch on" to
the NEO project, I proposed a contract from Homer Simpson to Bart
Simpson where Homer promised Bart $1, but Bart being a deceptivly
cleaver cryptographer would re-write the contract to some random 128 bit
value (odds are, a very large number).
Two things changed - 1) I saw that NEO wasn't going to be the privider I
wanted 2) explaining the contract and the collision attack and how it's
very different from RC5 attacks was too much for the average user to
take in when looking for a DC project.
> Again, my apologies; and thanks for showing me the
> light.
Glad I could help, you too helped me by forcing me to distill my
explaination. Thank you.
JLC
--
Michael Amling
While Jean-Luc Cooke may be able to control 128 bits of his
certificate request, what the certificate authority signs is not the
hash of the certificate request, but the hash of the certificate. So,
does the attack require predicting the portion of the content of
resulting certificate that does not come from the controllable
certificate request? Just checkin', sarge.
--Mike Amling
Paul Rubin
> While Jean-Luc Cooke may be able to control 128 bits of his
> certificate request, what the certificate authority signs is not the
> hash of the certificate request, but the hash of the certificate. So,
> does the attack require predicting the portion of the content of
> resulting certificate that does not come from the controllable
> certificate request? Just checkin', sarge.
That's a good point. Certificates have serial numbers. Verisign
certificate serial numbers are 128 bits and they look random. Other
CA's seem to assign serial numbers in sequence.
Jean-Luc Cooke
> While Jean-Luc Cooke may be able to control 128 bits of his
> certificate request, what the certificate authority signs is not the
> hash of the certificate request, but the hash of the certificate. So,
> does the attack require predicting the portion of the content of
> resulting certificate that does not come from the controllable
> certificate request? Just checkin', sarge.
Correct. But if you know ahead of time what the certificate will look
like, and you *do* have some control over what goes into the
certificate, it would be possible.
The CA could make a work-around by adding a random OU=ASDFGHJKLasdfghjkl
to the DN requested by the user - then the user would not know what the
signed data ahead of time to use in their attack.
JLC
--
Michael Amling
> Jean-Luc Cooke <jlc...@engsoc.org> writes:
>
>> - I generate a certificate for md5crk.com with a 128bit portion which I
>> can alter at will without changing the end-user expirience of the
>> certificate
>
> Sure, you can alter the 128 bit portion at will, but the 128 bit
> portion is a hash of an RSA public key, which means that you have to
> generate a new RSA public key to change the hash. RSA key generation
> is quite slow.
The hash that the certificate authority signs covers the RSA public
key and pretty much everything else in the certificate. Jean-Luc Cooke
can modify the OU in the Issued To part to vary the hash, leaving the
RSA public key unchanged.
>
> In other regards your trick is very clever and effective. Maybe if
> DSA certs were more widely deployed in browsers, it would even be
> dangerous.
--Mike Amling
Paul Rubin
> The hash that the certificate authority signs covers the RSA public
> key and pretty much everything else in the certificate. Jean-Luc Cooke
> can modify the OU in the Issued To part to vary the hash, leaving the
> RSA public key unchanged.
The OU is the part that the CA manually checks, and they may not be
willing to sign something with a weird 128-bit number in it. There's
some other areas which you can play with (maybe including the public
exponent as David Wagner suggested) but I think the CA's inserting a
random serial number into the cert (as Verisign does) defeats the
whole scheme. Even the sequential serial numbers that some other CA's
use makes the attack pretty difficult in practice.
Michael Amling
Also, isn't there a manual verification process for server SSL
certificates, whose time varies, causing some unpredictability in the
expiration date, which is to the minute?
--Mike Amling
Jean-Luc Cooke
> That's a good point. Certificates have serial numbers. Verisign
> certificate serial numbers are 128 bits and they look random. Other
> CA's seem to assign serial numbers in sequence.
Humm, that *is* interesting. Thawte seems to have a 24bit serial
number. At first glance this would certainly agrevate an collision
attack. Humm...
JLC
--
Francois Grieu
Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> Certificates have serial numbers. Verisign certificate
> serial numbers are 128 bits and they look random. Other
> CA's seem to assign serial numbers in sequence.
This corroborates info at
http://www.cs.auckland.ac.nz/~pgut001/pubs/x509guide.txt
so as my sampling of (few) certs.
I believe that messages bound to have at least 64 bits of
unpredictable data before any data an attacker would need
to change, are imune to extensions of Paul van Oorschot
and Michael Wiener's attack. That would include X509
certificate with enough unpredictable data in the
certificate serial number field, which appears to be at
least Verisign's practice.
On the other hand, if an attacker can arbitrarily change
at least 128 bit worth of information and can predict
all data before the last 512 bit block she needs to
change in a message, then the PvO/MW attack has a direct
extension. That could apply to X509 certificates with
some plausible assumptions on the signing process.
To illustrate Jean-Luc Cooke's attack plot and David
Wagner's choice of the random section, imagine an
hypothetical certificate format containing:
- Predictable data (e.g. sequential serial number)
- Assignee information
- CA information
- Assignee's RSA modulus n
- Assignee's RSA public exponent e, with at least
127 bits of e (except high and low bits of e) lying
in the same 512 bits block
- Predictable data (or more bits of e) up to the next
512 bit boundary
- Data uncorrelated to the above, possibly unpredictable
- Signature of MD5 hash of the above by the CA
The attacker
- Selects a modulus n with known factorization, and two
big prime factors p, each such that (p-1)/2 is prime.
- Fixes high and low bits of e to 1, and fixed random
values for other bits of e not in the 127 bits.
- Performs two partial hashes, up to and not including
the 512 bits block holding the 127 bits, with two
assignee information data (same length); one related
to an entity she controls, the other related to an
entity under attack; keep note of the 128 bits
intermediary hashes ABCD0 and ABCD1.
- Defines the function F: V -> F(V) with V a 128 bit
block, defined as the 128 bits result of an MD5 round
with hashed data the 512 bit block containing the 127
bits segment of e, with this segment replaced by the
127 high bits of V, and initial MD5 state ABCD0 or
ABCD1 depending on the low bit of V.
- Finds a collision on F, using the cycling and
distinguished point strategy in Paul van Oorschot and
Michael Wiener's paper, giving V0 != V1 with
F(V0) = F(V1).
- With probability about 1/2, V0 and V1 differ in the
low bit; else find another collision, which is
expected to require only little extra work, until
this condition is met; order things so that V0
applies to ABCD0, and V1 applies to ABCD1.
With overwhelming probability the values e0 and e1
corresponding to V0 and V1 are coprime with phi(n).
- Computes the corresponding inverses d0 and d1
modulo phi(n).
- Submit a certificate request to the CA, with assignee
information pertaining to the entity she controls,
and e = e0; get the certificate.
- In this certificate change the assignee information
to match the attacked entity, and set e = e1; this
gives a valid certificate for the entity under attack,
with the corresponding RSA secret key (n,d1) known.
We are getting close to a practicable attack!
Francois Grieu
David Wagner
>On the other hand, if an attacker can arbitrarily change
>at least 128 bit worth of information and can predict
>all data before the last 512 bit block she needs to
>change in a message, then the PvO/MW attack has a direct
>extension.
That's oh so clever. Nice observation -- this shows that it's not enough
just to include some unpredictable information in what you hash; that
information must, in fact, come first, if you want to resist collision
attacks. Maybe this is a good argument to use HMAC_salt(data), where
salt is unpredictable and data is what you wanted to hash.
Michael Amling
> In article <7xwu5uj...@ruckus.brouhaha.com>,
> Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
>
>
>>Certificates have serial numbers. Verisign certificate
>>serial numbers are 128 bits and they look random. Other
>>CA's seem to assign serial numbers in sequence.
>
>
> This corroborates info at
> http://www.cs.auckland.ac.nz/~pgut001/pubs/x509guide.txt
> so as my sampling of (few) certs.
>
> I believe that messages bound to have at least 64 bits of
> unpredictable data before any data an attacker would need
> to change, are imune to extensions of Paul van Oorschot
> and Michael Wiener's attack. That would include X509
> certificate with enough unpredictable data in the
> certificate serial number field, which appears to be at
> least Verisign's practice.
>
> On the other hand, if an attacker can arbitrarily change
> at least 128 bit worth of information and can predict
> all data before the last 512 bit block she needs to
> change in a message, then the PvO/MW attack has a direct
> extension. That could apply to X509 certificates with
> some plausible assumptions on the signing process.
Why "at least 128 bits worth of information"? A little over 2**64
different certificate requests would seem to be enough.
--Mike Amling
Francois Grieu
Michael Amling <nos...@nospam.com> wrote:
> Francois Grieu wrote:
> > On the other hand, if an attacker can arbitrarily change
> > at least 128 bit worth of information and can predict
> > all data before the last 512 bit block she needs to
> > change in a message, then the PvO/MW attack has a direct
> > extension. That could apply to X509 certificates with
> > some plausible assumptions on the signing process.
>
> Why "at least 128 bits worth of information"? A little over
> 2**64 different certificate requests would seem to be enough.
Very right; with little over 64 bits worth of randomizable
information, there probably is a collision to be found,
and the search can be distributed in prettly much the same way.
Only problem for the attacker is that if she finds no collision
after exhausting her search space, all work is lost.
Improving a few other details, we can say
Paul van Oorschot and Michael Wiener's distributed MD5
collision search attack has a direct extension to any
partialy chosen messages where an attacker can inject a
little over 64 bits worth of randomizable data, and knows
(or choose) prior to the search all message data not after
the last 512 bit block where the messages differ.
The extension increase the computing time by less than
2r, where r is the number of 512 bits blocks from the
first randomized bit in the message, to the last bit
where the messages differ.
In an hypothetical certificate format:
- Predictable data (e.g. sequential serial number)
- Assignee information
- Predictable data (e.g. CA information, validity..)
- Assignee's RSA modulus n
- Data uncorrelated to the above (e.g. RSA public e),
possibly unpredictable (e.g. unique IDs..)
- Signature of MD5 hash of the above by the CA
some sweet spot for the randomizable data is n.
Specificaly, the attacker can reach r=1 by randomizing the
last (say) 95 bits of the first 512 bits block holding at
least 96 bits worth of n. The attacker first finds a
collision up to this block (of two messages where she chooses
distinct "Assignee information" of the same length); then
after the search finds low bits of n in the next 512 bits
block(s) giving two values of n with known factorization
[even for 1024 bits n and pathological block alignment, it
is fairly easy to come up with such low bits giving one n
that is a perfectly respectable RSA modulus (resisting
conceivable factorisation attempt, including ECM with random
curves), and the other at least has no small factors].
In the case of X509 certificates using the md5RSA algorithm,
defenses against this attack may lie in randomness in the
certificate's serialNumber (and to some degree in validity).
A practical way out of this mess may be that
- CAs randomize the certificate's serialNumber of any
x509 certificate they issue with a 128 bits hash algorithm
(or ban the such algorithms alltogether, but some of their
customers wanting universaly accepted certificates might
complain); and update their policy accordingly.
Doing same rodomization at least for any hash of less
than 256 bits seems sound.
- Responsible maintainers of trusted CA lists ban
CAs that do not act responsibly.
This seems effective assuming the attack has not been
performed until all the CAs in the trusted CAs list have
put the randomization into effect.
There seems to be some level of urgency in raising awareness
on the potential attack, and necessary defense. MD5CRK might
be a way to do this.
Francois Grieu
John E. Hadstate
"David Wagner" <d...@taverner.cs.berkeley.edu> wrote in message
news:c2lbk6$19t4$1...@agate.berkeley.edu...
What would HMAC_salt look like in implementation?
Would it help to replace IPAD and OPAD with a string of (pseudo)random
characters, perhaps derived from the HMAC key?
Michael Amling
> In article <Enw3c.32280$PY.1...@newssvr26.news.prodigy.com>,
> Michael Amling <nos...@nospam.com> wrote:
>
>>Francois Grieu wrote:
>>
>>>On the other hand, if an attacker can arbitrarily change
>>>at least 128 bit worth of information and can predict
>>>all data before the last 512 bit block she needs to
>>>change in a message, then the PvO/MW attack has a direct
>>>extension. That could apply to X509 certificates with
>>>some plausible assumptions on the signing process.
>>
>> Why "at least 128 bits worth of information"? A little over
>>2**64 different certificate requests would seem to be enough.
>
> Very right; with little over 64 bits worth of randomizable
> information, there probably is a collision to be found,
> and the search can be distributed in prettly much the same way.
> Only problem for the attacker is that if she finds no collision
> after exhausting her search space, all work is lost.
If the attacker has some extra CPU cycles, the mydomain.com
certificate request need not even have 2**64 different configurations.
The attacker can probably find a collision with only (2**64)/n different
mydomain.com certificate requests if she can test a little over
(2**64)*n different paypal.com certificates.
--Mike Amling
Michael Amling
> "David Wagner" <d...@taverner.cs.berkeley.edu> wrote in message
> news:c2lbk6$19t4$1...@agate.berkeley.edu...
>
>>Francois Grieu wrote:
>>
>>>On the other hand, if an attacker can arbitrarily change
>>>at least 128 bit worth of information and can predict
>>>all data before the last 512 bit block she needs to
>>>change in a message, then the PvO/MW attack has a direct
>>>extension.
>>
>>That's oh so clever. Nice observation -- this shows that it's not enough
>>just to include some unpredictable information in what you hash; that
>>information must, in fact, come first, if you want to resist collision
>>attacks. Maybe this is a good argument to use HMAC_salt(data), where
>>salt is unpredictable and data is what you wanted to hash.
>
> What would HMAC_salt look like in implementation?
It would look like some number of bytes of salt, followed by the CAs
digital signature of an HMAC, in which the salt was used as the key, of
the certificate being signed. You'd need to get new OIDs. Switching from
MD5 to SHA1 sounds simpler.
--Mike Amling
Francois Grieu
Michael Amling wrote:
> isn't there a manual verification process for server SSL
> certificates, whose time varies, causing some unpredictability
> in the expiration date, which is to the minute?
Reportedly, dates are (since late 1996) mandatorily encoded
with seconds, and it is advisable seconds are never 00. Source:
http://www.cs.auckland.ac.nz/~pgut001/pubs/x509guide.txt
with humorous notes on why century is ommited, and serious
issues for 2038 and 2050.
A sampling of a half a dozen web server certificate using md5RSA
show that some dates are easily predictable (040312235959Z),
some are probably determined by some automatic process
(040331185239Z). All certificates that I scrutinized have one
of the date or serial number with some apparent randomness.
But it is hard to tell from examples if the minutiae of the dates
are from the certificate request, or CA-enforced (only the later
is a working safeguard).
BTW, anyone know a downloadable collection of X509 certificates
from various sources?
Francois Grieu
Francois Grieu
Michael Amling wrote:
> If the attacker has some extra CPU cycles, the mydomain.com
> certificate request need not even have 2**64 different configurations.
> The attacker can probably find a collision with only (2**64)/n different
> mydomain.com certificate requests if she can test a little over
> (2**64)*n different paypal.com certificates.
Clever. A certificate verifier is less stringent on certificate
content than the CA authority is, therefore this can be made to work
in practice. Some bit of CA-acceptable randomness can be spared at
the expense of about doubling the amount of CPU time for each
randomness bit spared.
If data past the modulus n is to be changed (making use of
piublic n as a randomness area computationaly costly), and
if the size and/or content of the public exponent e is restricted,
this might come into play.
Francois Grieu
Paul Rubin
> But it is hard to tell from examples if the minutiae of the dates
> are from the certificate request, or CA-enforced (only the later
> is a working safeguard).
The date in the cert is issued by the CA. It's the time at which the
cert is signed. However, this can be pretty predictable with some
types of cert and some CA's, particularly those with automated
approval systems.
> BTW, anyone know a downloadable collection of X509 certificates
> from various sources?
There's a bunch (CA roots from different CA's) included with OpenSSL.
Barry Fawthrop
How do you know that progress is being made?
I have it running on a Win32 box and over a period of time you will see
Work Unit Complete: xx/200 where XX is increase
Yet on my Mac OS X it shows nothing after setting proxy ''
Thanks in advance
Jean-Luc Cooke
> There seems to be some level of urgency in raising awareness
> on the potential attack, and necessary defense. MD5CRK might
> be a way to do this.
Approximate FLOPS: 340,674,480,128
Though this isn't a true Rmax/Rpeak rating, soon md5crk will beat out
#500 on http://www.top500.org/list/2003/11/
:P
JLC
--
Jean-Luc Cooke
> Thanks in advance
The unix clients (macosx included) only update when they find a DP.
this is because a UNIX user doesn't want to have a GUI. And if they do,
that's what my md5_*.xml files are for. Care to whip up a GUI in Tcl?
:)
JLC
--
Grumble
> The major risk with MD5 is more due to the fact it has
> been partially cracked,
Could you provide a reference supporting this assertion?
Paul Rubin
> > The major risk with MD5 is more due to the fact it has
> > been partially cracked,
>
> Could you provide a reference supporting this assertion?
Jean-Luc Cooke
> http://www.google.com/search?q=dobbertin+md5
This partial crack (better known a a compression function collision) is
less practical than a FULL collision of the MD5 function.
dobbertin's findings are not a monumental as the full collision found
in MD4 which quickly made it obsolete.
JLC
--
Arnold Reinhold
> In article <c2ad1e$k5c$1...@driftwood.ccs.carleton.ca>,
> Jean-Luc Cooke <jlc...@engsoc.org> wrote:
>
...
>
> In the case of digitaly signed code, an adversary who can choose
> a portion of the code (which is necessary to take advantage of an
> MD5 collision) can in many real life situations plant malicious code
> with a hard-to-find trigger that the procedures leading to code
> signing will fail to detect. If the adversary can "pull the trigger"
> after validation, she can mount an attack without the capability
> of an MD5 collision.
>
An insider attempting to plant malicious code runs a serious risk of
detection and perhaps going to prison. But the same insider could make
apparently random changes to code just before release, say by changing
low order bits in icons or altering PRNG initialization seeds. Such
changes would be much less likely to be detected and very hard to
prosecute. They would attract little attention in code reviews. Also
most copies of the program in circulation would contain no defect.
Only selected victims would be induced to use the doctored version of
the program.
Arnold Reinhold
Mok-Kong Shen
Arnold Reinhold wrote:
> Francois Grieu <fgr...@micronet.fr> wrote:
>> Jean-Luc Cooke <jlc...@engsoc.org> wrote:
> ...
>
>>In the case of digitaly signed code, an adversary who can choose
>>a portion of the code (which is necessary to take advantage of an
>>MD5 collision) can in many real life situations plant malicious code
>>with a hard-to-find trigger that the procedures leading to code
>>signing will fail to detect. If the adversary can "pull the trigger"
>>after validation, she can mount an attack without the capability
>>of an MD5 collision.
>>
>
>
> An insider attempting to plant malicious code runs a serious risk of
> detection and perhaps going to prison. But the same insider could make
> apparently random changes to code just before release, say by changing
> low order bits in icons or altering PRNG initialization seeds. Such
> changes would be much less likely to be detected and very hard to
> prosecute. They would attract little attention in code reviews. Also
> most copies of the program in circulation would contain no defect.
> Only selected victims would be induced to use the doctored version of
> the program.
You have well stressed a very essential and general issue
to be constantly kept in mind in using security software
that is not generated under one's strict supervision/control.
Trust is often liable to be misused (exploited by others).
M. K. Shen
Francois Grieu
rein...@world.std.com (Arnold Reinhold) wrote:
> Francois Grieu <fgr...@micronet.fr> wrote
> > In the case of digitaly signed code, an adversary who can choose
> > a portion of the code (which is necessary to take advantage of an
> > MD5 collision) can in many real life situations plant malicious code
> > with a hard-to-find trigger that the procedures leading to code
> > signing will fail to detect. If the adversary can "pull the trigger"
> > after validation, she can mount an attack without the capability
> > of an MD5 collision.
> >
>
> An insider attempting to plant malicious code runs a serious risk of
> detection and perhaps going to prison. But the same insider could make
> apparently random changes to code just before release, say by changing
> low order bits in icons or altering PRNG initialization seeds. Such
> changes would be much less likely to be detected and very hard to
> prosecute. They would attract little attention in code reviews. Also
> most copies of the program in circulation would contain no defect.
> Only selected victims would be induced to use the doctored version of
> the program.
I do agree that an insider can sneak malicious behaviour in hard to
detect ways, and that the ability to find MD5 collisions gives her
a nice trigger, or even way to introduce malicious code (it is possible
to find colliding messages which start is arbitrarily different, and
chosen, so that one is say the bitmap of a company logo with just a
few bits of randomness at the end, rendering in an inperceptible noise;
and the other is loads of arbitrary malicious code with a small random
portion at the end).
My point is that as far as we know, in order to mount such an attack
with a work factor any near 2^64 MD5 rounds, an adversary must be in
a position to choose at least some portion of BOTH messages, thus in a
position to choose some of the genuine code. This very much mitigates
the attack, because
If an adversary can choose some of the genuine code, in practice
she often does not need an MD5 collision to mount an attack. When all
she needs is a trigger, this often can be input data the program
processes (e.g. a special key press sequence). If she needs malicious
code escaping review, maybe she can imagine a discrete buffer overflow
allowing it to be remotely injected; or stick this code in a portion of
a bitmap that is not rendered.
In other words: an MD5 hash remains effective against outsiders.
Guarding against insiders requires a better hash AND additional
safeguards that often are not found in practice.
François Grieu
Jean-Luc Cooke
sustained GFLOPS has just passed the 412, by some definitions of
'supercomputer' this would place it in the Top500 Supercomputing
[Ref2] sites. Yes, it's not linpack, but the instruction inventory
is quite accurate [Ref3].
JLC
Ref1 -
http://slashdot.org/article.pl?sid=03/12/31/2246241&mode=thread&tid=126&tid=172&tid=93&tid=95
Ref2 -
http://www.top500.org/list/2003/11/
Ref3 -
http://www.md5crk.com/stats/topcores.php
JLC
--