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