Talk:Block cipher

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Cryptography / Computer science  (Rated C-class, Top-importance)
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.
C-Class article C  This article has been rated as C-Class on the quality scale.
 Top  This article has been rated as Top-importance on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science (marked as Top-importance).
 
edit·history·watch·refresh Stock post message.svg To-do list for Block cipher:
  • "unvarying transformation" in the first sentance needs an explanation or a link to an explanation.
  • Describe some of the generic attacks on block ciphers
  • Provide introductory information on Block Ciphers that explain it without the use of detailed terminology (introduce block ciphers to those new to this subject)
Priority 3

Image[edit]

The image for this article is screwed up, at least in Firefox. Anyone got a better one? —Preceding unsigned comment added by Burningmace (talkcontribs) 20:13, 19 December 2008 (UTC)

Description of specific "Notable block ciphers" is too long[edit]

I think that the section Notable block ciphers contains too much detail. Given that we have main articles for each algorithm (which I presume include all the detail that I propose to delete here) I think this article should have a brief description of the major external characteristics (block size, key size) and brief history, but not the more technical/internal details. Specifically, here's roughly what I would delete from the existing text:

Lucifer / DES

Lucifer is generally considered to be the first civilian block cipher, developed at IBM in the 1970s based on work done by Horst Feistel. A revised version of the algorithm was adopted as a US government Federal Information Processing Standard: FIPS PUB 46 Data Encryption Standard (DES). It was chosen by the US National Bureau of Standards (NBS) after a public invitation for submissions and some internal changes by NBS (and, potentially, the NSA). DES was publicly released in 1976 and has been widely used.

DES was designed to, among other things, resist a certain cryptanalytic attack known to the NSA and rediscovered by IBM, though unknown publicly until rediscovered again and published by Eli Biham and Adi Shamir in the late 1980s. The technique is called differential cryptanalysis and remains one of the few general attacks against block ciphers; linear cryptanalysis is another, but may have been unknown even to the NSA, prior to its publication by Mitsuru Matsui. DES prompted a large amount of other work and publications in cryptography and cryptanalysis in the open community and it inspired many new cipher designs.

DES has a block size of 64 bits and a key size of 56 bits. 64-bit blocks became common in block cipher designs after DES. Key length depended on several factors, including government regulation. Many observers in the 1970s commented that the 56-bit key length used for DES was too short. As time went on, its inadequacy became apparent, especially after a special purpose machine designed to break DES was demonstrated in 1998 by the Electronic Frontier Foundation. A variant of DES, Triple DES, triple-encrypts each block with either two independent keys (112-bit key and 80-bit security) or three independent keys (168-bit key and 112-bit security). It was widely adopted as a replacement. As of 2011, the three-key version is still considered secure, though the National Institute of Standards and Technology (NIST) standards no longer permit the use of the two-key version in new applications, due to its 80-bit security level.

IDEA

The International Data Encryption Algorithm (IDEA) is a block cipher designed by James Massey of ETH Zurich and Xuejia Lai; it was first described in 1991, as an intended replacement for DES.

IDEA operates on 64-bit blocks using a 128-bit key, and consists of a series of eight identical transformations (a round, see the illustration) and an output transformation (the half-round). The processes for encryption and decryption are similar. IDEA derives much of its security by interleaving operations from different groupsmodular addition and multiplication, and bitwise exclusive or (XOR) — which are algebraically "incompatible" in some sense.

The designers analysed IDEA to measure its strength against differential cryptanalysis and concluded that it is immune under certain assumptions. No successful linear or algebraic weaknesses have been reported. As of 2007, the best attack which applies to all keys can break IDEA reduced to 6 rounds (the full IDEA cipher uses 8.5 rounds).

RC5

RC5 is a block cipher designed by Ronald Rivest in 1994 which, unlike many other ciphers, has a variable block size (32, 64 or 128 bits), key size (0 to 2040 bits) and number of rounds (0 to 255). The original suggested choice of parameters were a block size of 64 bits, a 128-bit key and 12 rounds.

A key feature of RC5 is the use of data-dependent rotations; one of the goals of RC5 was to prompt the study and evaluation of such operations as a cryptographic primitive. RC5 also consists of a number of modular additions and XORs. The general structure of the algorithm is a Feistel-like network. The encryption and decryption routines can be specified in a few lines of code. The key schedule, however, is more complex, expanding the key using an essentially one-way function with the binary expansions of both e and the golden ratio as sources of "nothing up my sleeve numbers". The tantalising simplicity of the algorithm together with the novelty of the data-dependent rotations has made RC5 an attractive object of study for cryptanalysts.

12-round RC5 (with 64-bit blocks) is susceptible to a differential attack using 244 chosen plaintexts. 18–20 rounds are suggested as sufficient protection.

Rijndael / AES

DES has been superseded as a United States Federal Standard by the AES, adopted by NIST in 2001 after a 5-year public competition. The cipher was developed by two Belgian cryptographers, Joan Daemen and Vincent Rijmen, and submitted under the name Rijndael.

AES has a fixed block size of 128 bits and a key size of 128, 192, or 256 bits, whereas Rijndael can be specified with block and key sizes in any multiple of 32 bits, with a minimum of 128 bits. The blocksize has a maximum of 256 bits, but the keysize has no theoretical maximum. AES operates on a 4×4 column-major order matrix of bytes, termed the state (versions of Rijndael with a larger block size have additional columns in the state).

Blowfish

Blowfish is a block cipher, designed in 1993 by Bruce Schneier and included in a large number of cipher suites and encryption products. Blowfish has a 64-bit block size and a variable key length from 1 bit up to 448 bits. It is a 16-round Feistel cipher and uses large key-dependent S-boxes. Notable features of the design include the key-dependent S-boxes and a highly complex key schedule.

Schneier designed Blowfish as a general-purpose algorithm, intended as an alternative to the ageing DES and free of the problems and constraints associated with other algorithms. At the time Blowfish was released, many other designs were proprietary, encumbered by patents or were commercial/government secrets. Schneier has stated that, "Blowfish is unpatented, and will remain so in all countries. The algorithm is hereby placed in the public domain, and can be freely used by anyone." Blowfish provides a good encryption rate in software and no effective cryptanalysis of the full-round version has been found to date.


This is just to indicate the scope - some cleanup may be required so the text flows properly. Does anyone have any comments or objections? Mitch Ames (talk) 08:36, 7 April 2012 (UTC)

Hehe! This is why I objected so strongly to User:Mesoderm's lengthy addition of a discussion on block cipher modes of operation, which he for now prepared in his User:Mesoderm/sandbox article. At the same time, your addition is too short ;) – and a discussion on padding should be subsumed into the Modes of operation section.
But back to the question, yes, the "Notable ciphers" section is too long. But more importantly, I do not agree with the selection. Yes, DES and AES are notable, no doubt about that. IDEA is notable mostly for its innovative and highly lauded design, and its good security. RC5 is worthy a mention for its variable block and key sizes, but in total is not nearly as notable. Blowfish and Twofish are notably for their widespread implementation and usage in the open-source community, while also having a robust design. Camellia has recently become notable because it has been included in a variety of international standards. So what I propose is having the following sections:
  • DES – includes short mention of Lucifer and Triple-DES
  • IDEA
  • AES
  • Former AES candidates – includes Twofish (shortly mentioning its heritage from Blowfish), Serpent, and RC5
  • Other ciphers (approx. one to two sentences each) – Camellia, CAST (PGP/GPG), SEED (Korean standard), KASUMI (3GPP standard)
What regards your proposed text above, we do need to say in at least one sentence why each cipher is notable. Specific data such as the number of rounds is less important. I will probably go ahead working on this.
Thanks for the feedback! Nageh (talk) 13:12, 7 April 2012 (UTC)
Perhaps we should:
  • Limit the subsections (of Notable block ciphers) to particularly notable ciphers (I would not include former AES candidates unless they were particularly notable for some other reason)
  • Add to See also: List of block ciphers
  • Create the aforementioned List of block ciphers article, which could then include a brief (1 or 2 sentences maximum) summary and links to all block ciphers for which we have articles.
I'd like to see some feedback from Mesoderm before we make significant changes - if there's significant disagreement, better to sort it out here than edit-war. Mitch Ames (talk) 14:40, 7 April 2012 (UTC)
Let's see. My point is also to make it short. There is still lots of theoretical stuff missing in this article, particularly related to the last section ("Relation to other cryptographic primitives"), and in the overall scheme of one-way functions and their existence. Nageh (talk) 15:00, 7 April 2012 (UTC)
@Ad Former AES candidates. I think you did not understand my point. My intention is not to discuss all former candidates, just the three notable ones that I mentioned: Serpent, Twofish and RC5. Nageh (talk) 15:09, 7 April 2012 (UTC)

Modes of operation[edit]

<Quoting Nageh 13:12, 7 April 2012 (UTC) > ... your addition is too short ...

I disagree that my Modes of Operation section is too short. I think that the section of this article should just give a brief statement as to why we need them (to handle multiple blocks), mention the fundamental types (independent, depending on previous blocks, and I guess I should add "modes that depend on position but not other blocks", ie stream ciphers such as CFB) but leave most of the details to the Block cipher modes of operation article. Ie this article's section has a summary of the reasons and general characteristics, but leave the technical details to the main article. Mitch Ames (talk) 14:40, 7 April 2012 (UTC)

Have a look at my section. I don't think it is either too long or too short. Nageh (talk) 14:51, 7 April 2012 (UTC)

Padding[edit]

Resolved

<Quoting Nageh 13:12, 7 April 2012 (UTC) > ... a discussion on padding should be subsumed into the Modes of operation section. ..

I disagree. Padding is independent of modes of operation, and thus should be described independently of it. Yes you need padding for processing of multiple blocks, but you need padding for any use of block ciphers - even one block, and also for functions such as MACs. (Eg ISO/IEC 9797-1 does not explicitly use any of the defined "modes of operation". Iteration is basically CBC, but it doesn't apply to the first block for Initial Transform 2). We should take our lead from ISO/IEC 10116, which wisely does not include padding in its scope. (Is there an ISO/IEC standard that covers padding an only padding?) Mitch Ames (talk) 14:40, 7 April 2012 (UTC)

See, the problem is that people associate "modes of operation" only with encryption. NIST makes it clear that any use of a block cipher in a greater protocol is considered a "mode of operation" when it comes to block ciphers. As such, padding is inherently related to modes of operation. There is no use of padding outside of some mode of operation. Also, I considered it an issue of due weight. I hope you understand what I mean. Nageh (talk) 14:57, 7 April 2012 (UTC)
I think I see your point. Padding is certainly more widely applicable than just block ciphers and modes of operation. But this article only discusses these, and I think an entire section on padding is not quite appropriate. If you can live with the mention of it in the Modes of operation section that's great! If not... well, I'm not gonna fight forever. Nageh (talk) 15:20, 7 April 2012 (UTC)
Ad "you need padding for any use of block ciphers - even one block": That is not true, both of it. The AES Key Wrap mechanism does not need padding. Universal hash functions using block ciphers as almost-universal hash function components do not need padding. In addition, any protocol that uses a block cipher merely as a PRP or PRF does not need padding. This includes the OFB and CTR stream cipher modes of operation. Nageh (talk) 15:35, 7 April 2012 (UTC)
Nageh> NIST makes it clear that any use of a block cipher in a greater protocol is considered a "mode of operation" when it comes to block ciphers.
Exactly where does NIST say this. Do we consider MACs to be "modes of operation"? Should they be mentioned here and in the modes of operation article? In any case, NIST is not the only entity defining ciphers and modes of operation - ISO/IEC 10116 uses the same basic algorithms, but allows more flexibility. (For example SP 800-38A limits itself to use with FIPS approved block ciphers, whereas 10116 explicitly allows for use with any block cipher.)
FIPS 81 ("DES Modes of Operation") from Dec. 1980 standardizes the classic four modes of operation plus a basic CBC-MAC. Here NIST summarizes what it all considers modes of operation: encryption schemes, authentication schemes, and authenticated encryption schemes. Quoting: "A block cipher mode, or mode, for short, is an algorithm that features the use of a symmetric key block cipher algorithm to provide an information service, such as confidentiality or authentication.".
Anyway, I am not sure whether we should discuss non-encryption-only modes in the same article. I have avoided doing so in this article.
NIST limits the application to approved ciphers because they have a policy, that is all about it. You can take any other standard or recent book on cryptography, if you prefer. Nageh (talk) 11:12, 8 April 2012 (UTC)
Nageh> padding is inherently related to modes of operation.
No. I can define the padding algorithm without reference to a mode of operation. Some modes of operation inherently require padding, but the definition of the padding does not depend on the mode of operation. In fact, NIST SP 800-38A Recommendation for Block Cipher Modes of Operation explicitly says (I've added the bold):

5.2 Representation of the Plaintext and the Ciphertext

The formatting of the plaintext, including in some cases the appending of padding bits to form complete data blocks or data segments, is outside the scope of this recommendation.

Ie, while NIST gives examples (800-38A Appendix A) they also explicitly state that padding is not part of Modes of Operation.
Please do not omit what I said right below that paragraph when paraphrasing. I admitted that padding of course had wider application than just block ciphers and modes of operation, but this article is only concerned with these.
But more importantly, you do need to consider jointly a specific padding technique jointly with a specific encryption mode to prove that the combination is secure. Of course you can discuss padding outside of a specific standard document! That doesn't mean it's the right way to do so in this article! I would rather see a separate discussion on padding in its own article. But again, I won't fight about it. Nageh (talk) 11:23, 8 April 2012 (UTC)
Nageh> I think an entire section on padding is not quite appropriate.
Padding is logically separate from modes of operation - as stated explicitly by both NIST and ISO/IEC and the article should reflect that. If you think my original text was too long, I'm happy to accept your shorter paragraph - but I still believe that a small separate section is appropriate. It should not be buried in the Modes of Operation section.
It is conceptually separate, I agree. Yet, from a security point of view one may not take these as independent components. I really would rather avoid discussing padding issues in the article, and leave it at mentioning it in the section on modes of operation, but I won't revert you on this. Nageh (talk) 11:25, 8 April 2012 (UTC)

I've moved the padding paragraph into its own section again - after the Modes of Operation section, and keeping the same wording so that it flows on smoothly from the Modes of Operation text. Mitch Ames (talk) 00:41, 9 April 2012 (UTC)

Just saw your response here. As you'd probably figured I'm ok with it. Best, Nageh (talk) 13:00, 9 April 2012 (UTC)

FYI, the only reason why the recent version of ISO/IEC 10116 omits discussion of padding was because of Vaudenay's padding oracle attacks, which forced them to revise the document shortly before standardization. I even have a reference for this. Just to let you know. Nageh (talk) 00:41, 9 April 2012 (UTC)

IV need not be random[edit]

Resolved

I've changed the statement that the IV must be random for CBC. NIST SP 800-38A clause 5.3 says it must be, but NIST isn't the only definition of CBC. ISO/IEC 10116 also defines CBC, and explicitly excludes the derivation of IV (or SV, as they refer to it) from its scope. Clause 3.12 says:

3.12 starting variable (SV)

variable possibly derived from some initialization value and used in defining the starting point of the modes of operation.

NOTE The method of deriving the starting variable from the initializing value is not defined in this International Standard. It needs to be described in any application of the modes of operation.

Thus I could legitimately specify that my mode of operation is CBC, as defined in ISO/IEC 10116, with SV = all zeros. Mitch Ames (talk) 03:31, 8 April 2012 (UTC)

Argh, no!!! Only CBC encryption with a random IV is semantically secure, and this is what this short paragraph can only reasonably address! Did you read section B.2.2 bullet e) of – what seems to be – your favorite standard? And as far as I am aware this is about the only standard that does not prescribe the IV to be random, for reasons described in section B.2.2. The ANSI standard doesn't. BSI national standards don't. About each and every book on cryptography and lecture notes do not. Check the Handbook of Applied Cryptography. Check lecture notes by Bellare and Rogaway. Any other notable publication. And did you check other standards? Don't fool the reader into taking non-random IVs for CBC encryption, this error is far too common. I have reverted your revert. If you want to make a point about this standard please do so in the block cipher modes of operation article. Nageh (talk) 10:57, 8 April 2012 (UTC)
If you want the text to say "IV must be random to be semantically secure" then reword the sentence to add those extra words. NIST makes recommendations for US Federal agencies, which is fine, but there is a world outside of the US that uses international standards. You cannot limit the definition of CBC etc to what NIST says. ISO/IEC 10116 contains a perfectly valid and internationally acceptable definition of the CBC algorithm - and section B.2.2 is informative, not normative. If you don't qualify "must", the reader might reasonably assume that if the IV is not random, the algorithm is not CBC - which is not true for those using the international standard.
Frankly I think we are having this argument in the wrong place. As per my original text I think we should keep the description of modes of operation in this article very basic and leave the security analysis to the dedicated article Block cipher modes of operation. Mitch Ames (talk) 12:36, 8 April 2012 (UTC)
I don't have a preference for the NIST standard. But the ISO/IEC standard is virtually the only source permitting non-random IVs for the CBC mode. Whatever... Btw, even when a source is a U.S. standard it is still a national standard. Nageh (talk) 12:50, 8 April 2012 (UTC)
But NIST Special Publication 800-38A Recommendation for Block Cipher Modes of Operation is not. Quoting the 2nd para of section 2 of that document: "This recommendation is neither a standard nor a guideline, and as such, is neither mandatory nor binding on Federal agencies." But whether it is a standard or not is irrelevant. The important thing is that it is not the only definition of the CBC algorithm. Mitch Ames (talk) 12:55, 8 April 2012 (UTC)
Alright, you've got a point. FIPS PUB 81 is a standard. Oh, the important thing is that it IS the ONLY definition of the CBC algorithm. ISO/IEC is in a minority here when it comes to the specification of the IV. Period. Nageh (talk) 12:57, 8 April 2012 (UTC)
FIPS PUB 81 DES Modes of Operation is a standard - but it only applies to DES (the title is a giveaway, but also see section 7 Applicability), so its use for anything else is technically WP:OR without some other source. But that's not really the point. Your claim that is is the ONLY definition of CBC is patently ridiculous - you can't just dismiss an international standard because it doesn't match your text. I'm not saying that a non-random IV is good or secure - I'm saying that it factually and technically correct to say that you can have CBC (for some legitimate definitions of CBC) with non-random IV. As I said, the word "must" could reasonably mean two things "IV must be random to be secure" or "IV must be random to meet the recommendation / guideline /standard". I'll accept that the first is true, but the second is demonstrably not true for some internationally standard definitions of CBC. Add the extra words to the text to clarify, and the problem goes away. Mitch Ames (talk) 13:15, 8 April 2012 (UTC)
I think I did that already? How can you say that I reject a reference simply because it does not fit my text? Ok, I think as you won't believe me otherwise I need to start looking up references to prove that the majority indeed requires the IV to be random. Nageh (talk) 13:24, 8 April 2012 (UTC)
N> I think I did that already...
OK thanks. (We're obviously both editing at the same time, so there may be overlap.)
N> How can you say that I reject a reference ...
Because you said "FIPS PUB 81 ... IS the ONLY definition of the CBC algorithm", when ISO/IEC 10116 (which you appear to have a copy of, given your citing a specific clause of it) also defines CBC - just without mandating a random IV/SV.
Nevermind, the problem is solved, and the text is now correct, so I'm marking this as resolved. Mitch Ames (talk) 13:39, 8 April 2012 (UTC)
Because you said "FIPS PUB 81 ... IS the ONLY definition of the CBC algorithm". Yeah, never mind, that was nonsense of course. Just getting emotional, a consequence of debating via postings instead of face-to-face. :/ Nageh (talk) 13:46, 8 April 2012 (UTC)