452 VIEWS
Pinterest LinkedIn LINE

This June, it made major news that “DES was broken in only 3 and a half days.” Its significance lies in actually demonstrating something already understood in principle: if the effective key length is successfully reduced, a key can be found quite efficiently even through brute-force effort. What this experiment means is not that DES is dangerous, but that whenever any encryption is used, its effective key length must always be considered.
There are various ways to increase cryptographic strength, but they cost money. Security, including encryption, can be said to begin by classifying information according to its importance.

The EFF’s DES Cracker

This June, it made major news that “DES was broken in only 3 and a half days.” It was broken by an organization called the Electronic Frontier Foundation (EFF), which spent 1 and a half years building a machine equipped with many dedicated chips and broke RSA’s DES Challenge in 3 and a half days.

They used a method called a Plain Text Attack. The cost is said to have been $250,000, of which labor costs are said to have been $80,000. Of course, even on a part-time basis, that could not pay 10 people to work for 1 and a half years, so one can say there were an additional 1 and a half years’ worth of labor costs.

Even so, with perhaps $1,000,000, it should be entirely possible to build a machine capable of finding a DES key within a few days. This happens to concern DES, but the same can actually be said of other forms of encryption. Incidentally, according to their estimates, if money were no object, it would be relatively easy to build a machine that could break one key within seconds. It had long been said that DES contained a special mechanism making it easy for the government to break, but they demonstrated that no such mechanism would have been necessary because money alone should have solved the problem.

How to Break DES (and Other Block Ciphers)

First, let us look at how to break DES (and other ciphers). DES is used as the example here, but the same applies to other block ciphers. (Incidentally, stream ciphers are apparently easier to break.)

Basically, it is broken in 2 stages.

In the first stage, hardware eliminates keys that are clearly incorrect.
Then, in the second stage, software searches the remaining keys.

The method for eliminating clearly incorrect keys is as follows.

First, divide the text into units of 16 bytes. Divide each of those into units of 8 bytes, making 2 units. Start the work with the first 8 bytes.

First, decrypt the first 1 byte with the given key. If it is “interesting,” decode the next 1 byte. Here, “interesting” means that the decoded result falls within the expected character-code space. For example, if the original text is assumed to contain only [A-Z][a-z][0-9] and 2 punctuation marks, the probability that the decoded result is interesting is only 62/256=1/4. (With an incorrect key, any of 256 characters can be expected to appear at random.) If it is interesting, perform the same operation on the next 1 byte. If that too is interesting, do the same with the next one. After inspecting 8 bytes, only 1/(48) will be reported as interesting. Perform the same operation on the next 8 bytes. The probability that both are interesting is (1/(48))2 . This reduces the number of keys that the software must check to 224 . Compared with 256, this is a tremendous improvement.

The remaining task is to compare the resulting text for these 224  possibilities against a dictionary and determine whether it appears to be the correct text. This is the second stage. Since this processing becomes the bottleneck, one crucial point is how far this number can be reduced.

Using this method, the DES Cracker succeeded in decrypting the entire text in a little over 3 days. This method is called a Plain Text Attack.

An even more effective method is called a Known Plain Text Attack. This applies when known text is located at a particular place within the encrypted block. In this case, the 62/256 above becomes 1/256. The number of keys the software must check is then
((1/28)2)8*2128 = 1
In other words, no software checking is needed even if the key is 128 bits.

The Significance of a (Known) Plain Text Attack

The implications of this (Known) Plain Text Attack are serious, because in many cases the location of specific text is known in advance. For example, an MS Word document begins with a particular character string, and on the Web a request begins with GET. Mail often begins with From, and examples like these are innumerable. In other words, encryption on a per-message basis may actually have little meaning.

Moreover, in a simple tunneling arrangement, the IP header is encrypted within the data portion, so a Plain Text Attack can be launched against it. Tunneling therefore reduces the strength of the encryption. It may seem preferable to use tunneling because the IP Address becomes invisible, but considering how encryption works reveals that exactly the opposite is true.

In other words, encryption is not something that helps merely by being applied. Even if a key is long, it is meaningless if the effective Key Space is narrow. That is why discussing encryption strength solely in terms of key length is nonsense. Incidentally, in addition to the matters described above, the effective Key Space also depends on the encryption algorithm. RSA encryption, for example, depends on the difficulty of factorization, but numbers of around 100 digits have now been correctly factored. 2128  is a 39-digit number, so a 128-bit key in RSA encryption can be said to be wholly inadequate. (By contrast, 128 bits in IDEA and similar ciphers is quite secure.)

In any case, protecting security through encryption is a field that requires proper design.

How Should We Respond?

The preceding discussion shows that protecting data is actually quite difficult. Of course, the probability that one’s own data will actually be cracked is quite low. An ordinary cracker is not going to invest $1 million in something like this. Thus, the likelihood of being breached by a cracker on the Internet can be said to be vanishingly small.

The people who can realistically be expected to attempt such cracking are the following:

  • Corporate spies
  • Governments (militaries)

Governments will attempt to crack it in any event. It makes no difference whether it is a dedicated line or anything else. Basically, one should assume that any method permitted in the United States remains in a state where the Department of Defense can monitor it at any time, so let us set that aside. Next are corporate spies, and it is not impossible that they might build something like a DES Cracker. Detecting this is relatively difficult because, unlike crackers, they would never announce that they had broken it. But that does not mean avoiding public networks makes it safe. A company willing to spend $1 million to build a machine and crack it would first recruit an inside collaborator within the target company. It would then try to use that person to obtain the information, so encryption is still better than no encryption. The cost of obtaining the information rises from merely the cost of paying the inside collaborator to that cost plus the cost of breaking the encryption.

There are also ways to make the encryption itself harder to break. One basic method is to increase the Key length, but a variation is a method called Super Encryption. This prevents a Plain Text Attack by applying 2 stages of encryption. With 2 stages of encryption, the text produced when the 1st stage is broken is Random text and cannot be filtered at all. Applying DES 2 times secures an effective key length of at least about 80 bits. It therefore cannot possibly be broken in 3 and a half days. It is about 1024 times more difficult than a Plain Text Attack, so it is not something that can be broken so easily. Rather than break this, it would be better to offer consulting work to an executive nearing retirement.

Whether someone would go that far depends on how much the person obtaining the information could gain from it. Even if that information is extremely important to the company (for example, because a leak would damage its reputation), no one will spend money to obtain it if it cannot make someone else a profit. In that sense, security, including encryption, can be said to begin by classifying information according to its importance.

Related posts

7 Misconceptions About REST

Abroad, the REST-versus-SOAP debate seems already settled[1], for both enterprise and consumer applications. In Japan, however, discussions still reveal considerable confusion, almost like the situation around…

2011-11-21