The Lotus Position

[tcmay@got.net (Timothy C. May)]

At 4:03 AM 1/20/96, Bill Stewart wrote:

>40-unknown-bit RC4 may take a week for an ICE workstation or a herd of
>net-coordinated workstations, but it would be much faster to crack on
>a specialized machine actually designed for RC4.  I think Eric's estimate
>was $25-50K for a machine that could do it in 15 minutes, built out of
>programmable gate arrays.  That's not $10,000/crack, or $584, but $0.25-.50.
>Would they crack all the keys they wanted for a quarter each?  Sure;
>at that rate it's probably cheaper to crack them than read them
>(though in reality they'd feed most of them to keyword scanners.)

I take it as self-evidently true that NSA would spend the relatively small
amount of money to build a dedicated key cracker...probably at least
several for each major cipher. "In this room, where we used to have the
famed acre of Crays, now we have tenth of an acre of superfast custom key
crackers."

(Yes, I know the Crays are used for other things besides key cracking. In
fact, their main use probably is not for crypanalysis. Also, I'm not
talking about cracking ciphers that are essentially uncrackable with any
amount of compute power, I'm talking about cracking specific instances of
ciphers with NSA-approved key lengths.)

To consider just how _cheap_ such a dedicated machine is to them, consider
that in the late 50s and early 60s they built the "Harvest" machine, in
conjunction with IBM and based to some extent on IBM's "Stretch" machine,
as I recall. (Bamford has a bunch of stuff on it, and our own Norm Hardy
worked on it for IBM in the early 60s...he gave a good talk at a
Cypherpunks meeting on how big it was, how much it cost, its capabilities,
etc.)

The Harvest machine, and its ancillary units, such as the world's largest
and fastest tractor tape drive, cost something like $100 million in today's
dollars, according to Norm and others. And Harvest was still running in
1975-6, when it was finally replaced by the Cray 1. NSA also funded the
early efforts that later became Control Data Corporation (CDC), and NSA was
a major customer of Seymour Cray's CDC 6600, and the later 7600 (and maybe
even the ill-fated Star). NSA and AEC were also the early customers for the
Cray-1, of course.

This gives you some feel for what kind of expenditures "the Fort" is
prepared to make when it sees the need. And the black budgets of other
intelligence agencies, as described in Richelson's excellent books and
other books (such as "Deep Black," an unauthorized history of the National
Reconnaissance Organization), can only be described as "stupefyingly
large." A surveillance satellite can run upwards of $1.5 billion, so
spending a tiny fraction of that to decrypt what you've sniffed out of the
airwaves is a gimme.

The deep black budget is estimated to be something like $25 billion a year.

Recall that the Wiretap Bill _alone_ provided for up to $500 million for
compliance measures. Clearly the FBI somehow view their surveillance
capabilities as being worth at least this much to them, and probably a lot
more.

Throw in the budgets for the DEA, IRS, FinCen, FBI, BATF, and all the other
agencies fighting the Four Horsemen and the citizen-units who stray outside
the drawn lines, and it's clear that NSA could budget several hundred
million dollars *each and every year* for breaking its "approved ciphers."

Like many, I take it for granted that 40-bit RC4 can be broken for "small
change." Moreover, my guess is that foreign traffic is routinely cracked if
it is encrypted. After all, it's the encrypted traffic that is likeliest to
be interesting. (Sure, some dumbos like Pablo Escobar speak in the clear on
cellphones, but the correlation is definitely in the direction of encrypted
traffic being likelier than unencrypted traffic to contain interesting
stuff. This will become even more the case as more people become educated
and as crypto gets built into more things...this is the intelligence and
law enforcement communities' worse nightmare.)

A $25,000 machine. 4 cracks per hour, 100 per day, and 36,000 per year.
Running for an active life of several years (before being replaced, of
course, by something several times faster/cheaper), there you have the
$0.25 per crack that Bill cites above. Even at 100 times this estimate,
it's cheap. (Not for random vacuuming, but for anything targetted, even
casually.)

And think of what just a few percent of the "Harvest" budget buys you: 100
of these machines. Several million cracks per year. And from these cracks,
think of the correlations, the contact lists, and the further targetting
that can be done.

[Sidebar: One thing that bothers me about any of these LEAF-related
schemes--and I don't know if and how the Lotus scheme checks both ends for
compliance, etc.--is that they are fundamentally at odds with remailers
which hide the origin. If remailers are allowed to continue to exist,
schemes involving LEAF fields won't work. Unless I've forgotten how these
things work in the couple of years since I last looked at Clipper et. al.
in depth. So, I expect a move against remailers as part of the campaign.
And with no remailers, if this could ever be enforced, the ability to make
contact lists based on random decryption is frightening.]

Back to their 100 machines....

My guess is that they haven't even bothered to buy this many machines, that
the intelligence they get from a few tens of thousands of cracks is more
than enough to point to further leads, to trigger additional HUMINT, etc.

But even if the estimates are off by orders of magnitude, we know that a
40-bit RC4 can be cracked in ~hours with ~hundreds of Sun-class machines.
(Personally, I think it obvious the NSA has at least speeded up this work
factor by at least a factor of ten.) This is also essentially a minor
consideration compared to the amount of work done in ordinary wiretaps.

And in a few years, 40-bit RC4 will be even more ludicrously weak.

The Lotus position is untenable.

--Tim May

Boycott espionage-enabled software!
We got computers, we're tapping phone lines, we know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^756839 - 1  | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."