cryptography faq product ciphers archive name cryptography faq part last modified faq for sci crypt part product ciphers this is the fifth of ten parts of the sci crypt faq the parts are mostly independent but you should read the first part before the rest we don t have the time to send out missing parts by mail so don t ask notes such as kah refer to the reference list in the last part the sections of this faq are available via anonymous ftp to rtfm mit edu as pub usenet news answers cryptography faq part xx the cryptography faq is posted to the newsgroups sci crypt sci answers and news answers every days contents what is a product cipher what makes a product cipher secure what are some group theoretic properties of product ciphers what can be proven about the security of a product cipher how are block ciphers used to encrypt data longer than the block size can symmetric block ciphers be used for message authentication what exactly is des what is triple des what is differential cryptanalysis how was nsa involved in the design of des is des available in software is des available in hardware can des be used to protect classified information what are ecb cbc cfb and ofb encryption what is a product cipher a product cipher is a block cipher that iterates several weak operations such as substitution transposition modular addition multiplication and linear transformation a block cipher just means a cipher that encrypts a block of data bytes say all at once then goes on to the next block the notion of product ciphers is due to shannon sha examples of modern product ciphers include lucifer sor des nbs sp networks kam loki bro feal shi pes lai khufu and khafre me a the so called feistel ciphers are a class of product ciphers which operate on one half of the ciphertext at each round and then swap the ciphertext halves after each round lucifer des loki and feal are examples of feistel ciphers the following table compares the main parameters of several product ciphers cipher block length key bits number of rounds lucifer des loki feal x x pes what makes a product cipher secure nobody knows how to prove mathematically that a product cipher is completely secure so in practice one begins by demonstrating that the cipher looks highly random for example the cipher must be nonlinear and it must produce ciphertext which functionally depends on every bit of the plaintext and the key meyer mey has shown that at least rounds of des are required to guarantee such a dependence in this sense a product cipher should act as a mixing function which combines the plaintext key and ciphertext in a complex nonlinear fashion the fixed per round substitutions of the product cipher are referred to as s boxes for example lucifer has s boxes and des has s boxes the nonlinearity of a product cipher reduces to a careful design of these s boxes a list of partial design criteria for the s boxes of des which apply to s boxes in general may be found in brown bro and brickell et al bri what are some group theoretic properties of product ciphers let e be a product cipher that maps n bit blocks to n bit blocks let e k x be the encryption of x under key k then for any fixed k the map sending x to e k x is a permutation of the set of n bit blocks denote this permutation by p k the set of all n bit permutations is called the symmetric group and is written s n the collection of all these permutations p k where k ranges over all possible keys is denoted e s n if e were a random mapping from plaintexts to ciphertexts then we would expect e s n to generate a large subset of s n coppersmith and grossman cop have shown that a very simple product cipher can generate the alternating group a n given a sufficient number of rounds the alternating group is half of the symmetric group it consists of all even permutations i e all permutations which can be written as an even number of swaps even and goldreich eve were able to extend these results to show that feistel ciphers can generate a n given a sufficient number of rounds the security of multiple encipherment also depends on the group theoretic properties of a cipher multiple encipherment is an extension over single encipherment if for keys k k there does not exist a third key k such that e k e k x e k x which indicates that encrypting twice with two independent keys k k is equal to a single encryption under the third key k if for every k k there exists a k such that eq is true then we say that e is a group this question of whether des is a group under this definition was extensively studied by sherman kaliski and rivest she in their paper they give strong evidence for the hypothesis that des is not a group in fact des is not a group cam what can be proven about the security of a product cipher recall from above that p k is a permutation produced by e under some key k the goal of the designer of e is to ensure that p k appears to be a random element of s n the symmetric group let r be an element of s n selected randomly we will say that p k and r are indistinguishable if an observer given p k and r in some order cannot distinguish between these two permutations in polynomial time that is with time bounded resources the observer cannot determine which of the permutations is produced by e the optimal decision is no better than simply guessing luby and rackoff lub have shown that a class of feistel ciphers are secure in this sense when the round mapping is replaced by random boolean functions how are block ciphers used to encrypt data longer than the block size there are four standard modes of operation and numerous non standard ones as well the standard modes of operation are defined in the u s department of commerce federal information processing standard fips published in see the question about ecb below for more details although they are defined for the des block cipher the modes of operation can be used with any block cipher can symmetric block ciphers be used for message authentication one may use a symmetric cryptosystem block cipher to prove to himself that he did or did not generate a message and to prove to himself whether his message was altered or unaltered since generation but one cannot prove these things to another without revealing the key and thereafter that key cannot be used to prove anything about any messages that were authenticated using that key see ansi x and fips for a standard method of message authentication using des what exactly is des des is the u s government s data encryption standard a product cipher that operates on bit blocks of data using a bit key it is defined in fips which supersedes fips fips are federal information processing standards published by ntis des is identical to the ansi standard data encryption algorithm dea defined in ansi x what is triple des triple des is a product cipher which like des operates on bit data blocks there are several forms each of which uses the des cipher times some forms use two bit keys some use three the des modes of operation may also be used with triple des some people refer to e k d k e k x as triple des this method is defined in chapter of the ansi standard x financial institution key management and is intended for use in encrypting des keys and ivs for automated key distribution its formal name is encryption and decryption of a single key by a key pair but it is referenced in other standards documents as ede that standard says section key encrypting keys may be a single dea key or a dea key pair key pairs shoud be used where additional security is needed e g the data protected by the key s has a long security life a key pair shall not be encrypted or decrypted using a single key others use the term triple des for e k d k e k x or e k e k e k x one of us carl ellison keeps advocating des triple use in the form e k tran e k tran e k compress x where each des instance has its own key and iv for cbc mode and tran has been posted on sci crypt it is a large block transposition program taking its key from the data stream itself so that it is not an encryption program on its own part what is differential cryptanalysis differential cryptanalysis is a statistical attack that can be applied to any iterated mapping ie any mapping which is based on a repeated round function the method was recently popularized by biham and shamir bih but coppersmith has remarked that the s boxes of des were optimized against this attack some years ago this method has proved effective against several product ciphers notably feal bi a differential cryptanalysis is based on observing a large number of ciphertexts y y whose corresponding plaintexts x x satisfy a known difference d x x where is componentwise xor in the basic biham shamir attack such plaintext pairs are required to determine the key for des substantially fewer pairs are required if des is truncated to or rounds in these cases the actual key can be recovered in a matter of minutes using a few thousand pairs for full des this attack is impractical because it requires so many known plaintexts the work of biham and shamir on des revealed several startling observations on the algorithm most importantly if the key schedule was removed from des and a bit key was used the key could be recovered in less than steps thus independent subkeys do not add substantial security to des further the s boxes of des are extremely sensitive in that changing even single entries in these tables yields significant improvement in the differential attack adi shamir is quoted to say nytimes oct i would say that contrary to what some people believe there is no evidence of tampering with the des so that the basic design was weakened how was nsa involved in the design of des according to kinnucan kin tuchman a member of the group that developed des at ibm is quoted as saying we developed the des algorithm entirely within ibm using ibmers the nsa did not dictate a single wire tuchman and meyer another developer of des spent a year breaking ciphers and finding weaknesses in lucifer they then spent two years strengthening lucifer their basic approach was to look for strong substitution permutation and key scheduling functions ibm has classified the notes containing the selection criteria at the request of the nsa the nsa told us we had inadvertently reinvented some of the deep secrets it uses to make its own algorithms explains tuchman on the other hand a document called involvement of the nsa in the development of des unclassified summary of the united states select committee on intelligence printed in the ieee communications magazine p states in the development of des nsa convinced ibm that a reduced keysize was sufficient indirectly assisted in the development of the s box structures and certified that the final des algorithm was to the best of their knowledge free from any statistical or mathematical weakness clearly the key size was reduced at the insistence of the nsa the article further states that the nsa did not tamper with the algorithm itself just the parameters which in some sense resolves the apparent conflict in the remarks of meyer and tuchman presented above is des available in software several people have made des code available via ftp see part for pathnames stig ostholm ftpso bsd ftpbk eric young ftpey dennis furguson ftpdf mark riordan ftpmr phil karn ftppk a pascal listing of des is also given in patterson pat fips says the algorithm specified in this standard is to be implemented using hardware not software technology software implementations in general purpose computers are not in compliance with this standard despite this software implementations abound and are used by government agencies is des available in hardware the following paragraphs are quoted from messages sent to the editors we don t vouch for the quality or even existence of the products chip rosenthal says dallas semiconductor makes a des encryption decryption device for use on standard digital kbps pcm telecom data streams it is capable of processing data in real time e g one sample frame it is the ds their phone number is you would probably need to talk with dewight in telecom marketing christian franke franke informatik rwth aachen de says cryptech cry c mbit s according to data sheet with bit interface we use this one because it was the only one available when we started the project no problems pijnenburg pcc mbit s according to data sheet address pijnenburg b v boxtelswweg nl ne vught the netherlands infosys des chip germany s boxes must be loaded by software so you can modify the algorithm sorry i don t have the data sheet handy please e mail me if you need further information mjr tis com marcus j ranum says supercrypt mb sec and faster des and proprietary storage for bit keys key stream generator integrated hardware des procedure extended mode with bit keys computer elektronik infosys a herndon parkway herndon va thember gandalf ca tim hember says newbridge microsystems sells an am compatible des chip that operates at mhz performs a round of encryption in clocks has a three stage pipeline supports ecb cbc cfb and cfb further it is very reasonable priced as opposed to other high end des chips call newbridge microsystems ottawa there are no import export issues with canada and the us if you require custom des or public key ics then timestep engineering developed newbridge s crypto chips and ics for other commercial and educational establishments they can be reached at can des be used to protect classified information des is not intended to protect classified data fips says this standard will be used by federal departments and agencies for the cryptographic protection of computer data when the following conditions apply cryptographic protection is required and the data is not classified according to the national security act of as amended or the atomic energy act of as amended what are ecb cbc cfb and ofb encryption these are methods for using block ciphers such as des to encrypt messages files and blocks of data known as modes of operation four modes of operation are defined in fips december and also in ansi x fips specifies that when bit ascii data is sent in octets the unused most significant bit is to be set to fips also specifies the padding for short blocks the four des modes of operation are electronic code book ecb cipher block chaining cbc k bit cipher feedback cfb and k bit output feedback ofb these methods are explained below in a c language like notation some symbols p n the n th block of plaintext input to encryption output from decryption size of block determined by the mode c n the n th block of ciphertext output from encryption input to decryption size of block determined by the mode e m the des encryption function performed on bit block m using the key schedule derived from some bit key d m the des decryption function performed on bit block m using the same key schedule as in e m except that the keys in the schedule are used in the opposite order as in e m iv a bit initialization vector a secret value which along with the key is shared by both encryptor and decryptor i n the n th value of a bit variable used in some modes r n the n th value of a bit variable used in some modes lsb m k the k least significant right most bits of m e g m k msb m k the k most significant left most bits of m e g m k k operators as defined in the c langage electronic code book ecb p n and c n are each bits long encryption decryption c n e p n p n d c n cipher block chaining cbc p n and c n are each bits long encryption decryption c e p iv p d c iv n c n e p n c n p n d c n c n k bit cipher feedback cfb p n and c n are each k bits long k encryption decryption i iv i iv n i n i n k c n i n i n k c n all n r n msb e i n k r n msb e i n k all n c n p n r n p n c n r n note that for k this reduces to i iv i iv n i n c n i n c n all n r n e i n r n e i n all n c n p n r n p n c n r n cfb notes since i n depends only on the plain or cipher text from the previous operation the e function can be performed in parallel with the reception of the text with which it is used k bit output feedback ofb p n and c n are each k bits long k encryption decryption i iv i iv n i n i n k r n i n i n k r n all n r n msb e i n k r n msb e i n k all n c n p n r n p n c n r n note that for k this reduces to i iv i iv n i n r n i n r n all n r n e i n r n e i n all n c n p n r n p n c n r n ofb notes encryption and decryption are identical since i n is independent of p and c the e function can be performed in advance of the receipt of the plain cipher text with which it is to be used additional notes on des modes of operation ecb and cbc use e to encrypt and d to decrypt but the feedback modes use e to both encrypt and decrypt this disproves the erroneous claim that systems which feature e but not d cannot be used for data confidentiality and therefore are not subject to export controls
