Can a newbie with an idea get a fair reception on sci.crypt? Apparently not.
First we have the idea that, instead of having a fixed amount of state, stream cipher RNG's can be made to use a variable amount of state. (To me, the term "variable" is quite distinct from, say, "selectable.") But because the guy does not use exactly the right crypto words to convey the idea, the whole thing is misinterpreted several different ways, with no follow-up apology found.
It is very common for a stream cipher design to have some way to fill RNG internal state from variable-length key phrases. It is also not unknown to support different-size RNG's in a cipher. But it is at least uncommon to allow the amount of RNG state -- that is, the structure of the RNG itself -- to vary during ciphering operations.
It seems particularly interesting to consider the use of many RNG's, in the sense of different "step" functions covering different parts and amounts of the available internal state. By selecting among these functions dynamically, during operation, the stream cipher system no longer has an obvious fixed RNG structure which may be attacked. The RNG is instead the possibility that any step function may occur at any time, which should vastly complicate any attack on the RNG state.
Now we need to discuss how such a thing could be done in detail. That would include how we could create a vast number of different RNG's (or step functions), functioning in a way that gives confidence about the strength of the result.
Subject: cryptanalysis of keystream cipher Date: 12 Sep 2001 09:30:57 -0700 From: aghosh@omnesys.com (Avik Ghosh) Message-ID: <ad48d0ad.0109120830.1ec94bb6@posting.google.com> Newsgroups: sci.crypt Lines: 37 Hello all, Why is it that keystream ciphers seeded with a variable sized key are not used much ? It seems that the reason most current ciphers are block ciphers is that stream ciphers can be derived from block ciphers, but not vice versa. I do not know if this is the only reason for the relative absence of stream ciphers. All block ciphers have a known fixed block size. However, keystream ciphers need not be restricted to having a fixed size seed. It is relatively simple to design an algorithm that takes a variable length string as the key and performs some non-linear operations on it to generate the next iteration. It could even take some past output and feed it in during this iteration phase. ( Output would be generated by just XORing with the input stream on a byte by byte basis ). I can understand that by doing this operation on a variable sized key and also using the output stream as seed data would make analysis difficult, and the strength unpredictable. But the very fact that one does not even know the key space makes brute force attacks theoretically impossible. In any case, analysis should be harder. Why is this scheme not used in practice ? I am a newcomer to this newsgroup. I could not find related questions in the archive - which implies that it is possible that this is a silly question. I apologize if that is so. In either case, I would really like to know. Avik.
Subject: Re: cryptanalysis of keystream cipher Date: Wed, 12 Sep 2001 16:33:28 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9no2oo$2c9v$1@agate.berkeley.edu> References: <ad48d0ad.0109120830.1ec94bb6@posting.google.com> Newsgroups: sci.crypt Lines: 11 Avik Ghosh wrote: >Why is it that keystream ciphers seeded with a variable sized key are >not used much ? Why would you want a variable sized key? 128 bits is sufficient to protect against exhaustive keysearch, so if you build a cipher where there are no shortcut attacks, I can't see any reason why you would want more than 128 or 256 bit keys. And, in any case, the size of your keys seems orthogonal to whether you use a block or stream cipher. Organisation: The Clue Factory
Subject: Re: cryptanalysis of keystream cipher Date: Fri, 14 Sep 2001 05:33:34 GMT From: Paul Crowley <paul@JUNKCATCHER.cluefactory.org.uk> Message-ID: <87iten4h12.fsf@saltationism.subnet.hedonism.cluefactory.org.uk> References: <9no2oo$2c9v$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 22 > Avik Ghosh wrote: > >Why is it that keystream ciphers seeded with a variable sized key are > >not used much ? Another note: there is active research in the open community into cryptographic pseudo-random number generators (CPRNGs), the primitive at the heart of Vernam (keystream) ciphers. Check out RC4, Panama, Leviathan, SEAL, WAKE-ROFB, and ISAAC for examples. These ciphers are all *much* faster than stream ciphers constructed from even the fastest block ciphers. However, several have security problems and others have seen insufficient cryptanalysis, so this area still needs more research. Google turns up Helger Lipmaa's excellent stream cipher page which covers most of the ciphers I've mentioned here. http://www.tcs.hut.fi/~helger/crypto/link/stream/index.html -- __ Paul Crowley \/ o\ sig@paul.cluefactory.org.uk /\__/ http://www.cluefactory.org.uk/paul/ "Conservation of angular momentum makes the world go around" - John Clark
Subject: Re: cryptanalysis of keystream cipher Date: Wed, 12 Sep 2001 18:50:37 GMT From: ritter@ciphersbyNOSPAMritter.com (Terry Ritter) Message-ID: <3b9fad8d.11268679@netnews.att.net> References: <ad48d0ad.0109120830.1ec94bb6@posting.google.com> Newsgroups: sci.crypt Lines: 155 On 12 Sep 2001 09:30:57 -0700, in <ad48d0ad.0109120830.1ec94bb6@posting.google.com>, in sci.crypt aghosh@omnesys.com (Avik Ghosh) wrote: >Hello all, > >Why is it that keystream ciphers seeded with a variable sized key are >not used much ? > >It seems that the reason most current ciphers are block ciphers is >that stream ciphers can be derived from block ciphers, but not vice >versa. I do not know if this is the only reason for the relative >absence of stream ciphers. Stream ciphers are not "absent," they are just "hidden." The military has used (and I assume still uses) them extensively. It is instead academia which is in love with the particular form of block cipher we all know so well. Even though conventional academic block ciphers do seek to emulate huge Simple Substitutions, not all block ciphers do that. See, for example: http://www.ciphersbyritter.com/ARTS/DYNTRAGN.HTM If we see "streaming" as a sequence of "block" transformations, then stream ciphers must be based on "blocks." But what we normally call "stream ciphers" will have "block" sizes of a bit or a byte, so these transformations are not conventional block ciphers, and are probably not even Simple Substitutions. In that sense, most real stream ciphers are not derived from conventional block ciphers. See, for example: http://www.ciphersbyritter.com/CLO2DESN.HTM On the other hand, conventional block ciphers are almost always used in stream-like "operating modes" like CBC. The result makes sense when seen as stream meta-cipher based on a conventional block cipher transformation. So, mostly we do use stream ciphers. >All block ciphers have a known fixed block size. No they don't. All block ciphers have a particular block size at any particular time, but need not have a fixed block size over all time. Some designs allow blocks to vary in size throughout a message (see, for example: http://www.ciphersbyritter.com/NEWS/96021101.HTM ) although conventional block ciphers, of course, cannot. That is also a scalability problem, which means that academic block ciphers cannot be scaled down to toy size which can be exhaustively investigated experimentally. >However, keystream ciphers need not be restricted to having a fixed >size seed. It is relatively simple to design an algorithm that takes a >variable length string as the key and performs some non-linear >operations on it to generate the next iteration. I think this is saying that we can build pseudorandom number generators (RNG's) which have a variable-size seed or state. That is an interesting insight, and am unaware of any such work, or any attempt to capitalize on such a property. Certainly there is little problem building RNG's with an internal state of any general size. >It could even take >some past output and feed it in during this iteration phase. If the "past output" is ciphertext, we may have what is generally called an "autokey" cipher. >( Output >would be generated by just XORing with the input stream on a byte by >byte basis ). Whole different classes of "stream cipher" do not just use XOR or other additive combining. XOR is a strengthless special case of a Latin square combiner, which can be keyed. See, for example: http://www.ciphersbyritter.com/NEWS5/LATSQCMB.HTM >I can understand that by doing this operation on a variable sized key >and also using the output stream as seed data would make analysis >difficult, and the strength unpredictable. It would be important to find a practical construction in which some things can be said about the result, given size as a parameter. That is essentially the "scalability" issue. One example would be the Blum, Blum and Shub (BB&S) generator, which does have a security proof, but is far too slow for any real use protecting data. >But the very fact that one does not even know the key space makes >brute force attacks theoretically impossible. In any case, analysis >should be harder. While not knowing the keyspace might make brute force attacks difficult, with a "large enough" keyspace, brute force attacks are already impractical. I think the issue here is that parameterizing the RNG is essentially another type of "keying." One might imagine somehow deducing the key from various uses of an RNG of particular construction, but if we have a plethora of *different* constructions which change dynamically, it would seem to be hard to use any exposed sequence to expose "the key" or predict the future of the sequence. >Why is this scheme not used in practice ? First of all, the approach seems new, and a lot depends upon implementation. It could be an idea that we just don't know how to accomplish right now. In any case, academics seem most comfortable with conventional block ciphers, and perhaps can more clearly see progress there, and so tend to concentrate their attention on that type of cipher. The common academic view seems to be that the world does not need new ciphers, it instead needs just one conventional block cipher of mathematically-provable strength (which I expect is impossible). But since we do *not* have the needed provably secure block cipher, accepting a single standard cipher for common use seems particularly risky approach for society. Unfortunately, nobody really cares about risk. Another factor affecting "use in practice" is that many ciphers are available free, which thus limits the reward for the research and development needed to produce and have confidence in new and different ciphering approaches. By not establishing a for-pay industry of cipher development, society is forced to rely upon ciphers produced and analyzed "for free," typically by academics (who are, of course, paid). >I am a newcomer to this newsgroup. I could not find related questions >in the archive - which implies that it is possible that this is a >silly question. >I apologize if that is so. > >In either case, I would really like to know. > >Avik. --- Terry Ritter www.ciphersbyritter.com/ Crypto Glossary www.ciphersbyritter.com/GLOSSARY.HTM
Subject: Re: cryptanalysis of keystream cipher Date: Wed, 12 Sep 2001 19:52:42 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9noeea$2jcp$1@agate.berkeley.edu> References: <3b9fad8d.11268679@netnews.att.net> Newsgroups: sci.crypt Lines: 14 Terry Ritter wrote: >I think this is saying that we can build pseudorandom number >generators (RNG's) which have a variable-size seed or state. That is >an interesting insight, and am unaware of any such work, or any >attempt to capitalize on such a property. > >Certainly there is little problem building RNG's with an internal >state of any general size. I agree. It should be easy to do so securely. (For instance, use a Merkle hash tree to shrink down to a fixed size seed, then apply any standard PRG.) However, there seems to be no motivation to consider such a construction; fully variable-size keys do not seem to offer any advantages worth bothering with.
Subject: Re: cryptanalysis of keystream cipher Date: Wed, 12 Sep 2001 22:05:09 GMT From: ritter@ciphersbyNOSPAMritter.com (Terry Ritter) Message-ID: <3b9fdc12.23178590@netnews.att.net> References: <9noeea$2jcp$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 36 On Wed, 12 Sep 2001 19:52:42 +0000 (UTC), in <9noeea$2jcp$1@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>I think this is saying that we can build pseudorandom number >>generators (RNG's) which have a variable-size seed or state. That is >>an interesting insight, and am unaware of any such work, or any >>attempt to capitalize on such a property. >> >>Certainly there is little problem building RNG's with an internal >>state of any general size. > >I agree. It should be easy to do so securely. (For instance, use a >Merkle hash tree to shrink down to a fixed size seed, then apply any >standard PRG.) However, there seems to be no motivation to consider >such a construction; fully variable-size keys do not seem to offer any >advantages worth bothering with. Oddly, I gave such advantages in the parts you deleted. Dynamically changing the structure of the RNG means that the RNG is more difficult to attack in practice. When it is possible to select among a multitude of different RNG structures, the opponents do not know *which* RNG is operating. That makes the usual attack on a specific structure and design somewhat more complex. The real issue is whether it is first *possible* and then *practical* to parameterize a plethora of structural differences, which all produce acceptable RNG's yet require generally different attacks. --- Terry Ritter www.ciphersbyritter.com/ Crypto Glossary www.ciphersbyritter.com/GLOSSARY.HTM
Subject: Re: cryptanalysis of keystream cipher Date: Thu, 13 Sep 2001 00:39:34 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9nov86$2u3l$1@agate.berkeley.edu> References: <3b9fdc12.23178590@netnews.att.net> Newsgroups: sci.crypt Lines: 16 Terry Ritter wrote: >Dynamically changing the structure of the RNG means that the RNG is >more difficult to attack in practice. Do you mean dynamically changing the key size makes it more difficult to attack in practice? If so, I am skeptical; do you have a proof of this? If this is not what you meant, could you elaborate? Finally, I'll make a prediction: I bet we can prove that the existence of a secure variable-key-length cipher implies the existence of a secure fixed-key-length cipher. I haven't undertaken to write down such a proof, but I bet we could do it if it seemed important. If this is correct, I find it hard to understand what the claimed advantage of either would be. (Maybe this helps explain why I can't see any motivation for exploring variable-key-length ciphers.)
Subject: Re: cryptanalysis of keystream cipher Date: Thu, 13 Sep 2001 00:49:55 GMT From: ritter@ciphersbyNOSPAMritter.com (Terry Ritter) Message-ID: <3ba00208.32898182@netnews.att.net> References: <9nov86$2u3l$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 46 On Thu, 13 Sep 2001 00:39:34 +0000 (UTC), in <9nov86$2u3l$1@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>Dynamically changing the structure of the RNG means that the RNG is >>more difficult to attack in practice. > >Do you mean dynamically changing the key size makes it more difficult to >attack in practice? No. I mean that dynamically changing the structure of the RNG means that the RNG is more difficult to attack in practice. >If so, I am skeptical; do you have a proof of this? > >If this is not what you meant, could you elaborate? This is similar to using many different ciphers and selecting from among those in a key-selected way. It makes practical attacks more difficult because there is no one fixed structure to attack. As a result, there are no fixed peculiarities which can be exploited. There is no guaranteed weakness, even if one of the structures is known to be weak, because of the low probability the cipher uses the weak structure. >Finally, I'll make a prediction: I bet we can prove that the existence >of a secure variable-key-length cipher implies the existence of a secure >fixed-key-length cipher. This is PRACTICAL security, not theory. >I haven't undertaken to write down such a proof, >but I bet we could do it if it seemed important. If this is correct, I >find it hard to understand what the claimed advantage of either would be. >(Maybe this helps explain why I can't see any motivation for exploring >variable-key-length ciphers.) Or there may be an alternate explanation. --- Terry Ritter www.ciphersbyritter.com/ Crypto Glossary www.ciphersbyritter.com/GLOSSARY.HTM
Subject: Re: cryptanalysis of keystream cipher Date: Thu, 13 Sep 2001 02:55:45 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9np77h$1nb$1@agate.berkeley.edu> References: <3ba00208.32898182@netnews.att.net> Newsgroups: sci.crypt Lines: 10 Terry Ritter wrote: >daw@mozart.cs.berkeley.edu (David Wagner) wrote: >>Do you mean dynamically changing the key size makes it more difficult to >>attack in practice? > >No. I mean that dynamically changing the structure of the RNG means >that the RNG is more difficult to attack in practice. Does this have anything to do with variable-size keys? I can't see much relation, but maybe I'm missing something.
Subject: Re: cryptanalysis of keystream cipher Date: Thu, 13 Sep 2001 04:35:30 GMT From: ritter@ciphersbyNOSPAMritter.com (Terry Ritter) Message-ID: <3ba036d0.46411320@netnews.att.net> References: <9np77h$1nb$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 54 On Thu, 13 Sep 2001 02:55:45 +0000 (UTC), in <9np77h$1nb$1@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>daw@mozart.cs.berkeley.edu (David Wagner) wrote: >>>Do you mean dynamically changing the key size makes it more difficult to >>>attack in practice? >> >>No. I mean that dynamically changing the structure of the RNG means >>that the RNG is more difficult to attack in practice. > >Does this have anything to do with variable-size keys? Probably not the way *you* interpret "variable-size keys." >I can't see much relation, but maybe I'm missing something. Apparently you are. The source is a newbie who does not know the technical implications or the language of cryptography. It is thus necessary to interpret his words. Here are some quotes from the original message: ". . . keystream ciphers need not be restricted to having a fixed size seed." Here, "keystream ciphers" == "conventional stream ciphers," obviously. "It is relatively simple to design an algorithm that takes a variable length string as the key and performs some non-linear operations on it to generate the next iteration." My interpretation is: "variable length string as the key" == "variable size RNG state." He clearly is talking about building RNG's for stream ciphers such that variable amounts of state are involved in the RNG. The amount of state would be a parameter affecting the RNG design and in addition to the simple value of the state, which is normally the only parameter to an RNG. As an extension, one might consider more substantial and dynamic RNG changes as well; in the limit, one might switch between RNG designs dynamically during operation. That should complicate any attack on "the" generator (since there would *be* no fixed generator) even assuming the RNG keying stream is exposed (which need not happen with keyed Latin square or Dynamic Substitution combiners). --- Terry Ritter www.ciphersbyritter.com/ Crypto Glossary www.ciphersbyritter.com/GLOSSARY.HTM
Subject: Re: cryptanalysis of keystream cipher Date: Thu, 13 Sep 2001 10:06:38 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3BA0690E.3BBEBC41@t-online.de> References: <3ba036d0.46411320@netnews.att.net> Newsgroups: sci.crypt Lines: 24 Terry Ritter wrote: > [skip] > As an extension, one might consider more substantial and dynamic RNG > changes as well; in the limit, one might switch between RNG designs > dynamically during operation. That should complicate any attack on > "the" generator (since there would *be* no fixed generator) even > assuming the RNG keying stream is exposed (which need not happen with > keyed Latin square or Dynamic Substitution combiners). One thing that I did in that direction in my WEAK3-EX is to let some hash values obtained at intervals during the encryption processing to determine the number of elements of the stream of pseudo-random numbers from my compound PRNG that are to be skipped, thus through this 'feedback' achieve plaintext dependence, i.e. different output sequences from the compound PRNG are used for different plaintexts. M. K. Shen ----------------------- http://home.t-online.de/home/mok-kong.shen
Subject: Re: cryptanalysis of keystream cipher Date: Thu, 13 Sep 2001 10:28:43 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3BA06E3B.ED2CA3BD@t-online.de> References: <3ba00208.32898182@netnews.att.net> Newsgroups: sci.crypt Lines: 43 Terry Ritter wrote: > > daw@mozart.cs.berkeley.edu (David Wagner) wrote: > > >Terry Ritter wrote: > >>Dynamically changing the structure of the RNG means that the RNG is > >>more difficult to attack in practice. > > > >Do you mean dynamically changing the key size makes it more difficult to > >attack in practice? > > No. I mean that dynamically changing the structure of the RNG means > that the RNG is more difficult to attack in practice. I believe that this is certainly true. > >If so, I am skeptical; do you have a proof of this? > > > >If this is not what you meant, could you elaborate? > > This is similar to using many different ciphers and selecting from > among those in a key-selected way. It makes practical attacks more > difficult because there is no one fixed structure to attack. As a > result, there are no fixed peculiarities which can be exploited. > There is no guaranteed weakness, even if one of the structures is > known to be weak, because of the low probability the cipher uses the > weak structure. I like to mention that the design of my compound PRNG was motivated principally by that consideration. For there are in it an arbitrarily (user chosen, large) number of constituent PRNGs and these are activated pseudo-randomly (order being determined by the 'internal' outputs of these themselves) so that those attacks based on the fact that the numbers of the sequence in the hand of the opponent are sequentially obtained from one or a couple of PRNGs can't work. M. K. Shen ------------------------- http://home.t-online.de/home/mok-kong.shen
Subject: Re: cryptanalysis of keystream cipher Date: Thu, 13 Sep 2001 10:36:01 -0400 From: Shai Halevi <shaih@watson.ibm.com> Message-ID: <3BA0C451.90DC5A0E@watson.ibm.com> References: <9nov86$2u3l$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 23 David Wagner wrote: > Finally, I'll make a prediction: I bet we can prove that the existence > of a secure variable-key-length cipher implies the existence of a secure > fixed-key-length cipher. [...] Well, you would have to define exactly what a "variable-key-length cipher" is. The most straightforward interpretation of "variable" is "parametrized" (e.g., Rijndael-128, Rijnael-192, Rijndael-256). Under this interpretation, your security is a function of your key-size, and this is just the standard definition of a cipher (more precisely, a pseudorandom-function-family). Alternatively, you may want to talk about a pseudorandom-generator (aka stream cipher) that takes a seed of any length, n, and produces a stream of length >= n+1. Again, this is one of the standard definitions of PRGs. In terms of existence, these are all equivalent to one-way functions, and so they are all equivalent to one another. -- Shai
Subject: Re: cryptanalysis of keystream cipher Date: Wed, 12 Sep 2001 22:10:23 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B9FC12F.129D788C@t-online.de> References: <3b9fad8d.11268679@netnews.att.net> Newsgroups: sci.crypt Lines: 34 Terry Ritter wrote: > > aghosh@omnesys.com (Avik Ghosh) wrote: [snip] > >However, keystream ciphers need not be restricted to having a fixed > >size seed. It is relatively simple to design an algorithm that takes a > >variable length string as the key and performs some non-linear > >operations on it to generate the next iteration. > > I think this is saying that we can build pseudorandom number > generators (RNG's) which have a variable-size seed or state. That is > an interesting insight, and am unaware of any such work, or any > attempt to capitalize on such a property. > > Certainly there is little problem building RNG's with an internal > state of any general size. I designed a compound PRNG using one PRNG to accept an arbitrary number of seeds to generate the parameters of an arbitrary number of constituent PRNGs which are activated in a pseudo-random order. See my web page. Note that the constituent PRNGs may be of any type, linear or non-linear, though in the actual code given in the web page they are LCPRNGs. Further, in the actual code there, only a constant size (very small) seed of 56 bits is allowed. This was done in order to have the code conform to the restrictions as those required by the crypto clauses of the Wassenaar Arrangements. M. K. Shen -------------------------- http://home.t-online.de/home/mok-kong.shen
Subject: Re: cryptanalysis of keystream cipher Date: 12 Sep 2001 20:08:58 -0700 From: aghosh@omnesys.com (Avik Ghosh) Message-ID: <ad48d0ad.0109121908.1f14c609@posting.google.com> References: <3b9fad8d.11268679@netnews.att.net> Newsgroups: sci.crypt Lines: 162 Thanks very much. You have provided a lot for me to think about ( and also abandon ! ). Thanks again for your detailed reply. Avik. ritter@ciphersbyNOSPAMritter.com (Terry Ritter) wrote in message news:<3b9fad8d.11268679@netnews.att.net>... > On 12 Sep 2001 09:30:57 -0700, in > <ad48d0ad.0109120830.1ec94bb6@posting.google.com>, in sci.crypt > aghosh@omnesys.com (Avik Ghosh) wrote: > > >Hello all, > > > >Why is it that keystream ciphers seeded with a variable sized key are > >not used much ? > > > >It seems that the reason most current ciphers are block ciphers is > >that stream ciphers can be derived from block ciphers, but not vice > >versa. I do not know if this is the only reason for the relative > >absence of stream ciphers. > > Stream ciphers are not "absent," they are just "hidden." The military > has used (and I assume still uses) them extensively. It is instead > academia which is in love with the particular form of block cipher we > all know so well. Even though conventional academic block ciphers do > seek to emulate huge Simple Substitutions, not all block ciphers do > that. See, for example: > > http://www.ciphersbyritter.com/ARTS/DYNTRAGN.HTM > > If we see "streaming" as a sequence of "block" transformations, then > stream ciphers must be based on "blocks." But what we normally call > "stream ciphers" will have "block" sizes of a bit or a byte, so these > transformations are not conventional block ciphers, and are probably > not even Simple Substitutions. In that sense, most real stream > ciphers are not derived from conventional block ciphers. See, for > example: > > http://www.ciphersbyritter.com/CLO2DESN.HTM > > On the other hand, conventional block ciphers are almost always used > in stream-like "operating modes" like CBC. The result makes sense > when seen as stream meta-cipher based on a conventional block cipher > transformation. So, mostly we do use stream ciphers. > > > >All block ciphers have a known fixed block size. > > No they don't. All block ciphers have a particular block size at any > particular time, but need not have a fixed block size over all time. > Some designs allow blocks to vary in size throughout a message (see, > for example: > > http://www.ciphersbyritter.com/NEWS/96021101.HTM > > ) although conventional block ciphers, of course, cannot. That is > also a scalability problem, which means that academic block ciphers > cannot be scaled down to toy size which can be exhaustively > investigated experimentally. > > > >However, keystream ciphers need not be restricted to having a fixed > >size seed. It is relatively simple to design an algorithm that takes a > >variable length string as the key and performs some non-linear > >operations on it to generate the next iteration. > > I think this is saying that we can build pseudorandom number > generators (RNG's) which have a variable-size seed or state. That is > an interesting insight, and am unaware of any such work, or any > attempt to capitalize on such a property. > > Certainly there is little problem building RNG's with an internal > state of any general size. > > > >It could even take > >some past output and feed it in during this iteration phase. > > If the "past output" is ciphertext, we may have what is generally > called an "autokey" cipher. > > > >( Output > >would be generated by just XORing with the input stream on a byte by > >byte basis ). > > Whole different classes of "stream cipher" do not just use XOR or > other additive combining. XOR is a strengthless special case of a > Latin square combiner, which can be keyed. See, for example: > > http://www.ciphersbyritter.com/NEWS5/LATSQCMB.HTM > > > >I can understand that by doing this operation on a variable sized key > >and also using the output stream as seed data would make analysis > >difficult, and the strength unpredictable. > > It would be important to find a practical construction in which some > things can be said about the result, given size as a parameter. That > is essentially the "scalability" issue. One example would be the > Blum, Blum and Shub (BB&S) generator, which does have a security > proof, but is far too slow for any real use protecting data. > > > >But the very fact that one does not even know the key space makes > >brute force attacks theoretically impossible. In any case, analysis > >should be harder. > > While not knowing the keyspace might make brute force attacks > difficult, with a "large enough" keyspace, brute force attacks are > already impractical. > > I think the issue here is that parameterizing the RNG is essentially > another type of "keying." One might imagine somehow deducing the key > from various uses of an RNG of particular construction, but if we have > a plethora of *different* constructions which change dynamically, it > would seem to be hard to use any exposed sequence to expose "the key" > or predict the future of the sequence. > > > >Why is this scheme not used in practice ? > > First of all, the approach seems new, and a lot depends upon > implementation. It could be an idea that we just don't know how to > accomplish right now. > > In any case, academics seem most comfortable with conventional block > ciphers, and perhaps can more clearly see progress there, and so tend > to concentrate their attention on that type of cipher. > > The common academic view seems to be that the world does not need new > ciphers, it instead needs just one conventional block cipher of > mathematically-provable strength (which I expect is impossible). > > But since we do *not* have the needed provably secure block cipher, > accepting a single standard cipher for common use seems particularly > risky approach for society. Unfortunately, nobody really cares about > risk. > > Another factor affecting "use in practice" is that many ciphers are > available free, which thus limits the reward for the research and > development needed to produce and have confidence in new and different > ciphering approaches. By not establishing a for-pay industry of > cipher development, society is forced to rely upon ciphers produced > and analyzed "for free," typically by academics (who are, of course, > paid). > > > >I am a newcomer to this newsgroup. I could not find related questions > >in the archive - which implies that it is possible that this is a > >silly question. > >I apologize if that is so. > > > >In either case, I would really like to know. > > > >Avik. > > --- > Terry Ritter www.ciphersbyritter.com/ > Crypto Glossary www.ciphersbyritter.com/GLOSSARY.HTM
Subject: Re: cryptanalysis of keystream cipher Date: 12 Sep 2001 18:15:07 -0700 From: bryanjugglercryptographer@yahoo.com (Bryan Olson) Message-ID: <1a517b5.0109121715.3f2c96dc@posting.google.com> References: <ad48d0ad.0109120830.1ec94bb6@posting.google.com> Newsgroups: sci.crypt Lines: 19 Avik Ghosh wrote: [...] > But the very fact that one does not even know the key space makes > brute force attacks theoretically impossible. I think there's a definite error in that logic. Any key we actually use is of some fixed, finite size. The distribution that protects us it the one from which our keys are actually drawn, and that must assign some fixed, non-zero probability to each possible key. To minimize the number of trial decryptions in a brute-force search, the attacker wants to try keys in most-likely-first order. Thus the defender should choose keys so as to minimize the probability of the most likely key(s). Choosing uniformly from fixed-size keys is as good as it gets. --Bryan
Subject: Re: cryptanalysis of keystream cipher Date: Thu, 13 Sep 2001 10:37:46 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3BA0705A.7192F44F@t-online.de> References: <1a517b5.0109121715.3f2c96dc@posting.google.com> Newsgroups: sci.crypt Lines: 29 Bryan Olson wrote: > > Avik Ghosh wrote: > > [...] > > But the very fact that one does not even know the key space makes > > brute force attacks theoretically impossible. > > I think there's a definite error in that logic. Any key we actually use > is of some fixed, finite size. The distribution that protects us it the > one from which our keys are actually drawn, and that must assign some > fixed, non-zero probability to each possible key. > > To minimize the number of trial decryptions in a brute-force search, the > attacker wants to try keys in most-likely-first order. Thus the > defender should choose keys so as to minimize the probability of the > most likely key(s). Choosing uniformly from fixed-size keys is as good > as it gets. If I didn't misunderstand Avik Ghosh, he meant using a PRNG where the user can decide how much seed material is to be used, much like a block cipher that has variable (user choosable) number of rounds. M. K. Shen --------------------------- http://home.t-online.de/home/mok-kong.shen
Subject: Re: cryptanalysis of keystream cipher Date: 13 Sep 2001 13:53:01 -0700 From: bryanjugglercryptographer@yahoo.com (Bryan Olson) Message-ID: <1a517b5.0109131253.5c735bb4@posting.google.com> References: <3BA0705A.7192F44F@t-online.de> Newsgroups: sci.crypt Lines: 14 Mok-Kong Shen wrote: > If I didn't misunderstand Avik Ghosh, he meant using > a PRNG where the user can decide how much seed material > is to be used, much like a block cipher that has variable > (user choosable) number of rounds. Yes, that was my reading too (though a variable size key is very different from a variable number of rounds). He went on to postulate that the property made it invulnerable to exhaustive search, and that is not true. --Bryan
Subject: Re: cryptanalysis of keystream cipher Date: 13 Sep 2001 05:41:41 -0700 From: aghosh@omnesys.com (Avik Ghosh) Message-ID: <ad48d0ad.0109130441.fd829e6@posting.google.com> References: <1a517b5.0109121715.3f2c96dc@posting.google.com> Newsgroups: sci.crypt Lines: 48 bryanjugglercryptographer@yahoo.com (Bryan Olson) wrote in message news:<1a517b5.0109121715.3f2c96dc@posting.google.com>... > Avik Ghosh wrote: > > [...] > > But the very fact that one does not even know the key space makes > > brute force attacks theoretically impossible. > > I think there's a definite error in that logic. Any key we actually use > is of some fixed, finite size. The distribution that protects us it the > one from which our keys are actually drawn, and that must assign some > fixed, non-zero probability to each possible key. > > To minimize the number of trial decryptions in a brute-force search, the > attacker wants to try keys in most-likely-first order. Thus the > defender should choose keys so as to minimize the probability of the > most likely key(s). Choosing uniformly from fixed-size keys is as good > as it gets. > > I had not realized that 128 bits are considered large enough to be unbreakable. My point was that one should be able to give the user an option of choosing a much larger key ( in the limit it would become a one time pad ). The iterations that provide the rest of the keystream could then be less computation-intensive than that of standard block ciphers. As Terry has pointed out, I am not familiar with the technical language. Just to make it clear, here is what I had proposed : 1. Start with a variable sized key. 2. Output the cipher text by combining it modulo 256 with the same length of plaintext. 3. Then combine the ciphertext that was just generated along with the existing key of generation 0 with some non-linear operations to get generation 1. 4. Repeat steps 2 and 3 as many times as required until all plaintext has been consumed. Avik. > --Bryan
Subject: Re: cryptanalysis of keystream cipher Date: 13 Sep 2001 14:13:45 -0700 From: bryanjugglercryptographer@yahoo.com (Bryan Olson) Message-ID: <1a517b5.0109131313.278d6807@posting.google.com> References: <ad48d0ad.0109130441.fd829e6@posting.google.com> Newsgroups: sci.crypt Lines: 24 Avik Ghosh wrote: > My point was that one should be able to give the user an option of > choosing a much larger key ( in the limit it would become a one time > pad ). I didn't take any position on that point. You also suggested that allowing arbitrary size keys makes brute force attack impossible, and that's what I tried to show false. Searching the entire keyspace that the algorithm allows may be impossible, but for any particular key, searching until one finds it takes finite time. Many PRNG's do allow variable size-keys, but usually impose some reasonable limit. Examples that are actually in use include the FIPS-186 generator and RC4. AES will support keys of 128, 192, and 256 bits. I think the 192-bit option is silly - no one needs that level of granularity. While I like different options in principle, I dread the amount of time and effort sure to be wasted in determining proper AES key sizes for various enterprises and applications. --Bryan
Subject: Re: cryptanalysis of keystream cipher Date: 13 Sep 2001 14:33:15 -0700 From: ggr@qualcomm.com (Gregory G Rose) Message-ID: <9nr8mr$jvr@qualcomm.com> References: <1a517b5.0109131313.278d6807@posting.google.com> Newsgroups: sci.crypt Lines: 31 In article <1a517b5.0109131313.278d6807@posting.google.com>, Bryan Olson <bryanjugglercryptographer@yahoo.com> wrote: >Avik Ghosh wrote: >I didn't take any position on that point. You also suggested that >allowing arbitrary size keys makes brute force attack impossible, and >that's what I tried to show false. Searching the entire keyspace that >the algorithm allows may be impossible, but for any particular key, >searching until one finds it takes finite time. Your argument is flawed, since it applies equally well to the proven information-theoretically secure one time pad. The point is that searching all the keys is possible, what is impossible is determining the correct answer. Now, theoretically this other algorithm might (or might not) share the characteristic. But if the message length is N bits, and the key length is N bits, the will be some number M, M <= 2^N, of possible valid decryptions. If equality holds, you're back to the same proof of security. If it doesn't hold, the cipher might still be practically unbreakable. It's all a question of Unicity Distance, and that *does* depend on the key length. Greg. -- Greg Rose INTERNET: ggr@qualcomm.com Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Subject: Re: cryptanalysis of keystream cipher Date: Thu, 13 Sep 2001 21:37:08 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9nr8u4$vu1$1@agate.berkeley.edu> References: <9nr8mr$jvr@qualcomm.com> Newsgroups: sci.crypt Lines: 13 Gregory G Rose wrote: >But if the message length is >N bits, and the key length is N bits, the will be >some number M, M <= 2^N, of possible valid >decryptions. If equality holds, you're back to the >same proof of security. If it doesn't hold, the >cipher might still be practically unbreakable. Right. So the proposal is either secure but impractical (just like the one-time pad) or practical but susceptible to exhaustive keysearch (just like almost all modern ciphers). In other words, the variable key size proposal seems to offer no advantage over existing approaches in this respect.
Subject: Re: cryptanalysis of keystream cipher Date: Fri, 14 Sep 2001 00:22:19 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3BA1319B.C062EBEC@t-online.de> References: <9nr8u4$vu1$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 23 David Wagner wrote: > > Gregory G Rose wrote: > >But if the message length is > >N bits, and the key length is N bits, the will be > >some number M, M <= 2^N, of possible valid > >decryptions. If equality holds, you're back to the > >same proof of security. If it doesn't hold, the > >cipher might still be practically unbreakable. > > Right. So the proposal is either secure but impractical (just like > the one-time pad) or practical but susceptible to exhaustive keysearch > (just like almost all modern ciphers). In other words, the variable > key size proposal seems to offer no advantage over existing approaches > in this respect. However, it is an additional approach for the repertoire of what you consider as existing approaches. Its presence can't hurt in my humble view. M. K. Shen
Subject: Re: cryptanalysis of keystream cipher Date: Fri, 14 Sep 2001 06:50:21 GMT From: ritter@ciphersbyNOSPAMritter.com (Terry Ritter) Message-ID: <3ba1a8a8.55196359@netnews.att.net> References: <9nr8u4$vu1$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 72 On Thu, 13 Sep 2001 21:37:08 +0000 (UTC), in <9nr8u4$vu1$1@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Gregory G Rose wrote: >>But if the message length is >>N bits, and the key length is N bits, the will be >>some number M, M <= 2^N, of possible valid >>decryptions. If equality holds, you're back to the >>same proof of security. If it doesn't hold, the >>cipher might still be practically unbreakable. > >Right. So the proposal is either secure but impractical (just like >the one-time pad) It is not yet known whether it is or is not practical to get substantial parameterized variation in RNG structure. But it may well be practical. It is far too early for an authoritative Opinion that such a thing either cannot exist or would be useless if it did. No real OTP implementation of any sort is provably "secure" in practice. But what makes OTP's generally *impractical* is the size of their keying material, and the continuing need to create, transport, and hold keying material, all in absolute security. But none of that applies to the conventional stream ciphers as being discussed here. So the fact that OTP's are impractical is not relevant. Current stream ciphers generally manage to make do with a single RNG structure for each. But if one could have confidence in multiple different RNG structures, key-selecting any of those should be acceptable. If a stream cipher does key-select one from among many different possible RNG's, that would require the opponent to consider each possible alternative when trying to reconstruct the internal state of the RNG. For a fixed small number of RNG structures which are chosen and then used through an entire message, that would not provide much security advantage. But there need not be just a small number of RNG's, that number need not be fixed, and RNG changes could be made dynamically, during operation. It is this last possibility which could pay significant security dividends. If increasing numbers of RNG structures do become available, and the RNG is changed dynamically during operation, RNG state reconstruction by opponents might be made impractical. The result could well be a real gain in practical strength at minimal execution cost. >or practical but susceptible to exhaustive keysearch >(just like almost all modern ciphers). But, in practice, modern key-based ciphers use "large enough" keys and so are *not* "susceptible to exhaustive keysearch." >In other words, the variable >key size proposal seems to offer no advantage over existing approaches >in this respect. The obvious potential advantage is to complicate attacks on the RNG state. Since attacks on RNG state are the obvious route to breaking conventional stream ciphers, making those harder could produce an actual increase in strength. That would seem to be a very reasonable "advantage" indeed. --- Terry Ritter www.ciphersbyritter.com/ Crypto Glossary www.ciphersbyritter.com/GLOSSARY.HTM
Subject: Re: cryptanalysis of keystream cipher Date: Fri, 14 Sep 2001 10:34:58 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3BA1C132.44050306@t-online.de> References: <3ba1a8a8.55196359@netnews.att.net> Newsgroups: sci.crypt Lines: 73 Terry Ritter wrote: > [snip] > Current stream ciphers generally manage to make do with a single RNG > structure for each. But if one could have confidence in multiple > different RNG structures, key-selecting any of those should be > acceptable. > > If a stream cipher does key-select one from among many different > possible RNG's, that would require the opponent to consider each > possible alternative when trying to reconstruct the internal state of > the RNG. For a fixed small number of RNG structures which are chosen > and then used through an entire message, that would not provide much > security advantage. But there need not be just a small number of > RNG's, that number need not be fixed, and RNG changes could be made > dynamically, during operation. It is this last possibility which > could pay significant security dividends. > > If increasing numbers of RNG structures do become available, and the > RNG is changed dynamically during operation, RNG state reconstruction > by opponents might be made impractical. The result could well be a > real gain in practical strength at minimal execution cost. I fully agree with this. My compound PRNG (see my web page) was in fact designed with such conisderations in mind. The user can choose the size of seed and the number of constituent PRNGs that are activated psuedo-randomly to form a single stream. This is then shuffled using the algorithm of Bays and Durham and from this stream a (user specified) number of successive elements are combined mod 1 (the scheme of Wichmann and Hill). In its use in my humble ciphers of the WEAK series, I continuously (i.e. at intervals) employ some hash values obtained during processing to skip elements of the output stream of the compound PRNG, so that, even with the same seed, different plaintexts would be processed in general with different pseudo-random numbers. (One wouldn't of course reuse the seed, though, if one follows the common operation conventions of stream ciphers.) Your pointing out that even the basic 'structure' of the generating system can be dynamically changed is very valuable. In the context of my compound PRNG, one could at certain time points during the encryption processing replace the constituent PRNGs with new ones, i.e. changing the parameters of these and also modifying their number. This 'refreshing' is quite easy to do, since the work amounts to a (different) initializaition of the compound generator. > >or practical but susceptible to exhaustive keysearch > >(just like almost all modern ciphers). > > But, in practice, modern key-based ciphers use "large enough" keys and > so are *not* "susceptible to exhaustive keysearch." > > >In other words, the variable > >key size proposal seems to offer no advantage over existing approaches > >in this respect. > > The obvious potential advantage is to complicate attacks on the RNG > state. Since attacks on RNG state are the obvious route to breaking > conventional stream ciphers, making those harder could produce an > actual increase in strength. That would seem to be a very reasonable > "advantage" indeed. I agree absolutely with your very clearly understandable exposition of the issue. M. K. Shen ----------------------------- http://home.t-online.de/home/mok-kong.shen
Subject: Re: cryptanalysis of keystream cipher Date: 14 Sep 2001 15:28:22 -0700 From: ggr@qualcomm.com (Gregory G Rose) Message-ID: <9nu0a6$cvn@qualcomm.com> References: <3ba1a8a8.55196359@netnews.att.net> Newsgroups: sci.crypt Lines: 26 In article <3ba1a8a8.55196359@netnews.att.net>, Terry Ritter <ritter@ciphersbyNOSPAMritter.com> wrote: >But what makes OTP's generally *impractical* is the size of their >keying material, and the continuing need to create, transport, and >hold keying material, all in absolute security. But none of that >applies to the conventional stream ciphers as being discussed here. >So the fact that OTP's are impractical is not relevant. Sorry to sound argumentative, but we were discussing exactly the use of a key as long as the plaintext, and so the practicality or otherwise of a one-time-pad was exactly relevent. Now I agree that conventional stream ciphers are a perfectly good tool for many encryption requirements, and personally I prefer them in combination with a MAC for virtually all applications. But your comment missed the actual point being discussed. Greg. -- Greg Rose INTERNET: ggr@qualcomm.com Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Subject: Re: cryptanalysis of keystream cipher Date: Sat, 15 Sep 2001 00:41:12 GMT From: ritter@ciphersbyNOSPAMritter.com (Terry Ritter) Message-ID: <3ba2a35b.35599503@netnews.att.net> References: <9nu0a6$cvn@qualcomm.com> Newsgroups: sci.crypt Lines: 83 On 14 Sep 2001 15:28:22 -0700, in <9nu0a6$cvn@qualcomm.com>, in sci.crypt ggr@qualcomm.com (Gregory G Rose) wrote: >In article <3ba1a8a8.55196359@netnews.att.net>, >Terry Ritter <ritter@ciphersbyNOSPAMritter.com> wrote: >>But what makes OTP's generally *impractical* is the size of their >>keying material, and the continuing need to create, transport, and >>hold keying material, all in absolute security. But none of that >>applies to the conventional stream ciphers as being discussed here. >>So the fact that OTP's are impractical is not relevant. > >Sorry to sound argumentative, but we were >discussing exactly the use of a key as long as the >plaintext, and so the practicality or otherwise of >a one-time-pad was exactly relevent. Well, I am *also* sorry that you feel the need to sound argumentative. And I'm also sure that you are the best source to tell us what *you* were discussing. But the *actual* topic up for discussion was set by the original poster: >>>>However, keystream ciphers need not be restricted to having a fixed >>>>size seed. It is relatively simple to design an algorithm that takes a >>>>variable length string as the key and performs some non-linear >>>>operations on it to generate the next iteration. That is a clear description of an unusual form of random number generator for a stream cipher which takes and uses a seed of variable size. It is definitely *not* the use of a key as long as the plaintext, so if *that* is what you were discussing, you were simply off topic. Here is the original poster again: >>>>Just to make it clear, here is what I had proposed : >>>> >>>>1. Start with a variable sized key. >>>> >>>>2. Output the cipher text by combining it modulo 256 with the same >>>>length of plaintext. >>>> >>>>3. Then combine the ciphertext that was just generated along with the >>>>existing key of generation 0 with some non-linear operations to get >>>>generation 1. >>>> >>>>4. Repeat steps 2 and 3 as many times as required until all plaintext >>>>has been consumed. That is: 1) a conventional stream cipher, composed of RNG and additive combiner; 2) the RNG producing confusion in variable-size units; 3) XOR combining of confusion and data; and 4) autokey (ciphertext feedback) operation. The unique part of the discussion is the RNG with a variable amount of internal state. We can take that idea and run with it, but there seems to be a lot of fumbling in the back field. As far as I can see, none of the proposal has anything to do with a key as long as the text, unless you see a stream cipher "keystream" as the "key" in question, in which case every stream cipher has such a "key," and in any case that misses the point. In practice, we never can prove that we even have an OTP. But it should be obvious that no proposal of any sort can possibly be an OTP as soon as the message entropy exceeds the entropy in the original key, or in this case, "the seed." [See step (4), above.] Again, that aspect is just like every other stream cipher design, and again misses the point. >Now I agree that conventional stream ciphers are a >perfectly good tool for many encryption >requirements, and personally I prefer them in >combination with a MAC for virtually all >applications. But your comment missed the actual >point being discussed. I think not. --- Terry Ritter www.ciphersbyritter.com/ Crypto Glossary www.ciphersbyritter.com/GLOSSARY.HTM
Subject: Re: cryptanalysis of keystream cipher Date: Sat, 15 Sep 2001 19:18:28 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3BA38D64.3D9644F8@t-online.de> References: <3ba2a35b.35599503@netnews.att.net> Newsgroups: sci.crypt Lines: 78 Terry Ritter wrote: > > ggr@qualcomm.com (Gregory G Rose) wrote: > > >Sorry to sound argumentative, but we were > >discussing exactly the use of a key as long as the > >plaintext, and so the practicality or otherwise of > >a one-time-pad was exactly relevent. > > Well, I am *also* sorry that you feel the need to sound argumentative. > And I'm also sure that you are the best source to tell us what *you* > were discussing. But the *actual* topic up for discussion was set by > the original poster: > > >>>>However, keystream ciphers need not be restricted to having a fixed > >>>>size seed. It is relatively simple to design an algorithm that takes a > >>>>variable length string as the key and performs some non-linear > >>>>operations on it to generate the next iteration. > > That is a clear description of an unusual form of random number > generator for a stream cipher which takes and uses a seed of variable > size. It is definitely *not* the use of a key as long as the > plaintext, so if *that* is what you were discussing, you were simply > off topic. I like to take this opportunity to elaborate a bit of what I expressed in a couple of previous follow-ups. It concerns essentially the issue of 'variability', the fundamental significance of which I have repeatedly stressed in the past. In the context of PRNG, there are in my view three (distinguishable) forms of 'variability'. (1) A parameterized PRNG, in which the size of the seed being input can be chosen at will by the user. (2) A PRNG in which the 'normal' updating (change) of the state (as it continues to generate output) may be varied (influenced) during the operation time through some 'feedback' from the encryption processing that employs the PRNG. (3) The PRNG's basic 'structure' may be (dynamically) varied during the encryption processing, that is, it may at runtime change its 'algorithmic of certain constructs, types of operations, data flow As I have pointed out previously, neither (1) (which apparently is what the original poster had in mind) nor (2) is new, both having been anyway realized in my compound PRNG with its use in my humble encryption algorithm WEAK3-EX. On the other hand, (3), which apparently is an idea stemming from you (anyway, I am unaware of explicit mentioning of that in the literature), is novel and very valuable in my humble view. For it essentially presents the opponent with a 'moving' ('volatile' in contrast to 'stationary') target, which by nature is very much harder to attack. (Compare shooting birds with shooting at a fixed spot on the wall.) Certainly, (2) does have some similar effects, but, in comparison to (3), it is not as 'strong' (in the sense of 'radical') in terms of the 'variability' involved. Personally, I am glad to find that implementation of your suggestion as described under (3) isn't difficult in practice. In fact, it is fairly easy in the case of my compound PRNG. Every 'refreshing' amounts to simply doing another 'initialization' phase, where the (initializing) PRNGs that are employed at the start of the run to generate the internal constituent PRNGs are called once again to generate a (new, in general different) number of constituent PRNGs with their new parameter values. M. K. Shen -------------------------- http://home.t-online.de/home/mok-kong.shen
Subject: Re: cryptanalysis of keystream cipher Date: 13 Sep 2001 22:44:31 -0700 From: bryanjugglercryptographer@yahoo.com (Bryan Olson) Message-ID: <1a517b5.0109132144.10326586@posting.google.com> References: <9nr8mr$jvr@qualcomm.com> Newsgroups: sci.crypt Lines: 25 Gregory G Rose wrote > Bryan Olson wrote: > >You also suggested that > >allowing arbitrary size keys makes brute force attack impossible, and > >that's what I tried to show false. Searching the entire keyspace that > >the algorithm allows may be impossible, but for any particular key, > >searching until one finds it takes finite time. > > Your argument is flawed, since it applies equally > well to the proven information-theoretically > secure one time pad. I meant to apply it only to Avik's claim, which asserted that just because the algorithm has an infinite key space, brute force is theoretically impossible. That's not the case, as I wrote, it's the key space from which the user actually chooses his keys that determines theoretic security, not the keyspace the algorithm can accept. If the user actually chooses his keys, and limits his messages so that messages do not exceed the unicity distance, then I agree the key is not solvable even by brute force. --Bryan
Terry Ritter, his current address, and his top page.
Last updated: 2001-09-18