- Brute force attack
cryptanalysis, a brute force attack is a method of defeating a cryptographicscheme by trying a large number of possibilities; for example, possible keys in order to decrypt a message. In most schemes, the theoretical possibility of a brute force attack is recognized, but it is set up in such a way that it would be computationally infeasible to carry out. Accordingly, one definition of "breaking" a cryptographic scheme is to find a method faster than a brute force attack.
The selection of an appropriate
key lengthdepends on the practical feasibility of performing a brute force attack. By obfuscating the data to be encoded, brute force attacks are made less effective as it is more difficult to determine when one has succeeded in breaking the code.
The brute force attack could be combined with a
For symmetric-key ciphers, a brute force attack typically means a
brute-force searchof the key space; that is, testing all possible keys in order to recover the plaintextused to produce a particular ciphertext.
In a brute force attack, the expected number of trials before the correct key is found is equal to half the size of the key space. For example, if there are 264 possible keys, a brute force attack would, on average, be expected to find a key after 263 trials. [cite book | author = Bruce Schneier | title = Applied Cryptography, Second Edition | publisher = John Wiley & Sons | date = 1996 | pages = p. 151 | isbn = 0-471-11709-9]
For each trial of a candidate key the attacker needs to be able to recognize when he has found the correct key. The most straightforward way is to obtain a few corresponding plaintext and ciphertext pairs, that is, a
known-plaintext attack. Alternatively, a ciphertext-only attackis possible by decrypting ciphertext using each candidate key, and testing the result for similarity to plaintext language—for example, English encoded in ASCII.
In general, a
symmetric keycipher is considered secure if there is no method less expensive (in time, memory requirements, etc) than brute force; Claude Shannon used the term "work factor" for this.
Symmetric ciphers with keys of length up to 64 bits have been broken by brute force attacks. DES, a widely-used
block cipherwhich uses 56-bit keys, was broken by custom hardware in 1998 (see EFF DES cracker), and a message encrypted with RC5using a 64-bit key was broken more recently by Distributed.net. More recently, the [http://www.copacobana.org COPACOBANA (Cost-Optimized Parallel COde Breaker)] was built, which is a reconfigurable code breaker that is suited for key searching of many different algorithms, including DES. In addition, it is commonly speculated that government intelligence agencies (such as the U.S. NSA) can successfully attack a symmetric key cipher with long key lengths, such as a 64-bit key, using brute force. For applications requiring long term security, 128 bits is, as of 2004, currently thought a sufficient key length for new systems using symmetric key algorithms. NISThas recommended that 80-bit designs be phased out by 2015.
If keys are generated in a weak way, for example, derived from a guessable-
password, it is possible to exhaustively search over a much smaller set, for example, keys generated from passwords in a dictionary. See password crackingand passphrasefor more information.
Ciphers with proven perfect secrecy, such as the
one-time pad, cannot be broken by a brute force attack.
The resources required for a brute force attack scale exponentially with increasing
key size, not linearly. As a result, doubling the key size for an algorithm does not simply double the required number of operations, but rather squares them. Although algorithms which use 56 bit keys (e.g. the obsolete DES) are now vulnerable to brute force attack, this is not true of more modern encryption algorithms such as AES, Twofishand Serpent which use 128, 192 or 256 bit keys as standard.
There is a physical argument that a 128 bit symmetric key is secure against brute force attack. The so-called Von Neumann-Landauer Limit implied by the laws of physics sets a lower limit on the energy required to perform a computation of per bit erased in a computation, where T is the temperature of the computing device in
kelvin, k is the Boltzmann constant, and the natural logarithmof 2 is about 0.693. No irreversible computing device can use less energy than this, even in principle. [Rolf Landauer, " [http://domino.research.ibm.com/tchjr/journalindex.nsf/c469af92ea9eceac85256bd50048567c/8a9d4b4e96887b8385256bfa0067fba2?OpenDocument Irreversibility and heat generation in the computing process] ," IBM Journal of Research and Development, vol. 5, pp. 183-191, 1961.]
Thus, in order to simply flip through the possible values for a 128-bit symmetric key (ignoring doing the actual computing to check it) would require bit flips. If we assume that the calculation occurs near room temperature (~300 K) we can apply the Von Neumann-Landauer Limit to estimate the energy required as Joules, which is equivalent to consuming 30 gigawatts of power for one year (). The full actual computation—checking each key to see if you have found a solution—would consume many times this amount.
However, this argument assumes that the register values are changed using conventional set and clear operations which inevitably generate entropy. It has been shown that computational hardware can be designed not to encounter this theoretical obstruction: see
reversible computing. It should be pointed out that no known such computers have been constructed.
The amount of time required to break a 128 bit key is also daunting. Each of the possibilities must be checked. This is an enormous number, 340,282,366,920,938,463,463,374,607,431,768,211,456 in decimal. A device that could check a billion billion keys () per second would still require about years to exhaust the key space. This is longer than the
age of the universe, which is about 13,000,000,000 () years.
AES permits the use of 256 bit keys. Breaking a symmetric 256 bit key by brute force requires times more computational power than a 128 bit key. A device that could check a billion billion () AES keys per second would require about years to exhaust the 256 bit key space.
Hence, 128 bit symmetric keys are impractical to attack by brute force methods using current technology and resources, and 256 bit keys are not likely to be broken by brute force methods using any obvious future technology. The underlying assumption is that the complete keyspace is used to generate keys, something that relies on an effective random number generator.
Certain types of encryption, by their mathematical properties, cannot be defeated by brute force. An example of this is
one-time padcryptography, where every cleartextbit has a corresponding key bit. One-time pads rely on the ability to generate a truly random sequence of key bits. A brute force attack would eventually reveal the correct decoding, but also every other possible combination of bits, and would have no way of distinguishing one from the other. A small 100 byte one-time pad encoded string subjected to a brute force attack would eventually reveal every 100 byte string possible, including the correct answer, but mostly nonsense. Of all the answers given, there is no way of knowing which is the correct one. Nevertheless, the system can be defeated if not implemented correctly, for example if one-time pads are re-used. [cite book|url=http://books.google.com/books?id=3nTmBW0ONEEC&pg=PA86|title=Secret Code Breaker II: A Cryptanalyst's Handbook|author=Robert Reynard|isbn=1889668060|date=1997|acccessdate=2008-09-21|pages=p86]
A number of systems that were originally thought to be impossible to crack by brute force have nevertheless controversially been cracked in this manner. For example,
Netscape's implementation of Secure Sockets Layer(SSL) was cracked by Ian Goldbergand David Wagnerin 1995, after they discovered that the key spacewas in practice smaller than anticipated due to a bug in the random number generator of the software. A similar bug was found in 2008 in the OpenSSLlibrary used by the Debianand Ubuntuoperating systems. [cite web|url=http://www.us-cert.gov/cas/techalerts/TA08-137A.html|title=Technical Cyber Security Alert TA08-137A: Debian/Ubuntu OpenSSL Random Number Generator Vulnerability|date=2008-05-16|accessdate=2008-08-10|publisher= United States Computer Emergency Readiness Team]
Cryptographic key lengthfor a fuller discussion of recommended key sizes for symmetric and asymmetric algorithms.
RSA Factoring Challenge
Custom hardware attack
* Leonard M. Adleman, Paul W. K. Rothemund, Sam Roweis and Erik Winfree, On Applying Molecular Computation To The Data Encryption Standard, in Proceedings of the Second Annual Meeting on DNA Based Computers, Princeton University, June 10–12, 1996.
* "Cracking DES — Secrets of Encryption Research, Wiretap Politics & Chip Design" by the Electronic Frontier Foundation (ISBN 1-56592-520-3).
* W. Diffie and M.E. Hellman, Exhaustive cryptanalysis of the NBS Data Encryption Standard, Computer 10 (1977), pp74–84.
* Michael J. Wiener, "Efficient DES Key Search", presented at the rump session of Crypto 93; reprinted in Practical Cryptography for Data Internetworks, W. Stallings, editor, IEEE Computer Society Press, pp31–79 (1996).
* [http://www.cl.cam.ac.uk/users/rnc1/brute.html Brute force attacks on cryptographic keys] — a survey by Richard Clayton
* [http://www.distributed.net/des/ DES cracking contest]
* [http://www.keylength.com/ www.keylength.com: An online keylength calculator]
* [http://www.copacobana.org The COPACOBANA (Cost-Optimized Parallel COde Breaker) reconfigurable code breaker]
* [http://www.digitalgenesis.com/software/phrel/ phrel: A Linux utility to help prevent brute force attacks on FTP, DNS and other protocols.]
* [http://www.webappsec.org/projects/threat/classes/brute_force.shtml WASC Threat Classification - Brute Force]
Wikimedia Foundation. 2010.