Comparing Cryptographic Key Sizes
Below is a explanation of the meaning of cryptographic key sizes which started as an explanation I wrote for a journalist friend of mine, on being asked about how relatively secure a system using DES and RSA (SET) was as compared to netscapes export version of SSL. I've re-written it to make it more general in scope. One of the most common errors I see in news stories about cryptographic breaks is to (say) compare 1024 bit RSA keys with 56 bit symmetric keys as if the two key sizes are directly comparable. This new document is intended to be simple and understandable to give people a handle on how to describe and compare cryptographic systems strengths. This document by design glosses over some details, where I think this is reasonable. It could use some criticism. If you are not that crypto aware, does it make sense to you? If you are crypto aware, what do you think of my off the cuff estimates of hardness? I wrote it with journalists in mind. If you are a journalist and find it useful, feel free to quote parts/all of it without attribution. Adam Comparing Cryptographic Key Sizes There are two types of key sizes: public key (sometimes called asymmetric key) and symmetric keys. Examples of public key algorithms are RSA, and Diffie-Hellman. Examples of symmetric key algorithms are RC4, DES, IDEA. You can not directly compare public key lengths (for example RSA keys) with symmetric key lengths (DES, RC4). This is an important point which confuses many people. For example 40 bit RC4 (a symmetric key cipher) can be broken in a few hours with a few hundred workstations. 40 bit RSA (a public key cipher) can be broken in a fraction of a second on one PC. RSA keys need to be I'd guess around 350 bits to be equivalent in strength to 40 bit RC4. 56 bit DES is probably roughly similar to 512 bit RSA in hardness to break. Symmetric keys sizes are easy to reason with: one more bit in key length is twice as hard to break, for the same algorithm. It is more complicated estimating the hardness to break of public key (say RSA) keys of varying sizes as they get harder more gradually than symmetric keys. This is why public key systems have longer keys, you need more bits to get the same security level. Most systems use a mixture of public and symmetric key ciphers. This is because public key ciphers are _slow_. Symmetric key ciphers are fast, and so are used in combination with public key systems to speed up the combined system. Public key systems are used because of the advantages of public key management they make possible. When considering the strength of a system using two ciphers one public key and one symmetric key, the strength of the system is equal to the strength of the weakest link. For example: consider the export version of SSL, as shipped in the export version of Netscape browsers and servers. It uses 512 bit RSA, and 40 bit RC4. It is easier to crack 40 bit RC4 than it is to crack 512 bit RSA, so export SSL can be broken by breaking the 40 bit RC4 component. Ian Goldberg recently broke a 40 bit RC5 key himself with Berkeley univ machines in 3.5 hours. 40 bit RC4 could be broken in a similar amount of time. 512 bits RSA is not enough either, and you can rest assured that the NSA, other governments' secret services, and any corporation or organised crime group with sufficient funds can break it. 512 bits is likely within reach of a distributed internet effort, of similar or smaller scale than the recent DES breaking. 56 bit DES is harder to break than 40 bit RC4 (SSL), from the number bits you might think it would be 65536 times harder, but it's less than that because DES is faster than RC4. In software it's about 5 times faster, so that means breaking DES in software is about 10000 times harder than breaking 40 bit RC4 (as used in export SSL) in software. But, if the Russian Mafia, or a corporation involved in industrial espionage wanted to break 56 bit DES they would not do it in software. They would build a special purpose piece of hardware which was designed only to break DES. DES was designed to be fast in hardware, it is a relatively slow ciphers in software. About 10 years ago now Michael Wiener made a design for such a DES breaking machine. He estimated it would cost $10,000,000 to build a machine which would break a 56 bit DES encrypted message a few hours. His machine was scalable, pay more money, break the key faster, pay less take longer. The estimate was that could build one with enough DES key searching units to break it in a day for $1,000,000. That was 10 years ago. 10 years is a long time in the computer industry. Nowadays you build the machine more cheaply as chip technology has progressed, and computers are much faster per $. Estimates are around $100,000 to build the machine (neglecting hardware engineers consultancy fees). Everyone expects that NSA, GCHQ, SCSSI have built such a machine for $100,000+. This is obvious because the NSA and SCSSI allow export of 56 bit DES. $100,000 is not much money for a secret service. Algorithms using 40 bit keys aren't secure at all, past a very superficial casual level of protection. Systems using DES, such as SET are only secure against organisations who can't raise $100,000 and can't find people who know lots about crypto and hardware design. $100,000 is not much money for a secret service. It's not much for the Rusian Mafia either. END
participants (1)
-
Adam Back