Re: Borders *are* transparent
Jeff wrote:
The retail version of Netscape Navigator sold in US stores has been the US version for almost a year now. The first run were the export version, because the marketing people thought it would be easier. When I explained the issue, they made the change to the stronger US version immediately. --Jeff
This, I think, is one place where the activities of members of this list have had a real effect. Last September, three or four semi-overlapping efforts succeeded in brute-forcing 40 bit RC4 (used in export-quality SSL). This had three main effects: 1. Raising the issue in the media, and thus in the public consciousness. 2. Within a month, the government was starting to talk about permitting the export of stronger (but GAK'd) encryption products. 3. It enabled people like Jeff to argue successfully that releasing only an export-strength product was no longer a viable option.In practical terms is probably the most important effect of the crack: I know of at least one other company where it led directly to the release of both domestic and export versions. Any one up for a distributed brute force attack on single DES? My back-of-the-envelope calculations and guesstimates put this on the hairy edge of doability (the critical factor is how many machines can be recruited - a non-trivial cash prize would help). Peter Trei trei@process.com "Exportable strong encryption" is an oxymoron.
"Peter Trei" <trei@process.com> wrote:
Any one up for a distributed brute force attack on single DES? My back-of-the-envelope calculations and guesstimates put this on the hairy edge of doability (the critical factor is how many machines can be recruited - a non-trivial cash prize would help).
I'll be there. I have a pair of PowerPC machines that I can donate for a week or so. -- Marshall Marshall Clow Aladdin Systems <mailto:mclow@mailhost2.csusm.edu> "We're not gonna take it/Never did and never will We're not gonna take it/Gonna break it, gonna shake it, let's forget it better still" -- The Who, "Tommy"
Marshall Clow writes: : >"Peter Trei" <trei@process.com> wrote: : > : > Any one up for a distributed brute force attack on single DES? My : > back-of-the-envelope calculations and guesstimates put this on the : > hairy edge of doability (the critical factor is how many machines can : > be recruited - a non-trivial cash prize would help). : > : I'll be there. : I have a pair of PowerPC machines that I can donate for a week or so. I am afraid that the number of machines needed would trivialize even the most non-trivial cash prize. But for what its worth, I can give you a lot of spare cycles on a couple of 486 Linux boxes. -- Peter D. Junger--Case Western Reserve University Law School--Cleveland, OH Internet: junger@pdj2-ra.f-remote.cwru.edu junger@samsara.law.cwru.edu
On Tue, 23 Jul 1996, Peter D. Junger wrote:
I am afraid that the number of machines needed would trivialize even the most non-trivial cash prize. But for what its worth, I can give you a lot of spare cycles on a couple of 486 Linux boxes.
Not really - you just give the prize to the first person to return the correct key (just like a real lottery). BTW, if you use a central site to allocate ranges to search, this site should not know the correct key, as otherwise it could decide who gets the chocolate bar with the golden ticket. If this project is run, I can't see it getting a hit for at least six months unless its _really_ well promoted. The java approach would be a cool hook - a slowish applet for your web page with something along the lines of "You may already have won 20c; whilst you're reading this page, your computer is playing the cypherpunks challenge. For a better chance of winning, download this free high performance screen saver and game piece." Simon --- Cause maybe (maybe) | In my mind I'm going to Carolina you're gonna be the one that saves me | - back in Chapel Hill May 16th. And after all | Email address remains unchanged You're my firewall - | ........First in Usenet.........
-----BEGIN PGP SIGNED MESSAGE----- On Tue, 23 Jul 1996, Simon Spero wrote:
Date: Tue, 23 Jul 1996 13:38:59 -0400 (EDT) From: Simon Spero <ses@tipper.oit.unc.edu> To: "Peter D. Junger" <junger@pdj2-ra.F-REMOTE.CWRU.Edu> Cc: Cypherpunks <cypherpunks@toad.com> Subject: Re: Borders *are* transparent
On Tue, 23 Jul 1996, Peter D. Junger wrote:
I am afraid that the number of machines needed would trivialize even the most non-trivial cash prize. But for what its worth, I can give you a lot of spare cycles on a couple of 486 Linux boxes.
Not really - you just give the prize to the first person to return the correct key (just like a real lottery).
But who's money?
BTW, if you use a central site to allocate ranges to search, this site should not know the correct key, as otherwise it could decide who gets the chocolate bar with the golden ticket.
Definatly.
If this project is run, I can't see it getting a hit for at least six months unless its _really_ well promoted. The java approach would be a cool hook - a slowish applet for your web page with something along the lines of
"You may already have won 20c; whilst you're reading this page, your computer is playing the cypherpunks challenge. For a better chance of winning, download this free high performance screen saver and game piece."
Or better yet... use an applet and a cookie... you pass it a cookie, the applet figures the processor type and runs a certain number of cracks, (within a specified range, listed in the cookie) changes the cookie, and returns it (that may or may not have been sarcasm ;) --Deviant Whatever occurs from love is always beyond good and evil. -- Friedrich Nietzsche -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQEVAwUBMfXQWDAJap8fyDMVAQHudwf9HRjkXkToQcUb4dnmfLYl4LO3PFa0RCrF ADOZmOpdOGlHhSFmzXRM/mdd/hnPnbltVpAULC8Pkb+ztGOyAUbSyYyZaBszNKNE dF0ri0e+NXs6UNDFQonGriM3Qi+3Pvb4fVXYvJ5Of1NIvDlO+rSOzrymo6j1wb6A 1HA7/jj3xtpy0vV/175QNgnqmIcGFEn89biR/nVQpGuFBEXw+JGajjibohAbcvbv xeaxuKvNg3rMk0ynqUDL2/5sYGUf9q4VzLzmjt9c12OIt83lUWH4YAj7gDCrpCyx Lxsxln3Y9b6DoeBmtMY1RT9rUiNHziBOD7r1ePeGcrdAAVjFuR5QNg== =lltr -----END PGP SIGNATURE-----
"Peter Trei" <trei@process.com> wrote: Any one up for a distributed brute force attack on single DES? My back-of-the-envelope calculations and guesstimates put this on the hairy edge of doability (the critical factor is how many machines can be recruited - a non-trivial cash prize would help). Not quite sure what you mean by "doability" -- it's obviously doable, it just depends how long you want to wait. I'm in. -- Paul Foley <mycroft@actrix.gen.nz> --- PGPmail preferred PGP key ID 0x1CA3386D available from keyservers fingerprint = 4A 76 83 D8 99 BC ED 33 C5 02 81 C9 BF 7A 91 E8 ---------------------------------------------------------------------- Disclaimer: "These opinions are my own, though for a small fee they be yours too." -- Dave Haynie
Perhaps a Java page containing a DES cracker that one could run for the casual participant, and a set of links to download a real cracker for the non-casual participant... I think its really time that we did this. DES must be shown to be dead. When the media hear about it, they will, of course, get "experts" saying "but it took five thousand people millions of dollars in computer time". We should ask Matt Blaze to write a paper in advance explaining that although this test, on general hardware, took a lot of effort, that with specialized hardware it would be cheap as can be. Perry Paul Foley writes:
"Peter Trei" <trei@process.com> wrote:
Any one up for a distributed brute force attack on single DES? My back-of-the-envelope calculations and guesstimates put this on the hairy edge of doability (the critical factor is how many machines can be recruited - a non-trivial cash prize would help).
Not quite sure what you mean by "doability" -- it's obviously doable, it just depends how long you want to wait.
I'm in.
I've a few machines around that could be dedicated almost full time to the task. What are the bandwidth requirements? Specifically, could the keycracker be run over a 28.8 (with a 486 running linux)? If so, how many 486's could I get over a single 28.8 (i.e. 28.8 -> multiple 486's daisy chained with ppp over direct serial connection)? --nc On Mon, 22 Jul 1996, Perry E. Metzger wrote:
Perhaps a Java page containing a DES cracker that one could run for the casual participant, and a set of links to download a real cracker for the non-casual participant...
I think its really time that we did this. DES must be shown to be dead.
When the media hear about it, they will, of course, get "experts" saying "but it took five thousand people millions of dollars in computer time". We should ask Matt Blaze to write a paper in advance explaining that although this test, on general hardware, took a lot of effort, that with specialized hardware it would be cheap as can be.
Perry
Paul Foley writes:
"Peter Trei" <trei@process.com> wrote:
Any one up for a distributed brute force attack on single DES? My back-of-the-envelope calculations and guesstimates put this on the hairy edge of doability (the critical factor is how many machines can be recruited - a non-trivial cash prize would help).
Not quite sure what you mean by "doability" -- it's obviously doable, it just depends how long you want to wait.
I'm in.
I don't want to throw water over what I think would be a very useful thing to have done, but I'm really skeptical that current "net" computing power with general purpose processors is up to this. My back of the envelope calculation, making some generous assumptions about the implementation, suggests that such an effort would require somewhere in the range of 10,000 and 50,000 CPU years on general (100MHz or so Pentium) processors. This is well beyond any distributed computation I'm aware of ever having been done, even adjusting for "Moore inflation". While feasible in a "complexity theory" sense, it's really not realistic yet. Even if it were feasible, what would we use as a challenge key? Personally, I'd rather someone finish up the Wiener ASIC to the point where it could go out to fab, get some prototype chips made, design a board around it, and publish the design, from board layout on down. This would be a great Master's project, and some of us (maybe me, but I'll have to check) might even be able to scrape up enough funds to buy enough chips/boards/etc to build a modest size machine (say, that could exhaust a DES key in 1-6 months). Initial engineering costs aside, the marginal cost of each such machine could be well within the budgets of, say, a medium size crypto research lab, and would make a scary enough demo to convince even the most trusting management types of the risks of 56 bit keys. -matt (Please cc me on replies, as I'm not reading the list except when someone alerts me to an interesting topic. Thanks.)
I've a few machines around that could be dedicated almost full time to the task. What are the bandwidth requirements? Specifically, could the keycracker be run over a 28.8 (with a 486 running linux)? If so, how many 486's could I get over a single 28.8 (i.e. 28.8 -> multiple 486's daisy chained with ppp over direct serial connection)?
--nc
On Mon, 22 Jul 1996, Perry E. Metzger wrote:
Perhaps a Java page containing a DES cracker that one could run for the casual participant, and a set of links to download a real cracker for the non-casual participant...
I think its really time that we did this. DES must be shown to be dead.
When the media hear about it, they will, of course, get "experts" saying "but it took five thousand people millions of dollars in computer time". We should ask Matt Blaze to write a paper in advance explaining that although this test, on general hardware, took a lot of effort, that with specialized hardware it would be cheap as can be.
Perry
Paul Foley writes:
"Peter Trei" <trei@process.com> wrote:
Any one up for a distributed brute force attack on single DES? My back-of-the-envelope calculations and guesstimates put this on the hairy edge of doability (the critical factor is how many machines can be recruited - a non-trivial cash prize would help).
Not quite sure what you mean by "doability" -- it's obviously doable, it just depends how long you want to wait.
I'm in.
Matt Blaze writes:
I don't want to throw water over what I think would be a very useful thing to have done, but I'm really skeptical that current "net" computing power with general purpose processors is up to this.
I think it is a stretch, admittedly, but that it can be done, and most importantly, it can be done nearly for "free".
My back of the envelope calculation, making some generous assumptions about the implementation, suggests that such an effort would require somewhere in the range of 10,000 and 50,000 CPU years on general (100MHz or so Pentium) processors. This is well beyond any distributed computation I'm aware of ever having been done, even adjusting for "Moore inflation". While feasible in a "complexity theory" sense, it's really not realistic yet.
I'm not entirely sure. It is certainly bigger than the factorings that have been done, but on the other hand it is fairly easy to put together the experiment, and there are an awful lot of idle machines out there in the world. I have on several occassions been in possession of four or five hundred idle CPUs at night, and I am pretty sure that other people are in that position. The net has also grown quite dramatically in recent years, and reaching 100,000 reasonably high speed machines might not be so hard these days. At that point, it becomes a question of how fast one can get the DES cracker. A constant factor of two or three then makes a considerable difference in the outcome, as does the user friendlyness of the overall system.
Personally, I'd rather someone finish up the Wiener ASIC to the point where it could go out to fab, get some prototype chips made, design a board around it, and publish the design, from board layout on down. This would be a great Master's project, and some of us (maybe me, but I'll have to check) might even be able to scrape up enough funds to buy enough chips/boards/etc to build a modest size machine (say, that could exhaust a DES key in 1-6 months). Initial engineering costs aside, the marginal cost of each such machine could be well within the budgets of, say, a medium size crypto research lab, and would make a scary enough demo to convince even the most trusting management types of the risks of 56 bit keys.
Well, that would certainly be cool, but this does require real money. If you are willing to spend it, go for it, but I'm not sure we can count on people doing that sort of thing. What do you suppose the odds are that someone is going to build such a thing any time soon? Perry
Perry writes:
I'm not entirely sure. It is certainly bigger than the factorings that have been done, but on the other hand it is fairly easy to put together the experiment, and there are an awful lot of idle machines out there in the world. I have on several occassions been in possession of four or five hundred idle CPUs at night, and I am pretty sure that other people are in that position. The net has also grown quite dramatically in recent years, and reaching 100,000 reasonably high speed machines might not be so hard these days. At that point, it becomes a question of how fast one can get the DES cracker. A constant factor of two or three then makes a considerable difference in the outcome, as does the user friendlyness of the overall system.
Here are my back-of-the-calculator numbers: 2^55 = 3.6 * 10^16 trial ecb operations (+key setup). Best P-100 DES software implementation I can find can do 110000 ECBs/sec. Key setup takes about twice as long as a single ECB. Assuming amazingly fast key setup and careful ECB optimization (precompute IP and FP, gray coded key enumeration with cached round results, etc), MAYBE, somehow, you could do 100000 ECB/sec on "average" workstation (average = 100mhz Pentium). That's 11000 Pentium-100 years for half the DES keyspace.
Personally, I'd rather someone finish up the Wiener ASIC to the point where it could go out to fab, get some prototype chips made, design a board around it, and publish the design, from board layout on down. This would be a great Master's project, and some of us (maybe me, but I'll have to check) might even be able to scrape up enough funds to buy enough chips/boards/etc to build a modest size machine (say, that could exhaust a DES key in 1-6 months). Initial engineering costs aside, the marginal cost of each such machine could be well within the budgets of, say, a medium size crypto research lab, and would make a scary enough demo to convince even the most trusting management types of the risks of 56 bit keys.
Well, that would certainly be cool, but this does require real money. If you are willing to spend it, go for it, but I'm not sure we can count on people doing that sort of thing. What do you suppose the odds are that someone is going to build such a thing any time soon?
Well, I'm working on getting the funds to build (or support someone to build) some kind of parallel DES engine. I can probably scrape together an FPGA-based machine that can do a key in less than 6 months. I'm very serious about this project, but I can't say for sure when or if I'll be ready to start. -matt
Matt Blaze writes:
Here are my back-of-the-calculator numbers: [...] MAYBE, somehow, you could do 100000 ECB/sec on "average" workstation (average = 100mhz Pentium).
That's 11000 Pentium-100 years for half the DES keyspace.
Hmmm... Lets assume 20,000 P100 Years to give a bit more breathing room. 100,000 machines would be needed to get the thing into striking distance. I think that is potentially doable. Hard, but doable. Managing to avoid search failure (that is, having someone find the key but somehow fail to report back) is the biggest problem, I think.
Well, I'm working on getting the funds to build (or support someone to build) some kind of parallel DES engine. I can probably scrape together an FPGA-based machine that can do a key in less than 6 months. I'm very serious about this project, but I can't say for sure when or if I'll be ready to start.
If you can manage to do that, then I'd say that the software only approach could be abandoned. Meanwhile, I think its time to try to build those DES cracking screensavers for Windows... Perry
A little bit off topic, but some years ago some guys at our university were working on a project called "Cryptographic module for digital communications". I don't know if they ever finished it though, but it might be of some use to someone out there. The project aim was: Create integrated circuit (further CryptoChip or CC) capable of key exchange and generation using modular exponent based cryptosystem and block encryption using IDEA cipher. The ideology behind CC is based on having the minimal amount of information inside the chip and guaranteed block cipher encryption rate above 10 Mbit/sec. They have an old web page at: http://www.pld.ttu.ee/cchip/cchip.html Jüri Kaljundi jk@stallion.ee
On Tue, 23 Jul 1996, Matt Blaze wrote: <snip>
Personally, I'd rather someone finish up the Wiener ASIC to the point where it could go out to fab, get some prototype chips made, design a board around it, and publish the design, from board layout on down. This would be a great Master's project, and some of us (maybe me, but I'll have to check) might even be able to scrape up enough funds to buy enough chips/boards/etc to build a modest size machine (say, that could exhaust a DES key in 1-6 months). Initial engineering costs aside, the marginal cost of each such machine could be well within the budgets of, say, a medium size crypto research lab, and would make a scary enough demo to convince even the most trusting management types of the risks of 56 bit keys. alerts me to an interesting topic. Thanks.)
Matt, can you give us an idea of the cost of a "modest size machine" might be? Is this something we can do with a C'punks bake sale or our we going to need corporate/academic support? Also, if we do use the bake sale approach, is there some way the money can be collected and routed into an R&D sort of facility without causing a lot of stink with whomever actually runs the place, like a university? ------------------------------------------------------------------------- |Just as the strength of the Internet is |Mark Aldrich | |chaos, so the strength of our liberty |GRCI INFOSEC Engineering | |depends upon the chaos and cacophony of |maldrich@grci.com | |the unfettered speech the First Amendment|MAldrich@dockmaster.ncsc.mil | |protects - District Judge Stewart Dalzell| | |_______________________________________________________________________| |The author is PGP Empowered. Public key at: finger maldrich@grci.com | | The opinions expressed herein are strictly those of the author | | and my employer gets no credit for them whatsoever. | -------------------------------------------------------------------------
On Tue, 23 Jul 1996, Matt Blaze wrote:
<snip>
Personally, I'd rather someone finish up the Wiener ASIC to the point where it could go out to fab, get some prototype chips made, design a board around it, and publish the design, from board layout on down. This would be a great Master's project, and some of us (maybe me, but I'll have to check) might even be able to scrape up enough funds to buy enough chips/boards/etc to build a modest size machine (say, that could exhaust a DES key in 1-6 months). Initial engineering costs aside, the marginal cost of each such machine could be well within the budgets of, say, a medium size crypto research lab, and would make a scary enough demo to convince even the most trusting management types of the risks of 56 bit keys. alerts me to an interesting topic. Thanks.)
Matt, can you give us an idea of the cost of a "modest size machine" might be? Is this something we can do with a C'punks bake sale or our we going to need corporate/academic support? Also, if we do use the bake sale approach, is there some way the money can be collected and routed into an R&D sort of facility without causing a lot of stink with whomever actually runs the place, like a university?
My estimate is that an FPGA-based machine that can do a single DES key every four months (eight months to exhaust the whole keyspace) could be built with off-the-shelf stuff for comfortably under $50k (plus labor, plus software development costs). A prototype board should cost under $1000 and will help prove the concept and get a more accurate cost estimate. I expect to build such a prototype machine myself, and, if it works as I expect, maybe the whole thing. -matt
Matt Blaze <mab@crypto.com> writes:
[FPGA-based machine that can do a single DES key every four months] ... I expect to build such a prototype machine myself, and, if it works as I expect, maybe the whole thing.
Matt, I don't know exactly what resources you've got at your disposal these days, but we'd be interested in volunteering some time and effort on this. We can help out with things like interface design, device simulation, board layout, fab, and assembly. (Unless you want to make the whole thing a one-man thesis project, of course ;-) -- Roger Williams finger me for my PGP public key Coelacanth Engineering consulting & turnkey product development Middleborough, MA wireless * DSP-based instrumentation * ATE tel +1 508 947-8049 * fax +1 508 947-9118 * http://www.coelacanth.com/
-----BEGIN PGP SIGNED MESSAGE----- On Mon, 22 Jul 1996, Perry E. Metzger wrote:
Date: Mon, 22 Jul 1996 19:14:23 -0400 From: "Perry E. Metzger" <perry@piermont.com> To: Ben Holiday <ncognito@gate.net> Cc: cypherpunks@toad.com Subject: Re: Distributed DES crack
Ben Holiday writes:
I've a few machines around that could be dedicated almost full time to the task. What are the bandwidth requirements?
Probably near zero. People can get sections of the search space parceled out to them.
Perry
Well... as long as someone else is writing the code... I'm up for a small section of search space. --Deviant Whatever occurs from love is always beyond good and evil. -- Friedrich Nietzsche -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQEVAwUBMfUQHjAJap8fyDMVAQFFQwf7BxBxEOxHPMNOcWDeZCiThi4+iev8GjwO iQeW1diio1KdjyWyO1j/VHMkmiE3fLxOwTA+eRUJNh80+vInE4Waz8O5LlqyBvOY CylckQQl6q0ilPjJFcQSBLdChhmObqHVm60gPRaACXNyI394HIHudm1p84uyG1II hGpU5o6q7GiQmf7B9ThlwCQAW/sGYGpKmJ150WYE7lHoZutJ96TfFrOYLPoR8h3b z5qMoYLigdphOSFLDz8ewtRQO0c0oZepAJSclnFNj8nyIkHroviZ+/92kEnfRk0V 5B8SO9gwtfziletdTk7LrGAJwOIqvqi06+tXhQ/FtJohHEHC8MDo+Q== =5Ep7 -----END PGP SIGNATURE-----
On Mon, 22 Jul 1996, Perry E. Metzger wrote:
Ben Holiday writes:
I've a few machines around that could be dedicated almost full time to the task. What are the bandwidth requirements?
Probably near zero. People can get sections of the search space parceled out to them.
I've always wondered whether chinese lotterys could be made more reliable by having each player check random keys rather than searching within a block. That way it becomes a lot harder to spoof by volunteering for a block and reporting incorrect results. --- Cause maybe (maybe) | In my mind I'm going to Carolina you're gonna be the one that saves me | - back in Chapel Hill May 16th. And after all | Email address remains unchanged You're my firewall - | ........First in Usenet.........
participants (12)
-
Ben Holiday -
Jüri Kaljundi -
Mark O. Aldrich -
Marshall Clow -
Matt Blaze -
Paul Foley -
Perry E. Metzger -
Peter D. Junger -
Peter Trei -
Roger Williams -
Simon Spero -
The Deviant