Cascade Ciphering


Terry Ritter


A Ciphers By Ritter Page


One of the fundamental problems in modern cryptography is that we cannot know whether the cipher we use is keeping our data secret. Our opponents work in secret and do not tell us of their success. So if our cipher exposes our data even after changing keys, our real -- but unknown to us -- insecurity will continue until we change ciphers. Yet conventional cryptography would have us use that same broken cipher forever.

I have often proposed that, instead of using a single unchanging cipher, we should protect our data under three ciphers with independent keys. Further, we should change these cipher "stacks" frequently. These ideas have a strong theoretical basis going back to Shannon.

The multiciphering proposal is the so-called "cascade" ciphering discussed here. Some people believe this is more dangerous than using a single cipher. But if using two ciphers was likely to be weaker than using just one, that would be a fine basis for an academic attack. We see no such attacks.

If we really want to use a particular cipher, we can make that part of each of our ciphering stacks. Then, if that cipher is strong, we have lost nothing but ciphering time. But if that cipher is weak, our information will be protected by the other ciphers in the stack.

The mere use of a cipher stack means that known-plaintext information is not exposed for any individual cipher. In practice, that is a very significant strength advantage.


Contents


Subject: Multiple encryptions Date: Thu, 08 Jun 2000 21:08:12 GMT From: AllanW <allan_w@my-deja.com> Message-ID: <8hp1vd$ja4$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 60 We have some encryption program E, and we use it whenever we send messages to each other. E is meant to take any plaintext (even non-printable data) and encrypt it, to transmit it safely to other sites. E identifies the encrypted data with a brief cleartext message at the start of it's output, to allow the decryption engine to avoid trying to decrypt data that never was encrypted. Therefore, anyone that can intercept our messages already knows we use encryption program E. Secretly, we also have another encryption program D. It isn't public knowledge, but what we really do is take our data files and encrypt them with D. Then we take the D output and feed that into E. Programs D and E know nothing of each other; each is meant to be used as a stand-alone encryption engine. D also appends some cleartext at the beginning of it's output, but of course E encrypts that so our use of D is *mostly* a secret. I've heard that this hypothetical case is a bad idea, and not just because of any false sense of security. Someone I respect tells me that the result is actually LESS secure than using either D or E alone. How can this be? Let's say that word leaks out that we're using D before we use E. Someone uses this knowledge to come up with frequency distribution or some other pattern for D's output. Perhaps it gives them a minor leg up on what output to expect from E. But can the result actually be easier to crack than cracking D or E alone? If you can explain why the answer is YES, then I have another related question: Suppose that D is a home-grown "security by obscurity" encryption engine that was never released to the public. Therefore it was never given public scrutiny, and it may in fact have one or more extreme weaknesses that anyone familiar with encryption (except the author) could have easily detect, if they got a chance to review the code and/or analyze the output. But, the source code is held by a few trusted individuals and the "encrypted" output is never retained after it's been fed to program E or returned out of program E, so there's no way to do frequency analysis or anything similar. Does your explanation to the first case still fit the second case? Obviously these cases are all hypothetical and I'm not advocating anyone actually doing this. I appreciate any explanations you can give me. -- Allan_W@my-deja.com is a "Spam Magnet," never read. Please reply in newsgroups only, sorry. Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: Multiple encryptions Date: 09 Jun 2000 08:12:17 EDT From: guymacon@deltanet.com (Guy Macon) Message-ID: <8hqmv1$a8h@chronicle.concentric.net> References: <8hp1vd$ja4$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 59 AllanW wrote: > > >We have some encryption program E, and we use it whenever >we send messages to each other. E is meant to take any >plaintext (even non-printable data) and encrypt it, to >transmit it safely to other sites. E identifies the >encrypted data with a brief cleartext message at the >start of it's output, to allow the decryption engine to >avoid trying to decrypt data that never was encrypted. >Therefore, anyone that can intercept our messages already >knows we use encryption program E. > >Secretly, we also have another encryption program D. It >isn't public knowledge, but what we really do is take our >data files and encrypt them with D. Then we take the D >output and feed that into E. Programs D and E know >nothing of each other; each is meant to be used as a >stand-alone encryption engine. D also appends some >cleartext at the beginning of it's output, but of course >E encrypts that so our use of D is *mostly* a secret. > >I've heard that this hypothetical case is a bad idea, and >not just because of any false sense of security. Someone I >respect tells me that the result is actually LESS secure >than using either D or E alone. > >How can this be? Let's look at the degenerative cases; Assume that D and E are the exact same stream cipher with the same key, salt, etc., each of which uses XOR to encrypt. In that case, they undo each other. So clearly you can't say that multiple encryption never decreases security. Now assume that D and E are OTP ciphers with different random keys, again using XOR to encrypt. In that case, you have increased your security by exactly zero. So clearly you can't say that multiple encryption always increases security. Now assume that D and E are unrelated and hard (but not impossible) to break. Your security is greatly increased in this case. So clearly you can't say that multiple encryption never increases security. Now for the $64,000 question: Are you ABSOLUTLY SURE that the two methods are not related in some subtle way? Has the combo of D then E been subjected to the sophisticated attacks and extensive analysis that E alone has survived?
Subject: Re: Multiple encryptions Date: Fri, 09 Jun 2000 05:37:35 -0700 From: jkauffman <jeremy_kauffmanNOjeSPAM@hotmail.com.invalid> Message-ID: <11f733ec.78f1fbc3@usw-ex0109-069.remarq.com> References: <8hqmv1$a8h@chronicle.concentric.net> Newsgroups: sci.crypt Lines: 45 In article <8hqmv1$a8h@chronicle.concentric.net>, guymacon@deltanet.com (Guy Macon) wrote: > Let's look at the degenerative cases; > Assume that D and E are the exact same stream cipher > with > the same key, salt, etc., each of which uses XOR to > encrypt. > In that case, they undo each other. So clearly you > can't say > that multiple encryption never decreases security. > Now assume that D and E are OTP ciphers with different > random > keys, again using XOR to encrypt. In that case, you > have > increased your security by exactly zero. So clearly > you > can't say that multiple encryption always increases > security. > Now assume that D and E are unrelated and hard (but not > impossible) to break. Your security is greatly > increased > in this case. So clearly you can't say that multiple > encryption never increases security. > Now for the $64,000 question: Are you ABSOLUTLY SURE > that the > two methods are not related in some subtle way? Has > the combo > of D then E been subjected to the sophisticated > attacks and > extensive analysis that E alone has survived? But surely if the combination of D & E is weaker than alone then D represents the first stage of a cryptoanalytic attack on E. And if D was developed independently of E then this attack would be by pure chance. Another way of looking at it is that if E is a secure cipher it must be secure no matter what the input. This includes normal ASCII text, bitmaps, letters to Grandmother and the output of D. If its security can be compromised by chosing certain inputs then it is not a good cipher. * Sent from AltaVista http://www.altavista.com Where you can also find related Web Pages, Images, Audios, Videos, News, and Shopping. Smart is Beautiful
Subject: Re: Multiple encryptions Date: Mon, 12 Jun 2000 05:43:15 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <Fw1183.Fny@bath.ac.uk> References: <8ht8it$c2l@journal.concentric.net> <11f733ec.78f1fbc3@usw-ex0109-069.remarq.com> Newsgroups: sci.crypt Lines: 35 Guy Macon <guymacon@deltanet.com> wrote: : jkauffman wrote: :>But surely if the combination of D & E is weaker than alone :>then D represents the first stage of a cryptoanalytic attack :>on E. And if D was developed independently of E then this :>attack would be by pure chance. : "D was developed independently of E" is not the same as : "D is independent of E". Maybe the two developers had : the same bright idea. [...] If so it is irrelevant to the argument given. If D(E(P)) is weaker than E(P) (with independent keys) then application of D constitutes a cryptanalytic attack on E - and consequently most peoiple would say that E is broken. :>Another way of looking at it is that if E is a secure cipher :>it must be secure no matter what the input. This includes :>normal ASCII text, bitmaps, letters to Grandmother and the :>output of D. If its security can be compromised by chosing :>certain inputs then it is not a good cipher. : Then any cipher that uses XOR with the plaintext as a final step : is not a secure cipher, because if I choose to use as my plaintext : my original plaintext encrypted with the same algorithm and key, : then the output is my original plaintext. [...] That is an example of choosing the plaintext *and* the key. If a cypher is weakened by choosing just the plaintext, that would be a problem - resulting in chosen-plaintext attacks. -- __________ Lotus Artificial Life http://alife.co.uk/ tt@cryogen.com |im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
Subject: Re: Multiple encryptions Date: Mon, 12 Jun 2000 05:54:25 -0700 From: tomstd <tomNOtoSPAM@dasoft.org.invalid> Message-ID: <114ddc1b.e0cc0f4a@usw-ex0104-031.remarq.com> References: <0615c12f.e9d31f2b@usw-ex0109-069.remarq.com> <8ht8it$c2l@journal.concentric.net> <11f733ec.78f1fbc3@usw-ex0109-069.remarq.com> Newsgroups: sci.crypt Lines: 34 In article <0615c12f.e9d31f2b@usw-ex0109-069.remarq.com>, jkauffman <jeremy_kauffmanNOjeSPAM@hotmail.com.invalid> wrote: >In article <8ht8it$c2l@journal.concentric.net>, >guymacon@deltanet.com (Guy Macon) wrote: >> jkauffman wrote: >> > >> >But surely if the combination of D & E is weaker than >> alone >> >then D represents the first stage of a cryptoanalytic >> attack >> >on E. And if D was developed independently of E then >> this >> >attack would be by pure chance. >> "D was developed independently of E" is not the same as >> "D is independent of E". Maybe the two developers had >> the same bright idea. Maybe there is a suptle >> interaction >> that you haven't forseen. > >Presumably an attacker knows the full details of E, and so >having the same bright idea has nothing to do with it. If it >is possible to design D maliciously such that applying it to >E weakens E then this is an attack and E is not secure. As >long as I dont know the key used with E there should be >nothing I can do to weaken it. If D and E are truly independent keywise then there is nothing E can do to D (assuming a "E o D" construction) to weaken it. Tom * Sent from RemarQ http://www.remarq.com The Internet's Discussion Network * The fastest and easiest way to search and participate in Usenet - Free!
Subject: Re: Multiple encryptions Date: 12 Jun 2000 09:32:39 EDT From: guymacon@deltanet.com (Guy Macon) Message-ID: <8i2opn$pr8@journal.concentric.net> References: <0615c12f.e9d31f2b@usw-ex0109-069.remarq.com> <8ht8it$c2l@journal.concentric.net> <11f733ec.78f1fbc3@usw-ex0109-069.remarq.com> Newsgroups: sci.crypt Lines: 29 jkauffman wrote: > > >In article <8ht8it$c2l@journal.concentric.net>, >guymacon@deltanet.com (Guy Macon) wrote: >> jkauffman wrote: >> > >> >But surely if the combination of D & E is weaker than >> alone >> >then D represents the first stage of a cryptoanalytic >> attack >> >on E. And if D was developed independently of E then >> this >> >attack would be by pure chance. >> "D was developed independently of E" is not the same as >> "D is independent of E". Maybe the two developers had >> the same bright idea. Maybe there is a suptle >> interaction >> that you haven't forseen. > >Presumably an attacker knows the full details of E, and so >having the same bright idea has nothing to do with it. If it >is possible to design D maliciously such that applying it to >E weakens E then this is an attack and E is not secure. As >long as I dont know the key used with E there should be >nothing I can do to weaken it. Point well taken. I retract my statement. I was clearly wrong.
Subject: Re: Multiple encryptions Date: Fri, 09 Jun 2000 10:39:11 -0600 From: John Myre <jmyre@sandia.gov> Message-ID: <39411DAF.29C4BA77@sandia.gov> References: <8hqmv1$a8h@chronicle.concentric.net> Newsgroups: sci.crypt Lines: 36 Guy Macon wrote: > [An excellent analysis of composing ciphers] Is this in the FAQ? It ought to be. To the OP: the point about possibly getting a weaker system by composing ciphers can be taken in two ways. In a practical sense, it means you need to avoid the degenerate cases that Guy mentioned, and things like them. This should not be too hard, but you can see that inexperienced people could make mistakes. In a theoretical sense, the statement about weakness is just a statement about ignorance. A general composition of ciphers could be stronger, or weaker, or the same, depending on details. See Guy's post for examples. Also, it is often true that in a specific case, even after competent and lengthy study, we just don't *know*. We may have an intuition, which is probably right, but we can't *prove* it. Finally, it should be pointed out that some crypto types express annoyance at those who espouse doing something extra "because it can't hurt, and could help." It depends on the application, of course, but if one of the two ciphers really is strong (enough so that your opponents can't break it, at all), the extra steps don't help security, and could compromise it (just through the extra complexity it adds to the system). For example, say the extra cipher is fine, but the program that uses it sometimes copies the plaintext out to the internet (oops!). Of course that is a programming error, and has nothing to do with cryptology, per se. But the fewer programs you write, the less there is to go wrong. I must admit to feeling ambivalent on this point. If *I* write it, it will work, but if someone else does, I'm suspicious. Oh well, we all have our weak points; I guess that's one of mine. :) John M.
Subject: Re: Multiple encryptions Date: Mon, 12 Jun 2000 05:51:15 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <Fw11LF.Fz5@bath.ac.uk> References: <39411DAF.29C4BA77@sandia.gov> Newsgroups: sci.crypt Lines: 26 John Myre <jmyre@sandia.gov> wrote: : In a theoretical sense, the statement about weakness is just a : statement about ignorance. A general composition of ciphers could : be stronger, or weaker, or the same, depending on details. See Guy's : post for examples. Also, it is often true that in a specific case, : even after competent and lengthy study, we just don't *know*. We may : have an intuition, which is probably right, but we can't *prove* it. We can't do this for the component cyphers either - so the inability to do so for their composition should be no great suprise. : Finally, it should be pointed out that some crypto types express : annoyance at those who espouse doing something extra "because it : can't hurt, and could help." It depends on the application, of : course, but if one of the two ciphers really is strong (enough so : that your opponents can't break it, at all), the extra steps don't : help security, and could compromise it (just through the extra : complexity it adds to the system). Alas, nobody ever /knows/ that their cypher is strong - especially if their messages are longer than their keys. Consequently, adding strength can often appear to be an attractive proposition. -- __________ Lotus Artificial Life http://alife.co.uk/ tt@cryogen.com |im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
Subject: Re: Multiple encryptions Date: Fri, 9 Jun 2000 16:06:50 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <FvwA3E.Ev2@bath.ac.uk> References: <8hp1vd$ja4$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 39 AllanW <allan_w@my-deja.com> wrote: : We have some encryption program E [which] is meant to take any : plaintext (even non-printable data) and encrypt it, to : transmit it safely to other sites. E identifies the : encrypted data with a brief cleartext message at the : start of it's output, to allow the decryption engine to : avoid trying to decrypt data that never was encrypted. [...] : Secretly, we also have another encryption program D. It : isn't public knowledge, but what we really do is take our : data files and encrypt them with D. Then we take the D : output and feed that into E. Programs D and E know : nothing of each other; each is meant to be used as a : stand-alone encryption engine. D also appends some : cleartext at the beginning of it's output, but of course : E encrypts that [...] : I've heard that this hypothetical case is a bad idea, and : not just because of any false sense of security. Someone I : respect tells me that the result is actually LESS secure : than using either D or E alone. You have known-plaintext in both inputs to the respective cyphers. If there's a partial-known plaintext attack against both cyphers, the scheme migh be weaker than either alone - if known plaintext were otherwise not common. If you don't add in the known plaintext, then this is an orthodox cypher stack - which is likely to be stronger than either cypher alone. : Suppose that D is a home-grown "security by obscurity" : encryption engine that was never released to the public. [...] This makes little difference - a pretty fundamental principle is to assume that the attacker has access to the cyphermachine. -- __________ Lotus Artificial Life http://alife.co.uk/ tt@cryogen.com |im |yler The Mandala Centre http://mandala.co.uk/ Breast is best.
Subject: Re: Multiple encryptions Date: Fri, 09 Jun 2000 12:43:58 -0500 From: James Felling <james.felling@mail.arcanelogic.com> Message-ID: <39412CDE.C3C5FBAC@mail.arcanelogic.com> References: <8hp1vd$ja4$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 80 AllanW wrote: > We have some encryption program E, and we use it whenever > we send messages to each other. E is meant to take any > plaintext (even non-printable data) and encrypt it, to > transmit it safely to other sites. E identifies the > encrypted data with a brief cleartext message at the > start of it's output, to allow the decryption engine to > avoid trying to decrypt data that never was encrypted. > Therefore, anyone that can intercept our messages already > knows we use encryption program E. > > Secretly, we also have another encryption program D. It > isn't public knowledge, but what we really do is take our > data files and encrypt them with D. Then we take the D > output and feed that into E. Programs D and E know > nothing of each other; each is meant to be used as a > stand-alone encryption engine. D also appends some > cleartext at the beginning of it's output, but of course > E encrypts that so our use of D is *mostly* a secret. > > I've heard that this hypothetical case is a bad idea, and > not just because of any false sense of security. Someone I > respect tells me that the result is actually LESS secure > than using either D or E alone. > > How can this be? As a rule unless D and E are some how related this is at least as strong as the stronger of D and E, and may well be stronger than that. However, to using lame examples it can be shown that if D and E are related the potential of compromise exists. i.e. if D= N*Message mod P, and E= X* Message Mod P, then D(E(Message)) is as secure as D or E except when N*X mod P =1 in which D(E(message))=Message. so the system is no stronger, and can be weaker. So long as D and E do not work by similar mechanisms there will be little risk of this occuring though -- effectively 0 if you choose D and E with care. > > > Let's say that word leaks out that we're using D before we > use E. Someone uses this knowledge to come up with > frequency distribution or some other pattern for D's > output. Perhaps it gives them a minor leg up on what output > to expect from E. But can the result actually be easier to > crack than cracking D or E alone? > > If you can explain why the answer is YES, then I have > another related question: > > Suppose that D is a home-grown "security by obscurity" > encryption engine that was never released to the public. > Therefore it was never given public scrutiny, and it may in > fact have one or more extreme weaknesses that anyone > familiar with encryption (except the author) could have > easily detect, if they got a chance to review the code > and/or analyze the output. But, the source code is held by > a few trusted individuals and the "encrypted" output is > never retained after it's been fed to program E or returned > out of program E, so there's no way to do frequency analysis > or anything similar. Does your explanation to the first case > still fit the second case? > > Obviously these cases are all hypothetical and I'm not > advocating anyone actually doing this. I appreciate any > explanations you can give me. > > -- > Allan_W@my-deja.com is a "Spam Magnet," never read. > Please reply in newsgroups only, sorry. > > Sent via Deja.com http://www.deja.com/ > Before you buy.
Subject: Re: Multiple encryptions Date: 10 Jun 2000 07:38:54 EDT From: guymacon@deltanet.com (Guy Macon) Message-ID: <8ht9ce$fuo@chronicle.concentric.net> References: <39412CDE.C3C5FBAC@mail.arcanelogic.com> Newsgroups: sci.crypt Lines: 19 James Felling wrote: >So long as D and E do not work by similar mechanisms there will be >little risk of this occurring though -- effectively 0 if you choose >D and E with care. I fully agree with the above. I, of course, am a clueless newbie who lacks the ability to choose the two methods with care, and the top crypto experts may make a mistake when choosing the two methods with care. The probability of them doing so is almost certainly higher than the probability of the first method being cracked. That being said, I think that I can prove that the two methods are unrelated and therefor not weaker than either one alone if one of the methods it OTP. I have a gut feeling that making the two methods symmetric key and asymmetric key will make them unrelated, but I can't prove it.
Subject: Re: Multiple encryptions Date: Mon, 12 Jun 2000 12:15:13 -0500 From: James Felling <james.felling@mail.arcanelogic.com> Message-ID: <39451AA1.8D28DCBC@mail.arcanelogic.com> References: <8ht9ce$fuo@chronicle.concentric.net> Newsgroups: sci.crypt Lines: 33 Guy Macon wrote: > James Felling wrote: > > >So long as D and E do not work by similar mechanisms there will be > >little risk of this occurring though -- effectively 0 if you choose > >D and E with care. > > I fully agree with the above. I, of course, am a clueless newbie > who lacks the ability to choose the two methods with care, and the > top crypto experts may make a mistake when choosing the two methods > with care. The probability of them doing so is almost certainly > higher than the probability of the first method being cracked. I don't know about that. Examine them with a reasonable amount of scrutiny -- if one uses MXN Sboxes then the other shouldn't -- but KxL sboxes are probably OK, if one uses data dependent rotations, the other shouldn't, maybe make one a stream cypher and the other a block cypher -- that kind of thing. If you can manage this (and I am confident that you can) it is still POSSIBLE that you might have some element of relation between the two, but frankly the odds of that are much lower than the odds of your being struck by lighting -- repeatedly. > > > That being said, I think that I can prove that the two methods are > unrelated and therefor not weaker than either one alone if one of > the methods it OTP. I have a gut feeling that making the two methods > symmetric key and asymmetric key will make them unrelated, but I can't > prove it.
Subject: Re: Multiple encryptions Date: Mon, 12 Jun 2000 22:07:45 GMT From: AllanW <allan_w@my-deja.com> Message-ID: <8i3mv8$p64$1@nnrp1.deja.com> References: <8ht9ce$fuo@chronicle.concentric.net> Newsgroups: sci.crypt Lines: 24 Thank you all for your responses. I think that the general consensus is that E o D is OFTEN more secure than either E or D, other than degenerate cases. But there's a sense that we don't know how much more secure it is, and some concern that if we've stumbled across one of the degenerate cases we might not realize it. So we need to spend effort ensuring that D and E use algorithms that aren't related to each other. Using D=E, even with different keys, is a Bad Thing(tm). Using one symmetric key algorithm with one asymmetric key algorithm might be enough to ensure success, although of course nobody's making any promises. Have I got this right? Thanks again for your feedback. -- Allan_W@my-deja.com is a "Spam Magnet," never read. Please reply in newsgroups only, sorry. Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: Multiple encryptions Date: Tue, 13 Jun 2000 21:03:43 GMT From: "Douglas A. Gwyn" <gwyn@arl.mil> Message-ID: <3946A1AF.843F0C35@arl.mil> References: <8i3mv8$p64$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 5 AllanW wrote: > I think that the general consensus is that E o D is OFTEN > more secure than either E or D, other than degenerate cases. For a counterexample, see the most recent issue of Cryptologia.
Subject: Re: Multiple encryptions Date: Tue, 13 Jun 2000 01:57:05 GMT From: Bryan Olson <bryanolson@my-deja.com> Message-ID: <8i44db$2b7$1@nnrp1.deja.com> References: <8hp1vd$ja4$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 33 AllanW wrote: > We have some encryption program E, [...] > what we really do is take our > data files and encrypt them with D. Then we take the D > output and feed that into E. [...] > I've heard that this hypothetical case is a bad idea, and > not just because of any false sense of security. Someone I > respect tells me that the result is actually LESS secure > than using either D or E alone. If the keys are independant, then against ciphertext-only or known plaintext, the composition must be at least as strong as the first cipher applied, but there's a theoretical possibility that the chain is not as strong as the second cipher. See: Ueli M. Maurer and James L. Massey. Cascade ciphers: The importance of being first. Journal of Cryptology, 6(1):55-61, 1993. Against chosen plaintext, (again assuming independent keys) the composition must be at least as strong as the stronger of the two. --Bryan -- email: bolson at certicom dot com Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: Multiple encryptions Date: 13 Jun 2000 05:12:37 EDT From: guymacon@deltanet.com (Guy Macon) Message-ID: <8i4tu5$4kt@chronicle.concentric.net> References: <3945E70A.5DBB1E56@t-online.de> <8i44db$2b7$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 43 Mok-Kong Shen wrote: > >Does the requirement 'the keys are independent' somehow >implicitly also involve the additional requirement 'the ciphers are >independent in design' (which is presumably difficult to ascertain >in the absolute sense)? For otherwise I am afraid that counter- >example could be constructed such that a combination of two >ciphers is weaker than a single one. > That was exactly my reasoning until yesterday, when I read a post here and saw the light. Let me explain where we both went wrong in our thinking: Let's say that you have a good, strong cipher. Good, strong ciphers are strong even if the attacker knows the algorithm, can select plaintexts and have you encrypt them with your key, can intercept your ciphertext and repalace it with his own, who knows the length of your plaintext, and any other ability you can name except for knowing your plaintext or your key. In fact, the best cipher creators make it a point to supply all of the above to everyone and to encourage knowlwdgable attackers to try to break the system. Only after many such attacks by many people do we say that a cipher might be strong. Keeping the above facts in mind, let's assume that a combination of the strong cypher with another one (maybe the same one!) weakens the strong cipher. If it does, then you can attack someone who uses the strong cipher alone by taking his ciphertext and encrypting it with this second cipher. Using the same key is unfair, of course - we already know that giving the attacker the key or the plaintext "breaks" any conceivable cipher in a trivial way, so our attacker can use the same cipher twice but he can't do it with the same key because he doesn't know what the key is. Thus, if the second cipher weakens the first, then the first wasn't a strong cipher in the first place. This is what I love about this field. Common sense tells me that I might weaken a strong cipher by using a second cipher, but once it is explained to me, logic tells me that my common sense was wrong. Common sense tells me that no cipher is immune to a brute force attack by someone with infinite resources, cleverness, and time, but once OTP was explained to me, logic told me that my common sense was wrong. I love it!
Subject: Maurer & Massey's result on cascade ciphers (was: Multiple encryptions) Date: Tue, 13 Jun 2000 08:32:42 -0400 From: Nicol So <nobody@no.spam.please> Message-ID: <394629EA.51AD54CD@no.spam.please> References: <8i44db$2b7$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 31 Bryan Olson wrote: > > If the keys are independant, then against ciphertext-only or > known plaintext, the composition must be at least as strong > as the first cipher applied, but there's a theoretical > possibility that the chain is not as strong as the second > cipher. See: > Ueli M. Maurer and James L. Massey. Cascade ciphers: > The importance of being first. Journal of Cryptology, > 6(1):55-61, 1993. > > Against chosen plaintext, (again assuming independent keys) > the composition must be at least as strong as the stronger > of the two. I've had a problem with the result of Maurer and Massey for a long time. Basically, I think the result is "wrong". The (counter-)example they gave in the paper does not demonstrate the informal statement of the result. The definition of a secure cipher implicitly used in the paper is, in my opinion, unnatural. For a cipher to be secure, it should be secure w.r.t. all distributions of inputs. That's not the case with the "secure" ciphers in their example. [I don't have the paper handy and it's been a long while since I last look at it, so I could be missing something. Anyone interested in the problem should read the paper to see if my objection correctly applies.] -- Nicol So, CISSP // paranoid 'at' engineer 'dot' com Disclaimer: Views expressed here are casual comments and should not be relied upon as the basis for decisions of consequence.
Subject: Re: Maurer & Massey's result on cascade ciphers (was: Multiple encryptions) Date: 14 Jun 2000 15:12:24 -0700 From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner) Message-ID: <8i9008$g5k$1@blowfish.isaac.cs.berkeley.edu> References: <394629EA.51AD54CD@no.spam.please> Newsgroups: sci.crypt Lines: 42 In article <394629EA.51AD54CD@no.spam.please>, Nicol So <see.signature> wrote: > Bryan Olson wrote: > > Ueli M. Maurer and James L. Massey. Cascade ciphers: > > The importance of being first. Journal of Cryptology, > > 6(1):55-61, 1993. > > > Against chosen plaintext, (again assuming independent keys) > > the composition must be at least as strong as the stronger > > of the two. > > I've had a problem with the result of Maurer and Massey for a long time. > Basically, I think the result is "wrong". The (counter-)example they > gave in the paper does not demonstrate the informal statement of the > result. The definition of a secure cipher implicitly used in the paper > is, in my opinion, unnatural. For a cipher to be secure, it should be > secure w.r.t. all distributions of inputs. That's not the case with the > "secure" ciphers in their example. It sounds like you don't care too much for their definitions; you prefer different ones. That's ok. Their point remains. If all we care about is ciphertext-only security when the plaintext is distributed like ASCII English, and if the _only_ way we ever measure security is via this threat model, then a cascade of two ciphers may be weaker (_under this metric_) than the second cipher. I agree that, as you say, in practice our metrics are much more demanding. We insist that our ciphers be secure not just against plaintext distributed like English is, but against plaintext that is _chosen by the attacker_. Note that the chosen-plaintext security requirement is an even stronger requirement than just insisting that the cipher be secure for all plaintext free to _adaptively_ choose the plaintexts. And, yes, as Bryan Olson says, under this more demanding chosen-plaintext metric, the cascade is indeed at least as strong as the stronger of the two ciphers, as we'd intuitively hope and expect. The contribution of the Maurer and Massey paper, as I see it, is to show that this intuition need not hold true for all metrics, and indeed, there are some semi-reasonable metrics where our intuitive expectation is wrong. It doesn't mean that cascades don't work; it just means we need to be careful about our expectations. That's interesting, IMHO.
Subject: Re: Maurer & Massey's result on cascade ciphers (was: Multiple encryptions) Date: Wed, 14 Jun 2000 22:38:56 GMT From: Bryan Olson <bryanolson@my-deja.com> Message-ID: <8i91hu$l31$1@nnrp1.deja.com> References: <394629EA.51AD54CD@no.spam.please> Newsgroups: sci.crypt Lines: 28 Nicol So wrote: > I've had a problem with the result of Maurer and Massey for a > long time. > Basically, I think the result is "wrong". The (counter-)example they > gave in the paper does not demonstrate the informal statement of the > result. The definition of a secure cipher implicitly used in the paper > is, in my opinion, unnatural. For a cipher to be secure, it should be > secure w.r.t. all distributions of inputs. That's not the case with > the "secure" ciphers in their example. You have a point. I tried to avoid those difficulties by clearly separating the chosen-plaintext case, and referring the weakening as a "theoretical possibility". But I agree that the papers results are somewhat silly. The "folk theorem" they deride is basically correct, and the point that the attacker cannot insert a step between the plaintext and the first encryption seems trivial for a journal article. --Bryan -- email: bolson at certicom dot com Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Q: Cascading multiple block algorithms Date: Fri, 21 Jul 2000 23:02:02 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3978BA4A.272972A2@t-online.de> Newsgroups: sci.crypt Lines: 19 In Schneier's AC, p.367, about cascading two block ciphers it is stated: If the second algorithm is vulnerable to a chosen-plaintext attack, then the first algorithm might facilitate that attack and make the second algorithm vulnerable to a known- plaintext attack when used in a cascade. This isn't very clear for me. In which way can the first algorithm facilitate the chosen-plaintext attack on the second algorithm? Since now there is a cascade, the 'known-plaintext' above must refer to the input to the first algorithm, isn't it? And the 'chosen-plaintext' certainly refers to the second algorithm, right? I am confused. Could someone please explain the issue with a bit detail? Thanks in advance. M. K. Shen
Subject: Re: Q: Cascading multiple block algorithms Date: Fri, 21 Jul 2000 22:55:42 +0200 From: Ichinin <ichinin@suespammers.org> Message-ID: <3978B8CE.731F@suespammers.org> References: <3978BA4A.272972A2@t-online.de> Newsgroups: sci.crypt Lines: 9 Mok-Kong Shen wrote: <Snip> I think what he is saying is that the strenght of the (cascade) crypto is as weak as the weakest algorithm. (why hit a tank from the side when the top armour is weaker?) /Ichinin
Subject: Re: Q: Cascading multiple block algorithms Date: Sat, 22 Jul 2000 01:31:18 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3978f921.3618065@news.io.com> References: <3978B8CE.731F@suespammers.org> Newsgroups: sci.crypt Lines: 20 On Fri, 21 Jul 2000 22:55:42 +0200, in <3978B8CE.731F@suespammers.org>, in sci.crypt Ichinin <ichinin@suespammers.org> wrote: >[...] >I think what he is saying is that the strenght of the (cascade) >crypto is as weak as the weakest algorithm. He may be saying that, but it's wrong. >(why hit a tank from the side when the top armour is weaker?) Why build a tank with just one layer of armor? --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Cascading multiple block algorithms Date: Sat, 22 Jul 2000 10:19:07 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <397958FB.89D9B62F@t-online.de> References: <3978BA4A.272972A2@t-online.de> Newsgroups: sci.crypt Lines: 43 Mok-Kong Shen wrote: > In Schneier's AC, p.367, about cascading two block ciphers it > is stated: > > If the second algorithm is vulnerable to a chosen-plaintext > attack, then the first algorithm might facilitate that > attack and make the second algorithm vulnerable to a known- > plaintext attack when used in a cascade. Perhaps I may explain what difficulty I have in reading the sentence above. The premise 'If the second algorithm is vulnerable to a chosen-plaintext attack' means (to me) that, if its (direct) input can be chosen, then it can be cracked. Now that input is the output from the first algorithm. It cannot be directly chosen but only indireclty through choosing input to the first algorithm. This indirectness, assuming that the first algorithm has any strength at all, evidently means that the said attack is now more difficult. Given this fact, I can't understand the phrase 'the first algorithm might facilitate that attack', which I interpret to be the claim that the said attack has now become easier (i.e. easier than directly choosing input to the second algorithm). Finally I then can't understand 'make the second algorithm vulnerable to a known-plaintext attack'. For I can't see what this 'known-plaintext' refers to. It can't refer to the input to the second algorithm, because that's the output of the first algorithm and is not 'known', unless the analyst has already cracked the first algorithm. If it is the input to the first algorithm, then it is also senseless, since we have in the above already assumed that the analyst can choose input to the first algorithm so that he can obtain some (for him) more advantageous input to the second algorithm. (Assuming chosen- plaintext includes assuming known-plaintext, isn't it?) I don't exclude that my inability of comprehension is simply a result of my poor English language competence. You help will be sincerely appreciated. M. K. Shen
Subject: Re: Q: Cascading multiple block algorithms Date: Sat, 22 Jul 2000 19:02:42 GMT From: Bryan Olson <bryanolson@my-deja.com> Message-ID: <8lcr4a$j0j$1@nnrp1.deja.com> References: <397958FB.89D9B62F@t-online.de> Newsgroups: sci.crypt Lines: 42 Mok-Kong Shen wrote: > > > Mok-Kong Shen wrote: > > > In Schneier's AC, p.367, about cascading two block ciphers it > > is stated: > > > > If the second algorithm is vulnerable to a chosen-plaintext > > attack, then the first algorithm might facilitate that > > attack and make the second algorithm vulnerable to a known- > > plaintext attack when used in a cascade. > [...] > Now that input is the output from the first algorithm. It > cannot be directly chosen but only indireclty through choosing > input to the first algorithm. This indirectness, assuming that > the first algorithm has any strength at all, evidently means > that the said attack is now more difficult. The statement doesn't say there's any realistic chance of this happening. It's a possibility we cannot disprove, and we can create contrived situations to illustrate it, but we certainly don't expect it with reasonable ciphers. In known plaintext attack, the attacker is limited to the given plaintext distribution. Putting another cipher in front could result in a distribution much worse for the second cipher. Suppose you have a block cipher that's very strong if the first bit of the plaintext block is always 0, but terrible when the first bit is one. It's vulnerable to chosen plaintext, but when used to send ASCII text it's strong. --Bryan -- email: bolson at certicom dot com Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: Q: Cascading multiple block algorithms Date: Mon, 24 Jul 2000 09:47:20 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <397BF487.6DA045AA@t-online.de> References: <8lcr4a$j0j$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 59 Bryan Olson wrote: > Mok-Kong Shen wrote: > > Mok-Kong Shen wrote: > > > In Schneier's AC, p.367, about cascading two block ciphers it > > > is stated: > > > > > > If the second algorithm is vulnerable to a chosen-plaintext > > > attack, then the first algorithm might facilitate that > > > attack and make the second algorithm vulnerable to a known- > > > plaintext attack when used in a cascade. > > > [...] > > Now that input is the output from the first algorithm. It > > cannot be directly chosen but only indireclty through choosing > > input to the first algorithm. This indirectness, assuming that > > the first algorithm has any strength at all, evidently means > > that the said attack is now more difficult. > > The statement doesn't say there's any realistic chance of > this happening. It's a possibility we cannot disprove, and > we can create contrived situations to illustrate it, but we > certainly don't expect it with reasonable ciphers. > > In known plaintext attack, the attacker is limited to the > given plaintext distribution. Putting another cipher in > front could result in a distribution much worse for the > second cipher. Suppose you have a block cipher that's very > strong if the first bit of the plaintext block is always 0, > but terrible when the first bit is one. It's vulnerable to > chosen plaintext, but when used to send ASCII text it's > strong. However, 'chosen-plaintext attack' without further qualification means to the reader that it is the general case, i.e. the analyst can choose ANY plaintext he likes. With an intermediate (first) algorithm, his choice of the input to the second algorithm is evidently limited, unless he has already cracked the first algorithm somehow. Anyway, the presence of the first algorithm (which is at issue in the present context) can't have any negative effect on the second algorithm in aspect of its susceptibility to chosen- plaintext attack (with the term understood as such). While AC does refer to the attack as a 'potential attack', it says: If you let someone lese specify any algorithm which is used on you message before encryption, then you had better be sure that your encryption will withstand a chose-plaintext attack. which sounds like that the possibility discussed is not entirely imaginary/theoretical but could indeed very well happen in actual practice. M. K. Shen
Subject: Re: Q: Cascading multiple block algorithms Date: Mon, 24 Jul 2000 18:13:44 GMT From: Bryan Olson <bryanolson@my-deja.com> Message-ID: <8li10k$1u2$1@nnrp1.deja.com> References: <397BF487.6DA045AA@t-online.de> Newsgroups: sci.crypt Lines: 78 Mok-Kong Shen > > Bryan Olson wrote: > > > Mok-Kong Shen wrote: > > > Mok-Kong Shen wrote: > > > > In Schneier's AC, p.367, about cascading two block ciphers it > > > > is stated: > > > > > > > > If the second algorithm is vulnerable to a chosen-plaintext > > > > attack, then the first algorithm might facilitate that > > > > attack and make the second algorithm vulnerable to a known- > > > > plaintext attack when used in a cascade. > > > > > [...] > > > Now that input is the output from the first algorithm. It > > > cannot be directly chosen but only indireclty through choosing > > > input to the first algorithm. This indirectness, assuming that > > > the first algorithm has any strength at all, evidently means > > > that the said attack is now more difficult. > > > > The statement doesn't say there's any realistic chance of > > this happening. It's a possibility we cannot disprove, and > > we can create contrived situations to illustrate it, but we > > certainly don't expect it with reasonable ciphers. > > > > In known plaintext attack, the attacker is limited to the > > given plaintext distribution. Putting another cipher in > > front could result in a distribution much worse for the > > second cipher. Suppose you have a block cipher that's very > > strong if the first bit of the plaintext block is always 0, > > but terrible when the first bit is one. It's vulnerable to > > chosen plaintext, but when used to send ASCII text it's > > strong. > > However, 'chosen-plaintext attack' without further qualification > means to the reader that it is the general case, i.e. the analyst > can choose ANY plaintext he likes. Yes. > With an intermediate (first) > algorithm, his choice of the input to the second algorithm is > evidently limited, unless he has already cracked the first algorithm > somehow. Anyway, the presence of the first algorithm (which is at > issue in the present context) can't have any negative effect on > the second algorithm in aspect of its susceptibility to chosen- > plaintext attack (with the term understood as such). So adding the first algorithm (assuming independant keys) will not result in a chain weaker against chosen plaintext than is the second algorithm alone. By "facilitate the attack" Schneier means provide an opportunity to launch it where the system did not directly allow the attacker to choose plaintext. > While AC does refer to the attack as a 'potential attack', it says: > > If you let someone lese specify any algorithm which is > used on you message before encryption, then you had > better be sure that your encryption will withstand a > chose-plaintext attack. > > which sounds like that the possibility discussed is not entirely > imaginary/theoretical but could indeed very well happen in actual > practice. The problem here is not that two ciphers combined are likely to be weaker, but that the "any algorithm" need not be a realistic cipher, and the "someone" may even be the attacker. --Bryan -- email: bolson at certicom dot com Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: Q: Cascading multiple block algorithms Date: Mon, 24 Jul 2000 22:56:16 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <397CAD6F.9FF0DA27@t-online.de> References: <8li10k$1u2$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 36 Bryan Olson wrote: > Mok-Kong Shen wrote: > > > [snip] > > > With an intermediate (first) > > algorithm, his choice of the input to the second algorithm is > > evidently limited, unless he has already cracked the first algorithm > > somehow. Anyway, the presence of the first algorithm (which is at > > issue in the present context) can't have any negative effect on > > the second algorithm in aspect of its susceptibility to chosen- > > plaintext attack (with the term understood as such). > > So adding the first algorithm (assuming independant keys) > will not result in a chain weaker against chosen plaintext > than is the second algorithm alone. By "facilitate the > attack" Schneier means provide an opportunity to launch it > where the system did not directly allow the attacker to > choose plaintext. Many thanks for providing certain explanations. But at this point I still have a question: If the system does not directly allow the oppoent to choose plaintext (to the cascade, i.e. input to the first algorithm), then he has even less opportunity to exert influence on what the second algorithm gets as input. So 'facilitate the attack' on the second algorithm in the sense of 'chosen plaintext', i.e. arbitrarily choosing its input, seems to be far from being true in my view. (I exclude the obvious nonsense case that both algorithms were 'designed' by the opponent.) M. K. Shen
Subject: Re: Q: Cascading multiple block algorithms Date: Mon, 24 Jul 2000 14:29:33 -0700 From: "Joseph Ashwood" <ashwood@msn.com> Message-ID: <u6gdKZb9$GA.420@cpmsnbbsa08> References: <397CAD6F.9FF0DA27@t-online.de> Newsgroups: sci.crypt Lines: 11 That's correct, chosen-plaintext attacks are generally quite difficult to come by. In times of war they're done through active means(e.g. break in, plugin your date, grab the output and leave). This is a very expensive type of attack to carry out, but is considered mostly out of completeness, and because it can very often uncover flaws that are of use for other attacks. Joe
Subject: Re: Q: Cascading multiple block algorithms Date: Tue, 25 Jul 2000 01:44:05 GMT From: Bryan Olson <bryanolson@my-deja.com> Message-ID: <8lird4$llj$1@nnrp1.deja.com> References: <397CAD6F.9FF0DA27@t-online.de> Newsgroups: sci.crypt Lines: 22 Mok-Kong Shen wrote: > Many thanks for providing certain explanations. But at this point I > still have a question: If the system does not directly allow the > oppoent to choose plaintext (to the cascade, i.e. input to the first > algorithm), then he has even less opportunity to exert influence on > what the second algorithm gets as input. The point is that it is possible that the attack does not work given the original plaintext distribution, but does given the distribution induced by the interposed cipher. The attacker no longer needs to choose plaintext, because the cipher has given him the plaintext he needs. --Bryan -- email: bolson at certicom dot com Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: Q: Cascading multiple block algorithms Date: Tue, 25 Jul 2000 12:12:53 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <397D6825.6DD4DB20@t-online.de> References: <8lird4$llj$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 26 Bryan Olson wrote: > Mok-Kong Shen wrote: > > > Many thanks for providing certain explanations. But at this point I > > still have a question: If the system does not directly allow the > > oppoent to choose plaintext (to the cascade, i.e. input to the first > > algorithm), then he has even less opportunity to exert influence on > > what the second algorithm gets as input. > > The point is that it is possible that the attack does not > work given the original plaintext distribution, but does > given the distribution induced by the interposed cipher. > The attacker no longer needs to choose plaintext, because > the cipher has given him the plaintext he needs. > Thanks. I suppose this is why it could be valuable to insert a mixing process or pseudo-random whitening between two ciphers to form a stack of three. M. K. Shen
Subject: Re: Cascading multiple block algorithms Date: Fri, 21 Jul 2000 14:12:53 -0700 From: "Joseph Ashwood" <ashwood@msn.com> Message-ID: <#2Kn1h18$GA.240@cpmsnbbsa09> References: <3978BA4A.272972A2@t-online.de> Newsgroups: sci.crypt Lines: 17 One example is: attacker discovers flaws in ci (inner cipher) and co(outer cipher) such that ci has extreme tendancies towards certain values under random keys (e.g. 0xaaaaaaaaa maps 99% of the time to 0x186528965), and that co is subject to a known plaintext attack. For the chosen plaintext attack, the attacker chooses the plaintext to be 0xaaaaaaaaa, knowing that the input to co has high probability of being 0x186528965, facilitating an attack. Personally I'd call this a probably plaintext attack, but under the circumstances of a large target audience book (like AC), it would probably be clearer to the audience to use known/chosen plaintext terminology. Similar situations happen quite often in low grade ciphers, but are extremely unlikely in something the strength of DES, 3DES, Blowfish, Twofish, Serpent, Rijndael, et al. Joe
Subject: Re: Cascading multiple block algorithms Date: Sat, 22 Jul 2000 00:39:07 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3978D10B.C8E7DF08@t-online.de> References: <#2Kn1h18$GA.240@cpmsnbbsa09> Newsgroups: sci.crypt Lines: 25 Joseph Ashwood wrote: > One example is: > attacker discovers flaws in ci (inner cipher) and co(outer cipher) such that > ci has extreme tendancies towards certain values under random keys (e.g. > 0xaaaaaaaaa maps 99% of the time to 0x186528965), and that co is subject to > a known plaintext attack. For the chosen plaintext attack, the attacker > chooses the plaintext to be 0xaaaaaaaaa, knowing that the input to co has > high probability of being 0x186528965, facilitating an attack. Personally > I'd call this a probably plaintext attack, but under the circumstances of a > large target audience book (like AC), it would probably be clearer to the > audience to use known/chosen plaintext terminology. Sorry, I need further help. Which cipher is the first of the cascade, ci or co? I suppose it must be co. But I don't yet quite follow the reasoning. Could you please explain the matter together with the semantics of the two attacks, i.e. what the analyst gets in each case? (What the analyst 'knows' or 'chooses' of plaintext are all with respect to the input of the cascade and hence are input to the first cipher, isn't it?) Thanks. M. K. Shen
Subject: Re: Cascading multiple block algorithms Date: Fri, 21 Jul 2000 15:46:04 -0700 From: "Joseph Ashwood" <ashwood@msn.com> Message-ID: <e3$rS328$GA.278@cpmsnbbsa07> References: <3978D10B.C8E7DF08@t-online.de> Newsgroups: sci.crypt Lines: 18 > Sorry, I need further help. Which cipher is the first of the cascade, ci or co? ciphertext = co(ci(plaintext, key1), key2) > I suppose it must be co. But I don't yet quite follow the reasoning. Could > you please explain the matter together with the semantics of the two attacks, > i.e. what the analyst gets in each case? The analyst gets to choose the plaintext going into ci. This plaintext knowledge gives probably knowledge of the output of ci. Which translates directly to probable knowledge of the input of co From which point the analyst can perform a (probable) known-plaintext attack on co, by exploiting a flaw in ci. > Thanks.
Subject: Re: Cascading multiple block algorithms Date: Sat, 22 Jul 2000 01:38:42 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3978fb13.4115385@news.io.com> References: <e3$rS328$GA.278@cpmsnbbsa07> Newsgroups: sci.crypt Lines: 47 On Fri, 21 Jul 2000 15:46:04 -0700, in <e3$rS328$GA.278@cpmsnbbsa07>, in sci.crypt "Joseph Ashwood" <ashwood@msn.com> wrote: >> Sorry, I need further help. Which cipher is the first of the cascade, ci >or co? >ciphertext = co(ci(plaintext, key1), key2) > >> I suppose it must be co. But I don't yet quite follow the reasoning. Could >> you please explain the matter together with the semantics of the two >attacks, >> i.e. what the analyst gets in each case? >The analyst gets to choose the plaintext going into ci. >This plaintext knowledge gives probably knowledge of the output of ci. >Which translates directly to probable knowledge of the input of co >From which point the analyst can perform a (probable) known-plaintext attack >on co, by exploiting a flaw in ci. But the alternative to having a series of ciphers is to have only one cipher, and when we have only one cipher, known-plaintext can be directly applied. So even if the second cipher is as weak as postulated, it *still* has made things worse for the opponents by constraining the attack to very limited plaintext structures. And the whole argument depends upon the second cipher being weak. But if we can postulate a cipher being weak, we have a real worry when we are using only one cipher. The argument shows that it is possible to construct a case in which a sequence of ciphers is not much stronger than one cipher. That case is when one of the ciphers is almost invisibly weak in a way which can be attacked without known-plaintext. In other words, just as there is no proof of strength for any cipher, there is also no proof of strength for any sequence of ciphers. Suppose, however, we have three ciphers in sequence: Then, even if one cipher is weak in a way which can be addressed in such a stack, known-plaintext is *still* not useful on either of the other two ciphers. Where known-plaintext is the worst possible cipher-exposure, we have thus created a situation which can retain security in the face of the complete failure of a cipher upon which we are willing to depend. I'd call that an interesting result. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM

Terry Ritter, his current address, and his top page.

Last updated: 2001-06-27