Talk:Brute force attack

Missing image Key-crypto-sideways.png WikiProject on Cryptography

This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography in the 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.

Template:CryptographyReader

	Pending tasks for [[Template:Articlespace:Brute force attack]]: (https://academickids.com:443/encyclopedia/index.php?title=Talk:Brute_force_attack&action=purge)	edit (https://academickids.com:443/encyclopedia/index.php?title=Talk:Brute_force_attack/to_do&action=edit) - watch (https://academickids.com:443/encyclopedia/index.php?title=Talk:Brute_force_attack/to_do&action=watch) - purge (https://academickids.com:443/encyclopedia/index.php?title=Talk:Brute_force_attack&action=purge)
	Talk:Brute force attack/to do

Missing image Cscr-former.png Former featured article candidate

This article is a former featured article candidate. Please view its sub-page to see why the nomination failed. For older candidates (where the individual nomination does not exist) please check the archive. Once the objections have been met you may resubmit the article for featured article status.

Contents

1 Ciphers proved secure? 2 Brute force attack vs Key size 3 Two plaintexts per ciphertext? 4 Theoretical limits

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)

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 <math>kT<math> where <math>T<math> is the absolute temperature of the system and <math>k<math> 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).