Talk:Brute-force attack/Archive 1

Archive 1

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)

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)

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)

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)

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?— Preceding unsigned comment added by 164.58.224.236 (talk) 18:42, 14 February 2007 (UTC)

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

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)

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)
  • See One-time pad and XOR cipher. — Matt Crypto 08:09, 2 March 2006 (UTC)
• Thanks buddy! HighInBC 18:40, 2 March 2006 (UTC)

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)

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)

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)

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 2¹²⁸ 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)

GA Reassessment

This discussion is transcluded from Talk:Brute force attack/GA1. The edit link for this section can be used to add comments to the reassessment. In order to uphold the quality of Wikipedia:Good articles, all articles listed as Good articles are being reviewed against the GA criteria as part of the GA project quality task force. While all the hard work that has gone into this article is appreciated, unfortunately, as of August 14, 2008, this article fails to satisfy the criteria, as detailed below. For that reason, the article has been delisted from WP:GA. However, if improvements are made bringing the article up to standards, the article may be nominated at WP:GAN. If you feel this decision has been made in error, you may seek remediation at WP:GAR.

• This article is almost completely unreferenced, and therefore fails criteria 2b of the good article criteria. In addition, there has been a citation request in the article since November 2007. --Malleus Fatuorum (talk) 21:30, 14 August 2008 (UTC)

How many nuclear reactors?

This section is in definite need of a citation or explanation. If the model assumed is that we must use irreversible computation to flip through all 2^128 keys, then the operations required will be 2^128 - 1 bit flips, which corresponds to the energy of 30 GW-years as noted below if we assume the operation occurs at near room temperature 300K. Whether or not this model is appropriate needs further citation or explanation, but regardless the math is off by two orders of magnitude and needs to be corrected. I am changing the text to reflect this calculation and leaving the request for citation intact.

Bkessler (talk) 20:28, 29 July 2008 (UTC)

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)

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 $10^{18}$ 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)

No, not at all. Such calculations are not standard. Most cryptographers avoid making any long term predictions. Who can seriously claim to know how computers look like in 50 years from now? Wikipedia should also follow this model. Rather than making silly predictions with arbitrary assumptions it would be much better to state known and verifiable facts. E.g., a more comprehensive list of brute force searches completed so far. 85.2.10.181 (talk) 21:58, 30 July 2008 (UTC)

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(2^{n/2})$ time. 85.2.74.231 16:21, 17 August 2007 (UTC)

I think the more appropriate algorithm for brute force attacks by a quantum computer is Shor's factoring algorithm which is relevant to breaking RSA and has a computational complexity $O((\log {N})^{3})$ where N is the size of the integer to be factored. I don't know exactly how this translates into breaking a specific length RSA key Bkessler (talk) 17:28, 5 August 2008 (UTC)

Move?

The following is a closed discussion of the proposal. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the proposal was no concensus Anthony Appleyard (talk) 17:51, 13 April 2009 (UTC)

• brute force attack → Brute-force attack — Correction of hyphenation (compound adjective). — radiojon (talk) 17:21, 7 April 2009 (UTC)
• Was a {{db-move}}, queried in an edit comment at 21:20, 31 March 2009 by User:R'n'B (speedy declined; no notice at WP:RM or on article talk page, potentially controversial move): Anthony Appleyard (talk) 22:26, 7 April 2009 (UTC)
• Where is the literature that shows that 'brute-force attack' is in common use? I have never seem this form used and there is no reason for WP to try to improve on the language in use. Hmains (talk) 02:28, 13 April 2009 (UTC)

The above discussion is preserved as an archive of the proposal. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

Symmetric ciphers

On November 18 2009 the whole section on symmetric ciphers was deleted. Was this vandalism or is there a reason why this section did not belong here? 213.3.124.197 (talk) 10:18, 29 December 2009 (UTC)b

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.

 —Preceding unsigned comment added by 204.50.113.28 (talk) 18:20, 11 April 2008 (UTC) 

The attack you describe on the system you describe will give you the same subset of strings that have a matching MAC if all you have to work with is the MAC. If the data being protected by a OTP has the plaintext appended to it it also is not protected by the OTP. Just because it is possible to append something breakable to the OPC-encrypted ciphertext, that doesn't imply that the OPC can be broken.

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) 

Not true. If you see the results "Gh%43&jsdh$4Jd", "Grw7vFj$dswEJ#" and "Attack at dawn", you can figure out which is the real message. OTP also gives you "Attack at Dusk", "Do not attack!", "I like puppies" and all other possible strings from aaaaaaaaaaaaaa to ZZZZZZZZZZZZ. Ciphers with keys that are smaller than the text do not.66.53.222.254 (talk) 10:07, 7 February 2010 (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)

This article needs a re-write

This article filled with largely undefined, largely unexplained jargon.

I am an attorney-CPA. If the average person were to come into my office with a notice from the Internal Revenue Service and wanted to know what the notice meant, I would not respond with something like "you have a section 6321 problem with respect to your assets because you failed to pay the assessment demanded in a section 6212 notice within the period prescribed in Reg. 601.103, after having failed to file a petition within the statutory period under 6213 as prescribed in the 'stat notice' you received." The average person is not going to know what I'm talking about. And if I were to re-write the federal-tax-law-related articles in Wikipedia to target them to an audience of tax lawyers, the articles would become largely useless to general Wikipedia readers.

The article as currently written appears to be targeted at people who are knowledgeable about cryptography, etc. If the basic principles of the mind-numbing intricacies of U.S. federal income tax law and Einstein's Special Theory of Relativity can be broken down and explained in layman's terms in Wikipedia, I know there is someone out there with an expert knowledge of the subject of brute force attacks who can modify this article accordingly. Famspear (talk) 18:33, 1 September 2010 (UTC)

How would you suggest specifically improving the article? Have you considered helping? If you take a look at some of the medical articles on wikipedia (e.g. Coeliac disease), the contributors there argue that these articles' value comes from them not being watered down. Socrates2008 (Talk) 22:00, 1 September 2010 (UTC)

I think Famspear's comment is fair. An alternative could be:

In cryptography, a brute force attack is a strategy used to break the encryption of data. It involves checking all possible keys until the correct key is found. In the worst case, this would involve traversing the entire search space.

which would provide the key point in plain English. --h2g2bob (talk) 23:44, 1 September 2010 (UTC)

Something like what h2g2bob is saying. While I have strong writing and editing skills, and have written articles (on taxation) that have been published, I know nothing about this particular topic. Because of the nature of the topic, I think to be fair it needs someone who has at least some knowledge of the subject. I might do more damage than good on this one. Famspear (talk) 00:40, 2 September 2010 (UTC)