# Brute force attack

## Information about Brute force attack

The EFF's US\$250,000 DES cracking machine contained over 1,800 custom chips and could brute force a DES key in a matter of days — the photograph shows a DES Cracker circuit board fitted with several Deep Crack chips.
In cryptanalysis, a brute force attack is a method of defeating a cryptographic scheme by trying a large number of possibilities; for example, exhaustively working through all 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 length depends 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.

## Symmetric ciphers

For symmetric-key ciphers, a brute force attack typically means a brute-force search of the key space; that is, testing all possible keys in order to recover the plaintext used 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.

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 attack is 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 key cipher 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.

The COPACOBANA machine is a reprogrammable and cost-optimized hardware for cryptanalytical applications such as exhaustive key search. It was built for US\$10,000 by the Universities of Bochum and Kiel and contains 120 low-cost FPGAs.

Symmetric ciphers with keys of length up to 64 bits have been broken by brute force attacks. DES, a widely-used block cipher which uses 56-bit keys, was broken by custom hardware in 1998 (see EFF DES cracker), and a message encrypted with RC5 using a 64-bit key was broken more recently by Distributed.net. More recently, the 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. NIST has 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 cracking and passphrase for more information.

Ciphers with proven perfect secrecy, such as the one-time pad, cannot be broken by a brute force attack.

## Theoretical limits

The resources required for a brute force attack scale exponentially with increasing key size, not linearly. Doubling key size does not double the required number of operations, but rather squares the number of required operations. Thus, although 56 bit keys, such as those used by the obsolete Data Encryption Standard (DES) are now quite practical to attack by brute force, this is not true of much longer keys, such as those used by the more modern Advanced Encryption Standard (AES), which uses keys of at least 128 bits in length.

There is a physical argument that a 128 bit 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 logarithm of 2 is about .693. No irreversible computing device can use less energy than this, even in principle.

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. If a device could be built that could check a billion billion keys () per second, 10,790,283,070,806 (~) years would still be required to exhaust the key space. By way of comparison, the age of the universe is only about 13,000,000,000 () years.

(Although on average an attacker will find the key after searching only half the possible keys, this makes no practical difference given the time scales involved.)

AES permits the use of 256 bit keys. A 256 bit key requires not merely twice as long to crack as a 128 bit key, but rather times as long. If a device could be built that could check a billion billion () AES keys per second, it would require a staggering 3,671,743,063,080,802,746,815,416,825,491,118,336,290,905,145,409,708 () years to exhaust the 256 bit key space.

It should therefore be clear that, generally speaking, 128 bit keys are impractical to attack by brute force methods using current technology and resources, and that 256 bit keys are not likely to be broken by brute force methods using any obvious future technology.

## Unbreakable codes

Certain types of encryption, by their mathematical properties, cannot be defeated by brute force. An example of this is one-time pad cryptography, where every bit has a corresponding key bit. 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.

For example, 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.

## Sample of breaking time

Here are some sample times of brute force code breaking, assuming the attacker can try 100000 keys per second, the key is not case sensitive, and all letters of the English alphabet and numerals are used.

 Length Possibilities Time needed to break 1 36 0.0004 seconds 2 1296 0.01 seconds 3 46656 0.5 seconds 4 1679616 17 seconds 5 60466176 10 minutes 6 2176782336 6 hours 7 78364164096 9 days 8 2.8211099×1012 10 months 9 1.0155995×1014 32 years 10 3.6561584×1015 1,161 years 11 1.3162170×1017 41,822 years 12 4.7383813×1018 1,505,614 years

(information gets by Hacking Time Analizer)

## References

• 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).

xxxx
Cryptanalysis (from the Greek kryptós, "hidden", and analıein, "to loosen" or "to untie") is the study of methods for obtaining the meaning of encrypted information, without access to the secret information which is normally required to do so.
Cryptography (or cryptology; derived from Greek κρυπτός kryptós "hidden," and the verb γράφω gráfo "write" or λεγειν legein
key is a piece of information (a parameter) that controls the operation of a cryptographic algorithm. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa during decryption.
In cryptography, the key size (alternatively key length) is the size of the digits used to create an encrypted text; it is therefore also a measure of the number of possible keys which can be used in a cipher, and the number of keys which must be tested to 'break' the
Obfuscation is the concealment of meaning in communication, making it confusing and harder to interpret.

Obfuscation may be used for many purposes. Doctors have been accused of using jargon to conceal unpleasant facts from a patient.
In computer science, brute-force search or exhaustive search is a trivial but very general problem-solving technique, that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.
key is a piece of information (a parameter) that controls the operation of a cryptographic algorithm. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa during decryption.
key is a piece of information (a parameter) that controls the operation of a cryptographic algorithm. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa during decryption.
plaintext is information used as input to an encryption algorithm; the output is termed ciphertext. The plaintext could be, for example, a diplomatic message, a bank transaction, an e-mail, a diary and so forth — any information that someone might want to prevent
encryption is the process of transforming information (referred to as plaintext) to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key.
The known-plaintext attack (KPA) is an attack model for cryptanalysis where the attacker has samples of both the plaintext and its encrypted version (ciphertext) and is at liberty to make use of them to reveal further secret information; typically this is the secret key.
In cryptography, a ciphertext-only attack (COA) is an attack model for cryptanalysis where the attacker is assumed to have access only to a set of ciphertexts.

The attack is completely successful if the corresponding plaintexts can be deduced, or even better, the key.
English}}}
Writing system: Latin (English variant)
Official status
Official language of: 53 countries
Regulated by: no official regulation
Language codes
ISO 639-1: en
ISO 639-2: eng
ISO 639-3: eng
American Standard Code for Information Interchange (ASCII), generally pronounced ask-ee IPA: /ˈæski/ ( [1] ), is a character encoding based on the English alphabet.
Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related, often identical, cryptographic keys for both decryption and encryption.
Claude Shannon

Claude Shannon
Born 30 March 1916
Petoskey, Michigan
Died 24 January 2001 (aged 86)
Data Encryption Standard
The Feistel function (F function) of DES

General
IBM
1975 (standardized on January 1977)

Lucifer
Triple DES, G-DES, DES-X, LOKI89, ICE

Cipher detail
Key size(s):| 56 bits

Block size(s):| 64 bits
block cipher is a symmetric key cipher which operates on fixed-length groups of bits, termed blocks, with an unvarying transformation. When encrypting, a block cipher might take a (for example) 128-bit block of plaintext as input, and output a corresponding 128-bit block
EFF DES cracker (nicknamed "Deep Crack") is a machine built by the Electronic Frontier Foundation (EFF) to perform a brute force search of DES cipher's keyspace—that is, to decrypt an encrypted message by trying every possible key.
RC5
One round (two half-rounds) of the RC5 block cipher

General
Ron Rivest
1994

RC6, Akelarre

Cipher detail
Key size(s):| 0 to 2040 bits (128 suggested)

Block size(s):| 32, 64 or 128 bits (64 suggested)
Feistel-like network
distributed.net (or Distributed Computing Technologies, Inc. or DCTI) is a world-wide distributed computing effort that is attempting to solve large scale problems using otherwise idle CPU time. It is officially recognized as a non-profit organization under U.S.
Motto
"In God We Trust"   (since 1956)
"E Pluribus Unum"   ("From Many, One"; Latin, traditional)
Anthem
National Security Agency/Central Security Service (NSA/CSS) is the United States government's cryptologic organization that was officially established on November 4, 1952. Responsible for the collection and analysis of foreign communications, it coordinates, directs, and performs
20th century - 21st century - 22nd century
1970s  1980s  1990s  - 2000s -  2010s  2020s  2030s
2001 2002 2003 - 2004 - 2005 2006 2007

2004 by topic:
News by month
Jan - Feb - Mar - Apr - May - Jun
The National Institute of Standards and Technology (NIST), known between 1901–1988 as the National Bureau of Standards (NBS), is a non-regulatory agency of the United States Department of Commerce. The institute's mission is to promote U.S.