This conversation starts with a request for a cipher which does not expand the ciphertext. Since most cipher systems do in fact use random "IV" or "message key" values, which do constitute "expansion," this can be a tricky goal. One suggestion here is to step the key, but then a lost message will also confuse the stepping sequence.
Often such a request is made in conjunction with the direct ciphering of low-level disk sectors. One common approach is to use the track/sector address as part of the key or IV, but that can be dangerous. (For example, it is common to upgrade disk capacity by putting in a new drive and using disk utilities to copy the data from the old drive to the new one. But that will change the track/sector address, making the old data unrecoverable. We then hope company upgrades do not happen while we are on vacation.)
The main part of the conversation is the introduction of the stream cipher described in an Encyclopedia Britannica article. This cipher differs from the usual stream cipher in the open literature in that the data are not merely combined with an RNG keystream, but are themselves operated on by shift register techniques.
Subject: Re: what cipher? Date: Thu, 03 Jun 1999 04:36:41 GMT From: ritter@io.com (Terry Ritter) Message-ID: <375605b1.4543504@news.io.com> References: <928372166.713.23@news.remarQ.com> Newsgroups: sci.crypt Lines: 63 On Wed, 2 Jun 1999 21:09:19 -0400, in <928372166.713.23@news.remarQ.com>, in sci.crypt "Particle" <bsptree@geocities.com> wrote: >I'm looking for a stream cipher, or a block cipher >that works in 8-bit intervals. (actually, I'm looking for >the algorithm, I'm planning on implementing it myself) > >It is very important that the ciphertext retain the length >of plain text. It is extremely difficult to have a secure cipher which does not expand the ciphertext to some extent. In particular, the usual additive stream cipher must "never" re-use its ciphering or confusion sequence. That means we need a different key for every "message," and so probably implies at least a message key in addition to the data, which thus expands the ciphertext. There is some possibility of allowing some re-use of stream cipher confusion sequences in ciphers which discard additive combiners like exclusive-OR for table-based reversible nonlinear combiners such as Dynamic Substitution. (Note: I own Dynamic Substitution technology.) An ordinary 8-byte block cipher is universally considered too small to use in ECB (electronic codebook) mode, and most chaining modes will require at least an IV (initialization value) which will expand the ciphertext. Even ECB mode would expand the ciphertext for messages which are not an integral number of blocks. Even a 16-byte block cipher is probably too small for ciphering language plaintext in ECB mode. The non-expansion requirement often comes up when ciphering low-level disk storage. Fortunately, disk sectors normally have a length which is an integral number of block cipher blocks. Many people have attacked the problem by putting track and sector values into a hash, which then provides a unique random-like key for each sector, so each sector can be ciphered independently. But this is extremely risky if ever the disk is replaced with the data copied without being first deciphered (office machines are sometimes upgraded in just this way). It is possible to have large block ciphers (e.g., Mixing Ciphers) with a block size sufficient to generally avoid the ECB problem, although they still have the usual problem with wasted space in the last block with variable-size messages. (Note: I own Mixing Cipher technology.) It is also possible to have variable size block ciphers (VSBC's) which generally solve both the ECB problem and often can avoid wasted space in the last block even with variable-size messages. If the last block is too short for strength, data can be re-allocated from the preceding block, *provided* that block is long enough. If not, there is not much to be done. (Note: I own VSBC technology.) But if you need to handle short and long messages without *any* expansion at all, that will be very difficult. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: what cipher? Date: Thu, 03 Jun 1999 09:58:39 GMT From: "Douglas A. Gwyn" <DAGwyn@null.net> Message-ID: <37565180.7C920E3B@null.net> References: <375605b1.4543504@news.io.com> Newsgroups: sci.crypt Lines: 16 Terry Ritter wrote: > It is extremely difficult to have a secure cipher which does not > expand the ciphertext to some extent. In particular, the usual > additive stream cipher must "never" re-use its ciphering or confusion > sequence. That means we need a different key for every "message," and > so probably implies at least a message key in addition to the data, > which thus expands the ciphertext. Good stream ciphers aren't normally additive-key systems; the stock example is a feedback shift register, where plaintext feeds one end and ciphertext is produced at the other end. (The key determines the initial fill and some of the feedback parameters.) It is easy enough to combine the (variable) message sequence number with the (fixed) key to produce a different set of cryptovariables for each message.
Subject: Re: what cipher? Date: Thu, 03 Jun 1999 17:25:35 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3756ba69.3204406@news.io.com> References: <37565180.7C920E3B@null.net> Newsgroups: sci.crypt Lines: 43 On Thu, 03 Jun 1999 09:58:39 GMT, in <37565180.7C920E3B@null.net>, in sci.crypt "Douglas A. Gwyn" <DAGwyn@null.net> wrote: >Terry Ritter wrote: >> It is extremely difficult to have a secure cipher which does not >> expand the ciphertext to some extent. In particular, the usual >> additive stream cipher must "never" re-use its ciphering or confusion >> sequence. That means we need a different key for every "message," and >> so probably implies at least a message key in addition to the data, >> which thus expands the ciphertext. > >Good stream ciphers aren't normally additive-key systems; the stock >example is a feedback shift register, where plaintext feeds one end >and ciphertext is produced at the other end. That sounds like the "scrambler" we see in the data stream in modems, probably with keyed feedback paths. We might also know that structure better as a digital filter; the DSP theory people probably have a precise name for it. We can assume the feedback will be nonlinear, but making secure tap and function selections would seem to require a lot of new thought. Anyone aware of related literature, please let me know. >(The key determines >the initial fill and some of the feedback parameters.) > >It is easy enough to combine the (variable) message sequence number >with the (fixed) key to produce a different set of cryptovariables >for each message. Sure. In general I would call that a "message key," and not having some such thing is a very serious loss. But it *expands* the overall message by the size of the message key or IV, and it was my understanding that the original question wanted to avoid *any* data expansion at all. But if less than that was implied, we will be back into the comfortable area of "can do" cryptography. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: what cipher? Date: Fri, 04 Jun 1999 06:08:32 GMT From: "Douglas A. Gwyn" <DAGwyn@null.net> Message-ID: <37576D1A.BCD52876@null.net> References: <3756ba69.3204406@news.io.com> Newsgroups: sci.crypt Lines: 16 Terry Ritter wrote: > On Thu, 03 Jun 1999 09:58:39 GMT, in <37565180.7C920E3B@null.net>, in > sci.crypt "Douglas A. Gwyn" <DAGwyn@null.net> wrote: > >It is easy enough to combine the (variable) message sequence number > >with the (fixed) key to produce a different set of cryptovariables > >for each message. > Sure. In general I would call that a "message key," and not having > some such thing is a very serious loss. But it *expands* the overall > message by the size of the message key or IV, ... No, it doesn't -- the sequence number can be maintained synchronously at both ends of the link. However, typically there will be some "message header" containing routing instructions, indicators, MCNs, MSNs, etc. *and that overhead would be present regardless of the crypto algorithm*. Might as well use the routing-independent part to help generate message-unique cryptovariables.
Subject: Re: what cipher? Date: Fri, 04 Jun 1999 16:10:15 -0600 From: jgfunj@vgrknf.arg (wtshaw) Message-ID: <jgfunj-0406991610160001@dial-243-123.itexas.net> References: <37576D1A.BCD52876@null.net> Newsgroups: sci.crypt Lines: 26 In article <37576D1A.BCD52876@null.net>, "Douglas A. Gwyn" <DAGwyn@null.net> wrote: > Terry Ritter wrote: > > On Thu, 03 Jun 1999 09:58:39 GMT, in <37565180.7C920E3B@null.net>, in > > sci.crypt "Douglas A. Gwyn" <DAGwyn@null.net> wrote: > > >It is easy enough to combine the (variable) message sequence number > > >with the (fixed) key to produce a different set of cryptovariables > > >for each message. > > Sure. In general I would call that a "message key," and not having > > some such thing is a very serious loss. But it *expands* the overall > > message by the size of the message key or IV, ... > > No, it doesn't -- the sequence number can be maintained synchronously > at both ends of the link. However, typically there will be some > "message header" containing routing instructions, indicators, > MCNs, MSNs, etc. *and that overhead would be present regardless of > the crypto algorithm*. Might as well use the routing-independent > part to help generate message-unique cryptovariables. Olson and Gywn both seem to suggest that maintaining a constant data size through encryption is doable while pushing the details for making it work to somewhere else. This is liken to putting an expendature off-budgit and claiming that the money is not being spent. -- Weathermen prosphesize and insurance companies predict, while both pretend to be doing the other to get an audience.
Subject: Re: what cipher? Date: Thu, 03 Jun 1999 13:41:51 GMT From: dscott@networkusa.net (SCOTT19U.ZIP_GUY) Message-ID: <7j5t6g$34g6$1@news.gate.net> References: <375605b1.4543504@news.io.com> Newsgroups: sci.crypt Lines: 29 In article <375605b1.4543504@news.io.com>, ritter@io.com (Terry Ritter) wrote: > >On Wed, 2 Jun 1999 21:09:19 -0400, in ><928372166.713.23@news.remarQ.com>, in sci.crypt "Particle" ><bsptree@geocities.com> wrote: > >>I'm looking for a stream cipher, or a block cipher >>that works in 8-bit intervals. (actually, I'm looking for >>the algorithm, I'm planning on implementing it myself) >> >>It is very important that the ciphertext retain the length >>of plain text. > If you use the mehods in scott19u which handle any file of over 8 bytes you can use it to encrypt without changing the length of the file. If it is important for the ciphertext to retain the exact length. Any one with a basic understanding of the PC and C should be able to follow the source code that comes with it. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE http://www.jim.com/jamesd/Kong/scott19u.zip http://members.xoom.com/ecil/index.htm NOTE EMAIL address is for SPAMERS
Subject: Re: what cipher? Date: Thu, 03 Jun 1999 17:57:36 GMT From: schneier@counterpane.com (Bruce Schneier) Message-ID: <3756c1d6.16817867@news.visi.com> References: <375605b1.4543504@news.io.com> Newsgroups: sci.crypt Lines: 28 On Thu, 03 Jun 1999 04:36:41 GMT, ritter@io.com (Terry Ritter) wrote: > >On Wed, 2 Jun 1999 21:09:19 -0400, in ><928372166.713.23@news.remarQ.com>, in sci.crypt "Particle" ><bsptree@geocities.com> wrote: > >>I'm looking for a stream cipher, or a block cipher >>that works in 8-bit intervals. (actually, I'm looking for >>the algorithm, I'm planning on implementing it myself) >> >>It is very important that the ciphertext retain the length >>of plain text. > >It is extremely difficult to have a secure cipher which does not >expand the ciphertext to some extent. Actually, I think this is straightforward to do with technology that is in the public domain, that has been analyzed by cryptographers, and is generally trusted. But good luck in whatever you choose. Bruce ********************************************************************** Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098 101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590 Free crypto newsletter. See: http://www.counterpane.com
Subject: Re: what cipher? Date: Thu, 03 Jun 1999 18:37:45 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3756cb3c.7511552@news.io.com> References: <3756c1d6.16817867@news.visi.com> Newsgroups: sci.crypt Lines: 27 On Thu, 03 Jun 1999 17:57:36 GMT, in <3756c1d6.16817867@news.visi.com>, in sci.crypt schneier@counterpane.com (Bruce Schneier) wrote: >On Thu, 03 Jun 1999 04:36:41 GMT, ritter@io.com (Terry Ritter) wrote: > >>[...] >>It is extremely difficult to have a secure cipher which does not >>expand the ciphertext to some extent. > >Actually, I think this is straightforward to do with technology that >is in the public domain, that has been analyzed by cryptographers, and >is generally trusted. So instead of getting information, we get your typical "smarter than thou" response: Teacher says, "Johnny, do you know the answer to the question?" "Yes," says Johnny. OK, I'll bite: What do *you* think would work? That would be: in general, for messages of arbitrary size, with accepted security in all cases. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: what cipher? Date: Fri, 04 Jun 1999 06:57:57 GMT From: "Douglas A. Gwyn" <DAGwyn@null.net> Message-ID: <375778AF.A36543AF@null.net> References: <3756cb3c.7511552@news.io.com> Newsgroups: sci.crypt Lines: 14 Terry Ritter wrote: > OK, I'll bite: What do *you* think would work? That would be: in > general, for messages of arbitrary size, with accepted security in all > cases. Seems to me almost any modern military cryptosystem would work just fine. Unfortunately, there isn't a lot published about systems fielded after WWII. The Encyclopedia Brittanica article on cryptology describes the "n-stage Fibonacci" system, which was one of the earliest successful "purely electronic" cryptosystems, and offers further comment on extensions of the idea. There are exceedingly few people outside the official cryptologic services who could crack such a system, and even then, favorable circumstances are required for the attack to succeed.
Subject: Re: what cipher? Date: Fri, 04 Jun 1999 08:30:05 GMT From: ritter@io.com (Terry Ritter) Message-ID: <37578de7.3727442@news.io.com> References: <375778AF.A36543AF@null.net> Newsgroups: sci.crypt Lines: 55 On Fri, 04 Jun 1999 06:57:57 GMT, in <375778AF.A36543AF@null.net>, in sci.crypt "Douglas A. Gwyn" <DAGwyn@null.net> wrote: >Terry Ritter wrote: >> OK, I'll bite: What do *you* think would work? That would be: in >> general, for messages of arbitrary size, with accepted security in all >> cases. > >Seems to me almost any modern military cryptosystem would work just >fine. As it turns out, I think he is OK with most any stream cipher. >Unfortunately, there isn't a lot published about systems >fielded after WWII. The Encyclopedia Brittanica article on >cryptology describes the "n-stage Fibonacci" system, which was one >of the earliest successful "purely electronic" cryptosystems, and >offers further comment on extensions of the idea. There are >exceedingly few people outside the official cryptologic services who >could crack such a system, and even then, favorable circumstances >are required for the attack to succeed. OK, I *have* that article (on CD). Although the "n-stage Fibonacci" terminology is unfamiliar to me (although I do know that Marsaglia calls the additive and similar RNG's "Fibonacci"), the text description (and especially figure 8) shows a linear feedback shift register (LFSR). That is an old friend which I know very well from electronics, random number generators, and polynomial fields mod 2, and have successfully "attacked" such systems. But the article describes using the LFSR differently than the open systems I know. It implies that we drop plaintext into the SR, step it for a while, then use the result as ciphertext. I would call that a form of block cipher. The article implies that the keying is the step count, and fortunately with a LFSR we do have fast ways to step. It also implies that we have a keying register, which we step enough to diffuse the key and each value we take, then use those values to indicate how much we step the cipher register. Now, I've never tried to recover LFSR step distance knowing initial and resulting values, and with multiple registers that sounds tough. That said, I have experienced LFSR's completely exposing themselves to almost unbelievable degrees. So I can believe that such things could be used, and may be strong, yet know enough to be wary, and not enough to actually do it myself. And I am unaware of anything in the literature which would be much help. I note that we can of course re-key our well-known block ciphers on a block-by-block basis as controlled by another cipher or even a hash of some sort of counter. That has been proposed here before, and generally ignored, but as a matter of fact it may be one of the things we should take more seriously. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: what cipher? Date: 5 Jun 1999 10:27:55 -0700 From: daw@blowfish.isaac.cs.berkeley.edu (David Wagner) Message-ID: <7jbmmr$3ic$1@blowfish.isaac.cs.berkeley.edu> References: <37578de7.3727442@news.io.com> Newsgroups: sci.crypt Lines: 40 In article <37578de7.3727442@news.io.com>, Terry Ritter <ritter@io.com> wrote: > [...] we drop plaintext into the SR, step it for a while, then > use the result as ciphertext. I would call that a form of block > cipher. The article implies that the keying is the step count, and > fortunately with a LFSR we do have fast ways to step. It also implies > that we have a keying register, which we step enough to diffuse the > key and each value we take, then use those values to indicate how much > we step the cipher register. Sounds like an intriguing design, following a different path than any other system I've seen. Thanks for posting the high-level description! Since you looked at the article, would you mind if I ask a few questions? 1. Is this used one-bit-at-a-time (drop a plaintext bit in, step, repeat) or do you drop in the entire plaintext (or at least as much will fit in the register) all at once? 2. Is the output one bit from the main register, or is the entire contents of the register? 3. How on earth do you decrypt?? :-) > Now, I've never tried to recover LFSR > step distance knowing initial and resulting values, and with multiple > registers that sounds tough. Here's an observation: if you know the entire contents of the register before and after the stepping, and you know the taps, then recovering the step distance (for a n-bit LFSR) is just a discrete log problem over GF(2^n). Thus, you can solve it for any stepping distance if n is not too large (<512 or 1024 or so). Also, if the step amount is known to be relatively small, say less than 2^m, then you can solve the discrete log problem with 2^{m/2} operations using a birthday algorithm. It seems like a harder problem if you only know part of the initial and/or final register state. (Use linear consistency checks, maybe?) And I have absolutely no clue about how one might proceed if the taps are unknown.
Subject: Re: what cipher? Date: Sat, 05 Jun 1999 11:00:20 -0400 From: Boris Kazak <bkazak@worldnet.att.net> Message-ID: <37593B84.17CB@worldnet.att.net> References: <7jbmmr$3ic$1@blowfish.isaac.cs.berkeley.edu> Newsgroups: sci.crypt Lines: 44 David Wagner wrote: > > In article <37578de7.3727442@news.io.com>, Terry Ritter <ritter@io.com> wrote: > > [...] we drop plaintext into the SR, step it for a while, then > > use the result as ciphertext. I would call that a form of block > > cipher. The article implies that the keying is the step count, and > > fortunately with a LFSR we do have fast ways to step. It also implies > > that we have a keying register, which we step enough to diffuse the > > key and each value we take, then use those values to indicate how much > > we step the cipher register. > > Sounds like an intriguing design, following a different path than any > other system I've seen. Thanks for posting the high-level description! > > Since you looked at the article, would you mind if I ask a few questions? > > 1. Is this used one-bit-at-a-time (drop a plaintext bit in, step, repeat) > or do you drop in the entire plaintext (or at least as much will fit in > the register) all at once? > 2. Is the output one bit from the main register, or is the entire contents > of the register? > 3. How on earth do you decrypt?? :-) > (snip) -------------------- Actually, courtesy of Lars Knudsen, I published a desciption of a similar cipher in his "Journal of Craptology" (the publisher's comment was "It is a really crappy paper, indeed, obviously resulting from eating an excess amount of magical mushrooms"). The title is "Drunken family", the idea of the cipher boils down to a shift register with the mixing function being modular multiplication, you could call it MFSR - Multiplicative Feedback Shift Register. It is not presented this way in the paper, there the register is stationary and the multiplier moves along the register, but this is a superficial difference. Decryption uses the same operation, with inverses instead of modular multipliers, and the register shifting backwards. If the Journal is still online, you are welcome. Sorry, I don't have yet a Web page. Best wishes BNK
Subject: Re: what cipher? Date: Sat, 05 Jun 1999 18:48:47 GMT From: tomstdenis@my-deja.com Message-ID: <7jbred$cv7$1@nnrp1.deja.com> References: <7jbmmr$3ic$1@blowfish.isaac.cs.berkeley.edu> Newsgroups: sci.crypt Lines: 35 > Since you looked at the article, would you mind if I ask a few questions? > > 1. Is this used one-bit-at-a-time (drop a plaintext bit in, step, repeat) > or do you drop in the entire plaintext (or at least as much will fit in > the register) all at once? Probably a bit at a time. The PnP bios does a checksum this way too. > 2. Is the output one bit from the main register, or is the entire contents of the register? It would have to be the output, you cannot just use the register, since you will not know how to reverse the process without the output. > 3. How on earth do you decrypt?? :-) Well if you have the output and the register you can step backwards can't you? I can't imagine this being very secure... Maybe if the original poster could clarify this a bit? Tom -- PGP public keys. SPARE key is for daily work, WORK key is for published work. The spare is at 'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at 'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first! Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't.
Subject: Re: what cipher? Date: Sat, 05 Jun 1999 19:52:33 GMT From: ritter@io.com (Terry Ritter) Message-ID: <37597f84.6656316@news.io.com> References: <7jbmmr$3ic$1@blowfish.isaac.cs.berkeley.edu> Newsgroups: sci.crypt Lines: 62 On 5 Jun 1999 10:27:55 -0700, in <7jbmmr$3ic$1@blowfish.isaac.cs.berkeley.edu>, in sci.crypt daw@blowfish.isaac.cs.berkeley.edu (David Wagner) wrote: >In article <37578de7.3727442@news.io.com>, Terry Ritter <ritter@io.com> wrote: >> [...] we drop plaintext into the SR, step it for a while, then >> use the result as ciphertext. I would call that a form of block >> cipher. The article implies that the keying is the step count, and >> fortunately with a LFSR we do have fast ways to step. It also implies >> that we have a keying register, which we step enough to diffuse the >> key and each value we take, then use those values to indicate how much >> we step the cipher register. > >Sounds like an intriguing design, following a different path than any >other system I've seen. Thanks for posting the high-level description! > >Since you looked at the article, would you mind if I ask a few questions? The article is written in a sort of handwavy style which is probably easy to interpret if one has worked on such a system. >1. Is this used one-bit-at-a-time (drop a plaintext bit in, step, repeat) > or do you drop in the entire plaintext (or at least as much will fit in > the register) all at once? I think they are talking about tossing a block of text in the register and then scrambling. >2. Is the output one bit from the main register, or is the entire contents > of the register? I think they are talking about taking the whole thing. >3. How on earth do you decrypt?? :-) The main way they mention is to find involutory transformations. I'm surprised they exist, but I generally find them questionable anyway. Presumably, once we have fast stepping and the size of the register, and the key, we can just step 2**n - 1 positions back to plaintext. >> Now, I've never tried to recover LFSR >> step distance knowing initial and resulting values, and with multiple >> registers that sounds tough. > >Here's an observation: if you know the entire contents of the register >before and after the stepping, and you know the taps, then recovering >the step distance (for a n-bit LFSR) is just a discrete log problem over >GF(2^n). This may take your breath away, but I have myself never solved a discrete log problem. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: what cipher? Date: Sat, 05 Jun 1999 19:59:06 GMT From: ritter@io.com (Terry Ritter) Message-ID: <37598142.7102329@news.io.com> References: <37597f84.6656316@news.io.com> Newsgroups: sci.crypt Lines: 16 On Sat, 05 Jun 1999 19:52:33 GMT, in <37597f84.6656316@news.io.com>, in sci.crypt ritter@io.com (Terry Ritter) wrote: >[...] >Presumably, once we have fast stepping and the size of the register, >and the key, we can just step 2**n - 1 positions back to plaintext. I should have said that if we step <key> places from plaintext, we can continue around through ((2**n - 1) - <key>) positions back to plaintext. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: what cipher? Date: Fri, 04 Jun 1999 10:27:21 GMT From: "Douglas A. Gwyn" <DAGwyn@null.net> Message-ID: <3757A9BF.46B6EDA8@null.net> References: <375778AF.A36543AF@null.net> Newsgroups: sci.crypt Lines: 7 "Douglas A. Gwyn" wrote: > ... Encyclopedia Brittanica ... I didn't think that looked right when I wrote it. It's "Britannica", of course. Hm, it's one of those words that doesn't look right no matter *how* you spell it...
Subject: Re: what cipher? Date: 5 Jun 1999 13:46:40 -0700 From: daw@blowfish.isaac.cs.berkeley.edu (David Wagner) Message-ID: <7jc2bg$3lm$1@blowfish.isaac.cs.berkeley.edu> References: <375778AF.A36543AF@null.net> Newsgroups: sci.crypt Lines: 67 Ok, I was intrigued by Doug Gwyn's throwaway comment about the security of the Encyclopedia Britannica system. Thanks to Terry Ritter's help, I think I've managed to re-create the basic idea of the system. It's helpful to think of LFSRs as acting on GF(2^n) = GF(2)[x] / p(x), where p(x) is a primitive polynomial over GF(2) that corresponds to the the LFSR taps. LFSR states may be viewed as appropriate polynomials of degree < n, i.e. as field elements. If we let the initial state by denoted by the field element s, then stepping the LFSR once gives the state s*x (i.e. stepping = multiply by "x" in the Galois field). Therefore, stepping j times yields a state corresponding to the field element s*x^j. The Encyclopedia Britannica construction has two LFSRs, a n-bit main register and a k-bit key register. The plaintext is loaded into the main register, which is stepped a number of times selected by the key register, and the result is the ciphertext; then the key register is stepped enough to diffuse the bits around some. In other words, the encryption of the plaintext s is the ciphertext s*x^j, where j is selected by generating n bits of output from the key register. (Assuming I understand everything correctly.) This construction is easy to break with a known-plaintext attack, at least for reasonable sizes of n, if the taps to the main register are known. We note that recovering j from s, s*x^j is just an instance of the discrete log problem in GF(2^n), and thus can be solved in much less than 2^n time. (In practice, it seems barely possible to solve this type of discrete log problem for n=1024 or so; typical values of n like n=64 or n=128 are trivial to solve.) After we recover a few j values, we learn the output of the key register, which can then be easily cryptanalyzed with the Berlekamp-Massey algorithm (since it is just a single-LFSR system). Ciphertext-only attacks are not so easy, but might still be available. One line of attack is to hope to find two encryptions s*x^j, s*x^i of the same plaintext s, as might happen if s is a fairly-constant header or is some stereotyped text. In this case, we can compute x^{j-i} = (s*x^j)/(s*x^i) from the ciphertexts, and then solve the discrete log problem x, x^{j-i} over GF(2^n) to find the quantity j-i. After a few known values of j-i are recovered, it seems likely that the key register can be easily broken, since the j-i values are just the differences of outputs from a simple single-LFSR system. Another approach to a ciphertext-only attack is to use a meet-in-the-middle attack. If the number of likely plaintexts can be enumerated -- say there are 2^m possibilities -- then we can crack the system with 2^{(n+m)/2} complexity. The idea is simple: for each likely plaintext s, we compute s*x^i for i=0,1,..,T-1, and store the result in a lookup table. I suggest using T = 2^{(n-m)/2}. Next, when we see a ciphertext t, we compute t/s^{j*T} for j=0,1,..,U-1, and look for the result in the lookup table. I suggest U = 2^n/T. This process suggests 2^m possibilities for (s,j); then if k is small enough, each possibility can be used to immediately suggest a potential key value which is tested by trial decryption; or alternatively, we may apply the process to two consecutive ciphertexts, and look for pairs (s,j) (s',j') such that s' seems likely to follow s. Many variations on this basic theme are probably possible. Neither of these ciphertext-only attacks are particularly efficient, but maybe with more effort better ciphertext-only attacks could be found. The cryptanalysis problem looks much harder when the taps to the main register are not known, or when multiple stages of this construction are applied with differently-tapped registers. Who knows? Maybe such an approach might prove secure, if sufficient care is taken.
Subject: Re: what cipher? Date: Sun, 06 Jun 1999 04:30:59 GMT From: "Douglas A. Gwyn" <DAGwyn@null.net> Message-ID: <3759F937.8F1CCF65@null.net> References: <7jc2bg$3lm$1@blowfish.isaac.cs.berkeley.edu> Newsgroups: sci.crypt Lines: 10 David Wagner wrote: > The cryptanalysis problem looks much harder when the taps to the main > register are not known, or when multiple stages of this construction > are applied with differently-tapped registers. Who knows? Maybe such > an approach might prove secure, if sufficient care is taken. Actually, LFSR isn't particularly secure, and the taps can be found, although I don't think the methodology has been published. I was instead referring to the further generalizations of the idea, such as nonlinear combinators.
Subject: Re: what cipher? Date: 8 Jun 1999 12:17:15 -0700 From: daw@blowfish.isaac.cs.berkeley.edu (David Wagner) Message-ID: <7jjq7r$5oe$1@blowfish.isaac.cs.berkeley.edu> References: <3759F937.8F1CCF65@null.net> Newsgroups: sci.crypt Lines: 26 In article <3759F937.8F1CCF65@null.net>, Douglas A. Gwyn <DAGwyn@null.net> wrote: > Actually, LFSR isn't particularly secure, and the taps can be found, > although I don't think the methodology has been published. I was > instead referring to the further generalizations of the idea, such > as nonlinear combinators. Interesting. By nonlinear combinator, I assume you mean a NLFSR (shift register with nonlinear feedback function)? Here is an interesting tie between stream ciphers and block ciphers. Suppose you take a NLFSR, use the plaintext as the initial fill, step it enough times to ensure avalanche, and output the register state as the ciphertext. (This is a nonlinear version of the Encyclopedia Britannica cipher.) Then this construction is equivalent to an unbalanced Feistel cipher whose round function is given by the NLFSR's nonlinear feedback function. Thus, I would claim that the "NLFSR" and the "unbalanced Feistel cipher" are, in some sense, just two ways to view the same object. One difficulty with the construction as I described it is that it has no round-dependence (e.g. no round subkeys), so it is vulnerable to a slide attack. This suggests that you should add some form of round dependence to the NLFSR, be it round counters (like in Skipjack), round subkeys, or whatever you like.
Subject: Re: what cipher? Date: Tue, 08 Jun 1999 22:11:30 GMT From: tomstdenis@my-deja.com Message-ID: <7jk4e9$24d$1@nnrp1.deja.com> References: <7jjq7r$5oe$1@blowfish.isaac.cs.berkeley.edu> Newsgroups: sci.crypt Lines: 15 Viewing the NLFSR as a UFN is a very good observation. I don't think encrypting bit per bit on any sort of general purpose process is a good idea. Most UFN are word oriented (CAST-256, MacGuffin, etc..) and are therefore a little faster. Is there any good description of using the LFSR or NLFSR as a encryption algorithm avail? What is the secret key the stepping count? (Timing attack) or the polynomial (timing again, and possibly power consumption in black boxes...) ? Tom Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't.
Subject: Re: what cipher? Date: Wed, 09 Jun 1999 04:40:39 GMT From: "Douglas A. Gwyn" <DAGwyn@null.net> Message-ID: <375DF002.E1379384@null.net> References: <7jjq7r$5oe$1@blowfish.isaac.cs.berkeley.edu> Newsgroups: sci.crypt Lines: 21 David Wagner wrote: > By nonlinear combinator, I assume you mean a NLFSR (shift register with > nonlinear feedback function)? Essentially. More usually called a combiner, come to think of it. There are several ways to wire up SR-based cryptosystems, but since I don't know of a public source for the information I can't describe them. Feel free to invent some. > Suppose you take a NLFSR, use the plaintext as the initial fill, ... > ... Thus, I would claim that the "NLFSR" and the "unbalanced Feistel > cipher" are, in some sense, just two ways to view the same object. Well, no, just the particular way you "wired up" that NLFSR system. Other ways of doing it wouldn't be equivalent. > ... This suggests that you should add some form of round > dependence to the NLFSR, be it round counters (like in Skipjack), ... No doubt, Skipjack's example of round dependence is a good security feature, and one can surmise that it was put there for a reason.
Subject: Re: what cipher? Date: 9 Jun 1999 14:00:47 -0700 From: daw@blowfish.isaac.cs.berkeley.edu (David Wagner) Message-ID: <7jmklv$6ht$1@blowfish.isaac.cs.berkeley.edu> References: <375DF002.E1379384@null.net> Newsgroups: sci.crypt Lines: 81 In article <375DF002.E1379384@null.net>, Douglas A. Gwyn <DAGwyn@null.net> wrote: > Essentially. More usually called a combiner, come to think of it. > There are several ways to wire up SR-based cryptosystems, but since > I don't know of a public source for the information I can't describe > them. Feel free to invent some. Ok. There's one example given at <http://jya.com/nsasuit2.txt> (scroll down to find the ASCII art) of a NSA SR-based cryptosystem. Since the design is (apparently) unclassified, I don't feel bad about discussing it here. Basically, you take an incoming data bit and xor it against an output bit from a 63-bit LFSR F; the resulting bit is xor-ed into a 14-bit NLFSR R; both registers are stepped multiple times (it's not entirely clear, but I'll assume they're stepped independently, with no feedback between them except when you enter a data bit); and then you repeat. The number of steps is classified (but may be 29, not that it matters much) and the nonlinear feedback function for R is classified. There are also some small extra details which I've omitted. The algorithm is used as a MAC. The output is the high order 10 bits of the R register, after all data bits have been processed. The key is the initial fill of the registers. This is an interesting design. If you try to squint funny at this until it looks like an unbalanced Feistel design, for instance, you see that the F register, for instance, prevents slide attacks by adding "round dependence" of a sort (think of the F register as a "key schedule"). The multiple stepping adds a lot of avalanche and also makes it look somewhat like a block cipher, and (probably more importantly) prevents you from getting access to "before" and "after" snapshots of the R register's feedback function by querying the algorithm with very short messages. One of the very interesting features of this design is that (like e.g. A5/1) it seems to require very few gates in hardware, which is great if you are in a resource-limited environment. I guess if I wanted to attack this and if I got to mount chosen-plaintext attacks (assuming I don't get to desynchronize the endpoints or "reset" the device to its initial key fill setting), I might try repeatedly asking for the MAC of the one-bit message "0". Without the F register, this would eventually reveal the transition diagram for the R register (after about 2^14 queries), and then additional messages can be easily forged. With the F register, I think you still might be able to get somewhere, with an even larger number of queries. Let's first consider a simplified version where the entire R register is revealed (not just its high 10 bits) and where the F register is stepped just once between data bits (but the R register is possibly stepped multiple times). By the birthday paradox, we expect to see some "matching" pairs of query outputs, where by a "match" I mean that two conditions hold: (1) the R register contents are the same for both queries, and (2) the next few bits of F output are the same at both locations. When you have such a match, the R register contents (i.e. the MAC output) for the next few subsequent queries will also match. This is a readily recognizable condition. Also, it gives you some information on the transition diagram for the R register, and perhaps more importantly, it gives you a few bits of information on the F register. With a few dozen such matches, you should be able to recover the F register contents and reduce the problem to one without a F register. I think the same attack can also be generalized to the case where just some of the R register is output. (You might need somewhat more queries, because you'll need longer "matches".) Also, stepping the F register multiple times doesn't really help, either, if you assume that the F register output is suppressed (i.e. doesn't affect the R register) during the multiple stepping process. This style of attack could be prevented (it seems) by maintaining the feedback from the F register to the R register even when no data bit is present, during the multiple stepping process. (This might already be part of the design -- it is hard to tell from the brief description in the above web page.) In any case, this style of attack may be relatively unrealistic, since such chosen-text attacks should be readily detectable by the receiver (if you assume that there is no way to desynchronize the endpoints or "reset" the tamperproof device without setting off alarms and zeroizing key material).
Subject: Re: what cipher? Date: 9 Jun 1999 14:11:20 -0700 From: daw@blowfish.isaac.cs.berkeley.edu (David Wagner) Message-ID: <7jml9o$6ih$1@blowfish.isaac.cs.berkeley.edu> References: <375DF002.E1379384@null.net> Newsgroups: sci.crypt Lines: 15 In article <375DF002.E1379384@null.net>, Douglas A. Gwyn <DAGwyn@null.net> wrote: > > Suppose you take a NLFSR, use the plaintext as the initial fill, ... > > ... Thus, I would claim that the "NLFSR" and the "unbalanced Feistel > > cipher" are, in some sense, just two ways to view the same object. > > Well, no, just the particular way you "wired up" that NLFSR system. > Other ways of doing it wouldn't be equivalent. Fair enough. It's probably because I'm most comfortable with block ciphers that I try to look at everything from that perspective, which is admittedly not a very good basis for making such claims. I guess in this case maybe I was trying to force a square peg into a round hole. Thanks for keeping me honest. Approved: billy-bob@bait-casting.example.org
Subject: Re: what cipher? Date: Wed, 09 Jun 1999 22:07:38 GMT From: mikea@okcforum.org Message-ID: <KAB73.566$CT1.750@news.flash.net> References: <3759F937.8F1CCF65@null.net> Newsgroups: sci.crypt Lines: 29 Douglas A. Gwyn <DAGwyn@null.net> wrote: : David Wagner wrote: :> The cryptanalysis problem looks much harder when the taps to the main :> register are not known, or when multiple stages of this construction :> are applied with differently-tapped registers. Who knows? Maybe such :> an approach might prove secure, if sufficient care is taken. : Actually, LFSR isn't particularly secure, and the taps can be found, : although I don't think the methodology has been published. I was : instead referring to the further generalizations of the idea, such : as nonlinear combinators. The methodology has been published more than a few times. IIRC, one such was in _Machine Cryptography_ (?) by Deavours and ?Kruh?. But it's blindingly obvious after just a little thought: it's a linear system, so all you need to do is solve linear equations in GF(2), using 2n bits of the unperturbed output bitstream from the LFSR. If you have no access to a guaranteed unperturbed bitstream, then you need to do more work (maybe 4n or 8n bits) to try to determine the coefficients (equivalent to tap positions) for the LFSR. Deavours and Kruh(?) don't cover this explicitly, but it's an obvious extension. -- Mike Andrews Tired old sysadmin mikea@okcforum.org
Subject: Re: what cipher? Date: Sat, 12 Jun 1999 02:28:36 GMT From: "Douglas A. Gwyn" <DAGwyn@null.net> Message-ID: <3761C593.9403315A@null.net> References: <KAB73.566$CT1.750@news.flash.net> Newsgroups: sci.crypt Lines: 6 mikea@okcforum.org wrote: > ... it's a linear system, so all you need to do is > solve linear equations in GF(2), using 2n bits of the > unperturbed output bitstream from the LFSR. You only have equations if you know the input stream.
Subject: Re: what cipher? Date: Thu, 03 Jun 1999 18:45:21 GMT From: bryan.olson@uptronics.com Message-ID: <7j6ig0$mpg$1@nnrp1.deja.com> References: <928372166.713.23@news.remarQ.com> Newsgroups: sci.crypt Lines: 50 Particle wrote: > I'm looking for a stream cipher, or a block cipher > that works in 8-bit intervals. (actually, I'm looking for > the algorithm, I'm planning on implementing it myself) > > It is very important that the ciphertext retain the length > of plain text. It has to be fast, and secure That's a little tricky. Can we assume a new key for each message, or enough extra space to store an IV? With zero extra storage, the same message under the same key always produces the same ciphertext. This allows "dictionary" attacks. [...] > it would also be nice to have a feature of not having > to decrypt all the text before a certain point (i.e.: so that > I can seek to the middle of the file, get what I need, > without ever touching the start) Supporting random access reads but not writes is easy. A block cipher in counter mode would work, as would the SEAL stream cipher and some others. Secure random access writes are tricky. Without extra storage space, there's no way to prevent the new data from using the same cipher+key+IV as the old data. An attacker who can see the same file at different times can gain information. Most solutions involve re-writing a large page (several kilobytes) even if only changing a bit. The secure solution is to include an IV in each page and change the IV on each write. Of course holding the IV means each ciphertext page is slightly larger than the plaintext. A less secure but often acceptable solution is to choose a cipher and mode such that any change effects a whole page. We might also use the offset of the page as an IV. The scheme still has the dictionary problem, but the large page tends to make the dictionary large, and the offset as IV means each page has its own dictionary. See Peter Gutmann's SFS for an example. --Bryan Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't. CC: bsptree@geocities.com
Subject: Re: what cipher? Date: Thu, 03 Jun 1999 15:02:42 -0600 From: John Myre <jmyre@sandia.gov> Message-ID: <3756ED72.51600A7D@sandia.gov> References: <928372166.713.23@news.remarQ.com> Newsgroups: sci.crypt Lines: 79 A really good answer to this question depends on other factors that have not yet been discussed, and on details of the actual application. If I were paying someone for their time to help with this, she would probably start by asking questions to clarify the problem. (The following rather long-winded discussion is really just an expansion of the above comment. Skip if I'm "preaching to the choir".) For example, it sounds to me as if the problem is to encrypt files (on disk) without changing their size, but perhaps this isn't everything? Do we want to encrypt data for communication, such as e-mail messages or perhaps even individual keystrokes? If encrypting files is the point, would a minimum file size (to match the block size of the chosen cipher) be an acceptable constraint? Or do we need to handle, say, files with just three bytes in them? And of course, sometimes we find we have overspecified the problem, anyway: it may be, for example, that encrypting an entire disk drive (rather than individual files) solves a problem in a simpler way. It just depends on the situation. Another broad class of questions would deal with the threat model. That is, to decide on a cryptographic system we need to decide what sorts of attacks to defend against, based on a (conservative) estimate of the powers and interests of the attackers. For example, do we assume that the attackers might be able to modify a disk file, so that we need some means of ensuring the data is authentic, or are we just worried about keeping the data secret? Various posts in this thread have given advice of one sort or another. Using OFB mode to create a stream cipher out of a block cipher certainly is useful in some situations. Similarly, data expansion may be easy to avoid or tricky, depending on other constraints. The thing to note is that to decide whether the advice is applicable means knowiwng more about your situation. Here in the newsgroup, just as for a one-on-one situation, the answers will be better when the question has more context. It just takes longer. And is sometimes more interesting... Particle wrote: > > I'm looking for a stream cipher, or a block cipher > that works in 8-bit intervals. (actually, I'm looking for > the algorithm, I'm planning on implementing it myself) > > It is very important that the ciphertext retain the length > of plain text. It has to be fast, and secure (preferably, > computationally secure). I would use a derivative of > RSA, but that's a bit slow. > > Oh, I'm willing to use keys upto 128 bits, which > will be totally randomly generated and secure from > intruders. > > it would also be nice to have a feature of not having > to decrypt all the text before a certain point (i.e.: so that > I can seek to the middle of the file, get what I need, > without ever touching the start) > > any ideas on a possible algorithm? > > please cc reply to my e-mail > thanks. > > -- > Particle > bsptree@geocities.com > http://www.geocities.com/SiliconValley/Way/7650 > Home of the Java Data Structures 2nd Edition.
Terry Ritter, his current address, and his top page.
Last updated: 2001-06-11