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). 

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.
>

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

-----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.........

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.
> > 
>

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/

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

>"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-----