- cypherpunks-legacy - lists.cpunks.org

Hole in MD5
by Mike Ingle 17 Dec '03

17 Dec '03

Recently there was a message here about MD5 having a hole in it. Maybe this is what the person was talking about... >From msuinfo!uwm.edu!cs.utexas.edu!uunet!ddsw1!chinet!schneier Tue Mar 23 10:36:50 1993 Newsgroups: sci.crypt Path: msuinfo!uwm.edu!cs.utexas.edu!uunet!ddsw1!chinet!schneier From: schneier(a)chinet.chi.il.us (Bruce Schneier) Subject: Successful Cryptanalysis of MD5 Message-ID: <C42Gr3.M3w(a)chinet.chi.il.us> Organization: Chinet - Public Access UNIX Date: Thu, 18 Mar 1993 04:06:39 GMT Lines: 25 This is from Bart Preneel's Ph.D. thesis, "Analysis and Design of Cryptographic Hash Functions," Jan 1993, p. 191. It is about the cryptanalysis of MD5: B. den Boer noted that an approximate relation exists between any four consecutive additive constants. Moreover, together with A. Bosselaers he developed an attack that produces pseudo-collisions, more specifically they can construct two chaining variables (that only differ in the most significant bit of every word) and a single message block that yield the same hashcode. The attack takes a few minutes on a PC. This means that one of the design principles behind MD4 (and MD5), namely to design a collision resistant function is not satisfied. I have not seen the actual paper yet, which will be presented at Eurocrypt. Both PEM and PGP rely on MD5 for a secure one-way hash function. This is troublesome, to say the least. Bruce ************************************************************************** * Bruce Schneier * Counterpane Systems For a good prime, call 391581 * 2^216193 - 1 * schneier(a)chinet.chi.il.us ************************************************************************** From: burt(a)chirality.rsa.com (Burt Kaliski) Newsgroups: sci.crypt Subject: Pseudocollisions in MD5 Message-ID: <BURT.93Apr23171338(a)chirality.rsa.com> Date: 23 Apr 93 21:13:38 GMT Distribution: sci Organization: RSA Data Security, Inc. Lines: 89 NNTP-Posting-Host: chirality.rsa.com Following is a short note commenting on den Boer and Bosselaers' recent work on the MD5 message-digest algorithm. Feel free to email questions or further comments. -- Burt Kaliski RSA Laboratories ---------------------------------------------------------------------- \documentstyle[12pt]{article} \begin{document} \title{On ``Pseudocollisions'' in the MD5 Message-Digest Algorithm} \author{Burton S. Kaliski Jr. \\ {\tt burt(a)rsa.com} \and Matthew J.B. Robshaw \\ {\tt matt(a)rsa.com} \and RSA Laboratories \\ 100 Marine Parkway \\ Redwood City, CA 94065} \date{April 23, 1993} \maketitle A message-digest algorithm maps a message of arbitrary length to a ``digest'' of fixed length, and has three properties: Computing the digest is easy, finding a message with a given digest---``inversion''---is hard, and finding two messages with the same digest---``collision''---is also hard. Message-digest algorithms have many applications, including digital signatures and message authentication. RSA Data Security's MD5 message-digest algorithm, developed by Ron Rivest \cite{rfc-md5}, maps a message to a 128-bit message digest. Computing the digest of a one-megabyte message takes as little as a second. While no message-digest algorithm can yet be {\em proved} secure, MD5 is believed to be at least as good as any other that maps to a 128-bit digest. Inversion should take about $2^{128}$ operations, and collision should take about $2^{64}$ operations. No one has found a faster approach to inversion or collision. Recent work by den Boer and Bosselaers \cite{den-boer-md5} presents a special kind of ``pseudocollision'' in MD5's internal compression function, which maps a 512-bit message block $x$ and a 128-bit input state $s$ to a 128-bit output state. They show how to find a message block $x$ and two related input states $s_1$ and $s_2$ that yield the same output state: $f(x,s_1)$ = $f(x,s_2)$. Their well-thought approach exploits structural properties of the collision function to find a pseudocollision in about $2^{16}$ operations, much less than one would expect. Practical implications of this pseudocollision work to the security of MD5 are not evident. While a real collision in MD5 implies a pseudocollision (or a ``pseudo-inversion''), a pseudocollision need not imply a real collision. Indeed, a real collision, since it involves two different messages, would almost always involve {\em different} message blocks $x_1$ and $x_2$ such that $f(x_1,s_1) = f(x_2,s_2)$, but the pseudocollisions have the same message blocks. Moreover, the input states $s_1$ and $s_2$ would generally be unrelated, but the pseudocollisions' input states are the same except for four bits. There does not seem to be any way to extend den Boer and Bosselaers' approach to anything beyond the special pseudocollisions, a limitation they readily admit. It is reasonable, therefore, to believe that MD5 remains secure. While den Boer and Bosselaers have found interesting structural properties in MD5, the properties seem only to lead to special pseudocollisions and not anything approaching real collisions. Further research, of course, will give a better understanding of the strengths of MD5 and other message-digest algorithms, with the eventual hope that such algorithms can, in some sense, be proved secure. \bibliographystyle{plain} \begin{thebibliography}{1} \bibitem{den-boer-md5} Bert den~Boer and Antoon Bosselaers. \newblock Collisions for the compression function of {MD5}. \newblock In {\it Advances in Cryptology --- Eurocrypt '93}, 1993. \newblock Preprint. \bibitem{rfc-md5} R.L. Rivest. \newblock {\it {RFC} 1321: The {MD5 Message-Digest Algorithm}}. \newblock Internet Activities Board, April 1992. \end{thebibliography} \end{document}

1 0

on the road...
by George A. Gleason 17 Dec '03

17 Dec '03

...and in Berkeley the PD has a little trailer they set up all by itself, which has a radar system in it and a display in large red numerals. There is a place to hang some large printed numbers representing the speed limit. There is a large sign on the back which says, "Speed limit (printed numbers); your speed: (red display numbers), drive safely!" No tickets dispensed, but pretty effective at getting people to slow down.

1 0

Re: Anonymous vs false IDs
by dmandl＠lehman.com 17 Dec '03

17 Dec '03

> From: kovar(a)nda.com (David Kovar) > > There is a lot of effort being put into creating tools to mask identities. > I'm curious why people don't go a different route - creating a false > electronic identity? If you have control over your own system, it is easy > enough to create an account. Lacking that, there are a lot of companies > out there offering low cost accounts on Unix systems with full Internet > access. Why not get an account in a different name rather than using > anonymous remailers? If you use five different identities, why waste your money paying for five accounts, especially if some of them are used only infrequently? Why have a full UNIX account (like my account on PANIX, say) for an identity that won't need to do anything but send out a couple of email messages now and then? What if you create and kill off personas relatively frequently? Having everything centralized seems like the most logical way to go--don't forget, separate accounts would mean setting up separate .profile files, copying code from one place to another all the time, keeping duplicate copies of things, etc., etc. The exception would be when you have identities or "lives" that are truly separate, with little overlap, but even then I'd prefer having full access to all my files and robots in one place all the time. If I had an Internet connection on my own box at home, sure, it might be more convenient to segregate things in separate accounts, but most people don't have that luxury yet. --Dave.

6 5

Re: 700 Club Report on the Clipper Chip on Wednesday, October 20, 1993
by mlshew＠netcom.com 17 Dec '03

17 Dec '03

I have an error in my spelling. I spelled Jerry Berman's name wrongly as Jerry Berrman. Major apologies. And after mentioning him as just 'an eff guy' in the first message. <sigh> I'm sorry to have misspelled your name, Mr. Berman. *** Everyone, please do a search and replace of Berrman->Berman before distributing the document any further. ***

1 0

ANON: mail concerns
by Karl Lui Barrus 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- Hm.. there have been some concerns over anonymous mail recently... both Alan and Thomas have noted that it is easy to match up sender and destination for a remailer which processes each message as it arrives. Solution: cache all messages and process them later (once a day, once a week, etc.). For example, the remailer at elee9sf(a)menudo.uh.edu caches all incoming requests, and processes them (randomly) at midnight. I didn't even have to modify the remailer scripts to do this; rather, I wrote some extra ones. The process seems stable. The trickiest part is scheduling the remailing: I have to use the 'at' command since I can't have my own crontab. Also, Thomas mentioned what seems to be 'random remailing'. As I mentioned in a previous message ("ANON: anonymous mail"), forcing mail to progress through a network randomly also forces the final destination to be known to everybody, where before only one site knows the final destination. Also, instead of building the necessay headers to hop mail you may be able to use one of several scripts and programs available at soda.berkeley.edu Karl Barrus <klbarrus(a)owlnet.rice.edu> -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLNbQEoOA7OpLWtYzAQEe0QP+KaDWOyep8+wSfEMtUjBOj8OGJMrdSCkO jAfS3zW/uASpOfZ8zgaGBhl8kFPzF9ZyEJyKV/tydIHJdQUEI9K3FU0AE4vB2Fei xcGcM16dZlSSOW/E+CkRR/3UstlRwUuHCccFACTh5SIPIG3mSSVvNMEp7Cz+SIss j5Mkq9KqJc0= =tWzv -----END PGP SIGNATURE-----

2 1

anonymous remailing/posting software
by khijol!erc 17 Dec '03

17 Dec '03

Ah, yes. Once again, it's time to upgrade the APS software here at khijol. For those who don't know, I run an anonymous posting site which posts to only a select set of newsgroups (to prevent abuse). Now that the machine is sitting on the Internet, it's time to revamp the software, and I have thought that it might be easier to hack someone else's than to redo my own (which was one of those all-day hack sessions). Double blind remailing and unique ID services are essential, with the 'nice to have' services like automatic pinging of posts, checksum verifications of posts, automatic encryption/decryption of posts, etc. would be ideal. Any ideas on where I could obtain such software? Shell scripts are OK, C is better. Perl is not desirable unless I really have to. :( Thanks! -- Ed Carp, N7EKG erc(a)apple.com 510/659-9560 an38299(a)anon.penet.fi, anon-1157(a)twwells.com If you want magic, let go of your armor. Magic is so much stronger than steel! -- Richard Bach, "The Bridge Across Forever"

1 0

the GWELST Game
by L. Detweiler 17 Dec '03

17 Dec '03

Hey, I have a neat new game that cypherpunks would be interested in. Unfortunately, I don't have a lot of material for anything but one or two rounds. Maybe some other people can join in as the dealer after this round. GWELST stands for Guess Which Eminent Leader Said This. One eminent cypherpunk leader is the author of a quote I include here. Your mission, if you choose to accept it, is to determine the originator. The quote is: ``There is no movement. Get this delusion out of your head. There is only software.'' A few hints for you all. I was quite depressed and disoriented by this quote at first. I thought, of course there is a movement! That's why I'm here! That's what makes me interested in the Cypherpunks! Isn't a NYT and Wired article an indication of a Movement? Aren't all the people who post here indications of a Movement? Aren't the leaders interested in promoting the Movement? Actually, the answers to all these questions are quite contrary to what you might think. It seems that the real cypherpunk agenda is to *pretend* that there is a movement, and play it out like a movie in a theatre for the audience, and fool them into thinking it is real. Many still do! But this is like being convinced by one of those fake Hollywood building facades, with empty nothingness behind it. The leaders are interested in deceiving reporters like Markoff and Kelly, NYT and Wired respectively, into thinking that the movie is real, that real people are getting real things done. Many of the people who post here are *not* real. Some of the most `respected' ones are tentacles. And the audience is so dazzled by the show that they continue to believe in the Movie despite that it has ended and an usher is telling them to Leave! Many tentacles are dangled before us by the Master Puppeteers themselves. The tentacles assault us on the list and in our mail, sandwiched between real people. How can one tell the difference? Most can't. So the fraud, the mockery, the sham, the farce plays on. So, even the leaders have some honesty in some moments. On rare occasions of unguarded, uncharacteristically candid moments, they hint that there the idea that there is a Movement is actually an elaborate hoax. `There is no movement. Get this delusion out of your head. There is only software.' That last sentence is a reference to the elaborate movie-generating software that they run, that helps them project the characters onto the screen with an amazing degree of realism and verasimilitude. But the characters are not real people. Only after attempting to interact with them like real people, can other real people discover that they are fake. It is like an Eliza-Turing test. Which email addresses are intelligent? Which are tentacles? Hint: The tentacles are like robots that explode when asked a question they cannot answer. Interestingly, the individual A.Abraham, himself involved in the Cypherpunk leadership, who posts as a2(a)ah.com (the infamous Abraham-Hughes site), recently sent me mail along the same lines, saying that `There is only software.' This is a fat clue for you in this round of the GWELSTing Game! Answer will appear shortly!

1 0

Real People
by an12070＠anon.penet.fi 17 Dec '03

17 Dec '03

Hey, there was an interesting series of articles in RISKS 15.25, 15.27, and 15.28x that covered the `Cryptoanarchist' movement. Many cypherpunks may be interested in this analysis. Has it shown up here? I missed it if it did. Boy, the tentacles are *really* pissed off from that E.Hughes == P.Ferguson insinuation in my recent messages. Joe Thomas <jthomas(a)access.digex.net> told me that `you're getting on my nerves' and accuses me of `damaging the list discussion' here. I'm very hurt and upset by this claim. Why don't you lay off a little? I'm just trying to do my job. Some people are born demons, and some people are born exorcists! He says he met P.Ferguson at the D.C. cypherpunks meeting `this spring' (last spring?). What was the date on that, anyway? Who else was there? He said he didn't get to talk to P.Ferguson for very long, but he did see his Virginia driver's license. So, according to J.Thomas <jthomas(a)access.digex.net> anyway, P.Ferguson exists! Thanks for this valuable entry in the Real People Trust Web. Would anyone like to vouch for Joe Thomas, <jthomas(a)access.digex.net>? BTW, I heard that access.digex.net had lax authentication standards like netcom.com. Could anyone send me mail clarifying what is actually required for authentication at these sites? BTW, many thanks to L.Detweiler for his lone help in helping me break a corrupt conspiracy and massive cyberspatial hoax. It's really tough going lately, and we're really being bombarded with some of the most vicious material the tentacles can muster. But we can stand the heat, and we're going to stay in the kitchen, and continue to fight the raging arson flames to make cyberspace safe for honest people. ------------------------------------------------------------------------- To find out more about the anon service, send mail to help(a)anon.penet.fi. Due to the double-blind, any mail replies to this message will be anonymized, and an anonymous id will be allocated automatically. You have been warned. Please report any problems, inappropriate use etc. to admin(a)anon.penet.fi.

2 1

RE: CRYPTOANARCHIST INFILTRATION ALERT
by dheck＠odo.cc.uakron.edu 17 Dec '03

17 Dec '03

who appointed this guy Netcop status? If I wanted to receive info appropriate to alt.whistleblowing, I'd read Usenet...These self-appointed, self-important, self-inflated egos really get under my skin...take me off this list...the signal-to-noise ratio is getting a little out of hand. (By the way, my real name is Heck...) David

1 0

Re: Banning any subscriber
by plaz＠netcom.com 17 Dec '03

17 Dec '03

I said: >>I personally disagree with censorship. It would be impossible to enforce >>anyway. A move of this type would simply drive Detweiler to use the >>Cypherpunk remailers which would be harder to detect. Then what do we do? >>Stop accepting mail from our own remailers? Eric replied: >Basically, yes, except for signed letters from previously >authenticated pseudonyms. This is a simple form of a positive >reputation system. A kill fill is a negative reputation--'not that >person'. A positive reputation rejects all but a particular set of >identities. I'm sorry, I didn't realize that you wanted to erect a barrier against anonymous newbies, such as "wonderer" and "Dark Unicorn" were recently. You know, Detweiler might get a new account under a new name, better seal the list to only postings from "previously authenticated" accounts too. Then we'd be all happy and safe from the dreaded Detweiler. Don't let this guy screw up the positive aspects of the list. His irritant is the by-product of the free world that we are trying to create. You can't stop his communication without comprimising our own goals. (You can delete it without reading it or kill file him or once we are on extropians list software, ::exclude him.) >Much of the debate on cypherpunks magically incants 'reputation >systems' to solve all sorts of sticky problems, but none have ever >been implemented in software, except for killfiles, which are not >effective against disruption in an anonymous environment. > >Necessity is the mother of invention. A motivated individual trying >to disrupt a communications forum and who has to avoid a kill file >will be necessary to create the need for a positive reputation system. >Once the need is there, the software will follow. LD could become the >most valuable participant in the endeavor of creating a positive >reputation system, namely, the irritant at the center of the pearl. > >Let us encapsulate him well. > >Eric I'm not entirely against positive reputation systems, but they really need to be implimented on the user end, or at least be user settings, as on the extropians list. But the main problem with positive reputation systems is dealing with the zero reputation newbies. I don't want to see these guys shut out. Think well, before you act on this impulse. _______________________________________________________________________ Geoff Dale -- insert standard disclaimers here -- plaz(a)netcom.com "Life is a sexually transmitted terminal disease." - Peter McWilliams

2 1