Non-government cryptologists have been saying DES's 56-bit key was tooshort for some time -- some of them were saying it in the 70's whenDES became a standard -- but the US government hasconsistently ridiculed such suggestions.
A group of well-known cryptographers looked at key lengths in a1996 paper. They suggested aminimum of 75 bits to consider an existing cipher secure anda minimum of 90 bits for new ciphers. More recent papers,covering both symmetricand public key systems are atcryptosavvy.com andrsa.com.For all algorithms, the minimum keylengths recommended in such papers aresignificantly longer than the maximums allowed by various export laws.
In arecent ruling,a German court described DES as "out-of-date and not safe enough" and held abank liable for using it.Dedicated hardware breaks DES in a few days
The question of DES security has now been settled once and for all. Inearly 1998, the Electronic Frontier Foundationbuilt aDES-cracking machine.It can find a DES key in an average of a few days' search. It cost justover $200,000 to design and build it. A copy based on the finished designwould of course cost less.The details of all this, including complete code listings and completeplans for the machine, have been published inCracking DES,by the Electronic Frontier Foundation.
A large corporation could build one of these out of petty cash. The costis low enough for a senior manager to hide it in a departmental budgetand avoid having to announce or justify the project. Any governmentagency, from a major municipal police force up, could afford one too.Or any large criminal organisation, any reasonably large political group,labour union or religious group, . . .
One might wonder if a private security or detective agency would haveone for rent. They wouldn't need many clients to pay off that investment.
"Moore's Law" is that machines get faster (or cheaper, for the same speed)by roughly a factor of two every 18 months. At that rate, the EFF machinewould cost well under $100,000 as I write in mid-2000. By the end of thedecade, building one might be an undergraduate lab project.
Spooks may break DES faster yet
As for the security and intelligence agencies of various nations, someof them may have had DES crackers for years. Possibly very fast ones!Cipher-cracking is one of the few known applications which is easy tospeed up by just adding more processors and memory. Within very broadlimits, you can make it as fast as you like if you have the budget.The EFF's $200,000 machine breaks DES in a few days. Anaviation website gives the cost of aB1 bomber as $200,000,000. Spending that much, an intelligence agencycould expect to break DES in an average time of six and a half minutes.That estimate assumes they use the EFF's 1998 technology and just spend moremoney. They may have an attack that is superior to brute force, they quitehave better chip technology (Moore's law, a bigger budget, and whateversecret advances they may have made) and of course they may have spentthe price of an aircraft carrier, not just one aircraft.
In short, we have no idea how quickly these organisations can breakDES. Unless they're grossly incompetent, they can certainly do it more quicklythan the users of the cipher would like, but beyond that we can't say.Pick any time unit between days and milliseconds. None of these is entirelyunbelievable. More to the point, none of them is of any comfort if youdon't want such organisations reading your communications.
Note that this may be a concern even if nothing you do is a threat toanyone's national security. An intelligence agency might well considerit to be in their national interest for certain companies to do well.If you're competing against such companies in a world market and thatagency can read your secrets, you have a serious problem. For oneexample, see thisnews story.The US are the villains in that piece, but there is no reason to imaginethey are the only, or even the worst, villains in this area.
One might wonder about technolgy the former Soviet Union and its alliesdeveloped for cracking DES during the Cold War. They must have tried;the cipher was an American standard and widely used. How well did theysucceed? Is their technology now for sale or rent?Networks break DES in a few weeks
Before the definitive EFF effort, DES had been cracked several timesby people using many machines. See thispress release for example.
A major corporation, university, or government department could breakDES by using spare cycles on their existing collection of computers,by dedicating a group of otherwise surplus machines to the problem, orby combining the two approaches. It might take them weeks or months,rather than the days required for the EFF machine, but they could do it.
What about someone working alone, without the resources of a largeorganisation? For them, cracking DES will not be easy, but it may bepossible. A few thousand dollars buys a lot of surplus workstations,especially since Year 2000 concerns driven more old machinesinto the surplus market. A pile of such machines will certainly heatyour garage nicely and might break DES in a few months or years. Orenroll at a university and use their machines. Or use an employer'smachines. Or crack security somewhere and steal the resources to cracka DES key. Or write a virus that steals small amounts of resources onmany machines. Or . . .
None of these approaches are really easy or break DES really quickly, butan attacker only needs to find one that is feasible and breaks DES quicklyenough to be dangerous. How much would you care to bet that this will beimpossible if the attacker is determined and/or clever? How valuable isyour data? Are you authorised to risk it on a dubious bet?
We disable DES
In short, it is now absolutely clear that DES is not secure against- any well-funded opponent
- any opponent (even a pennilessone) with access (even stolen access) to enough general purposecomputers
DES is in the source code, because we need DES to implement ourdefault encryption transform, Triple DES.We urge you not to use single DES. We do notprovide any easy way to enable it in FreeS/WAN, and our policyis to provide no assistance to anyone wanting to do so.40-bits is laughably weak
The same is true, in spades, of ciphers -- DES or others -- crippledby 40-bit keys, as many ciphers were required to be until recentlyunder various export laws.A brute force search of such a cipher's keyspace is 216times faster than a similar search against DES. The EFF's machinecan do a brute-force search of a 40-bit key space in seconds.One contest to crack a 40-bit cipher was won by a studentusing a few hundred idle machines at his university. Ittook only three and half hours.
We do not, and will not, implement any 40-bit cipher.Alternatives to DES
A number of non-DES encryption algorithms have been proposed. We willimplement some of them eventually, of course choosing ciphers with atleast 128-bit key length.AES in IPSEC
The winning candidate from the AESproject to develop a replacementfor DES will almost certainly become widely used for IPSEC, but analysistakes time and no winner is expected before the summer of 2000.
Meanwhile, there is a variant of DES which is far better than plain DES.Triple DES, usually abbreviated3DES, applies DES three times, with three different keys. This is believedto be much stronger thansingle DES, and it quite definitely turns brute-force key search into aridiculous impossibility. 3DES is what our code now uses bydefault. 3DES is, unfortunately, about 1/3 the speed of DES, but modernCPUs still do it at quite respectable speeds. Somespeed measurements for our codeare available.
Click below to go to:- Document index file
- Table of Contents
- Beginning of this file
- FreeS/WAN home page
