When we talk about attacking a cipher, we normally expect the opponents to have ciphertext. So known-plaintext is the information condition of having some amount of both the plaintext and the related ciphertext, for use in an attack. (The point of such an attack might be to expose the key, thus eventually exposing plaintext not otherwise known. In practice, the "known" plaintext might consist of some real knowledge and some guesses.)
Anyone who has actually attacked a real cipher in practice must know the irreplaceable advantage of known-plaintext: A cipher is a key-selected transformation between plaintext and ciphertext. To attack a cipher is to use knowledge of a particular transformation to expose the key which selected that transformation. But the very concept of a "transformation" implies knowledge of both input (plaintext) and output (ciphertext).
Obviously, ciphers can have various weaknesses which can be attacked in different ways. Normally, we expect ciphertext to be random-like and not have peculiar statistical characteristics. In this situation, nobody can mount an attack on the cipher transformation without knowing -- or assuming -- something about the plaintext. Absent actual plaintext -- or some identifiable plaintext or ciphertext characteristic -- it is impossible to expose the transformation. In this situation, the correct key cannot be identified by any means whatsoever, without knowing both plaintext and ciphertext.
Considering the general lack of proof of strength in practice in cryptography, leveraging an actual impossibility would seem very useful. But, in practice, it is very difficult to prevent some amount of plaintext from escaping, because the information in that plaintext may not have any worth, and so will not be protected.
Nevertheless, if some way could be found to prevent known-plaintext exposure, we could eliminate all attacks of any sort -- known or unknown -- on the transformation itself. And we can approach that happy state by multi-ciphering with a stack of three ciphers using independent keys.
It is true that the three ciphers in a stack could be considered a single cipher, which might well have some exposed plaintext. But we expect the overall cipher -- the Shannon addition of three ciphers -- to be vastly more complex than any particular component cipher used alone. The stack thus protects against attacks on each of the component transformations themselves. It also protects against the case where the component cipher we might have used by itself is actually weak.
Subject: Known plaintext considered harmless Date: 19 Jun 2001 05:20:32 -0000 From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> Message-ID: <20010619052032.804.qmail@nym.alias.net> Newsgroups: sci.crypt Lines: 34 Inexperienced users of crypto systems are often concerned about known plaintext. They have heard that known plaintext can give a cryptanalyst an entry point into breaking ciphers. Accordingly they fear known plaintext and try to avoid it. Sometimes they will even complicate their data structures or protocols in order to avoid known plaintext. They will incorporate compression for no good reason, or restructure headers, or make sure that fields set aside for future expansion hold random values rather than zeros. All this complicates their overall system design and introduces new possibilities for errors. We need to communicate clearly that known plaintext is no longer an issue. With modern ciphers and a reasonable chaining mode, you don't have to worry about known plaintext. If your cipher is weak against known plaintext, you should be using a different cipher. When designing data which will be protected by a cipher, the only consideration should be the needs to which the data will be put. Design for clarity and convenience. NO CONSIDERATION WHATSOEVER should be given to manipulating or constraining the data structures in the hopes of making the encryption stronger! In your overall system, the cipher is there to do the job of protecting the plaintext. The job of the plaintext is to represent whatever data is being communicated. Don't be misled into blurring these boundaries. Modern ciphers are fully capable of providing confidentiality with any and every plaintext. Let the cipher do its job, don't try to "help" it in the other parts of your design. Let us all agree that it is time to put concerns about known plaintext behind us. Recommendations to avoid it are obsolete.
Subject: Re: Known plaintext considered harmless Date: Tue, 19 Jun 2001 07:16:42 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b2efc49.1170309@news.io.com> References: <20010619052032.804.qmail@nym.alias.net> Newsgroups: sci.crypt Lines: 24 On 19 Jun 2001 05:20:32 -0000, in <20010619052032.804.qmail@nym.alias.net>, in sci.crypt lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> wrote: >[...] >Let us all agree that it is time to put concerns about known plaintext >behind us. Recommendations to avoid it are obsolete. No. "Known-plaintext" is an information condition; it is the condition of knowing both the input to -- and the output from -- the secret transformation. The value of such knowledge to any real attack should be obvious. Modern ciphers are indeed designed to resist known-plaintext. That is a noble design goal. Whether or not it has been achieved is, of course, of some continuing interest. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Known plaintext considered harmless Date: Tue, 19 Jun 2001 11:08:59 -0600 From: John Myre <jmyre@sandia.gov> Message-ID: <3B2F872B.1F4DAC8F@sandia.gov> References: <3b2efc49.1170309@news.io.com> Newsgroups: sci.crypt Lines: 21 Terry Ritter wrote: <snip> > "Known-plaintext" is an information condition; it is the condition of > knowing both the input to -- and the output from -- the secret > transformation. The value of such knowledge to any real attack should > be obvious. > > Modern ciphers are indeed designed to resist known-plaintext. That is > a noble design goal. Whether or not it has been achieved is, of > course, of some continuing interest. Which is the point. Many experts believe that it has, which would mean that the "obvious" value of known plaintext is in fact "very little". The lack of a proof for such strength is, in my view, insufficient evidence for weakness such that plaintext manipulations specifically to help the cipher are warranted. It's an engineering point of view: separate the encryption itself from the rest of the application. JM
Subject: Re: Known plaintext considered harmless Date: 19 Jun 2001 14:29:13 -0400 From: lbudney-usenet@nb.net Message-ID: <m3r8wg8gsm.fsf@peregrine.swoop.local> References: <3B2F872B.1F4DAC8F@sandia.gov> Newsgroups: sci.crypt Lines: 25 John Myre <jmyre@sandia.gov> writes: > > The lack of a proof for such strength is, in my view, insufficient > evidence for weakness such that plaintext manipulations specifically > to help the cipher are warranted. Note, however, that reducing known plaintext is trivial; compression helps quite a lot. The cipher should be strong enough not to depend on compression (or anything else), but not doing compression is just silly! (1) It makes encryption easier by shrinking the file. (2) It saves bandwidth by shrinking the ciphertext. (3) Reducing known plaintext certainly can't hurt. I would agree (for what that's worth!) if you'd said that *extreme* efforts to eliminate known plaintext is just silly. But I wouldn't deprecate an inexpensive measure which probably helps and definitely has other benefits. Len. -- Wow. Another unbiased evaluation from Nick ``claims against Exim's security ... firmly grounded in prejudice'' Maclaren. -- Dan Bernstein, author of qmail
Subject: Re: Known plaintext considered harmless Date: Tue, 19 Jun 2001 13:46:27 -0600 From: John Myre <jmyre@sandia.gov> Message-ID: <3B2FAC13.547765F1@sandia.gov> References: <m3r8wg8gsm.fsf@peregrine.swoop.local> Newsgroups: sci.crypt Lines: 23 lbudney-usenet@nb.net wrote: <snip> > Note, however, that reducing known plaintext is trivial; compression > helps quite a lot. The cipher should be strong enough not to depend on > compression (or anything else), but not doing compression is just silly! > > (1) It makes encryption easier by shrinking the file. > (2) It saves bandwidth by shrinking the ciphertext. > (3) Reducing known plaintext certainly can't hurt. > > I would agree (for what that's worth!) if you'd said that *extreme* > efforts to eliminate known plaintext is just silly. But I wouldn't > deprecate an inexpensive measure which probably helps and definitely > has other benefits. <snip> All true. But note that (the best) two of the three reasons have nothing to do with cryptographic security. It will of course be rare that compression cannot be justified, in practice. I just think it's wrong to bring security into the decision, because it's too easy to get your priorities wrong. JM
Subject: Re: Known plaintext considered harmless Date: Wed, 20 Jun 2001 00:33:24 +0100 From: David Hopwood <david.hopwood@zetnet.co.uk> Message-ID: <3B2FE144.C841DE65@zetnet.co.uk> References: <m3r8wg8gsm.fsf@peregrine.swoop.local> Newsgroups: sci.crypt Lines: 62 -----BEGIN PGP SIGNED MESSAGE----- lbudney-usenet@nb.net wrote: > John Myre <jmyre@sandia.gov> writes: > > > > The lack of a proof for such strength is, in my view, insufficient > > evidence for weakness such that plaintext manipulations specifically > > to help the cipher are warranted. > > Note, however, that reducing known plaintext is trivial; compression > helps quite a lot. The cipher should be strong enough not to depend on > compression (or anything else), but not doing compression is just silly! Not doing compression is not "just silly". Compression has a performance cost (which typically isn't outweighed by encrypting less data [*]), and requires fairly large buffers. Whether compression is of benefit to a protocol depends on the relative costs of bandwidth and storage vs the processing needed for compression. If an evaluation of those costs suggests that it would not be worthwhile for cleartext, then it probably won't be worthwhile when encryption is used either. OTOH, since just before encryption is the "last chance" to compress, there is a good case for supporting compression in cryptography standards. It shouldn't be expected to improve security, though; if anything, it complicates the security analysis. (For instance, do you authenticate the compressed data or the uncompressed data? There is a case for doing either.) [*] I'm assuming relatively fast ciphers like Rijndael or RC4, with a fast MAC if applicable. > (1) It makes encryption easier by shrinking the file. > (2) It saves bandwidth by shrinking the ciphertext. > (3) Reducing known plaintext certainly can't hurt. It can't hurt security (assuming it's integrated correctly with the security protocol), but you might not want to use it for other reasons. - -- David Hopwood <david.hopwood@zetnet.co.uk> Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/ RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01 Nothing in this message is intended to be legally binding. If I revoke a public key but refuse to specify why, it is because the private key has been seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBOy/gtDkCAxeYt5gVAQFYzwf8DvawcqlWfwegXxJekpJx+VtPlaZt+mNv yq3aPUScglGRcjykl4H4j3DFBxJuZDpa0BAcAJ/k04z/J9YuUeCJCqRWtKdPQXQ0 g8rKn+Ism6tdDHj058I+UPj8ZYUEmqVyLbg0PxDQ2L9YPyaHKkXaPVeRsJ2a28eR vfzjyrK+e4uo6AqqRoglYyZN5uQmlHg0JbnGydbcd0ZYV2NWiSddchVhxRlWisAz VqPuZYRFDyx75jK7XYEGzkQdpJmif8aYjNUWGUvF1hjNFEe0nq4IJi0nBwaxPj4h FiWloRPGCKfa9IX5qengSWlkPchvYRezqoyQh4x5t5XqU64xQ/C21w== =bXdd -----END PGP SIGNATURE-----
Subject: Re: Known plaintext considered harmless Date: Wed, 20 Jun 2001 10:13:06 GMT From: Tim Tyler <tt@iname.com> Message-ID: <GF84Du.BBC@bath.ac.uk> References: <3B2FE144.C841DE65@zetnet.co.uk> Newsgroups: sci.crypt Lines: 49 David Hopwood <david.hopwood@zetnet.co.uk> wrote: : lbudney-usenet@nb.net wrote: :> Note, however, that reducing known plaintext is trivial; compression :> helps quite a lot. The cipher should be strong enough not to depend on :> compression (or anything else), but not doing compression is just silly! : Not doing compression is not "just silly". Compression has a performance : cost (which typically isn't outweighed by encrypting less data [*]) Compression and encryption can sometimes be done in parallel. *Then* it's almost always faster due to the fact that less data is encrypted - unless your compressor is slower than your encryption. Only on a serial machine is performance much of a concern. : OTOH, since just before encryption is the "last chance" to compress, : there is a good case for supporting compression in cryptography standards. : It shouldn't be expected to improve security, though; if anything, it : complicates the security analysis. (For instance, do you authenticate : the compressed data or the uncompressed data? There is a case for doing : either.) I'm not sure I can see much case for authenticating the data after compression. I suppose signatures won't compress well - but apart from that... : [*] I'm assuming relatively fast ciphers like Rijndael or RC4, with a : fast MAC if applicable. :> (1) It makes encryption easier by shrinking the file. :> (2) It saves bandwidth by shrinking the ciphertext. :> (3) Reducing known plaintext certainly can't hurt. : It can't hurt security (assuming it's integrated correctly with the : security protocol), but you might not want to use it for other reasons. I think there are /some/ cases where it can damage security. For example, if the plaintexts are all fixed size forms, then compressing them may result in the attacker getting more information that not doing so. Forms with lots of additional data in them will not compress so well - so you can see how much data there is in the form by the length of the compressed file - while before they were all indistinguishable. -- __________ |im |yler tt@iname.com Home page: http://alife.co.uk/tim/
Subject: Re: Known plaintext considered harmless Date: 20 Jun 2001 06:41:54 -0400 From: lbudney-usenet@nb.net Message-ID: <m3hexb5t71.fsf@peregrine.swoop.local> References: <3B2FE144.C841DE65@zetnet.co.uk> Newsgroups: sci.crypt Lines: 22 David Hopwood <david.hopwood@zetnet.co.uk> writes: > lbudney-usenet@nb.net wrote: >> ...not doing compression is just silly! > > Not doing compression is not "just silly". Compression has a performance > cost... 1,000 pardons. I never intended the statement to be sweepingly true of every context in the universe where encryption is used. There may indeed be circumstances in which compression is clearly not the best idea. Are you happy now? Fact remains, that somehow deprecating compression is just silly. It has its place. Len. -- Frugal Tip #55: Get yourself a realistic-looking mongoose costume. Then, rent yourself out to somebody who wants a rented mongoose.
Subject: Re: Known plaintext considered harmless Date: Tue, 19 Jun 2001 19:58:07 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b2fabca.1848659@news.io.com> References: <3B2F872B.1F4DAC8F@sandia.gov> Newsgroups: sci.crypt Lines: 40 On Tue, 19 Jun 2001 11:08:59 -0600, in <3B2F872B.1F4DAC8F@sandia.gov>, in sci.crypt John Myre <jmyre@sandia.gov> wrote: >Terry Ritter wrote: ><snip> >> "Known-plaintext" is an information condition; it is the condition of >> knowing both the input to -- and the output from -- the secret >> transformation. The value of such knowledge to any real attack should >> be obvious. >> >> Modern ciphers are indeed designed to resist known-plaintext. That is >> a noble design goal. Whether or not it has been achieved is, of >> course, of some continuing interest. > >Which is the point. Many experts believe that it has, which would >mean that the "obvious" value of known plaintext is in fact "very >little". The "obvious" value to which I referred is the process of cryptanalysis itself: Some keyed function takes plaintext to ciphertext. Consider trying to expose that function while knowing only the plaintext but not the ciphertext, or knowing the ciphertext but not the plaintext. We can create toy examples for which this is easy, but in general, this is very tough. Not knowing both the input and the output acts to hide the ciphering function itself. Now consider trying to expose the ciphering function knowing both the plaintext and the ciphertext. We expect this to be tough anyway, if we assume (that is, make an ASS out of U and ME) the cipher design is strong. But we wouldn't have to hope as hard if there were no known plaintext in the first place. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Known plaintext considered harmless Date: Tue, 19 Jun 2001 23:17:16 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3b2fdc9d.29036540@news.powersurfr.com> References: <3B2F872B.1F4DAC8F@sandia.gov> Newsgroups: sci.crypt Lines: 24 On Tue, 19 Jun 2001 11:08:59 -0600, John Myre <jmyre@sandia.gov> wrote, in part: >It's an engineering point of >view: separate the encryption itself from the rest of the application. That does have validity, although there are also cases when the encryption _is_ the application, in which case that concern does not apply. Also, a "reasonable chaining mode" leaves some latitude for doing, in the encryption, things that might be done elsewhere. However, if the application tends to leave certain fields blank, does it make sense to separate this from, say, the _compression_ stage? If there is nothing wrong about a compressor receiving side information about its input, so as to be able to compress it more efficiently, then can't we make similar allowances for an encryption stage? (Thus, part of the decryption will be to restore the blank fields and so on, with some short indicator handling the possibility that they will stop being blank in future expansion.) John Savard http://home.ecn.ab.ca/~jsavard/frhome.htm
Subject: Re: Known plaintext considered harmless Date: Wed, 20 Jun 2001 09:57:52 -0600 From: John Myre <jmyre@sandia.gov> Message-ID: <3B30C800.654F81F0@sandia.gov> References: <3b2fdc9d.29036540@news.powersurfr.com> Newsgroups: sci.crypt Lines: 22 John Savard wrote: <snip> > If > there is nothing wrong about a compressor receiving side information > about its input, so as to be able to compress it more efficiently, > then can't we make similar allowances for an encryption stage? (Thus, > part of the decryption will be to restore the blank fields and so on, > with some short indicator handling the possibility that they will stop > being blank in future expansion.) <snip> The only thing wrong with approaches like this is the practical side effects of such design decisions on the implementation effort. It's *easy* to f*** up your security by making mistakes in the implementation. It's *hard* to be "sure" you haven't done so. Complexity is the enemy of correctness. Therefore, it will most often be best to KISS your encryption modules. If you want to do compression, that's fine, but beware of compromising security by implementation (or design!) problems. JM
Subject: Re: Known plaintext considered harmless Date: Tue, 19 Jun 2001 09:41:56 GMT From: Tim Tyler <tt@iname.com> Message-ID: <GF689w.H76@bath.ac.uk> References: <20010619052032.804.qmail@nym.alias.net> Newsgroups: sci.crypt Lines: 19 lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> wrote: : NO CONSIDERATION WHATSOEVER should be given to manipulating or : constraining the data structures in the hopes of making the : encryption stronger! [...] : Let us all agree that it is time to put concerns about known plaintext : behind us. Recommendations to avoid it are obsolete. You go far too far. While tying yourself in knots to avoid known plaintext may be over the top, avoiding it *is* desirable. You presume that cryptanalytic attack is the only possible method of getting information relating to the key of a cypher. This is not the case. If the number of possible keys can be reduced - by any means - known-plaintext attacks can become a practical issue. -- __________ |im |yler tt@iname.com Home page: http://alife.co.uk/tim/
Subject: Re: Known plaintext considered harmless Date: Tue, 19 Jun 2001 10:46:22 -0600 From: John Myre <jmyre@sandia.gov> Message-ID: <3B2F81DE.901777B1@sandia.gov> References: <GF689w.H76@bath.ac.uk> Newsgroups: sci.crypt Lines: 37 Tim Tyler wrote: <snip> > You go far too far. While tying yourself in knots to avoid known > plaintext may be over the top, avoiding it *is* desirable. But the question is: *how* desirable? Exactly how much effort is it worth? I'd agree with (anonymous) that the proper solution is to reinforce the cipher. Failure of software systems due to unwarranted complexity is a *bad* problem. > You presume that cryptanalytic attack is the only possible method of > getting information relating to the key of a cypher. ? > This is not the > case. If the number of possible keys can be reduced - by any means - > known-plaintext attacks can become a practical issue. That is at best an exaggeration. You can reduce the number of possible keys quite easily by brute force: guess a few keys, decrypt the entire message for each guess, and discard the ones that are clearly nonsense. (We must assume that any keyless transformations (e.g., compression) are known to the attacker.) In practice - this is simply not an issue. The point is that if a simple keysearch can be made practical, because the entropy (unknown bits in the key) is small enough, then using obfuscation on the source text as a way to prevent that attack is almost certainly pointless. Terry's response is more reasoned. The suspicion that maybe we are all fooling ourselves, that there *aren't* any ciphers that we can trust are as strong as we think, is at least defensible. I think he's wrong, but of course I can't prove it. JM
Subject: Re: Known plaintext considered harmless Date: Tue, 19 Jun 2001 19:44:26 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b2fab57.1733188@news.io.com> References: <3B2F81DE.901777B1@sandia.gov> Newsgroups: sci.crypt Lines: 28 On Tue, 19 Jun 2001 10:46:22 -0600, in <3B2F81DE.901777B1@sandia.gov>, in sci.crypt John Myre <jmyre@sandia.gov> wrote: >[...] >Terry's response is more reasoned. The suspicion that maybe we >are all fooling ourselves, that there *aren't* any ciphers that >we can trust are as strong as we think, is at least defensible. I think that viewpoint is not only defensible but also *appropriate* for security analysis. (Also, the issue is not so much that no strong ciphers exist, but that the particular cipher we propose to use may have weakness.) >I think he's wrong, but of course I can't prove it. Wrong? How can it be *wrong* to have a suspicion of weakness, when the assertion of strength is not based on proven fact? Absent proof of strength in practice, suspicion of weakness is entirely appropriate. We need to consider the consequences of our hopes being wrong. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Known plaintext considered harmless Date: Tue, 19 Jun 2001 23:33:37 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3b2fde73.29506471@news.powersurfr.com> References: <3b2fab57.1733188@news.io.com> Newsgroups: sci.crypt Lines: 45 On Tue, 19 Jun 2001 19:44:26 GMT, ritter@io.com (Terry Ritter) wrote, in part: >On Tue, 19 Jun 2001 10:46:22 -0600, in <3B2F81DE.901777B1@sandia.gov>, >in sci.crypt John Myre <jmyre@sandia.gov> wrote: >>I think he's wrong, but of course I can't prove it. >Wrong? How can it be *wrong* to have a suspicion of weakness, when >the assertion of strength is not based on proven fact? >Absent proof of strength in practice, suspicion of weakness is >entirely appropriate. We need to consider the consequences of our >hopes being wrong. Of course, he meant you would be "wrong" if the weakness did not in fact exist, regardless of the fact that you are right that there is no proof it does not. In a way, that isn't fair, since in effect it does make it appear as though you had done what David A. Scott did when he made his first appearance on this newsgroup - assert for a fact that one or more popular block ciphers (in his case, IDEA) is not secure. It is possible to have reasons for confidence in something that fall short of proof, and it is even possible for such reasons to be sufficient to make some forms of precaution unwarranted. On the one hand, I certainly could imagine cases where designing a file format around eventual encryption of the files in question could create serious problems in developing and debugging an application. On the other, under most circumstances, the computational cost of encryption is trivial these days, and making extra effort over and above what is considered the "standard" seems difficult to argue against. As for the specific issue: known plaintext + small key = brute-force search possible. Hence, any flaw in our ciphers that makes their effective keys smaller, or any advance in computation, is more threatening when the plaintext is known. But an answer is available that doesn't involve the equivalent of redesigning the English language to make it less redundant. Use larger keys, if your response to known plaintext must be confined to the cipher stage. John Savard http://home.ecn.ab.ca/~jsavard/frhome.htm
Subject: Re: Known plaintext considered harmless Date: Wed, 20 Jun 2001 05:20:57 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b30322a.7707648@news.io.com> References: <3b2fde73.29506471@news.powersurfr.com> Newsgroups: sci.crypt Lines: 69 On Tue, 19 Jun 2001 23:33:37 GMT, in <3b2fde73.29506471@news.powersurfr.com>, in sci.crypt jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) wrote: >[...] >It is possible to have reasons for confidence in something that fall >short of proof, and it is even possible for such reasons to be >sufficient to make some forms of precaution unwarranted. Not in cryptography. In the normal world where we build our intuition, we can see the consequences of design error: If some make of car has problems, we know (a human gets out and reports, or gets squished). If a computer program has problems doing what we want, we know, because it is not doing what we want (it may of course be doing *more* than we want, but that is a different issue). If a medicine does not do what we want, we know that too. In the normal world we know when things don't work. Cryptography is fundamentally different: In cryptography, we want to protect our information from opponents, but we have no way of knowing whether any particular cipher is successful. We don't know who our opponents are, and they don't tell us of their successes. There is thus no feedback to the design and development process from the real mission. The feedback we have is from practice missions. And that's fine, as far as it goes. But that has little to do with the real mission, and so should not build confidence. While we cannot affect that per se, we *can* develop systems which reduce the consequences of weakness, and also expose as little information as possible. >[...] >As for the specific issue: known plaintext + small key = brute-force >search possible. Hence, any flaw in our ciphers that makes their >effective keys smaller, or any advance in computation, is more >threatening when the plaintext is known. But an answer is available >that doesn't involve the equivalent of redesigning the English >language to make it less redundant. Use larger keys, if your response >to known plaintext must be confined to the cipher stage. I disagree. The problem is not keyspace. We already have keyspace. Adding more keyspace is no advantage here. The problem is the improved ability to analyze a ciphering function when one has both the input to -- and output from -- that function (this is known-plaintext, as opposed to having ciphertext-only). Some ciphers can be broken with ciphertext only. But the *reason* for this is that their plaintext is structured, or correlated. Knowing the plaintext, or something about it, is how we solve ciphers. When that knowledge is not available, even simple, supposedly-"weak" ciphers can be strong in practice. The obvious approach to minimizing the risk of known-plaintext is to encipher at least twice with different ciphers and keys, so that the plaintext to the last cipher is both randomized and hidden even from the authorized user. I always recommend using three ciphers, which allows one to be completely broken without exposing the others. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Known plaintext considered harmless Date: 20 Jun 2001 12:10:59 GMT From: david_a_scott@emailv.com (SCOTT19U.ZIP_GUY) Message-ID: <90C6325BDH110W296LC45WIN3030R@207.36.190.226> References: <3b30322a.7707648@news.io.com> Newsgroups: sci.crypt Lines: 89 ritter@io.com (Terry Ritter) wrote in <3b30322a.7707648@news.io.com>: > >On Tue, 19 Jun 2001 23:33:37 GMT, in ><3b2fde73.29506471@news.powersurfr.com>, in sci.crypt >jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) wrote: > >>[...] >>It is possible to have reasons for confidence in something that fall >>short of proof, and it is even possible for such reasons to be >>sufficient to make some forms of precaution unwarranted. > >Not in cryptography. > >In the normal world where we build our intuition, we can see the >consequences of design error: If some make of car has problems, we >know (a human gets out and reports, or gets squished). If a computer >program has problems doing what we want, we know, because it is not >doing what we want (it may of course be doing *more* than we want, but >that is a different issue). If a medicine does not do what we want, >we know that too. In the normal world we know when things don't work. > >Cryptography is fundamentally different: In cryptography, we want to >protect our information from opponents, but we have no way of knowing >whether any particular cipher is successful. We don't know who our >opponents are, and they don't tell us of their successes. There is >thus no feedback to the design and development process from the real >mission. > >The feedback we have is from practice missions. And that's fine, as >far as it goes. But that has little to do with the real mission, and >so should not build confidence. > >While we cannot affect that per se, we *can* develop systems which >reduce the consequences of weakness, and also expose as little >information as possible. > > >>[...] >>As for the specific issue: known plaintext + small key = brute-force >>search possible. Hence, any flaw in our ciphers that makes their >>effective keys smaller, or any advance in computation, is more >>threatening when the plaintext is known. But an answer is available >>that doesn't involve the equivalent of redesigning the English >>language to make it less redundant. Use larger keys, if your response >>to known plaintext must be confined to the cipher stage. > >I disagree. The problem is not keyspace. We already have keyspace. >Adding more keyspace is no advantage here. > >The problem is the improved ability to analyze a ciphering function >when one has both the input to -- and output from -- that function >(this is known-plaintext, as opposed to having ciphertext-only). > >Some ciphers can be broken with ciphertext only. But the *reason* for >this is that their plaintext is structured, or correlated. Knowing >the plaintext, or something about it, is how we solve ciphers. When >that knowledge is not available, even simple, supposedly-"weak" >ciphers can be strong in practice. > >The obvious approach to minimizing the risk of known-plaintext is to >encipher at least twice with different ciphers and keys, so that the >plaintext to the last cipher is both randomized and hidden even from >the authorized user. I always recommend using three ciphers, which >allows one to be completely broken without exposing the others. > I agree basically with what your said. But I don't think you have ever completely described the nature of the three ciphers that would be used in series. Do you argee they should be fully bijective. Meaning false keys would lead to something in the input message space so no information is given to attacker to break the system. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM" http://www.jim.com/jamesd/Kong/scott19u.zip My website http://members.nbci.com/ecil/index.htm My crypto code http://radiusnet.net/crypto/archive/scott/ MY Compression Page http://members.nbci.com/ecil/compress.htm **TO EMAIL ME drop the roman "five" ** Disclaimer:I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged. As a famous person once said "any cryptograhic system is only as strong as its weakest link"
Subject: Re: Known plaintext considered harmless Date: Wed, 20 Jun 2001 17:29:26 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b30dd41.6478879@news.io.com> References: <90C6325BDH110W296LC45WIN3030R@207.36.190.226> Newsgroups: sci.crypt Lines: 58 On 20 Jun 2001 12:10:59 GMT, in <90C6325BDH110W296LC45WIN3030R@207.36.190.226>, in sci.crypt david_a_scott@emailv.com (SCOTT19U.ZIP_GUY) wrote: >ritter@io.com (Terry Ritter) wrote in <3b30322a.7707648@news.io.com>: >[...] >>Some ciphers can be broken with ciphertext only. But the *reason* for >>this is that their plaintext is structured, or correlated. Knowing >>the plaintext, or something about it, is how we solve ciphers. When >>that knowledge is not available, even simple, supposedly-"weak" >>ciphers can be strong in practice. >> >>The obvious approach to minimizing the risk of known-plaintext is to >>encipher at least twice with different ciphers and keys, so that the >>plaintext to the last cipher is both randomized and hidden even from >>the authorized user. I always recommend using three ciphers, which >>allows one to be completely broken without exposing the others. >> > > I agree basically with what your said. But I don't think >you have ever completely described the nature of the three ciphers >that would be used in series. Do you argee they should be fully >bijective. Meaning false keys would lead to something in the input >message space so no information is given to attacker to break the >system. I don't like using the term "bijective" for this. Maybe "plaintext complete" comes closer, as in every possible plaintext should be at least technically valid. But whatever we call it, it certainly is a desirable and possibly important property that the ideal system would assure before invoking a cipher. Language does not have this property, which is exactly why we can solve some simple ciphers. Without some knowledge of the plaintext itself, or of structure in the plaintext, breaking a cipher becomes very difficult. If we communicate in distinct messages, and if the "plaintext" includes a length field, that "length" had better be modulo or block size, or we will be describing in plaintext a size the opponents can see as ciphertext. This is a form of known plaintext. But known plaintext is also common in salutations, signatures, HTML codes and so on. On the other hand, even if a length is added to the input of the first cipher, the input to the second and third ciphers should be well distributed -- such that every possible plaintext seems possible -- and so not a problem. That sounds to me like a reason for using a sequence or "cascade" of multiple ciphers, and is related to hiding known plaintext. As I see it, the problem is not so much the "bijective" nature of the last cipher, but instead the known structure in the original plaintext. This is a known-plaintext issue. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Known plaintext considered harmless Date: Tue, 26 Jun 2001 23:10:20 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3b391527.19647451@news.powersurfr.com> References: <90C6325BDH110W296LC45WIN3030R@207.36.190.226> Newsgroups: sci.crypt Lines: 25 On 20 Jun 2001 12:10:59 GMT, david_a_scott@emailv.com (SCOTT19U.ZIP_GUY) wrote, in part: > I agree basically with what your said. But I don't think >you have ever completely described the nature of the three ciphers >that would be used in series. Do you argee they should be fully >bijective. Meaning false keys would lead to something in the input >message space so no information is given to attacker to break the >system. Whether or not, in the compression stage, one has used a bijective compressor so that arbitrary bit strings of length N decompress to valid messages - if that's even possible - I agree that the ciphers in a cascade should not expand the data being enciphered. So they will be bijective: every N bit input leads to one of the possible N bit outputs. However, if an exception is made to allow the cipher steps to use a random IV, they should be forced to get that IV from the overall 'system' and not produce it for themselves. This prevents a weak cipher layer from leaking its own key. John Savard http://home.ecn.ab.ca/~jsavard/index.html
Subject: Re: Known plaintext considered harmless Date: 26 Jun 2001 23:51:11 GMT From: david_a_scott@emailv.com (SCOTT19U.ZIP_GUY) Message-ID: <90CCB31B0H110W296LC45WIN3030R@207.36.190.226> References: <3b391527.19647451@news.powersurfr.com> Newsgroups: sci.crypt Lines: 55 jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) wrote in <3b391527.19647451@news.powersurfr.com>: >On 20 Jun 2001 12:10:59 GMT, david_a_scott@emailv.com >(SCOTT19U.ZIP_GUY) wrote, in part: > >> I agree basically with what your said. But I don't think >>you have ever completely described the nature of the three ciphers >>that would be used in series. Do you argee they should be fully >>bijective. Meaning false keys would lead to something in the input >>message space so no information is given to attacker to break the >>system. > >Whether or not, in the compression stage, one has used a bijective >compressor so that arbitrary bit strings of length N decompress to >valid messages - if that's even possible - Actually Mr J it is possible so what are you trying to say? > >I agree that the ciphers in a cascade should not expand the data being >enciphered. So they will be bijective: every N bit input leads to one >of the possible N bit outputs. But what you neglect here is that ciphers may have different boundaries. Some work in 8 byte units others may work in 10 or 15 byte units. So in your cascadeing are you limiting to only methods that have matching block sizes or do you allow transforms to change block size if bijective? > >However, if an exception is made to allow the cipher steps to use a >random IV, they should be forced to get that IV from the overall >'system' and not produce it for themselves. This prevents a weak >cipher layer from leaking its own key. I think you don't really need to call it an exception if you think of the random IV if used as input data that is part of the unique decryption of the the resulting encrypted file. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM" http://www.jim.com/jamesd/Kong/scott19u.zip My website http://members.nbci.com/ecil/index.htm My crypto code http://radiusnet.net/crypto/archive/scott/ MY Compression Page http://members.nbci.com/ecil/compress.htm **TO EMAIL ME drop the roman "five" ** Disclaimer:I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged. As a famous person once said "any cryptograhic system is only as strong as its weakest link"
Subject: Re: Known plaintext considered harmless Date: Wed, 27 Jun 2001 12:59:39 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3b39d840.1040971@news.powersurfr.com> References: <90CCB31B0H110W296LC45WIN3030R@207.36.190.226> Newsgroups: sci.crypt Lines: 20 On 26 Jun 2001 23:51:11 GMT, david_a_scott@emailv.com (SCOTT19U.ZIP_GUY) wrote, in part: > But what you neglect here is that ciphers may have different >boundaries. Some work in 8 byte units others may work in 10 or >15 byte units. So in your cascadeing are you limiting to only >methods that have matching block sizes or do you allow transforms >to change block size if bijective? Either they all have the same alignment restriction (say, to whole bytes) or they must all be able to preserve the exact number of bits. Block ciphers can do so through "ciphertext stealing", as long as the message is at least one block long. Thus, I assume that an encryption program of this type will require that messages to be encrypted be at least 256 bits long, but will make no other restriction on length. John Savard http://home.ecn.ab.ca/~jsavard/index.html
Subject: Re: Known plaintext considered harmless Date: 27 Jun 2001 14:18:41 GMT From: david_a_scott@emailv.com (SCOTT19U.ZIP_GUY) Message-ID: <90CD59D08H110W296LC45WIN3030R@207.36.190.226> References: <3b39d840.1040971@news.powersurfr.com> Newsgroups: sci.crypt Lines: 59 jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) wrote in <3b39d840.1040971@news.powersurfr.com>: >On 26 Jun 2001 23:51:11 GMT, david_a_scott@emailv.com >(SCOTT19U.ZIP_GUY) wrote, in part: > >> But what you neglect here is that ciphers may have different >>boundaries. Some work in 8 byte units others may work in 10 or >>15 byte units. So in your cascadeing are you limiting to only >>methods that have matching block sizes or do you allow transforms >>to change block size if bijective? > >Either they all have the same alignment restriction (say, to whole >bytes) or they must all be able to preserve the exact number of bits. >Block ciphers can do so through "ciphertext stealing", as long as the >message is at least one block long. > >Thus, I assume that an encryption program of this type will require >that messages to be encrypted be at least 256 bits long, but will make >no other restriction on length. > I think your starting to get there. If you used encryption that was fully reversible with any key. And did not allow the size of file to change. The system would be stronger than the weakest length. Especially if one looking at 3 seperate encryption routines. However I think you wrong about the extreme length constrants just as the misguided souls were about how to achive perfect encyption with an OTP. Example if each of your methods normal encryption and ecb,cbc or standard chaining mods. There is very little propagation between blocks. If bewteen each layer of encryption say you expand the file by h2unc.exe then reversed the file and compressed say with arib,exe then used the next encryption with ciphertext stealing as you state above and do same betwwen last two ciphers. THe length of final output would not very likely be the length of input nessage and the actaully encrypted message would be more like all or nothing transform where whole file needed to decrypt it at all. While in your trusted method if last half of file missing an attacker still only needs the front half of file to break the encryption since all the information needed may be there. Now which do you rally think would be more secure? David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM" http://www.jim.com/jamesd/Kong/scott19u.zip My website http://members.nbci.com/ecil/index.htm My crypto code http://radiusnet.net/crypto/archive/scott/ MY Compression Page http://members.nbci.com/ecil/compress.htm **TO EMAIL ME drop the roman "five" ** Disclaimer:I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged. As a famous person once said "any cryptograhic system is only as strong as its weakest link"
Subject: Re: Known plaintext considered harmless Date: Thu, 21 Jun 2001 01:50:22 -0700 From: Bryan Olson <nospam@nospam.net> Message-ID: <3B31B54E.AE0A120D@nospam.net> References: <3b30322a.7707648@news.io.com> Newsgroups: sci.crypt Lines: 29 Terry Ritter wrote: > > John Savard) wrote: > > >[...] > >It is possible to have reasons for confidence in something that fall > >short of proof, and it is even possible for such reasons to be > >sufficient to make some forms of precaution unwarranted. > > Not in cryptography. [...] > The obvious approach to minimizing the risk of known-plaintext is to > encipher at least twice with different ciphers and keys, so that the > plaintext to the last cipher is both randomized and hidden even from > the authorized user. I always recommend using three ciphers, which > allows one to be completely broken without exposing the others. Then the attacker gets known plaintext against a cipher that happens to be built from two or three other ciphers. And if we believe we cannot have confidence without proof, then we have the same problem we started with. We are just as motivated to triple the ciphers that that are themselves tripled ciphers. --Bryan
Subject: Re: Known plaintext considered harmless Date: Thu, 21 Jun 2001 18:18:33 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b32391a.9437472@news.io.com> References: <3B31B54E.AE0A120D@nospam.net> Newsgroups: sci.crypt Lines: 72 On Thu, 21 Jun 2001 01:50:22 -0700, in <3B31B54E.AE0A120D@nospam.net>, in sci.crypt Bryan Olson <nospam@nospam.net> wrote: >Terry Ritter wrote: >> >> John Savard) wrote: >> >> >[...] >> >It is possible to have reasons for confidence in something that fall >> >short of proof, and it is even possible for such reasons to be >> >sufficient to make some forms of precaution unwarranted. >> >> Not in cryptography. > >[...] > >> The obvious approach to minimizing the risk of known-plaintext is to >> encipher at least twice with different ciphers and keys, so that the >> plaintext to the last cipher is both randomized and hidden even from >> the authorized user. I always recommend using three ciphers, which >> allows one to be completely broken without exposing the others. > >Then the attacker gets known plaintext against a cipher that happens >to be built from two or three other ciphers. And if we believe we >cannot have confidence without proof, then we have the same problem >we started with. We are just as motivated to triple the ciphers that >that are themselves tripled ciphers. But that argument makes sense only if every "cipher" is the same as every other "cipher," something we all know to be false. That is a debating ploy, not an argument. The "cipher" composed of a sequence of different ciphers is a vastly more complex transformation than any component cipher, as we can see from the expanded keyspace. Using a sequence of different ciphers is how we multiply ciphers both in number and complexity; this is Shannon multiplication of secrecy systems. Even just a single tripling addresses practical problems that conventional ciphering wisdom otherwise leaves open: As one example, when we use one cipher alone, that cipher may actually be already broken, in the context of the opponents. What we can do about this is to place that same cipher in a stack with other ciphers. That hides known-plaintext information. Knowing both clear ciphertext and something about plaintext is how ciphers are broken; if we can really hide either or both, a cipher becomes far stronger in practice. Of course, even if one of the ciphers *is* broken in situ, the others continue to protect our data. That is Shannon multiplication of secrecy systems. As another example, when we use one cipher alone, if our cipher is already broken, we will continue to use it and so expose our data day-after-day, until we do something about it. What we can do about that is to change ciphers, and so have a new chance of getting a strong one. And if we change ciphers frequently, we also have the advantage of reducing the amount of data under any one cipher, which reduces both the motivation and the ability to invest in attacks on that cipher. Selecting among different ciphers is Shannon addition of secrecy systems. Clearly, if we do both -- use, say, three ciphers in sequence and change them frequently -- we gain the advantage of changing ciphers, with protection against using weak ciphers. And that is Shannan's "algebra of secrecy systems." --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Known plaintext considered harmless Date: Thu, 21 Jun 2001 14:17:45 -0600 From: John Myre <jmyre@sandia.gov> Message-ID: <3B325669.A6F389E6@sandia.gov> References: <3b32391a.9437472@news.io.com> Newsgroups: sci.crypt Lines: 38 Terry Ritter wrote: > > On Thu, 21 Jun 2001 01:50:22 -0700, in <3B31B54E.AE0A120D@nospam.net>, > in sci.crypt Bryan Olson <nospam@nospam.net> wrote: > > >Terry Ritter wrote: > >> <snip> > >> The obvious approach to minimizing the risk of known-plaintext is to > >> encipher at least twice with different ciphers and keys, so that the > >> plaintext to the last cipher is both randomized and hidden even from > >> the authorized user. I always recommend using three ciphers, which > >> allows one to be completely broken without exposing the others. > > > >Then the attacker gets known plaintext against a cipher that happens > >to be built from two or three other ciphers. And if we believe we > >cannot have confidence without proof, then we have the same problem > >we started with. We are just as motivated to triple the ciphers that > >that are themselves tripled ciphers. > > But that argument makes sense only if every "cipher" is the same as > every other "cipher," something we all know to be false. That is a > debating ploy, not an argument. <snip> It might be right to construct a cipher out of three component ciphers, different in structure. It's incredibly difficult to believe that it wouldn't be stronger. The *logical argument*, however, goes to Bryan. From the premise that we don't know the strength of our ciphers we can only conclude that we don't know the strength of any construction based on them, either. If we want to conclude that tripling is right, we have to assume something like "most of our presumed-strong ciphers actually are strong, we just don't know which ones," or some other premise that says *something* about the component cipher strengths. JM
Subject: Re: Known plaintext considered harmless Date: Thu, 21 Jun 2001 14:03:40 -0700 From: "Paul Pires" <diodude@got.net> Message-ID: <cjtY6.104428$Ne5.3793518@e420r-sjo3.usenetserver.com> References: <3B325669.A6F389E6@sandia.gov> Newsgroups: sci.crypt Lines: 72 John Myre <jmyre@sandia.gov> wrote in message news:3B325669.A6F389E6@sandia.gov... > Terry Ritter wrote: > > > > On Thu, 21 Jun 2001 01:50:22 -0700, in <3B31B54E.AE0A120D@nospam.net>, > > in sci.crypt Bryan Olson <nospam@nospam.net> wrote: > > > > >Terry Ritter wrote: > > >> > <snip> > > >> The obvious approach to minimizing the risk of known-plaintext is to > > >> encipher at least twice with different ciphers and keys, so that the > > >> plaintext to the last cipher is both randomized and hidden even from > > >> the authorized user. I always recommend using three ciphers, which > > >> allows one to be completely broken without exposing the others. > > > > > >Then the attacker gets known plaintext against a cipher that happens > > >to be built from two or three other ciphers. And if we believe we > > >cannot have confidence without proof, then we have the same problem > > >we started with. We are just as motivated to triple the ciphers that > > >that are themselves tripled ciphers. > > > > But that argument makes sense only if every "cipher" is the same as > > every other "cipher," something we all know to be false. That is a > > debating ploy, not an argument. > <snip> > > It might be right to construct a cipher out of three component > ciphers, different in structure. It's incredibly difficult to > believe that it wouldn't be stronger. The *logical argument*, > however, goes to Bryan. From the premise that we don't know > the strength of our ciphers we can only conclude that we don't > know the strength of any construction based on them, either. Playing Devils advocate. If the individual threat to all three ciphers was something that involved known plaintext. Wouldn't it be obvious that combining the ciphers must be more secure since the intermediate ciphertexts (AKA the intermediate plaintexts) are not preserved? Cipher 1 may have a known plaintext but the corresponding ciphertext is gone. Ciphert 2 has no known plaintext or ciphertext. Cipher 3 has a known ciphertext but no known plaintext. Is there any known "known plaintext attack" that works without knowledge of the ciphertext? Is there any ciphertext only attack that can work when the plaintext is unknowable and Pseudo-random? Forget the philosophy of multi encryption and check the assumptions for all known attacks. Sure this only applies to Known attacks, what about the unknown ones? Who cares? It may be possible to *prove* that a method is unbreakable to all known attacks to date, faster than brute force. That has to be worth something. This is the one part of this multi-encryption argument that I just can't get a grip on. Folks seem to be arguing the Gotta-be-there weaknesses of the individual ciphers but I can't see how the requirements for the Gotta-be-there attacks are provided by the multi cipher example. It looks like a no-go from front to back, middle out and back to front. Am I too far gone here or just missing a clue? Paul > > If we want to conclude that tripling is right, we have to assume > something like "most of our presumed-strong ciphers actually are > strong, we just don't know which ones," or some other premise > that says *something* about the component cipher strengths. > > JM
Subject: Re: Known plaintext considered harmless Date: Fri, 22 Jun 2001 01:00:35 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3b329843.3659104@news.powersurfr.com> References: <cjtY6.104428$Ne5.3793518@e420r-sjo3.usenetserver.com> Newsgroups: sci.crypt Lines: 19 On Thu, 21 Jun 2001 14:03:40 -0700, "Paul Pires" <diodude@got.net> wrote, in part: >Sure this only applies to Known attacks, what about the unknown ones? >Who cares? It may be possible to *prove* that a method is unbreakable >to all known attacks to date, faster than brute force. >That has to be worth something. >Am I too far gone here or just missing a clue? The only thing missing here is that the individual ciphers it is being proposed to triple up are *already* immune to any known attacks to date that is faster than brute force! Still, immunity to any unknown attack remotely similar to the kinds of attacks that are known must be worth something... John Savard http://home.ecn.ab.ca/~jsavard/index.html
Subject: Re: Known plaintext considered harmless Date: 22 Jun 2001 13:26:14 GMT From: mdw@nsict.org (Mark Wooding) Message-ID: <slrn9j6hrm.clo.mdw@daryl.nsict.org> References: <cjtY6.104428$Ne5.3793518@e420r-sjo3.usenetserver.com> Newsgroups: sci.crypt Lines: 77 Paul Pires <diodude@got.net> wrote: > Playing Devils advocate. If the individual threat to all three > ciphers was something that involved known plaintext. Wouldn't > it be obvious that combining the ciphers must be more secure > since the intermediate ciphertexts (AKA the intermediate plaintexts) > are not preserved? I think there's very little that's `obvious' around here. However, we can /prove/ that cascading ciphers doesn't introduce any weaknesses, assuming that they're keyed independently. (The proof is rather dull, and included below for the sake of completeness. See Bellare, Desai, Jokipii and Rogaway for background information.) Proving that it actually helps seems very hard. It's intuitively fairly clear that inventing a new key, pretending we don't know what it is, and gluing a cipher with that key before or after the encryption (which is basically what the proof below does) isn't the most direct or efficient way of breaking an encryption scheme. But this seems very hard to prove. The proof Suppose that X = (K, E, D) and Y = (K', E', D') are symmetric encryption systems. Define Seq(X, Y) = (K^*, E^*, D^*) as follows: * K^*(1^k) computes \kappa_X <- K (1^k) and \kappa_Y <- K'(1^k, and returns the pair (\kappa_X, \kappa_Y) * E^*(\kappa, x), where \kappa = (\kappa_X, \kappa_Y), computes c_X <- E(\kappa_X, x) and returns c <- E'(\kappa_Y, c_X). * D^*(\kappa, x), where \kappa = (\kappa_X, \kappa_Y), computes c_X<- D'(\kappa_Y, x) and returns p <- D(\kappa_X, c_X). Suppose A is an adversary which runs in time t, performs q_e queries to a left-or-right encryption oracle totalling \mu_e bits, and performs q_d queries to a decryption oracle totalling \mu_d bits, and has advantage \epsilon distinguishing Seq(X, Y) in the left-or-right sense. We construct the adversary A_X as follows: Adversary A_X^{\mathcal{LR}(., .), \mathcal{D}(.)} Choose \kappa <- K'(1^k) Get b <- A^{\mathcal{LR}'(., .), \mathcal{D}'(.)} where \mathcal{LR}'(l, r) = E'(\kappa, \mathcal{LR}(l, r)) \mathcal{D}'(c) = \mathcal{D}(D'(c)) return b This adversary distinguishes X with the same advantage as A has against Seq(X, Y), and makes the same number of queries ot its oracles. The additional running time is only the time taken to run K'. The additional size of the queries is related only to the ciphertext expansion in E. Similarly, we construct an adversary A_Y: Adversary A_X^{\mathcal{LR}(., .), \mathcal{D}(.)} Choose \kappa <- K(1^k) Get b <- A^{\mathcal{LR}'(., .), \mathcal{D}'(.)} where \mathcal{LR}'(l, r) = \mathcal{LR}(E(\kappa, l), E(\kappa, r)) \mathcal{D}'(c) = D'(\mathcal{D}(c)) return b with the same properties against Y. This proves that the combination Seq(X, Y) is no less secure than the stronger of X and Y (in the left-or-right sense). If we define by induction, Seq(A, B, C, ...) = Seq(A, Seq(B, Seq(C, ...))) we see can we can build a cascade of ciphers which is at least as strong (in the left-or-right sense) as the strongest cipher in the cascade, whichever one that is. (Left-or-right security is at most a factor of 2 weaker than real-or-random security, and much easier to use in this instance.) -- [mdw]
Subject: Re: Known plaintext considered harmless Date: Fri, 22 Jun 2001 16:10:45 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3b336d3f.2356247@news.powersurfr.com> References: <slrn9j6hrm.clo.mdw@daryl.nsict.org> Newsgroups: sci.crypt Lines: 13 On 22 Jun 2001 13:26:14 GMT, mdw@nsict.org (Mark Wooding) wrote, in part: >I think there's very little that's `obvious' around here. However, we >can /prove/ that cascading ciphers doesn't introduce any weaknesses, >assuming that they're keyed independently. That is not true when the second cipher in the chain is vulnerable to a known-plaintext attack, particularly when the input to the first cipher is either compressible, or is expanded by the first cipher. John Savard http://home.ecn.ab.ca/~jsavard/index.html
Subject: Re: Known plaintext considered harmless Date: Thu, 21 Jun 2001 23:40:30 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b3285bc.5858111@news.io.com> References: <3B325669.A6F389E6@sandia.gov> Newsgroups: sci.crypt Lines: 67 On Thu, 21 Jun 2001 14:17:45 -0600, in <3B325669.A6F389E6@sandia.gov>, in sci.crypt John Myre <jmyre@sandia.gov> wrote: >Terry Ritter wrote: >> >> On Thu, 21 Jun 2001 01:50:22 -0700, in <3B31B54E.AE0A120D@nospam.net>, >> in sci.crypt Bryan Olson <nospam@nospam.net> wrote: >> >> >Terry Ritter wrote: >> >> ><snip> >> >> The obvious approach to minimizing the risk of known-plaintext is to >> >> encipher at least twice with different ciphers and keys, so that the >> >> plaintext to the last cipher is both randomized and hidden even from >> >> the authorized user. I always recommend using three ciphers, which >> >> allows one to be completely broken without exposing the others. >> > >> >Then the attacker gets known plaintext against a cipher that happens >> >to be built from two or three other ciphers. And if we believe we >> >cannot have confidence without proof, then we have the same problem >> >we started with. We are just as motivated to triple the ciphers that >> >that are themselves tripled ciphers. >> >> But that argument makes sense only if every "cipher" is the same as >> every other "cipher," something we all know to be false. That is a >> debating ploy, not an argument. ><snip> > >It might be right to construct a cipher out of three component >ciphers, different in structure. It's incredibly difficult to >believe that it wouldn't be stronger. The *logical argument*, >however, goes to Bryan. From the premise that we don't know >the strength of our ciphers we can only conclude that we don't >know the strength of any construction based on them, either. That "logical argument" is a "red herring": I made no claim that cipher stacks have provable known strength. But since we are comparing the situation where we have one cipher against having a stack of three ciphers, the issue would seem to be the same in both cases. I claim that, simply by using a cipher stack, known-plaintext information is not available to the opponent for use in attacks against the component ciphers. Not exposing known-plaintext is a very serious advantage. >If we want to conclude that tripling is right, we have to assume >something like "most of our presumed-strong ciphers actually are >strong, we just don't know which ones," or some other premise >that says *something* about the component cipher strengths. Well, if we suppose that *all* are ciphers are weak, there might seem to be no point in using ciphers at all. On the other hand, multiciphering with three different ciphers and independent keys makes an overall "cipher" that is arguably much stronger than its component parts, and also prevents the exposure of information which might otherwise have been used to attack those parts. So even if every fundamental block cipher really is weak, the multiciphering stack of three ciphers may *not* be. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Known plaintext considered harmless Date: Fri, 22 Jun 2001 02:03:41 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B328B5D.9BB0AA37@t-online.de> References: <3b3285bc.5858111@news.io.com> Newsgroups: sci.crypt Lines: 19 Terry Ritter wrote: > [snip] > On the other hand, multiciphering with three different ciphers and > independent keys makes an overall "cipher" that is arguably much > stronger than its component parts, and also prevents the exposure of > information which might otherwise have been used to attack those > parts. So even if every fundamental block cipher really is weak, the > multiciphering stack of three ciphers may *not* be. I guess that it could be useful in this connection to recall the fact that a good block cipher needs a sufficient number of rounds, which are put together in a cascading fashion not 'entirely' different in principle to cascading multiple ciphers. M. K. Shen
Subject: Re: Known plaintext considered harmless Date: Fri, 22 Jun 2001 00:42:12 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3b329348.2383501@news.powersurfr.com> References: <3B328B5D.9BB0AA37@t-online.de> Newsgroups: sci.crypt Lines: 15 On Fri, 22 Jun 2001 02:03:41 +0200, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote, in part: >I guess that it could be useful in this connection to >recall the fact that a good block cipher needs a sufficient >number of rounds, which are put together in a cascading >fashion not 'entirely' different in principle to cascading >multiple ciphers. True. Of course, an important difference is that block ciphers usually repeat the same round many times, although with different subkeys, and this could be bad if the round is weak in certain ways. John Savard http://home.ecn.ab.ca/~jsavard/index.html
Subject: Re: Known plaintext considered harmless Date: Thu, 21 Jun 2001 23:52:10 -0300 From: "Alexis Machado" <alexismachado@ieg.com.br> Message-ID: <tj5cfo5dsdl1ca@corp.supernews.com> References: <3B328B5D.9BB0AA37@t-online.de> Newsgroups: sci.crypt Lines: 28 "Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote in message news:3B328B5D.9BB0AA37@t-online.de... > > > Terry Ritter wrote: > > > [snip] > > On the other hand, multiciphering with three different ciphers and > > independent keys makes an overall "cipher" that is arguably much > > stronger than its component parts, and also prevents the exposure of > > information which might otherwise have been used to attack those > > parts. So even if every fundamental block cipher really is weak, the > > multiciphering stack of three ciphers may *not* be. > > I guess that it could be useful in this connection to > recall the fact that a good block cipher needs a sufficient > number of rounds, which are put together in a cascading > fashion not 'entirely' different in principle to cascading > multiple ciphers. > You discovered why cipher chaining is not necessary. --- Alexis
Subject: Re: Known plaintext considered harmless Date: Fri, 22 Jun 2001 03:35:14 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b32bc2f.5448490@news.io.com> References: <tj5cfo5dsdl1ca@corp.supernews.com> Newsgroups: sci.crypt Lines: 53 On Thu, 21 Jun 2001 23:52:10 -0300, in <tj5cfo5dsdl1ca@corp.supernews.com>, in sci.crypt "Alexis Machado" <alexismachado@ieg.com.br> wrote: >"Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote in message >news:3B328B5D.9BB0AA37@t-online.de... >> >> >> Terry Ritter wrote: >> > >> [snip] >> > On the other hand, multiciphering with three different ciphers and >> > independent keys makes an overall "cipher" that is arguably much >> > stronger than its component parts, and also prevents the exposure of >> > information which might otherwise have been used to attack those >> > parts. So even if every fundamental block cipher really is weak, the >> > multiciphering stack of three ciphers may *not* be. >> >> I guess that it could be useful in this connection to >> recall the fact that a good block cipher needs a sufficient >> number of rounds, which are put together in a cascading >> fashion not 'entirely' different in principle to cascading >> multiple ciphers. >> > >You discovered why cipher chaining is not necessary. First of all, "chaining" is the worst possible description of multiciphering: A "chain" is only as strong as its weakest link; multiciphering is as strong as its strongest cipher. Next, the point of multiciphering is not strength, per se. If we could trust the strength we supposedly get from a single cipher, there would be no point. Unfortunately there is no way to know how a cipher will fare against real opponents; there is no feedback, thus no way to know when we have succeeded or failed. We cannot know how good a design really is with respect to real opponents. The reason for multiciphering is to address this uncertainty as best we can. Using structurally different ciphers and different keys is fundamentally different than just using more rounds. Usually we have a fixed design and don't have the opportunity to triple the number of rounds anyway. And we can't just go around re-designing standard ciphers under the illusion that more rounds and an arbitrary expanded key schedule is necessarily better; it is not. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Known plaintext considered harmless Date: Fri, 22 Jun 2001 00:57:43 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3b3294be.2757790@news.powersurfr.com> References: <3B325669.A6F389E6@sandia.gov> Newsgroups: sci.crypt Lines: 58 On Thu, 21 Jun 2001 14:17:45 -0600, John Myre <jmyre@sandia.gov> wrote, in part: >From the premise that we don't know >the strength of our ciphers we can only conclude that we don't >know the strength of any construction based on them, either. True. But even a weak cipher, as long as it does have a variable key, will indeed prevent a known-plaintext attack on the next cipher in the chain. Similarly, a weak cipher with a variable key will deny known ciphertext to the attacker of the preceding cipher in the chain. So, in a certain case - where one of the three ciphers is weak only against a known plaintext attack - something has been achieved, hence improving the odds. The point is, though, without proof of strength in either case, we don't know either that using three ciphers is warranted (any one recognized modern cipher may be strong enough, as generally believed) or that it will be sufficient to solve the problem (our unknown opponents may have even more powerful techniques than we guess). Thus, using three ciphers in a row will only improve security under a certain set of conditions. This is a valid criticism. But on the other hand, it's an easy enough thing to do, and, since many messages need to stay secret for extended periods, and since computers are getting faster at such a rate (even quantum computers may be on the horizon) it's just possible that even if modern ciphers are quite secure at present, it is really going to be worth tripling up against threats that will emerge within the next 100 years. To me, though, the killer criticism of using, say, a Rijndael/MARS/SAFER+ sandwich for encryption is that the danger of a breakthrough against block ciphers is - obviously - small in comparison to the danger of solving far less messy problems of far greater general utility and with a wider array of mathematical tools to attack them. Factoring. Discrete logarithm. If people are going to insist on using public-key cryptosystems to distribute their keys, possible weaknesses in block ciphers in general seem like a very small threat. (However, the risk that any single block cipher could have a severe, unnoticed flaw is, I have to admit, large enough to be real, which is a strong argument for multiciphering.) Thus, I tend to think that any serious attempt to upgrade the security of conventional cryptography - and such attempts are quite possible, and don't require inordinate amounts of computer time to implement - is quite properly viewed as pointless, except for those who are willing to give up the convenience of public-key cryptography. (They might still *use* PKC, however, to augment the security of those hand-transported secret keys.) John Savard http://home.ecn.ab.ca/~jsavard/index.html
Subject: Re: Known plaintext considered harmless Date: Fri, 22 Jun 2001 01:48:27 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9gu85b$2261$1@agate.berkeley.edu> References: <3b3294be.2757790@news.powersurfr.com> Newsgroups: sci.crypt Lines: 7 John Savard wrote: >But even a weak cipher, as long as it does have a variable key, >will indeed prevent a known-plaintext attack on the next cipher in the >chain. How do you know? If we don't know for certain whether our ciphers are secure (and we don't know), we can't know this for certain, either.
Subject: Re: Known plaintext considered harmless Date: Fri, 22 Jun 2001 06:15:02 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3b32dfaf.1885474@news.powersurfr.com> References: <9gu85b$2261$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 43 On Fri, 22 Jun 2001 01:48:27 +0000 (UTC), daw@mozart.cs.berkeley.edu (David Wagner) wrote, in part: >John Savard wrote: >>But even a weak cipher, as long as it does have a variable key, >>will indeed prevent a known-plaintext attack on the next cipher in the >>chain. >How do you know? If we don't know for certain whether our ciphers are >secure (and we don't know), we can't know this for certain, either. Maybe I just defined my terms badly. One can have a cipher that isn't secure, but is still known to (usually) produce different ciphertext for any plaintext if the key is changed. Of course, in that connection, one might note that DESX doesn't gain any resistance to differential cryptanalysis, which is usually considered a "known-plaintext" attack. Because you don't really need to know the plaintext itself with certainty, only the XOR between pairs of plaintexts, to do differential cryptanalysis. Thus, a cascade of three ciphers that are very weak against a differential attack can still be submitted to a differential attack; as long as one can cascade the characteristics. (If they're very weak, there will be multiple possibilities.) So if some unknown attack has similar properties... I do agree that it is only for a very specific circumstance that triple encipherment (for example) is neither unnecessary nor useless, and there is no particularly compelling evidence to suggest that the strength of contemporary block ciphers is in that narrow range. But I also noted that, if triple encipherment is unnecessary at present, as most experts believe, then within the next 75-100 years, advances in computer power just might cause their strength to at least enter that zone. Of course, on http://home.ecn.ab.ca/~jsavard/crypto/co041205.htm I suggest rather more extreme measures for the worriers among us than mere triple encipherment. John Savard http://home.ecn.ab.ca/~jsavard/index.html
Subject: Re: Known plaintext considered harmless Date: Fri, 22 Jun 2001 08:03:15 GMT From: Tim Tyler <tt@iname.com> Message-ID: <GFBnpF.19o@bath.ac.uk> References: <3B325669.A6F389E6@sandia.gov> Newsgroups: sci.crypt Lines: 19 John Myre <jmyre@sandia.gov> wrote: : If we want to conclude that tripling is right, we have to assume : something like "most of our presumed-strong ciphers actually are : strong, we just don't know which ones," or some other premise : that says *something* about the component cipher strengths. That would be what was needed if we wanted to claim that a cypher stack was *strong*. You barely need to say anything to claim that it's *stronger* than any of the individual encryptions. No doubt the proper point of comparison for a cypher stack would be a purpose-designed algorithm with three times the keyspace of conventional cyphers. -- __________ |im |yler http://rockz.co.uk/ http://alife.co.uk/ http://atoms.org.uk/
Subject: Re: Known plaintext considered harmless Date: Thu, 21 Jun 2001 22:14:41 -0700 From: Bryan Olson <nospam@nospam.net> Message-ID: <3B32D441.CFF98E11@nospam.net> References: <3b32391a.9437472@news.io.com> Newsgroups: sci.crypt Lines: 52 Terry Ritter wrote: > > On Thu, 21 Jun 2001 01:50:22 -0700, in <3B31B54E.AE0A120D@nospam.net>, > in sci.crypt Bryan Olson <nospam@nospam.net> wrote: > > >Terry Ritter wrote: > >> > >> John Savard) wrote: > >> > >> >[...] > >> >It is possible to have reasons for confidence in something that fall > >> >short of proof, and it is even possible for such reasons to be > >> >sufficient to make some forms of precaution unwarranted. > >> > >> Not in cryptography. > > > >[...] > > > >> The obvious approach to minimizing the risk of known-plaintext is to > >> encipher at least twice with different ciphers and keys, so that the > >> plaintext to the last cipher is both randomized and hidden even from > >> the authorized user. I always recommend using three ciphers, which > >> allows one to be completely broken without exposing the others. > > > >Then the attacker gets known plaintext against a cipher that happens > >to be built from two or three other ciphers. And if we believe we > >cannot have confidence without proof, then we have the same problem > >we started with. We are just as motivated to triple the ciphers that > >that are themselves tripled ciphers. > > But that argument makes sense only if every "cipher" is the same as > every other "cipher," something we all know to be false. That is a > debating ploy, not an argument. Oh spare us the nonsense. That mistake - evaluating all ciphers as the same - is the error you commit when you disagreed with Savard's quote above. > The "cipher" composed of a sequence of different ciphers is a vastly > more complex transformation than any component cipher, as we can see > from the expanded keyspace. But you don't even look at the component ciphers. You blindly advocate composing three with no regard to their complexity. Whatever the right extent of conservative design is, it makes no sense to say it's automatically three times what any other cipher designers choose. --Bryan
Subject: Re: Known plaintext considered harmless Date: Tue, 19 Jun 2001 23:09:17 GMT From: Tim Tyler <tt@iname.com> Message-ID: <GF79nH.E3H@bath.ac.uk> References: <3B2F81DE.901777B1@sandia.gov> Newsgroups: sci.crypt Lines: 56 John Myre <jmyre@sandia.gov> wrote: : Tim Tyler wrote: : <snip> :> You go far too far. While tying yourself in knots to avoid known :> plaintext may be over the top, avoiding it *is* desirable. : But the question is: *how* desirable? Exactly how much effort : is it worth? I'd agree with (anonymous) that the proper solution : is to reinforce the cipher. [...] Reinforcing the cypher is not a solution. Consider, for example, the case where there is no known attack on the cypher, but the key generator is broken. :> You presume that cryptanalytic attack is the only possible method of :> getting information relating to the key of a cypher. : ? Attackers can get hold of information about keys by other means besides cryptanalysis. :> This is not the case. If the number of possible keys can be reduced - :> by any means - known-plaintext attacks can become a practical issue. : That is at best an exaggeration. You can reduce the number of : possible keys quite easily by brute force: guess a few keys, : decrypt the entire message for each guess, and discard the ones : that are clearly nonsense. [...] Known-plaintext attacks can *sometimes* become a practical issue, then. : In practice - this is simply not an issue. So cryptosystems are never compromised by regularities and lack of entropy in key generaors? : The point is that if a simple keysearch can be made practical, : because the entropy (unknown bits in the key) is small enough, : then using obfuscation on the source text as a way to prevent : that attack is almost certainly pointless. I believe I can see the point - but where is the argument supporting it? : Terry's response is more reasoned. The suspicion that maybe we : are all fooling ourselves, that there *aren't* any ciphers that : we can trust are as strong as we think, is at least defensible. : I think he's wrong, but of course I can't prove it. Even in fantasy-land - where the cyphers are known to be theoretically invulnerable - there are still other ways things can go wrong. Known plaintext will never be irrelevant. -- __________ |im |yler tt@iname.com Home page: http://alife.co.uk/tim/
Subject: Re: Known plaintext considered harmless Date: Tue, 19 Jun 2001 23:20:53 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3b2fddcd.29340382@news.powersurfr.com> References: <3B2F81DE.901777B1@sandia.gov> Newsgroups: sci.crypt Lines: 19 On Tue, 19 Jun 2001 10:46:22 -0600, John Myre <jmyre@sandia.gov> wrote, in part: >The point is that if a simple keysearch can be made practical, >because the entropy (unknown bits in the key) is small enough, >then using obfuscation on the source text as a way to prevent >that attack is almost certainly pointless. It's true that the old days of 40-bit keys are now behind us...finding a way to achieve security under such a constraint may well be an impossible challenge, but not entirely without value. Particularly if those days might be coming back - in effect. What if quantum computers start appearing at corner computer stores near you? Won't simple keysearch get a lot simpler for all those back intercepts? John Savard http://home.ecn.ab.ca/~jsavard/frhome.htm
Subject: Re: Known plaintext considered harmless Date: Fri, 22 Jun 2001 19:33:42 +0200 From: "Thomas J. Boschloo" <nospam@multiweb.nl> Message-ID: <3B338176.539BDD09@multiweb.nl> References: <GF689w.H76@bath.ac.uk> Newsgroups: sci.crypt Lines: 73 -----BEGIN PGP SIGNED MESSAGE----- Tim Tyler wrote: > > lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> wrote: > > : NO CONSIDERATION WHATSOEVER should be given to manipulating or > : constraining the data structures in the hopes of making the > : encryption stronger! [...] > > : Let us all agree that it is time to put concerns about known plaintext > : behind us. Recommendations to avoid it are obsolete. > > You go far too far. While tying yourself in knots to avoid known > plaintext may be over the top, avoiding it *is* desirable. > > You presume that cryptanalytic attack is the only possible method of > getting information relating to the key of a cypher. This is not the > case. If the number of possible keys can be reduced - by any means - > known-plaintext attacks can become a practical issue. I am in no way a cryptographer, so I'll try to keep this short. What I wonder about is if compression does really 'reduce' plain-text, or if it does only add to it? I am at the moment reading an interesting article on practical low-tech attacks on steganography <C'T magazine 7/8 2001> and the randomness of certain stego applications is what gives them away, so it might be a problem in crypto also. If you get 8 zero's of plaintext inside a PGP(tm) encrypted packet, you sure know that it is not PGP encrypted because it is clearly not compressed. So you can discard possible plaintexts that you could otherwise not discard at all. It may not be much situations in which this will happen, but my motto has always been 'Keep It Simple (stupid)'. Compression also results in various 'end of data' markers and maybe even checksums to see if it decompressed right. And if compression is so important to crypto security, then why isn't it incorporated into new encryption algorithms to make them more secure? Another interesting question is where to start compressing. If you start at the beginning your LZ buffer (is it called that?) might still be empty and certainly a certain plaintext will always be compressed the same way with most algorithms (if you can choose random redundancy, you could and should have compressed it further). If you start at the end, you might as well have run an extra layer of encryption backwards to solve any problems there were to begin with. BTW I like the fixed plaintext size argument someone made. Very Anon-server like (and I like Anon servers, like the one the original message was posted from and which for once made anonymous messages look good for a change, it might have been a renown cryptographer who made the original statement for all we know, which would thus have polluted the argument (or ruined his reputation, depending on how you look at it ;-)). Happy regards, sorry if I didn't make any sense, I am only a crypto implementator wannabe, not a specialist. Thomas J. Holland -----BEGIN PGP SIGNATURE----- Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com> Comment: My homepage <http://home.soneraplaza.nl/mw/prive/boschloo> iQB5AwUBOzNzZAEP2l8iXKAJAQFR2wMfZLgE2lMaAMBO32cDeO5RSkJr0dIr1BJ/ WidiS/MvPqWo2WndZWq1vdwfo6VoKeRcua2ikGR635o1eEZ+gnwCA7CwnPiJHQ8i 9LEG8qPzF0DP8PfkdhVmuYHV/3wJjX8YMUzbSA== =8xF2 -----END PGP SIGNATURE----- -- "Only flawed software is more secure with a closed source policy", me
Subject: Re: Known plaintext considered harmless Date: 19 Jun 2001 22:40:34 -0000 From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> Message-ID: <20010619224034.10622.qmail@nym.alias.net> References: <20010619052032.804.qmail@nym.alias.net> Newsgroups: sci.crypt Lines: 52 Here's an example of known-plaintext-phobia at its worst, from a post which appeared a few hours ago: : From: Thierry Nivon <tnivon@waika9.com> : Date: Tue, 19 Jun 2001 22:50:33 +0200 : Message-ID: <9godml$2ou$2@fenris.isp.9tel.net> : : because the beginning of the document is always (nearly) the same : <xml .... : wich brings a little (verry little) bit of information : : Thierry Nivon : : Mok-Kong Shen wrote: : : > : > I read somewhere an article stating that the possibility : > in the new standard for XML-security of user selective determination of : > parts of an XML document to be encrypted : > is essential, for otherwise one could encrypt only the : > whole document and that would be bad for security. Could : > someone explain why the encryption of the whole document : > is bad in clear-cut terms? Thanks in advance. : > : > M. K. Shen We see a claim that piecewise encryption of XML documents is essential, with the suggested reason being that otherwise there is known plaintext in that every document starts with "<xml". Of course, it's unlikely that this is the true reason why the XML encryption effort is supporting encryption of subparts. But it is disturbing that it is offered as an explanation, that someone presumably at least slightly knowledgeable in cryptography believes that it is unsafe to encrypt XML documents because they all start the same way. This is exactly the error which the cryptographic community must correct. For too long have naive and inexperienced users been taught to fear known plaintext and to produce elaborate monstrosities in a futile attempt to avoid weakening their encryption. It is an abrogation of the responsibility of professional cryptographers to allow users of this technology to suffer under such a misconception. Imagine if this attitude were allowed to go uncorrected, and if the XML encryption group had actually adopted the need to encrypt parts, a requirement which has added tremendous complexity to the specification, purely out of a misguided fear about known plaintext! This disaster would be the fault, ultimately, of the cryptographic community for failing to speak with a clear and united voice on this issue. It is time to put this sad error to an end. Known plaintext is not harmful, and will not weaken a properly-applied encryption transform.
Subject: Re: Known plaintext considered harmless Date: 19 Jun 2001 23:05:17 GMT From: david_a_scott@emailv.com (SCOTT19U.ZIP_GUY) Message-ID: <90C5AFD90H110W296LC45WIN3030R@207.36.190.226> References: <20010619224034.10622.qmail@nym.alias.net> Newsgroups: sci.crypt Lines: 27 mix@anon.lcs.mit.edu (lcs Mixmaster Remailer) wrote in <20010619224034.10622.qmail@nym.alias.net>: > >It is time to put this sad error to an end. Known plaintext is not >harmful, and will not weaken a properly-applied encryption transform. > Actually any known plaintext is harmful and will weaken an ecryption system. But if you properly compress to remove the common known parts then you apply the encryption. Since if they are known they can be added in during the decryption decompression process. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM" http://www.jim.com/jamesd/Kong/scott19u.zip My website http://members.nbci.com/ecil/index.htm My crypto code http://radiusnet.net/crypto/archive/scott/ MY Compression Page http://members.nbci.com/ecil/compress.htm **TO EMAIL ME drop the roman "five" ** Disclaimer:I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged. As a famous person once said "any cryptograhic system is only as strong as its weakest link"
Subject: Re: Known plaintext considered harmless Date: Wed, 20 Jun 2001 10:34:09 GMT From: Tim Tyler <tt@iname.com> Message-ID: <GF85Cx.Ctp@bath.ac.uk> References: <20010619224034.10622.qmail@nym.alias.net> Newsgroups: sci.crypt Lines: 16 lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> wrote: : It is time to put this sad error to an end. Known plaintext is not : harmful, and will not weaken a properly-applied encryption transform. How do you know whan you have one of them? How do you know how much entropy there is in your key generator? How do you know whether your keybook has been quietly copied? You don't know any of these things. Known plaintext is rightly considered harmful. It is the assertion that is is harmless that is the "sad error". -- __________ |im |yler tt@iname.com Home page: http://alife.co.uk/tim/
Subject: Re: Known plaintext considered harmless Date: Wed, 20 Jun 2001 16:24:31 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9gqinv$96v$3@agate.berkeley.edu> References: <GF85Cx.Ctp@bath.ac.uk> Newsgroups: sci.crypt Lines: 20 Tim Tyler wrote: >lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> wrote: >: It is time to put this sad error to an end. Known plaintext is not >: harmful, and will not weaken a properly-applied encryption transform. > >How do you know whan you have one of them? > >How do you know how much entropy there is in your key generator? > >How do you know whether your keybook has been quietly copied? > >You don't know any of these things. If you any of these failures occur, all bets are off. Whether or not you've tried to minimize known plaintext, getting those wrong puts your system in great danger. Therefore, I would argue that it is a better use of your energies to spend time making sure you defend against those failure modes than to worry about known plaintext.
Subject: Re: Known plaintext considered harmless Date: Wed, 20 Jun 2001 19:24:44 GMT From: Tim Tyler <tt@iname.com> Message-ID: <GF8tx8.Apw@bath.ac.uk> References: <9gqinv$96v$3@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 40 David Wagner <daw@mozart.cs.berkeley.edu> wrote: : Tim Tyler wrote: :>lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> wrote: :>: It is time to put this sad error to an end. Known plaintext is not :>: harmful, and will not weaken a properly-applied encryption transform. :> :>How do you know whan you have one of them? :> :>How do you know how much entropy there is in your key generator? :> :>How do you know whether your keybook has been quietly copied? :> :>You don't know any of these things. : If you any of these failures occur, all bets are off. Whether or not : you've tried to minimize known plaintext, getting those wrong puts your : system in great danger. Indeed. : Therefore, I would argue that it is a better use of your energies to : spend time making sure you defend against those failure modes than to : worry about known plaintext. It depends on who you are, and what the relative expenditure is. As a designer of an encryption device, you may have no control over the way others feed keys to you. It may not be up to you to control how codebooks are destroyed upon enemy capture. However, you /may/ be in a position to eliminate some classes of known plaintexts. Eliminating known plaintext may not help very much - or may only help sometimes, but it can and does help. Whether you consider it worth doing should be a function of the percieved costs and benefits. Known plaintext *can* be harmful, and *can* weaken the security of messages transmitted under encryption applied with great care. -- __________ |im |yler tt@iname.com Home page: http://alife.co.uk/tim/
Subject: Re: Known plaintext considered harmless Date: Wed, 20 Jun 2001 19:45:07 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9gqug3$fpf$3@agate.berkeley.edu> References: <GF8tx8.Apw@bath.ac.uk> Newsgroups: sci.crypt Lines: 28 Tim Tyler wrote: >David Wagner <daw@mozart.cs.berkeley.edu> wrote: >: Therefore, I would argue that it is a better use of your energies to >: spend time making sure you defend against those failure modes than to >: worry about known plaintext. > >It depends on who you are, and what the relative expenditure is. As a >designer of an encryption device, you may have no control over the way >others feed keys to you. If you're a designer of an encryption device, you have no control over the plaintext being fed to you, so you can't plausibly do anything about known plaintext anyway. In any case, I thought we were talking about protocol and systems design. >Eliminating known plaintext may not help very much - or may only help >sometimes, but it can and does help. Whether you consider it worth >doing should be a function of the percieved costs and benefits. Sure. I contend, though, that the cost is very high and the benefit is low. The cost is complexity, and complexity is the worst enemy of security. The benefit is only applicable if the cipher is weak (but not too weak---it has to be just weak enough that there are practical known plaintext attacks, but no practical attacks with the reduced amount of knowledge on the text), and given the state of modern cryptography, this failure mode currently seems to have a relatively low probability when compared to the other types of failures of security, empirically speaking.
Subject: Re: Known plaintext considered harmless Date: 20 Jun 2001 14:10:15 -0600 From: mackys+usenet@dim.com (Ben Cantrick) Message-ID: <9gqvv7$ehk@flatland.dimensional.com> References: <9gqug3$fpf$3@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 30 In article <9gqug3$fpf$3@agate.berkeley.edu>, David Wagner <daw@mozart.cs.berkeley.edu> wrote: >Tim Tyler wrote: >>David Wagner <daw@mozart.cs.berkeley.edu> wrote: >>: Therefore, I would argue that it is a better use of your energies to >>: spend time making sure you defend against those failure modes than to >>: worry about known plaintext. >> >>It depends on who you are, and what the relative expenditure is. As a >>designer of an encryption device, you may have no control over the way >>others feed keys to you. > >If you're a designer of an encryption device, y