Talk:Brute force attack

From Wikipedia, the free encyclopedia

Good article Brute force attack has been listed as one of the Engineering and technology good articles under the good article criteria. If you can improve it further, please do. If it no longer meets these criteria, you can delist it, or ask for a reassessment.
This article is within the scope of Computing WikiProject, an attempt to build a comprehensive and detailed guide to computers and computing. If you would like to participate, you can edit the article attached to this page, or visit the project page, where you can join the project and/or contribute to the discussion.
Good article GA This article has been rated as GA-Class on the quality scale
High This article has been rated as High-importance on the importance scale
WikiProject on Cryptography This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography on Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.
WikiReader Cryptography It is intended that this article be included in WikiReader Cryptography, a WikiReader on the topic of cryptography. Help and comments for improving this article would be especially welcome. A tool for coordinating the editing and review of these articles is the daily article box.
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Good article GA rated as GA-Class on the assessment scale
High rated as High-importance on the assessment scale
To-do list for Brute force attack: edit · history · watch · refresh
  • Discussion of TWINKLE and TWIRL
  • Add an overview of suggested hardware designs for key search.
  • Discuss hash collision search; MD5CRK
  • Discuss Time-memory tradeoffs
  • Briefly survey the cracking challenges (RC5, DES etc)
  • Types of attacks
Priority 3  

Contents

[edit] Ciphers proved secure?

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 been proved to be so for very few ciphers...

Has any cipher been proved secure in this sense? Such a proof of security would trivially imply P != NP (in fact even the much weaker assertion of the existence of a trapdoor function would suffice to imply P != NP). Unless I'm majorly missing something, the wording should be changed. -- Arvindn 18:26, 23 Jul 2004 (UTC)
Arvindn, What I think the wording meant to imply was "Shannon maximally difficult to break", not unconditionally secure. You're right that the term is sloppily used, and that's unsatisfactory, but the alternative is a lot of contingent hedging every time the idea is mentioned or the virtues of one time pads are discussed. Hard to know quite how to handle this in a way suited to WP (and those who don't like complication or too many words, however precise). I've been trimmed several times when I attempted to do something like that. ??? Ideas? ww 20:41, 23 Jul 2004 (UTC)
OK, I see your point. I assume by 'Shannon' above you mean OTP. The security notion here is, you keep the key length fixed, and allow the plaintext/ciphertext to be arbitrarily large, and see if breaking the cipher is as hard as brute force. So the OTP doesn't qualify. Is it possible to phrase that in a not-too-verbose way? Would "no general purpose cipher has so far been proven secure" be OK? Arvindn 03:12, 24 Jul 2004 (UTC)
Arvindn, I think I'm missing the import of your observation above. What I thought was awkwardly intended was Shannon's proof that the effort for breaking OTP is maximal, and his notion that that's the best one can do (added " to bring this out some). Hence, effective unbreakability in that limited sense. But I must admit I'm confused, so I'm can't see that your proposed wording is apt here. Help? ww 17:11, 24 Jul 2004 (UTC)
The confusion about the other person's meaning is mutual, I assure you :) What I was trying to say was, if we explicitly throw in the restriction that key length should be fixed, thereby eliminating the OTP, then there aren't any ciphers that we can prove secure. The restriction is a natural one, since a brute force attack doesn't make any sense when key length is unbounded.
If I've still not managed to communicate, I suggest we leave it at that. Arvindn 18:20, 24 Jul 2004 (UTC)
Arvindn, Now I see what you meant. Thank you. But I would observe that, in rather remote theory, a brute force attack is still possible against a one time pad. Any particular message (attack at dawn) will produce via a one time pad a cryphertext of the same length (modulo padding or some such). One may try to brute force substitute in that message. The combinatorics are brutal, but will -- eveeeentually -- produce the original plaintext -- amongst many many others. Your point is certainly true with the restriction you note, but may have reduced significance since, at least for the one time pad, 'keys' are of variable length. ww 15:09, 27 Jul 2004 (UTC)

[edit] Brute force attack vs Key size

I think we need to be careful not to discuss various key lengths in too much detail within this article; of course, it's relevant, and a short discussion is quite appropriate, but we have a separate article (key size) for an in-depth treatment. I think we can should here concentrate on various brute force designs, algorithms and technologies. — Matt Crypto 15:17, 12 Dec 2004 (UTC)

[edit] Two plaintexts per ciphertext?

What about ciphers that return two or more plaintext given one ciphertext depending on the key?

Hmm.. explanation is definitly needed about what I mean.

Lets start with the shrinking generator but put the ciphertext instead of the leftshifting register A.

We let the initial condition of the leftshifting register S be the key of this cipher.

So (probably) two keys, a and b, will produce two streams from leftshifting register S that if XORed together produces a stream of zeros.

Now we use key a to encrypt some data we want to keep private and key b to encrypt some data which we want to make a third-party think that we want to keep priviate.

So how does a third-party know which key yields the data we wanted to keep private? ;-) — Zarutian 01:54, 22. april 2005 (UTC)

I think the above is called Deniable_encryption. — Zarutian 15:52, 22. april 2005 (UTC)

[edit] Theoretical limits

The thermodynamical assumptions in the "Theoretical limits" section are wrong (and probably taken from a gross mistake in Schneier's "Applied Cryptography", 2nd Ed., p.157). Let me elaborate a little bit: setting or clearing a single bit indeed requires a minimum amount of energy not less than kT where T is the absolute temperature of the system and k is our old friend, Boltzmann's constant. However, complementing a bit (what you will be doing most of the time) is a reversible operation and has no minimum required energy whatsoever. We will certainly need an entropy increase for copying the answer, but as you may see, that implies that energy requirements will be linear on key's length, not exponential.

PS: I'm not a registered user at en.wikipedia, but you may contact me if you wish at the Spanish language wikipedia, here. Regards, Cinabrium, currently 200.59.66.253 01:09, 30 May 2005 (UTC).

[edit] Translations of "brute force" and "brute force attack"

Icelandic: kembileit and kembileitar árás.

(I simply dont know where to put stuff like this) — Zarutian 02:02, 21. july 2005 (UTC)


[edit] Asymmetric encryption

This section seems to define things like GNFS factorization attacks on RSA and birthday-based discrete log attacks on elliptic curve systems as brute force attacks. I would never have thought of these attacks as brute force - could someone provide a cite that suggests that the term is appropriate in these instances? — ciphergoth 09:26, 27 February 2006 (UTC)

[edit] we can say this with a sentence about the OTP

What is OTP? If you are removing my contribution on the premise that another sentence would be better then where is this sentance? I see no need to remove my contribution unless you can replace it or have some kind of critisism. Please get back to me. HighInBC 02:31, 2 March 2006 (UTC)

  • It just occured to me that OTP is One Time Page? Did I get that right? While I understand the mechanics of XOR, and know that it is a OTP system, I don't understand it enough to write about it. It certainly needs mention here though, as it is the exception to the type of attack. HighInBC 06:45, 2 March 2006 (UTC)
  • Thanks buddy! HighInBC 18:40, 2 March 2006 (UTC)

[edit] Number of custom chips contradiction

There is a difference of 10x between the EFF DES cracker and Brute force attack image capations each indicating '1800' and '18,000' chips respectively. When searching 1800 appears to be the correct amount, but it would be good to confirm.--ShaunMacPherson 16:54, 15 July 2006 (UTC)

[edit] How many nuclear reactors?

So I think the section saying how many nuclear reactors for 100 years would be needed to power breaking a 128 bit key needs revisiting. In particular, we need to make explicit the temperature we are expecting the crack to run at (since the kT limit involves temperature) and we need to make our model of bit flipping more explicit.

I will note that each key iteration need not involve flipping all the bits in the key -- the average is much lower than 128. If you assumed an average of 1 bit erased per iteration (using some sort of ordering in which hamming distance is minimized), I come up with only 3 10GW reactor years of power at 300K.

Ideally, this section should contain enough information that a reader can repeat the actual calculation with ease.


Adding to the above remark, both the physics and the math are wrong. First and foremost, there is a confusion between units of power (watts) and units of energy (watts-hour). Furthermore, the base for the power or energy demand has not been explained. How many miliwatts would a bit-flip take in his/her model? If the author intended, as I guess, to write about energy and we should understand 10GWh, then the math is wrong: a 500MW power plant will deliver 10GWh in 20 hours, not 8 years. If there are no further comments, I will remove the controversial paragraph in a few days. Cinabrium 02:31, 5 June 2007 (UTC).
Actually, there was no confusion. Watts times seconds equals joules, so units of energy can be expressed as gigawatts of power over years. Second, the power for a bit flip WAS explained: it is ln(2)*k*T, where ln(2) is the natural log of 2, k is the Boltzmann constant, and T is the temperature in kelvin. Your removal was incorrect.
As for the accuracy of the calculation itself, I did a back-of-the-envelope, and it seems like it may be off somewhat, but not too badly. My main problem is that I don't know how many bits on average get changed on every increment in counting from 0 to 2^128. Assuming only one bit changed, I get something like the same order of magnitude, so I'm leaving the figure for now, but a more accurate calculation would be good. --Pmetzger 00:18, 25 October 2007 (UTC)
Incrementing a counter by 1 is a reversible operation and hence it seems that Landauer's principle does not apply. Similarly, encryption is reversible and hence Landauer's principle does not need to apply there either. It seems that the whole discussion is plagued by a little too many assumptions and a reliable source is necessary. 85.2.105.236 15:56, 14 November 2007 (UTC)
Many computations are reversible in principle. However, effective designs to do reversible computation in practice for things as complicated as brute force cracking of ciphers are not currently known. There is also the not entirely small matter that the closer to reversibility you get, the slower you most likely get because non-adiabatic operations are almost certainly irreversible. Unless there is better evidence that reversible calculation can be used here in practice, I think the content should stand. Pmetzger (talk) 16:42, 20 April 2008 (UTC)
I'd be interested to learn more about the reasons why reversible computing is hard to achieve. If you have references supporting your claim, would you mind adding them to the reversible computing article. 85.2.112.20 (talk) 16:31, 26 April 2008 (UTC)

[edit] Successful bruteforce

How does one go about successful bruteforce?? I guess this doesn't depend on the encryption techniques all that much but the actual key being used, so if i put "password" as my key it will be bruteforced in seconds but if i put a random key like this "-+;>,AdñÇcQ┘Y578?~&Bh+2}ûí."kïM#d" , wouldn't that be theroritcally impossible to crack even by bruteforce?? —The preceding unsigned comment was added by 75.15.184.217 (talk) 20:05, 8 January 2007 (UTC).

It could still be cracked. The cracking program would have to attempt to decrypt the data (or match the hash as is usual for passwords) with every possible password, including your random one. If the data is decrypted or the hash matches, the attack was successfully. Thus, brute force attacks are guaranteed to be successful, as long as you know what cypher or hash algo you are brute forcing. —Preceding unsigned comment added by Mojo-chan (talk • contribs) 15:44, 2 January 2008 (UTC)

[edit] brutus

I recently found a program called Brutus. It's a Brute Force Attack program, and I have no idea how to use it. Is there any links that anyone knows of?

[edit] Quantum computers used in brute force attacks

I brought up quantum computing being used to crack 128 bit key lengths. Even if a quantum computer is developed, how would it fare in the cracking of a 128 (or evan a 256) bit key? (compared with today's digital computing).

Or would such key lengths be so complex that they they are 'future-proof' even against quantum mecanical brute force attacks? Hellcat fighter 15:54, 17 August 2007 (UTC)

→ I think it's a really interesting question, but it may be hitting Wikipedia:What Wikipedia is not#Wikipedia is not a crystal ball territory. If you have references that would make a great addition, but I don't think it's there yet. Mmernex 16:01, 17 August 2007 (UTC)

Finding a key on a quantum computer using Grover's algorithm may be regarded as the equivalent to a brute force search on a classical computer. Breaking an n bit key with this algorithm requires O(2n / 2) time. 85.2.74.231 16:21, 17 August 2007 (UTC)

[edit] Mathematical nonsense

There are a few things on this page that simply don't make sense. Firstly, it is kind of pointless to convert the time it would take to break a 256-bit cryptosystem on an hypothetical computer into a 52-digit number of years, since it is already difficult to define a year with more then 5-7 digits accuracy. Btw, the given integer is even less accurate, because the editor who added this number was apparently unaware of the existence of leap years. Secondly, the section "Sample of breaking time" is equally funny, with the assumption of base-36 keys and an attacker that can only break 100000 keys per second. 24.228.51.109 19:45, 4 September 2007 (UTC)

There is a good reason for leaving the 52 digit number of years (which I believe may have been my calculation): it provides a better sense to a person who does not understand exponential notation of how hard the problem is. Given the fact that the source of the calculation is quite obvious, there is no reason to worry that a false impression of accuracy is being given. (I agree that the "breaking time" stuff was silly but that wasn't mine and someone else has already removed it.) --Pmetzger 00:25, 25 October 2007 (UTC)
I wouldn't be too proud about these calculations, because they are actually incorrect (hint: leap year). Publishing information that one cannot know is a 'no-no' in science. People, who don't understand exponentials will probably also have problems to grasp the significance of big numbers. But the really big question is whether a device that can break 1018 keys is a good estimate for an upper bound on what can be built. I seriously doubt it is. Rather than trying to predict the future, it seems better to me to just report on the size of brute force searches done so far. 85.0.108.181 10:02, 14 November 2007 (UTC)
I see nothing wrong with the calculations, and it is standard in the actual cryptographic literature to discuss estimates such as this. I will repeat on the "precision" that there is again nothing wrong with it as a reader will not be deceived -- the source of the calculation is clear and obvious.Pmetzger (talk) 16:45, 20 April 2008 (UTC)

[edit] Misnomer

The biggest problem with this article is that its title is a misnomer. A commonly used one but a misnomer nevertheless. The technique described is not brute force. In fact it uses no force at all, rather it simply tries all possibilities to, in effect, chip away slowly but surely until the final solution is revealed. The proper term for this type of attack is "exhaustion". HughNo (talk) 18:04, 29 February 2008 (UTC)

This name of the concept is widely known in papers on cryptography (for instance, Applied Cryptography By Bruce Scheneir iirc) Zarutian (talk) 00:29, 14 March 2008 (UTC)
The term brute force does not necessarily mean physical force. In particular 'brute force' is used both in computer science and mathematics to describe exhaustive methods (see brute force search or proof by exhaustion). So the crypto community does not misuse the term and the title is not a misnomber. 85.2.13.92 (talk) 09:16, 16 March 2008 (UTC)

[edit] Unbreakable codes?

The section that says OTPs cannot be broken with brute-force attacks seems misleading. If the data being protected by a OTP has some kind of MAC to ensure proper decryption, then a brute-force attack will not find all 100-character strings, but only the subset of strings which have a matching MAC.

If an encryption protocol uses a C-bit MAC to verify a message M bits long, then there are 2^(M-C) M-bit strings which appear to be correct. Likewise, if a K-bit key is used to encrypt the message, then there are 2^K possible decryptions of the M-bit cyphertext. There must be at least one string in the intersection of possible decryptions and correct-appearing strings (the original plaintext). Depending on the sizes of M, C and K, there may be other strings in this intersection. The exact size of the intersection depends on the actual message and keys, but one (who is better at probability and cryptanalysis than I am) can compute the probability of a given size of intersection depending on M, C, and K. However, as C gets bigger, the intersection set gets smaller, and we can assume with a "large enough" C the intersection contains only the original plaintext.

The important aspect of the OTP is that M = K (your key is as long as your message). But what makes the brute-force attack impossible is the assumption that in a OTP, C = 0 (there is no MAC). If you add a reasonable MAC, then you can break a OTP, using only 2^(M-1) tries on average.

I don't think that C = 0 is actually required for an OTP algorithm, so I don't think that an OTP is any more invulnerable to brute-force attacks than any other algorithm. Any encryption protocol that does not use a MAC to verify the decryption is equally invulnerable to brute-force attacks, since there is no way of knowing which key is the correct one: all keys produce a valid-appearing result. —Preceding unsigned comment added by 204.50.113.28 (talk) 18:20, 11 April 2008 (UTC)

No rational person would put a MAC on a OTP encrypted message OUTSIDE the encrypted region. If the MAC is itself encrypted by the OTP, an attacker clearly gains nothing as he has no way to know which of all possible MACs is the true MAC. However, even so, I will note that even if the MAC is outside the OTP encrypted region, all possible reasonable messages with the same MAC will appear to be the correct decryption with equal probability. If you have a message of significant length, say over 10kB in length, any given MAC will correspond to a huge number of texts -- even a vast number of seemingly sensible human created texts. The problem remains much like that of trying to find the "correct index" in Borges' Library of Babel even if the space of possible messages is now drastically lowerPmetzger (talk) 20:09, 11 April 2008 (UTC)

[edit] No need for Citation Needed on Theoretical Limits

I think there is no need for "Citation Needed" on the theoretical limits section as the section does not describe any information that is not clearly verifiable using the calculations presented in the section itself. What would such a citation verify, that 2^256 is indeed the listed number or something similar? Pmetzger (talk) 16:48, 20 April 2008 (UTC)

Calculation would not need any references as they can be easily verified with a calculator. However, the section theoretical limits currently contains several claims and assumptions of unknown origin. E.g. the claim that counting up to 2128 needs at least 10 Gigawatt for 100 years makes the implicit assumption that such a task requires approx. 30\cdot 2^{128} irreversible operations. It is not explained where the factor 30 comes from. It further makes the implicit assumption that this device runs at temperature of 300K. Finally, since the theoretical limits are not really theoretical limits because of reversible computing, we need a reference explaining why these computations still might be useful. 85.2.112.20 (talk) 16:18, 26 April 2008 (UTC)