Chaining modes are a virtual requirement for the secure use of ciphers with small blocks. But then how do we get random access?
Subject: Enhancement of EBC mode? Date: Tue, 22 Dec 1998 09:13:31 +0100 From: Marco Stolpe <marco.stolpe@usa.net> Message-ID: <367F54AB.173BBA95@usa.net> Newsgroups: sci.crypt Lines: 55 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hello! I'm planning to write an application where encryption of files is needed but random access to the content of these files is necessary. - From chapter nine of the book "Applied Cryptography" by Bruce Schneier (1996) I concluded that the only thing I can do is to use a block cipher with ECB mode. In this book the following negative aspects of ECB are mentioned: " 1) Plaintext patterns are not concealed. 2) Input to the block cipher is not randomized; it is the same as the plaintext. 3) Plaintext is easy to manipulate; blocks can be removed, repeated, or interchanged. " Although I don't know a good solution to 3), I considered the following solution to 1) and 2): - - Decrease the amount of information stored in each byte, for example by using the base64 encoding scheme. - - Fill up the 'free' bits in each byte with random bits produced by a very good random sequence generator (for example the one proposed in chapter 17.14 of the book which I mentioned). - - Encrypt the block with a normal block cipher. Since I'm not a professional cryptographer, I would like to know if such a procedure could increase security of ECB mode in any way? I'd like to hear from you, Marco Stolpe - -- PGP Key, ID 0x4F3FE0B5 should be available on a keyserver Fingerprint: D0AA F39C 0D9D 4AC8 D742 C0DB 3536 3D29 4F3F E0B5 -----BEGIN PGP SIGNATURE----- Version: PGPfreeware 5.0i for non-commercial use Charset: noconv iQA/AwUBNn9UGjU2PSlPP+C1EQI3wwCgryDeEfLncaRIi0bXrYaNioGziG4An0aD PsYMo4YqvIfmzvS+D4swjPoW =stKf -----END PGP SIGNATURE-----
Subject: Re: Enhancement of EBC mode? Date: Tue, 22 Dec 1998 02:10:45 -0800 From: Bryan Olson <bryan.olson@uptronics.com> Message-ID: <367F7025.3A767E97@uptronics.com> References: <367F54AB.173BBA95@usa.net> Newsgroups: sci.crypt Lines: 39 Marco Stolpe wrote: > I'm planning to write an application where encryption of files > is needed but random access to the content of these files is > necessary. [...] > I concluded that the only thing I can > do is to use a block cipher with ECB mode. You actually have lots of options. The most popular is to work in units of pages. You can divide the file into pages of, for example, two kilobytes, and encrypt these units with a better mode. To randomly access byte 2567, you'd need to decrypt the second page, and pull out the byte at offset (2567-2048) within the page. If you can afford an IV for each page, you can use one of standard chaining modes. If not, you can use a mode that makes each ciphertext byte dependent on each byte in the page, and the page number, and one IV for the file. See Peter Gutmann's SFS for an example. http://www.cs.auckland.ac.nz/~pgut001/ > - - Decrease the amount of information stored in each byte, > for example by using the base64 encoding scheme. > > - - Fill up the 'free' bits in each byte with random bits > produced by a very good random sequence generator > (for example the one proposed in chapter 17.14 of the > book which I mentioned). > > - - Encrypt the block with a normal block cipher. Those are good ideas. I think you'd still be better off working in units larger than one typical cipher block. --Bryan
Subject: Re: Enhancement of EBC mode? Date: Tue, 22 Dec 1998 12:51:13 GMT From: neilmck@hotmail.com Message-ID: <75o4k1$5q3$1@nnrp1.dejanews.com> References: <367F54AB.173BBA95@usa.net> Newsgroups: sci.crypt Lines: 27 > " 1) Plaintext patterns are not concealed. > 2) Input to the block cipher is not randomized; it is the same > as the plaintext. > 3) Plaintext is easy to manipulate; blocks can be removed, > repeated, or interchanged. " > Consider the following: As for the plaintext patterns not being concealed, place an 8-byte block containing a random number at the beginning of the file. XOR this value with your key before encrypting-decrypting. Further XOR the key with the offset of the data data block from the beginning of the file (the key is then unique per file and per block). (Note if you are using DEA and your key is spread over 8-bytes you must be sure to XOR your offset with only key bits so that adjacent blocks do not use the same key) To detect manipulation of the data split your plaintext into 6-byte blocks and add a two byte checksum to make an 8-byte block. If the ciphertext is then manipulated or blocks are switched within the file then after decryption the checksum will not match the plaintext. -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Subject: Re: Enhancement of EBC mode? Date: Tue, 22 Dec 1998 13:44:58 GMT From: dscott@networkusa.net Message-ID: <75o7oq$8d5$1@nnrp1.dejanews.com> References: <367F54AB.173BBA95@usa.net> Newsgroups: sci.crypt Lines: 92 In article <367F54AB.173BBA95@usa.net>, Marco Stolpe <marco.stolpe@usa.net> wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > Hello! > > I'm planning to write an application where encryption of files > is needed but random access to the content of these files is > necessary. > > - From chapter nine of the book "Applied Cryptography" by > Bruce Schneier (1996) I concluded that the only thing I can > do is to use a block cipher with ECB mode. In this book the > following negative aspects of ECB are mentioned: > > " 1) Plaintext patterns are not concealed. > 2) Input to the block cipher is not randomized; it is the same > as the plaintext. > 3) Plaintext is easy to manipulate; blocks can be removed, > repeated, or interchanged. " > > Although I don't know a good solution to 3), I considered the > following solution to 1) and 2): > > - - Decrease the amount of information stored in each byte, > for example by using the base64 encoding scheme. > this would be a mistake since it would decrease the total number of different types of blocks while increasing the number of bloks that a hacker can look at. It would make plain text attack easier. > - - Fill up the 'free' bits in each byte with random bits > produced by a very good random sequence generator > (for example the one proposed in chapter 17.14 of the > book which I mentioned). It is very hard to get random data. Since you should assume the attacker may have access to same random number generator. This can also add more time to impliment in a good way than you think. > > - - Encrypt the block with a normal block cipher. > > Since I'm not a professional cryptographer, I would like to > know if such a procedure could increase security of ECB mode > in any way? One simple way to reduce your exposure would to be to use as large a block size as possible. And a simple way to protect data in such an environment is to XOR the block number (index number whatever) used in randomaccess fetch so that the bad effects ECB mode are eliminated. Do this XOR before the block is encrypted. The hardest part is finding a good method for the block size you need. I will eventually write a method using 1675 bits of key space for a scott8u method that would allow a varable block size of 40 to 40,000 bits so those that have similar problems can use it. You can write your own if you like just look at my C code. for file encryption and instead of "file" use a "block" > > I'd like to hear from you, > > Marco Stolpe > > - -- > PGP Key, ID 0x4F3FE0B5 should be available on a keyserver > Fingerprint: > D0AA F39C 0D9D 4AC8 D742 C0DB 3536 3D29 4F3F E0B5 > > -----BEGIN PGP SIGNATURE----- > Version: PGPfreeware 5.0i for non-commercial use > Charset: noconv > > iQA/AwUBNn9UGjU2PSlPP+C1EQI3wwCgryDeEfLncaRIi0bXrYaNioGziG4An0aD > PsYMo4YqvIfmzvS+D4swjPoW > =stKf > -----END PGP SIGNATURE----- > -- 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: Enhancement of EBC mode? Date: Wed, 23 Dec 1998 16:18:50 +0100 From: Marco Stolpe <marco.stolpe@usa.net> Message-ID: <368109DA.E70A98BD@usa.net> References: <75o7oq$8d5$1@nnrp1.dejanews.com> Newsgroups: sci.crypt Lines: 77 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Thanks to all who gave me an advice. Encrypting larger blocks of a file with CBC mode seems to be a good solution. But there's one statement which surprised me a little bit. You (dscott@networkusa.net) wrote: >> - - Decrease the amount of information stored in each byte, >> for example by using the base64 encoding scheme. >> > this would be a mistake since it would decrease the total > number of different types of blocks while increasing the > number of bloks that a hacker can look at. It would make > plain text attack easier. I think that base64 encoding is a bad example, especially because it uses 65 instead of 64 (= 6 bits) different characters. The whole idea of mine was the following: I've read the main danger of using ECB mode is that one block of plaintext always encrypts to the same block of ciphertext. That means that it is theoretically possible to create a code book of plaintexts and corresponding ciphertexts, especially if the whole plaintext has some regularities. So my idea was - for example - to divide each byte of plaintext in the middle and to create two bytes from these half bytes. For example, the byte 0xB6 = 10110110 would lead to 0x_6 = ____0110 and 0x_B = ____1011. Then I would fill up the upper half of the two bytes with random bits (under the assumption of course that it IS possible to create random bits, perhaps by using special hardware events or devices). This means that the 4 bits of valuable information in one byte of plaintext are randomized by the upper 4 bits and that now one block of valuable(!) plaintext together with the 4 random bits encrypts to many different blocks of ciphertext. If the sequence of random bits is really random and equally distributed then there exist 16 different bytes containing the same information in the lower 4 bits and that would make up to 16^8 = 2^32 different blocks of ciphertext for one block of valuable plaintext. So I thought that the goal of randomizing the plaintext and thereby reducing the possibility of creating a code book could be reached by the method which I proposed, and not that it would even make a plaintext attack easier. Of course it would increase (doubling up) the number of blocks a hacker can look at, but I thought that creating different types of plaintext blocks would be much more important for security. Actually I'll prefer the methods that you proposed (encrypting larger blocks of the file in CBC mode), but I'm still a little bit confused. Marco Stolpe - -- PGP Key, ID 0x4F3FE0B5 should be available on a keyserver Fingerprint: D0AA F39C 0D9D 4AC8 D742 C0DB 3536 3D29 4F3F E0B5 -----BEGIN PGP SIGNATURE----- Version: PGPfreeware 5.0i for non-commercial use Charset: noconv iQA/AwUBNoEHoDU2PSlPP+C1EQIKHACdEfv5No3lX3vk1U5H90jdKjESrcoAnihA BIJtd+Bwk+XQ3jM02wWpGdPv =Kf3R -----END PGP SIGNATURE-----
Subject: Re: Enhancement of EBC mode? Date: Thu, 24 Dec 1998 06:31:54 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3681df9a.18319798@news.io.com> References: <368109DA.E70A98BD@usa.net> Newsgroups: sci.crypt Lines: 35 On Wed, 23 Dec 1998 16:18:50 +0100, in <368109DA.E70A98BD@usa.net>, in sci.crypt Marco Stolpe <marco.stolpe@usa.net> wrote: >[...] >Then I would fill up the upper half of the two bytes with >random bits (under the assumption of course that it IS possible >to create random bits, perhaps by using special hardware >events or devices). > >This means that the 4 bits of valuable information in one byte >of plaintext are randomized by the upper 4 bits and that now >one block of valuable(!) plaintext together with the 4 random >bits encrypts to many different blocks of ciphertext. This technique is disclosed in one of the Feistel patents; oddly, we do not find it in the crypto texts. I have been describing it on sci.crypt for the past few years as the "homophonic" block cipher construction. It is "homophonic" in that each different random value selects a different ciphertext for exactly the same data field. The "random" field also can be used to validate the block against possible changes in transit, even if blocks are delivered out of sequence. The technique is obviously most efficient when we have large blocks; Feistel mentions it in the context of 128-bit blocks (Lucifer), but even that would be expensive. We need enough "random" bits per block to make a cryptographic difference. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Enhancement of EBC mode? Date: 23 Dec 1998 23:15:54 GMT From: ka@socrates.hr.lucent.com.no_spam (Kenneth Almquist) Message-ID: <75rtja$1s7@nntpa.cb.lucent.com> References: <367F54AB.173BBA95@usa.net> Newsgroups: sci.crypt Lines: 75 > I'm planning to write an application where encryption of files > is needed but random access to the content of these files is > necessary. > > !- From chapter nine of the book "Applied Cryptography" by > Bruce Schneier (1996) I concluded that the only thing I can > do is to use a block cipher with ECB mode. If you only want to read the data in a random order, you can use CBC mode. (To decrypt a block, you have to read the preceding block as well, which should not be a major problem.) So I assume you need to write random locations as well as read them. You seem to be assuming that the only alternative to CBC mode is ECB mode. To understand the other alternatives, it may be helpful to review the rationale for CBC mode. The basic weakness of ECB mode is that a pair of identical plaintext blocks will produce identical ciphertext blocks. To avoid this, we need to come up with an encryption function which encrypts each block differently. Specificly, we want to come up with a block encryption function C = E'(P, K, BN, IV, Prev) where C is the ciphertext block produced by the function. P is the plaintext block to encrypt. K is the encrytion key. BN is the block number of the block to encrypt. IV is a random value. Prev is a vector consisting of all plaintext blocks which precede P. The first two arguments are the arguments standardly passed to a block encryption algorithm. The next argument is BN. It is used to cause the encryption function to be different for each block in the file. The IV argument is needed to prevent block BN of two different files from being encrypted the same way. From a security point of view, it does not matter whether E' uses its last argument. The latter arguments to E' act like additional key data. In fact, the most conceptually simple way to define E' is to define E'(P, K, BN, IV, Prev) = E(P, K || BN || IV) where || is the concatenation operator. The defintion of E' used with CBC mode is E'(P, K, BN, IV, Prev) = E(P xor H(BN, IV, Prev), K) H is a hash function. It is defined as follows: function H(BN, IV, Prev) is result := IV for i := 1 to BN - 1 do result := result xor Prev[i] result := E(result, K) return result This hash function produces uniformly distributed random numbers if the block encryption function E is any good. But the real cleverness in this choice of hash function is the fact that it is equal to the result of encrypting the previous block. Thus there is no need to actually compute this hash function. Once you understand the theory behind CBC mode, coming up with an alternative which allows random access is straightforward. For example, you can stick with the hash function approach, but use a hash function which doesn't depend upon the value of Prev. One such hash function is E(BN, IV), giving us: E'(P, K, BN, IV, Prev) = E(P xor E(BN, IV), K) The coresponding decryption function is D'(C, K, BN, IV, Prev) = D(C, K) xor E(BN, IV) Kenneth Almquist
Subject: Re: Enhancement of EBC mode? Date: Thu, 24 Dec 1998 06:32:24 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3681dfde.18387695@news.io.com> References: <75rtja$1s7@nntpa.cb.lucent.com> Newsgroups: sci.crypt Lines: 40 On 23 Dec 1998 23:15:54 GMT, in <75rtja$1s7@nntpa.cb.lucent.com>, in sci.crypt ka@socrates.hr.lucent.com.no_spam (Kenneth Almquist) wrote: >> I'm planning to write an application where encryption of files >> is needed but random access to the content of these files is >> necessary. >[...] >The basic weakness of ECB >mode is that a pair of identical plaintext blocks will produce >identical ciphertext blocks. To avoid this, we need to come up >with an encryption function which encrypts each block differently. >Specificly, we want to come up with a block encryption function > > C = E'(P, K, BN, IV, Prev) >where > C is the ciphertext block produced by the function. > P is the plaintext block to encrypt. > K is the encrytion key. > BN is the block number of the block to encrypt. > IV is a random value. > Prev is a vector consisting of all plaintext blocks which precede P. Let me point out that it can be a serious mistake to build a system which uses a file position in encryption. For example, if the file is any form of database, it could not then be re-organized, nor could new blocks be "inserted" in the middle. So while this solution may be fine for reading static files or ciphering absolute storage, that same approach may be inappropriate in a dynamic database. One alternative is to store a "block number" value along with each block so that it travels with the block. But it would be easier to just save an IV for each block. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Enhancement of EBC mode? Date: Thu, 24 Dec 1998 17:08:44 GMT From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) Message-ID: <368272c2.1212553@news.prosurfr.com> References: <3681dfde.18387695@news.io.com> Newsgroups: sci.crypt Lines: 51 ritter@io.com (Terry Ritter) wrote, in part: >Let me point out that it can be a serious mistake to build a system >which uses a file position in encryption. For example, if the file is >any form of database, it could not then be re-organized, nor could new >blocks be "inserted" in the middle. So while this solution may be >fine for reading static files or ciphering absolute storage, that same >approach may be inappropriate in a dynamic database. >One alternative is to store a "block number" value along with each >block so that it travels with the block. But it would be easier to >just save an IV for each block. For the application discussed, altering the data to obscure patterns by XORing each block with its absolute address need not create a problem; data is decrypted whenever it is read, and it is encrypted whenever it is written. If an application *not authorized to read the data* were, nontheless, permitted to re-organize the data, then there would be a problem. This situation, though, does not occur in many applications: in some, for example, without the decryption key, not only does one have no idea where record boundaries are, one also does not know which blocks belong to a file. Just as in networks there is a difference between end-to-end encryption and link-to-link encryption, whole-disk and whole-file encryption can do certain things, and record encryption can do others. So one could use CBC mode within a record, and one could use the XOR of an address relative to the start of the file for file encryption, and one could use the XOR of a track and sector address for disk encryption without a problem. Someone with the disk encryption password only could still copy the file to another disk without destroying it; someone with the disk encryption password and the file encryption password could move records within the file; and someone with all three keys could modify and read data within a record. So it depends on the level where encryption is used what measures are available to mask against codebook attacks without preventing random access. John Savard http://www.freenet.edmonton.ab.ca/~jsavard/index.html
Subject: Re: Enhancement of EBC mode? Date: Thu, 24 Dec 1998 19:28:31 GMT From: ritter@io.com (Terry Ritter) Message-ID: <368295a6.9181110@news.io.com> References: <368272c2.1212553@news.prosurfr.com> Newsgroups: sci.crypt Lines: 90 On Thu, 24 Dec 1998 17:08:44 GMT, in <368272c2.1212553@news.prosurfr.com>, in sci.crypt jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) wrote: >ritter@io.com (Terry Ritter) wrote, in part: > >>Let me point out that it can be a serious mistake to build a system >>which uses a file position in encryption. For example, if the file is >>any form of database, it could not then be re-organized, nor could new >>blocks be "inserted" in the middle. So while this solution may be >>fine for reading static files or ciphering absolute storage, that same >>approach may be inappropriate in a dynamic database. > >>One alternative is to store a "block number" value along with each >>block so that it travels with the block. But it would be easier to >>just save an IV for each block. > >For the application discussed, altering the data to obscure patterns >by XORing each block with its absolute address need not create a >problem; > >data is decrypted whenever it is read, and it is encrypted whenever it >is written. > >If an application *not authorized to read the data* were, nontheless, >permitted to re-organize the data, then there would be a problem. This >situation, though, does not occur in many applications: in some, for >example, without the decryption key, not only does one have no idea >where record boundaries are, one also does not know which blocks >belong to a file. > >Just as in networks there is a difference between end-to-end >encryption and link-to-link encryption, whole-disk and whole-file >encryption can do certain things, and record encryption can do others. > >So one could use CBC mode within a record, and one could use the XOR >of an address relative to the start of the file for file encryption, >and one could use the XOR of a track and sector address for disk >encryption without a problem. > >Someone with the disk encryption password only could still copy the >file to another disk without destroying it; > >someone with the disk encryption password and the file encryption >password could move records within the file; > >and someone with all three keys could modify and read data within a >record. > >So it depends on the level where encryption is used what measures are >available to mask against codebook attacks without preventing random >access. Yes, an encryption sensitivity to physical storage location can be hidden by deciphering on every read, then enciphering on every write, but this can have both significant costs and unexpected risks. Consider, for example, the case of disk encryption, where the plaintext is randomized by a track / sector hash. Inevitably there will come a time when we wish to upgrade storage with a new drive. Now, upgrading can be tedious even when we do just a straight copy from drive to drive. But when the encryption depends upon the track / sector position, we have to read each "block," decipher it, decide where to put it, then re-encipher the block on the new drive. This is a significant overhead at a bad time, and incidentally implies the transient exposure of the data as plaintext. Worse, the inability to simply copy sector contents to new store is a mortgage on the future and a risk of failure to intervene, since automatic upgrade utilities will only copy sectors and change file pointers. So if there comes a day when the encrypted data is forgotten and the storage upgraded (which can be as simple as being away on a trip), the data will simply become usable. This is not a risk of losing a record or two; this is the risk of losing an entire database, with everything inside, and all the effort it took to construct. But these costs need not be paid and the risks need not be taken if we don't first design a system which depends upon physical storage values which may change in the future. And there are similar overhead and transient exposure problems with respect to the reorganization of database storage within files, when encryption depends upon file position. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Enhancement of EBC mode? Date: Thu, 24 Dec 1998 16:53:29 GMT From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) Message-ID: <36827058.593902@news.prosurfr.com> References: <367F54AB.173BBA95@usa.net> Newsgroups: sci.crypt Lines: 24 Marco Stolpe <marco.stolpe@usa.net> wrote, in part: >I'm planning to write an application where encryption of files >is needed but random access to the content of these files is >necessary. >- From chapter nine of the book "Applied Cryptography" by >Bruce Schneier (1996) I concluded that the only thing I can >do is to use a block cipher with ECB mode. As others have noted, that isn't quite true. As has been noted, if you need random access to the files, but in units of blocks or records, where a block or record is larger than the blocksize of the cipher you're using, then you can always use CBC mode within each block or record. To conceal patterns in the plaintext, where you actually are restricted to ECB mode, you can always XOR each plaintext block with its address (perhaps also trivially encrypted). This avoids having to expand the plaintext at all. John Savard http://www.freenet.edmonton.ab.ca/~jsavard/index.html
Terry Ritter, his current address, and his top page.
Last updated: 1999-02-20