Re: Bank transactions on Internet

At 12:13 AM 4/9/96 -0700, Steve Reid wrote:
>> Is it really that easy to break 40-bit? Don't you need access to a "fair
>> amount of cpu power" to brute force crack 40bit? 
>
>I remember reading a recent paper at this URL:
>  http://theory.lcs.mit.edu/~rivest/bsa-final-report.ascii
>They mentioned a Field Programmable Gate Array (FPGA), specifically a
>board-mounted AT&T Orca chip available for around $400. They said it could
>crack a 40-bit key in 5 hours (average). Sounds like anyone with root
>access on a major internet node could make a significant profit stealing
>credit card numbers.
>
>The FPGA sounds like a very interesting device, with quite a few
>legitimate uses... Has anyone out there seen one of these? 

I was hoping a hardware type would answer this question, and give
references to manufacture's spec sheets, but not having seen such an
answer, here is a software person's answer.

Gate arrays are a common part of complex electronics.  If you are viewing
this answer on a screen, it is quite probable that there is one right
before your nose.  They come in two basic forms, mask programmed and field
programmed.  Mask programmed gate arrays are an array of logic gates, which
are "programmed" to an application by a final metalization layer.  They are
quite inexpensive when ordered in quantity.  Field Programmed Gate Arrays
(FPGAs) are designed for prototyping designs, and can programmed
electrically.


------------------------------------------------------------------------
Bill Frantz       | The CDA means  | Periwinkle  --  Computer Consulting
(408)356-8506     | lost jobs and  | 16345 Englewood Ave.
frantz@netcom.com | dead teenagers | Los Gatos, CA 95032, USA

> At 12:13 AM 4/9/96 -0700, Steve Reid wrote:
> >> Is it really that easy to break 40-bit? Don't you need access to a "fair
> >> amount of cpu power" to brute force crack 40bit? 
> >
> >I remember reading a recent paper at this URL:
> >  http://theory.lcs.mit.edu/~rivest/bsa-final-report.ascii
> >They mentioned a Field Programmable Gate Array (FPGA), specifically a
> >board-mounted AT&T Orca chip available for around $400. They said it could
> >crack a 40-bit key in 5 hours (average). Sounds like anyone with root
> >access on a major internet node could make a significant profit stealing
> >credit card numbers.
> >
> >The FPGA sounds like a very interesting device, with quite a few
> >legitimate uses... Has anyone out there seen one of these? 
> 
> I was hoping a hardware type would answer this question, and give
> references to manufacture's spec sheets, but not having seen such an
> answer, here is a software person's answer.

I thought Perry Metzger's short answer (roughly "yes, but the software
can be tricky") adequate, but as a hardware type I can give some more
insight into the economics.  While my experience is with gate array ASICs
rather than field programmable chips, I have some idea.

My short answer:  Yes, it's that cheap, but only if you already work
with the chip vendor and have the software tools to program the chips.
If not, expect to spend many thousands of dollars buying engineering
expertise and software.

There's a lot of different ways to make chips for a custom application,
which vary in unit cost, startup cost, engineering effort, and production
time.

Some points in the range:  (costs are probably off a bit)

type			startup cost	program		design tool

full custom		$1000000	at design time	schematic editors
ASIC			$100000		at design time	gate synthesis
FPGA			$0		once		vendor's tools
reprogrammable FPGA	$0		dynamically	vendor's tools
DSP chip		$0		easily		compiler
General purpose CPU	$0		very easily	compiler

Anyone who knows these better is welcome to correct me, of course.

I've neglected software costs from this, which are significant.  Chip
synthesis tools are often more expensive than the workstations they run on.

Also, in most cases some of the necesary tools are only available from the
company that sells the chips.  They tend to insist on nondisclosure
agreements and software licenses, which makes anonymous production tricky.

More design effort will give better price/performance.  The appeal of the
Orca and similar chips is that they can be reprogrammed, but still have the
inherent parallelism of gates in silicon.

I expect that in 5 or 10 years, PC's will come with reprogrammable logic
chips and software that takes advantage of it.  At present it really
takes a trained engineer to use these things.  That's just enough difficulty
that people might feel secure, without actually being secure at all.

Jon Leonard

>>>>> "Jon Leonard" <jleonard@divcom.umop-ap.com> writes:

  > My short answer: Yes, it's that cheap, but only if you already
  > work with the chip vendor and have the software tools to program
  > the chips.  If not, expect to spend many thousands of dollars...

Huh?  We're talking about modern FPGAs here.  The cost of the tools
necessary to actually *program* the damn things is very small, as
almost all of them are SRAM-based and programmed out of an external
EPROM, bus, or serial bitstream.

Sure, we've spent $50,000 on FPGA *development* tools, but we program
the serial EEPROMs themselves on $300 PC-based programmers which are
available -- as are the FPGAs and EEPROMs -- from Digikey, Allied,
Newark, etc., to anyone with a credit card.

Actually, in almost all of our designs, the FPGAs are programmed
in-circuit by application software.  If I were to design a hardware
key cracker, it would almost certainly be a simple ISA-bus card
containing a couple of big Xilinx FPGAs which would get programmed by
a simple C program.

[Funny thing -- there seems to be a lot of "theft" of satellite and
 cable programming by folks who know just enough to use a soldering
 iron, but haven't a clue about what really happens inside a set-top
 box.  How do they manage it, if they don't have the tools to design or
 reverse-engineer a cable converter?  Hmmm...]

-- 
Roger Williams            PGP key available from PGP public keyservers
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/

Coincidentaly enough, this is part of my project for my Hardware class.
I'll let you know when I have it working.  I'm using Altera FLEX 81188s,
though the 10K models (with built-in RAM) would be _way_ faster...

   - Ian

On 10 Apr 1996, Ian Goldberg wrote:

> Coincidentaly enough, this is part of my project for my Hardware class.
> I'll let you know when I have it working.  I'm using Altera FLEX 81188s,
> though the 10K models (with built-in RAM) would be _way_ faster...

Once someone gets this kind of cracking device ready, I think it would be
nice to make the information freely available, or start selling these for
nominal price.

This would also make an interesting device connected to Internet. In case
of fast device people could use it either for free or pay using ecash for
using it, and crack their SSL sessions. May be Netscape or Microsoft or
someone else (may be even Community Connexion :) lobbying the government
for allowing export of strong encryption could sponsor it. It should not
be so expencive. Much more useful than amazing fish-cam or coke machine on
Internet.

Juri Kaljundi
jk@digit.ee

> 
> 
	As a hardware(and sometimes software) type who has used these sorts
of parts in real designs several things need be said.  

	First, the $400 cost is about what the physical chip and test
board would cost, it does not include the cost of the software packages
required to generate the programming information for the chip and
simulate and verify the design.   While this software can sometimes be
pirated or "borrowed" from an employer or school or even the chip
distributors, charges for a legitimate copy of the software for
programming many kinds of FPGA's can run in the low to mid thousands and
it it is usually dongle protected.
And the more advanced software packages that take high level
descriptions of the logic in languages such as VHDL and compile them
into the special optimized forms required to get speed out of FPGAs with
highly assymetric routing delays through their interconnect networks are
considerably more expensive and may require RISC workstation hardware
(most of them ran only on Suns or HP in the past) and unix rather than
just a high end PC running Win 95. Costs of this sort of software
package and workstation run as high as $50K per seat.
And it is rather unlikely that one could make a high clock speed
high performance hardware based key cracker work without traditional
high speed logic debugging tools such as a fast logic analyzer (if we
are talking 5-10 ns clock especially) and a 1 ghz or so digital scope.
These kinds of gear, though sometimes available after hours to engineers
working for more liberal companies or schools, cost many thousands
of dollars and are not garden variety items available to any hacker.
And finally, depending on the technology of the part being
used, there may be a significant cost in the order of at least hundreds
if not thousands of dollars for a specialized programmer capable of
programming ("burning") the FPGA with the interconnect patterns generated
by the software. These tend to either be specialized to one kind of
part and maybe modestly cheap (hundreds of dollars) or universal and
several thousands of dollars (such as DataIO gear).
And at least in my experiance (I may be unusually stupid and
careless and clumsy or may not be) even if the parts are a few times
reprogrammable (as CMOS FPGAs often are these days) one can assume
that one will fry, or break the pins off, or reprogram one time too
many the FPGA or FPGA's before one gets the design working.  This
means that it would be realistic to assume several parts would be
consumed by the prototyping effort, they may not be cheap and this
adds up too.

	So whilst someone working with these parts as part of their job
or schooling might well have access to all the required resources on an
informal basis and be able to build a key cracker in evenings or
weekends for little more than the cost of the chip and a PC board to
hold it, it should be realistically noted that the actual cost of
equiping a lab from scratch with the required resources is more on the
order of tens to hundreds of thousands of dollars rather than $400.

	I must hasten to add that high density FPGAs have many many
legitimate uses in prototyping logic and producing products in small
volumes too small to justify the tooling costs of doing mask programmed 
gate arrays (which tend to be significantly faster and easier to design,
but cost $5-100K NRE to set up custom masks for fabrication). The
current generation of them make it possible to build logic systems in
one small chip that a few years ago would have been large  PC boards
full of PALs and other logic.

	Actually designing a workable key cracker for say RC-4 would be
a significant design challenge even with current parts, but probably not
something that someone skilled in the art (and of course reasonably
bright) couldn't handle. (At first blush I think in the case of RC-4
the pipelined key scheduling logic required would be the very hard
thing to make efficient). And the availablity of simulation and timing
analysis tools would make the process of creating such a deamon largely
a software or logic programming exercise that could be mostly carried
out over weeks or months of effort on a workstation or high performance
PC, rather than something that requires the intensive resources of an
extensive hardware lab for a long period.
Unfortunately, like so many hacker projects these days, the cost
of reproducing multiple copies of a cracker and the skill level required
is very minimal compared to the real logic programming talent and
architectural insight it would take to fit one into a FPGA or two.
So once one is built, there can be hundreds or thousands of copies
made and put to work in the underground by all sorts of evil people who
wouldn't have a prayer of designing one from scratch,

						Dave Emery
						die@die.com

>>  At 12:13 AM 4/9/96 -0700, Steve Reid wrote:
  >> a board-mounted AT&T Orca chip available for around $400. They
  >> said it could crack a 40-bit key in 5 hours (average)...
  >> ... Has anyone out there seen one of these?

>>>>> "Dave Emery" <die@pig.die.com> pessimised:

  > [... the tools are too expensive...]
  > [... and the skills required are too high...]
  > [... for anyone on cypherpunks...]

Come on, Dave, this isn't alt.2600!  

Most of the subscribers to this list are professionals -- engineers,
programmers, mathematicians, lawyers -- not phone phreaks.  I'm sure
that there are more than a few of us with the knowledge, experience,
and free access to the resources needed to handle most relatively
small-scale designs like this.

(It's like saying that no one on cypherpunks has access to the
distributed computing resources necessary to perform other sorts of
brute-force cracking -- which is patently ludicrous.)

For instance, from where I'm sitting in my *home* office, I can see
the full development packages for Xilinx and AT&T FPGAs, Viewlogic
VHDL, schematic, and simulation tools, an HP 1660A logic analyser, and
a Tek THS 720 500 MHz digital scope.

And I doubt if I'm the only one here who does this for a living.

The problem isn't resources, but time and motivation -- what sort of
situation would it take to get me (for instance), and one of
cypherpunk's cryptography wizards, to take the time to collaborate on
something like this.

(BTW, if you're willing to break the design into a couple of FPGAs,
like the Motorola MPA 1000 devices, you can find all the software you
need for free...)

-- 
Roger Williams            PGP key available from PGP public keyservers
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/