MD4 collision reproduced
I have reproduced both MD4 collisions from the recent paper. The example given had endian problems similar to those noted by Eric Rescorla for the sorta-MD5 collision. Also similar to Eric's results, the hash value (while a collision) does not match what the authors give in the paper. Example one: $ od -tx1 file1.bin 000 83 9c 7a 4d 7a 92 cb 56 78 a5 d5 b9 ee a5 a7 57 020 3c 8a 74 de b3 66 c3 dc 20 a0 83 b6 9f 5d 2a 3b 040 b3 71 9d c6 98 91 e9 f9 5e 80 9f d7 e8 b2 3b a6 060 31 8e dd 45 e5 1f e3 97 08 bf 94 27 e9 c3 e8 b9 100 $ od -tx1 file2.bin 000 83 9c 7a 4d 7a 92 cb d6 78 a5 d5 29 ee a5 a7 57 020 3c 8a 74 de b3 66 c3 dc 20 a0 83 b6 9f 5d 2a 3b 040 b3 71 9d c6 98 91 e9 f9 5e 80 9f d7 e8 b2 3b a6 060 31 8e dc 45 e5 1f e3 97 08 bf 94 27 e9 c3 e8 b9 100 $ cmp file1.bin file2.bin file1.bin file2.bin differ: char 8, line 1 $ openssl md4 file1.bin file2.bin MD4(file1.bin)= 4d7e6a1defa93d2dde05b45d864c429b MD4(file2.bin)= 4d7e6a1defa93d2dde05b45d864c429b Example two: $ od -tx1 file1.bin 000 83 9c 7a 4d 7a 92 cb 56 78 a5 d5 b9 ee a5 a7 57 020 3c 8a 74 de b3 66 c3 dc 20 a0 83 b6 9f 5d 2a 3b 040 b3 71 9d c6 98 91 e9 f9 5e 80 9f d7 e8 b2 3b a6 060 31 8e dd 45 e5 1f e3 97 40 c2 13 f7 69 cf b8 a7 100 $ od -tx1 file2.bin 000 83 9c 7a 4d 7a 92 cb d6 78 a5 d5 29 ee a5 a7 57 020 3c 8a 74 de b3 66 c3 dc 20 a0 83 b6 9f 5d 2a 3b 040 b3 71 9d c6 98 91 e9 f9 5e 80 9f d7 e8 b2 3b a6 060 31 8e dc 45 e5 1f e3 97 40 c2 13 f7 69 cf b8 a7 100 $ cmp file1.bin file2.bin file1.bin file2.bin differ: char 8, line 1 $ openssl md4 file1.bin file2.bin MD4(file1.bin)= c6f3b3fe1f4833e0697340fb214fb9ea MD4(file2.bin)= c6f3b3fe1f4833e0697340fb214fb9ea David - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cryptome on ABC Evening News?
At 03:32 PM 8/12/2004, R. A. Hettinga wrote: There's a teaser for tonight's 6:30 news about a website that publishes pipeline maps and the names and addresses of government employees. The horror. Speaking unofficially for the telecom industry, we're really happy to have the site there showing pictures of cable landings, antennas, etc. I've seen them used in internal training about submarine cables and I think we've probably used them in talks to customers as well. Separately, of course, we have bureaucrats who don't want to publish the addresses of telecom POPs, ignoring the fact that you can't buy physically diverse access to a location if you don't know where it is, and also ignoring the fact that 90% of a certain large 3-1/2-letter-acronym long distance carrier's POPs are in the same buildings as the local telcos so everybody knows where they are anyway, even though everybody's forgotten the derivation of VH coordinates... Bill Stewart [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 rumors
No, it was on the compression function, but not in any sense reduced. But you had to start with particular values of the chaining variables, and in practice no-one knows how to do that, so MD5 (as a whole) isn't broken by this, at least until tomorrow evening. The rumour here is that MD5, HAVAL, and RIPE-MD are all goners. We know SHA-0 is toast too. There might also be results against SHA-1. Hash functions are hard. What I've heard (also at CRYPTO right now like Greg) is that the four Chinese researchers (Wang, Fang, Lai, Yu) have found collisions in MD4, MD5, HAVAL, and RIPEMD. They state that SHA-0 collisions can be found as well. However, the collision they list for MD5 doesn't produce work because the Chinese translation of [MOV] had an error which caused an endianness problem. So they have a collision for a PARTICULAR IV. One of the four researchers is back in China, so they are on the phone trying to fix the problem for the announcment tomorrow evening. However, they have announced nothing regarding SHA-1 or any of the larger-output SHA versions like SHA-256, etc. We haven't seen their methods yet, but one has to believe that their methods are fairly general given the range of hash functions they've attacked. This would SEEM to put the SHA family into jeopardy as well, but we should know more tomorrow evening. John Black [MOV] Menezes, van Oorschot, Vanstone; Handbook of Applied Cryptography, CRC Press. _ FREE pop-up blocking with the new MSN Toolbar get it now! http://toolbar.msn.click-url.com/go/onm00200415ave/direct/01/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
CRYPTO2004 Rump Session Presentations, was Re: A collision in MD5'
Hello: This is Jim Hughes, General Chair of CRYPTO2002. There are three significant Rump session papers on hash collisions that will be presented, including an update on this one (and about 40 other short papers on other aspects of cryptography). As the session firms up, more information it will be posted at http://www.iacr.org/conferences/crypto2004/rump.html Barring technical or other difficulties, if you want to hear this from the horses mouth, the CRYPTO2004 Rump Session will be webcast at 7pm pacific Tuesday Aug 17 for as long as it takes. You may join us virtually using the following links (depending on the readers). Internet Explorer http://128.111.55.99/crypto.htm Microsoft media server mms://128.111.55.99/crypt The players (for MS and Mac) are available from http://www.microsoft.com/windows/windowsmedia/players.aspx I assume MS clients will be able to cope. I know that my MacOSX machine with Windows Media Player can use the mms: link. I welcome feedback from anyone using other readers on other platforms like Linux. The server is currently up and running and is broadcasting a dark, empty, and silent hall. This should be more interesting after sunup Tuesday Santa Barbara time. You may expect sound near to the start time. This is our the conferences first webcast, and I hope that it works for you. If there are problems, I will apologize in advance. Thanks jim On Aug 16, 2004, at 9:02 PM, Eric Rescorla wrote: I've now successfully reproduced the MD5 collision result. Basically there are some endianness problems. The first problem is the input vectors. They're given as hex words, but MD5 is defined in terms of bitstrings. Because MD5 is little-endian, you need to reverse the written byte order to generate the input data. A related problem is that some of the words are given as only 7 hex digits. Assuming that they have a leading zero fixes that problem. Unfortunately, this still doesn't give you the right hash value. The second problem, which was found by Steve Burnett from Voltage Security, is that they authors aren't really computing MD5. The algorithm is initialized with a certain internal state, called an Initialization Vector (IV). This vector is given in the MD5 RFC as: word A: 01 23 45 67 word B: 89 ab cd ef word C: fe dc ba 98 word D: 76 54 32 10 but this is little-endian format. So, the actual initialization values should be 0x67452301, etc... The authors use the values directly, so they use: 0x01234567, etc... Obviously, this gives you the wrong hash value. If you use these wrong IVs, you get a collision... though strangely with a different hash value than the authors provide. Steve and I have independently gotten the same result, though of course we could have made mistakes... So, this looks like it isn't actually a collision in MD5, but rather in some other algorithm, MD5'. However, there's nothing special about the MD5 IV, so I'd be surprised if the result couldn't be extended to real MD5. -Ekr - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RPOW - Reusable Proofs of Work
A couple of quick responses to the questions on RPOW, as I am at Crypto this week. Taral asked about the attestation. It is based on a root key published in Appendix C of IBM's IBM 4758 PCI Cryptographic Coprocessor Custom Software Interface Reference, available from http://www.ibm.com/security/cryptocards/html/library.shtml. It is also published on IBM's web page at http://www.ibm.com/security/cryptocards/html/faqcopvalidity.shtml This tells you that the attestation refers to a valid IBM 4758. Further, the attestation contains within it both a hash of the RPOW program, and a set of keys generated by that program. Using the methods described on the rpow.net web site, it is possible to take the RPOW source code and generate a hash which matches that reported in the attestation. This tells you that you have access to the actual source code running on the RPOW server. By studying the source you can confirm that the program never exposes its private keys or allows them to leave the board. This tells you that if you send a message encrypted to the RPOW communications key and get a meaningful response (messages are protected with HMAC), you are talking to the program described in the attestation. Lynn Wheeler mentions the IBM 4758 break by Mike Bond and Richard Clayton described at http://www.cl.cam.ac.uk/~rnc1/descrack/. This was not actually a break of the 4758 but an exploit of a cryptographic weakness in the application running on the board, which was IBM's CCA support software. RPOW does not use CCA and is not vulnerable to that attack, and IBM has since fixed the CCA. Of course it is possible that RPOW may have vulnerabilities and errors of its own, being my own work and far from perfect. I welcome review and comment on the RPOW source code which is open source and available from rpow.net. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: MD5 collisions?
Eric Rescorla wrote: Check out this ePrint paper, which claims to have collisions in MD5, MD4, HAVAL, and full RIPEMD. http://eprint.iacr.org/2004/199.pdf The authors claim that the MD5 attack took an hour for the first collision and 15 seconds to 5 minutes for subsequent attacks with the same first 512 bits. So what's the status?, the MD5 collisions has been confirmed by Eric Rescorla (taken the type into consideration), the MD4 by David Shaw, what about Haval and RipeMD?. I did a test on the RipeMD results and couldn't get the results written. Anybody else having the same problems? Any news on Antoine Joux and his attack on SHA-0? how did he create the collision previously announced on sci.crypt? Regards, Mads Rasmussen Open Communications Security - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Data watchdog slams ID card plans
http://www.theregister.co.uk/2004/08/16/id_card_surveillance_fears/print.html The Register Biting the hand that feeds IT The Register » Internet and Law » Digital Rights/Digital Wrongs » Original URL: http://www.theregister.co.uk/2004/08/16/id_card_surveillance_fears/ Data watchdog slams ID card plans By John Leyden (john.leyden at theregister.co.uk) Published Monday 16th August 2004 14:05 GMT Britain is at risk sleepwalking into a surveillance society because of David Blunkett's identity card scheme and other UK government plans, according to the UK's Information Commissioner. Richard Thomas also cited plans for a population register by the Office for National Statistics and a database on children, in warning of a slide towards a Big Brother-style system of ubiquitous surveillance in the UK. Thomas predicted Britain risks moving towards an East German Stasi-style snooping culture if current plans are followed through. Thomas's comments came in an interview (http://www.timesonline.co.uk/article/0,,2-1218615_2,00.html) with The Times published today. He said: My anxiety is that we don't sleepwalk into a surveillance society where much more information is collected about people, accessible to far more people shared across many more boundaries than British society would feel comfortable with. The Information Commissioner is not opposed to ID cards on principle. But he is concerned about what he sees as the Home Office's failure to clearly define a purpose for ID cards, the amount of information that would be held on any card and who might be able to access this information. Clamping down on benefit fraud, control illegal immigration and preventing terrorism have been cited as the main reason why Britain needs ID cards by the Home Office at one time or another. The government proposed ID card scheme will involve the establishment of a national register of citizens' personal details, widely accessible to government departments. This approach gives the UK's Information watchdog the fear. In response to the Home Office's consultation on identity cards, Thomas concludes whilst I am not fundamentally opposed to the introduction of ID cards I do have significant concerns about the current proposals. The privacy implications of an extensive national identity register are, in many ways, of far greater concern for individuals. This aspect needs more of a public debate. -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire' - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: CRYPTO2004 Rump Session Presentations, was Re: A collision in MD5'
I have 2 items of note for this list. 1. The web site is updated with program and the times. http://www.iacr.org/conferences/crypto2004/rump.html 2. I was typing fast, and mistyped my title. I am General Chair this year, not 2002 as was stated. Enjoy. On Aug 17, 2004, at 1:39 PM, james hughes wrote: Yes, my mistake. the link has an 'o' at the end. mms://128.111.55.99/crypto - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
crypto '04 rump webcast
I've been watching the webcast. The team that did the md4/md5/haval-128/ripemd attacks just presented, and although it was interesting it included precious few details of the attack beyond the fact that it was a twist on differential cryptanalysis. Is there any more information available at this point from anyone? Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: MD5 collisions?
At 14:12 2004-08-17 -0300, Mads Rasmussen wrote: Eric Rescorla wrote: Check out this ePrint paper, which claims to have collisions in MD5, MD4, HAVAL, and full RIPEMD. http://eprint.iacr.org/2004/199.pdf The authors claim that the MD5 attack took an hour for the first collision and 15 seconds to 5 minutes for subsequent attacks with the same first 512 bits. So what's the status?, the MD5 collisions has been confirmed by Eric Rescorla (taken the type into consideration), the MD4 by David Shaw, what about Haval and RipeMD?. I did a test on the RipeMD results and couldn't get the results written. Anybody else having the same problems? Any news on Antoine Joux and his attack on SHA-0? how did he create the collision previously announced on sci.crypt? Eli Biham -- has collisions on 34 (out of 80) rounds of SHA-1, but can extend that to probably 46. Still nowhere near a break. Antoine Joux -- his team announced the collision on SHA-0 earlier this week. There is concentration on the so-called IF function in the first 20 rounds... f(a,b,c) = (a b) ^ (~a c). That is, the bits of a choose whether to pass the bits from b, or c, to the result. The technique (and Eli's) depends on getting a near collision in the first block hashed, then using more near collisions to move the different bits around, finally using another near collision to converge after the fourth block hashed. This took 20 days on 160 Itanium processors. It was about 2^50 hash evaluations. Xiaoyun Wang was almost unintelligible. But the attack works with any initial values, which means that they can take any prefix, and produce collisions between two different suffixes. The can produce the first collision for a given initial value in less than an hour, and then can crank them out at about one every 5 minutes. It seems to be a straightforward differential cryptanalysis attack, so one wonders why no-one else came up with it. The attack on Haval takes about 64 tries. On MD4, about 4 tries. RIPE-MD, about 2 hours (but can improve it). SHA-0 about 2^40 (1000 times better than Joux). Xuejia Lai clarified that the paper on E-print has been updated with correct initial values. They were initially byte-reversed, which they blamed on Bruce Schneier. Greg. Regards, Mads Rasmussen Open Communications Security - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111/232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]