Home > Brute force attack
In cryptanalysis, a brute force attack is a brute-force search of the 'key space' (i.e., all possible keys) 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 all plaintext encrypted with the found key, though it may also provide hints which might help other 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 never been proven mathematically (at least publically as of 2004) for any cipher other than the one time pad, it is possible that a cipher well regarded today may be shown to be insecure in this sense sometime in future; cryptographers rely on emperical methods, though imperfect, to foretell such developments.
If the keys were originally chosen randomly, or they are searched randomly, the plaintext will on average become available after half of all the possible keys are tried. The underlying assumption in a brute force attack is, of course, that the cipher algorithm is known. Since Auguste Kerckhoffs 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. However, few nations publish the algorithms they use to secure state secrets.
1 Symmetric algorithms
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 FoundationThe Electronic Frontier Foundation EFF is a non-profit advocacy and legal organization with the stated purpose of being dedicated to preserving first amendment rights in the context of today's digital age. Its stated main goal is to ". educate the press, (EFF) project in 19981998 was a common year starting on Thursday (see link for calendar), and was designated the International Year of the Ocean''. Events January January 1998 A massive ice storm, caused by El Nino, strikes New England, southern Ontario and Quebec, resulting (see EFF DES crackerEFF's US$250,000 DES cracking machine contained over 18,000 custom chips and could brute force a DES key in a matter of days — the photo shows a DES Cracker circuit board fitted with several Deep Crack chips In cryptography, the EFF DES cracker (nicknamed), and an RC5RC5 is a block cipher notable for its simplicity. Designed by Ronald Rivest in 1994, RC stands for "Rivest Cipher", or alternatively, "Ron's Code" (compare RC2, RC4). The AES candidate RC6 was based on RC5. Unlike many schemes, RC5 has a variable block si 64-bit key message was broken more recently. Many people feel that well-funded organisations, such as NSA, can now (as of 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 new systems using symmetric key algorithms. Existing systems with at least 90-bit keys are still considered safe. NIST has recommended that 80-bit designs be phased out by 2015.
Even in situations were 128-bit or larger keys are used with well-designed ciphers like AES, a brute force attack may be possible if keys are not gererated properly. Many commercial and shareware security products that proudly advertise "128-bit security" derive keys from a user-selected password or passphrase. Since users rarely employ passwords with anything close to 128 bits of entropy, such systems are often quite easy to break in practice. See: Password cracking. Some security products even limit the maximum number of characters the user can enter to a length that is too small for an adaquate passphrase. Here are some examples of passwords or passphrases that would provide 128-bit security if randomly created and kept secret:
- all single-case letters (28 characters needed): sqrnf oikas ocmpe vflte krbqa jwf
- mixed-case letters, numbers and special characters (20 characters needed): iTb.\ /&/-} it/P; ^+22q
- Diceware passphrase (10 words needed): serf bare gd jab weld hum jf sheet gallop neve
Almost no one uses passwords this complex. One solution is to accept lower strength. 16 letters or 6 Diceware words will provide 75-bit security, enough to protect against all but the most powerful cryptoanalytic agencies. Another partial solution is to use a key derivation function (KDF) or "key stretcher" that performs significant computational work in converting the password into a key, making the brute force attacker repeat this work for each trial key. In practice, this technique can add 10 to 20 bits of strength to a password, enough to allow a reasonably memorable passphrase to be used, but not enough to secure the short passwords most people employ. Unfortunately, few security products incorporate KDF technology.
Perhaps the best solution is to store randomly-generated full-strength keys in a tamper resistant security token, internally protected by a password or PIN.
