# Stream Ciphers Using Variable Amounts of RNG State

## A Ciphers By Ritter Page

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.

### Contents

• 2001-09-12 Avik Ghosh: "Why is it that keystream ciphers seeded with a variable sized key are not used much ?" "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." [An RNG with a variable amount of state.] "It could even take some past output and feed it in during this iteration phase." [Autokey operation.] ( Output would be generated by just XORing with the input stream on a byte by byte basis )." [A stream cipher.]
• 2001-09-12 David Wagner: "Why would you want a variable sized key? 128 bits is sufficient . . . ."
• 2001-09-14 Paul Crowley: ". . . there is active research in the open community into cryptographic pseudo-random number generators (CPRNGs) . . . ."
• 2001-09-12 Terry Ritter: "Stream ciphers are not "absent," they are just "hidden." The military has used (and I assume still uses) them extensively."
• 2001-09-12 David Wagner: ". . . fully variable-size keys do not seem to offer any advantages worth bothering with."
• 2001-09-12 Terry Ritter: "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."
• 2001-09-13 David Wagner: "Do you mean dynamically changing the key size makes it more difficult to attack in practice?"
• 2001-09-13 Terry Ritter: "I mean that dynamically changing the structure of the RNG means that the RNG is more difficult to attack in practice." "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."
• 2001-09-13 David Wagner: "Does this have anything to do with variable-size keys? I can't see much relation, but maybe I'm missing something."
• 2001-09-13 Terry Ritter: "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:"
• 2001-09-13 Mok-Kong Shen: "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 . . . ."
• 2001-09-13 Mok-Kong Shen: "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 . . . ."
• 2001-09-13 Shai Halevi: "The most straightforward interpretation of "variable" is "parametrized" (e.g., Rijndael-128, Rijnael-192, Rijndael-256)."
• 2001-09-12 Mok-Kong Shen: "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."
• 2001-09-12 Avik Ghosh: "Thanks very much."
• 2001-09-12 Bryan Olson: "I think there's a definite error in that logic."
• 2001-09-13 Mok-Kong Shen: "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 . . . ."
• 2001-09-13 Bryan Olson: "He went on to postulate that the property made it invulnerable to exhaustive search, and that is not true."
• 2001-09-13 Avik Ghosh: "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."
• 2001-09-13 Bryan Olson: "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."
• 2001-09-13 Gregory G Rose: "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."
• 2001-09-13 David Wagner: "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."
• 2001-09-14 Mok-Kong Shen: "However, it is an additional approach . . . ."
• 2001-09-14 Terry Ritter: "The obvious potential advantage is to complicate attacks on the RNG state."
• 2001-09-14 Mok-Kong Shen: "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."
• 2001-09-14 Gregory G Rose: "Sorry to sound argumentative, but we were discussing exactly the use of a key as long as the plaintext . . . ."
• 2001-09-15 Terry Ritter: " . . . the *actual* topic up for discussion was set by the original poster:"
• 2001-09-15 Mok-Kong Shen: "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."
• 2001-09-13 Bryan Olson: "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."
```
Subject: cryptanalysis of keystream cipher
Date: 12 Sep 2001 09:30:57 -0700
From: aghosh@omnesys.com (Avik Ghosh)
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>
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.

--
__  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)
Newsgroups: sci.crypt
Lines: 155

On 12 Sep 2001 09:30:57 -0700, in
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

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
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>
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

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

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>
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)
Newsgroups: sci.crypt
Lines: 162

Thanks very much.

You have provided a lot for me to think about ( and also abandon ! ).

Avik.

ritter@ciphersbyNOSPAMritter.com (Terry Ritter) wrote in message news:<3b9fad8d.11268679@netnews.att.net>...
> On 12 Sep 2001 09:30:57 -0700, in
> 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
>
> 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
> 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)
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>
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)
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)
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 :

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)
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

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>
Newsgroups: sci.crypt
Lines: 31

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

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

---
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

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

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

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 :
>>>>
>>>>
>>>>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)
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

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