Re: MD5 crack for digital certificates

[vtlists () wyae de]

M.D.Mufambisi writes:

> I have been reading about the recent crack on digital certificates
> signed using MD5 hashing algorithm. I am a bit confused by the concept
> and i request clarification from anyone who understands it. From my
> understanding, this is what happens when a certificate is created:
>
> 1. Message hash computed (in this instance using MD5)
> 2. Message hash encrypted with CA private key.
> 3. Message hash appended to certificate.
>
> How then are they "cracking" md5? when there is the encryption done on
> the hash? Im quite hazy on this one.

As was shown on
http://events.ccc.de/congress/2008/Fahrplan/events/3023.en.html
http://dewy.fem.tu-ilmenau.de/CCC/25C3/video_h264_720x576/25c3-3023-en-making_the_theoretical_possible.mp4.torrent
the attack basically works like this:

Regular cert:
1. Message hash computed (in this instance using MD5)
2. Message hash encrypted with CA private key.
3. Message hash appended to certificate.


Attack:
1. Take a signed message, extract MD5 hash
2. Create your own message (any message)
3. Add different paddings to your message until it has the
   known MD5 hash the signed message from (1) has.
   This part is the bruteforcing one. 
4. Replace the original message (1) - only the mkessage text - with
   your own message (2) plus padding, but keep the surrounding MD5/cert
   envelope intact (i.e. copy it 1:1).
5. Voila - your own signed message.

The 25c3 talk cited above is using quite some tricks to ease workload
and simplify MD5 hash calculations, but basically shows that the
attack is within doable dimensions.


> Also, just another one with regards to bruteforce attacks, how does a
> brute force attacker (application) know it has reached the correct
> password? Because to it, they are just characters right? is there a
> flag set by the application being cracked to say "alright, stop, you
> got the right one there?"

With the MD5 bruteforcing you change the plain text and compare the
MD5 hash to the one you already have.

With applications (shell login, POP3 login, FTP login, Web-access
auth...) you simply try against the target, e.g. write a program that
keeps logging in until
   - it does NOT receive an "Invalid login" (HTTP: 401)
or
   - it DOES receive a proper "ok, allowed" code (HTTP: 200)
   
   
Bye

Volker


--

Volker Tanger    http://www.wyae.de/volker.tanger/
--------------------------------------------------
vtlists () wyae de                    PGP Fingerprint
378A 7DA7 4F20 C2F3 5BCC  8340 7424 6122 BB83 B8CB