« previous 1 2 3 4 5 next »

Success stories

Since their introduction, TMTOs have been used successfully against a great number of cryptographic algorithms. Among their earliest targets were the LM (LAN Manager) hashes used by Windows to store user passwords. Windows stores a local user password in blocks of seven characters, regardless of its length, which leads to the paradoxical situation that a password with ten characters may be weaker than one with seven. The reason is that the hash is very easy to crack using the last three characters, and the clear text yielded can betray the first seven characters of the password.

The number of passwords that an attack has to take into consideration depends heavily on the character set from which a user selects, or can select, his password. Entropy has become established as a unit of measure for the quality of a password, reflecting the number of possible states it can take on and thus how many passwords have to be tried out in the course of an attack. Seven-character Windows passwords consisting only of letters have the same entropy as 33 randomly selected bits. If special characters and numbers can be used as well as letters, the entropy value is equal to that of 36 bits. Popular combinations, however, such as names, or words ending with a number or an exclamation mark, have far lower entropy.

Typical Windows passwords are therefore easy targets for TMTOs. Tables with a 99 per cent hit rate take about two seconds to crack a 14-character alphanumeric password, while occupying only around one gigabyte of memory [2]. The time taken to load the tables from the hard disk into main memory has to be added to those two seconds, of course, but it pays off if large numbers of passwords are to be cracked. Because of the high collision rate in the LM hash function, pre-computing the tables takes around ten times as long as a brute-force attack – a few weeks on a PC. But ready-made tables can be downloaded from sites such as www.shmoo.com. The high collision rate also makes rainbow tables approximately ten times faster than distinguished points.

It's the other way round for mobile phone calls and A5/1 SMS encryption, a stream cipher that employs 64-bit keys. This uses a random initial state in order to thwart TMTO attacks. Yet it incorporates a cryptographic weakness that allows this protection to be circumvented. There are more than 200 overlapping segments, each of 64 bits, in an encrypted GSM packet – an SMS, for example. An attacker need only crack one of these segments in order to decrypt the complete message, since the cipher can be computed both forwards and backwards from there, to complete the missing bits. Even with incomplete tables, there is a comparatively high likelihood that at least one of the 200 values is included.

Cracking passwords with rainbow tables is blindingly fast. Programs like OphCrack and suitable tables are already available for downloading.

This optimisation enables GSM keys to be cracked with tables that occupy only about one and a half per cent of the space that would theoretically be required for a 64-bit cipher. But it puts rainbow tables out of court, because a few dozen empty passes have to be gone through before a find is made, which is particularly unfavourable with that method.

Because of the lower collision rate, it takes far less effort to pre-compute GSM tables than Windows passwords – about twice as long as a brute-force attack. The 259 calculations do however take several months on expensive special hardware, equipped with field programmable gate arrays (FPGAs).

But, as with Windows hashes, others have already made the effort. The GSM Cracking Project recently compiled tables for A5/1, which they share with researchers who have three terabytes of free memory space. Using the tables, the secret key can be found within 30 seconds with better than 95 per cent probability. Once a key is found, the whole conversation or SMS message can be monitored or read, as appropriate.

The Crypto1 encryption of the Mifare Classic RFID system, which is widely used not only in many contactless travel payment systems and student payment cards, but also in access control systems, is also susceptible to a TMTO attack. The protection against TMTO that Crypto1 provides relies on the individual chip ID contributing to the encryption process, so that an attacker would have to pre-compute a separate table for each chip. But the key and the chip ID are linked with each other through a function that can be inverted, so just one set of tables can be used for all chip IDs. Crypto1 also uses quite short 48-bit keys, making attacks even easier. It took just 50 minutes to generate a set of distinguished points tables on the FPGA cluster, which the GSM Cracking Project also uses. Using these tables, keys can be found in seconds.

Next: Protection against TMTOs

« previous 1 2 3 4 5 next »