What is all this stuff about "bijective" ciphering?
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Wed, 25 Oct 2000 23:44:01 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G30F9D.Ez0@bath.ac.uk> References: <8FD894EF9H110W296@207.36.190.226> Newsgroups: sci.crypt Lines: 29 SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: : I did a search of the internet for IEEE encryption padding [...] Here's an existing padding method: http://www.cix.co.uk/~klockstone/bookends.htm This is more along the lines of padding out a file with random garbage (rather than increasing its size to a multiple of the existing block size). It pads with PRNG data. Surely this is a bad idea. It does appear that until recently there were zero bijective schemes for mapping a n-byte file to a file which is a multiple of the block size of an orthodox block cypher. In the absence of many block cyphers with variable-size blocks, use of such algorithms appear to be superior to existing padding schemes - in terms of avoiding potential security problems. Something simple like appending a 1 and padding with 0s to the end of the block can allow up to 2^128 - 1 out of 2^128 keys to be rejected without any further knowledge of the plaintext - possibly enough to reject all but one message. -- __________ http://alife.co.uk/ http://mandala.co.uk/ |im |yler tt@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sat, 28 Oct 2000 13:36:50 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G3575E.5us@bath.ac.uk> References: <8FD894EF9H110W296@207.36.190.226> Newsgroups: sci.crypt Lines: 26 SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: [RFC 1423 padding mechanism] Here's what Applied Cryptography has to say about padding: ``Pad the last block with some regular padding - zeros, ones, alternating ones and zeros - to make it a complete block. If you need to delete the padding after decryption, add the number of padding bytes as the last byte of the last block.'' -2nd ed. p. 190. So far, not very good (from the known-plaintext POV). However, we also have a method which does not change the size of the message. The idea is to encrypt the last full block *again* truncate this to the size of any short block at the end and XOR this with the plaintext of the short block (rather than encrypting that with the cypher). This means that the OFB-like bit-flipping attacks can only be applied to the short block at the end. (2nd e. p. 195 for details). This method gets a bijection - at the expense of not encrypting the end of the file very securely. -- __________ http://alife.co.uk/ http://mandala.co.uk/ |im |yler tt@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Subject: Re: DATA PADDING FOR ENCRYPTION Date: 28 Oct 2000 14:31:13 GMT From: this.address@is.for.spamers (SCOTT19U.ZIP_GUY) Message-ID: <8FDB55B74H110W296@207.36.190.226> References: <G3575E.5us@bath.ac.uk> Newsgroups: sci.crypt Lines: 45 tt@cryogen.com (Tim Tyler) wrote in <G3575E.5us@bath.ac.uk>: >SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: > >[RFC 1423 padding mechanism] > >Here's what Applied Cryptography has to say about padding: > >``Pad the last block with some regular padding - zeros, ones, alternating > ones and zeros - to make it a complete block. If you need to delete the > padding after decryption, add the number of padding bytes as the last > byte of the last block.'' -2nd ed. p. 190. > >So far, not very good (from the known-plaintext POV). However, >we also have a method which does not change the size of the message. > >The idea is to encrypt the last full block *again* truncate this to the >size of any short block at the end and XOR this with the plaintext of >the short block (rather than encrypting that with the cypher). > >This means that the OFB-like bit-flipping attacks can only be applied to >the short block at the end. (2nd e. p. 195 for details). > >This method gets a bijection - at the expense of not encrypting the end >of the file very securely. Tim I may by wrong but I don't see how it gets a bijection of all 8 bit file to all 8 bit files. Example if the encrypted file is one byte long, If the method above that you mention is bijective how did this encrypted one byte file occur? David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE http://www.jim.com/jamesd/Kong/scott19u.zip Scott famous encryption website **now all allowed** http://members.xoom.com/ecil/index.htm Scott LATEST UPDATED source for scott*u.zip http://radiusnet.net/crypto/ then look for sub directory scott after pressing CRYPTO Scott famous Compression Page http://members.xoom.com/ecil/compress.htm **NOTE EMAIL address is for SPAMERS*** I leave you with this final thought from President Bill Clinton:
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sat, 28 Oct 2000 22:12:39 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G35v13.9x3@bath.ac.uk> References: <8FDB55B74H110W296@207.36.190.226> Newsgroups: sci.crypt Lines: 42 SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: : tt@cryogen.com (Tim Tyler) wrote in <G3575E.5us@bath.ac.uk>: :>Here's what Applied Cryptography has to say about padding: :> :>``Pad the last block with some regular padding - zeros, ones, alternating :> ones and zeros - to make it a complete block. If you need to delete the :> padding after decryption, add the number of padding bytes as the last :> byte of the last block.'' -2nd ed. p. 190. :> :>So far, not very good (from the known-plaintext POV). However, :>we also have a method which does not change the size of the message. :> :>The idea is to encrypt the last full block *again* truncate this to the :>size of any short block at the end and XOR this with the plaintext of :>the short block (rather than encrypting that with the cypher). :> :>This means that the OFB-like bit-flipping attacks can only be applied to :>the short block at the end. (2nd e. p. 195 for details). :> :>This method gets a bijection - at the expense of not encrypting the end :>of the file very securely. : Tim I may by wrong but I don't see how it gets a bijection of all : 8 bit file to all 8 bit files. Example if the encrypted file is one : byte long, If the method above that you mention is bijective how : did this encrypted one byte file occur? The case of a single block is not explicitly mentioned. It can be dealt with (for example) by encryping a block of zeros and XORing that with the plaintext. I.e. "encrypt the last full block *again* (or encrypt zero if there is no full block in the first place)...". I believe this method gets a bijection - though any fractional last block is susceptible to bitflipping attacks - and such problems would not normally be tolerated. -- __________ http://alife.co.uk/ http://mandala.co.uk/ |im |yler tt@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Subject: Re: DATA PADDING FOR ENCRYPTION Date: 28 Oct 2000 23:27:32 GMT From: this.address@is.for.spamers (SCOTT19U.ZIP_GUY) Message-ID: <8FDBB69F9H110W296@207.36.190.226> References: <G35v13.9x3@bath.ac.uk> Newsgroups: sci.crypt Lines: 62 tt@cryogen.com (Tim Tyler) wrote in <G35v13.9x3@bath.ac.uk>: >SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: >: tt@cryogen.com (Tim Tyler) wrote in <G3575E.5us@bath.ac.uk>: > >:>Here's what Applied Cryptography has to say about padding: >:> >:>``Pad the last block with some regular padding - zeros, ones, >:>alternating >:> ones and zeros - to make it a complete block. If you need to delete >:> the padding after decryption, add the number of padding bytes as the >:> last byte of the last block.'' -2nd ed. p. 190. >:> >:>So far, not very good (from the known-plaintext POV). However, >:>we also have a method which does not change the size of the message. >:> >:>The idea is to encrypt the last full block *again* truncate this to >:>the size of any short block at the end and XOR this with the plaintext >:>of the short block (rather than encrypting that with the cypher). >:> >:>This means that the OFB-like bit-flipping attacks can only be applied >:>to the short block at the end. (2nd e. p. 195 for details). >:> >:>This method gets a bijection - at the expense of not encrypting the >:>end of the file very securely. > >: Tim I may by wrong but I don't see how it gets a bijection of all >: 8 bit file to all 8 bit files. Example if the encrypted file is one >: byte long, If the method above that you mention is bijective how >: did this encrypted one byte file occur? > >The case of a single block is not explicitly mentioned. > >It can be dealt with (for example) by encryping a block of zeros >and XORing that with the plaintext. > >I.e. "encrypt the last full block *again* (or encrypt zero if there >is no full block in the first place)...". > >I believe this method gets a bijection - though any fractional last >block is susceptible to bitflipping attacks - and such problems would >not normally be tolerated. I am not saying thats its not possible, It is just that the procedure is incomplete and can't be directly bijective unless it tells explicitedly how to create an ecnrypted file shorter than a block. That is if it really is bijective for every possible file as an encrypted or plaintext file. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE http://www.jim.com/jamesd/Kong/scott19u.zip Scott famous encryption website **now all allowed** http://members.xoom.com/ecil/index.htm Scott LATEST UPDATED source for scott*u.zip http://radiusnet.net/crypto/ then look for sub directory scott after pressing CRYPTO Scott famous Compression Page http://members.xoom.com/ecil/compress.htm **NOTE EMAIL address is for SPAMERS*** I leave you with this final thought from President Bill Clinton:
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sun, 29 Oct 2000 09:16:25 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G36prD.F3G@bath.ac.uk> References: <8FDBB69F9H110W296@207.36.190.226> Newsgroups: sci.crypt Lines: 79 SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: : tt@cryogen.com (Tim Tyler) wrote in <G35v13.9x3@bath.ac.uk>: :>SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: :>: tt@cryogen.com (Tim Tyler) wrote in <G3575E.5us@bath.ac.uk>: [what Applied Cryptography has to say about padding] :>:>we also have a method which does not change the size of the message. :>:> :>:>The idea is to encrypt the last full block *again* truncate this to :>:>the size of any short block at the end and XOR this with the plaintext :>:>of the short block (rather than encrypting that with the cypher). :>:> :>:>This means that the OFB-like bit-flipping attacks can only be applied :>:>to the short block at the end. (2nd e. p. 195 for details). :>:> :>:>This method gets a bijection - at the expense of not encrypting the :>:>end of the file very securely. :> :>: Tim I may by wrong but I don't see how it gets a bijection of all :>: 8 bit file to all 8 bit files. Example if the encrypted file is one :>: byte long [...] :> :>The case of a single block is not explicitly mentioned. :> :>It can be dealt with (for example) by encryping a block of zeros :>and XORing that with the plaintext. :> :>I.e. "encrypt the last full block *again* (or encrypt zero if there :>is no full block in the first place)...". :> :>I believe this method gets a bijection - though any fractional last :>block is susceptible to bitflipping attacks - and such problems would :>not normally be tolerated. : I am not saying thats its not possible, It is just that the : procedure is incomplete and can't be directly bijective unless : it tells explicitedly how to create an ecnrypted file shorter than : a block. [...] Applied cryptography is a kind-of chatty book. The author is describing the algorithm, not presenting a full working algorithm. I expect he would consider the case of a single block to be a simple degenerative case. Anyway, I missed out another important bit: After describing the bitflipping problem, it goes on to say: ``Ciphertext stealing is a better way (see figure 9.5[snip ref]). [snip description which makes little sense withouut the diagram] The benefit of this method is that all the bits of the plaintext go through the encryption algorithm.'' I believe this is bijective *provided* more than 1 block is present. It seems that the plaintext and the cyphertext are always the same length under such conditions, anyway. It pads with (say) zeros, encrypts, and then uses some clever XORing to make sure that truncating the cyphertext does not lose any information. AFAICS, ciphertext stealing does genuinely *not* work with short single blocks. http://www.io.com/~ritter/NEWS4/CTXSTEAL.HTM discusses the case of applying ciphertext stealing to single blocks in more detail. Ciphertext stealing in conjunction with OFB (i.e. simple XOR) for single blocks would be bijective (I believe) - and it's weakness would probably arise only infrequently in practice. At any rate, this is the best traditional method of dealing with the combination of large-power-of-two size block cyphers and real world files that I have seen to date. -- __________ http://alife.co.uk/ http://mandala.co.uk/ |im |yler tt@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sun, 29 Oct 2000 19:35:20 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G37IEw.494@bath.ac.uk> References: <8FDC42D42H110W296@207.36.190.226> <G36prD.F3G@bath.ac.uk> Newsgroups: sci.crypt Lines: 28 SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: : tt@cryogen.com (Tim Tyler) wrote in <G36prD.F3G@bath.ac.uk>: :>After describing the bitflipping problem, it goes on to say: :> :>``Ciphertext stealing is a better way (see figure 9.5[snip ref]). :> [snip description which makes little sense withouut the diagram] :> The benefit of this method is that all the bits of the plaintext :> go through the encryption algorithm.'' :> :>I believe this is bijective *provided* more than 1 block is present. : I don't like to think I'm a purest. But it is sort of skipping : the problem. Especailly when it can be solved with a little thought. One plus point is that it's fast and simple. By contrast, to make the transition from an 8-bit file to a 128 bit list of blocks normally takes some time, effort and programming. Matt gets this for free since he's compressing first - and winds up with one of his finitely odd streams - given that he has to convert this to *something*, converting it to a 128-bit granular file comes naturally - but other folks may not be performing such a stage - in which case a few simple XORs might look attractive. -- __________ http://alife.co.uk/ http://mandala.co.uk/ |im |yler tt@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sun, 29 Oct 2000 20:18:31 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G37KEv.6Bp@bath.ac.uk> References: <8FDC42D42H110W296@207.36.190.226> <G36prD.F3G@bath.ac.uk> Newsgroups: sci.crypt Lines: 26 SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: : Have you lookes at Matts method yet. I have very few useful comments to make. If I were considering using the device, I would have liked to have seen some more documentation relating to how the passphrase is turned into a key - so I can be confident that this is being done intelligently - using the available entropy to best effect. I was somewhat suprised to find that Matt appears to post-process the output of Rijndael in order to make it into an 8-bit granular file again. This step appears to add nothing to the security of the system. While it decreases the typical size of the resulting file somewhat, I expect anyone using the compressor /and/ the encryptor will be primarily after the security. Perhaps this makes the system a bijection between the two nicest possible sets. However, I would probably have been inclined to not expend any computational time over such a final transformation. -- __________ http://alife.co.uk/ http://mandala.co.uk/ |im |yler tt@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Subject: Re: DATA PADDING FOR ENCRYPTION Date: 30 Oct 2000 04:34:18 GMT From: this.address@is.for.spamers (SCOTT19U.ZIP_GUY) Message-ID: <8FDCD9ECEH110W296@207.36.190.226> References: <G37KEv.6Bp@bath.ac.uk> Newsgroups: sci.crypt Lines: 52 tt@cryogen.com (Tim Tyler) wrote in <G37KEv.6Bp@bath.ac.uk>: >SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: > >: Have you lookes at Matts method yet. > >I have very few useful comments to make. > >If I were considering using the device, I would have liked to have seen >some more documentation relating to how the passphrase is turned into a >key - so I can be confident that this is being done intelligently - >using the available entropy to best effect. > It allows for any key to be used if you use the -p 0x[hex code] option other wise it just an ascii string that one types in. But any Rijndael key it allowed >I was somewhat suprised to find that Matt appears to post-process the >output of Rijndael in order to make it into an 8-bit granular file again. > >This step appears to add nothing to the security of the system. > >While it decreases the typical size of the resulting file somewhat, I >expect anyone using the compressor /and/ the encryptor will be >primarily after the security. > >Perhaps this makes the system a bijection between the two nicest possible >sets. However, I would probably have been inclined to not expend any >computational time over such a final transformation. The computaion work at end is necessary to make it bijective. It really is not that much extra work. And since the compression goes to a finitely odd file and the encryption is on that specail file it would be about the same amount of work to make it match the block size of rijndael so it makes sense to do the job right in the first place which is what he did. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE http://www.jim.com/jamesd/Kong/scott19u.zip Scott famous encryption website **now all allowed** http://members.xoom.com/ecil/index.htm Scott LATEST UPDATED source for scott*u.zip http://radiusnet.net/crypto/ then look for sub directory scott after pressing CRYPTO Scott famous Compression Page http://members.xoom.com/ecil/compress.htm **NOTE EMAIL address is for SPAMERS*** I leave you with this final thought from President Bill Clinton:
Subject: Re: DATA PADDING FOR ENCRYPTION Date: 30 Oct 2000 16:11:58 GMT From: this.address@is.for.spamers (SCOTT19U.ZIP_GUY) Message-ID: <8FDD53EB6H110W296@207.36.190.226> References: <G39201.GwH@bath.ac.uk> <8FDCD9ECEH110W296@207.36.190.226> Newsgroups: sci.crypt Lines: 80 tt@cryogen.com (Tim Tyler) wrote in <G39201.GwH@bath.ac.uk>: >SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: >: tt@cryogen.com (Tim Tyler) wrote in <G37KEv.6Bp@bath.ac.uk>: >:>SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: >:> >:>: Have you lookes at Matts method yet. >:> >:>I have very few useful comments to make. >:> >:>If I were considering using the device, I would have liked to have >:>seen some more documentation relating to how the passphrase is turned >:>into a key - so I can be confident that this is being done >:>intelligently - using the available entropy to best effect. > >: It allows for any key to be used if you use the -p 0x[hex code] >: option >: other wise it just an ascii string that one types in. [...] > >I would like to hear some sort of story about hashing the passphrease to >produce the key. However, I did not know about the 0x option. >Anybody with concerns in the area could use that. > >:>I was somewhat suprised to find that Matt appears to post-process the >:>output of Rijndael in order to make it into an 8-bit granular file >:>again. >:> [...] >:>Perhaps this makes the system a bijection between the two nicest >:>possible sets. However, I would probably have been inclined to not >:>expend any computational time over such a final transformation. > >: The computaion work at end is necessary to make it bijective. > >I would have expected the set of possible outputs from Rijndael formed a >bijection with the set of input messages. > >This is a bijection between a set of 128-bit granular blocks of data and >8-bit conventional files - but it is a bijection none-the-less. > >Without looking more closely, I can't be certain what Matt's doing, >though. I can't speak for Matt. He and I use totally different words to describe the same thing. And I am sure he would word it far better than me. And yes he could have made it bidective to 128 or 256 or 512 bit boundiares if possible. But my feeling are that in theroy that you make it bijective to the smallest unit that you can. You can always make one of many whitening passes to map it to larger block sizes if one wishes. But if you have many encrypted files a large block size will take more space. After all compression was done to partly save file space. Why would one want to make the file longer by making it a specail mulitple of a blockzise. THe longer file would contain the ezact same information so from an entropy point of veiw this is a mistake. Like I have said to others this is not the end all. But I fill his implementions should be one of the ones most used people combine compression and encryption. You can add other stages far more safely in this kind of system then you can in others. Since other methods add information at each stage they are not as safe. For example you could use Matts method to create a encrypted file that is 100% bijective. You could then use soctt16u as another stage. The encryption would still be fully bijective from input file to encrypted outputfile. If each stage is fully bijective they can be much stronger in series than poorer non fully bijective methods chained together. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE http://www.jim.com/jamesd/Kong/scott19u.zip Scott famous encryption website **now all allowed** http://members.xoom.com/ecil/index.htm Scott LATEST UPDATED source for scott*u.zip http://radiusnet.net/crypto/ then look for sub directory scott after pressing CRYPTO Scott famous Compression Page http://members.xoom.com/ecil/compress.htm **NOTE EMAIL address is for SPAMERS*** I leave you with this final thought from President Bill Clinton:
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sat, 28 Oct 2000 20:56:27 GMT From: Bryan Olson <bryanolson@my-deja.com> Message-ID: <8tfeho$76b$1@nnrp1.deja.com> References: <G3575E.5us@bath.ac.uk> Newsgroups: sci.crypt Lines: 36 Tim Tyler wrote: > The idea is to encrypt the last full block *again* truncate > this to the size of any short block at the end and XOR this > with the plaintext of the short block (rather than encrypting > that with the cypher). That constitutes encrypting the last partial block with CFB mode. CFB mode handles plaintext of any size without padding. It expands the message only by the size of the IV. There's also ciphertext-stealing, which is adaptable to CBC mode. Again it only expands by the size of the IV. > This means that the OFB-like bit-flipping attacks can only > be applied to the short block at the end. (2nd e. p. 195 > for details). Page 195 does not discuss attacks, only errors. None of the standard block chaining encryption modes detect modification. Use a MAC for authentication. > This method gets a bijection - at the expense of not > encrypting the end of the file very securely. When using an authentication mechanism, there's nothing wrong with the last partial block. Without the authentication, the entire file is vulnerable. --Bryan Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sun, 29 Oct 2000 09:31:52 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G36qH4.Iqy@bath.ac.uk> References: <8tfeho$76b$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 35 Bryan Olson <bryanolson@my-deja.com> wrote: :> This means that the OFB-like bit-flipping attacks can only :> be applied to the short block at the end. (2nd e. p. 195 :> for details). : Page 195 does not discuss attacks, only errors. [...] Try reading it again: ``The weakness here is that while Mallory cannot recover the last plaintext block, he can change it systematically by changing individual bits in the ciphertext. If the last few bits of the cyphertext contain essential information, this is a weakness.`` - page 195. : None of the standard block chaining encryption modes detect : modification. Use a MAC for authentication. Bruce seems to think that bit-flipping attacks are a problem - and consequently that resistance to them is a strength. The reason is that block cyphers are their own (weak) authentication mechanism - in that they often make it relatively obvious when the file has been tampered with, by making two blocks (or sometimes the remainder of the file) decrypt to garbage. This is clearly a very imperfect authentication mechanism - but it's a lot better than allowing flipping a single bit in the ciphertext to affect the corresponding single bit in the plaintext. Obviously this is only relevant when use of a MAC is prohibitively expensive (in terms of processing, bandwidth, complexity, etc). -- __________ Lotus Artificial Life http://alife.co.uk/ tt@cryogen.com |im |yler The Mandala Centre http://mandala.co.uk/ ILOVEYOU.
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sun, 29 Oct 2000 21:39:30 GMT From: Bryan Olson <bryanolson@my-deja.com> Message-ID: <8ti5ei$4n8$1@nnrp1.deja.com> References: <G36qH4.Iqy@bath.ac.uk> Newsgroups: sci.crypt Lines: 26 Tim Tyler wrote: > Bryan Olson wrote: > > :> This means that the OFB-like bit-flipping attacks can only > :> be applied to the short block at the end. (2nd e. p. 195 > :> for details). > > : Page 195 does not discuss attacks, only errors. [...] > > Try reading it again: > > ``The weakness here is that while Mallory cannot recover the last > plaintext block, he can change it systematically by changing individual > bits in the ciphertext. If the last few bits of the cyphertext contain > essential information, this is a weakness.`` - page 195. Yup. My mistake. I'm not sure what I was looking at. --Bryan Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sat, 28 Oct 2000 22:34:44 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G35w1v.AoC@bath.ac.uk> References: <8tdakt$n8l$1@nnrp1.deja.com> <G33CGI.Dny@bath.ac.uk> Newsgroups: sci.crypt Lines: 54 Bryan Olson <bryanolson@my-deja.com> wrote: : Tim Tyler wrote: :> Bryan Olson wrote: :> : [...] can you imagine someone so clueless as to expect his message :> : space won't have enough redundancy to cover a couple hundred (or :> : several thousand) bits of key equivocation? :> :> Surely it is *very* easy to imagine such a case. :> :> What about the man sending short messages, for example? : "Message" yes, that's what the OTP is all about. "Messages" : sounds he doesn't really have a grasp of the requirements for : information theoretic security. Your implication that someone sending some short messages with a block cypher has a screw loose appears to be unwaranted. I suppose you are suggesting he should be using an OTP, and not bothering with a padding scheme? Using an OTP may require significantly more key material. Note that the redundancy you mentioned arises with messages longer than the unicity distance. This may be significantly greater than the length of the normal block cypher's key. Consequently, using an OTP may require far larger keys than are on the cards. It's probably simpler to use a padding scheme that adds zero bytes of known plaintext to the message, thus avoiding the problem completely. :> What about the man who forwards an encrypted message he has :> intercepted back to his HQ for decipherment? : Then he normally wouldn't even have a way to estimate the redundancy. So he won't know "whether it has enough redundancy". Why should he be so clueless as to /expect/ that it doesn't have such a redundancy when he doesn't know much about his message. The attacker that intercepts his message may be unable to distinguish a correct decrypt from a random stream (without lots of work). Consequently adding up to 127 zero bits to the file might make finding a termination criteria much easier for him. Redundancy is only useful to attackers if they can detect it. It's not a case of whether /I/ can imagine someone so clueless as to have such expections - it's why /you/ can't see that a perfectly intelligent and rational person could have such expectations. -- __________ http://alife.co.uk/ http://mandala.co.uk/ |im |yler tt@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sun, 29 Oct 2000 08:16:35 GMT From: Bryan Olson <bryanolson@my-deja.com> Message-ID: <8tgmd1$35i$1@nnrp1.deja.com> References: <G35w1v.AoC@bath.ac.uk> Newsgroups: sci.crypt Lines: 105 Tim Tyler wrote: > Bryan Olson wrote: > : Tim Tyler wrote: > :> Bryan Olson wrote: > > :> : [...] can you imagine someone so clueless as to expect his message > :> : space won't have enough redundancy to cover a couple hundred (or > :> : several thousand) bits of key equivocation? > :> > :> Surely it is *very* easy to imagine such a case. > :> > :> What about the man sending short messages, for example? > > : "Message" yes, that's what the OTP is all about. "Messages" > : sounds he doesn't really have a grasp of the requirements for > : information theoretic security. > > Your implication that someone sending some short messages with a block > cypher has a screw loose appears to be unwaranted. I implied nothing of the sort. Use a unique IV, a modern block cipher and a standard chaining and padding scheme. If one does not trust computational security, then use the OTP. > I suppose you are suggesting he should be using an OTP, > and not bothering with a padding scheme? No. Just don't bother with the pointless non-standard padding schemes. > Using an OTP may require significantly more key material. > Note that the redundancy you mentioned arises with messages > longer than the unicity distance. Wrong. It arises when the sum of the redundancy in all the messages sent under the key exceeds the key entropy. > This may be significantly > greater than the length of the normal block cypher's key. > > Consequently, using an OTP may require far larger keys than > are on the cards. > > It's probably simpler to use a padding scheme that adds zero bytes of > known plaintext to the message, thus avoiding the problem completely. That's where you've made your mistake - moving away from the standard padding schemes solves no problem. > :> What about the man who forwards an encrypted message he has > :> intercepted back to his HQ for decipherment? > > : Then he normally wouldn't even have a way to estimate the > : redundancy. > > So he won't know "whether it has enough redundancy". Why > should he be so clueless as to /expect/ that it doesn't have > such a redundancy when he doesn't know much about his message. That's my point. He has to expect his message space has enough redundancy to cover the key equivocation. > The attacker that intercepts his message may be unable to > distinguish a correct decrypt from a random stream (without > lots of work). Huh? If he's forwarding intercepted messages, then there's a small pool of possible plaintexts. > Consequently adding up to 127 zero bits to the file might make > finding a termination criteria much easier for him. As John Myre wrote Nobody with any sense cares, and you know why. > Redundancy is only useful to attackers if they can detect it. > > It's not a case of whether /I/ can imagine someone so > clueless as to have such expections - it's why /you/ can't > see that a perfectly intelligent and rational person could > have such expectations. And yet your examples fail. You thought small messages can't cover the unicity distance; not so since you can send more than one. You thought intercepted encrypted messages won't have useful redundancy. Did it occur to you that the attacker could have intercepted the same messages, or that the original sender is a likely attacker? Might there be some case where one could achieve ideal secrecy without a one-time random key? Perhaps. The point is how clueless it is to design for that case. --Bryan Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: DATA PADDING FOR ENCRYPTION Date: 29 Oct 2000 14:00:19 GMT From: this.address@is.for.spamers (SCOTT19U.ZIP_GUY) Message-ID: <8FDC4B093H110W296@207.36.190.226> References: <8tgmd1$35i$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 77 bryanolson@my-deja.com (Bryan Olson) wrote in <8tgmd1$35i$1@nnrp1.deja.com>: >Tim Tyler wrote: >> Bryan Olson wrote: >No. Just don't bother with the pointless non-standard >padding schemes. The problem is the so called standard padding schemes suck and to stick ones head in the sand and use no new padding schemes that are better while allowing underlying block encryption progrmas to chane is stupid. Especaill when most real world breaks occur due to know weakness in the resulting cipher test. Why on earth not use something that does not add any information to the resulting file. >That's where you've made your mistake - moving away from >the standard padding schemes solves no problem. > WHY? Do you naviely belive the current padding schemesa are written on some holy grail. They are not and they are plain stupid. > >As John Myre wrote > Nobody with any sense cares, and you know why. I guess becasue you think you have specail special sense that makes only your views correct. Well you wrong. >And yet your examples fail. You thought small messages >can't cover the unicity distance; not so since you can send >more than one. You thought intercepted encrypted messages >won't have useful redundancy. Did it occur to you that the >attacker could have intercepted the same messages, or that >the original sender is a likely attacker? All an attacker could learn from exteremly short messages if he could do this type of chosen text attack is what message a few characters long are. He is no closer to solving what any message of over a few bytes is. That is unless Rijndael is inheirently weak in the first place. Also what we are discussing is a single tool and how it should preform. If one is in battle one would send long messages and would use something like the example of my rotat and dsc to add ransom data to the file and rotate it before Matts code is called. One could aslo add a digital signature after Matts code used. Another point is although Matts code is 1-1 (unadulterated bijective whatever) It does not mean that one byte of plaintext maps to one byte of cipher test. It just means all is used. And most likey one byte of text would map to 16 bytes of output. While 16 bytes of input could map to one byte. So the padding as you would call it is not what you think. In fact I dare say it hasn't been used in any program combination compression encryption till matt coded it up for easy use. I would say you have to open up your closed mind as hard as that is and check it out. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE http://www.jim.com/jamesd/Kong/scott19u.zip Scott famous encryption website **now all allowed** http://members.xoom.com/ecil/index.htm Scott LATEST UPDATED source for scott*u.zip http://radiusnet.net/crypto/ then look for sub directory scott after pressing CRYPTO Scott famous Compression Page http://members.xoom.com/ecil/compress.htm **NOTE EMAIL address is for SPAMERS*** I leave you with this final thought from President Bill Clinton:
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sun, 29 Oct 2000 19:26:18 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G37Hzu.3z4@bath.ac.uk> References: <8tgmd1$35i$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 126 Bryan Olson <bryanolson@my-deja.com> wrote: : Tim Tyler wrote: :> Bryan Olson wrote: :> : Tim Tyler wrote: :> :> Bryan Olson wrote: :> :> : [...] can you imagine someone so clueless as to expect his message :> :> : space won't have enough redundancy to cover a couple hundred (or :> :> : several thousand) bits of key equivocation? :> :> :> :> Surely it is *very* easy to imagine such a case. :> :> :> :> What about the man sending short messages, for example? :> :> : "Message" yes, that's what the OTP is all about. "Messages" :> : sounds he doesn't really have a grasp of the requirements for :> : information theoretic security. :> :> Your implication that someone sending some short messages with a block :> cypher has a screw loose appears to be unwaranted. : I implied nothing of the sort. [...] "Doesn't really have a grasp of the issues at hand" then. :> I suppose you are suggesting he should be using an OTP, :> and not bothering with a padding scheme? : No. Just don't bother with the pointless non-standard : padding schemes. The problems of padding scheme of appending a 1 and padding with 0s to the end of the block is the topic under discussion I believe. If you would label this as "pointless, non-standard" then we would be in agreement. :> Using an OTP may require significantly more key material. :> Note that the redundancy you mentioned arises with messages :> longer than the unicity distance. : Wrong. It arises when the sum of the redundancy in : all the messages sent under the key exceeds the key : entropy. I was (rather obviously) dealing with the case of one key per message. Sending more than one message under the same key can only make things worse (from the POV of the security of the messages). :> This may be significantly greater than the length of the normal block :> cypher's key. :> :> Consequently, using an OTP may require far larger keys than :> are on the cards. :> :> It's probably simpler to use a padding scheme that adds zero bytes of :> known plaintext to the message, thus avoiding the problem completely. : That's where you've made your mistake - moving away from : the standard padding schemes solves no problem. It decreases the chance of an attacker being able to identify a correct message. Perhaps you should specify what you think "the standard padding schemes" refers to. Does it include the zero padding discussed further up this thread, for example? :> :> What about the man who forwards an encrypted message he has :> :> intercepted back to his HQ for decipherment? :> The attacker that intercepts his message may be unable to :> distinguish a correct decrypt from a random stream (without :> lots of work). : Huh? If he's forwarding intercepted messages, then there's : a small pool of possible plaintexts. Which may not be known to the attacker. He may not even know the cipher it is encrypted under. His task might be to strip off the outer layer of encryption and then pass the message to his supervisor to deal with the (classified) inner algorithm. If he can recognise a correct decrypt by the zero padding, he may succeed. If the padding is not present, his job is impossible. :> Consequently adding up to 127 zero bits to the file might make :> finding a termination criteria much easier for him. : As John Myre wrote : Nobody with any sense cares, and you know why. It was false then, and is false now. :> Redundancy is only useful to attackers if they can detect it. :> :> It's not a case of whether /I/ can imagine someone so :> clueless as to have such expections - it's why /you/ can't :> see that a perfectly intelligent and rational person could :> have such expectations. : And yet your examples fail. No they do not - you just fail to grasp them. : You thought small messages can't cover the unicity distance; [...] Which is true, under some circumstances. : [...] not so since you can send more than one. Um - not if there's one key per message. : You thought intercepted encrypted messages won't have useful : redundancy. Did it occur to you that the attacker could have : intercepted the same messages, or that the original sender is a likely : attacker? Did it occur to you that there might be other attackers not in this category? Obviously not. -- __________ Lotus Artificial Life http://alife.co.uk/ tt@cryogen.com |im |yler The Mandala Centre http://mandala.co.uk/ Florist: Petal pusher.
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sun, 29 Oct 2000 23:08:05 GMT From: Bryan Olson <bryanolson@my-deja.com> Message-ID: <8tiakj$8le$1@nnrp1.deja.com> References: <G37Hzu.3z4@bath.ac.uk> Newsgroups: sci.crypt Lines: 175 Tim Tyler wrote: > Bryan Olson <bryanolson@my-deja.com> wrote: > : Tim Tyler wrote: > :> Bryan Olson wrote: > :> : Tim Tyler wrote: > :> :> What about the man sending short messages, for example? > :> > :> : "Message" yes, that's what the OTP is all about. "Messages" > :> : sounds he doesn't really have a grasp of the requirements for > :> : information theoretic security. > :> > :> Your implication that someone sending some short messages with a block > :> cypher has a screw loose appears to be unwaranted. > > : I implied nothing of the sort. [...] > > "Doesn't really have a grasp of the issues at hand" then. > > :> I suppose you are suggesting he should be using an OTP, > :> and not bothering with a padding scheme? > > : No. Just don't bother with the pointless non-standard > : padding schemes. > > The problems of padding scheme of appending a 1 and padding with 0s to > the end of the block is the topic under discussion I believe. Specifically, you suggested that known plaintext it adds, and thus the ability to reject most individual keys (out of 2^128 of them) was some kind of security problem, and followed with: | It is true that some people are prepared to trust security | based on the percieved difficulty of performing certain | mathematical operations, rather than security based on an | information theoretical lack of ability to determine | whether keys are correct. One who cannot trust computational security might reasonably use the OTP. But presenting this as a justification for bijective padding is nonsense. The same 128-bit key is not going to provide ideal secrecy for realistic message spaces. > :> Using an OTP may require significantly more key material. > :> Note that the redundancy you mentioned arises with messages > :> longer than the unicity distance. > > : Wrong. It arises when the sum of the redundancy in > : all the messages sent under the key exceeds the key > : entropy. > > I was (rather obviously) dealing with the case of one > key per message. Then don't phrase it as a response to "the redundancy you mentioned" when I was talking about multiple small messages covering the key equivocation. Very short messages happens frequently; for example an encrypted telnet session often sends individual key-strokes. Do you know someone sending very-small messages with a new small key every time? (I suppose in some public-key applications the session key is new each time, but the unicity distance is zero so no message is short enough.) [...] > : That's where you've made your mistake - moving away from > : the standard padding schemes solves no problem. > > It decreases the chance of an attacker being able to > identify a correct message. In realistic models of message space it's only nuisance value. > Perhaps you should specify what you think "the standard > padding schemes" refers to. Does it include the zero padding > discussed further up this thread, for example? It could include the "1" followed by zeros, though I'm not sure offhand of a standard using it. It includes similar schemes such as adding n octets, 1 <= n <= 256, by repeating the value n (or zero to represent 256). > :> :> What about the man who forwards an encrypted message he has > :> :> intercepted back to his HQ for decipherment? > > :> The attacker that intercepts his message may be unable to > :> distinguish a correct decrypt from a random stream (without > :> lots of work). > > : Huh? If he's forwarding intercepted messages, then there's > : a small pool of possible plaintexts. > > Which may not be known to the attacker. He may not even > know the cipher it is encrypted under. His task might be to > strip off the outer layer of encryption and then pass the > message to his supervisor to deal with the (classified) > inner algorithm. "Intercepted" means it came from an adversary. We're not talking about how the user might get lucky and not be attacked by that adversary. One has to defend against chosen-plaintext in this case, where bijective padding is useless at best. > > If he can recognise a correct decrypt by the zero padding, > he may succeed. > If the padding is not present, his job is impossible. > > :> Consequently adding up to 127 zero bits to the file might make > :> finding a termination criteria much easier for him. > > : As John Myre wrote > : Nobody with any sense cares, and you know why. > > It was false then, and is false now. How about I give you message encrypted with a 128-bit key, but with over 128 zero bits at the end of the plaintext. It will have, as you defined the term, an "effective key space" of just one key. The termination criteria will be trivial. Want to try to recover the message? > :> Redundancy is only useful to attackers if they can detect it. > :> > :> It's not a case of whether /I/ can imagine someone so > :> clueless as to have such expections - it's why /you/ can't > :> see that a perfectly intelligent and rational person could > :> have such expectations. > > : And yet your examples fail. > > No they do not - you just fail to grasp them. > > : You thought small messages can't cover the unicity distance; [...] > > Which is true, under some circumstances. Which you omitted from the example, and are false in the real-world cases that occur every day. > : [...] not so since you can send more than one. > > Um - not if there's one key per message. > > : You thought intercepted encrypted messages won't have useful > : redundancy. Did it occur to you that the attacker could have > : intercepted the same messages, or that the original sender is > : a likely attacker? > > Did it occur to you that there might be other attackers not in this > category? > > Obviously not. Actually it did. I think we should design for the dangerous cases, not the ones where we get lucky. Resist adaptive-chosen-plaintext; don't bother adding nuisance value against ciphertext-only. --Bryan Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: DATA PADDING FOR ENCRYPTION Date: 30 Oct 2000 04:24:01 GMT From: this.address@is.for.spamers (SCOTT19U.ZIP_GUY) Message-ID: <8FDCDB514H110W296@207.36.190.226> References: <8tiakj$8le$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 31 bryanolson@my-deja.com (Bryan Olson) wrote in <8tiakj$8le$1@nnrp1.deja.com>: >It could include the "1" followed by zeros, though I'm not >sure offhand of a standard using it. It includes similar >schemes such as adding n octets, 1 <= n <= 256, by repeating >the value n (or zero to represent 256). When looking for blessed standards I did come across the adding of a 1 followed by zeros to fil. And that like the meth of using 01 0202 ... such that if last blcok filled you create a extra block they are reversable. But they suck in that they are not bijective to the orignal files iencrypted and a false key is very likely to lead to a file that could not be encrypted with the set of rules. So the standards leak information favorable to an attacker and then is plain foolishness since it so easy to prevent this extra added information. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE http://www.jim.com/jamesd/Kong/scott19u.zip Scott famous encryption website **now all allowed** http://members.xoom.com/ecil/index.htm Scott LATEST UPDATED source for scott*u.zip http://radiusnet.net/crypto/ then look for sub directory scott after pressing CRYPTO Scott famous Compression Page http://members.xoom.com/ecil/compress.htm **NOTE EMAIL address is for SPAMERS*** I leave you with this final thought from President Bill Clinton:
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Mon, 30 Oct 2000 10:59:40 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G38p7G.HCJ@bath.ac.uk> References: <8tiakj$8le$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 207 Bryan Olson <bryanolson@my-deja.com> wrote: : Tim Tyler wrote: :> Bryan Olson <bryanolson@my-deja.com> wrote: :> : Tim Tyler wrote: :> :> Bryan Olson wrote: :> :> : Tim Tyler wrote: :> The problems of padding scheme of appending a 1 and padding with 0s to :> the end of the block is the topic under discussion I believe. : Specifically, you suggested that known plaintext it adds, : and thus the ability to reject most individual keys (out of : 2^128 of them) was some kind of security problem [...] That's a fair assessment. : | It is true that some people are prepared to trust security : | based on the percieved difficulty of performing certain : | mathematical operations, rather than security based on an : | information theoretical lack of ability to determine : | whether keys are correct. : One who cannot trust computational security might reasonably : use the OTP. If they can handle the large keys involved. : But presenting this as a justification for bijective padding is : nonsense. It's not nonsense. Failing to add known plaintext might help when the attacker would not otherwise have a unique halting criterion. All he has to do is to guess keys ar random to stand an increased chance of success with his improved halting criterion. This isn't difficult to understand. What is your problem with it? : The same 128-bit key is not going to provide ideal secrecy for : realistic message spaces. There you go with your "message spaces" again. If each message has its own key, message spaces are of little relevance. An attacker can attack indivdual messages. It does not matter what the message space is - if the parties communicating with one another send *any* short messages, then an attacker's ability to decode these messages will be likely to be improved if he can get a better halting criterion for them. :> :> Using an OTP may require significantly more key material. :> :> Note that the redundancy you mentioned arises with messages :> :> longer than the unicity distance. :> :> : Wrong. It arises when the sum of the redundancy in :> : all the messages sent under the key exceeds the key :> : entropy. :> :> I was (rather obviously) dealing with the case of one :> key per message. : Then don't phrase it as a response to "the redundancy you : mentioned" when I was talking about multiple small messages : covering the key equivocation. You wrote: ``can you imagine someone so clueless as to expect his message space won't have enough redundancy to cover a couple hundred (or several thousand) bits of key equivocation?'' "Multiple small messages" were not mentioned, AFAICS. Regardless of what you thought you were talking about, my point still stands - short messages may not contain enough entropy to allow a unique halting criterion. If you pad them out with lots of zero bits, that may make the difference between having a single unique possible message, and having many such possible messages. : Very short messages happens frequently; for example an : encrypted telnet session often sends individual key-strokes. : Do you know someone sending very-small messages with a new : small key every time? I believe you can send messages of any size with PGP. You don't have to /repeatedly/ send small messages - just sending one is enough. A "small" key is not required - or a very good idea for obvious reasons. [snip clarifying ``what you think "the standard padding schemes" refers :> :> :> What about the man who forwards an encrypted message he has :> :> :> intercepted back to his HQ for decipherment? :> :> :> The attacker that intercepts his message may be unable to :> :> distinguish a correct decrypt from a random stream (without :> :> lots of work). :> :> : Huh? If he's forwarding intercepted messages, then there's :> : a small pool of possible plaintexts. :> :> Which may not be known to the attacker. He may not even :> know the cipher it is encrypted under. His task might be to :> strip off the outer layer of encryption and then pass the :> message to his supervisor to deal with the (classified) :> inner algorithm. : "Intercepted" means it came from an adversary. We're not : talking about how the user might get lucky and not be : attacked by that adversary. [...] I was not talking about that either. I was saying that some attackers might not have the information necessary to mount the attack you suggested. Consequently, defending against their (weaker) attacks may still be worthwhile. :> If he can recognise a correct decrypt by the zero padding, :> he may succeed. If the padding is not present, his job is impossible. :> :> :> Consequently adding up to 127 zero bits to the file might make :> :> finding a termination criteria much easier for him. :> :> : As John Myre wrote :> : Nobody with any sense cares, and you know why. :> :> It was false then, and is false now. : How about I give you message encrypted with a 128-bit key, : but with over 128 zero bits at the end of the plaintext. It : will have, as you defined the term, an "effective key space" : of just one key. The termination criteria will be trivial. : Want to try to recover the message? I'm no great cryptanalyst - that would probably be a waste of my time. That such problems can be hard does not mean that adding known plaintext to a message has no security implicactions, though. Even I would stand a better chance of identifiying the message with the known plaintext added (even if I just guessed keys at random) - since without that known plaintext, my chance of getting the correct message (and knowing that I have it) is zero. :> : And yet your examples fail. :> :> No they do not - you just fail to grasp them. :> :> : You thought small messages can't cover the unicity distance; [...] :> :> Which is true, under some circumstances. : Which you omitted from the example [...] I would have though it obvious from my statement that you could identify keys with messages longer than the unicity distance. Even if you failed to understand me then, I have made it blindingly clear what I was referring to in the interim. : [...] and are false in the real-world cases that occur every day. Nope. People can and do send short messages, and change key before they exceed the unicity distance. Deal with it. *Even* in cases where the unicity distance is massively exceeded, adding specific known plaintext is something to avoid - since it may be able to provide a halting criterion that is either more concrete, or faster to evaluate than other types of statistic about the plaintext. Alternatively, the halting criterion may be simpler, allowing a brute-force parallel machine to be built using a smaller area of silicon. :> : You thought intercepted encrypted messages won't have useful :> : redundancy. Did it occur to you that the attacker could have :> : intercepted the same messages, or that the original sender is :> : a likely attacker? :> :> Did it occur to you that there might be other attackers not in this :> category? :> :> Obviously not. : Actually it did. I think we should design for the dangerous : cases, not the ones where we get lucky. So (in this case) because some attacker might have complete known plaintexts, don't bother trying to reduce known plaintext?? Please. With known plaintext attakers can guess message keys, confirm correct keys, etc. Without any known plaintext, they can be stumped. : Resist adaptive-chosen-plaintext; don't bother adding nuisance value : against ciphertext-only. [...] Despite the fact that adaptive chosen plaintext attacks are relatively rare in practice? I think one should defend against known-plaintext as well as is conveniently possible. Especially if the "defense" is the relatively inexpensive one of avoiding padding one's message out with zeros. -- __________ Lotus Artificial Life http://alife.co.uk/ tt@cryogen.com |im |yler The Mandala Centre http://mandala.co.uk/ Organic: Church music.
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Mon, 30 Oct 2000 20:51:50 GMT From: Bryan Olson <bryanolson@my-deja.com> Message-ID: <8tkn12$6de$1@nnrp1.deja.com> References: <G38p7G.HCJ@bath.ac.uk> Newsgroups: sci.crypt Lines: 243 Tim Tyler wrote: > Bryan Olson wrote: > : Tim Tyler wrote: > :> Bryan Olson <bryanolson@my-deja.com> wrote: > :> : Tim Tyler wrote: > > :> The problems of padding scheme of appending a 1 and padding > :> with 0s to the end of the block is the topic under discussion > :> I believe. > > : Specifically, you suggested that known plaintext it adds, > : and thus the ability to reject most individual keys (out of > : 2^128 of them) was some kind of security problem [...] > > That's a fair assessment. [...] > : One who cannot trust computational security might reasonably > : use the OTP. > > If they can handle the large keys involved. > > : But presenting this as a justification for bijective padding is > : nonsense. > > It's not nonsense. Failing to add known plaintext might help when the > attacker would not otherwise have a unique halting criterion. > > All he has to do is to guess keys ar random to stand an increased > chance of success with his improved halting criterion. > > This isn't difficult to understand. What is your problem with it? We already beat it. Exhaustive search is trivial to defeat. If you think it's still to dangerous with 128 bit keys, or that the attacker might know some, but not all, of the bits - then use a 256-bit key. > : The same 128-bit key is not going to provide ideal secrecy for > : realistic message spaces. > > There you go with your "message spaces" again. Yes. If you're seeking ideal secrecy without the OTP, then it turns out to be pretty important. > If each message > has its own key, message spaces are of little relevance. That's one of my points. Use techniques that work for all message spaces. [...] > You wrote: > > ``can you imagine someone so clueless as to expect his message > space won't have enough redundancy to cover a couple hundred (or > several thousand) bits of key equivocation?'' > > "Multiple small messages" were not mentioned, AFAICS. Perhaps this was just a mis-communication. When I distinguished "message" from "messages", I was pointing out just that. What you quote above was from before the small-message case. > Regardless of what you thought you were talking about, my > point still stands - short messages may not contain enough > entropy to allow a unique halting criterion. If you pad them > out with lots of zero bits, that may make the difference > between having a single unique possible message, and > having many such possible messages. And your point is still nonsense. Halting criteria is no problem. Use a large enough key. Note that the one-bit followed by enough zeros to fill the block differs trivially from a bijection. Any message that does not end with an all-zero block is the padded image of some bit-string. > : Very short messages happens frequently; for example an > : encrypted telnet session often sends individual key-strokes. > > : Do you know someone sending very-small messages with a new > : small key every time? > > I believe you can send messages of any size with PGP. Yes, I noted public key systems in the previous post, and that they have a unicity distance of zero, so no message is short enough. And do you actually know anyone sending only one message with each PGP key? > :> :> :> What about the man who forwards an encrypted message he has > :> :> :> intercepted back to his HQ for decipherment? > :> > :> :> The attacker that intercepts his message may be unable to > :> :> distinguish a correct decrypt from a random stream (without > :> :> lots of work). > :> > :> : Huh? If he's forwarding intercepted messages, then there's > :> : a small pool of possible plaintexts. > :> > :> Which may not be known to the attacker. He may not even > :> know the cipher it is encrypted under. His task might be to > :> strip off the outer layer of encryption and then pass the > :> message to his supervisor to deal with the (classified) > :> inner algorithm. > > : "Intercepted" means it came from an adversary. We're not > : talking about how the user might get lucky and not be > : attacked by that adversary. [...] > > I was not talking about that either. I was saying that some attackers > might not have the information necessary to mount the attack you > suggested. Consequently, defending against their (weaker) attacks > may still be worthwhile. As I wrote in the snipped part, one has to defend against chosen-plaintext in this case, where bijective padding is useless at best. Expecting that the message space won't have enough redundancy is clearly wrong if _any_ adversary knows the plaintext. This example fails big. It's probably a good case to use randomized encryption. These schemes actually do render known or chosen plaintext attacks inapplicable. Randomized encryption is one-to-many. See the proceedings of Crypto 82 for three papers on techniques. [...] > : How about I give you message encrypted with a 128-bit key, > : but with over 128 zero bits at the end of the plaintext. It > : will have, as you defined the term, an "effective key space" > : of just one key. The termination criteria will be trivial. > : Want to try to recover the message? > > I'm no great cryptanalyst - that would probably be a waste > of my time. > > That such problems can be hard does not mean that adding known > plaintext to a message has no security implicactions, though. > > Even I would stand a better chance of identifiying the message > with the known plaintext added (even if I just guessed keys at > random) - since without that known plaintext, my chance of getting > the correct message (and knowing that I have it) is zero. Not true. To have a non-zero chance the attacker only needs recognizable plaintext, not known plaintext. Real-world traffic is recognizable. [...] > Nope. People can and do send short messages, and change key > before they exceed the unicity distance. Deal with it. Yet the only one you named, when specifically asked if you could, was PGP. It's public key - unicity distance zero. In addition, I know a lot of people who use PGP. I've set it up and provided support for a few. Never once have I heard of one who used one key per message (except maybe by accident). Have you? > *Even* in cases where the unicity distance is massively exceeded, > adding > specific known plaintext is something to avoid - since it may be > able to provide a halting criterion that is either more concrete, or > faster to evaluate than other types of statistic about the plaintext. That's nuisance value. Don't bother. > Alternatively, the halting criterion may be simpler, allowing a > brute-force parallel machine to be built using a smaller area of > silicon. No problem. If the chance of finding a key is too great, or the work factor too small, use a bigger key. > :> : You thought intercepted encrypted messages won't have useful > :> : redundancy. Did it occur to you that the attacker could have > :> : intercepted the same messages, or that the original sender is > :> : a likely attacker? > :> > :> Did it occur to you that there might be other attackers not in this > :> category? > :> > :> Obviously not. > > : Actually it did. I think we should design for the dangerous > : cases, not the ones where we get lucky. > > So (in this case) because some attacker might have complete known > plaintexts, don't bother trying to reduce known plaintext?? > > Please. With known plaintext attakers can guess message keys, > confirm correct keys, etc. Without any known plaintext, they > can be stumped. Again, no problem. Use a big enough key. > : Resist adaptive-chosen-plaintext; don't bother adding nuisance value > : against ciphertext-only. [...] > > Despite the fact that adaptive chosen plaintext attacks are relatively > rare in practice? Absolutely. Beating adaptive chosen plaintext implies beating off-line chosen plaintext, which implies beating known plaintext which implies beating ciphertext only. And adaptive chosen plaintext is not as rare as keys that go out of use before encrypting enough text to cover the unicity distance. > I think one should defend against known-plaintext as well as is > conveniently possible. Then by all means use randomized one-to-many encryption and really beat it. > Especially if the "defense" is the > relatively inexpensive one of avoiding padding one's message out > with zeros. Again, randomized one-to-many is better. --Bryan Sent via Deja.com http://www.deja.com/ Before you buy.
Subject: Re: DATA PADDING FOR ENCRYPTION Date: 1 Nov 2000 00:20:41 GMT From: this.address@is.for.spamers (SCOTT19U.ZIP_GUY) Message-ID: <8FDEBD3CDH110W296@207.36.190.226> References: <8tni4q$j3b$1@nnrp1.deja.com> <G39rpD.GoC@bath.ac.uk> <8tkn12$6de$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 42 bryanolson@my-deja.com (Bryan Olson) wrote in <8tni4q$j3b$1@nnrp1.deja.com>: >If you need to disable known or chosen plaintext attacks, >then use a system that can do so. Bijective padding does >not. Actually none of the standard ciphers can be proven to be a immune to plaintext attacks. So that is not so easy. > >If we're intercepting these messages, an adversary supplies >our plaintext. We have to expect not only known, but chosen >plaintext attacks. Bijectively transforming chosen >plaintext just means that the attacker can choose every >bit of the post-padded message. Ture but one can use my rotat to add random datat if that makes you happy wiht DSC. The problem with many nobijective methods is that an attacker does not even have to supply the plain text as in a choosen plain text attack. He couls just look a the encrypted messages alone and use the infomration adde by the use of nobijective compression if thats part of the package as in PGP. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE http://www.jim.com/jamesd/Kong/scott19u.zip Scott famous encryption website **now all allowed** http://members.xoom.com/ecil/index.htm Scott LATEST UPDATED source for scott*u.zip http://radiusnet.net/crypto/ then look for sub directory scott after pressing CRYPTO Scott famous Compression Page http://members.xoom.com/ecil/compress.htm **NOTE EMAIL address is for SPAMERS*** I leave you with this final thought from President Bill Clinton:
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Wed, 01 Nov 2000 01:00:27 GMT From: jsavard@fNrOeSePnAeMt.edmonton.ab.ca (John Savard) Message-ID: <39ff6ae0.2341181@news.powersurfr.com> References: <8tni4q$j3b$1@nnrp1.deja.com> <G39rpD.GoC@bath.ac.uk> <8tkn12$6de$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 13 On Tue, 31 Oct 2000 22:46:52 GMT, Bryan Olson <bryanolson@my-deja.com> wrote, in part: >More importantly, it applies to the message as people >actually send it. It makes no sense to say we must not >provide known plaintext and then use a public-key cipher. A very important point. Unless, of course, one is using a secure public-key cipher to transmit a key for a much less secure (for speed reasons) conventional cipher. John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Wed, 1 Nov 2000 12:04:21 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G3CHJ9.MvH@bath.ac.uk> References: <39ff6ae0.2341181@news.powersurfr.com> Newsgroups: sci.crypt Lines: 15 John Savard <jsavard@fnroesepnaemt.edmonton.ab.ca> wrote: : Bryan Olson <bryanolson@my-deja.com> wrote, in part: :>More importantly, it applies to the message as people :>actually send it. It makes no sense to say we must not :>provide known plaintext and then use a public-key cipher. : A very important point. Unless, of course, one is using a secure : public-key cipher to transmit a key for a much less secure (for speed : reasons) conventional cipher. Exactly - I doubt I could have put this better. -- __________ Lotus Artificial Life http://alife.co.uk/ tt@cryogen.com |im |yler The Mandala Centre http://mandala.co.uk/ Hat: Baldness cure.
Subject: Re: DATA PADDING FOR ENCRYPTION Date: Sun, 5 Nov 2000 13:59:29 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G3K1J5.15D@bath.ac.uk> References: <8tni4q$j3b$1@nnrp1.deja.com> <G39rpD.GoC@bath.ac.uk> <8tkn12$6de$1@nnrp1.deja.com> Newsgroups: sci.crypt Lines: 263 Bryan Olson <bryanolson@my-deja.com> wrote: : Tim Tyler wrote: :> Bryan Olson wrote: :> : Tim Tyler wrote: :> :> Bryan Olson wrote: :> :> : One who cannot trust computational security might reasonably :> :> : use the OTP. :> :> :> :> If they can handle the large keys involved. :> :> :> :> : But presenting this as a justification for bijective padding is :> :> : nonsense. :> :> :> :> It's not nonsense. Failing to add known plaintext might help when :> :> the attacker would not otherwise have a unique halting criterion. :> :> :> :> All he has to do is to guess keys ar random to stand an increased :> :> chance of success with his improved halting criterion. :> :> :> :> This isn't difficult to understand. What is your problem with it? :> :> : We already beat it. Exhaustive search is trivial to defeat. :> :> Guessing keys is going to work some of the time, nevertheless. : No. With a 256-bit key guessing has an insignificant : chance of working even once. You don't seem to share my idea of what "some of the time" means. I would contrast this term with "never". This point does not seem terribly interesting, though. We're agreed that a brute force search of a reasonable keyspace is not a viable attack in practice. :> If you are arguing that the advantage offered by an improved halting :> criterion is relatively small in the face of to difficulties imposed :> by a 128 bit key space, then you would be right - *IF* there are no :> attacks on the algorithm in question, and there are no other ways to :> get hold of key material besides cryptanalyic attack. Since neither :> of these can be known to be true there are other attacks besides :> brute force or guessing whith which the ability to reject keys helps. : If you need to disable known or chosen plaintext attacks, : then use a system that can do so. Unfortunately, this is easier said than done. You can't normally defend perfectly against having your keys stolen - consequently, known plaintext attacks may arise, no matter how secure your cypher, or how large your key. :> :> There you go with your "message spaces" again. :> :> : Yes. If you're seeking ideal secrecy without the OTP, then it :> : turns out to be pretty important. :> :> Of course - but in the context of this discussion, individual messages :> are what can be short - not whole spaces of messages. A single short :> message in a message space of millions of lengthy messages is :> liable to lack a concrete halting criterion - in the absence of :> padding slip-ups. : So your example actually does have millions of lengthy : messages in the message space? [...] Perhaps. I never said it didn't at any rate. : But you think it's clue-ful to expect the messages will not have enough : redundancy to resolve the key, because there are some short ones too? Short messages won't have enough redundancy to resolve the key they are transmitted with - because they are short. I repeat again, I'm assuming the each message gets its own key. :> :> Regardless of what you thought you were talking about, my :> :> point still stands - short messages may not contain enough :> :> entropy to allow a unique halting criterion. If you pad them :> :> out with lots of zero bits, that may make the difference :> :> between having a single unique possible message, and :> :> having many such possible messages. :> :> : And your point is still nonsense. Halting criteria is no :> : problem. Use a large enough key. :> :> Your objection appears to be nonsensical and contradictory! ;-) :> :> Using a large enough key *makes* halting criteria a problem. :> :> Your whole argument to date has been that the attacker can :> always get hold of a halting criterion, even without padding. :> If you now say "use a large enough key" to ensure no halting :> criterion exists, you seem to be sabotaging your own argument. : Ah, I should have been more specific. Use a key large : enough that even with a halting criteria key-trial is : useless. There's no such key size (much short of using an OTP). Key spaces can be reduced to searchable spaces by any number of non-cryptographic means, including espionage, theft, component failures, and carelessness. :> : Note that the one-bit followed by enough zeros to fill the :> : block differs trivially from a bijection. :> :> There's a categorial difference - one is a padding scheme :> - and the other is a mapping between two sets ;-) : How does the way you choose to categorize them limit : an attacker? Sorry. I was just being pedantic. Don't bother to treat the question seriously. :> : Any message that does not end with an all-zero block is the padded :> : image of some bit-string. :> :> Sounds a bit wasteful. Why not do what you suggested and :> use "a one-bit followed by enough zeros to fill the block." : I think this is a mis-communication again. Misunderstanding, more like - on my part. :> Better still, why not use a bijective mapping between :> the set of 8-bits files, and files with the desired block :> size. : One could. The fact that it's bijective between those : two sets does not mean that it doesn't add redundancy. Hmm. It's true that individual messages /could/ become longer and much more redundant - and that this could happen in a systematic way. However, this is a thorny region that I'm not keen to enter into. I think you could use a simple mapping and get maximum and minimum bounds on any contraction or expansion, which - together with the bijective property - would satisfy most that no such funny business was occurring. : Not to worry though - real world message spaces have : a lot of redundancy anyway, so our ciphers are designed : to handle it. As best they can. Our cypher's can't possibly be designed to resist key theft, though. By contrast, decreasing message redundancy can sometimes help defend against that. :> :> : Very short messages happens frequently; for example an :> :> : encrypted telnet session often sends individual key-strokes. :> :> :> :> : Do you know someone sending very-small messages with a new :> :> : small key every time? :> :> :> :> I believe you can send messages of any size with PGP. :> :> : Yes, I noted public key systems in the previous post, and that :> : they have a unicity distance of zero, so no message is short :> : enough. :> :> You mentioned symmetric key distribution using PK systems. :> :> Once a symmetric key has been distributed, what then? : Then you are already among the "some people" in: : It is true that some people are prepared to trust : security based on the percieved difficulty of performing : certain mathematical operations, rather than security : based on an information theoretical lack of ability to : determine whether keys are correct. Indeed. Use of public key systems seems destined to rest on one-way trapdoor mathematical functions - and not information-theoretic secrecy considerations. [...] :> : And do you actually know anyone sending only one message with :> : each PGP key? :> :> With each PGP *session* key? Yes. :> AFAIK, everyone who uses PGP does this. : So if you strip off the public key encryption, then : send the session key encrypted messages, and transport : the unique session key by some out-of-band channel, : then for very short messages you would have a case : where the messages do not cover the unicity distance. : Do you know anyone who does that? No - but you have a case where the unicity distance is exceeded without that - just consider the unicity distance relative to the symmetric key - on the assumption that this is the weaker component of the system. It matters little if there's a key which could be verified as unique hidden in a PK cryptosystem - if you have no attack on that system, and no practical way to determine if a particular symmetric key is being encrypted with it. :> :> I was saying that some attackers might not have the information :> :> necessary to mount the attack you suggested. Consequently, :> :> defending against their (weaker) attacks may still be worthwhile. :> :> : As I wrote in the snipped part, one has to defend against :> : chosen-plaintext in this case, where bijective padding is :> : useless at best. Expecting that the message space won't have :> : enough redundancy is clearly wrong if _any_ adversary knows :> : the plaintext. :> :> Obviously. Equally obviously, the contingent "if" need :> not be true. :> :> : This example fails big. :> :> No - you've still just failed to grasp it. : Not through lack of trying. Where did I misunderstand? I'm not /exactly/ clear what's going on in your mind. One possible guess is that you're applying the principle that looking after powerful attackers deals with weaker ones, so you're concluding that an attacker with minimal known plaintext is not worthy of consideration. : These are intercepted encrypted messages. The plaintext of your : messages is the intercepted ciphertext. You cited this as a : case in which it would be reasonable (non-clueless) to : expect our messages did not cover the unicity distance of a : conventional cipher. Yes. : If we're intercepting these messages, an adversary supplies : our plaintext. We have to expect not only known, but chosen : plaintext attacks. Bijectively transforming chosen : plaintext just means that the attacker can choose every : bit of the post-padded message. Yes. However, not all possible adversaries will be able to do that. Of those that can, if they can /also/ reduce the keyspace to managable proportions, all is lost. However, we can still defend against attackers who don't have the knowlegde of the original plaintexts, but do have a keyspace reduction. Simply avoiding giving these attackers known plaintext can defeat these folk under some circumstances. It may be of value to identify forwarded encrypted messages, even if they can't decode them immediately. Obviously you should try to defend against having your keyspace reduced as well - but this is not a problem with a purely cryptographic resolution. [...] -- __________ Lotus Artificial Life http://alife.co.uk/ tt@cryogen.com |im |yler The Mandala Centre http://mandala.co.uk/ Hat: Baldness cure.
Subject: Re: Padding scheme? Date: 30 Oct 2000 04:47:07 GMT From: this.address@is.for.spamers (SCOTT19U.ZIP_GUY) Message-ID: <8FDCD13EEH110W296@207.36.190.226> References: <39FCCD02.DC14C89@earthlink.net> Newsgroups: sci.crypt Lines: 60 goldbb2@earthlink.net (Benjamin Goldberg) wrote in <39FCCD02.DC14C89@earthlink.net>: >I'm not certain if this padding scheme is new. If it's not, don't sue >me :) > >messagesize and blocksize are measured in bytes. > >x = (messagesize + 1) mod blocksize >if( x == 0 ) > y = 0 >else > y = blocksize-x >append y Truly Random bytes to the message >append a final byte that has the lower log2(blocksize) bits set to y, >and the upper bitlength(byte)-log2(blocksize) bits filled in from your >Truly Random bitsource. > >To remove the padding, read the message up to the last byte, use a mask >to extract y, and discard the y previous bytes. > >Note that the scheme requires that blocksize be fewer than >2**bitlength(byte) bytes, and works best if blocksize is a power of 2. > >Does anybody see any weakness in this scheme? > The main objection I see is the same when people bitch about the "random bits" in a OTP. The weaknes is you have to count on having such bits. I have nothing agains using random bits. But I prefer to have a sound method with out the use of the "random god" and then add random later. But I would prefer to use the random number as a number use to rotate the source file and then DSC to mate it in. Then optimal end treatment such as Matts or mine that works on any file to match the block size of the encryption used. That is what I would so if for some reason I want to padd out to match the encrypted block size. The other error I feel that is there is when you start doing this for real the field you use to contain the data must be able to account for all bit patterns you still have to play same games with this so that every combination of bits is possible. Even if you try to add a constant to a file the way I did there are optimal end considerations that come out in the details. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE http://www.jim.com/jamesd/Kong/scott19u.zip Scott famous encryption website **now all allowed** http://members.xoom.com/ecil/index.htm Scott LATEST UPDATED source for scott*u.zip http://radiusnet.net/crypto/ then look for sub directory scott after pressing CRYPTO Scott famous Compression Page http://members.xoom.com/ecil/compress.htm **NOTE EMAIL address is for SPAMERS*** I leave you with this final thought from President Bill Clinton:
Subject: Re: Padding scheme? Date: Mon, 30 Oct 2000 18:27:55 GMT From: Benjamin Goldberg <goldbb2@earthlink.net> Message-ID: <39FD2A57.CEFE5501@earthlink.net> References: <8FDCD13EEH110W296@207.36.190.226> Newsgroups: sci.crypt Lines: 91 SCOTT19U.ZIP_GUY wrote: > > goldbb2@earthlink.net (Benjamin Goldberg) wrote in > <39FCCD02.DC14C89@earthlink.net>: > > >I'm not certain if this padding scheme is new. If it's not, don't > >sue me :) > > > >messagesize and blocksize are measured in bytes. > > > >x = (messagesize + 1) mod blocksize > >if( x == 0 ) > > y = 0 > >else > > y = blocksize-x > >append y Truly Random bytes to the message > >append a final byte that has the lower log2(blocksize) bits set to y, > >and the upper bitlength(byte)-log2(blocksize) bits filled in from > >your Truly Random bitsource. > > > >To remove the padding, read the message up to the last byte, use a > >mask to extract y, and discard the y previous bytes. > > > >Note that the scheme requires that blocksize be fewer than > >2**bitlength(byte) bytes, and works best if blocksize is a power of > >2. > > > >Does anybody see any weakness in this scheme? > > > > The main objection I see is the same when people bitch about the > "random bits" in a OTP. The weaknes is you have to count on having > such bits. I have nothing agains using random bits. But I prefer to > have a sound method with out the use of the "random god" and then add > random later. I don't see anything unsound about the method. To give a more concrete example of my algorithm, I'll fill in things that were left as parameters. Assume bytes are 8 bits each, and the cipher blocksize is 16 bytes (those are what I'd left as parameters). Let xx be the number of bytes in the message. Append 15-(xx mod 16) bytes of padding. Append 4 bits of padding. Append the number of complete bytes of padding as a 4 bit value. The final result will be a message whose length is a multiple of 16 bytes. The bytes and bits of the padding could be all 0s, or all 1s, or generated from a PRBG, or from a TRBG; regardless, the amount of padding depends entirely (100%) on the length of the original message, not on the output of the bit generator. However, it is desired that the bits of padding not be distinguishable from random, so as to avoid giving the opponent known or probable plaintext. To strip off the padding, read all the data, logical and the value 0xF with the last byte, and strip off that many of the preceding bytes. If the blocksize were 32 bytes, we would instead append 31-(xx mod 32) bytes of padding, followed by 3 bits of padding, followed by a 5 bit number indicating the number of complete bytes of padding. To strip off the padding, read all the data, logical and the value 0x1F with the last byte, and strip off that many of the preceding bytes. > But I would prefer to use the random number as a number use to > rotate the source file and then DSC to mate it in. Then optimal end > treatment such as Matts or mine that works on any file to match the > block size of the encryption used. That is what I would so if for some > reason I want to padd out to match the encrypted block size. This statement of yours is completely "out there." Perhaps you should get your head out of your ass and read what I wrote. Nowhere do I use my random bits as numbers... they're just garbage data, junk, fill, un-looked-at bits-and-bytes. The reason I want randomness is to avoid giving known or probable plaintext. > The other error I feel that is there is when you start doing this > for real the field you use to contain the data must be able to account > for all bit patterns you still have to play same games with this so > that every combination of bits is possible. Even if you try to add a > constant to a file the way I did there are optimal end considerations > that come out in the details. Clearly you are the type of person, who, if given a large bottle of "clue musk," could not get a clue. -- "Mulder, do you remember when I was missing -- that time that you *still* insist I was being held aboard a UFO?" "How could I forget?" "Well, I'm beginning to wonder if maybe I wouldn't have been better off staying abo-- I mean, wherever it was that I was being held." [from an untitled spamfic by SkyFire@aol.com]
Subject: Re: Padding scheme? Date: Mon, 30 Oct 2000 22:46:38 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G39Lxq.Anr@bath.ac.uk> References: <39FDE5D5.B6AEF57C@earthlink.net> <39FCCD02.DC14C89@earthlink.net> Newsgroups: sci.crypt Lines: 21 Benjamin Goldberg <goldbb2@earthlink.net> wrote: : After having read some other recent stuff on this group discussing : padding, I realize that a trojan horse type program could use the random : padding as a subliminal channel. To avoid this, the padding should, : instead of being random, be the first bytes and bits from a : cryptographicly secure hash of the message. The reason for doing a hash : is that won't add known or probable plaintext, whereas fixed content : padding would. Using a hash is inferior to the use of genuinely random numbers in at least one sense - because attackers can identify incorrect decrypts by checking to see if the padding is padding that would have been added if the specified hash function was used. This allows them to use the padding to reject keys. Rejecting keys by this method would be laborious, though - since you need to have the entire message on hand to reject each key. -- __________ http://alife.co.uk/ http://mandala.co.uk/ |im |yler tt@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Subject: Re: Padding scheme? Date: Tue, 31 Oct 2000 00:15:05 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G39q15.FrA@bath.ac.uk> References: <39FDF0FC.FDBD0CC5@earthlink.net> <8FDD9E1FCH110W296@207.36.190.226> Newsgroups: sci.crypt Lines: 36 Benjamin Goldberg <goldbb2@earthlink.net> wrote: : SCOTT19U.ZIP_GUY wrote: :> goldbb2@earthlink.net (Benjamin Goldberg) wrote in :> <39FDE5D5.B6AEF57C@earthlink.net>: :> >After having read some other recent stuff on this group discussing :> >padding, I realize that a trojan horse type program could use the :> >random padding as a subliminal channel. To avoid this, the padding :> >should, instead of being random, be the first bytes and bits from a :> >cryptographicly secure hash of the message. [...] :> :> Yes this might be valuable if the padding is applied in some purely :> bijective way so that the result is still fully bijective. [...] : Although it's true that using bits from a hash, rather than bits from a : TRBG, does create a bijective mapping from the set of messages whose : lengths are multiples of 8 bits to the set of messages whose lengths are : multiples of 128 bits [...] s/true/false/ You've just added a redundant section to the message. A bit like cutting the first few characters and pastuing them onto the end of the file. No bijective map is likely to be found there. : there is no significant difference in security between the original : 1-to-many mapping and the hash-based 1-to-1 mapping. You don't rate that ability to reject keys on the basis of their having appended padding in the form of hash data (that doesn't match the contents of the message) as a security risk? Don't expect folks like me or David to agree with that. -- __________ http://alife.co.uk/ http://mandala.co.uk/ |im |yler tt@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Subject: Re: Padding scheme? Date: Tue, 31 Oct 2000 18:57:47 GMT From: Benjamin Goldberg <goldbb2@earthlink.net> Message-ID: <39FE3405.4DA9BF95@earthlink.net> References: <G39q15.FrA@bath.ac.uk> Newsgroups: sci.crypt Lines: 68 Tim Tyler wrote: > > Benjamin Goldberg <goldbb2@earthlink.net> wrote: > : SCOTT19U.ZIP_GUY wrote: > :> goldbb2@earthlink.net (Benjamin Goldberg) wrote in > :> <39FDE5D5.B6AEF57C@earthlink.net>: > > :> >After having read some other recent stuff on this group discussing > :> >padding, I realize that a trojan horse type program could use the > :> >random padding as a subliminal channel. To avoid this, the > :> >padding should, instead of being random, be the first bytes and > :> >bits from a cryptographicly secure hash of the message. [...] > :> > :> Yes this might be valuable if the padding is applied in some > :> purely bijective way so that the result is still fully bijective. > :> [...] > > : Although it's true that using bits from a hash, rather than bits > : from a TRBG, does create a bijective mapping from the set of > : messages whose lengths are multiples of 8 bits to the set of > : messages whose lengths are multiples of 128 bits [...] > > s/true/false/ > > You've just added a redundant section to the message. A bit like > cutting the first few characters and pastuing them onto the end of the > file. No bijective map is likely to be found there. Note that the domain and range are not the same. The domain is the set of messages whose lengths are integral numbers of 8-bit bytes. The range is the set of messages whose lengths are integral numbers of 128-bit blocks. If the hash of the message is used as the source of 'random' padding bytes, then each message in the domain maps to precisely one message in the range. Furthermore, the inverse function, which strips padding, maps each message in the range of the padding function to one and only one message in the domain. Does not this padding scheme describe a mapping that is one-to-one and onto? > : there is no significant difference in security between the original > : 1-to-many mapping and the hash-based 1-to-1 mapping. > > You don't rate that ability to reject keys on the basis of their > having appended padding in the form of hash data (that doesn't > match the contents of the message) as a security risk? Consider that the entire message must be decrypted to be able to reject a key. There's a tradeoff... either use a RBG to create the padding, and risk the possibility of a subliminal channel being snuck in (a trojan horsed encryption program) by your opponent, or use hash bits, which allow rejection of keys. I personally would use an RBG to create the padding, but that's because, if I'm implementing it, I know that my RBG is not trojan horsed. > Don't expect folks like me or David to agree with that. Well, like I said, you can either introduce a known (minor?) weakness, which can't have a subliminal channel, or risk the unknown weakness of your enemy (possibly) introducing a data leak. -- "Mulder, do you remember when I was missing -- that time that you *still* insist I was being held aboard a UFO?" "How could I forget?" "Well, I'm beginning to wonder if maybe I wouldn't have been better off staying abo-- I mean, wherever it was that I was being held." [from an untitled spamfic by SkyFire@aol.com]
Subject: Re: Padding scheme? Date: Wed, 1 Nov 2000 01:04:03 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G3BMyr.7DM@bath.ac.uk> References: <39FE3405.4DA9BF95@earthlink.net> Newsgroups: sci.crypt Lines: 94 Benjamin Goldberg <goldbb2@earthlink.net> wrote: : Tim Tyler wrote: :> Benjamin Goldberg <goldbb2@earthlink.net> wrote: :> :> goldbb2@earthlink.net (Benjamin Goldberg) wrote: :> :> >After having read some other recent stuff on this group discussing :> :> >padding, I realize that a trojan horse type program could use the :> :> >random padding as a subliminal channel. To avoid this, the :> :> >padding should, instead of being random, be the first bytes and :> :> >bits from a cryptographicly secure hash of the message. [...] [snip] :> : Although it's true that using bits from a hash, rather than bits :> : from a TRBG, does create a bijective mapping from the set of :> : messages whose lengths are multiples of 8 bits to the set of :> : messages whose lengths are multiples of 128 bits [...] :> :> s/true/false/ :> :> You've just added a redundant section to the message. A bit like :> cutting the first few characters and pastuing them onto the end of the :> file. No bijective map is likely to be found there. : Note that the domain and range are not the same. The domain is the set : of messages whose lengths are integral numbers of 8-bit bytes. The : range is the set of messages whose lengths are integral numbers of : 128-bit blocks. If the hash of the message is used as the source of : 'random' padding bytes, then each message in the domain maps to : precisely one message in the range. Furthermore, the inverse function, : which strips padding, maps each message in the range of the padding : function to one and only one message in the domain. Does not this : padding scheme describe a mapping that is one-to-one and onto? No. You're correct that each message in the domain maps onto one and only one object in the range. However you are not correct that each message in the range maps onto one and only one message in the domain. To illustrate this, I'll present an example, using a dumbed down, trivialised version of your padding scheme (which will hopefully nonetheless contain sufficient elements to illustrate the point). Consider the mapping between: [Message] and [Message|128 bit hash of the message] (where "|" indicates a stratigtforwards appending of the data). Is this mapping a bijection? No. Proof? To recover the [message] from the combined [message|hash],one simply strips off the last 128 bits. Obviously this stripping is many to one operation. 101010011|1111100 gets mapped to 101010011. 101010011|0101010 *also * gets mapped to 101010011. Your system is much the same. A number of 128-bit granular objects map to the same original 8-bit file (or some of them don't map to anything and do something like generate errors). :> : there is no significant difference in security between the original :> : 1-to-many mapping and the hash-based 1-to-1 mapping. :> :> You don't rate that ability to reject keys on the basis of their :> having appended padding in the form of hash data (that doesn't :> match the contents of the message) as a security risk? : Consider that the entire message must be decrypted to be able to reject : a key. There's a tradeoff... either use a RBG to create the padding, : and risk the possibility of a subliminal channel being snuck in (a : trojan horsed encryption program) by your opponent, or use hash bits, : which allow rejection of keys. [...] These are (more or less) the only options if you are using random padding. There's an alternative (which David advocates) - which is not using any padding at all and simply applying a bijective map between the set of 8-bit files and the set of 128-bit ones. This method has a number of attractions - however, I believe it has an imperfection of its own. There's another alternative to padding - which is to use an encryption algorithm that can cope with variable size messages, without padding them. Cyphertext stealing is one such method of converting an ordinary block cypher into such a variable-length device - though it too appears to have an imperfection. -- __________ http://alife.co.uk/ http://mandala.co.uk/ |im |yler tt@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Subject: Re: Padding scheme? Date: 1 Nov 2000 03:01:36 GMT From: this.address@is.for.spamers (SCOTT19U.ZIP_GUY) Message-ID: <8FDEC3F7AH110W296@207.36.190.226> References: <G3BMyr.7DM@bath.ac.uk> Newsgroups: sci.crypt Lines: 108 tt@cryogen.com (Tim Tyler) wrote in <G3BMyr.7DM@bath.ac.uk>: >Benjamin Goldberg <goldbb2@earthlink.net> wrote: >: Tim Tyler wrote: >:> Benjamin Goldberg <goldbb2@earthlink.net> wrote: >:> :> goldbb2@earthlink.net (Benjamin Goldberg) wrote: > >:> :> >After having read some other recent stuff on this group discussing >:> :> >padding, I realize that a trojan horse type program could use the >:> :> >random padding as a subliminal channel. To avoid this, the >:> :> >padding should, instead of being random, be the first bytes and >:> :> >bits from a cryptographicly secure hash of the message. [...] > >[snip] > >:> : Although it's true that using bits from a hash, rather than bits >:> : from a TRBG, does create a bijective mapping from the set of >:> : messages whose lengths are multiples of 8 bits to the set of >:> : messages whose lengths are multiples of 128 bits [...] >:> >:> s/true/false/ >:> >:> You've just added a redundant section to the message. A bit like >:> cutting the first few characters and pastuing them onto the end of the >:> file. No bijective map is likely to be found there. > >: Note that the domain and range are not the same. The domain is the set >: of messages whose lengths are integral numbers of 8-bit bytes. The >: range is the set of messages whose lengths are integral numbers of >: 128-bit blocks. If the hash of the message is used as the source of >: 'random' padding bytes, then each message in the domain maps to >: precisely one message in the range. Furthermore, the inverse function, >: which strips padding, maps each message in the range of the padding >: function to one and only one message in the domain. Does not this >: padding scheme describe a mapping that is one-to-one and onto? > >No. You're correct that each message in the domain maps onto one and only >one object in the range. > >However you are not correct that each message in the range maps >onto one and only one message in the domain. > >To illustrate this, I'll present an example, using a dumbed down, >trivialised version of your padding scheme (which will hopefully >nonetheless contain sufficient elements to illustrate the point). > >Consider the mapping between: > >[Message] and [Message|128 bit hash of the message] (where "|" indicates >a stratigtforwards appending of the data). > >Is this mapping a bijection? No. Proof? > >To recover the [message] from the combined [message|hash],one simply >strips off the last 128 bits. > >Obviously this stripping is many to one operation. > >101010011|1111100 gets mapped to 101010011. >101010011|0101010 *also * gets mapped to 101010011. > >Your system is much the same. A number of 128-bit granular objects map to >the same original 8-bit file (or some of them don't map to anything and >do something like generate errors). > >:> : there is no significant difference in security between the original >:> : 1-to-many mapping and the hash-based 1-to-1 mapping. >:> >:> You don't rate that ability to reject keys on the basis of their >:> having appended padding in the form of hash data (that doesn't >:> match the contents of the message) as a security risk? > >: Consider that the entire message must be decrypted to be able to reject >: a key. There's a tradeoff... either use a RBG to create the padding, >: and risk the possibility of a subliminal channel being snuck in (a >: trojan horsed encryption program) by your opponent, or use hash bits, >: which allow rejection of keys. [...] > >These are (more or less) the only options if you are using random padding. > >There's an alternative (which David advocates) - which is not using any >padding at all and simply applying a bijective map between the set of >8-bit files and the set of 128-bit ones. > >This method has a number of attractions - however, I believe it >has an imperfection of its own. > >There's another alternative to padding - which is to use an encryption >algorithm that can cope with variable size messages, without padding them. > And that is just what scott16u and scott19u do. They treat the whole file as a single block. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE http://www.jim.com/jamesd/Kong/scott19u.zip Scott famous encryption website **now all allowed** http://members.xoom.com/ecil/index.htm Scott LATEST UPDATED source for scott*u.zip http://radiusnet.net/crypto/ then look for sub directory scott after pressing CRYPTO Scott famous Compression Page http://members.xoom.com/ecil/compress.htm **NOTE EMAIL address is for SPAMERS*** I leave you with this final thought from President Bill Clinton:
Subject: Re: Padding scheme? Date: Tue, 31 Oct 2000 10:56:34 GMT From: Tim Tyler <tt@cryogen.com> Message-ID: <G3AJqA.H08@bath.ac.uk> References: <8FDDA00F6H110W296@207.36.190.226> <39FDF0FC.FDBD0CC5@earthlink.net> Newsgroups: sci.crypt Lines: 29 SCOTT19U.ZIP_GUY <this.address@is.for.spamers> wrote: :>Although it's true that using bits from a hash, rather than bits from a :>TRBG, does create a bijective mapping from the set of messages whose :>lengths are multiples of 8 bits to the set of messages whose lengths are :>multiples of 128 bits [...] : Not only is what you said not true but unless you give more detail : I am not sure you even have a bijective transoformation to from the : plain text to you 128 bits. [...] His proposed scheme does not attempt to produce a bijective map. It's a 1 to many map - though all added information is normally random in character. It appears to be an extension of John Savard's scheme of padding out a stream of bits to an 8-bit block boundary to cope with arbitrary block sizes (though these are limited to byte boundaries, not doubt for practical reasons). It appears to produce "unbiased" output if: * A true RNG is used; * There's a lack of certain kinds of systematic variation in the lengths of the files in the input set; * Power-of-two block sizes are employed. -- __________ http://alife.co.uk/ http://mandala.co.uk/ |im |yler tt@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Terry Ritter, his current address, and his top page.
Last updated: 2001-06-28