Talk:Brute force attack

Origin

Much of this is taken from The FreeS/WAN docs [1] which I have permission User_talk:Sandy_Harris/Permission to re-use here, but I have rewritten quite a lot so I do not think it needs tagging as an external article at this point. Editors care to comment?

More generally, can others improve this?

Another dimension to key strength

Something not often considered in crypto for the civil sector, but often examined in depth in the military and intelligence areas, is not just how long a brute force (or more skilled) attack would take to yield the plaintext, but how long a period of protection is needed?

A classic example is that if you can hit a target with artillery in 5 minutes, but it would take the intended target 15 minutes to move out of range, the main reason to encrypt at all is the equivalent, I suppose, of giving the condemned a blindfold. Now, there might be a rationale for using encryption with resistance just slightly longer than the period between unit code name changes.

On the other hand, espionage traffic really should be protected for decades, because there are literally families of spies.

It happened that I was on the U.S. Federal Telecommunications Standards Committee at a time when one of the military members wanted the option for a longer checksum on -- IIRC -- HDLC. They said it was needed to protect nuclear command and control, and I inquired when the U.S. government had decided that the risk of accidental nuclear war was unacceptable at 16 bits but acceptable at 32 -- or maybe it was 32 and 64. My observation was not appreciated.

For things like money and securities trading, you do need strong protection until the trades are made, at which point the information is public. If the typical period between placing the order and making the sale is 15 minutes, how quickly would you have to break it and give it to another trader who could exploit the information?

I've had some generically weird experiences in clinical computing. In one case, the doctors insisted on very strong crypto (for 1966) for hard copies of lab charts they would leave unattended in hard copy. In another case, I became extremely frustrated with a client, who wanted strong security for an in-hospital hospital system on which an authenticated physician could prescribe narcotics. Trying for a reduction ad absurdum, I drew up a system that was generally more rigorous than used to order the launch of an ICBM. To get to the audit file, you had to have two people, at two locations, monitored by remote video links to two different guard centers, turn keys and enter their codes within 10 seconds of one another.

The client loved it. I went out and beat my head against the wall until it really felt good to stop.

Howard C. Berkowitz 23:51, 4 August 2008 (CDT)

In many cases, though, there is no extra cost to use better crypto. Stuff I've written on the question of using short keys or weak ciphers for some data is here [2]. It is far too polemical for an encyclopedia, and ignores issues like running out of random numbers or problems that may arise in managing larger keys, but I think it is basically correct.

In the artillery case, you might decide to go without cypto because it is faster or cheaper, or because simpler systems are more reliable. However, if you do decide to use crypto, it is likely worth using something strong. This blocks things like the enemy collecting a bunch of your fire orders so he can analyse your tactics and look for flaws. Sandy Harris 08:32, 5 August 2008 (CDT)

The point about building up patterns is well taken. In the case of artillery, since, at least in the U.S. and NATO, the system of coordinates and firing orders is very standardized and quite public. I am not going to try to rationalize the U.S. making the bombing of Cambodia TOP SECRET during the Vietnam War, since the surviving targets clearly knew they were being bombed. Oh well...it kept it mostly secret from the Congress and the voters.

You have set up a good example for the more general topic of communications intelligence, subset direction finding. It would be wise for whoever is being shelled to plot the locations of the firing positions, and perhaps work out a movement pattern, which is definitely the case with guerillas firing rockets and mortars. Noting the exact times is also relevant, because a security person might be able to correlate actions on the target side when they are fired on — and maybe more important, not fired upon. For example, they might observe that if they transmitted on HF at a power of 10 watts, it always drew fire, but nothing seemed to happen when they talked on UHF at 100 milliwatts. In other words, communications security, or electronic warfare#electronic protection, was a function less of crypto and more of power and frequency.

Since the direction in military crypto is greater automation, using stronger crypto is a reasonable direction. In practice, however, when the methods were pencil-and-paper or electromechanical (e.g., Enigma machine), the crypto clerks would try to save work and might do things that very much increased vulnerability.

Howard C. Berkowitz 19:40, 5 August 2008 (CDT)

Delete text?

I would like to delete most of Brute_force#Algebraic_attack, leaving only the first sentence and a link to Block_cipher#Non-linearity which covers the same ground more thoroughly. Sandy Harris 10:50, 26 October 2008 (UTC)

Did that, except I create a new algebraic attack article & made both this and Block_cipher#Non-linearity link to it. Sandy Harris 11:08, 2 November 2008 (UTC)

After more coffee, I'm going to take some paper and draw a little map. Chris has some quick diagramming software that may be better for the purpose.

What I'm trying to visualize is the relationships among these articles, which have places in multiple hierarchies. Very roughly, there's a cryptography/cipher/cipher type hierarchy (for both 1-way and 2-way communication), and there's a cryptanalysis hierarchy, which to some extent is subordinate to information security. In turn, cryptanalysis helps judge strength of crypto, while the problem analysis part of infosec helps determine how much strength is appropriate.Howard C. Berkowitz 12:59, 2 November 2008 (UTC)

In good shape

I'm comfortable with this. One minor thing -- might want to convert the embedded EFF link either to an external link or to an inline citation.

As I remember, I only did copy edits; I don't know if that is a bar to my being the only approver. I'm willing to nominate it. Howard C. Berkowitz 01:39, 21 March 2009 (UTC)

Since we have both a wikilink to our EFF article and a citation for the EFF-published book, I think we can just drop the link to the EFF website. It is not central to this discussion. Sandy Harris 06:47, 21 March 2009 (UTC)

Makes sense. Do you remember, without going through the histories, if I did more than copy edit? I don't think so. Ideally, it would be good to get another Editor to co-nominate. Is there anyone in Mathematics? Again, strong Related Articles helps a lot. EFF can move to External Links. Howard C. Berkowitz 16:08, 21 March 2009 (UTC)

Checking the history, you did only one edit that was not pure copy editing, adding "or there is a weakness in the algorithm. It is not the only attack against a cipher; there are other means including classic analytic cryptanalysis against a sufficiently simple cipher, chosen plaintext attacks, etc." to the end of first paragraph. I then rewrote it and made it a separate paragraph, the current second one. Your point survives, but not much of your text :-) Sandy Harris 05:14, 22 March 2009 (UTC)

The page has only about 60 edits overall, about 5 by you, someone adding the subpages tag, the rest by me. Sandy Harris 05:40, 22 March 2009 (UTC)

Plan for approval

Since this topic applies to telecommunications networks as well as computer systems, and we've been putting general telecommunications under the Engineering workgroup, I added Engineering to the workgroups and nominated it for Approval. Another Engineering editor can make the procedural judgment if my edits were substantive; I don't think they were. If so, then we would need another Editor or two.

We could also add Mathematics. Howard C. Berkowitz 01:26, 23 March 2009 (UTC)

So,... are you going to look for other Editors to join in on approval? Otherwise you're walking a fine line with this one, I think.--Joe Quick 02:43, 24 March 2009 (UTC)

It's tough, Joe. We are just plain short on editors. I've been trying for months to get a Computers editor for several articles of mine. I just don't know of anyone active with expertise in this area. Howard C. Berkowitz 03:18, 24 March 2009 (UTC)

The need for other editors has been discussed before, see Talk:Cryptography#Next_steps.3F for one example. But there are quite a few crypto-related articles that are close to approval, see User_talk:Howard_C._Berkowitz#Approvals.3F for a partial list, and almost the only people active in the area seem to be me as author and Howard (mainly) as editor. If you are an editor with time to look, or know of others, it would be greatly appreciated. Sandy Harris 03:22, 24 March 2009 (UTC)

Agreed. Sandy is right that there is a legitimate backlog; I picked this one because I regarded it as least controversial. I made more and more of a point of not doing direct collaborative editing so I could...ummm...remain chaste? to be an approving editor. Howard C. Berkowitz 03:48, 24 March 2009 (UTC)

From what I understand of this and other related articles, there is a lot of math that goes into encryption and attacks against encrypted material. But maybe less math for this particular attack than for others? Would it be appropriate to add the Mathematics Workgroup and recruit editors from there? Joe Quick 14:52, 25 March 2009 (UTC)

It's not an unreasonable place to look, but as I regard this type of attack, it is well named: it uses less mathematical theory to improve the attack than do other methods. Instead, the math is in generating all possible attacks, and then, as much as anything, linguistic and mathematical analysis to know which is the right possible attack.

Mathematics is very appropriate for some cryptography related areas, but some more than others. In some cases, it's more of a computer science than a mathematical approach, because there are subfields of computer science (e.g., computability theory) that consider if a particular computation is feasible in plausible resources, including time. Classic mathematics doesn't look at that constraint. You'll find that computer science departments often have their own variants on mathematics department courses, which have more emphasis on feasibility and less on formal derivations.

(There is an article lurking here on the math vs. CS learning/knowledge approach) I can use lots of math and stat algorithms and understand their applicability without being able to derive them. This is very true in the specific area of cryptography; I can make rational decisions when an algorithm gives adequate protection for an application, but I can't develop a state-of-the-art encryption algorithm. I can take that algorithm and develop a very state-of-the-art tool that uses it. Howard C. Berkowitz 15:10, 25 March 2009 (UTC)

Toward Approval

These edits by Howard were mostly copyedits with the exception of the one that Sandy mentions above (that he later edited and made into a new paragraph). I think the spirit of the one editor approval is to assure that an editor cannot approve his/her own work. As Sandy rewrote and obviously approves of Howards addition, it seems that it is just as likely that he would have written it himself. I think an exception could be made in this instance and approval could move forward on March 29 if there are no objections. I might add that this is as close as I think we should go to that thin line that Joe was talking about, so if you plan to attempt a single editor approval, make your suggestions on the talk page and, if the author wants, they can add them. D. Matt Innis 00:45, 26 March 2009 (UTC)

Well put, Matt. Let's move forward with approval. (If other editors want to join Howard in his nomination, they are obviously still welcome.)--Joe Quick 04:10, 26 March 2009 (UTC)

They are absolutely welcome. There are other crypto articles that may contain some of my content, but I didn't consider this at all something that contains any appreciable direct work of mine. There are others where Sandy is indeed the principal author, but I contributed more specifics either in earlier drafts or on the talk page. Howard C. Berkowitz 04:47, 26 March 2009 (UTC)

I am not an expert in this field by any means. However, I am an engineering editor and I found the article to be very interesting and very will written. Would it be appropriate for me to join in the nomination for approval of this article? Please let me know fairly soon. Milton Beychok 07:13, 26 March 2009 (UTC)

I'd say by all means. Cryptography is, among other things, an area of engineering. Ideally we'd have computer, math and engineering editors all taking a look and helping to improve or approve it. Sandy Harris 11:03, 26 March 2009 (UTC)

Done, I have added my name as a nominator. However, Sandy, to satisfy the valid comment by Daniel Mietchen in the above "Delete Text?" section, would you please create the Bibliography and the External Links subpages ... and then populate them with at least a few books and a few external links? I'm sure you can do quite easily. Regards, Milton Beychok 16:56, 26 March 2009 (UTC)

(Moved from different section into which it had erroneously been put originally). I am not in a position to judge about approval here but would like to comment that the subpages are basically empty, which I do not think appropriate for an approved article in general. --Daniel Mietchen 16:10, 26 March 2009 (UTC)

I've created those sections, but this is my first time for those and I'm not certain I used the right format. Editors please check & adjust or comment if necessary. Sandy Harris 00:15, 27 March 2009 (UTC)

Thank you, Milt. I particularly value your opinion here, as with some specialized engineering articles of my own, because I think that any good engineer should be able to recognize and produce clear writing. When I can follow one of your process descriptions very clearly, I also know full well that I couldn't build the plant; there are areas of chemical engineering implementation that may involve strange acts, under a full moon, so that things don't leak under pressure. One of my computer science professors used to drive me, as a software/network engineer, to distraction, when he'd question why I'd put input checking and documentation into a class project. Clearly, he was not an engineer.

While I may be nutty, I'm not crazy enough to try to adjust the text and jeopardize Approval. My suggestion is that you have the bibliography a little inverted. Put the book bibliographic information as a bullet in the main text, not a footnote, and explain why the book is relevant in some free text.

Rather than refer to the other articles, pull in some of the text. You might very well take some historical perspective on brute force, such as the very common mistake — ENIGMA comes to mind — that overoptimistic people assume that brute force is the main cryptanalytic technique, and Poland and France and Britain could never work through all the ENIGMA keys.

Similar general comments on external links: the valuable ones have a little annotation about why the link is useful, and at least the name of the site, not just a footnote. Howard C. Berkowitz 00:31, 27 March 2009 (UTC)

Sandy:The wiki recommended way of citing books in a "Bibliography" subpage and using bullets is as below. Look at the edit display of this page to see how to use the {{cite book}} template. I would do this for you, but as a nominator I am not allowed to do so.

• Electronic Frontier Foundation (1998). Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design - How federal agencies subvert privacy, First Edition. O'Reilly & Associates, Inc. ISBN 1-56592-520-3.  The Electronic Frontier Foundation (EFF) built a machine called the "DES Cracker" specifically designed to speed up brute force against the Data Encryption Standard. The work was politically motivated, aimed at demonstrating that DES was insecure despite US government claims to the contrary. They published this book and it is avaliable at Cryptome.

• David Kahn (1967). The Codebreakers: the Story of Secret Writing. MacMillan. ISBN 0-684-83130-9.  Gives many historical examples both of brute force attacks and of systems believed secure largely because they could resist brute force but which fell to other attacks.

The "External Links" subpage is for bulleted hyperlinks to external websites using the {{cite web}}templates as below. Look at the edit display of this page to see how to use the {{cite book}} template. Again, I would do this for you, but as a nominator I am not allowed to do so.

• Blaze, M.; W. Diffie, R.l. Rivest, B. Schneier, T. Shimomura, E. Thompson, and M. Weiner (January 1966). Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security. Retrieved on March 27, 2009.

I recommend that you delete this item from the "External Links" subpage because it is redundant to the same info in the "Biliography> subpage.

EFF's DES Cracker was a machine designed and built for a fast brute force attack on the Data Encryption Standard. The book on it, Cracking DES - Secrets of Encryption Research, Wiretap Politics & Chip Design, 1998, by the Electronic Frontier Foundation, ISBN 1-56592-520-3, published by O'Reilly, in online at Cryptome

You can just copy the above citations into the relevant subpages. Sorry, this took me a while. Milton Beychok 03:14, 27 March 2009 (UTC)

Done. Sandy Harris 03:32, 27 March 2009 (UTC)

Clarification: this edit , as explained by Milt above, would be considered a copy edit (since it did not make any content change) and can be performed by an editor of a single editor approval. Everyone is encouraged to look for copy edit issues. The only edits a single approval editor is unable to do is an edit that changes the meaning of the text (content edit). D. Matt Innis 04:12, 27 March 2009 (UTC)

Perhaps a copy edit?

Rather than "Some ASCII characters do not occur in English text; that narrows the possibilities further. Looking at character frequency or looking for English words can reduce it further.", I suggest "Plaintext recognition becomes more efficient when simple rules can be used to reject possible keys. Since some ASCII characters do not appear in English text, a result containing them can be rejected at once. More heuristic rejection rules can use character frequency or word recognition; the rejects can always be reexamined if all better results fail to be useful. " Howard C. Berkowitz 01:58, 28 March 2009 (UTC)

I'm afraid this would cross the line into content edit. A copy edit would not introduce a new idea. The safest thing to do is let Sandy change it if he agrees, and if he doesn't (and you still don't like it) then you can always remove the ToApprove template. That way we know that two of you agree with the content and context of the wording. D. Matt Innis 15:19, 28 March 2009 (UTC)

It's close to the line, but I don't see it as an especially new idea, but a rephrasing of terminology. Sandy is talking about heuristics but not using the term. The rest of the section is reorganizing and rephrasing his ideas. Note that it was not a change to the article itself but a suggestion on how he might rephrase. To me, in a discipline-specific article, suggesting a specific term rather than a free-text description is something that the copy editor on my published books, not just the technical editor, routinely made.

The other comment I make about keyspace reduction definitely would be content.

Nevertheless, I think we are all exploring the process of final improvement, and I don't think Sandy or I would necessarily object to pushing out Approval for a few days. I know that both when I've been Approving and being Approved, a lot of back-and-forth happened in that focused period; a good thing we need to learn how best to harness. Howard C. Berkowitz 15:58, 28 March 2009 (UTC)

Yes, I think your getting the idea. Keep in mind that those performing the approval are not experts and don't know which technical jargon means what. More importantly, we don't know (and shouldn't be involved in any decision concerning) any of the idiosyncracies that might exist in why the author may have chosen 'not' to use a specific term. So it is best to discuss it here and let the author decide whether to change it (as you've done). And, yes, you can always add more time to the clock if you need it. Of course, if there were a third editor, you could make all the content changes that you wanted until everyone was happy (or at least satisfied). With the single editor approval, you can still make content changes, but Howard has to be the one to be satisfied when the clock runs out. D. Matt Innis 16:25, 28 March 2009 (UTC)

EEEK!

ULTRA broke many codes???  !!!

With the ahem obvious correction, that's a good addition. You may, however, want to use that in external links, etc., because a change after nomination will reset the Approval clock. It's your call.

Ciphers. Please.

Howard C. Berkowitz 01:21, 27 March 2009 (UTC)

Changed to "ciphers"; a thinko on my part. Editors who do not know what we're talking about, see Cryptography#Codes_versus_ciphers.

I think this is an important point, worth having in the main article. If that delays approval, OK. Sandy Harris 01:33, 27 March 2009 (UTC)

As long as no-one removes the ToApprove template AND Howard does not make a content edit AND I see that Howard (himself) changes the version number to include any new edits before the 29th, it will still get approved under the single editor approval. Of course you can always change the date if you feel that you need more time to get something right. D. Matt Innis 01:56, 27 March 2009 (UTC)

Thanks, Matt. I didn't know I could accept changes like that without resetting.

We can laugh together about codes and ciphers, but TV writers will keep going on about "seeekrit kodes". Seriously, it is important, and I'm glad you are OK on a reset. Do you want to look further before restarting the clock? It occurs to me that in the process of adding external links or bibliography, you may get other ideas. Kahn's Codebreakers has lots of examples of the brute force fallacy.

You make a good implied point that brute force is much more feasible with computers, but you might want to point out one of the problems of brute force. It may or may not be a good example to suggest that a brute force attack against 1000 characters could produce plaintexts of every possible string that could be expressed in 1000 characters. The computational limitations may very well not be generating keys, but recognizing the correct plaintext. A starting point would be using basic metrics such as frequency analysis and the index of coincidence to recognize natural language, but how does one recognize the right recovery? Which is correct:

1. Third brigade to fire twelve guns at noon
2. Fifth company to launch one decoy at dawn

Howard C. Berkowitz 02:02, 27 March 2009 (UTC)

There's some discussion of recognition questions at Cryptanalysis#Known_plaintext. You're correct that it is an important issue that could be expanded, but I don't think it necessarily belongs in this article. Sandy Harris 02:21, 27 March 2009 (UTC)

Would a brief transition and a link to that section be useful? Howard C. Berkowitz 02:28, 27 March 2009 (UTC)

I added a paragraph at the end of "symmetric ciphers" section. Sandy Harris 03:20, 27 March 2009 (UTC)

Then went back, moved it to introduction & edited. Found one idiotic error; N*2^8 instead of 2^(N*8). Sandy Harris 04:08, 27 March 2009 (UTC)

So at this point, I've added two paragraphs to the article since the approval nomination — the last one in the introduction and the second in the "Cautions" section — both as responses to comments by Howard here. Are those OK? Do they change the approval status? Sandy Harris 05:31, 27 March 2009 (UTC)

Sandy, let me acknowledge that you've really improved the phrasing; in some of your text here and in articles, I had a nagging discomfort with what seemed an overemphasis on key length and underemphasis on algorithmic strength. Now, however, I think you've got the balance just right, and put in the context of brute force versus other attacks.

I did see some potential copyedit in the plaintext recognition, but I'm getting too sleepy to edit someone else's words. Let me look at it again tomorrow. From my perspective, you have simply been making the meaning more clear, not changing it -- do other people find that a valid distinction? I have suggested clarification and emphasis but not, I think, any fundamentally new ideas; maybe a citation or example whose acceptance was up to you. Howard C. Berkowitz 05:44, 27 March 2009 (UTC)

See text/copy edit above. In the cautions section, I apologize if this is text that was there before, but

That said, one might choose to use longer keys, say 256 bits rather than 128, on the principle that this offers some protection against a cryptanalytic attack that might weaken the cipher without completely breaking it. Suppose an attacker discovers a bit of cleverness that reduces the effective key length to half the actual key length. He can break the 128-bit cipher with the cleverness plus a brute force search of the reduced 64-bit key space, clearly feasible for an attacker with large resources. Against a 256-bit key, however he is stymied; even after the cleverness he has a 128-bit space to search and this is thoroughly infeasible.

doesn't read to me as a brute force attack — once you add "cleverness", I would interpret that as having some knowledge of the key generation, or key application, algorithm. Am I misreading this paragraph? Howard C. Berkowitz 02:01, 28 March 2009 (UTC)