In cryptography, a brute-force attack consists of an attacker submitting many passwords or passphrases with the hope of eventually guessing correctly. The attacker systematically checks all possible passwords and passphrases until the correct one is found. Alternatively, the attacker can attempt to guess the key which is typically created from the password using a key derivation function. This is known as an exhaustive key search.

A brute-force attack is a cryptanalytic attack that can, in theory, be used to attempt to decrypt any encrypted data (except for data encrypted in an information-theoretically secure manner).  Such an attack might be used when it is not possible to take advantage of other weaknesses in an encryption system (if any exist) that would make the task easier.

When password-guessing, this method is very fast when used to check all short passwords, but for longer passwords other methods such as the dictionary attack are used because a brute-force search takes too long. Longer passwords, passphrases and keys have more possible values, making them exponentially more difficult to crack than shorter ones.

Brute-force attacks can be made less effective by obfuscating the data to be encoded making it more difficult for an attacker to recognize when the code has been cracked or by making the attacker do more work to test each guess. One of the measures of the strength of an encryption system is how long it would theoretically take an attacker to mount a successful brute-force attack against it.

Brute-force attacks are an application of brute-force search, the general problem-solving technique of enumerating all candidates and checking each one. The word 'hammering' is sometimes used to describe a brute-force attack, with 'anti-hammering' for countermeasures.

Basic concept

Brute-force attacks work by calculating every possible combination that could make up a password and testing it to see if it is the correct password. As the password's length increases, the amount of time, on average, to find the correct password increases exponentially.

Theoretical limits
The resources required for a brute-force attack grow exponentially with increasing key size, not linearly. Although U.S. export regulations historically restricted key lengths to 56-bit symmetric keys (e.g. Data Encryption Standard), these restrictions are no longer in place, so modern symmetric algorithms typically use computationally stronger 128- to 256-bit keys.

There is a physical argument that a 128-bit symmetric key is computationally secure against brute-force attack. The 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 kelvins, k is the Boltzmann constant, and the natural logarithm of 2 is about 0.693 (0.6931471805599453). No irreversible computing device can use less energy than this, even in principle.  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, theoretically, require 2128 − 1 bit flips on a conventional processor.  If it is assumed that the calculation occurs near room temperature (≈300 K), the Von Neumann-Landauer Limit can be applied to estimate the energy required as ≈1018 joules, which is equivalent to consuming 30 gigawatts of power for one year. This is equal to 30×109 W×365×24×3600 s = 9.46×1017 J or 262.7 TWh (about 0.1% of the yearly world energy production). The full actual computation – checking each key to see if a solution has been found – would consume many times this amount. Furthermore, this is simply the energy requirement for cycling through the key space; the actual time it takes to flip each bit is not considered, which is certainly greater than 0 (see Bremermann's limit).

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), though no such computers are known to have been constructed.

 
As commercial successors of governmental ASIC solutions have become available, also known as custom hardware attacks,  two emerging technologies have proven their capability in the brute-force attack of certain ciphers. One is modern graphics processing unit (GPU) technology, the other is the field-programmable gate array (FPGA) technology.  GPUs benefit from their wide availability and price-performance benefit, FPGAs from their energy efficiency per cryptographic operation. Both technologies try to transport the benefits of parallel processing to brute-force attacks. In case of GPUs some hundreds, in the case of FPGA some thousand processing units making them much better suited to cracking passwords than conventional processors.
Various publications in the fields of cryptographic analysis have proved the energy efficiency of today's FPGA technology, for example, the COPACOBANA FPGA Cluster computer consumes the same energy as a single PC (600 W), but performs like 2,500 PCs for certain algorithms. A number of firms provide hardware-based FPGA cryptographic analysis solutions from a single FPGA PCI Express card up to dedicated FPGA computers.  WPA and WPA2 encryption have successfully been brute-force attacked by reducing the workload by a factor of 50 in comparison to conventional CPUs and some hundred in case of FPGAs.

Advanced Encryption Standard (AES) permits the use of 256-bit keys. Breaking a symmetric 256-bit key by brute force requires 2128 times more computational power than a 128-bit key. One of the fastest supercomputers in 2019 has a speed of 100 petaFLOPS which could theoretically check 100 million (1014) AES keys per second (assuming 1000 operations per check), but would still require 3.67×1055 years to exhaust the 256-bit key space. 

An underlying assumption of a brute-force attack is that the complete key space was used to generate keys, something that relies on an effective random number generator, and that there are no defects in the algorithm or its implementation.  For example, a number of systems that were originally thought to be impossible to crack by brute force have nevertheless been cracked because the key space to search through was found to be much smaller than originally thought, because of a lack of entropy in their pseudorandom number generators. These include Netscape's implementation of Secure Sockets Layer (SSL) (cracked by Ian Goldberg and David Wagner in 1995) and a Debian/Ubuntu edition of OpenSSL discovered in 2008 to be flawed.  A similar lack of implemented entropy led to the breaking of Enigma's code.

Credential recycling
Credential recycling is the hacking practice of re-using username and password combinations gathered in previous brute-force attacks. A special form of credential recycling is pass the hash, where unsalted hashed credentials are stolen and re-used without first being brute forced.

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 cleartext bit has a corresponding key from a truly random sequence of key bits. A 140 character one-time-pad-encoded string subjected to a brute-force attack would eventually reveal every 140 character string possible, including the correct answer – but of all the answers given, there would be no way of knowing which was the correct one. Defeating such a system, as was done by the Venona project, generally relies not on pure cryptography, but upon mistakes in its implementation, such as the key pads not being truly random, intercepted keypads, or operators making mistakes.

Countermeasures
In case of an offline attack where the attacker has gained access to the encrypted material, one can try key combinations without the risk of discovery or interference. In case of online attacks, database and directory administrators can deploy countermeasures such as limiting the number of attempts that a password can be tried, introducing time delays between successive attempts, increasing the answer's complexity (e.g., requiring a CAPTCHA answer or employing multi-factor authentication), and/or locking accounts out after unsuccessful login attempts.  Website administrators may prevent a particular IP address from trying more than a predetermined number of password attempts against any account on the site.

Reverse brute-force attack
In a reverse brute-force attack, a single (usually common) password is tested against multiple usernames or encrypted files. The process may be repeated for a select few passwords. In such a strategy, the attacker is not targeting a specific user.

See also
 Bitcoin mining
 Cryptographic key length
 Distributed.net
 Key derivation function
 MD5CRK
 Metasploit Express
 Side-channel attack
 TWINKLE and TWIRL
 Unicity distance
 RSA Factoring Challenge
 Secure Shell

Notes

References

External links
RSA-sponsored DES-III cracking contest
Demonstration of a brute-force device designed to guess the passcode of locked iPhones running iOS 10.3.3
How We Cracked the Code Book Ciphers – Essay by the winning team of the challenge in The Code Book

Cryptographic attacks
암호학에서 무차별 대입 공격()은 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 것을 의미한다. 대부분의 암호화 방식은 이론적으로 무차별 대입 공격에 대해 안전하지 못하며, 충분한 시간이 존재한다면 암호화된 정보를 해독할 수 있다. 하지만 대부분의 경우 모든 계산을 마치려면 실용적이지 못한 비용이나 시간을 소요하게 되어, 공격을 방지하게 한다. 암호의 '취약점'이라는 의미에는 무차별 대입 공격보다 더 빠른 공격 방법이 존재한다는 것을 의미한다.

대칭키 암호의 경우 암호에 사용된 키를 알아내면 암호화된 정보를 복원할 수 있고, 여기에서 사용한 키 길이에 따라 무차별 대입 공격의 최대 소요 시간이 정해진다. 암호화 키가 n비트일 경우 가능한 값은 최대 가지가 존재한다.

사용되고 있는 대부분의 암호체계는 보통 수학적 복잡성에 기반을 두고 있고 가역적이기 때문에 언젠가는 문제가 풀리게 된다. 가장 강력한 암호체계중 하나로 불리는 RSA의 경우 문제풀이에 천문학적인 시간이 소요되므로 사용되고 있지만, 컴퓨터의 발전에 따른 처리시간의 단축으로 인해 단시간 안에 해독될 가능성이 있다는 의견이 제시되기도 했다. 반면 양자암호의 경우 수학적 복잡성이 아닌 비가역적인 물리학적 자연현상에 기반을 두고 있어서 앞선 다른 암호체계같은 수학적 접근이 불가능하다

2009년 기준으로 128비트 이상의 키는 안전하다고 평가된다. 64비트 이하의 경우 실제 무차별 대입 공격이 성공하였다. 예를 들어, 56비트를 사용하는 DES의 경우 약 하루 안에 전체 키를 대입하는 하드웨어가 1999년에 공개되었다. 64비트 키를 사용하는 RC5의 경우 Distributed.net이라는 분산 컴퓨팅 프로젝트에서 해독한 사례가 있다.

사용자 암호와 같이 암호가 특정 패턴을 이루고 있을 경우에는 대입해야 할 값의 범위를 크게 줄일 수 있다. 이 경우 사전의 단어를 조합하여 대입하는 사전 공격이 사용된다. 그러므로 암호의 패턴을 불규칙적으로 하고 자신의 개인정보와 연계되지 않도록 하는 것이 좋다.

2017년에는 영국과 스코틀랜드 의회가 무차별 대입 공격의 피해를 보았고, 1년 뒤에는 북아일랜드 의회를 대상으로도 비슷한 공격이 일어났지만 성공하지 못했다. 다음 해에는 캐세이 퍼시픽(Cathay Pacific) 항공이 무차별 대입 공격을 받았는데, 영국 데이터 감독 기관은 충분한 예방 수단을 두지 않았다는 이유로 캐세이 퍼시픽에 50만 파운드(약 63만 달러) 벌금을 부과했다. 광고 차단 서비스인 애드 가드(Ad Guard) 역시 무차별 대입 공격을 받은 이후 모든 사용자를 대상으로 강제 비밀번호 재설정을 했다.

소수를 이용한 RSA 암호화 방식 
저장된 인증 정보의 비밀번호가 길고 암호화 수준이 높을수록 이 공격이 성공하기 위해 필요한 시간과 컴퓨팅 성능도 높아진다. 따라서 이런 방법으로 공격이 사실상 불가능한 수준까지 무차별 대입 공격의 효과를 낮출 수 있다.

컴퓨터 과학자들은 이 시스템을 더욱 발전시켜서 소인수 분해 방식(prime number factorisation) 하에서 적용 가능하게 만들었고, 이름을 RSA Cryptography System으로 바꾸었는데, RSA는 세명의 과학자의 성을 딴 것이다. RSA 암호화 시스템은 순식간에 소수를 이용한 암호기술의 대표로 떠오르게 된다.

RSA는 1978년에 매사추세츠 공과 대학(MIT)의 리베스트(R. Rivest), 샤미르(A. Shamir), 아델먼(L. Adelman)이 공동으로 개발했기에 그들 이름의 앞 글자를 따서 붙인 이름이다. RSA 암호는 큰 수의 소인수분해에 많은 시간이 필요하나 소인수분해의 결과를 알면 원래의 수는 곱셈으로 간단히 구해지는 사실에 바탕을 두고 있다.

BB84 프로토콜

BB84 프로토콜 

  이 문단은 C. H. Bennet과 G. Brassard가 1984년 IEEE International Conference on Computers, Systems, and Signal Processing에서 발표한 《Quantum Cryptography: Public key distribution and coin tossing》논문과 Bouwmeester, Dirk, Artur K. Ekert, Anton Zeilinger가 저서한 Springer社의 《The physics of quantum information :quantum cryptography, quantum teleportation, quantum computation》을 토대로 작성했다.  

Chapter 2. Quantum Cryptography p. 15

1984년 C. H. Bennet과 G. Brassard가 양자암호에 대한 논문을 발표하면서 같이 제안한 양자암호 통신 프로토콜이다. 송신자(엘리스)와 수신자(밥) 사이에 OTP를 생성하는 프로토콜이며, 표와 같이 0비트의 상태를 나타내는 편광 2가지와 1비트의 상태를 나타내는 편광 2가지를 정의 한 다음 십자필터와 대각필터를 통해 측정하게 된다. 이 프로토콜을 통해 엘리스와 밥은 임의의 난수를 생성할 수 있으며, 중간에 도청자(이브)가 난입하여 정보를 가로채려는 시도를 해도 정확한 정보획득이 어려울뿐더러, 신호가 왜곡되어 이브의 존재가 드러나게 된다. BB84 프로토콜의 전체적인 흐름은 다음과 같다.

 엘리스가 임의의 비트를 생성한다
 비트를 전송할 편광신호로 변환하기 위해 필터를 하나 선택한다.
 필터에 대응되는 편광신호를 생성하고 양자채널로 보낸다
 밥은 측정하기 위한 편광필터를 임의로 선택한다.
 선택한 편광필터로 값을 측정하여 보관한다.
 엘리스와 밥은 퍼블릭 채널을 통해 같은 필터를 사용했는지 여부를 검증한다.
 같은 필터를 사용한 비트에 대해서만 보관하고 서로 다른 필터를 사용한 비트는 제거한다.

이와같은 과정을 거치면 표처럼 엘리스와 밥은 0101이라는 같은 값을 공유하게 되며 이것을 비밀키로 활용하게 된다.

같이 보기 
 키 클러스터링

각주 

암호학