Brute force attack: Difference between revisions
imported>Sandy Harris (New page: A brute force or '''exhaustive search''' attack is an attempt to break a cipher by trying all possible keys. This is always possible in theory (except against a one-time pad), but it ...) |
imported>Sandy Harris No edit summary |
||
| Line 1: | Line 1: | ||
A brute force or '''exhaustive search''' attack is an attempt to break a [[cipher]] by trying all possible keys. This is always possible in theory (except against a one-time pad), but it becomes practical only if the key size is inadequate. | A brute force or '''exhaustive search''' attack is an attempt to break a [[cipher]] by trying all possible keys. This is always possible in theory (except against a one-time pad), but it becomes practical only if the key size is inadequate. | ||
For a [[symmetric cipher] | ==Symmetric ciphers== | ||
For a [[symmetric cipher]] longer keys protect against brute force attacks. Each extra bit in the key doubles the number of possible keys and therefore doubles the work a brute force attack must do. In general, with an n-bit key a brute force attack requires 2<sup>n-1</sup> encryptions on average and 2<sup>n</sup> in the worst case. A large enough key defeats any brute force attack. | |||
For example, the EFF's DES Cracker <ref>{{cite book|title=Cracking DES - Secrets of Encryption Research, Wiretap Politics & Chip Design|author=Electronic Frontier Foundation|id=ISBN 1-56592-520-3|publisher=Oreilly & Associates Inc|year=1998|url=http://cryptome.org/cracking-des/cracking-des.htm}}</ref> searched a 56-bit key space in an average of a few days. Assume an attacker that can find a 64-bit key (256 times harder) by brute force search in a second (a few hundred thousand times faster). For a 96-bit key, that attacker needs 2<sup>32</sup> seconds, about 135 years. Against a 128-bit key, he needs 2<sup>32</sup> times that, over 500,000,000,000 years. Your data is then obviously secure against brute force attacks. Even if our estimate of the attacker's speed is off by a factor of a million, it still takes him over 500,000 years to crack a message. | For example, the EFF's DES Cracker <ref>{{cite book|title=Cracking DES - Secrets of Encryption Research, Wiretap Politics & Chip Design|author=Electronic Frontier Foundation|id=ISBN 1-56592-520-3|publisher=Oreilly & Associates Inc|year=1998|url=http://cryptome.org/cracking-des/cracking-des.htm}}</ref> searched a 56-bit key space in an average of a few days. Assume an attacker that can find a 64-bit key (256 times harder) by brute force search in a second (a few hundred thousand times faster). For a 96-bit key, that attacker needs 2<sup>32</sup> seconds, about 135 years. Against a 128-bit key, he needs 2<sup>32</sup> times that, over 500,000,000,000 years. Your data is then obviously secure against brute force attacks. Even if our estimate of the attacker's speed is off by a factor of a million, it still takes him over 500,000 years to crack a message. | ||
This is why | This is why single [[DES]] is now considered dangerously insecure, all of the current generation of block ciphers use a 128-bit or longer key, and [[AES]] ciphers support key sizes 128, 192 and 256 bits. | ||
The question of how large a key is "large enough" has been extensively studied. A summary <ref>{{cite paper|title=Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security|year=1996|url=http://www.crypto.com/papers/keylength.txt}}</ref> recommended a minimum of 90 bits for any new ciphers deployed as of 1996. Computers improve roughly in accord with [[Moore's Law]], twice as fast every 18 months, so ciphers need about one extra bit of key every 18 months to keep up. | |||
==Public-key Systems== | |||
==Cautions== | ==Cautions== | ||
| Line 19: | Line 21: | ||
There may be reasons of convenience in the design of the cipher to support larger keys. For example [[Blowfish]] allows up to 448 bits and [[RC4]] up to 2048, but beyond 100-odd bits it makes no difference to practical security. | There may be reasons of convenience in the design of the cipher to support larger keys. For example [[Blowfish]] allows up to 448 bits and [[RC4]] up to 2048, but beyond 100-odd bits it makes no difference to practical security. | ||
==References== | |||
{{reflist|2}} | |||
Revision as of 23:55, 3 August 2008
A brute force or exhaustive search attack is an attempt to break a cipher by trying all possible keys. This is always possible in theory (except against a one-time pad), but it becomes practical only if the key size is inadequate.
Symmetric ciphers
For a symmetric cipher longer keys protect against brute force attacks. Each extra bit in the key doubles the number of possible keys and therefore doubles the work a brute force attack must do. In general, with an n-bit key a brute force attack requires 2n-1 encryptions on average and 2n in the worst case. A large enough key defeats any brute force attack.
For example, the EFF's DES Cracker [1] searched a 56-bit key space in an average of a few days. Assume an attacker that can find a 64-bit key (256 times harder) by brute force search in a second (a few hundred thousand times faster). For a 96-bit key, that attacker needs 232 seconds, about 135 years. Against a 128-bit key, he needs 232 times that, over 500,000,000,000 years. Your data is then obviously secure against brute force attacks. Even if our estimate of the attacker's speed is off by a factor of a million, it still takes him over 500,000 years to crack a message.
This is why single DES is now considered dangerously insecure, all of the current generation of block ciphers use a 128-bit or longer key, and AES ciphers support key sizes 128, 192 and 256 bits.
The question of how large a key is "large enough" has been extensively studied. A summary [2] recommended a minimum of 90 bits for any new ciphers deployed as of 1996. Computers improve roughly in accord with Moore's Law, twice as fast every 18 months, so ciphers need about one extra bit of key every 18 months to keep up.
Public-key Systems
Cautions
Inadequate keylength always indicates a weak cipher but it is important to note that adequate keylength does not necessarily indicate a strong cipher. There are many attacks other than brute force, and adequate keylength only guarantees resistance to brute force. Any cipher, whatever its key size, will be weak if design or implementation flaws allow other attacks.
Also, once you have adequate keylength, adding more key bits make no practical difference , even against brute force. Consider our 128-bit example above that takes 500,000,000,000 years to break by brute force. We really don't care how many zeroes there are on the end of that, as long as the number remains ridiculously large. That is, we don't care exactly how large the key is as long as it is large enough.
There may be reasons of convenience in the design of the cipher to support larger keys. For example Blowfish allows up to 448 bits and RC4 up to 2048, but beyond 100-odd bits it makes no difference to practical security.
References
- ↑ Electronic Frontier Foundation (1998). Cracking DES - Secrets of Encryption Research, Wiretap Politics & Chip Design. Oreilly & Associates Inc. ISBN 1-56592-520-3.
- ↑ . Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security.