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)

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)

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)

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)

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)