Citizendia

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.
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. The Electronic Frontier Foundation ( EFF) is an international non-profit advocacy and legal organization based in the United States with the stated purpose of being dedicated In Cryptography, the EFF DES cracker (nicknamed " Deep Crack " is a machine built by the Electronic Frontier Foundation (EFF to perform a

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. Cryptanalysis (from the Greek kryptós, "hidden" and analýein, "to loosen" or "to untie" is the study of methods for Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write" In Cryptography, a key is a piece of information (a Parameter) that determines the functional output of a cryptographic algorithm 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. In Cryptography, key size or key length is the size (usually measured in bits or bytes of the key used in a cryptographic algorithm (such as a Cipher 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. Obfuscation is the concealment of meaning in Communication, making it Confusing and harder to Interpret.

The brute force attack could be combined with a dictionary attack. In Cryptanalysis and Computer security, a dictionary attack is a technique for defeating a Cipher or authentication mechanism by trying to determine its

Contents

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 Computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique In Cryptography, a key is a piece of information (a Parameter) that determines the functional output of a cryptographic algorithm In Cryptography, a key is a piece of information (a Parameter) that determines the functional output of a cryptographic algorithm In Cryptography, plaintext is the information which the sender wishes to transmit to the receiver(s

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. [1]

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. The known-plaintext attack (KPA is an Attack model for Cryptanalysis where the attacker has samples of both the Plaintext and its encrypted 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 Cryptography, a ciphertext-only attack (COA or known ciphertext attack is an Attack model for Cryptanalysis where the attacker is assumed English is a West Germanic language originating in England and is the First language for most people in the United Kingdom, the United States American Standard Code for Information Interchange ( 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. Symmetric-key algorithms are a class of Algorithms for Cryptography that use trivially related often identical Cryptographic keys for both decryption Claude Elwood Shannon (April 30 1916 – February 24 2001 an American Electronic engineer and Mathematician, is "the father of Information

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, Germany, and contains 120 low-cost FPGAs.
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, Germany, and contains 120 low-cost FPGAs. Ruhr University Bochum ( German Ruhr-Universität Bochum, RUB) located on the southern hills of central Ruhr area Bochum The University of Kiel ( German Christian-Albrechts-Universität zu Kiel, CAU) is a University in the city of Kiel, Germany Germany, officially the Federal Republic of Germany ( ˈbʊndəsʁepuˌbliːk ˈdɔʏtʃlant is a Country in Central Europe.

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. The Data Encryption Standard ( DES) is a Cipher (a method for Encrypting information selected by NBS as an official Federal Information In Cryptography, a block cipher is a symmetric key Cipher which operates on fixed-length groups of Bits termed blocks, with an In Cryptography, the EFF DES cracker (nicknamed " Deep Crack " is a machine built by the Electronic Frontier Foundation (EFF to perform a In Cryptography, RC5 is a Block cipher notable for its simplicity distributednet (or Distributed Computing Technologies Inc or DCTI) is a world-wide Distributed computing effort that is attempting to solve large scale 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. The United States of America —commonly referred to as the The National Security Agency/ Central Security Service ( NSA/CSS) is a cryptologic intelligence agency of the United States government 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. In computing a password is a Word or string of characters that is entered often along with a user name, in modern times usually into a computer system In Cryptanalysis and Computer security, a dictionary attack is a technique for defeating a Cipher or authentication mechanism by trying to determine its See password cracking and passphrase for more information. Password cracking is the process of recovering Passwords from data that has been stored in or transmitted by a Computer system. A passphrase is a sequence of words or other text used to control access to a computer system program or data

Ciphers with proven perfect secrecy, such as the one-time pad, cannot be broken by a brute force attack. In Cryptography, the one-time pad (OTP is an Encryption Algorithm where the Plaintext is combined with a random key or "pad"

Theoretical limits

The resources required for a brute force attack scale exponentially with increasing key size, not linearly. Exponential growth (including Exponential decay) occurs when the growth rate of a mathematical function is proportional to the function's current value In Cryptography, key size or key length is the size (usually measured in bits or bytes of the key used in a cryptographic algorithm (such as a Cipher 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. The Data Encryption Standard ( DES) is a Cipher (a method for Encrypting information selected by NBS as an official Federal Information In Cryptography, the Advanced Encryption Standard ( AES) also known as Rijndael, is a Block cipher adopted as an Encryption

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 ln(2)kT 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 0. Landauer's Principle, first argued in 1961 by Rolf Landauer of IBM, holds that "any logically irreversible manipulation of information such as the erasure The kelvin (symbol K) is a unit increment of Temperature and is one of the seven SI base units The Kelvin scale is a thermodynamic Bridge from macroscopic to microscopic physics Boltzmann's constant k is a bridge between Macroscopic and microscopic physics The natural logarithm, formerly known as the Hyperbolic logarithm is the Logarithm to the base e, where e is an irrational 693. No irreversible computing device can use less energy than this, even in principle. [2]

Thus, in order to simply flip through the possible values for a 128-bit key (ignoring doing the actual computing to check it), one would need a device consuming at a minimum 10 gigawatts (about the equivalent of eight large, dedicated nuclear reactors) running continuously for 100 years. This page lists examples of the power in Watts produced by various different sources of energy This article is a subarticle of Nuclear power. A nuclear reactor is a device in which Nuclear chain reactions are initiated controlled 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. Reversible computing includes any Computational process that is (at least to some close approximation Reversible, i 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 2128 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 (1018) per second would still require about 1013 years to exhaust the key space. This is longer than the age of the universe, which is about 13,000,000,000 (1.3 \times 10^{10}) years. The age of the Universe is the time elapsed between the theory of the Big Bang and the present day

AES permits the use of 256 bit keys. Breaking a 256 bit key by brute force requires 2128 time more computational power than a 128 bit key. A device that could check a billion billion (1018) AES keys per second would require about 3 \times 10^{51} years to exhaust the 256 bit key space.

Hence, 128 bit 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.

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. In Cryptography, the one-time pad (OTP is an Encryption Algorithm where the Plaintext is combined with a random key or "pad" 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.

See also

References

External links

Notes

  1. ^ Bruce Schneier (1996). Applied Cryptography, Second Edition. John Wiley & Sons, p. 151. ISBN 0-471-11709-9.  
  2. ^ Rolf Landauer, "Irreversibility and heat generation in the computing process," IBM Journal of Research and Development, vol. 5, pp. 183-191, 1961.
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic