If we use a block cipher, how can we avoid causing the message to expand when ciphering? And what do we do when the message is shorter than a block?
Subject: CTS a la Schneier, Rivest Date: 4 Jan 1999 19:16:49 GMT From: becker@Xenon.Stanford.EDU (Jon Becker) Message-ID: <76r431$h5g$1@nntp.Stanford.EDU> Newsgroups: sci.crypt Lines: 31 I have a question about Ciphertext Stealing, particularly as it relates to RC5. In "Applied Cryptography" (Schneier, p. 195) as well as in RFC 2040 (section 8, on RC5-CTS), CTS is described as a way of using a block cipher to encrypt a message of any size and have the ciphertext length match the plaintext length. In both documents, however, the descriptions assume the existence of a second-to-last block of full size. My question is, how does one use CTS to generate the ciphertext for a plaintext message which is less than the cipher's block size (so that the aforementioned assumption doesn't hold)? For example, if I'm using RC5 with a 64-bit block size and I have a plaintext message which is 6 bytes long, what will the ciphertext be using RC5-CTS? I suppose it would be possible to act as if the IV is the encryption of the second-to-last plaintext block. Then it would be XORed with the plaintext padded with 0s and encrypted to form the second-to-last ciphertext block. This would be transmitted as a new IV, while the first 6 bytes of the original IV would be transmitted as the real ciphertext. I'm reasonably sure this method maintains security, but it does have the disadvantage of changing the IV before and after encryption, which is pretty much contrary to the idea of an IV. Can anyone point me to some definitive documentation on the subject? -Jon
Subject: Re: CTS a la Schneier, Rivest Date: Mon, 04 Jan 1999 22:59:39 GMT From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) Message-ID: <36914690.3976436@news.prosurfr.com> References: <76r431$h5g$1@nntp.Stanford.EDU> Newsgroups: sci.crypt Lines: 34 becker@Xenon.Stanford.EDU (Jon Becker) wrote, in part: >In both documents, however, the descriptions assume the existence of a >second-to-last block of full size. My question is, how does one use >CTS to generate the ciphertext for a plaintext message which is less >than the cipher's block size (so that the aforementioned assumption >doesn't hold)? There is no method to encipher a message of less than the blocksize in length, using ECB mode, to produce an enciphered message of the same length. Thus, while one could still use the block cipher, either by padding the message to a full block, or by using a stream cipher mode such as counter mode, no technique that sufficiently resembles "ciphertext stealing" to be called a case of it is applicable to such short messages. Essentially, the only difference between the complicated-looking "ciphertext stealing" technique depicted in AC and simply enciphering each complete block of the message, and then, if an incomplete block is left unenciphered, enciphering the last 64 bits (or whatever the blocksize is) of the message is that the ciphertext stealing technique avoids alignment problems. (Myself, I would tend to encipher the last 8 bytes - and use the ciphertext stealing technique only to fill out the last byte if incomplete.) Clearly, you can't encipher the 'first 64 bits' and the 'last 64 bits' of something less than 64 bits long. John Savard http://www.freenet.edmonton.ab.ca/~jsavard/index.html
Subject: Re: CTS a la Schneier, Rivest Date: 4 Jan 1999 23:23:55 GMT From: becker@Xenon.Stanford.EDU (Jon Becker) Message-ID: <76riib$mq8$1@nntp.Stanford.EDU> References: <36914690.3976436@news.prosurfr.com> Newsgroups: sci.crypt Lines: 42 In article <36914690.3976436@news.prosurfr.com>, John Savard <jsavard@tenMAPSONeerf.edmonton.ab.ca> wrote: >becker@Xenon.Stanford.EDU (Jon Becker) wrote, in part: > >>In both documents, however, the descriptions assume the existence of a >>second-to-last block of full size. My question is, how does one use >>CTS to generate the ciphertext for a plaintext message which is less >>than the cipher's block size (so that the aforementioned assumption >>doesn't hold)? > >There is no method to encipher a message of less than the blocksize in >length, using ECB mode, to produce an enciphered message of the same >length. > >Thus, while one could still use the block cipher, either by padding >the message to a full block, or by using a stream cipher mode such as >counter mode, no technique that sufficiently resembles "ciphertext >stealing" to be called a case of it is applicable to such short >messages. > >Essentially, the only difference between the complicated-looking >"ciphertext stealing" technique depicted in AC and simply enciphering >each complete block of the message, and then, if an incomplete block >is left unenciphered, enciphering the last 64 bits (or whatever the >blocksize is) of the message is that the ciphertext stealing technique >avoids alignment problems. > >(Myself, I would tend to encipher the last 8 bytes - and use the >ciphertext stealing technique only to fill out the last byte if >incomplete.) > >Clearly, you can't encipher the 'first 64 bits' and the 'last 64 bits' >of something less than 64 bits long. Yes, clearly. So we have a conundrum. According to RFC 2040: This mode handles any length of plaintext and produces ciphertext whose length matches the plaintext length. So what is one to make of that? Is it just a mistake? -Jon
Subject: Re: CTS a la Schneier, Rivest Date: 4 Jan 1999 18:41:46 -0500 From: giff@eng.us.uu.net (Frank Gifford) Message-ID: <76rjjq$mgl@trebuchet.eng.us.uu.net> References: <76riib$mq8$1@nntp.Stanford.EDU> Newsgroups: sci.crypt Lines: 35 In article <76riib$mq8$1@nntp.Stanford.EDU>, Jon Becker <becker@Xenon.Stanford.EDU> wrote: >In article <36914690.3976436@news.prosurfr.com>, >John Savard <jsavard@tenMAPSONeerf.edmonton.ab.ca> wrote: >>becker@Xenon.Stanford.EDU (Jon Becker) wrote, in part: >> >>>In both documents, however, the descriptions assume the existence of a >>>second-to-last block of full size. My question is, how does one use >>>CTS to generate the ciphertext for a plaintext message which is less >>>than the cipher's block size (so that the aforementioned assumption >>>doesn't hold)? >> >>There is no method to encipher a message of less than the blocksize in >>length, using ECB mode, to produce an enciphered message of the same >>length. Take the last complete encrypted block and encrypt that again. Then do an XOR with an equal number of bytes from that result and the final bytes of the message. There is a potential problem of the encryption of two messages which differ only in those bytes, however, so this is more of a "here's a way to do it" situation. In many cases, padding is added to bring the message to a block size. If you want to encrypt a message which has a smaller blocksize than your cipher, you can tack on 0 bits to the beginning, encrypt that, chop off the first several bits and send the answer. Your recipient then can try decrypting all possible starting bit values and which have the sent message as the remainder. When he gets a decryption starting with all zero bits, he knows he has the right answer. [This example is a little far fetched, I know - it's just for illustration.] -Giff -- giff@uu.net Too busy for a .sig
Subject: Re: CTS a la Schneier, Rivest Date: Tue, 05 Jan 1999 13:10:27 GMT From: dscott@networkusa.net Message-ID: <76t303$jv$1@nnrp1.dejanews.com> References: <76rjjq$mgl@trebuchet.eng.us.uu.net> Newsgroups: sci.crypt Lines: 31 In article <76rjjq$mgl@trebuchet.eng.us.uu.net>, giff@eng.us.uu.net (Frank Gifford) wrote: snip ... > > If you want to encrypt a message which has a smaller blocksize than your > cipher, you can tack on 0 bits to the beginning, encrypt that, chop off > the first several bits and send the answer. Your recipient then can try > decrypting all possible starting bit values and which have the sent message > as the remainder. When he gets a decryption starting with all zero bits, > he knows he has the right answer. [This example is a little far fetched, > I know - it's just for illustration.] Actuall the above does not work since getting all zeros does not even necessiarly mean you have the right soultion and more than one solution can exist. I guess it means you have not played much with encryption. There are several modes of encryption that allow short blocks and most are enferior. Even the mode in PGP 2.6.3 is worse than ECB since it uses a stream generated by the key only then XOR s the result with the file to be encrypted. This allows short blocks and any lenght files. Many codes use this method. But it sucks. David Scott P.S. like at common chainning modes in the FAQ -- http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip http://members.xoom.com/ecil/index.htm -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Subject: Re: CTS a la Schneier, Rivest Date: 5 Jan 99 03:16:13 GMT From: jsavard@ecn.ab.ca () Message-ID: <369183fd.0@ecn.ab.ca> References: <76riib$mq8$1@nntp.Stanford.EDU> Newsgroups: sci.crypt Lines: 18 Jon Becker (becker@Xenon.Stanford.EDU) wrote: : Yes, clearly. So we have a conundrum. According to RFC 2040: : This mode handles any length of plaintext and produces : ciphertext whose length matches the plaintext length. : So what is one to make of that? Is it just a mistake? Yes. However, "any length" may simply have meant any length that may arise in practice; the caveat concerning a message shorter than a single block may have been a detail not worth the words it would have taken to mention it: even in a standards document, people will sometimes speak without using mathematical precision. An oversight, or an oversimplification. Not even just a full-fledged mistake, but less than a mistake. John Savard
Subject: Re: CTS a la Schneier, Rivest Date: Mon, 04 Jan 1999 23:00:17 GMT From: dscott@networkusa.net Message-ID: <76rh61$nr4$1@nnrp1.dejanews.com> References: <76r431$h5g$1@nntp.Stanford.EDU> Newsgroups: sci.crypt Lines: 57 In article <76r431$h5g$1@nntp.Stanford.EDU>, becker@Xenon.Stanford.EDU (Jon Becker) wrote: > > I have a question about Ciphertext Stealing, particularly as it > relates to RC5. In "Applied Cryptography" (Schneier, p. 195) as well > as in RFC 2040 (section 8, on RC5-CTS), CTS is described as a way of > using a block cipher to encrypt a message of any size and have the > ciphertext length match the plaintext length. > > In both documents, however, the descriptions assume the existence of a > second-to-last block of full size. My question is, how does one use > CTS to generate the ciphertext for a plaintext message which is less > than the cipher's block size (so that the aforementioned assumption > doesn't hold)? > > For example, if I'm using RC5 with a 64-bit block size and I have a > plaintext message which is 6 bytes long, what will the ciphertext be > using RC5-CTS? > > I suppose it would be possible to act as if the IV is the encryption > of the second-to-last plaintext block. Then it would be XORed with > the plaintext padded with 0s and encrypted to form the second-to-last > ciphertext block. This would be transmitted as a new IV, while the > first 6 bytes of the original IV would be transmitted as the real > ciphertext. > > I'm reasonably sure this method maintains security, but it does have > the disadvantage of changing the IV before and after encryption, which > is pretty much contrary to the idea of an IV. > > Can anyone point me to some definitive documentation on the subject? > > -Jon > Scott16u and scott19u also have this feature for long files the length of the encrypted file can be exactly the same as the plaintext file. However files that are too short can't be encrypted at all unless one uses the option of adding random padding to the file which makes the encrypted file longer but yet allows short plain text files to be encrypted. It also has the advantage that short files that are identical and encrypted with same key will be totally different in the encrypted state. The method used realies on "wrapped PCBC" see source code and it can be used with any block cipher it would greatly encrease the strength of encryption compared to simple methods endorsed by Mr B.S and his NSA friends. Just my opinion never having read his book. David Scott -- http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip http://members.xoom.com/ecil/index.htm -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Terry Ritter, his current address, and his top page.
Last updated: 1999-02-20