1 2 3 4 5 next »

Cheap cracks

Karsten Nohl

Of dictionaries and rainbows

Modern cryptological attacks can crack mobile phone calls, as well as debit and credit card systems, in seconds. The trick is to find a practical compromise between computing time and memory space with the help of precomputed tables. Probably no algorithm is immune to such an approach, but special techniques can thwart such attacks.

The security of any form of encryption is based on a secret key known only to the parties legitimately involved in the communications process. However, progress in cryptanalysis is putting pressure on cryptographic algorithms, and attacking techniques now being used are often able to discover the key. Even algorithms for which no special attack methods have been devised, may be vulnerable with some degree of probability.

The simplest possible attack, which can be used against any encryption algorithm, is to try all the possible keys – after all one of them is bound to work, yielding the original text in clear. Most encryption systems use very long keys in order to make these “brute force” attacks as time-consuming as possible.

There are four billion 32-bit keys, but checking all of them takes just minutes on a PC. An attack can take a month if 48-bit keys are used, while 64-bit keys can bump up the time required to thousands of years. Even COPACOBANA (sic), the expensive special-purpose hardware at the Ruhr University in Bochum, needs about a year to crack a 64-bit key, which means that a brute force attack is more or less hopeless if keys contain 64 or more bits.

The 120 FPGAs of COPACOBANA, the special-purpose hardware at the Ruhr University in Bochum, make short shrift of cryptographic keys containing fewer than 64 bits.

The level of security is calculated a little differently for asymmetrical encryption methods such as RSA (named for its inventors, Rivest, Shamir and Adleman). The RSA cipher can use only a subset of all possible values for a key of a given length, due to the nature of the mathematical problem on which it is based. This explains why an RSA key made up of 1024 bits, for example, is only as secure as an 80-bit key in a symmetrical process.

Depending on the method of encryption, there are other basic methods of attack that can discover a secret key much more quickly than a brute-force approach. Although they need less computing time, they require some preparation that makes heavy demands on computing power or memory. One such preparatory method is to create a dictionary for a specific message that assigns the key used to every possible value of the encrypted message. The dictionary is stored on the hard disk as a list of keys, whose index represents the encrypted value. In order to find the secret key, the attacker now need only induce the system concerned to encrypt the message that fits the list. He can then use the result as a list index.

The one-off generation of the dictionary, however, requires about the same amount of computing time as a brute-force attack, so it only makes sense if the effort is likely to be repaid during a large number of attacks. A dictionary of this kind also gobbles up enormous amounts of memory – 1536 terabytes for a 48-bit key, for example. For a 64-bit key, more memory would be required than is currently available to all humankind. In the case of long keys, therefore, the heavy memory requirement makes a dictionary attack even less practical than a brute-force approach.

Next: Wrapped up in chains

1 2 3 4 5 next »