Brute force attack
In cryptanalysis, a brute force attack is a brute-force search of the 'key space' (ie, all possible keyss) in an attempt to recover the plaintext used to produce a particular ciphertext. Note that, in most cases, recovery of the plaintext in this way is not equivalent to 'breaking' the underlying cipher as that requires a method of recovering plaintext for all ciphertexts; a successful brute force attack merely supplies one plaintext, though it may also provide hints which might help such a cryptanalysis.In general, a cipher is considered secure if there is no method less 'expensive' (in time, computational capacity, etc) than brute force; Claude Shannon used the term 'work factor' for this. Since this has been proved to be so for very few ciphers, it is possible that a well regarded cipher (today) may be shown to be insecure in this sense sometime in future; there is no known way to foretell such developments.
If the keys were originally chosen randomly, the plaintext is (statistically) likely to become available after about half of all the possible keys are tried. The underlying assumption is, of course, that the cipher algorithm is known. Since A. Kerckoffs first published it, a fundamental maxim of cryptography has been that security must reside only in the key. Around WWII, Shannon gave another version, 'the enemy knows the system'. Given the high number of well regarded ciphers whose design details have unintentionally become available, it has been excellent advice for cryptography designers.
As of the year 2002, symmetric ciphers with keys 64 bits or less are vulnerable to brute force attacks. DES, a well respected symmetric algorithm which uses 56-bit keys, was broken by an Electronic Frontier Foundation (EFF) project in the late '90s (see EFF DES cracker), and an RC5 64-bit key message was broken more recently. Many people feel that well-funded organisations, such as NSA, can now (ca 2004) routinely successfully attack a symmetric key cipher with a 64-bit key using brute force. For applications requiring long term security, 128 bits is currently thought a minimum sensible key length for symmetric key algorithms.
The situation with regard to asymmetric key algorithms is more complicated and depends on the individual encryption algorithm. Thus, the currently breakable key length for the RSA algorithm is at least 512 bits (ie, it has been done publicly), and recent research developments suggest that 1024 bits might be breakable in the near to medium term future. For most elliptic curve asymmetric algorithms, the largest currently breakable key length is believed to be rather shorter, perhaps as little as 128 bits or so. A message encrypted with a 109 bit key by an elliptic curve encryption algorithm was publicly broken by brute force key search in early 2003. At this writing (ca 2004), 128 bit key lengths seem the minimum reasonable for elliptic curve algorithms, and 1024 bits for such asymmetric key algorithms as RSA.
See also
- 40-bit encryption
- Distributed.net
- Password cracking
- Cryptographic key length
- MD5CRK
- Unicity distance
- RSA numbers
- RSA Factoring Challenge
References
- Cracking DES - Secrets of Encryption Research, Wiretap Politics & Chip Design by the Electronic Frontier Foundation (ISBN 1565925203).