MD5 collisions
Boudewijn W. Ch. Visser
I have just checked and seen that the messages and IV given
in Dobbertin's paper indeed do collide. The messages and
a small patch for md5.c from the PGP distribution are included,
so that other people can see for themselves what happens.
Below is first explanation of how MD5 works,intended for people
who are not familiar with it.
Very short summary for PGP users : It is not clear as yet if this
attack can be used in a practical way against PGP-signed messages.
But it does mean that MD5 should be replaced in newer versions
of PGP. (imho)
Dobbertin's paper : http://www.cs.ucsd.edu/users/bsy/dobbertin.ps
Boudewijn
+-------------------------------------------------------------------+
|Boudewijn Visser |E-mail:vis...@ph.tn.tudelft.nl |finger for |
|Dep. of Applied Physics,Delft University of Technology |PGP-key |
+-- my own opinions etc --------------------------------------------+
Collisions in the MD5 compression function.
- What exactly has Hans Dobbertin found ? -
In his 2 page paper "Cryptanalysis of MD5 Compress", published May 2
1996, Hans Dobbertin shows that there are collisions in the MD5
compression function.
A collision means that two different messages produce the same output
value. Of course, we are certain that for messages longer than the
hash-output length, there will be collisions. After all, since the
hash-value can have at most 2^128 different output values, if we hash
2^128+1 different messages,we are certain that at least two will have
the same hash. This is called the pigeon-hole principle. But it
shouldn't be too easy to find collisions ! However,finding a collision
in the MD5 compression function takes about 10 hours on a Pentium
computer.
What exactly is the Compress Function in MD5 ?
First lets see how MD5 works. The message is processed in block of 512
bits. The message is first padded so that it is just 64 bits short of a
multiple of 512 bits. This padding is adding a single 1 bit at the end of
the message, and as many 0 bits as are required. Then the original
message length (before the padding) is added as a 64 bit number.Now
the message is an exact multiple of 512 bits. The blocks are processed
as 16 32-bit chunks.
First 4 variables are initialized :
A=0x01234567
B=0x89abcdef
C=0xfedcab98
D=0x76543210
These four variables are now copied into the variables a,b,c,d
and the main loop begins.
These loop is run as long as there are message blocks.
+-------------------------+
| Message Block |
+-------------------------+
/ | | \
/ | | \
/ | | \
/ | | \
/ | | \
/ | | \
+-------+ +-------+ +-------+ +-------+
A-+---| round |--->| round |--->| round |--->| round |->Add-------------A
B-|+--| |--->| |--->| |--->| |---|->Add---------B
C-||+-| 1 |--->| 2 |--->| 3 |--->| 4 |---|---|->Add-----C
D-|||+| |--->| |--->| |--->| |---|---|---|->Add-D
||||+-------+ +-------+ +-------+ +-------+ | | | |
+|||---------------------------------------------------+ | | |
+||-------------------------------------------------------+ | |
+|-----------------------------------------------------------+ |
+---------------------------------------------------------------+
This loop above is the compression function.
The final MD5-hash are the A,B,C,D after the last message block
is processed.
In the rounds there are 4 nonlinear functions :
F(X,Y,Z) = (X And Y) Or ( (Not X) And Z)
G(X,Y,Z) = (X And Z) Or ( Y And (Not Z))
H(X,Y,Z) = X Xor Y Xor Z
I(X,Y,Z) = Y Xor (X Or (Not Z))
One round looks like this :
+------------------------------------------------------------------+
| |
| +----+ |
| | | |
+->| a |-------------------------+ |
| | | |
+----+ | M_j t_i |
| | | | | |
| b |+------------------------|-----|-----|-----------------+ |
| | \ | | | | |
+----+ \ __________ | | | | |
| | +->/Nonlinear \ V V | V |
| c |----->| Function |---->Add-->Add-->Add-->Rotateleft->Add-+
| | +->\__________/
+----+ /
| | /
| d |+
| |
+----+
Now if we write this as :
FF(a,b,c,d,M_j,s,t_i) denotes a = b+((a+F(b,c,d) + M_j + t_i <<<s)
GG(a,b,c,d,M_j,s,t_i) denotes a = b+((a+G(b,c,d) + M_j + t_i <<<s)
HH(a,b,c,d,M_j,s,t_i) denotes a = b+((a+H(b,c,d) + M_j + t_i <<<s)
II(a,b,c,d,M_j,s,t_i) denotes a = b+((a+I(b,c,d) + M_j + t_i <<<s)
(<<<s is a rotating the bits to left over s positions)
/* Round 1 */
FF (a, b, c, d, M_0, 7, 0xd76aa478); /* 1 */
...
FF (b, c, d, a, M_15,22, 0x49b40821); /* 16 */
/* Round 2 */
GG (a, b, c, d, M_1, 5, 0xf61e2562); /* 17 */
...
GG (b, c, d, a, M_12,20, 0x8d2a4c8a); /* 32 */
/* Round 3 */
HH (a, b, c, d, M_5, 4, 0xfffa3942); /* 33 */
...
HH (b, c, d, a, M_2, 23, 0xc4ac5665); /* 48 */
/* Round 4 */
II (a, b, c, d, M_0, 6, 0xf4292244); /* 49 */
...
II (b, c, d, a, M_9, 21, 0xeb86d391); /* 64 */
Most of the round functions deleted for brevity. They can be found in
the RFC. It should be clear that bits are flying all over the place.
The constant t_i are the integer parts of 2^32* abs(sin(i)),with i in
radians.
Finally,as the last message block is processed,the numbers a,b,c,d
form the MD5 hash for the file that has been processed.
Literature : the reference implementation of MD5 can be found in
rfc1321
Applied Cryptography 2nd edition,by Bruce Schneier
===================================================================
Dobbertin has found a collision in the compression function. If you
initialize the a,b,c,d to a certain value (the Initialization
Vector,IV), he has given two different 64-byte (512 bit ) messages that
hash to the same output.
Although this does not mean that it is possible to find colliding
messages to any given message,or even to find a collision when
starting with the standard IV,in my opinion MD5 should be replaced
with a stronger hash-function. SHA-1 and RIPEMD-160 are good
candidates (and as such recommended by Dobbertin).
Below I have appended a small patch for md5.c from PGP-2.6.i,and
the two messages from Dobbertin's paper.
The patch uses Dobbertin's IV,and if you compile md5sum with this
patched MD5 it can be seen that the messages have the same hashes.
The messages should be 64 bytes each.
Copy md5.c and md5.h from the src directory in the pgp distribution
to the contrib/md5sum directory.
Patch md5.c : patch <patch_md5
Compile md5.c : gcc -c md5.c
compile md5sum : gcc md5sum.c md5.o -o md5sum
Now type md5sum Message1
md5sum Message2
(Check your path,to make sure that you don't use the standard md5sum)
This works for me on a Linux machine. Those using a big-endian
computer like Motorola CPU's may have to reverse the byte-order
of the constants. This took me a while when typing things over from
Dobbertin's paper :-(
end
^^^^^^^ Watch the difference.
end
^^^^^^^ Yep. Not the same
--- patch for md5.c --- cut below this line ------------------------
*** md5.c.orig Sun May 26 16:39:18 1996
--- md5.c Sun May 26 20:20:16 1996
***************
*** 45,54 ****
--- 45,61 ----
*/
void MD5Init(struct MD5Context *ctx)
{
+ /* Comment out the original initialisation constants
ctx->buf[0] = 0x67452301;
ctx->buf[1] = 0xefcdab89;
ctx->buf[2] = 0x98badcfe;
ctx->buf[3] = 0x10325476;
+ */
+ /* Patch in the collision IV from Dobbertin's paper */
+ ctx->buf[0] = 0x12ac2375;
+ ctx->buf[1] = 0x3b341042;
+ ctx->buf[2] = 0x5f62b97c;
+ ctx->buf[3] = 0x4ba763ed;
ctx->bits[0] = 0;
ctx->bits[1] = 0;
***************
*** 93,98 ****
--- 100,110 ----
memcpy(ctx->in, buf, 64);
byteReverse(ctx->in, 16);
MD5Transform(ctx->buf, (uint32 *) ctx->in);
+
+ /* Show here the collided data */
+ printf("This is the output after processing the first block:\n");
+ printf("%x %x %x %x \n",ctx->buf[0],ctx->buf[1],ctx->buf[2],ctx->buf[3]);
+
buf += 64;
len -= 64;
}
cts
MD5 collision. Is this of a Useful message? (The original paper is
illegible to most of the world, being PostScript)
cts NSW
(home page killed because it was judged "commercial")
William Unruh
>MD5 collision. Is this of a Useful message? (The original paper is
>illegible to most of the world, being PostScript)
What was shown in the paper was that given a certain input and a given
message that there existed another message differeing from the first in
just one bit which gave the same compressed value. It also took 10 hrs
on a Pentium to find it. There are no details as to how that input was
chosen, nor how that message was chosen. It is not known from the paper
what those 10 hours of calculations consisted of. It is not known
whether this is a weird totaly untypical result, or whether it indicates
a real problem with MD5. It is worrying however since one wants the
compress function to produce an output which differs in about 50% of the
bits if the messages differ in one bit. Maybe almost all do except this
one example. Maybe this indicates a more general problem with MD5.
(certainly if all messages had a collision with another differing by
just one bit, I think it would have been noticed by now.)
Dobbertin claims he used the same technique that he used on MD4 and
RIPEMD[ RIPEMD with two-round compress functin is not collision-free J.
Cryptology (to appear) and Cryptanalysis of MD4 Fast Software
emcryption, LNCS 1039, D. Gollmann, Ed., Springer Verlag, 1996 pp53-69 ]
[Note, ghostscript is a free postscript intepreter, which can print out
or display on most printers/computers. It is well worth getting so as to
alleviate that illegibility problem]
--
Bill Unruh
un...@physics.ubc.ca
Donald T. Davis
William Unruh writes:
> There are no details as to how that input was chosen, nor how that
> message was chosen. It is not known from the paper what those 10 hours
> of calculations consisted of. It is not known whether this is a weird
> totaly untypical result, or whether it indicates a real problem with MD5.
i have corresponded with prof. dobbertin since i
posted my query. his 10-hr computation prepared a
able of special bitstrings and other data, from which
new collision-pairs can be calculated in 15 minutes!
each calculation generates a new iv and a new pair of
colliding inputs, which differ only in one bit. that
bit's position is currently fixed. prof. dobbertin's
attack differs from a similar 1993 collision result,
in that he produces a single iv and a pair of inputs,
while the '93 attack produced a pair of iv's and
either a single input buffer, or a pair of inputs.
it is thought that the current attack carries more
practical import.
i've also corresponded about this with another hash-
cryptanalyst, who is confident that prof. dobbertin's
attack can be extended to one that admits the free
choice of at least some of the colliding input bits.
that is, at least one half of the colliding pair
might make some sense as a message, by the time this
attack has been fully developed.
thank you all for your helpful replies to my question.
-don davis, boston
Paul Rubin
In article <4og4ai$7...@gza-client1.cam.ov.com>,
Donald T. Davis <d...@cam.ov.com> wrote:
>i've also corresponded about this with another hash-
>cryptanalyst, who is confident that prof. dobbertin's
>attack can be extended to one that admits the free
>choice of at least some of the colliding input bits.
Are details of the attack going to be published?
Mutatis Mutantdis
The question should now turn to: what about PGP now?!
Is it worth writing a PGP 2.6.4 that uses SHA-1 as an alternative (I forget
whether current PGP format has notations for alternate algorithms...)? Or
should we wait for PGP3?
d...@cam.ov.com (Donald T. Davis) writes:
>i have corresponded with prof. dobbertin since i
>posted my query. his 10-hr computation prepared a
>able of special bitstrings and other data, from which
[..]
>it is thought that the current attack carries more
>practical import.
>i've also corresponded about this with another hash-
>cryptanalyst, who is confident that prof. dobbertin's
>attack can be extended to one that admits the free
>choice of at least some of the colliding input bits.
Mutatis Mutantdis
I poked around the pgp.h and pgformat.txt files in the PGP 2.6.2
distribution. There *are* designator bytes for the hash (and cipher)
algorithms, hash size, etc.
It seems quite doable to add support for SHA-1 signatures (and possibly key
generation for encrypting secret keys?).
Adding 3DES (and maybe Luby-Rackoff-SHA, assuming it hasn't been cracked
recently at the Fast Software Conf.... more info?!?) would be nifty too...
unless, of course, there's meaning to the Real Soon Now that PGP3 folx
claim.
I
d work on the hack now (and just might...) but I'm stuck stranded in the
United States. :(
Rob.
Boudewijn W. Ch. Visser
wlkn...@unix.asb.com (Mutatis Mutantdis) writes:
>The question should now turn to: what about PGP now?!
>Is it worth writing a PGP 2.6.4 that uses SHA-1 as an alternative (I forget
>whether current PGP format has notations for alternate algorithms...)? Or
>should we wait for PGP3?
That depends on how soon we can expect PGP3....
However,the replacement of MD5 is now needed. Although the current attack
is not of practical use yet,it is very close.
MD5 can now no longer be trusted as a good hash-function,IMHO.
Boudewijn
--
Greg Miller
On Wed, 29 May 1996 19:15:01 GMT, wlkn...@unix.asb.com (Mutatis Mutantdis)
wrote:
>The question should now turn to: what about PGP now?!
>
>Is it worth writing a PGP 2.6.4 that uses SHA-1 as an alternative (I forget
>whether current PGP format has notations for alternate algorithms...)? Or
>should we wait for PGP3?
I believe the answer was: It's too early to say.
"Randomness is in the eye of the beholder" --Numerical Recipes
gre...@mis.net (Greg Miller)
http://grendel.ius.indiana.edu/~gmiller/
Mutatis Mutantdis
vis...@ph.tn.tudelft.nl (Boudewijn W. Ch. Visser) writes:
>wlkn...@unix.asb.com (Mutatis Mutantdis) writes:
[..]
>>Is it worth writing a PGP 2.6.4 that uses SHA-1 as an alternative (I forget
>>whether current PGP format has notations for alternate algorithms...)? Or
>>should we wait for PGP3?
>That depends on how soon we can expect PGP3....
>However,the replacement of MD5 is now needed. Although the current attack
>is not of practical use yet,it is very close.
>MD5 can now no longer be trusted as a good hash-function,IMHO.
From cyphe...@toad.com list (make of it what you will):
Message-Id: <1996052923...@toxicwaste.media.mit.edu>
Date: Wed, 29 May 1996 19:10:11 EDT
From: Derek Atkins <war...@MIT.EDU>
[..]
Both of these algorithms are currently in the PGPlib sources.
-derek
-- End --
Brian B. Riley
-----BEGIN PGP SIGNED MESSAGE-----
In article <4og4ai$7...@gza-client1.cam.ov.com>, d...@cam.ov.com (Donald T.
Davis) wrote:
>William Unruh writes:
>> There are no details as to how that input was chosen, nor how that
>> message was chosen. It is not known from the paper what those 10 hours
>> of calculations consisted of. It is not known whether this is a weird
>> totaly untypical result, or whether it indicates a real problem with MD5.
>
>i have corresponded with prof. dobbertin since i
>posted my query. his 10-hr computation prepared a
>able of special bitstrings and other data, from which
>new collision-pairs can be calculated in 15 minutes!
>each calculation generates a new iv and a new pair of
>colliding inputs, which differ only in one bit. that
>bit's position is currently fixed. prof. dobbertin's
>attack differs from a similar 1993 collision result,
>in that he produces a single iv and a pair of inputs,
>while the '93 attack produced a pair of iv's and
>either a single input buffer, or a pair of inputs.
>it is thought that the current attack carries more
>practical import.
>
>i've also corresponded about this with another hash-
>cryptanalyst, who is confident that prof. dobbertin's
>attack can be extended to one that admits the free
>choice of at least some of the colliding input bits.
>that is, at least one half of the colliding pair
>might make some sense as a message, by the time this
>attack has been fully developed.
>
>thank you all for your helpful replies to my question.
>
> -don davis, boston
I really must question the significance of this. After all the
purpose of the digital signiture is to verify the authenticity
of a message. Even if he can generate an alternative to any given
class of messages with a one-bit difference, what is the probabiity
that a one bit difference in the message could _SO_ alter the message
content as to be a problem? AS it is we are saying that MD5 probability
of duplicating the MD5 hash on a drastic alteration is billions to one.
So I fail to see what bearing a narrow range of specified strings which
can be duped on a one bit position alteration and that bit position, so
far is fixed will have on message authetication.
Now I do see that we could have some problems with digital signitures
on binary files, it might have more impact there.
fixed
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv
iQCVAwUBMa94RDTEZIFmKnZBAQEyhQP/chIdUCdJgvAJlQ2epa6cM07l/lK090AX
ut5Fc/a0HC06srLdG7+gM9P8HvHy4dK8ay9elFH2wCJLw6bwLski+kAy/yno0Y1n
vwgYjr+W/XAriKRlrUxNZLTukRSZdx4C1iaIgA1cSqMpH21zgQVoaH/IiVoLn8CB
b1f1+r11U84=
=GW0A
-----END PGP SIGNATURE-----
--
Brian B. Riley --> http://www.together.com/~brianbr
PGP Key IDs; 1024/662A7641 2047/17C2B699
"If this is the first day of the rest of my life, I am in DEEP trouble!"
Paul Rubin
In article <brianbr-3105...@news.together.net>,
Brian B. Riley <bri...@together.net> wrote:
> I really must question the significance of this. After all the
>purpose of the digital signiture is to verify the authenticity
>of a message. Even if he can generate an alternative to any given
>class of messages with a one-bit difference, what is the probabiity
>that a one bit difference in the message could _SO_ alter the message
>content as to be a problem? AS it is we are saying that MD5 probability
>of duplicating the MD5 hash on a drastic alteration is billions to one.
>So I fail to see what bearing a narrow range of specified strings which
>can be duped on a one bit position alteration and that bit position, so
>far is fixed will have on message authetication.
Small differences (like single bits) are the most important
differences. Here are two messages differing a single bit:
MESSAGE 1:
I will pay you $1,000,000 on June 30, 1996.
MESSAGE 2:
I will pay you $2,000,000 on June 30, 1996.
Let's say you take out a bank loan and affix your digital
signature to message 1 as a promise of repayment.
You definitely don't want the same signature to show
that you signed message 2 instead!
William Unruh
In <phrDsA...@netcom.com> p...@netcom.com (Paul Rubin) writes:
>differences. Here are two messages differing a single bit:
>MESSAGE 1:
> I will pay you $1,000,000 on June 30, 1996.
>MESSAGE 2:
> I will pay you $2,000,000 on June 30, 1996.
Well, actually two bits (in BCD) or 8 bits in binary representation.
A better example is $1000000 to 3000000 in BCD or
$1,048,576 to $3,145,728 in binary, either of which would have made your
point equally well. (changing the exponent in exponential notation would
be even better of course.) :-)
--
Bill Unruh
un...@physics.ubc.ca
Paul Rubin
In article <4oom3u$5...@nntp.ucs.ubc.ca>,
What are you talking about? Both are ascii messages.
You change the digit "1" (61 octal) to a "2" (62 octal).
That's a single bit change.
Mel Wilson
That's a two bit change [no it's not -- it's a whole millon
dolla#@#(%$]. Changing a '1' to (e.g.) a '0', '3', '5' or 'Q' would be
a one bit change. Doesn't alter the original overall argument though.
Regards. Mel.
Arnoud Galactus Engelfriet
-----BEGIN PGP SIGNED MESSAGE-----
In article <phrDsB...@netcom.com>,
p...@netcom.com (Paul Rubin) wrote:
> In article <4oom3u$5...@nntp.ucs.ubc.ca>,
> William Unruh <un...@physics.ubc.ca> wrote:
> >In <phrDsA...@netcom.com> p...@netcom.com (Paul Rubin) writes:
> >>MESSAGE 1:
> >> I will pay you $1,000,000 on June 30, 1996.
> >
> >>MESSAGE 2:
> >> I will pay you $2,000,000 on June 30, 1996.
>
> What are you talking about? Both are ascii messages.
> You change the digit "1" (61 octal) to a "2" (62 octal).
> That's a single bit change.
"1" = 00110001 binary in ASCII (49 decimal)
"2" = 00110010 binary in ASCII (50 decimal)
That's TWO bits which are changed.
Galactus
who feels like nitpicking at this moment
- --
To find out more about PGP, send mail with HELP PGP in the SUBJECT line to me.
E-mail: gala...@stack.urc.tue.nl - Please PGP encrypt your mail if you can.
Finger gala...@turtle.stack.urc.tue.nl for public key (key ID 0x416A1A35).
Anonymity and privacy site: <http://www.stack.urc.tue.nl/~galactus/remailers/>
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: cp850
iQCVAgUBMbCY7TyeOyxBaho1AQGGhwQAx8gXFe6sYpk6skbAUebWR/bLilC5U4az
vtoBjaQVILXSVKeQcT/ZhKGq+unGlxBgTqT+xIXIFkHam8VpbVAJivrK+pLl9AI8
uX7rVti1xO73r0A4LlWttmiu40sF7y3pqeLc0U1xkFPPfKstC2yiMYsvqj76dP7Z
U0916LM9szY=
=60gr
-----END PGP SIGNATURE-----
William Unruh
>What are you talking about? Both are ascii messages.
>You change the digit "1" (61 octal) to a "2" (62 octal).
>That's a single bit change.
I'm sorry but bits refer tot he binary representation of numbers, and
61 and 62 octal differ in two bits -- 110001 and 110010 differ in both the
right most and the second right most bit- one digit but two bits. As I
said, if you use ascii or BCD 1000000 and 3000000 would differ in only
one bit, second most right bit. of the left most byte.
--
Bill Unruh
un...@physics.ubc.ca
Paul Rubin
In article <phrDsB...@netcom.com>, Paul Rubin <p...@netcom.com> wrote:
>In article <4oom3u$5...@nntp.ucs.ubc.ca>,
>William Unruh <un...@physics.ubc.ca> wrote:
>>In <phrDsA...@netcom.com> p...@netcom.com (Paul Rubin) writes:
>>
>>> I will pay you $1,000,000 on June 30, 1996.
>>
>>>MESSAGE 2:
>>> I will pay you $2,000,000 on June 30, 1996.
>>
>>A better example is $1000000 to 3000000 in BCD or
>>$1,048,576 to $3,145,728 in binary, either of which would have made your
>>point equally well. (changing the exponent in exponential notation would
>>be even better of course.) :-)
>
>You change the digit "1" (61 octal) to a "2" (62 octal).
>That's a single bit change.
Whoops, "1" to "2" is a two bit change. Should have said $2 million
and $3 million instead of $1 million and $2 million.
Christopher J. Reimer
: What are you talking about? Both are ascii messages.
: You change the digit "1" (61 octal) to a "2" (62 octal).
: That's a single bit change.
I'll give you a hint, 61 octal is 110001 in binary,
and 62 octal is 11010 in binary. Two bits have changed.
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Christopher Reimer
http://www.doe.carleton.ca/~reimer/
rei...@doe.carleton.ca
Lulu of the Lotus-Eaters
gala...@stack.urc.tue.nl (Arnoud "Galactus" Engelfriet) wrote previously:
*}> >>MESSAGE 1:
*}> >> I will pay you $1,000,000 on June 30, 1996.
*}> >
*}> >>MESSAGE 2:
*}> >> I will pay you $2,000,000 on June 30, 1996.
*}>
*}"1" = 00110001 binary in ASCII (49 decimal)
*}"2" = 00110010 binary in ASCII (50 decimal)
*}
*}That's TWO bits which are changed.
Well... to be REALLY nitpicky, the original poster didn't mention that
ASCII encoding was used, rather than EBCDIC or some other. The moral,
of course, remains the same.
Yours, Lulu...
_/_/_/ THIS MESSAGE WAS BROUGHT TO YOU BY: Postmodern Enterprises _/_/_/
_/_/ ~~~~~~~~~~~~~~~~[qui...@philos.umass.edu]~~~~~~~~~~~~~~~~~ _/_/
_/_/ The opinions expressed here must be those of my employer... _/_/
_/_/_/_/_/_/_/_/_/_/ Surely you don't think that *I* believe them! _/_/
------------------------------------------------------------------------
PGP 2.6 key available by finger <qui...@oitunix.oit.umass.edu>
Bill Sommerfeld
What are you talking about? Both are ascii messages.
You change the digit "1" (61 octal) to a "2" (62 octal).
That's a single bit change.
nope.
061 == 00110001
062 == 00110010
======!!
- Bill
Marc Thibault
p...@netcom.com (Paul Rubin) writes:
>
> What are you talking about? Both are ascii messages.
> You change the digit "1" (61 octal) to a "2" (62 octal).
> That's a single bit change.
No, though it is a 'bitty change. I guess they aren't teaching
machine language anymore. Pity.
Mac McKeon
Bill Sommerfeld wrote:
>
> What are you talking about? Both are ascii messages.
> You change the digit "1" (61 octal) to a "2" (62 octal).
> That's a single bit change.
>
>
> 061 == 00110001
> 062 == 00110010
> ======!!
>
> - Bill
What a two-bit discussion this is turning into! >;)
--
====
/McK
====
"Due to circumstances beyond my control, I am master of my
fate and captain of my soul."
- Ashleigh Brilliant
--
0xADAA2931: 24 83 0B C8 4C AA 8E CD 47 3C 97 4C 9E 43 B1 E4
Matthew Francey
bri...@together.net (Brian B. Riley) wrote:
> what is the probabiity
>that a one bit difference in the message could _SO_ alter the message
>content as to be a problem?
hamming_distance("Pay mdf $100.00", "Pay mdf $900.00") == 1
Lionel Mamane
p...@netcom.com (Paul Rubin) wrote:
>Small differences (like single bits) are the most important
>differences. Here are two messages differing a single bit:
>MESSAGE 1:
> I will pay you $1,000,000 on June 30, 1996.
>MESSAGE 2:
> I will pay you $2,000,000 on June 30, 1996.
Exuse me, but they differ two bits: In ASCII,
1 is 31(hex), 49 (decimal) and 110001 (binary)
2 is 32(hex), 50 (decimal) and 110010 (binary)
Your idea is correct, but not the example! In place, you could take
2,000,000 and 3,000,000: this works: only one bit different
--
Lionel Mamane
PGP Key ID's: 1024bits:F6467875, 2048bits:20C897E9
Dave Sill
p...@netcom.com (Paul Rubin) writes:
> Small differences (like single bits) are the most important
> differences. Here are two messages differing a single bit:
>
> MESSAGE 1:
> I will pay you $1,000,000 on June 30, 1996.
>
> MESSAGE 2:
> I will pay you $2,000,000 on June 30, 1996.
>
> Let's say you take out a bank loan and affix your digital
> signature to message 1 as a promise of repayment.
> You definitely don't want the same signature to show
> that you signed message 2 instead!
Ignoring the fact that that's a two-bit change, all this does is
invalidate the signature, it doesn't change the contract from
$1,000,000 to $2,000,000.
A signs the $1M message, B discovers that the $2M message has the same
MD5 checksum. B demands $2M. A and B go to court. B produces $2M
message and shows it matches A's signature. A produces $1M message and
shows it matches *the same signature*. Judge ignores signature, A and
B present other evidence regarding the contract, case proceeds as if
message was never sent.
It's still *highly* unlikely that there'll be any practical way to
find a useful colliding message any time soon.
--
Dave Sill (d...@ornl.gov) <URL:http://www.lookup.com/Homepages/72300/home.html>
Lockheed Martin Energy Systems, Oak Ridge National Lab, Workstation Support
Stanley Chow
In article <wx0wx1k...@sws5.ctd.ornl.gov>,
Dave Sill <d...@sws5.ctd.ornl.gov> wrote:
>
>Ignoring the fact that that's a two-bit change, all this does is
>invalidate the signature, it doesn't change the contract from
>$1,000,000 to $2,000,000.
Ignoring any change to the contract, invalidating the signature
totally defeats the purpose of a signature in the first place.
>It's still *highly* unlikely that there'll be any practical way to
>find a useful colliding message any time soon.
You *may* be right. A somewhat shacky basis for real electronic
commerce with enforcable signatures.
--
Stanley Chow; sc...@bnr.ca, stanley....@nt.com; (613) 763-2831
Bell Northern Research Ltd., PO Box 3511 Station C, Ottawa, Ontario
Me? Represent other people? Don't make them laugh so hard.
Marc Thibault
Dave Sill <d...@sws5.ctd.ornl.gov> writes:
>
> A signs the $1M message, B discovers that the $2M message has the same
> MD5 checksum. B demands $2M. A and B go to court. B produces $2M
This is not my reading of the problem. In this example, 'A'
would have to generate both messages. I don't see anything in
the paper that suggests 'B' can take an arbitrary signed
message and make a different one with the same signature. It
doesn't even suggest that there is a way to find out whether
it is possible, short of exhaustive search.
It does, however, indicate that it may be possible to generate
two useful messages with the same signature. In the example,
the existence of the two messages would probably constitute
prima facie evidence that 'A' was trying to pull something
off.
After some thought, I can't think of a single useful thing
that could be done with this, unless it's an Ellery Queenish
thing involving sending two different messages to two
different people and taking advantage of their behaviour. A
concrete example escapes me.
Cheers,
Marc
---
This is not a secure channel; Assume nothing.
Marc Thibault Information Systems Architect
http://www.synapse.net/~mthibault
Key fingerprint = 76 21 A3 B2 41 77 BC E8 C9 1C 74 02 80 48 A0 1A
cts
I give up.. MD5,RIPEMD cosidered obsolete..
where can I find Specification or Source code for
RIPE-MD160 or RIPEMD-160 or whatever the new hash is?
(lycos,archie,altavista dont give the actual specs)
cts NSW
Dave Sill
ma...@tanda.on.ca (Marc Thibault) writes:
> Dave Sill <d...@sws5.ctd.ornl.gov> writes:
> >
> > A signs the $1M message, B discovers that the $2M message has the same
> > MD5 checksum. B demands $2M. A and B go to court. B produces $2M
>
> This is not my reading of the problem. In this example, 'A'
> would have to generate both messages.
Why? If you send me a signed message, I can theoretically discover
other messages with the same signature. Perhaps the method outlined in
the recent paper requires access to the private key, but I'm speaking
more generally.
> I don't see anything in
> the paper that suggests 'B' can take an arbitrary signed
> message and make a different one with the same signature. It
> doesn't even suggest that there is a way to find out whether
> it is possible, short of exhaustive search.
I wasn't limiting myself to the technique used in the paper.
> It does, however, indicate that it may be possible to generate
> two useful messages with the same signature. In the example,
> the existence of the two messages would probably constitute
> prima facie evidence that 'A' was trying to pull something
> off.
I don't think so. Given that hashing maps an infinite set of inputs
into a merely huge set of hashes, there *will* be cases where two
similar messages will yield the same hash. It's unlikely, but not
impossible.
> After some thought, I can't think of a single useful thing
> that could be done with this, unless it's an Ellery Queenish
> thing involving sending two different messages to two
> different people and taking advantage of their behaviour. A
> concrete example escapes me.
Say A wants to send B a signed message saying A agrees to do X, but A
doesn't really want to do X--he just wants B to think A's committed to
X. A generates two messages M and M' where M is the agreement to X and
M' is not an agreement to X (could be completely unrelated to X, could
say A does not agree to do X--must be a reasonable message, though,
not gibberish).
A sends B the signed message M. Later, A fails to do X. B sues A,
producing M and its signature. A produces M', claiming it's the
message he sent B, and shows that it, too, matches the signature. B is
screwed.
Dave Sill
sc...@bnr.ca (Stanley Chow) writes:
> In article <wx0wx1k...@sws5.ctd.ornl.gov>,
> Dave Sill <d...@sws5.ctd.ornl.gov> wrote:
> >
> >Ignoring the fact that that's a two-bit change, all this does is
> >invalidate the signature, it doesn't change the contract from
> >$1,000,000 to $2,000,000.
>
> Ignoring any change to the contract, invalidating the signature
> totally defeats the purpose of a signature in the first place.
Agreed.
> >It's still *highly* unlikely that there'll be any practical way to
> >find a useful colliding message any time soon.
>
> You *may* be right. A somewhat shacky basis for real electronic
> commerce with enforcable signatures.
Right, but it's always been true that hashes aren't guaranteed unique.
William Unruh
> This is not my reading of the problem. In this example, 'A'
> would have to generate both messages. I don't see anything in
> the paper that suggests 'B' can take an arbitrary signed
> message and make a different one with the same signature. It
> doesn't even suggest that there is a way to find out whether
> it is possible, short of exhaustive search.
That is precisely what is suggested. Remember what a signature is. IT is
the MD5 hash of the message encrypted with A's secret key. Now if you
have a second message with the same MD5 hash, you (B) can claim that IT
is the one signed by A. The issue was whether a 1 bit different message
could be troublesome The example (poorly designed but trivailly altered
to be a good example) was to show how a 1 bit change could be
troublesome. You are cetainly right that there is nothing to show that
the breaking discovered would change just that right single bit to cause
the trouble. However the demonstration in court that a single bit could
have been changed could cast sufficient doubt on the contract to have it
annulled. This possibility would make those kinds of contract not very
useful. Remember the burden of proof on a new technology is much higher
than on an old technology, even if the old one has obvious problems.
--
Bill Unruh
un...@physics.ubc.ca
Jonathan M. Gilligan
Perhaps I am missing something, but for the truly paranoid encrypting the
whole document with one's private key could function as a signature. This
is not vulnerable to hash collisions and decrypting with the appropriate
public key is an assurance that the item was encrypted with the
corresponding private key.
The downside is that there would be no way to generate a compact
cumulative notary method, as can be effected with one-way hash keys.
However, for those occasions where it might be profitable for an adversary
to invest significant resources in forging a colliding message, encrypting
the whole thing might serve as a more secure signature mechanism.
Jonathan Gilligan
Fran Litterio
-----BEGIN PGP SIGNED MESSAGE-----
Dave Sill <d...@sws5.ctd.ornl.gov> wrote:
> ma...@tanda.on.ca (Marc Thibault) writes:
> > After some thought, I can't think of a single useful thing
> > that could be done with this, unless it's an Ellery Queenish
> > thing involving sending two different messages to two
> > different people and taking advantage of their behaviour. A
> > concrete example escapes me.
> Say A wants to send B a signed message saying A agrees to do X, but A
> doesn't really want to do X--he just wants B to think A's committed to
> X. A generates two messages M and M' where M is the agreement to X and
> M' is not an agreement to X (could be completely unrelated to X, could
> say A does not agree to do X--must be a reasonable message, though,
> not gibberish).
> A sends B the signed message M. Later, A fails to do X. B sues A,
> producing M and its signature. A produces M', claiming it's the
> message he sent B, and shows that it, too, matches the signature. B is
> screwed.
Why B and not A? A and B each present (to the judge) conflicting documents
that both have valid digital signatures. The forger of the signature could
be either A or B with equal likeliehood. The judge is left with only
traditional methods of determining who to believe. B could still win the
case.
All that A has achieved by his deceit is to remove weight of the digital
signature from the dispute. The judge will either decide which signature
is binding based on the facts, or the judge will decide that neither
signature is binding because of the undecidability of the facts (at which
point we fall back to traditional legal proceedings).
- --
Francis Litterio fr...@world.std.com
PGP Public Key Fingerprint: http://world.std.com/~franl/
02 37 DF 6C 66 43 CD 2C 508-263-4141 x123
10 C8 B5 8B 57 34 F3 21 PGP-encrypted email preferred
"Those that give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety." -- Benjamin Franklin (1773)
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: http://world.std.com/~franl/
iQCVAwUBMbgRIHeXQmAScOodAQGkTAP9GFeOhGeZpDH9Z3LGCGUihtCW0AJSX0Cr
crJQvjDf6VyZETkTItK2AM8LlJlUW9k/D4ytz0HPuVDZNPhli6/h3NcrK5JEeaSQ
R7yVZGEAo+GntcPoZcRPP0r2fqaJrC6dM8IFCTEUTa+gTbo0odzii98m+4X3/JWb
9eW0dOPhg0U=
=gnAr
-----END PGP SIGNATURE-----
William Unruh
In <01bb5485.7cab3840$0aa5...@island.vanderbilt.edu> Jonathan M. Gilligan <Jonathan...@Vanderbilt.Ed> writes:
>Perhaps I am missing something, but for the truly paranoid encrypting the
>whole document with one's private key could function as a signature. This
>is not vulnerable to hash collisions and decrypting with the appropriate
>public key is an assurance that the item was encrypted with the
>corresponding private key.
A signature IS the MD5 has of the document, encrypted with one's private
key. Thus a second message withthe same MD5 hash has EXACTLY the same
signature as the first message. Certainly your proposal would work, but
it is not a signature. The advantage of a signature is that you can get
a second person to sign the document without revealing the document to
them (time stamping services, etc)
--
Bill Unruh
un...@physics.ubc.ca
Dave Sill
Followups directed to sci.crypt.
fr...@world.std.com (Fran Litterio) writes:
> Dave Sill <d...@sws5.ctd.ornl.gov> wrote:
>
> > Say A wants to send B a signed message saying A agrees to do X, but A
> > doesn't really want to do X--he just wants B to think A's committed to
> > X. A generates two messages M and M' where M is the agreement to X and
> > M' is not an agreement to X (could be completely unrelated to X, could
> > say A does not agree to do X--must be a reasonable message, though,
> > not gibberish).
>
> > A sends B the signed message M. Later, A fails to do X. B sues A,
> > producing M and its signature. A produces M', claiming it's the
> > message he sent B, and shows that it, too, matches the signature. B is
> > screwed.
>
> Why B and not A? A and B each present (to the judge) conflicting documents
> that both have valid digital signatures. The forger of the signature could
> be either A or B with equal likeliehood.
Agreed.
> The judge is left with only
> traditional methods of determining who to believe. B could still win the
> case.
Right, but B's strongest proof of his claim that A agreed to X is now
worthless. Clearly this hurts B more than A. :-)
> All that A has achieved by his deceit is to remove weight of the digital
> signature from the dispute.
Which is all that his deceit was intended to accomplish. He duped B
into believing B had proof of A's agreement to X. A, of course, was
careful not to leave any other other evidence of his agreement to X:
e.g., no third-party witnesses saw A agree to X, A never agreed to X
over the phone (which could have been overheard or recorded), etc.
A more concrete example. Bill verbally proposes selling a parcel of
land to Joe for $10M. Joe agrees, verbally. Joe e-mail's a letter of
intent to pay Bill $10M for parcel XYZ, digitally signed. Bill
transfers the land to Joe. Bill waits for Joe to pay. Joe doesn't
pay, says he thought the land was gift, per an earlier conversation.
They go to court. Bill produces Joe's signed letter of intent. Joe
produces another letter saying "Thanks for the watch you gave me for
my birthday", also with the same signature. Bill is screwed.
Brian B. Riley
... what you guys keep missing is that you cannot be sure that the
bit-8 in the nine will be ithe position that will permit a one bit
chnage, the author of the exceptions has clealry stAted that for now the
bit position that is 'flexible' is in a fixed position ..... I know you
cannot be sure that it won't but the point is that its still in the
realm of a highly specific exception.
--
Brian B. Riley --> http://www.together.com/~brianbr
PGP Key IDs; 1024/662A7641 2047/17C2B699
"If this is the first day of the rest of my life, I am in DEEP
trouble!"
Patrick J. LoPresti
-----BEGIN PGP SIGNED MESSAGE-----
>>>>> "de5" == Dave Sill <d...@sws5.ctd.ornl.gov> writes:
de5> Right, but it's always been true that hashes aren't guaranteed
de5> unique.
That is a silly argument. Factoring a big number isn't "guaranteed"
to be hard; after all, you might get lucky and just guess one of the
factors at random.
For practical purposes, cryptographic hashes *are* unique. When the
odds of something are 2^64 to 1 in my favor, I consider that a
guarantee.
This attack on MD5 *is* significant, and *does* argue against its
continued use for digital signatures.
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Processed by Mailcrypt 3.4, an Emacs/PGP interface
iQCVAwUBMbifYHr7ES8bepftAQF0oAQAg5eGRdniPzqgeyIJmtRh8KMFvU0/sYe6
l9kXS2vPd3XCV5kRztnG7SkDmfwRNgpONpVpPo7JhbGK6GbJBET1G6cgJlR9M5oH
Y5TwakEYcAeurAa2Gh0oeW965rqCWrj6PMaPMorVRrQWt1aRLEonluBiGcRCATC2
3l9ZWd9hDU0=
=jIPJ
-----END PGP SIGNATURE-----
Patrick J. LoPresti
-----BEGIN PGP SIGNED MESSAGE-----
>>>>> "de5" == Dave Sill <d...@sws5.ctd.ornl.gov> writes:
de5> It's still *highly* unlikely that there'll be any practical way
de5> to find a useful colliding message any time soon.
How about signed binaries, which is a proposed use of digital
signatures? Do you think flipping a bit in a binary could be
sufficient to introduce a security hole?
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Processed by Mailcrypt 3.4, an Emacs/PGP interface
iQCVAwUBMbif+nr7ES8bepftAQHFtwP9HYzGYLH5xKmNApYtptfoWdoUoPxriueP
m1iBnqx0lerSx3lYPdxyJaZ6dDR2hh9MpIF9B5kmoe+YZ9EUXSvoN2DxqGYaWE3p
iclSQYTyQYGe8KdwQj7W/AHmQJUjKPSvaGlNwyksQT3uhgydZWoimz7JxTXNtFl8
3WYrxk1QSlc=
=Tdn/
-----END PGP SIGNATURE-----
Marc Thibault
Dave Sill <d...@sws5.ctd.ornl.gov> writes:
> Why? If you send me a signed message, I can theoretically discover
> other messages with the same signature. Perhaps the method outlined in
> the recent paper requires access to the private key, but I'm speaking
> more generally.
"Theoretically" has always been the case, since the hash is
shorter than the message. "Practically" is what's important,
and Dobbertin hasn't changed that. Dobbertin has figured a way
to generate colliding pairs that don't seem to have any
practical application other than to amaze his friends and
annoy his enemies.
> A sends B the signed message M. Later, A fails to do X. B sues A,
> producing M and its signature. A produces M', claiming it's the
> message he sent B, and shows that it, too, matches the signature. B is
> screwed.
Nope. B has A's committment in message M. There is no reason
for any court to believe that B could have forged it. A's
ability to produce other messages with the signature is
irrelevant because only A can do it. Now - if A could produce
M' with B's signature it would be another matter - but he
can't.
I don't see any threat to PGP here.
Marc Thibault
un...@physics.ubc.ca (William Unruh) writes:
> the MD5 hash of the message encrypted with A's secret key. Now if you
> have a second message with the same MD5 hash, you (B) can claim that IT
> is the one signed by A. The issue was whether a 1 bit different message
For this to work, B has to generate the colliding messages and
get A to sign one of them. The question of who generated the
messages would be important. It also suggests an easy form of
protection against this kind of fraud: 'A' should make an
inconsequential change to the file before signing it.
He should also be very suspicious of anyone who suggests that
they use a custom IV.
Marc Thibault
un...@physics.ubc.ca (William Unruh) writes:
> it is not a signature. The advantage of a signature is that you can get
> a second person to sign the document without revealing the document to
> them (time stamping services, etc)
Although it is true that many documents have the same MD5 hash,
the probability of two documents relating to the same
circumstances and having the same MD5 hash is vanishingly
small. This means that any two such documents would have to
have been generated out of a single process designed to
generate a collision. A timestamp valid for one is valid for
the other.
Marc Thibault
pa...@lcs.mit.edu (Patrick J. LoPresti) writes:
> This attack on MD5 *is* significant, and *does* argue against its
> continued use for digital signatures.
Oops! That doesn't follow at all. The ability to generate
pairs of related documents with the same MD5 hash does not
invalidate MD5. As soon as the existence of such a pair comes
to light, the author can be assumed to be doing research or
attempting some kind of fraud, since generating such a pair
requires a very non-accidental procedure.
So far we've only seen highly contrived scenarios for putting
Dobbertin to use, all of which ignore important facets of how
the real world operates.
Marc Thibault
> signatures? Do you think flipping a bit in a binary could be
> sufficient to introduce a security hole?
If you were authenticating a binary wth a digital signature,
you wouldn't go to the trouble of generating a colliding pair,
one of which had a security hole. Why would you want to weaken
your own authentication?
David Hopwood
In article <wuT7oD...@tanda.on.ca>, Marc Thibault <ma...@tanda.on.ca> wrote:
>pa...@lcs.mit.edu (Patrick J. LoPresti) writes:
>
>> continued use for digital signatures.
>
> Oops! That doesn't follow at all. The ability to generate
> pairs of related documents with the same MD5 hash does not
> invalidate MD5. As soon as the existence of such a pair comes
> to light, the author can be assumed to be doing research or
> attempting some kind of fraud, since generating such a pair
> requires a very non-accidental procedure.
>
> So far we've only seen highly contrived scenarios for putting
> Dobbertin to use, all of which ignore important facets of how
> the real world operates.
Assume this is a couple of years from now, and executable programs are
routinely signed and checked.
Take a signed executable from a widely trusted source, e.g. a web browser.
Change some instruction or constant so that it makes the program exploitable
(for example, change a conditional jump that makes a security check so
that it always succeeds). This assumes that you can choose which bit gets
inverted; I'm not sure whether this is true for Dobbertin's attack, but it's
not implausible.
Then distribute the hacked executable, and write an untrusted program (e.g.
in Java, or Safe-TCL or whatever) that exploits the change.
I'm sure there are lots of other instances where signatures are used for
applications where a change would not be immediately obvious to the user.
David Hopwood
david....@lmh.ox.ac.uk
Marc Thibault
Jonathan M. Gilligan <Jonathan...@Vanderbilt.Ed> writes:
>
> cumulative notary method, as can be effected with one-way hash keys.
Wouldn't the last N bytes of the encrypted file function as a
secure hash?
William Unruh
> "Theoretically" has always been the case, since the hash is
> shorter than the message. "Practically" is what's important,
> and Dobbertin hasn't changed that. Dobbertin has figured a way
> to generate colliding pairs that don't seem to have any
> practical application other than to amaze his friends and
Is his attack at present a practical attack? No. Does it given one the
feeling that a practical attack might be found soon (ie before the
contract I sign today might become moot)- yes. Part of the strength of
contracts is one's faith in them. Once thatgoes, the contract becomes
nearly worthless. You are like the guy at Kitty Hawk who exclaimed-
That's a bloody stupid way to travel a few hundred feet over sand
dunes.
--
Bill Unruh
un...@physics.ubc.ca
Jolt-X
Marc Thibault (ma...@tanda.on.ca) wrote:
: Wouldn't the last N bytes of the encrypted file function as a
: secure hash?
I doubt it. I can see quite a few flaws, especialy in simpler types of
encryption.
--
Jolt-X -- God of All Who Follow | ... Torklamuffin ... Sarkalar ... Bushin ...
mail:jo...@west.net | finger for my public key | theNSAiswatching
http://www.west.net/~joltx | <reserved>
Fingerprint: D7086E47E6494E40 D67B03B5C2D1EC82 :tnirpregniF
T. Jones
Check out http://www.seattle-webworks.com/pgp/ for a very good tutorial
on setting up and using PGP, remailers and anon mailers in Windows.
Help for newbies without condescension!
Peter Gutmann
pa...@lcs.mit.edu (Patrick J. LoPresti) writes:
>>>>>> "de5" == Dave Sill <d...@sws5.ctd.ornl.gov> writes:
> de5> It's still *highly* unlikely that there'll be any practical way
> de5> to find a useful colliding message any time soon.
>How about signed binaries, which is a proposed use of digital
>signatures? Do you think flipping a bit in a binary could be
>sufficient to introduce a security hole?
Yes. Changing a "read" flag to a "write" flag when opening a file (which can
often be accomplished by flipping a single bit) would be enough to destroy data.
Peter.
Marc Thibault
jo...@west.net (Jolt-X) writes:
>
> I doubt it. I can see quite a few flaws, especialy in simpler types of
> encryption.
Undoubtedly there are encryption algorithms that would work
badly this way. On the other hand, if we assume a strong
algorithm like IDEA, Blowfish or multiple-DES run in one of
the feedback modes, the end of the encrypted file is a
function of every bit in the file.
I'm not comfortable with what might be done at the end of the
plaintext, but I'm unable to find an exploitable weakness in
this.
Mutatis Mutantdis
William Unruh
From Dobbertin's article
ftp.esat.kuleuven.ac.be/pub/COSIC/bosselae/ripemd/
contains their article defining RIPEMD-160
>SHA-1?
In Applied Cryptography (Schneier)
--
Bill Unruh
un...@physics.ubc.ca
Boudewijn W. Ch. Visser
ma...@tanda.on.ca (Marc Thibault) writes:
>un...@physics.ubc.ca (William Unruh) writes:
>>
>> Is his attack at present a practical attack? No. Does it given one the
>> feeling that a practical attack might be found soon (ie before the
>> contract I sign today might become moot)- yes. Part of the strength of
> Like everything else in this game, it's a matter of scale.
> What we have is a way of finding an unpredictable IV that
> gives you a 1-bit collision.
> There is a long distance between that and finding a meaningful
> sentence or paragraph that you can convince someone to add to
> a contract, such that you've produced a useful collision.
How do you know this ? *If* your statement could be proven,there
would indeed be no need for concern.
Dobbertin has not published his method yet. And you seem to be sure
that this method can't be extented ?
> Even if the one-bit collision is all you need, you still face
> the problem of finding not just _an_ IV but _a coherent_ IV
> that doesn't tip off your mark. I'd say that's about like
> going from RSA-129 to RSA-1000.
I won't say that. Because in the case of RSA,the factoring algorithms
that were used for RSA-129 (en now for RSA-130) don't seem to
allow such a large improvement. That would probably require
a whole new algorithm.
We can't say such a thing about the collision algorithm.
> The other part of this problem is that hashes aren't unique,
> and it's entirely possible that for every hash algorithm, some
> collision relationship can be found. Dobbertin could make a
> career of finding them. He might even prove the general case.
> What do we do - give up on digital signatures altogether? That
> way lies madness.
Indeed. But collisions that need 2^64 steps or one that can be
done in half a day on a PC are different.
> Technical difficulties aside, there is nothing Dobbertin can
> do or might do that is more of a problem than what is routine
> with paper documents. Electronic contracts, like paper
> contracts exist in a context. We rely on this context for much
> of the authentication of the action documents we use. If
> digital signatures aren't perfect, they are still much less
> imperfect than ink.
With electronics,it should be possible to do better than ink.
> With no exception that I can think of, all of the business
> I've done in the last three or four years has been based on
> faxed or e-mailed documents with my signature pasted from a
> .pcx file. I don't have a molecular fax machine. Some of them
> are MS-Word files where my signature is a separable object.
> Anybody could capture my signature and put it on any document
> at all. Am I at risk? Hardly. Would a post-Dobbertin digital
> signature be more secure? Of course it would.
> We now know that an interesting academic exercise can produce
> demo collisions. We will no doubt be watching carefully to see
> if it goes farther than that. A note I just got from Dobbertin
> suggests that it might. I won't know until I can get to a UNIX
> machine to decode the DVI file he sent me (why anybody would
> use a printer control code as an interchange format escapes me
> completely).
An interchange format should be device independent. If there is anything
I hate,it's people who send their documents in some propietary
wordprocessor format,and assume the whole world has that program.
Of course,he might have sent PostScript.
> In the meantime, we have the advantage in PGP that anyone who
> signs a document is assured that the intended recipient can
> check the signature, because every copy of PGP supports MD5.
> MD5 is still not compromised for real-world purposes and it
> makes no sense to panic.
Nope. But it does make sense to replace MD5 in the next version of PGP.
> PGP remains the best tool for ordinary purposes. In high
> value, high risk, long-term situations, if you're really
> worried, forget hashes and go for full-body encryption where
> collisions are impossible. The extra storage probably won't
> cause any hardship.
> Cheers,
> Marc
Boudewijn
--
+-------------------------------------------------------------------+
|Boudewijn Visser |E-mail:vis...@ph.tn.tudelft.nl |finger for |
|Dep. of Applied Physics,Delft University of Technology |PGP-key |
+-- my own opinions etc --------------------------------------------+
Marc Thibault
un...@physics.ubc.ca (William Unruh) writes:
>
> Is his attack at present a practical attack? No. Does it given one the
> feeling that a practical attack might be found soon (ie before the
> contract I sign today might become moot)- yes. Part of the strength of
Like everything else in this game, it's a matter of scale.
What we have is a way of finding an unpredictable IV that
gives you a 1-bit collision.
There is a long distance between that and finding a meaningful
sentence or paragraph that you can convince someone to add to
a contract, such that you've produced a useful collision.
Even if the one-bit collision is all you need, you still face
the problem of finding not just _an_ IV but _a coherent_ IV
that doesn't tip off your mark. I'd say that's about like
going from RSA-129 to RSA-1000.
The other part of this problem is that hashes aren't unique,
and it's entirely possible that for every hash algorithm, some
collision relationship can be found. Dobbertin could make a
career of finding them. He might even prove the general case.
What do we do - give up on digital signatures altogether? That
way lies madness.
Technical difficulties aside, there is nothing Dobbertin can
do or might do that is more of a problem than what is routine
with paper documents. Electronic contracts, like paper
contracts exist in a context. We rely on this context for much
of the authentication of the action documents we use. If
digital signatures aren't perfect, they are still much less
imperfect than ink.
With no exception that I can think of, all of the business
I've done in the last three or four years has been based on
faxed or e-mailed documents with my signature pasted from a
.pcx file. I don't have a molecular fax machine. Some of them
are MS-Word files where my signature is a separable object.
Anybody could capture my signature and put it on any document
at all. Am I at risk? Hardly. Would a post-Dobbertin digital
signature be more secure? Of course it would.
We now know that an interesting academic exercise can produce
demo collisions. We will no doubt be watching carefully to see
if it goes farther than that. A note I just got from Dobbertin
suggests that it might. I won't know until I can get to a UNIX
machine to decode the DVI file he sent me (why anybody would
use a printer control code as an interchange format escapes me
completely).
In the meantime, we have the advantage in PGP that anyone who
signs a document is assured that the intended recipient can
check the signature, because every copy of PGP supports MD5.
MD5 is still not compromised for real-world purposes and it
makes no sense to panic.
PGP remains the best tool for ordinary purposes. In high
value, high risk, long-term situations, if you're really
worried, forget hashes and go for full-body encryption where
collisions are impossible. The extra storage probably won't
cause any hardship.
Cheers,
Marc
---
Jeffrey Goldberg
-----BEGIN PGP SIGNED MESSAGE-----
On Sat, 8 Jun 1996, Marc Thibault wrote:
> [One] should also be very suspicious of anyone who suggests that
> they use a custom IV.
I think that this is a major point that has been overlooked in the hype
about the Dobbertin paper: That technique uses a non-standard IV, but
in one sense (unless I am mistaken) the standard IV is part of the
definition of MD5. It would be like saying that DES can be weakened
if you use different numbers in the S-boxes. Basically that wouldn't
be DES, and Dobbertin's modifications make that system not MD5.
So, unless that technique and be extented to the real MD5 IV, then
there are no consequences for MD5 or PGP.
I could, of course, have misunderstood.
- -jeff
- --
Jeffrey Goldberg +44 (0)1234 750 111 x 2826
Cranfield Computer Centre FAX 751 814
J.Gol...@Cranfield.ac.uk http://WWW.Cranfield.ac.uk/public/cc/cc047/
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
Comment: Processed by mkpgp, a Pine/PGP interface.
iQCVAgUBMbwNfxu6nIqxqP+5AQFufQP9FQLcPLj/ZPR7QZus8GgoYd708Jw3emD4
yTAsjEnN3hQM8SEDG6xte4I6UNmxsgh1j9AY22U4UfbI5KfR1mB/nPzPljNLtEK6
+A02m2LPlLWDaI6+BmKTWiKAZSfCU6/7+lppK15ugrpawJrPBZQEyPskIU2g7UVF
XqpAard6qLE=
=gvhw
-----END PGP SIGNATURE-----
Boudewijn W. Ch. Visser
ma...@tanda.on.ca (Marc Thibault) writes:
>un...@physics.ubc.ca (William Unruh) writes:
>>
>> Is his attack at present a practical attack? No. Does it given one the
>> feeling that a practical attack might be found soon (ie before the
>> contract I sign today might become moot)- yes. Part of the strength of
> Like everything else in this game, it's a matter of scale.
> What we have is a way of finding an unpredictable IV that
> gives you a 1-bit collision.
> There is a long distance between that and finding a meaningful
> sentence or paragraph that you can convince someone to add to
> a contract, such that you've produced a useful collision.
How do you know this ? *If* your statement could be proven,there
would indeed be no need for concern.
Dobbertin has not published his method yet. And you seem to be sure
that his method can't be extented ?
> Even if the one-bit collision is all you need, you still face
> the problem of finding not just _an_ IV but _a coherent_ IV
> that doesn't tip off your mark. I'd say that's about like
> going from RSA-129 to RSA-1000.
I won't say that. Because in the case of RSA,the factoring algorithms
that were used for RSA-129 (en now for RSA-130) don't seem to
allow such a large improvement. That would probably require
a whole new algorithm.
We can't say such a thing about the collision algorithm.
> The other part of this problem is that hashes aren't unique,
> and it's entirely possible that for every hash algorithm, some
> collision relationship can be found. Dobbertin could make a
> career of finding them. He might even prove the general case.
> What do we do - give up on digital signatures altogether? That
> way lies madness.
Indeed. But 2^64 steps and half a day on a PC are rather different
> Technical difficulties aside, there is nothing Dobbertin can
> do or might do that is more of a problem than what is routine
> with paper documents. Electronic contracts, like paper
> contracts exist in a context. We rely on this context for much
> of the authentication of the action documents we use. If
> digital signatures aren't perfect, they are still much less
> imperfect than ink.
With electronics,it should be possible to do better than ink.
> With no exception that I can think of, all of the business
> I've done in the last three or four years has been based on
> faxed or e-mailed documents with my signature pasted from a
> .pcx file. I don't have a molecular fax machine. Some of them
> are MS-Word files where my signature is a separable object.
> Anybody could capture my signature and put it on any document
> at all. Am I at risk? Hardly. Would a post-Dobbertin digital
> signature be more secure? Of course it would.
> We now know that an interesting academic exercise can produce
> demo collisions. We will no doubt be watching carefully to see
> if it goes farther than that. A note I just got from Dobbertin
> suggests that it might. I won't know until I can get to a UNIX
> machine to decode the DVI file he sent me (why anybody would
> use a printer control code as an interchange format escapes me
> completely).
An interchange format should be device independent. If there is anything
I hate,it's people who send their documents in some propietary
wordprocessor format,and assume the whole world has that program.
Of course,he could perhaps better have sent PostScript.
> In the meantime, we have the advantage in PGP that anyone who
> signs a document is assured that the intended recipient can
> check the signature, because every copy of PGP supports MD5.
> MD5 is still not compromised for real-world purposes and it
> makes no sense to panic.
Nope. But it does make sense to replace MD5 in the next version of PGP.
> PGP remains the best tool for ordinary purposes. In high
> value, high risk, long-term situations, if you're really
> worried, forget hashes and go for full-body encryption where
> collisions are impossible. The extra storage probably won't
> cause any hardship.
> Cheers,
> Marc
Boudewijn
Dave Sill
pa...@lcs.mit.edu (Patrick J. LoPresti) writes:
> de5> It's still *highly* unlikely that there'll be any practical way
> de5> to find a useful colliding message any time soon.
>
> How about signed binaries, which is a proposed use of digital
> signatures? Do you think flipping a bit in a binary could be
> sufficient to introduce a security hole?
Of course. I just don't think, from what I've heard, that that will be
possible any time soon. For one thing, Dobbertin's method seems to
require a nonstandard modification to the MD5 algorithm. For another,
it doesn't seem to let one perform arbitrary one-bit changes.
Want to protect against possible one-bit changes and still use MD5?
Just calculate all the possible MD5 checksums resulting from a one-bit
change to your file. If none of those match the original checksum,
you're safe.
Dave Sill
ma...@tanda.on.ca (Marc Thibault) writes:
> Dave Sill <d...@sws5.ctd.ornl.gov> writes:
>
> > A sends B the signed message M. Later, A fails to do X. B sues A,
> > producing M and its signature. A produces M', claiming it's the
> > message he sent B, and shows that it, too, matches the signature. B is
> > screwed.
>
> Nope. B has A's committment in message M.
But without A's signature, M is worthless. And the existence of M and
M', different messages with the same signature, completely invalidates
the signature.
> There is no reason
> for any court to believe that B could have forged it.
Sure there is. There's nothing preventing B from discovering M', and
anything A could do to discover it, B could also do.
> A's
> ability to produce other messages with the signature is
> irrelevant because only A can do it.
You keep asserting this, but I don't see the basis for it. What magic
does A have that B doesn't have?
William Unruh
In <Pine.ULT.3.93.960610124558.10501L-100000@xdm011> Jeffrey Goldberg <cc...@ecs.pc.Cranfield.ac.uk> writes:
>So, unless that technique and be extented to the real MD5 IV, then
>there are no consequences for MD5 or PGP.
There is no "real MD5 IV", they are all possible IVs. MD5 uses the IV
and 512 bits of text to produce an output. That output is the IV for the
next 512 bits of text. Ie, The IV for any round is just the output for the
previous round. Of course the system needs to be started up, but unless
the nessage is less than a few bytes long, that starting IV is not the
only IV.
--
Bill Unruh
un...@physics.ubc.ca
William Unruh
>Want to protect against possible one-bit changes and still use MD5?
>Just calculate all the possible MD5 checksums resulting from a one-bit
>change to your file. If none of those match the original checksum,
>you're safe.
Ah yes, and then also do the same for 2 3 and 4 bit changes. On the
other hand, just use what is now a much much much faster hash (Ie,
almo9st anything else is now faster). The advantage that MD5 had was
that it was fast. It was designed to be fast. SHA is about a factor of 2
slower, but if you have to go through 512 rounds of MD5 for each block
of text.....
Note that the worry is that MD5 seems to have far too many collisions
for one bit changes in the text for comfort. It is thus possible that
there are far more 2 bit changes and even more 3 bit, etc. IF true and
if they are easily found, MD5 is useless for collision resistance.
--
Bill Unruh
un...@physics.ubc.ca
Dave Sill
un...@physics.ubc.ca (William Unruh) writes:
> In <wx0spc3...@sws5.CTD.ORNL.Gov> Dave Sill <d...@sws5.ctd.ornl.gov> writes:
>
> >Want to protect against possible one-bit changes and still use MD5?
> >Just calculate all the possible MD5 checksums resulting from a one-bit
> >change to your file. If none of those match the original checksum,
> >you're safe.
>
> Ah yes, and then also do the same for 2 3 and 4 bit changes.
I thought the current technique for generating collisions was based on
one bit changes. If it is, there's no reason to assume that similar
multibit techniques will be developed.
> On the
> other hand, just use what is now a much much much faster hash (Ie,
> almo9st anything else is now faster). The advantage that MD5 had was
> that it was fast. It was designed to be fast. SHA is about a factor of 2
> slower, but if you have to go through 512 rounds of MD5 for each block
> of text.....
MD5 now has the further advantage of being widely distributed and
used. If there's a little more overhead for paranoids who don't trust
it any more, so what? At least the rest of can still use it quickly.
> Note that the worry is that MD5 seems to have far too many collisions
> for one bit changes in the text for comfort. It is thus possible that
> there are far more 2 bit changes and even more 3 bit, etc. IF true and
> if they are easily found, MD5 is useless for collision resistance.
Those are big IF's. I think people would do well to calm down a little
and wait until we understand the implications before we abandon
MD5. As far as I'm aware, nobody's produced two documents that yield
the same MD5 checksum yet.
Dave Sill
un...@physics.ubc.ca (William Unruh) writes:
> There is no "real MD5 IV", they are all possible IVs. MD5 uses the IV
> and 512 bits of text to produce an output. That output is the IV for the
> next 512 bits of text. Ie, The IV for any round is just the output for the
> previous round. Of course the system needs to be started up, but unless
> the nessage is less than a few bytes long, that starting IV is not the
> only IV.
Right, but when I hand someone a file to be MD5'd, I don't give them
an IV. Show me two files that differ in one bit with the same MD5
hash. Perhaps Dobberin has demonstrated the existence of weak IV's. So
what? Is that knowledge practically exploitable? How?
David Wagner
In article <4mgaPD...@tanda.on.ca>, Marc Thibault <ma...@tanda.on.ca> wrote:
> Undoubtedly there are encryption algorithms that would work
> badly this way. On the other hand, if we assume a strong
> algorithm like IDEA, Blowfish or multiple-DES run in one of
> the feedback modes, the end of the encrypted file is a
> function of every bit in the file.
False. In standard chaining modes (CBC,CFB) the last block of the
ciphertext depends only on the last and next-to-last blocks of the
plaintext.
Using the last block of the encryption of a message as a hash of
the message is not cryptographically secure by any stretch of the
imagination.
Marc Thibault
Dave Sill <d...@sws5.ctd.ornl.gov> writes:
> But without A's signature, M is worthless. And the existence of M and
> M', different messages with the same signature, completely invalidates
> the signature.
Aauughh! Put it in context. Think of paper. I have a document
with your signature in which you agree to pay me a million
dollars. You have a document with your signature in which you
wish me a happy birthday.
> Sure there is. There's nothing preventing B from discovering M', and
> anything A could do to discover it, B could also do.
Not even Dobbertin claims that this is possible. A doesn't
"discover" M'. The method Dobbertin developed requires that A
generate M and M' as a related pair. You start with a proposed
M, and a desired variation. Then you warm up a computer
generating the changes to both M and M' which will cause them to
have the same hash.
The existence of a collision is powerful evidence that both
messages were generated by A, on purpose.
Jeffrey Goldberg
-----BEGIN PGP SIGNED MESSAGE-----
[I have directed follow-ups to comp.text.tex]
On Mon, 10 Jun 1996, Marc Thibault wrote:
> [...] We will no doubt be watching carefully to see
> if it goes farther than that. A note I just got from Dobbertin
> suggests that it might. I won't know until I can get to a UNIX
> machine to decode the DVI file he sent me (why anybody would
> use a printer control code as an interchange format escapes me
> completely).
(1) DVI is not a printer control language. It was designed to be
platform and printer independent. It stands for DeVice Independent.
It is a page description language.
(2) Free translaters for DVI exist for many systems in addition to Unix.
Including DOS, OS/2, Amiga, VMS, Archimdes, TOPS-20, ...
These can be used to translate DVI to printer control languages
like PCL or PostScript. They do however require having the
appropriate fonts (the standard ones are free) as well.
If you wish you can send me a copy of the .dvi file and I will
sent you either PostScript or PCL.
PS: I have had my misunderstanding of the Dobbertin attack clarified,
and do see that this is a serious problem for MD5.
- -jeff
- --
Jeffrey Goldberg +44 (0)1234 750 111 x 2826
Cranfield Computer Centre FAX 751 814
J.Gol...@Cranfield.ac.uk http://WWW.Cranfield.ac.uk/public/cc/cc047/
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
Comment: Processed by mkpgp, a Pine/PGP interface.
iQCVAgUBMb05SRu6nIqxqP+5AQFwQgQAqpypWR9XOZggAxLC1iMslq3/eUIxtRRx
qvd/EJBf3n1som5c0NvYva2sRUbkDKSBn9U64D8GJfIxj3OOlVDgSavOW58C30TA
nB5plw80ENYX4JwbplJC1WvB5+PeJoU+jlPuRWlXx3V87/y3A0k4HmIEec6bokc9
EBIWGHMUXV4=
=nXax
-----END PGP SIGNATURE-----
Dave Sill
ma...@tanda.on.ca (Marc Thibault) writes:
> Dave Sill <d...@sws5.ctd.ornl.gov> writes:
>
> > But without A's signature, M is worthless. And the existence of M and
> > M', different messages with the same signature, completely invalidates
> > the signature.
>
> Aauughh! Put it in context. Think of paper. I have a document
> with your signature in which you agree to pay me a million
> dollars. You have a document with your signature in which you
> wish me a happy birthday.
Yeah, but the problem is the signatures are identical, too identical
for both to be authentic. And there's no way to tell which is the one
I signed and which is the perfect forgery.
> > Sure there is. There's nothing preventing B from discovering M', and
> > anything A could do to discover it, B could also do.
>
> Not even Dobbertin claims that this is possible.
I don't care what Dobbertin claims, it *is* possible. Whether or not
it is practical with widely-known methods is irrelevant. *IF* two
documents have the same MD5 hash, *THEN* there's no way to tell which
was originally signed.
The courts can't assume that Dobbertin's technique is the only way to
generate colisions.
> The existence of a collision is powerful evidence that both
> messages were generated by A, on purpose.
Circumstantial, at best. B could also have discovered another
technique for locating collisions, or he could have simply brute-force
checked various desired alternates and gotten *extremely* lucky.
William Unruh
>I don't care what Dobbertin claims, it *is* possible. Whether or not
>it is practical with widely-known methods is irrelevant. *IF* two
>documents have the same MD5 hash, *THEN* there's no way to tell which
>was originally signed.
Yes, but the question is whether you believe that is possible.
>The courts can't assume that Dobbertin's technique is the only way to
>generate colisions.
No but expert testimony can help them to decide that the probablility of
such a method existing and being used is too small to worry about. Of
course if two documents do turn up witht he same MD5 hash, the issue
becomes moot.
--
Bill Unruh
un...@physics.ubc.ca
Jerry Leichter
This entire line of argument reminds me of one of the standard examples
in the "theory of evidence". Consider the statement: No man is 50 feet
tall. You decide to test this, so you go around the world, measuring
the height of the men you meet. You find a 6 foot man - ah, a
confirming instance. A 6.5 foot man. Ah, another. Hundreds of men,
5 feet tall, 6 feet tall, even 7 feet tall. All confirming instances.
The statement is looking good. Then you meet a 49 foot tall man. It's
another confirming instance - but it seriously shakes your belief in the
truth of the statement!
The thing that has always bothered me about the design of MD5-like
hashing algorithms is how little theory there has been to justify them.
The arguments start off with, well, (a) every bit depends on every other
bit; (b) changing one input bit seems to change half the bits of the
output (partly proof, mainly experimental evidence); (c) the smallest
expression as a Boolean formula is very long (partly by construction);
(d) the dependency of each output bit on each input bit is very complex.
More recently, techniques adapted from differential cryptography point
in the direction of a proof that knowing *which* bits in the input were
changed doesn't let you compute which output bits will change.
These are a nice start, but they don't prove *anything* about the
properties that we really want out of a cryptographic hash function.
They simply show that MD5 (apparently) *doesn't* have some properties we
know such hash functions *must not* have.
Not only don't we have even the beginnings of a proof that MD5, or any
function like it, is cryptographically strong, as far as I know, we
don't even have a theory that would give us a hint as to how such a
proof would look.
Dobbertin's result, as described here, is like the 49-foot man. By
itself, it provides no attack. However, it apparently accomplishes
something that *ought not to be possible* for a true cryptographically
strong hash function.
The best theoretical work on security of cryptographic primitives uses
an approach that says the primitive is, in some appropriate sense,
indistinguishable (to an attacker with bounded resources) from a truely
random function. This is a very strong requirement, but it seems to be
the only one that really captures all attacks - not just the ones known
today. Dobbertin's result - again, as reported here - *almost* shows
how you could distinguish a box the computed MD5 of its input from a
random function of its input. That would make it unusable as a basis
for various provably-secure protocols and constructions (that show that
if you start with, say, a hash function indistinguishable from a random
function, then you can construct an efficient MAC that is provably
secure.)
Should you stop using MD5? No one can answer that for you. At the
moment, there is no practical attack. There is also no proof of
security - and the first chink in the armor has appeared. Is it
possible that MD5 will remain secure against all practical attacks for,
say, 50 years? Sure. Is it possible that someone will come up with an
algorithm tomorrow afternoon that produces collisions in 15 minutes on
any PC? Also, sure. What are the probabilities either way? ***No one
has the slightest idea!*** Has this fact changed since Dobbertin's work
was announced? No, not really. However, the prudent user will factor
the latest results into his estimates.
-- Jerry
Marc Thibault
Dave Sill <d...@sws5.ctd.ornl.gov> writes:
> Right, but when I hand someone a file to be MD5'd, I don't give them
> an IV. Show me two files that differ in one bit with the same MD5
> hash. Perhaps Dobberin has demonstrated the existence of weak IV's. So
> what? Is that knowledge practically exploitable? How?
What can be done with an IV can be done, with some extra
difficulty, by manipulating the text of the file. It's not
clear how much extra difficulty - Dobbertin is concerned that
it will be relatively easy. If he is right, it will be
possible for someone to create pairs of files with the same
MD5 hash.
Cheers,
Jerry Leichter
Marc Thibault wrote:
>
> Jerry Leichter <leic...@smarts.com> writes:
>
> > Should you stop using MD5? No one can answer that for you. At the
> > moment, there is no practical attack. There is also no proof of
> > security - and the first chink in the armor has appeared. Is it
>
You've quoted me out of context, but even so what you quote doesn't
match what you say! It is true that there is no proof of security for
any existing cryptographically secure hash functions. However, it is
*not* true that "chinks in the armor" have appeared for all such
functions. As far as the reports go, Dobbertin's attack is specific to
MD5, as his earlier attack was specific to MD4. MD5 is a modified
version of MD4 created in response to proposed attacks (though I think
the design pre-dated an actual demonstrated attack). SHA is also a
modification of MD4, along somewhat similar lines, but it's different
enough that, at last word, it still appears strong. Other hash
functions (e.g., HAVEL, RIPE-MD) also have not, at the moment, been
shown to have any problems.
> As I've already
> suggested, that way lies madness.
The madness is inherent in the paranoid demand of some users for
absolute security, forever, from everyone - for free. Not available,
sorry. Non-mad decisions - rational decisions - are always tradeoffs.
The more information you have, the better positioned you are to make
reasonable tradeoffs. Ignoring adverse information is hardly the way to
make good decisions.
-- Jerry
Marc Thibault
Dave Sill <d...@sws5.ctd.ornl.gov> writes:
> Yeah, but the problem is the signatures are identical, too identical
> for both to be authentic. And there's no way to tell which is the one
> I signed and which is the perfect forgery.
Yes there is. With the state of the art as it is, including
fantastic extensions on Dobbertin's method, they must both be
authentic and manipulated by you to have the same hash.
Neither is a forgery, and the one I have says you agree to pay
me a million dollars.
An essential feature of MD5 and all useful digests is that,
given file A, there is no way to create file B with the same
hash. Repeated assertions to the contrary haven't changed
that.
> ... at best. B could also have discovered another
> technique for locating collisions, or he could have simply brute-force
> checked various desired alternates and gotten *extremely* lucky.
He could also have been given the file by leprechauns.
If B discovers such a technique and uses it without disclosing
it, he will have perpetrated the perfect fraud and framed A.
No court would rule against him after hearing a parade of
experts explaining that there was no known or likely technique
to do this and that A must have generated both messages.
If B could do this, there is no doubt that the next week he
would invent the universal decoder, destroying electronic
security forever.
In the meantime, I'll use MD5.
Marc Thibault
Jerry Leichter <leic...@smarts.com> writes:
> Should you stop using MD5? No one can answer that for you. At the
> moment, there is no practical attack. There is also no proof of
> security - and the first chink in the armor has appeared. Is it
This applies equally to _all_ digests. As I've already
suggested, that way lies madness.
Cheers,
Marc Thibault
Jeffrey Goldberg <cc...@ecs.pc.Cranfield.ac.uk> writes:
> (1) DVI is not a printer control language. It was designed to be
> platform and printer independent. It stands for DeVice Independent.
> It is a page description language.
Document interchange formats don't need to have "device
independent" in their names. All "device independent" means is
that the target printer is a mythical device. It's still a
printer control language. "Page description language" is a
cute conceit.
As far as platform independence is concerned - it is easier
for me to crack and print an encrypted Word or Wordperfect
file than to simply view a DVI or PS file. In relative terms
that makes DVI and PS reasonably good encryption in a DOS or
Windows context. :)
Douglas R. Floyd
In article <wx0spc3...@sws5.CTD.ORNL.Gov>,
Dave Sill <d...@sws5.ctd.ornl.gov> wrote:
>
>Want to protect against possible one-bit changes and still use MD5?
>Just calculate all the possible MD5 checksums resulting from a one-bit
>change to your file. If none of those match the original checksum,
>you're safe.
Um... What about two bit changes then? This is an idea, but the problem
still remains.
--
Douglas R. Floyd <dfl...@io.com> Doug the Doomed
Disclaimer: I speak for myself, not for my employer(s).
Unsolicited, commercial "junk mail" will be read for a $500 fee.
NOTE: New PGP key, old ones were revoked... finger dfl...@io.com for them.
William Unruh
> An essential feature of MD5 and all useful digests is that,
> given file A, there is no way to create file B with the same
> hash. Repeated assertions to the contrary haven't changed
> that.
That this is an essential feature of a digest is clear. That this is a
feature of MD5 is no longer clear. No noone has shown that it is not.
However Dobbertin;s result casts some doubt on it.
> If B could do this, there is no doubt that the next week he
> would invent the universal decoder, destroying electronic
> security forever.
Huh? They have done it with MD4 and we still do not have a universal
decoder. What gives you such faith in MD5?
> In the meantime, I'll use MD5.
Fine.
--
Bill Unruh
un...@physics.ubc.ca
William Unruh
>Jerry Leichter <leic...@smarts.com> writes:
>> Should you stop using MD5? No one can answer that for you. At the
>> moment, there is no practical attack. There is also no proof of
>> security - and the first chink in the armor has appeared. Is it
> This applies equally to _all_ digests. As I've already
> suggested, that way lies madness.
No it does not apply equally to ALL digests. We know for example that
MD4 is definitely broken. No one has published any attack on SHA. On MD5
a "chink in the armour" has appeared. Whether it is broad eough for the
entry of a sword (or can be made such) is not clear at present. But MD5
is different from both MD4 and SHA.
Why are you so enamoured of MD5? Do you have stocks in some secret
company whose product is essentially based on MD5?
Your ccontention that all digests have collisions is obviously true. It
is even true for the elementary XOR digest. However there is a vast
difference between the security of XOR, MD4, MD4 or SHA. The difference
lies in the ease of finding that collision text. Recognising that
difference sounds sane to me. It is the denial of that difference that
sounds mad to me.
> Cheers,
> Marc
>---
> This is not a secure channel; Assume nothing.
> Marc Thibault Information Systems Architect
> http://www.synapse.net/~mthibault
> Key fingerprint = 76 21 A3 B2 41 77 BC E8 C9 1C 74 02 80 48 A0 1A
>
--
Bill Unruh
un...@physics.ubc.ca
William Unruh
> As far as platform independence is concerned - it is easier
> for me to crack and print an encrypted Word or Wordperfect
> file than to simply view a DVI or PS file. In relative terms
> that makes DVI and PS reasonably good encryption in a DOS or
> Windows context. :)
Since there are free programs for doing all of the above ( cracking Wor
or WordPerfect, or displaying DVI or postscript files) for PCs running
DOS or windows, your statement must be one regarding your personal
psychology rather than anything to do with the file types. It is also
true that all of the above are reasonably good encryption for anyone not
owning a computer at all, but the relevance of that (or your)
observation seems a little unclear to me.
--
Bill Unruh
un...@physics.ubc.ca
Andreas E. Bombe
-----BEGIN PGP SIGNED MESSAGE-----
p...@netcom.com (Paul Rubin) writes:
> Small differences (like single bits) are the most important
> differences. Here are two messages differing a single bit:
>
> MESSAGE 1:
> I will pay you $1,000,000 on June 30, 1996.
>
> MESSAGE 2:
> I will pay you $2,000,000 on June 30, 1996.
>
> Let's say you take out a bank loan and affix your digital
> signature to message 1 as a promise of repayment.
> You definitely don't want the same signature to show
> that you signed message 2 instead!
As with every transactions of big sums of money, you should write the
amount in words, too.
Now this message:
"I will pay you $1,000,000 (one million dollars) on June 30, 1996."
couldn't be hacked to other contents with still valid signature.
Numbers which are important should be wrote in words, too. You would
want to write the date in this example in words, just to be sure.
BTW, I tested changing only numbers in a signed file, PGP always
reported bad signature. (2->3 : only single bit change)
- --
Andreas E. Bombe | PGP Key Fingerprint: available on
andrea...@munich.netsurf.de | 13 6B BC 15 36 B8 B7 7A request and
| 20 05 58 E8 6F AA F8 ED on homepage
http://home.pages.de/~andreas.bombe/
Zahme Vögel singen von Freiheit... ...wilde Vögel fliegen
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
iQEVAwUBMb8qjO6K0Br2LVzBAQE2QQf/dWlxgjZClhmkRO+hCLK+yL+SbecoRLDR
loLS2H9cvidBqjvOtKUkbUJpS1YveJWgPnECLh3SbDNR//dttcuvsWhxkJru98vx
tSY+p33hvN8Fd9s4yuhngLiOxrAZewLI90SnhTrH5UdBYuv58TU7x/8y3t2togK4
lCHJRQez3VD4QafwolEMYt+WM4mtTYN/D8w3+lm49XqLRYgdCzQxGQhZ2xf6kwak
NRUb8bT68s/Y2f9TRGsutrBuzFqgGsW7XEmiLK8yp4+lUQWLX56rsUB44PXzb11f
OrIfKxGBAokgc8iuusf/DIz6qAUvrT1LmXjc6+xS0R11nBrBc4G7iw==
=2wj6
-----END PGP SIGNATURE-----
Hallam-Baker
Dave Sill wrote:
> MD5 now has the further advantage of being widely distributed and
> used. If there's a little more overhead for paranoids who don't trust
> it any more, so what? At least the rest of can still use it quickly.
Nonsense, MD5 was introduced only a few years ago after MD4 was found to
be weak. Code for SHA is readily avaliable. It is likely that the
initial expansion function in SHA will make it resistant to the class of
attacks attempted.
A one bit attack is the most serious possible. It means that changes
such as $1000 --> $9000 are possible. Multiple bit transformations can
be performed by making multiple single bit transformations.
The question is whether the attack has one or two independent variables.
If the attack is merely finding pairs which compress to the same value
the problem is notless than if a collision can be found for an arbitary
hash. I don't believe that this is the case however, I believe that both
parameters must be varied to make the break...
In other words the break is discovering input paterns which are
particuarly vulnerable to an attack rather than a more general attack.
Phill
Marc Thibault
You haven't been paying attention. Dobbertin has himself
posted a message on sci.crypt making it clear that both
files have to be manipulated and that nothing he has done
casts any such doubt.
> decoder. What gives you such faith in MD5?
I was being sarcastic. I'll try to be less subtle next
time.
Marc Thibault
un...@physics.ubc.ca (William Unruh) writes:
> > This applies equally to _all_ digests. As I've already
> > suggested, that way lies madness.
>
> No it does not apply equally to ALL digests. We know for example that
I should have been more specific. I was responding to "there
is no proof of security". My mistake. I generally assume
minimal intelligence of people who can string words into
meaningful sentences. These things happen when I forget not
everyone makes the same assumption about me.
> Why are you so enamoured of MD5? Do you have stocks in some secret
I know that if I generate an MD5 hash or use PGP, just about
anybody on just about any machine can deal with it. I'm not
looking forward to the chaos of a dozen or so competing
algorithms if we panic and drop MD5 prematurely.
Right now we have a small nick - not in the armor but in the
chain mail under the armor. It has no practical use and
presents no risk. It is, on the other hand, an itch that a lot
of cryptologists will want to scratch, so we should know
relatively soon whether to worry or not. I suggest we wait.
At the very least, we should wait for Dobbertin's next paper.
In the meantime, quoting Dobbertin:
"If someone writes a message and nobody else has any influence
on its contents, then the signed message cannot be manipulated
afterwards. Thus in this situation, which certainly covers the
major part of all practical applications, there is no risk (at
least according to our knowledge today)."
Stefan Lucks
On Wed, 12 Jun 1996, Jerry Leichter wrote:
A quote from Dobbertin's paper on breaking MD4:
"We anticipate that, in addition to the already known two-round attacks
[...], the compress function of RIPE-MD is also not collision free."
> [ ... ] As far as the reports go, Dobbertin's attack is specific to
> MD5, as his earlier attack was specific to MD4. MD5 is a modified
> version of MD4 created in response to proposed attacks (though I think
> the design pre-dated an actual demonstrated attack). SHA is also a
> modification of MD4, along somewhat similar lines, but it's different
> enough that, at last word, it still appears strong. Other hash
> functions (e.g., HAVEL, RIPE-MD) also have not, at the moment, been
^^^^^^^
> shown to have any problems.
Stefan Lucks Inst. f. NAM, Lotzestrasse 16-18, 37083 Goettingen, Germany
e-mail: lu...@math.uni-goettingen.de
home: http://www.num.math.uni-goettingen.de/lucks/
----- Wer einem Computer Unsinn erzaehlt, muss immer damit rechnen. -----
Ulrich Kuehn
> I don't care what Dobbertin claims, it *is* possible. Whether or not
> it is practical with widely-known methods is irrelevant. *IF* two
> documents have the same MD5 hash, *THEN* there's no way to tell which
> was originally signed.
>
In my opinion, that is not the point. Of course it is possible for ANY
hash function to produce collisions. That is a simple argument that
the output of the function is fixed in size, while the input is not,
so there must be different inputs being hashed to the same output.
But the big questions are: can anyone produce a document with a given
hash value? Can anyone generate two documents with the same hash value?
Regards,
Ulrich
--
--
+---------------+----------------------------+--------------------------+
| Ulrich Kuehn | Internet: | Two wrongs do not make a |
| Dipl.-Math. | ku...@math.uni-muenster.de | right but three lefts do |
+---------------+----------------------------+--------------------------+
Lutz Kotoll
Hi,
Marc Thibault (ma...@tanda.on.ca) wrote:
> Document interchange formats don't need to have "device
> independent" in their names. All "device independent" means is
> that the target printer is a mythical device. It's still a
> printer control language. "Page description language" is a
> cute conceit.
why do you want to call it 'printer control language'?
dvi is designed to get displayed on any media you like -- including screen
(and even converting it to ascii ;-)
it describes coordinates on a virtual page -- ergo it is a 'page description
language'!
\bye{Lutz}
There is ONE reason to use Windows95 -- it has multitasking:
you can boot the system and crash it simultaneously!
Jolt-X
William Unruh (un...@physics.ubc.ca) wrote:
: troublesome. You are cetainly right that there is nothing to show that
: the breaking discovered would change just that right single bit to cause
: the trouble. However the demonstration in court that a single bit could
: have been changed could cast sufficient doubt on the contract to have it
: annulled. This possibility would make those kinds of contract not very
: useful. Remember the burden of proof on a new technology is much higher
: than on an old technology, even if the old one has obvious problems.
Either for the good or bad, it should be shown what the =REAL= IV
produces. I'm sure the judge (with enough explation) would understand who
to pick. This means that both A and B need to check the MD5 of their
contract on a machine they know is secure.
--
Jolt-X -- God of All Who Follow | ... Torklamuffin ... Sarkalar ... Bushin ...
mail:jo...@west.net | finger for my public key | theNSAiswatching
http://www.west.net/~joltx | <reserved>
Fingerprint: D7086E47E6494E40 D67B03B5C2D1EC82 :tnirpregniF
Hal
ma...@tanda.on.ca (Marc Thibault) writes:
> At the very least, we should wait for Dobbertin's next paper.
> In the meantime, quoting Dobbertin:
> "If someone writes a message and nobody else has any influence
> on its contents, then the signed message cannot be manipulated
> afterwards. Thus in this situation, which certainly covers the
> major part of all practical applications, there is no risk (at
> least according to our knowledge today)."
While the first part is true, it misses the point of how signatures are
used. A signature is not designed to provide assurance to the signer; he
already knows what he wrote. Rather, it should provide assurance to the
person he gives the signature to! That is what signatures are for. And
that is exactly the circumstance where Dobbertin's attack, if extended to
be as powerful as his attack on MD4, would strike at the heart of the use
of digital signatures based on MD5. A signature which can't be trusted
is not of much use.
The other issue is that there are circumstances where we sign things
written by others, such as contracts. So if there is a dispute between
two parties where two versions of a contract end up with the same
hash (and hence both parties' signatures apply to both versions of the
contract), there is no way for an arbitrator to know which one created
the collision. Each party may accuse the other of being the one who set
the final form of the contract, and hence of being the one who kludged it
into colliding form. So simple assertions that it is always the person
who signed the document who was responsible for any collisions are not
necessarily true.
Hal Finney
Jeffrey Goldberg
-----BEGIN PGP SIGNED MESSAGE-----
On 16 Jun 1996, Hal wrote:
> ma...@tanda.on.ca (Marc Thibault) writes:
>
> > "If someone writes a message and nobody else has any influence
> > on its contents, then the signed message cannot be manipulated
> > afterwards. Thus in this situation, which certainly covers the
> > major part of all practical applications, there is no risk (at
> > least according to our knowledge today)."
>
> While the first part is true, it misses the point of how signatures are
> used.
I agree.
Imagine a scheme (I have an essay on it that is nearly ready
for internet "publishing") where a mailhub logs not only the dates,
sizes, recipients etc of messages that it handles, but also an MD5 summary
of them.
One purpose would be so that someone could later prove that they
actually sent a message (timestamping isn't always enough) with
the postmasters help for looking at logs.
Suppose that Bob says that he recieved an offensive message from Alice.
Alice says that she sent an inoffensive one. Each produce a copy of
a message, one offensive one inoffensive. A summary in the mailhub
log might help determine who is lying.
Although there are many ways why such a scheme might not work, it
would certainly be bad if Alice could produce two distinct messages
with the same summary. If we ignore the specific problems of
this scheme, we can still see it as an example of where author generated
collisions could be a bad thing.
- -j
- --
Jeffrey Goldberg +44 (0)1234 750 111 x 2826
Cranfield Computer Centre FAX 751 814
J.Gol...@Cranfield.ac.uk http://WWW.Cranfield.ac.uk/public/cc/cc047/
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
Comment: Processed by mkpgp, a Pine/PGP interface.
iQCVAgUBMcZ1XBu6nIqxqP+5AQHaawQAtKY20JQNaulJwgTF9Cm14JyilWEli4ns
NhUmM/5KiWebMdwnAN6R4dZAYAbFWecb0/qjlZE+Ew7sAQP7/xpjU98yKrLAI8CM
8zyBbE2lm2qF4KdAQaGGWBtHCUXxZCf41/EC/pqIbU2CdH/Z9xncKAEAzrAoBpym
/MGsAieO7cQ=
=seFd
-----END PGP SIGNATURE-----
Marc Thibault
Jeffrey Goldberg <cc...@ecs.pc.Cranfield.ac.uk> writes:
> Although there are many ways why such a scheme might not work, it
> would certainly be bad if Alice could produce two distinct messages
> with the same summary. If we ignore the specific problems of
Why? Based on the available and predictable art, she would have
to have generated them both herself.
Pay attention.
Cheers,
Marc
Nothing is provable
Marc Thibault
eac...@spectre.mitre.org (Robert I. Eachus) writes:
> During WWII, Enigma machines were widely distributed and used. On
>SNIP
> Using a cipher system beyond its effective lifetime is a good way
> to guarantee insecurity. It is time to bury MD5.
a) MD5 isn't a cipher system.
b) The weakness in Enigma was that the British had broken it and
were willing to sacrifice lives to keep the news of that from the
Germans. A nation at war needs to take special precautions. No one
proposes using MD5 to protect lives.
c) The attack on MD5 is happening in the open. The only thing we
know now is that there may be an exploitable weakness in it. On
the other hand, there may not be. In either case, the use of MD5
for normal signatures is unaffected. Only in the special case of
"I sign your file" is there a remote possibility of a problem.
Notaries beware!
d) Until significant effort has been put into similar attacks on
other digests we have no idea whether there is any value in
switching away from MD5.
Cheers,
Marc
Nothing is provable - Knowledge comes from disproof
schl...@bbs.cruzio.com
In article <74eXPD...@tanda.on.ca>, ma...@tanda.on.ca (Marc Thibault) writes:
>
> b) The weakness in Enigma was that the British had broken it and
> were willing to sacrifice lives to keep the news of that from the
> Germans. A nation at war needs to take special precautions. No one
> proposes using MD5 to protect lives.
>
> c) The attack on MD5 is happening in the open.
So we hope. The progress of secret attacks is unknown.
> The only thing we
> know now is that there may be an exploitable weakness in it. On
> the other hand, there may not be. In either case, the use of MD5
> for normal signatures is unaffected. Only in the special case of
> "I sign your file" is there a remote possibility of a problem.
> Notaries beware!
Yeah, that's all WE know. But what do others know? Now and in
the future?
> Nothing is provable - Knowledge comes from disproof
Based on your signature, I guess convincing you of anything is
a waste of time.
Roger
Marc Thibault
schl...@bbs.cruzio.com writes:
>
> Based on your signature, I guess convincing you of anything is
> a waste of time.
My signature is an alternate statement of the scientific principle.
Convincing me of something is in no way a waste of time, though
you might waste your time trying. I am particularly resistant to
things that live under beds and go bump in the night. Try to keep
it in mind that "The X-Files" is fiction.
The "what do others know that they don't tell" rhubarb applies to
everything discussed in sci.crypt. You can jump at every rustle in
the bush or just get on with the job.
Cheers,
Marc
Nothing is provable - Knowledge comes from disproof
schl...@bbs.cruzio.com
> schl...@bbs.cruzio.com writes:
> >
> > Based on your signature, I guess convincing you of anything is
> > a waste of time.
>
> My signature is an alternate statement of the scientific principle.
Not even close. Proof is as common as disproof.
> The "what do others know that they don't tell" rhubarb applies to
> everything discussed in sci.crypt. You can jump at every rustle in
> the bush or just get on with the job.
Many here are rightfully concerned with crypto attacks based on
the knowledge of others. This includes currently unpublished
knowledge, and knowledge obtained in the future.
If this disturbs you for some reason, stay off of sci.crypt.