Talk:Cryptanalysis

From Wikipedia, the free encyclopedia
Jump to: navigation, search
          This article is of interest to the following WikiProjects:
WikiProject Cryptography / Computer science   
WikiProject icon This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the quality scale.
 ???  This article has not yet received a rating on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science.
 
WikiProject Military history (Rated C-Class)
MILHIST This article is within the scope of the Military history WikiProject. If you would like to participate, please visit the project page, where you can join the project and see a list of open tasks. To use this banner, please see the full instructions.
C This article has been rated as C-Class on the quality assessment scale.
WikiProject Citizendium Porting    (Inactive)
WikiProject icon This article is within the scope of WikiProject Citizendium Porting, a project which is currently considered to be inactive.
 

Article needs work[edit]

This article seems a bit incoherent. whats this "two-key" stuff? You mean public key / asymmetric cryptography, or what? And "one-key" means what? Symmetric cryptography?

Also, chosen ciphertext and chosen plaintext attacks are different for symmetric crypto. For symmetric crypto, attacks are: ciphertext-only, known-plaintext, chosen-plaintext and chosen-ciphertext (in order of increasing strength.) For assymetric, the three main attacks are: known-plaintext, chosen-ciphertext and adaptive chosen-ciphertext.

This page needs to be rewritten by someone who knows what they are talking about (I know enough to know this page is awful, but I'll leave fixing it to those more knowledgeable than I...) -- SJK

How is it that there's no mention whatsoever of OTPs/perfect ciphers? I didn't have time to review the whole article but just the fact that there's no mention of those is enough to figure that it's quite lacking. — Preceding unsigned comment added by 86.145.97.79 (talk) 00:04, 6 November 2012 (UTC)

What do do about cryptanalysis assumptions?[edit]

There's some short stub-esque pages on the various types of cryptanalysis attacks: known-plaintext attack, chosen plaintext attack, ciphertext-only attack, chosen ciphertext attack, adaptive chosen ciphertext attack. They are all quite short and similar, and its unlikely they'll every expand into longer articles. Some options:

  1. Keep the short pages. If this was the case, you'd want to add things like "adaptive chosen plaintext attack" and "related-key attack" and (believe it or not) "related-cipher attack".
  2. Merge them all into a Scenarios for cryptanalysis article.
  3. Merge them all into cryptanalysis.

I'd favour doing 2., seeing how long the article is, and then deciding whether to do 3.

Matt 02:59, 13 Mar 2004 (UTC)

Matt, I think keeping (and adding to) the stubesque pages makes some sense, when combined with 2. The problem is that no _real_ sense of the operation of cryptanalytic technique can be anything less than detailed -- probably far too detailed for a WP article, even a technical one. But any attempt to do so, which I would nevertheless encourage (it might be possible for one or another technique), should be kept quarantined. More or less the way the mathematics or physics people have done in some cases.

Nevertheless, an overview of cryptanalysis (how to think about it, how to consider choosing an attack technique, what informatio is needed to decide, ...) would be useful. Both to the somewhat curious reader (more ambitious than the average) and to the serious reader. It's hard to keep the abstraction levels straight when thinking about crypto generally and abotu cryptoanalysis in particular, so whatever illumination is possible would be well, even for the serious reader.

Comments?

ww 16:09, 15 Mar 2004 (UTC)

The modern treatment of this stuff is in terms of the random oracle model. There should definitely be an article explaining terms like IND-CPA and IND-CCA security (CPA=chosen plaintext attack, CCA=chosen ciphertext attack, etc). But it shouldn't be in the main cryptanalysis article. I've been wanting for a while to write something on those topics but I'm too busy right now. Rogaway and Bellare have an excellent downloadable textbook that I'll try to add a link to. Phr 08:41, 16 February 2006 (UTC)

Presumably this is the text-book http://www.cs.ucsd.edu/~mihir/cse207/classnotes.html --AWZ (talk) 19:16, 3 February 2008 (UTC)

Shannon link[edit]

Can somebody check the link on "Shannon Information" (the Shannon part)? It used to point to a disambiguation page. I've changed it to what I think is the right person, but I'm not completely sure... Ealex292 02:12, 10 Apr 2005 (UTC)

I've never heard the term "Shannon Information" before, but from context it just means the cryptanalyst has gained information that lowers the effective Shannon entropy of the (unknown) plaintext. For example, suppose you have a ciphertext and you know that the plaintext was written in either English or French, but you don't know which, and you consider both equally likely. If you have a statistical method that doesn't yield any plaintext, but can determine from the ciphertext that the plaintext is 65% likely to be English, that would be an information deduction attack. In general, perfect security means that for a given ciphertext, all plaintexts are equally likely. Any algorithm that discloses that some plaintexts are more likely than others is an attack. Phr 08:38, 16 February 2006 (UTC)

History of cryptanalysis[edit]

I see that a large chunk of the article was just removed. For what reason? — DAGwyn 19:01, 6 April 2007 (UTC)

animal behavorial cryptanalysis[edit]

I removed a tag pointing to other species signs and signals. This is so wide a divergence in the sense of cryptanalysis as to be out of context entirely. Linguistically embedded mehaphor being not entirely rational, I'd futher observe that this meaning of the term is entirely unknown to me. ww 11:13, 26 May 2007 (UTC)

Thanks. You don't actually have to justify the reversion in the Talk page; Wikipedia editors constantly revert "random" additions that make no sense (in addition to obvious instances of vandalism). Usually just a brief reason in the "Edit summary" box will suffice. — DAGwyn 05:45, 27 May 2007 (UTC)
Actually, I realize that, but I've never bothered to figure out how to add an edit summary to a 'rollback' action. Usually I don't bother, as I did in this case, to explain further, but there is/was an actual point to the tag, just more than a little off any sensible target. Thus... ww 10:50, 27 May 2007 (UTC)

Characterisation of attacks (deduction vs induction)[edit]

I hope I'm not being to picky, but I question the use of the word "deduce" in the context of cryptanalysis. It is my experience this is primarily an inductive process based on guesses and experimentation. There can be very little information at the begining of an attack; certainly not enough to solve the system in the way deduction demands. The analyst usually looks for possible known algorithms or mathematically simple methods, which is really more of inductive process. I'd like to see the wording changed so this is more clearly reflected. I'm not going to change it myself, because I don't feel it is my place. I just wanted to throw this out to wp community. —The preceding unsigned comment was added by Mbset (talkcontribs).

There are elements of both induction and deduction involved, also plain guesswork (confirmed by results). — DAGwyn 16:20, 21 August 2007 (UTC)
"Deduce" is correct. One has to distinguish between finding an attack against a cryptosystem (i.e., developing an algorithm) and performing the attack (i.e. running the algorithm). While finding the algorithm might be an inductive process, running it is not. The article talks about what the result of the attack is (e.g. key, plaintext etc.). Hence the article is describing what the output of running an algorithm is. 169.231.5.121 07:42, 22 August 2007 (UTC)
If we were to accept that strange model of cryptanalysis, then the "deductive" part would be of little interest anyway. — DAGwyn (talk) 17:37, 14 March 2008 (UTC)

Legal issues[edit]

  • Bizarrely, the article fails to address the legal aspects of what is essentially codebreaking or cracking the code, which assumingly is illegal (whereas Cryptography#Legal issues involving cryptography has such section). I suppose there have been some international conventions prohibiting this. Back in the Soviet time, the students at the KGB Higher School trained in this, were referred to only as mathematicians, i understand exactly for legal reasons.Muscovite99 (talk) 23:08, 3 January 2009 (UTC)
There is no legal standpoint on codebreaking in the UK, and as far as I'm aware there isn't one in the USA either. Legal protection only applies to the data that was encrypted. Obviously if it was government classified or covered by the official/trade secrets acts the unauthorized decryption of such data would be illegal. In most cases it's what you do with the data you get that is covered by law. It is not illegal to break the encryption of an SSL connection, but it is illegal to use someone's bank account details to fraudulently obtain money. However, breaking encryption at work would probably be considered a fireable offence and you wouldn't stand a chance if you tried to take them to court over illegal dismissal. It also may be considered a breach of your ISP's terms and conditions if you try to break encryption of data sent over the internet. 86.14.89.251 (talk) 19:39, 6 January 2009 (UTC)
Far from being bizarre, when there is nothing useful to say it is best to say nothing. In particular we need to be careful not to offer legal advice, since we are not licensed to do so. — DAGwyn (talk) 15:43, 11 January 2009 (UTC)
  • History of the US government's interaction with academic cryptography, and the relevance of the DMCA's anti-circumvention provisions and research exception, may deserve a sentence or two. As you note, we can't provide legal advice. 24.7.68.35 (talk) 21:57, 6 March 2010 (UTC)

Putting classifications of attacks real-world perspective[edit]

Seems like it could be useful to provide some concrete examples of attacks on modern algorithms, to complement the sort of abstract section in there now that's describing how attacks can be useful or not.

We could list some algorithms that were once commonly used but had to be phased out (or are being phased out) after cryptanalysis (MD5, RC4 in WEP, single-DES, export-level cryptography, SHA-1, DECT Standard Cipher), and some where reduced-round attacks exist but few people are running for the exits yet (AES, SHA-2, 3DES). Guess we could work those examples into the current section on attack types as appropriate, too.

Also, we should have a shout out to protocol/application breaks that aren't algorithm breaks, with examples. Maybe there's a good Wikipedia article on protocol attacks? Haven't looked.

Replacing "cryptosystem" with more specific terms, quantum computation, protocol break[edit]

The word "cryptosystem" is deprecated as ambiguous according to its article. In a couple places where we use it, we mean an application of cryptography, in "Types of cryptanalytic attack" we essentially mean a cipher or hash function, and in "Cryptanalysis of asymmetric cryptography" we mean an asymmetric algorithm (we say "cipher" now, but that's not precise for, e.g., Diffie-Hellman).

Post-quantum cryptography and Quantum computer say more than this article does about the implications of QC for crypto -- improve and link.

There's still only one paragraph here about flaws above the algorithm level (protocol breaks, implementation flaws); that might deserve a short section that links elsewhere. —Preceding unsigned comment added by 24.7.68.35 (talk) 06:45, 4 April 2010 (UTC)

The word "cryptosystem" has not been deprecated. Rather, IETF does discourage its use because, "cryptosystem" does indeed cover a wide range from ciphers to protocols. It is, however, fine to talk about "types of attacks against cryptosystems", since a cryptographic attack can for example exploit a weakness in a cipher (e.g. a differential attack) or exploit a weakness in a cryptographic protocol (e.g. a man-in-the-middle attack) or an implementaion (e.g. timing-attack). Hence in this article it is ok to use a term (cryptosystem) that covers a wide range. The same also holds for the section "cryptanalysis of asymmetric cryptography". Many attacks against asymmetric cryptosystems do not break the "asymmetric algorithm" (e.g. RSA). Rather these attacks exploit the way that the algorithm is used. How many times have we seen newspaper articles claiming that RSA is broken, only to find that some protocol was not using it correctly? 81.62.26.199 (talk) 10:21, 4 April 2010 (UTC)

Huge changes without discussion[edit]

User Mesoderm has made a very extensive set of changes to this article in the last two days. These are unlikely to be welcomed by all concerned with it. I am going to restore some of what has been deleted, but wouldn't a pause be appropriate with discussion here as to the philosophy behind the changes. --TedColes (talk) 14:56, 3 April 2012 (UTC)

Formatting problem[edit]

User DAGwyn has improved the wording on the section on 'Depth'. But (s)he has edited out a lot of formatting including that which gives the correct symbol for the "XOR" operator (symbolized by ) on the grounds that "was unreadable (font issue?) on computer I borrowed; reformatted and added somewhat for clarity". As far as I can see, the previous formatting used standard HTML and Wiki markup, so I wonder whether it was a problem with the HTML of the web browser on the borrowed computer. I am reluctant to accept that all such markup should be eliminated – where would it stop? I therefore plan to restore the formatting unless a good argument against doing so is forthcoming. --TedColes (talk) 08:31, 30 April 2012 (UTC)

The problem was that the circled-plus symbol (⊕) was appearing as an empty rectangle instead, on the computer at my friend's house. I don't think you're supposed to embed special HTML symbols in article source text. Note that in the source text of this message, I inserted the ⊕ character using the "Math and logic" menu from the pull-down list below the "Save page" button, and I suggest that the Wikipedia staff would prefer that that be used. There is also a "math" tag that may be better to use for equations etc., but I don't recall offhand its name for that symbol. The current text looks marginally acceptable on my own computer (the character is overly large and bold for the font), but I'm concerned that it might not work at all on many others, unless changed to use another approach (such as I just suggested). There is also a problem with centering the standalone equations: it becomes hard to read on wide screens. However, I'll leave it up to others to address. — DAGwyn (talk) 10:38, 30 April 2012 (UTC)
Thanks for this helpful response. --TedColes (talk) 11:24, 30 April 2012 (UTC)
And thank you for taking care of this. — DAGwyn (talk) 23:33, 2 May 2012 (UTC)

Sir Harry Hinsley[edit]

The article, and many others on wikipedia, state that:

"Sir Harry Hinsley, official historian of British Intelligence in World War II, made a similar assessment about Ultra, saying that it shortened the war "by not less than two years and probably by four years"; moreover, he said that in the absence of Ultra, it is uncertain how the war would have ended."

This quote is attributed to the introduction Hinsley wrote in his book, Hinsley & Stripp (eds.) 'Codebreakers: The Inside Story of Bletchley Park', (Cambridge, 1993), pp. 1-13.

However, I have read the entire introduction and could not find this quote. — Preceding unsigned comment added by 144.124.226.21 (talk) 12:24, 23 July 2012 (UTC)

I've located that quote from Hinsley in a web security book which cites a talk he gave in 1993 as the original source. It may be as simple as swapping out for the proper source, but I haven't read through it to see if it supports the rest of the sentence. VernoWhitney (talk) 14:54, 23 July 2012 (UTC)
The quote comes from a lecture that Hinsley gave on Tuesday 19 October 1993 at Cambridge University. See: Hinsley, Harry (1996) [1993], The Influence of ULTRA in the Second World War  which contains the following

Now the question remains how much did it [Ultra] shorten the war, leaving aside the contribution made to the campaigns in the Far East on which the necessary work hasn't been done yet. My own conclusion is that it shortened the war by not less that two years and probably by four years - that is the war in the Atlantic, the Mediterranean and Europe.

Pages 11 to 13 of the introduction to Hinsley, F.H.; Stripp, Alan, eds. (1993) [1992], Codebreakers: The inside story of Bletchley Park, Oxford: Oxford University Press, ISBN 978-0-19-280132-6  gives a carefully argued case as to how he came to this conclusion. It includes the following.

As it was, the invasion of Normandy was carried out on such tight margins in 1944 that it would have been impracticable—or would have failed—without the precise and reliable intelligence provided by Ultra about German strengths and order of battle. Carried out in 1945, it would have failed more decisively—or, more likely, these other considerations would have necessitated further delay.

--TedColes (talk) 15:05, 23 July 2012 (UTC)
Indeed, however it does not contain the quote nor does it contain Hinsley's conclusion regarding the full amount of time ULtra reduced the length of the war. However, do not doubt that makes that claim somewhere in print. I imagine it appears somewhere in one of the four volumes he editted on the official history of British Intelligence in the Second World War. However, I noted that people above have found an alternative source from the transcript of a seminar. Would that do?--144.124.226.21 (talk) 04:03, 24 July 2012 (UTC)
I am sure that the above link to "The Influence of ULTRA in the Second World War" is a reliable source and acceptable in Wikipedia. --TedColes (talk) 08:46, 24 July 2012 (UTC)