Comments on Staying with the Herd

Terry Ritter

A Ciphers By Ritter Page

One installment of the continuing conversation about problems with the current understandings of cryptography, and the advantages of multi-ciphering using different ciphers. This particular pulse of controversy is triggered by my article "Cryptography: Is Staying with the Herd Really Best?" in the August 1999 IEEE Computer.

Contents

• http://www.io.com/~ritter/ARTS/R8INTW1.PDF The article: "Cryptography: Is Staying with the Herd Really Best?", a .PDF file. Copyright 1999, IEEE.
• 1999-08-13 Terry Ritter: "I have just had an article published in the current (August, 1999) IEEE Computer magazine, titled "Cryptography: Is Staying with the Herd Really Best?" The general theme goes like this:"
• 1999-08-13 David A Molnar: "Thanks for the heads up."
• 1999-08-13 David A Molnar: "This is a good month for crypto in magazines, it looks like."
• 1999-08-13 John Savard: "Of course, these issues were discussed at great length in a thread some time back."
• 1999-08-13 Mok-Kong Shen: "We have discussed the same matter in our group."

  ---

• 1999-09-12 Mok-Kong Shen: "While the content has been subjects of a number of previous discussion threads in this group, the presentation of the article is extremely lucid . . . ."
• 1999-09-13 Terry Ritter: "There appears to be a .PDF copy of the article on-line . . . ."
• 1999-09-13 John Savard: "Appearances can be decieving. The PDF copy is only available to service subscribers."
• 1999-09-14 Terry Ritter: "There is a copy of the article .PDF on my pages." "The exact link is: http://www.io.com/~ritter/ARTS/R8INTW1.PDF."
• 1999-09-14 Medical Electronics Lab: "Thanks!"
• 1999-09-14 SCOTT19U.ZIP_GUY: "Are you saying it is against the law to decode something this is encrypted with a patented method?"
• 1999-09-14 John Savard: "While that doesn't really add much to security, that is true!"
• 1999-09-14 Terry Ritter: ". . . the civil recovery of damages is a different issue than criminal wiretapping."
• 1999-09-14 Terry Ritter: ". . . using a patented cipher without an explicit license is grounds for a suit to recover damages in federal court."
• 1999-09-15 SCOTT19U.ZIP_GUY: "How then can one study a patented method and tell others the weakness so they don't use a weak system."
• 1999-09-19 Terry Ritter: "A patent protects the particular *use* of particular information, not learning about it."
• 1999-09-18 Sundial Services: "I happen to be of the opinion that whether or not you have a patent on something is immaterial to the state of the art. It's either a good idea, or it's not."
• 1999-09-14 Sundial Services: ". . . personally I felt that the article was a bit too self-defensive about the issue of a cipher being patentable or not, and patented or not."
• 1999-09-19 Terry Ritter: "If you would count sentences which did not refer to patenting, as opposed to those which did, you might have a different slant on what "self-defensive" means."
• 1999-09-18 Sundial Services: "The cipher's the thing. The only thing. Is it safe, or not? Does it advance the [non-classified] art, or not? Why or why not?"
• 1999-09-14 David Wagner: "However, I don't think your suggestion works. I'd like to invite you to look over my reasoning and see if you find any errors."
• 1999-09-14 Terry Ritter: "For one thing, this model is too limited to describe the advantage of placing exponentially many ciphers before our Opponents. It also slouches toward comparing probabilities which we cannot know and thus make no scientific sense to discuss."
• 1999-09-14 David Wagner: "1. We might not be able to calculate the quantity f(R), but that's irrelevant to my argument; I don't care what the value of f(R) is."
• 1999-09-15 Trevor Jackson, III: "We have only ciphers that are not secure or whose security we are unable to determine. Note that last: it does not mean we "think" they are secure. It means we do not know."
• 1999-09-15 David Wagner: "I think you have forgotten to make a clear distinction between ciphers with unknown security and insecure ciphers."
• 1999-09-15 Trevor Jackson, III: "Agreed. The statement should have been: "...we have no ciphers that are KNOWN secure"."
• 1999-09-15 David Wagner: "Ok. So, why is this a gap in the reasoning?"
• 1999-09-16 Douglas A. Gwyn: "OTP is clearly not secure *in practice*."
• 1999-09-16 John Savard: "Since he only mentioned OTP in order to exclude it, it's enough that OTP is a cipher with the potential of being secure . . . ."
• 1999-09-16 Patrick Juola: "My understanding is that there are other cyphers -- the Rip van Winkle cypher leaps to mind -- that are "provably secure" in the sense of a proven lower bound on the work factor."
• 1999-09-16 Douglas A. Gwyn: "Yes, that's the sort of thing I was referring to."
• 1999-09-16 Sundial Services: "I suspect that the weakest link in most crypto implementations is not the cipher but the key-management."
• 1999-09-16 John Savard: "Although that might be just too simple for a learned cryptanalyst in these suspicious times."
• 1999-09-17 Trevor Jackson, III: "Yes, but work factor arguments are suspect."
• 1999-09-17 Jerry Coffin: ". . . nobody knows a way of proving that these problems have any particular level of difficulty, but nobody's shown that a proof of their difficulty is impossible either."
• 1999-09-17 Trevor Jackson, III: "The unicity point concept has little bearing on the great majority of modern block ciphers. Modern ciphers attempt to confuse/diffuse/etc until the best attack is brute force."
• 1999-09-15 Bodo Moeller: "In the multi-cipher scenario, you assume that there's an independent team for each cipher . . . ."
• 1999-09-15 David Wagner: "Good point! If you can share the workload and develop N ciphers for less than N times the cost of a single cipher, that changes the model."
• 1999-09-16 Richard Parker: ". . . wouldn't this raise the possibility that the ciphers are not sufficiently independent?"
• 1999-09-20 dianelos@tecapro.com: ". . . even though I do not completely agree with Ritter's article, I do share his preoccupation about building the information society of the future on top of a single cipher - it's like putting all the eggs in the world in a single basket."
• 1999-09-21 wtshaw:
• 1999-10-05 Mok-Kong Shen: "In a certain restricted sense I have exploited the possibility of affecting the PRNG output via the content of the text being processed (data dependency)."
• 1999-10-06 wtshaw: "I believe that I have wee captured a method for using randomness in encription, storing it integrated into the ciphertext, and unraveling its effects if decription."
• 1999-09-19 Terry Ritter: ". . . I claim it is impossible to extrapolate cipher strength from unsuccessful cryptanalytic work.
• 1999-09-14 David Wagner: ". . . Oops! I didn't mean to use such a loaded word . . . ."
• 1999-09-15 SCOTT19U.ZIP_GUY:
• 1999-09-15 Douglas A. Gwyn: "That isn't a useful contribution . . . ."
• 1999-09-16 rosi: "Dear Ritter, I see more sense in your side of the argument."
• 1999-09-18 bryan.olson@uptronics.com: "Could you clarify: in what parameter is the number of ciphers increasing exponentially?"
• 1999-09-15 SCOTT19U.ZIP_GUY: "His idea was to use some in series. But with your method we can be almost 100% sure that the NSA will be pulling the strings for the AES candidate that wins. So it will be weak."
• 1999-09-16 Jerry Leichter: "If AES is broken, every message sent using it is broken . . . ." "On the other hand, even if a significant fraction of Mr. Ritter's individual ciphers are broken, many messages remain secure . . . ."
• 1999-09-17 SCOTT19U.ZIP_GUY: "There are many ciphers that can withstand the known public attacks. You just have to look."
• 1999-09-19 Terry Ritter: "Anybody who likes AES can tell their system to use AES as one of the ciphers and pick the other two "at random" from a local list of approved ciphers . . . ."
• 1999-09-17 Trevor Jackson, III: ". . . we want to minimize the maximum damage that the opponent can do to us. In this regard several strong ciphers look vastly better than one universal cipher no matter how much "better" it is."
• 1999-09-19 Terry Ritter: "The question is whether we would bet our grandmother's income on our *opinion* that a particular mathematical conundrum could not be solved. Would we do it, and would it be right if we did?" "I advocate getting all the analysis we can, not using ciphers we think are weak, and using multiple ciphers in sequence. It is this last which quickly expands the body of overall "ciphers," and also tends to protect individual ciphers from unknown weakness they may possess."
• 1999-09-20 Mok-Kong Shen: "It is to be noted that using multiple ciphers does not mean deliberately seeking to use a combination of the poorer ciphers. It is an implicit assumption that the choice of the component ciphers is done with the usual care appropriate for the applications at hand."
• 1999-09-29 SCOTT19U.ZIP_GUY: "The AES contest is about finding a WEAK method so that it can be used for all encryption in all aplications. Even small smart cards. If there was room to allow parametrization the NSA would have a hader job of reading your files."
• 1999-09-30 John Savard: "Although the AES candidates are excellent ciphers, the fact that they are, in terms of their key size and block size, merely one step beyond DES, rather than two or three steps beyond . . . ."
• 1999-09-30 Johnny Bravo: "There is nothing insecure about 256 bit keys or 128 bit blocks."
• 1999-09-30 SCOTT19U.ZIP_GUY: "But way the hell would anyone other than a fool want to use the same encryption for all applitcations. Unless it was to aid an attacker."
• 1999-10-01 John Savard: "It is true that the AES candidates are highly secure ciphers . . . ."
• 1999-10-01 Tim Tyler: "As few cyphers are broken by brute force searches through all the possible keys, it really is unlikely to be valid to conclude that increasing the size of the keyspace increases the security in direct proportion."
• 1999-10-04 Tim Tyler: "I really have difficulty in seeing what point there was in specifying in advance that cyphers must encrypt in 128-bit blocks."
• 1999-10-04 Trevor Jackson, III: "What are the units of "ability to resist breaks"?"
• 1999-10-05 wtshaw: "It may be hard to put out one scale . . . ."
• 1999-10-05 Douglas A. Gwyn: "If you have a complete source model, we know how to *compute* information-theoretic measures from it."
• 1999-10-05 John Savard: "it's rather difficult to produce a complete source model of English text?"
• 1999-10-09 jerome: "any reference about the usage of the Hidden Markov Models in cryptography ?"
• 1999-10-09 Douglas A. Gwyn: "The applications are numerous, and once you're familiar with the technology it isn't hard to find opportunities to use it, for example to classify suspected textual units into functional categories (noun, verb, consonant, vowel, digit, punctuation, null, whatever)."
• 1999-10-09 John Savard: "I only recall the very simple example of a Markov model given in Scientific American . . . ."
• 1999-10-09 John Savard: "Thus, instead of the Markov chain, one wants something more "steady-state" to model a language."
• 1999-10-10 Douglas A. Gwyn: "The thing about a *hidden* Markov model is that it models internal states of a system that are seen only indirectly via the output of the system . . . ."
• 1999-10-06 Trevor Jackson, III: "This does not lead to an engineering figure of merit . . . ."
• 1999-10-08 Patrick Juola: "Differen cyphers have different areas of application, and different strengths depending on the use."
• 1999-10-08 Trevor Jackson, III: ". . . there are separate application domains whose metrics will always be distinct."
• 1999-10-08 Trevor Jackson, III: "We can inventory the weaknesses of ciphers, and thus measure the upper bounds on their strength, but I do not see any way to establish a lower bound on strength, which is the operational meaning of "known strength"."
• 1999-10-09 John Savard: "The problem of establishing a lower bound on a cipher's strength is, I believe, fundamentally equivalent to the famous "halting problem"."
• 1999-10-09 wtshaw: "I think it is fitting to leave an analyst flustered."
• 1999-10-10 Tim Tyler: "Turing's halting problem is often used to express hopelessness at finding an answer . . . ."
• 1999-10-11 John Savard: ". . . the requirement for doing this is to know that, no matter how much new we may learn about mathematics in the future, we will not find a better way of cracking that particular cipher."
• 1999-10-11 Tim Tyler: ". . . I'm still rather far from convinced that this analogy is a good one . . . ."
• 1999-10-12 wtshaw: "Exploring wartime evidence, we see lots of actual data about strength, and when knowing the cipher and having ciphertext was solely not enough."
• 1999-10-09 Tim Tyler: "I see no reason in principle why a PRNG-based cypher should be weak."
• 1999-10-10 Trevor Jackson, III: "There may be many attacks on a particular cipher, each attack requiring a different amount of ciphertext or plaintext."
• 1999-10-10 Tim Tyler: "Your posts seem to paint a black picture of PRNG-based cryptography." "Looking more closely, I see absolutely no evidence that they are (in principle) any less secure than any other modern cypher."
• 1999-10-10 Trevor Jackson, III: "As time goes on the sophistication of analytic algorithms increases whereas the sophistication any particular PRNG is constant."
• 1999-10-11 Tim Tyler: "This is true of all types of cypher, not just PRNG-based ones."
• 1999-10-09 wtshaw: ". . . cryptograhic weaknesses in one area tend to knock the stuffing out strengths in another."
• 1999-10-10 Trevor Jackson, III: ". . . progress both flavors of cryptology appears to be non-monotonic. The discontinuities make it very hard to use past experience to predict the future."
• 1999-10-10 wtshaw: ". . . ciphers can be scaled and some ciphers are obviously weaker or stronger than others."
• 1999-10-08 wtshaw: "Resistance to quantifying strength is really the *pro*-ignorance position."
• 1999-10-09 Tim Tyler: "Although customers can rarely measure strength directly, there are some clues available."
• 1999-10-05 wtshaw: ". . . I strongly advocated for a variable length block cipher. What came out was the result of compromise, in good faith."
• 1999-10-05 Doug Gwyn: "NIST wanted to evaluate proposals on a comparable basis. 128 bits was (and is) considered proof against brute-force attack;"
• 1999-10-06 Tim Tyler: "It seems to me that you can gain some security advantages by semaring the information in a file out through a larger block, /without/ requiring a larger key."
• 1999-10-06 wtshaw: "Yea, managing big keys is such a hastle when you don't know how to do it. But, it is not such a big deal once you understand the basics."
• 1999-09-14 John Savard: "You've presented a case with which I agree in many points. However, Bruce Schneier's paper on "Staying With the Herd" presents many points I agree with as well."
• 1999-09-14 Terry Ritter: "I am aware that the old point of view is fundamentally flawed and scientifically invalid. It is *not* almost valid. It is *not* partly right. It is *not* right in practice. It is just wrong."
• 1999-09-15 John Savard: "My point here is that a cipher beyond the reach of Eli Biham and the like *is* beyond the reach of a large number of likely opponents."
• 1999-09-15 SCOTT19U.ZIP_GUY: "Actually anyone aware of the state of electronics at the time DES was employed. I am talking custom hardware not computers. Realizes that DES could be easily broken by a realtime brute force search."
• 1999-09-19 Terry Ritter: "What is beyond Biham now may not be beyond the ordinary hacker after new technology is published."
• 1999-09-18 Sundial Services: "It's academic debate."
• 1999-09-19 John Savard: "I firmly believe that an ideological war is *not* the best climate for the search for truth. There are two schools of thought, and in my opinion each is incomplete."
• 1999-09-19 John Savard: "The best we can conclude, using Bayesian statistics, from the fact that a cipher has withstood X man-hours of analysis by qualified academics is that our best estimate of the probability that a given man-hour of analysis by other academics of similar qualification will uncover its crack is 1/(2X)."
• 1999-09-15 John Savard: "My position on these issues does not make exciting reading, as it consists of sitting resolutely on the fence."

Subject: IEEE Computer:  Staying with the Herd
Date: Fri, 13 Aug 1999 01:56:04 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37b379df.1528868@news.io.com>
Newsgroups: sci.crypt
Lines: 47


I have just had an article published in the current (August, 1999)
IEEE Computer magazine, titled "Cryptography:  Is Staying with the
Herd Really Best?"  The general theme goes like this:  

The idea that older ciphers are more secure than newer ones is false.
We do not know the strength of any cipher until it is broken, and even
then know only a transient upper bound instead of the "real" strength.
We cannot measure strength, and it is a delusion to imagine that
passing many tests and examinations tells us *anything* about "real"
strength.  We have no knowledge of cipher strength, and comparisons
between values we do not know are laughable.  

Assuming our ciphers are secure is fantasy.  We do not know whether or
not our ciphers keep our data secure.  We *can* not know because the
interaction of interest occurs between the ciphertext and The
Opponent, in private.  Cipher strength is thus contextual, with a
context for each possible Opponent.  To simply *believe* in the
strength of our ciphers is to deliver ourselves into the hands of our
Opponents, just as happened to Germany and Japan in WWII.  We can
choose to learn from history, or to repeat it.  

The cipher situation is far worse than the apparently similar
situation that we have in software, which we cannot prove bug-free,
but is useful anyway.  The difference is that we can in a general
sense measure what we want from software; bugs which interfere with
what we want are thus largely visible and can be worked around.  But
failure of our ciphers is unlikely to be apparent.  We simply cannot
expect to know whether or not our ciphers are keeping our secrets.  

We have options beyond bemoaning our fate or ignorantly accepting
delusion as opposed to harsh reality.  Options include multi-ciphering
as standard practice, using a wide variety of ciphers, choosing
ciphers dynamically, and having an expanding set of ciphers to choose
from.  Contrary to the conventional wisdom, some of these alternatives
benefit from having many new ciphers instead of just using old ones.
A design alternative is to produce scalable designs which can be
better investigated than any of our conventional large ciphers.  

Because of my current situation I am probably not going to be able to
participate in a discussion, but the article (actually, a guest
column) is published whether I am ready or not.

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: IEEE Computer:  Staying with the Herd
Date: 13 Aug 1999 03:59:38 GMT
From: David A Molnar <dmolnar@fas.harvard.edu>
Message-ID: <7p057a$360$1@news.fas.harvard.edu>
References: <37b379df.1528868@news.io.com>
Newsgroups: sci.crypt
Lines: 13

Terry Ritter <ritter@io.com> wrote:

> I have just had an article published in the current (August, 1999)
> IEEE Computer magazine, titled "Cryptography:  Is Staying with the
> Herd Really Best?"  The general theme goes like this:  
[snip concise summary]

Thanks for the heads up. I just joined the IEEE Computer Society; good to
know that such an article is coming. Will be interesting to see what the
response in the next issues is like. 

Thanks, 
-David Molnar


Subject: Re: IEEE Computer:  Staying with the Herd
Date: 13 Aug 1999 22:39:11 GMT
From: David A Molnar <dmolnar@fas.harvard.edu>
Message-ID: <7p26qf$c5i$3@news.fas.harvard.edu>
References: <7p057a$360$1@news.fas.harvard.edu>
Newsgroups: sci.crypt
Lines: 10

David A Molnar <dmolnar@fas.harvard.edu> wrote:

> Thanks for the heads up. I just joined the IEEE Computer Society; good to
> know that such an article is coming. Will be interesting to see what the
> response in the next issues is like. 

This is a good month for crypto in magazines, it looks like. Bruce
Schneier has an article on biometrics in _Communications of the ACM_.        

-David 


Subject: Re: IEEE Computer:  Staying with the Herd
Date: Fri, 13 Aug 1999 18:01:12 GMT
From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard)
Message-ID: <37b45aa0.8838507@news.prosurfr.com>
References: <37b379df.1528868@news.io.com>
Newsgroups: sci.crypt
Lines: 35

ritter@io.com (Terry Ritter) wrote, in part:

>Because of my current situation I am probably not going to be able to
>participate in a discussion, but the article (actually, a guest
>column) is published whether I am ready or not.

Of course, these issues were discussed at great length in a thread
some time back.

I think both sides have valid points, and thus I agree that multiple
layers of encryption - when handled properly - are a useful measure.

Although the fact that an algorithm has recieved a large amount of
attention and study from the most respected academic researchers does
not _prove_ that a weakness in it won't be discovered in the near
future,

it is also valid to say that such an algorithm has survived a
winnowing process that many new, unknown, unexamined algorithms are
likely not to get as far in.

On the other hand, a large quantity of different algorithms can create
a large amount of required effort for an attacker, and for that one
has to make use of algorithms that are less well tried.

Addressing both threats by using algorithms from both sides, under
safeguards (message expansion not allowed by the algorithms themselves
- a separate and "trusted" method produces IVs and/or session keys -
keys for each algorithm are effectively independent, due to being
produced by distinct hashes) that prevent one algorithm's weakness
from undermining another one's strength is a sensible and cautious way
to go.

John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm


Subject: Re: IEEE Computer:  Staying with the Herd
Date: Fri, 13 Aug 1999 20:46:56 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <37B46820.7749CADC@t-online.de>
References: <37b379df.1528868@news.io.com>
Newsgroups: sci.crypt
Lines: 27

Terry Ritter schrieb:
> 
> I have just had an article published in the current (August, 1999)
> IEEE Computer magazine, titled "Cryptography:  Is Staying with the
> Herd Really Best?"  The general theme goes like this:
> 

> 
> We have options beyond bemoaning our fate or ignorantly accepting
> delusion as opposed to harsh reality.  Options include multi-ciphering
> as standard practice, using a wide variety of ciphers, choosing
> ciphers dynamically, and having an expanding set of ciphers to choose
> from.  Contrary to the conventional wisdom, some of these alternatives
> benefit from having many new ciphers instead of just using old ones.
> A design alternative is to produce scalable designs which can be
> better investigated than any of our conventional large ciphers.

We have discussed the same matter in our group. I am convinced that
'variability', which generically covers all the above said, is one
of the principal means to render analysis futile and hence to attain
(practical) security. It is satisfying, that the author of the IEEE
article (not yet available to me), who I assume is certainly a very 
knowledgeable person in the field, confirms this view.

M. K. Shen
------------------------
http://home.t-online.de/home/mok-kong.shen


Subject: Ritter's paper
Date: Sun, 12 Sep 1999 22:11:42 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <37DC08FE.46DBF54E@t-online.de>
References: <37b379df.1528868@news.io.com>
Newsgroups: sci.crypt
Lines: 14

I just read Terry Ritter's Article

      Cryptography: Is Staying with the Herd Really Best?

in Computer (August issue). While the content has been subjects
of a number of previous discussion threads in this group, the 
presentation of the article is extremely lucid and renders it not 
only a valuable paper for the general readers of that journal but 
also worthy, in my humble opinion, the time of those who have 
participated in the said discussions to glance over it to refresh 
in memory what has been argued in the past. I enjoyed very much
reading the paper.

M. K. Shen


Subject: Re: Ritter's paper
Date: Mon, 13 Sep 1999 02:51:15 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37dc669e.1315229@news.io.com>
References: <37DC08FE.46DBF54E@t-online.de>
Newsgroups: sci.crypt
Lines: 29


On Sun, 12 Sep 1999 22:11:42 +0200, in
<37DC08FE.46DBF54E@t-online.de>, in sci.crypt Mok-Kong Shen
<mok-kong.shen@t-online.de> wrote:

>I just read Terry Ritter's Article
>
>      Cryptography: Is Staying with the Herd Really Best?
>
>in Computer (August issue). While the content has been subjects
>of a number of previous discussion threads in this group, the 
>presentation of the article is extremely lucid and renders it not 
>only a valuable paper for the general readers of that journal but 
>also worthy, in my humble opinion, the time of those who have 
>participated in the said discussions to glance over it to refresh 
>in memory what has been argued in the past. I enjoyed very much
>reading the paper.
>
>M. K. Shen


There appears to be a .PDF copy of the article on-line; see:

   http://computer.org/computer/co1999/r8toc.htm

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: Mon, 13 Sep 1999 17:21:25 GMT
From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard)
Message-ID: <37dd3129.8720079@news.prosurfr.com>
References: <37dc669e.1315229@news.io.com>
Newsgroups: sci.crypt
Lines: 24

ritter@io.com (Terry Ritter) wrote, in part:

>There appears to be a .PDF copy of the article on-line; see:

>   http://computer.org/computer/co1999/r8toc.htm

Appearances can be decieving. The PDF copy is only available to
service subscribers. But COMPUTER is widely available at libraries.

I've finally figured out a halfway-plausible rationale for the East
German cipher machine that uses a 12-level tape to XOR with a
"12-level form" of 5-level characters,

http://www.ecn.ab.ca/~jsavard/ro020404.htm

And I've extended my page on shift-register-based stream ciphers
noting how the timing of a device based on such principles might
interact with the usual method of serial transmission of 5-level
characters:

http://www.ecn.ab.ca/~jsavard/co041101.htm

John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm


Subject: Re: Ritter's paper
Date: Tue, 14 Sep 1999 00:40:21 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37dd996e.3608812@news.io.com>
References: <37dd3129.8720079@news.prosurfr.com>
Newsgroups: sci.crypt
Lines: 24


On Mon, 13 Sep 1999 17:21:25 GMT, in
<37dd3129.8720079@news.prosurfr.com>, in sci.crypt
jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) wrote:

>ritter@io.com (Terry Ritter) wrote, in part:
>
>>There appears to be a .PDF copy of the article on-line; see:
>
>>   http://computer.org/computer/co1999/r8toc.htm
>
>Appearances can be decieving. The PDF copy is only available to
>service subscribers. But COMPUTER is widely available at libraries.

There is a copy of the article .PDF on my pages.  It is first in the
list in the Technical Articles section on my top page.  The exact link
is:

   http://www.io.com/~ritter/ARTS/R8INTW1.PDF

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: Tue, 14 Sep 1999 12:44:59 -0500
From: Medical Electronics Lab <rosing@physiology.wisc.edu>
Message-ID: <37DE899B.76F6@physiology.wisc.edu>
References: <37dd996e.3608812@news.io.com>
Newsgroups: sci.crypt
Lines: 11

Terry Ritter wrote:
> There is a copy of the article .PDF on my pages.  It is first in the
> list in the Technical Articles section on my top page.  The exact link
> is:
> 
>    http://www.io.com/~ritter/ARTS/R8INTW1.PDF

Thanks!

Patience, persistence, truth,
Dr. mike


Subject: Re: Ritter's paper
Date: Tue, 14 Sep 1999 20:28:45 GMT
From: dscott@networkusa.net (SCOTT19U.ZIP_GUY)
Message-ID: <7rm7ls$1jki$1@news.gate.net>
References: <37DE899B.76F6@physiology.wisc.edu>
Newsgroups: sci.crypt
Lines: 26

In article <37DE899B.76F6@physiology.wisc.edu>, Medical Electronics Lab <rosing@physiology.wisc.edu> wrote:
>Terry Ritter wrote:
>> There is a copy of the article .PDF on my pages.  It is first in the
>> list in the Technical Articles section on my top page.  The exact link
>> is:
>> 
>>    http://www.io.com/~ritter/ARTS/R8INTW1.PDF
>
>Thanks!
>
>Patience, persistence, truth,
>Dr. mike

   I check it out nice article. But what I did not get was the comment about
if you use a patented system and someone breaks it you can recover damages.
What did you mean by that Mr. Ritter.  Are you saying it is against the law to 
decode something this is encrypted with a patented method?



David A. Scott
--
                    SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
                    http://www.jim.com/jamesd/Kong/scott19u.zip
                    http://members.xoom.com/ecil/index.htm
                    NOTE EMAIL address is for SPAMERS


Subject: Re: Ritter's paper
Date: Tue, 14 Sep 1999 19:58:24 GMT
From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard)
Message-ID: <37dea849.21467824@news.prosurfr.com>
References: <7rm7ls$1jki$1@news.gate.net>
Newsgroups: sci.crypt
Lines: 17

dscott@networkusa.net (SCOTT19U.ZIP_GUY) wrote, in part:

>   I check it out nice article. But what I did not get was the comment about
>if you use a patented system and someone breaks it you can recover damages.
>What did you mean by that Mr. Ritter.  Are you saying it is against the law to 
>decode something this is encrypted with a patented method?

While that doesn't really add much to security, that is true!
Building, for example, an IDEA-cracker is something for which you
would be unlikely to get a license to do under the patents on IDEA.

Since wiretapping is *also* illegal, if one uses cryptography one
generally is assuming one is protecting against adversaries who do not
balk at breaking the law, of course.

John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm


Subject: Re: Ritter's paper
Date: Tue, 14 Sep 1999 23:58:23 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37dee11c.5130018@news.io.com>
References: <37dea849.21467824@news.prosurfr.com>
Newsgroups: sci.crypt
Lines: 35


On Tue, 14 Sep 1999 19:58:24 GMT, in
<37dea849.21467824@news.prosurfr.com>, in sci.crypt
jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) wrote:

>dscott@networkusa.net (SCOTT19U.ZIP_GUY) wrote, in part:
>
>>   I check it out nice article. But what I did not get was the comment about
>>if you use a patented system and someone breaks it you can recover damages.
>>What did you mean by that Mr. Ritter.  Are you saying it is against the law to 
>>decode something this is encrypted with a patented method?
>
>While that doesn't really add much to security, 

That depends upon what you call "security," and is only true IF you
think security is Boolean.  But if you were a bank, you might see a
continuous shading of "security," depending on your losses, lawsuits,
and the growth of your business.  


>that is true!
>Building, for example, an IDEA-cracker is something for which you
>would be unlikely to get a license to do under the patents on IDEA.
>
>Since wiretapping is *also* illegal, if one uses cryptography one
>generally is assuming one is protecting against adversaries who do not
>balk at breaking the law, of course.

Of course.  But we know it happens.  And the civil recovery of damages
is a different issue than criminal wiretapping.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: Tue, 14 Sep 1999 23:58:02 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37dee100.5101955@news.io.com>
References: <7rm7ls$1jki$1@news.gate.net>
Newsgroups: sci.crypt
Lines: 37


On Tue, 14 Sep 1999 20:28:45 GMT, in <7rm7ls$1jki$1@news.gate.net>, in
sci.crypt dscott@networkusa.net (SCOTT19U.ZIP_GUY) wrote:

>In article <37DE899B.76F6@physiology.wisc.edu>, Medical Electronics Lab <rosing@physiology.wisc.edu> wrote:
>>Terry Ritter wrote:
>>> There is a copy of the article .PDF on my pages.  It is first in the
>>> list in the Technical Articles section on my top page.  The exact link
>>> is:
>>> 
>>>    http://www.io.com/~ritter/ARTS/R8INTW1.PDF
>>
>>Thanks!
>>
>>Patience, persistence, truth,
>>Dr. mike
>
>   I check it out nice article. But what I did not get was the comment about
>if you use a patented system and someone breaks it you can recover damages.
>What did you mean by that Mr. Ritter.  Are you saying it is against the law to 
>decode something this is encrypted with a patented method?

Against the law?  Well, yes, sort of:  using a patented cipher without
an explicit license is grounds for a suit to recover damages in
federal court.  

This is a distinct -- perhaps minor, perhaps not-so-minor -- advantage
over non-patented designs, for which, if broken, there is no recourse
at all.  The hard part would be to know what company was involved, but
once you get wage-scale employees in depositions or even on the stand,
someone would probably tell the truth, if just to avoid the stigma of
perjury.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: Wed, 15 Sep 1999 04:35:59 GMT
From: dscott@networkusa.net (SCOTT19U.ZIP_GUY)
Message-ID: <7rn47f$2i26$3@news.gate.net>
References: <37dee100.5101955@news.io.com>
Newsgroups: sci.crypt
Lines: 58

In article <37dee100.5101955@news.io.com>, ritter@io.com (Terry Ritter) wrote:
>
>On Tue, 14 Sep 1999 20:28:45 GMT, in <7rm7ls$1jki$1@news.gate.net>, in
>sci.crypt dscott@networkusa.net (SCOTT19U.ZIP_GUY) wrote:
>
>>In article <37DE899B.76F6@physiology.wisc.edu>, Medical Electronics Lab
> <rosing@physiology.wisc.edu> wrote:
>>>Terry Ritter wrote:
>>>> There is a copy of the article .PDF on my pages.  It is first in the
>>>> list in the Technical Articles section on my top page.  The exact link
>>>> is:
>>>> 
>>>>    http://www.io.com/~ritter/ARTS/R8INTW1.PDF
>>>
>>>Thanks!
>>>
>>>Patience, persistence, truth,
>>>Dr. mike
>>
>>   I check it out nice article. But what I did not get was the comment about
>>if you use a patented system and someone breaks it you can recover damages.
>>What did you mean by that Mr. Ritter.  Are you saying it is against the law to
> 
>>decode something this is encrypted with a patented method?
>
>Against the law?  Well, yes, sort of:  using a patented cipher without
>an explicit license is grounds for a suit to recover damages in
>federal court.  
>
>This is a distinct -- perhaps minor, perhaps not-so-minor -- advantage
>over non-patented designs, for which, if broken, there is no recourse
>at all.  The hard part would be to know what company was involved, but
>once you get wage-scale employees in depositions or even on the stand,
>someone would probably tell the truth, if just to avoid the stigma of
>perjury.  
>
>

       I am not sure there is such a thing as perjury anymore. I think
Clinton has should that one can easily lie and avoid any possible
perjury charge.

   But I fear you make a point that a patented cipher may be weak
becasue if the break is easy and if one publishes the break you
could make a suit to recover damages. How then can one study
a patented method and tell others the weakness so they don't
use a weak system. It seems like the patent would actually slow
the down the science of crypto. Except for groups like the NSA
which never follow any laws anyway.



David A. Scott
--
                    SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
                    http://www.jim.com/jamesd/Kong/scott19u.zip
                    http://members.xoom.com/ecil/index.htm
                    NOTE EMAIL address is for SPAMERS


Subject: Re: Ritter's paper
Date: Sun, 19 Sep 1999 00:30:47 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37e42eb1.4466295@quake.io.com>
References: <7rn47f$2i26$3@news.gate.net>
Newsgroups: sci.crypt
Lines: 45


On Wed, 15 Sep 1999 04:35:59 GMT, in <7rn47f$2i26$3@news.gate.net>, in
sci.crypt dscott@networkusa.net (SCOTT19U.ZIP_GUY) wrote:

>[...]
>   But I fear you make a point that a patented cipher may be weak
>becasue if the break is easy and if one publishes the break you
>could make a suit to recover damages. 

That doesn't sound right to me.  Patents *disclose* information.  A
break might even be a different patentable invention.  It is not a
patent infringement to describe a patent which depends on another
patent -- in fact that happens all the time.  

On the other hand, using trade secret information which was protected
by cipher and then stolen by infringing on a cipher patent is wrong in
a lot of ways, and we are right to have laws to punish such activity.


We always use ciphers we think cannot be broken.  But if they also
have some possibility of legal recovery, that may be some advantage in
some cases.  


>How then can one study
>a patented method and tell others the weakness so they don't
>use a weak system. It seems like the patent would actually slow
>the down the science of crypto. Except for groups like the NSA
>which never follow any laws anyway.

Maybe you have the wrong idea about patents:  The whole point of a
patent is to *reveal* information, not protect it.  It is trade
secrecy which hides information.  A patent protects the particular
*use* of particular information, not learning about it.  

In reality, a patent is an *economic* right, and rarely has anything
to do with individual use.  (One could of course postulate the
existence of a large company with an individual owner who might say
that he was using a patent for his "own personal use" all over the
company, but that is rare.)

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: Sat, 18 Sep 1999 22:22:55 -0700
From: Sundial Services <info@sundialservices.com>
Message-ID: <37E4732F.7D2E@sundialservices.com>
References: <37e42eb1.4466295@quake.io.com>
Newsgroups: sci.crypt
Lines: 11

You know, Mr. Ritter, I think it really is worth saying in public that
you furnish an extremely innovative web-site to the crypto-interested
community, and that you have -- and yes, have patented -- some extremely
refreshing and original ideas.  In fact, you seem to be about the only
person "here" whose ideas "think outside the box" of XOR and shifting.

I happen to be of the opinion that whether or not you have a patent on
something is immaterial to the state of the art.  It's either a good
idea, or it's not.  :->

Keep it up.


Subject: Re: Ritter's paper
Date: Tue, 14 Sep 1999 21:55:14 -0700
From: Sundial Services <info@sundialservices.com>
Message-ID: <37DF26B2.3DEB@sundialservices.com>
References: <37dee100.5101955@news.io.com>
Newsgroups: sci.crypt
Lines: 23

Terry Ritter wrote:

> >   I check it out nice article. But what I did not get was the comment about
> >if you use a patented system and someone breaks it you can recover damages.
> >What did you mean by that Mr. Ritter.  Are you saying it is against the law to
> >decode something this is encrypted with a patented method?
> 
> Against the law?  Well, yes, sort of:  using a patented cipher without
> an explicit license is grounds for a suit to recover damages in
> federal court.


It may be so, Mr. Ritter, but personally I felt that the article was a
bit too self-defensive about the issue of a cipher being patentable or
not, and patented or not.  An algorithm's patent status is neither a
crown nor a scarlet-letter and should not interfere with objective
judgement of it.  You have some original ideas and should be justifiably
pleased to have a patent and you should continue to exploit it.

But I debate in my mind how successful one would be, asking a jury to
reward one spook for stealing secrets from another spook.  I debate how
successful software patents really are, anyway.  You just can't
touchy-feely computer software like you can a physical invention...


Subject: Re: Ritter's paper
Date: Sun, 19 Sep 1999 00:31:04 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37e42eba.4475541@quake.io.com>
References: <37DF26B2.3DEB@sundialservices.com>
Newsgroups: sci.crypt
Lines: 65


On Tue, 14 Sep 1999 21:55:14 -0700, in
<37DF26B2.3DEB@sundialservices.com>, in sci.crypt Sundial Services
<info@sundialservices.com> wrote:

>Terry Ritter wrote:
>
>> >   I check it out nice article. But what I did not get was the comment about
>> >if you use a patented system and someone breaks it you can recover damages.
>> >What did you mean by that Mr. Ritter.  Are you saying it is against the law to
>> >decode something this is encrypted with a patented method?
>> 
>> Against the law?  Well, yes, sort of:  using a patented cipher without
>> an explicit license is grounds for a suit to recover damages in
>> federal court.
>
>
>It may be so, Mr. Ritter, but personally I felt that the article was a
>bit too self-defensive about the issue of a cipher being patentable or
>not, and patented or not.  

If you would count sentences which did not refer to patenting, as
opposed to those which did, you might have a different slant on what
"self-defensive" means.  

The problem is that academics refuse to address patented cryptographic
technology, for the various reasons Schneier discusses.  But whatever
those reasons are, they prevent academics from becoming expert on that
new technology, and we all lose.  


>An algorithm's patent status is neither a
>crown nor a scarlet-letter and should not interfere with objective
>judgement of it.  You have some original ideas and should be justifiably
>pleased to have a patent and you should continue to exploit it.

I don't know that I have been exploiting very much.  I do note that my
work is not discussed in the literature -- despite ink-on-paper
publication as well as patents -- while many arguably lesser systems
have been.


>But I debate in my mind how successful one would be, asking a jury to
>reward one spook for stealing secrets from another spook.  

Actually, we would be asking a jury for damages, subsequent to misuse
of trade secrets.  The deciphering would be clear indication of a
patent infringement, and the worth of that would be the value of the
lost information. 


>I debate how
>successful software patents really are, anyway.  You just can't
>touchy-feely computer software like you can a physical invention...

This does not appear to apply to me:  It would be difficult to call my
patents "software patents" in any conventional sense.  While it is
true that they do apply to software, they are very much conventional
machine patents.  And their purpose is to protect new cryptographic
technology, not particular ciphers.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: Sat, 18 Sep 1999 22:25:03 -0700
From: Sundial Services <info@sundialservices.com>
Message-ID: <37E473AF.55A5@sundialservices.com>
References: <37e42eba.4475541@quake.io.com>
Newsgroups: sci.crypt
Lines: 25

Terry Ritter wrote:
>
> >It may be so, Mr. Ritter, but personally I felt that the article was a
> >bit too self-defensive about the issue of a cipher being patentable or
> >not, and patented or not.
> 
> If you would count sentences which did not refer to patenting, as
> opposed to those which did, you might have a different slant on what
> "self-defensive" means.
> 
> The problem is that academics refuse to address patented cryptographic
> technology, for the various reasons Schneier discusses.  But whatever
> those reasons are, they prevent academics from becoming expert on that
> new technology, and we all lose.

We are in complete agreement on this statement.  I have made the same
observation privately myself.  "The cipher is the thing.  The only
thing."  If an individual is prescient enough to acquire a patent on a
really good idea -- and IF AND ONLY IF the idea really IS a good one --
then "goody for him, for about seven years."

The cipher's the thing.  The only thing.  Is it safe, or not?  Does it
advance the [non-classified] art, or not?  Why or why not?  

etc...


Subject: Re: Ritter's paper
Date: 14 Sep 1999 12:55:58 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David Wagner)
Message-ID: <7rm98e$69h$1@blowfish.isaac.cs.berkeley.edu>
References: <37dd996e.3608812@news.io.com>
Newsgroups: sci.crypt
Lines: 66

In article <37dd996e.3608812@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> There is a copy of the article .PDF on my pages.  It is first in the
> list in the Technical Articles section on my top page.  The exact link
> is:
>    http://www.io.com/~ritter/ARTS/R8INTW1.PDF

Thanks for posting!  I think this is an important subject for
discussion.

However, I don't think your suggestion works.  I'd like to invite
you to look over my reasoning and see if you find any errors.

Let's think of this as a resource allocation problem (i.e., an
economics problem), where our sole goal is to minimize the risk
that the adversary can read our traffic.  Then I think a fairly
simple calculation shows that your proposed approach is sub-optimal,
and that the best strategy is to "follow the crowd".

Suppose we have a fixed bound R on the total amount of resources
we can apply to the problem (e.g., R man-years, R months of Eli
Biham's time, whatever).  Further suppose we have a fixed amount T
of traffic to protect.  We have two choices:
 ("AES")  Design one cipher that you really really believe in; use
          it for _all_ the traffic.
          In other words, spend all of R on design and analysis
          of the cipher, and use it for all of T.
 (Ritter) Design N ciphers, and hope most of them don't get broken.
          In other words, spend R/N on each of the N designs, and
          use each cipher to encrypt T/N of the traffic.
I think these scenarios accurately characterize the two approaches
we want to compare.  Do you agree with the model?

Let f(R) be the probability that we apply the resources specified
by R to cryptographic design and analysis, and yet the adversary still
manages (somehow) to break our cipher.

We can now calculate the risk of failure for each scenario.
 ("AES")  With probability f(R), the cipher breaks, and all T of
          our traffic is broken.
   => Expected loss = T*f(R).
 (Ritter) Each cipher breaks with probability f(R/N), and each break
          reveals T/N of our traffic.
          Since expectation is linear, the total expected loss is the
          sum of the expected losses; the latter quantity is T/N * f(R/N)
          for each cipher, and there are N of them, so...
   => Expected loss = N * T/N * f(R/N) = T*f(R/N).
Here, I've made the assumption that the "utility function" we want
to minimize is the expected amount of compromised traffic.  This is
probably an unrealistic assumption, but let's make it for the moment.

It's hard to tell a priori what the graph of f() will look like,
but at least we can be pretty sure that f() is monotonic: doing
more analysis will only reduce the risk of catastrophic failure.

Thus, we can see that f(R) < f(R/N), and in particular,
T*f(R) < T*f(R/N), so the way to minimize the expected loss is to
choose the single-cipher strategy (the "AES" approach).  Using lots
of ciphers only increases the expected loss.

In the real world, the expected loss is probably not exactly the right
function to minimize (probably the harm is a non-linear function of
the amount of traffic compromised, where leaking 10% of one's traffic
is almost as bad as leaking 90% of it).  Nonetheless, a moment's thought
will show that adjusting this assumption to be more realistic will only
widen the gap between the two strategies, and will make the "AES"
approach even more appealing than the above calculation might suggest.


Subject: Re: Ritter's paper
Date: Tue, 14 Sep 1999 23:58:17 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37dee117.5124278@news.io.com>
References: <7rm98e$69h$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 144


On 14 Sep 1999 12:55:58 -0700, in
<7rm98e$69h$1@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
daw@blowfish.isaac.cs.berkeley.edu (David Wagner) wrote:

>In article <37dd996e.3608812@news.io.com>, Terry Ritter <ritter@io.com> wrote:
>> There is a copy of the article .PDF on my pages.  It is first in the
>> list in the Technical Articles section on my top page.  The exact link
>> is:
>>    http://www.io.com/~ritter/ARTS/R8INTW1.PDF
>
>Thanks for posting!  I think this is an important subject for
>discussion.
>
>However, I don't think your suggestion works.  I'd like to invite
>you to look over my reasoning and see if you find any errors.
>
>Let's think of this as a resource allocation problem (i.e., an
>economics problem), where our sole goal is to minimize the risk
>that the adversary can read our traffic.  Then I think a fairly
>simple calculation shows that your proposed approach is sub-optimal,
>and that the best strategy is to "follow the crowd".
>
>Suppose we have a fixed bound R on the total amount of resources
>we can apply to the problem (e.g., R man-years, R months of Eli
>Biham's time, whatever).  Further suppose we have a fixed amount T
>of traffic to protect.  We have two choices:
> ("AES")  Design one cipher that you really really believe in; use
>          it for _all_ the traffic.
>          In other words, spend all of R on design and analysis
>          of the cipher, and use it for all of T.
> (Ritter) Design N ciphers, and hope most of them don't get broken.
>          In other words, spend R/N on each of the N designs, and
>          use each cipher to encrypt T/N of the traffic.

I notice that you say I "hope" my ciphers are not broken.  Yet it is
*I* who can afford to lose a few:  I have exponentially many, you
know.  On the contrary, it is *you* who must *hope* your cipher is not
broken, because that is everything.  And you can *only* hope, because
you cannot *measure* that probability.


>I think these scenarios accurately characterize the two approaches
>we want to compare.  Do you agree with the model?

No.  For one thing, this model is too limited to describe the 
advantage of placing exponentially many ciphers before our Opponents.
It also slouches toward comparing probabilities which we cannot know
and thus make no scientific sense to discuss.  


>Let f(R) be the probability that we apply the resources specified
>by R to cryptographic design and analysis, and yet the adversary still
>manages (somehow) to break our cipher.

No, no, no we can't.  We might calculate the economic disaster
which would result from breaking (and those results would be:
disaster for the AES approach; a regrettable transient loss in mine),
but we cannot calculate the probability that a cipher will fail.  


>We can now calculate the risk of failure for each scenario.
> ("AES")  With probability f(R), the cipher breaks, and all T of
>          our traffic is broken.
>   => Expected loss = T*f(R).
> (Ritter) Each cipher breaks with probability f(R/N), and each break
>          reveals T/N of our traffic.
>          Since expectation is linear, the total expected loss is the
>          sum of the expected losses; the latter quantity is T/N * f(R/N)
>          for each cipher, and there are N of them, so...
>   => Expected loss = N * T/N * f(R/N) = T*f(R/N).
>Here, I've made the assumption that the "utility function" we want
>to minimize is the expected amount of compromised traffic.  This is
>probably an unrealistic assumption, but let's make it for the moment.

Alas, these are false computations.  One hidden -- dare I say
"sneakily" hidden -- assumption is that adding cryptanalysis resources
R reduces f.  But where is the evidence for this?  For example:

*  If the cipher is already broken, f = 1.0, and all the R we spend is
completely wasted to no avail.  

*  If the cipher is not broken but will be some day, we are again in
the same situation, but we just do not know it.  And this may be the
whole of our universe.

Yet another hidden assumption is that there exists a probability of
failure, and that we can discuss that.  I assert that while there may
be some such probability, there is no way to measure it, and no way to
know if our discussions are correct, and so no scientific use in
discussing it.  We cannot say when it is reduced, or even what that
might mean, unless we invent a special case where more attack
resources break more messages.  Normally we handwave a "break" which,
when known, exposes "all" messages.

You have also not included the per-cipher resource reduction which
affects the Opponents, and some sort of effort factor to describe the
difference between placing twice as much effort into something you
know as opposed to having to learn some whole new cipher and trying to
attack that.  One of the advantages of multi-ciphering is that it
creates exponentially many "ciphers" which may exist.  Another
advantage is that multiciphering protects each individual cipher
against known-plaintext attacks against an individual cipher.  If the
only reasonable attacks are known-plaintext, this alone inherently
increases strength over any single cipher which is necessarily exposed
to known-plaintext.  


>It's hard to tell a priori what the graph of f() will look like,
>but at least we can be pretty sure that f() is monotonic: doing
>more analysis will only reduce the risk of catastrophic failure.

This is CERTAINLY false if catastrophic failure already exists, or
will exist.  It is only true if you BELIEVE that the cipher is strong.
But if you are satisfied by belief, you don't need crypto -- just
*believe* your Opponents are not looking.


>Thus, we can see that f(R) < f(R/N), and in particular,
>T*f(R) < T*f(R/N), so the way to minimize the expected loss is to
>choose the single-cipher strategy (the "AES" approach).  Using lots
>of ciphers only increases the expected loss.

GIGO.


>In the real world, the expected loss is probably not exactly the right
>function to minimize (probably the harm is a non-linear function of
>the amount of traffic compromised, where leaking 10% of one's traffic
>is almost as bad as leaking 90% of it).  Nonetheless, a moment's thought
>will show that adjusting this assumption to be more realistic will only
>widen the gap between the two strategies, and will make the "AES"
>approach even more appealing than the above calculation might suggest.

I would say that "a moment's thought" should be sufficient to show the
futility of attempting a statistical argument on something which one
cannot measure, such as cipher "strength," or discussing the
"probability" that it will be broken, when we have no accounting and
no evidence relating to real probability.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: 14 Sep 1999 17:35:45 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David Wagner)
Message-ID: <7rmpl1$6li$1@blowfish.isaac.cs.berkeley.edu>
References: <37dee117.5124278@news.io.com>
Newsgroups: sci.crypt
Lines: 77

In article <37dee117.5124278@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> daw@blowfish.isaac.cs.berkeley.edu (David Wagner) wrote:
> >Let f(R) be the probability that we apply the resources specified
> >by R to cryptographic design and analysis, and yet the adversary still
> >manages (somehow) to break our cipher.
> 
> No, no, no we can't.  We might calculate the economic disaster
> which would result from breaking (and those results would be:
> disaster for the AES approach; a regrettable transient loss in mine),
> but we cannot calculate the probability that a cipher will fail.  

Thanks for the feedback; it's helpful.  But I must admit I disagree
with the above.  It's probably my fault for not making things clearer.


1. We might not be able to calculate the quantity f(R), but that's
irrelevant to my argument; I don't care what the value of f(R) is.
My argument indicates that, no matter what the values of f(R) are, the
single-cipher strategy is preferred to the multi-cipher strategy.  All
that is required is that f(R) be well-defined, not that it be easy to
calculate.

By analogy: let N = 10^(10^(10^(10^10))), and let M be the N-th digit
of pi; despite the fact that M is probably very hard to calculate, it
is still well-defined.  This shows that just because a quantity is hard
to calculate in practice doesn't necessarily mean it is ill-defined.


2. One must be a bit careful in interpreting the probability space here.
The probability space is given by the subjective choices of the designers
and analysts; the sample space is whether or not the resulting cipher is
secure.  In other words, if we let X = 1 if the cipher is insecure and 0
otherwise, then X is a random variable, and f(R) = Prob[X = 1].

Maybe the following will help make the definition of f(R) a bit more
explicit.  One can imagine running the following thought experiment many
times: hire some cryptographers to design the best cipher they can with
resources R, and then ask some "oracle" whether the result is secure.
Then the idea is that the probability f(R) is the fraction of times that
the resulting cipher is insecure.

(In practice, it may be too difficult to check whether the result is
secure, but in principle, we know there is some truth of the matter
about whether the cipher is secure, so the value f(R) is well-defined.)


3. I hope the above comments make it clearer why f(R) < f(R') when R > R'.
It just says that, if we run the above thought experiment with more
resources, we'll see fewer insecure ciphers.

This _is_ an assumption about humans.  But if the assumption is wrong,
doing cryptanalysis would be an actively harmful activity, because it
would confuse us more often than it will help us -- and I doubt that
too many folks want to try to make the case for _that_ result.


4. By the way, your note has helped me to recognize and clarify several
unstated assumptions.  Thank you.

First: I have not considered the workfactor required to read traffic;
if the adversary does not know which cipher each message was encrypted
in, then the adversary's workfactor may be as much as N times higher
in a multi-cipher scenario.  I believe this reasoning can be made
precise with a bit more work.

Second: as you say, I have not compared the resources required for the
adversary to analyze the ciphers.  A good point; thank you.  It is not
immediately clear to me which approach this factor would favor, but if
we assume in practice that the adversary's analysis resources are much
larger than our own, it may not matter.  I do not know whether this can
be modeled in my model, or whether it is an fundamental limitation of
my model.

I do agree that these are fundamental premises which must be assumed
if the conclusion of my argument is to be valid.  This suggests that
in practice we should be looking carefully at those assumptions to see
whether they hold in the real world or not.


Subject: Re: Ritter's paper
Date: Wed, 15 Sep 1999 12:30:58 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <37DFC9C2.297BC5FA@aspi.net>
References: <7rmpl1$6li$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 109

David Wagner wrote:

> In article <37dee117.5124278@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> > daw@blowfish.isaac.cs.berkeley.edu (David Wagner) wrote:
> > >Let f(R) be the probability that we apply the resources specified
> > >by R to cryptographic design and analysis, and yet the adversary still
> > >manages (somehow) to break our cipher.
> >
> > No, no, no we can't.  We might calculate the economic disaster
> > which would result from breaking (and those results would be:
> > disaster for the AES approach; a regrettable transient loss in mine),
> > but we cannot calculate the probability that a cipher will fail.
>
> Thanks for the feedback; it's helpful.  But I must admit I disagree
> with the above.  It's probably my fault for not making things clearer.
>
> 1. We might not be able to calculate the quantity f(R), but that's
> irrelevant to my argument; I don't care what the value of f(R) is.
> My argument indicates that, no matter what the values of f(R) are, the
> single-cipher strategy is preferred to the multi-cipher strategy.  All
> that is required is that f(R) be well-defined, not that it be easy to
> calculate.
>
> By analogy: let N = 10^(10^(10^(10^10))), and let M be the N-th digit
> of pi; despite the fact that M is probably very hard to calculate, it
> is still well-defined.  This shows that just because a quantity is hard
> to calculate in practice doesn't necessarily mean it is ill-defined.

Likewise ease of calcluation tells nothing about the quality of the definitions.

> 2. One must be a bit careful in interpreting the probability space here.
> The probability space is given by the subjective choices of the designers
> and analysts; the sample space is whether or not the resulting cipher is
> secure.  In other words, if we let X = 1 if the cipher is insecure and 0
> otherwise, then X is a random variable, and f(R) = Prob[X = 1].

There are several gaps here.  The grlaring one is that we have no ciphers
(excluding OTP) that are secure.  We have only ciphers that are not secure or
whose security we are unable to determine.  Note that last: it does not mean we
"think" they are secure.  It means we do not know.

This is not related to the scientific process of theorization and experiment.  We
are able to theorize about degrees of security, but we are not able to conduct
repeatable experiments to confirm those theories.  Thus we have theories (cipher C
is secure) that are known to be false and those whose validity is unknown.

Further, from history of cryptology, ciphers move only from the unknown class to
the known-broken class.  There is no process by which we can move a cipher out of
the unknown class into the known-unbreakable category.

So the concept of probabilities or security do not apply here.

> Maybe the following will help make the definition of f(R) a bit more
> explicit.  One can imagine running the following thought experiment many
> times: hire some cryptographers to design the best cipher they can with
> resources R, and then ask some "oracle" whether the result is secure.
> Then the idea is that the probability f(R) is the fraction of times that
> the resulting cipher is insecure.
>
> (In practice, it may be too difficult to check whether the result is
> secure, but in principle, we know there is some truth of the matter
> about whether the cipher is secure, so the value f(R) is well-defined.)

It appears that you are trying to create an extensible metric; one with predictive
power.

1. We cannot predict which ciphers are secure.  We can only break them, not prove
them.

2. The past experience of a group of cryptographs probably isn't predictive of
their own future success at breaking ciphers much less the success of others.


> 3. I hope the above comments make it clearer why f(R) < f(R') when R > R'.
> It just says that, if we run the above thought experiment with more
> resources, we'll see fewer insecure ciphers.
>
> This _is_ an assumption about humans.  But if the assumption is wrong,
> doing cryptanalysis would be an actively harmful activity, because it
> would confuse us more often than it will help us -- and I doubt that
> too many folks want to try to make the case for _that_ result.
>
> 4. By the way, your note has helped me to recognize and clarify several
> unstated assumptions.  Thank you.
>
> First: I have not considered the workfactor required to read traffic;
> if the adversary does not know which cipher each message was encrypted
> in, then the adversary's workfactor may be as much as N times higher
> in a multi-cipher scenario.  I believe this reasoning can be made
> precise with a bit more work.
>
> Second: as you say, I have not compared the resources required for the
> adversary to analyze the ciphers.  A good point; thank you.  It is not
> immediately clear to me which approach this factor would favor, but if
> we assume in practice that the adversary's analysis resources are much
> larger than our own, it may not matter.  I do not know whether this can
> be modeled in my model, or whether it is an fundamental limitation of
> my model.

You probably need to model some kind of summation over the capabilities of
multiple opponents rather than assuming a single monolithic opponent.

> I do agree that these are fundamental premises which must be assumed
> if the conclusion of my argument is to be valid.  This suggests that
> in practice we should be looking carefully at those assumptions to see
> whether they hold in the real world or not.





Subject: Re: Ritter's paper
Date: 15 Sep 1999 09:42:55 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David Wagner)
Message-ID: <7roiaf$70m$1@blowfish.isaac.cs.berkeley.edu>
References: <37DFC9C2.297BC5FA@aspi.net>
Newsgroups: sci.crypt
Lines: 15

In article <37DFC9C2.297BC5FA@aspi.net>,
Trevor Jackson, III <fullmoon@aspi.net> wrote:
> There are several gaps here.  The grlaring one is that we have no ciphers
> (excluding OTP) that are secure.  We have only ciphers that are not secure or
> whose security we are unable to determine.  Note that last: it does not mean
> we "think" they are secure.  It means we do not know.

Why do you think we have no ciphers that are secure?
If that were true, we would be able to trivially determine whether
any given cipher is secure -- the answer would always be "no". :-)

I think you have forgotten to make a clear distinction between
ciphers with unknown security and insecure ciphers.  Your reasoning
supports the conclusion that we have no ciphers with known security;
it does not support the conclusion that we have no secure ciphers.


Subject: Re: Ritter's paper
Date: Wed, 15 Sep 1999 16:01:47 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <37DFFB2B.D96B08F5@aspi.net>
References: <7roiaf$70m$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 28

David Wagner wrote:

> In article <37DFC9C2.297BC5FA@aspi.net>,
> Trevor Jackson, III <fullmoon@aspi.net> wrote:
> > There are several gaps here.  The grlaring one is that we have no ciphers
> > (excluding OTP) that are secure.  We have only ciphers that are not secure or
> > whose security we are unable to determine.  Note that last: it does not mean
> > we "think" they are secure.  It means we do not know.
>
> Why do you think we have no ciphers that are secure?
> If that were true, we would be able to trivially determine whether
> any given cipher is secure -- the answer would always be "no". :-)
>
> I think you have forgotten to make a clear distinction between
> ciphers with unknown security and insecure ciphers.  Your reasoning
> supports the conclusion that we have no ciphers with known security;
> it does not support the conclusion that we have no secure ciphers.

Agreed.  The statement should have been: "...we have no ciphers that are KNOWN
secure".

Sorry for the poor phrasing.








Subject: Re: Ritter's paper
Date: 15 Sep 1999 16:19:01 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David Wagner)
Message-ID: <7rp9h5$7ic$1@blowfish.isaac.cs.berkeley.edu>
References: <37DFFB2B.D96B08F5@aspi.net>
Newsgroups: sci.crypt
Lines: 10

In article <37DFFB2B.D96B08F5@aspi.net>,
Trevor Jackson, III <fullmoon@aspi.net> wrote:
> > In article <37DFC9C2.297BC5FA@aspi.net>,
> > Trevor Jackson, III <fullmoon@aspi.net> wrote:
> > > There are several gaps here.  [...]
> 
> Agreed.  The statement should have been: "...we have no ciphers that are KNOWN
> secure".

Ok.  So, why is this a gap in the reasoning?


Subject: Re: Ritter's paper
Date: Thu, 16 Sep 1999 06:14:21 GMT
From: "Douglas A. Gwyn" <DAGwyn@null.net>
Message-ID: <37E08AB3.B866B508@null.net>
References: <37DFC9C2.297BC5FA@aspi.net>
Newsgroups: sci.crypt
Lines: 27

"Trevor Jackson, III" wrote:
> There are several gaps here.  The grlaring one is that we have no
> ciphers (excluding OTP) that are secure.  We have only ciphers that
> are not secure or whose security we are unable to determine.  Note
> that last: it does not mean we "think" they are secure.  It means we
> do not know.

(a) OTP is clearly not secure *in practice*.  In a simplified
theoretical framework, it has certain mathematical properties
that are usually summarized by "is secure", but the exact
formulation is important.

(b) Other cipher systems have been described in the open literature
under the appellation "provably secure".  Again, one has to examine
the details to know exactly what that means.

(c) Shannon showed one way in which degree of security could be
quantified, in his description of unicity point.  An elaboration
of this idea can be used to prove certain bounds on insecurity
for systems on the proper side of the unicity point.  (These
might not correspond to systems in actual use, but it shows that
there are non-OTP theoretical counterexamples to your claim.)

(d) By "we" you must mean "Trevor Jackson and people I know about."
How do you know that point (c), or some other approach, hasn't been
developed into a full, practical theory by people you *don't* know
about?


Subject: Re: Ritter's paper
Date: 16 Sep 99 12:52:07 GMT
From: jsavard@ecn.ab.ca ()
Message-ID: <37e0e7f7.0@ecn.ab.ca>
References: <37E08AB3.B866B508@null.net>
Newsgroups: sci.crypt
Lines: 67


Douglas A. Gwyn (DAGwyn@null.net) wrote:
: "Trevor Jackson, III" wrote:
: > There are several gaps here.  The grlaring one is that we have no
: > ciphers (excluding OTP) that are secure.  We have only ciphers that
: > are not secure or whose security we are unable to determine.  Note
: > that last: it does not mean we "think" they are secure.  It means we
: > do not know.

: (a) OTP is clearly not secure *in practice*.  In a simplified
: theoretical framework, it has certain mathematical properties
: that are usually summarized by "is secure", but the exact
: formulation is important.

Since he only mentioned OTP in order to exclude it, it's enough that OTP
is a cipher with the potential of being secure; it is not essential to his
argument that OTP always be secure. We know it isn't robust under errors
in key handling.

: (b) Other cipher systems have been described in the open literature
: under the appellation "provably secure".  Again, one has to examine
: the details to know exactly what that means.

In the case of these other ciphers, such as Blum-Blum Shub, the term
always means "provably as secure as" a mathematical problem, such as
factoring or discrete logarithm, which cannot itself be proved to be truly
hard.

: (c) Shannon showed one way in which degree of security could be
: quantified, in his description of unicity point.  An elaboration
: of this idea can be used to prove certain bounds on insecurity
: for systems on the proper side of the unicity point.  (These
: might not correspond to systems in actual use, but it shows that
: there are non-OTP theoretical counterexamples to your claim.)

If a "one-time pad" containing a whole random alphabet for each letter
were used twice, instead of a series of displacements, the cryptanalyst
would only know that certain letters in the two messages were equal or
unequal. This is why two messages with the same starting point wouldn't be
sufficient to provide a good entry for an attack on the SIGABA, but in the
case of the SIGABA instead of truly random alphabets we already have left
the realm where one can really prove security. Also, if messages are
well-compressed before encryption (_very_ well compressed, to an extent
not done in the open literature) one may need to intercept quite a few
encrypted under the same key to have a possibility of solving them.

Perhaps this sort of thing is what you are referring to, or not.

: (d) By "we" you must mean "Trevor Jackson and people I know about."
: How do you know that point (c), or some other approach, hasn't been
: developed into a full, practical theory by people you *don't* know
: about?

He's describing the situation the open cryptographic community finds
itself in. This may be an important caveat, but it doesn't affect a
discussion about how people outside the NSA should behave when choosing
ciphers for their correspondence, which is in fact the topic of this
discussion.

I was hoping you might have some interesting input to this discussion; I'm
a bit disappointed to see here what appear to me to be merely quibbles.
But then I've still fallen short of what I might say, so far merely
reacting to what I see as "obvious" errors by Terry Ritter.

John Savard


Subject: Re: Ritter's paper
Date: 16 Sep 1999 11:31:52 -0400
From: juola@mathcs.duq.edu (Patrick Juola)
Message-ID: <7rr2h8$2u4$1@quine.mathcs.duq.edu>
References: <37e0e7f7.0@ecn.ab.ca>
Newsgroups: sci.crypt
Lines: 23

In article <37e0e7f7.0@ecn.ab.ca>,  <jsavard@ecn.ab.ca> wrote:
>: (b) Other cipher systems have been described in the open literature
>: under the appellation "provably secure".  Again, one has to examine
>: the details to know exactly what that means.
>
>In the case of these other ciphers, such as Blum-Blum Shub, the term
>always means "provably as secure as" a mathematical problem, such as
>factoring or discrete logarithm, which cannot itself be proved to be truly
>hard.

My understanding is that there are other cyphers -- the Rip van Winkle
cypher leaps to mind -- that are "provably secure" in the sense of a 
proven lower bound on the work factor.

Of course, these cyphers are also impractical (more impractical than
the OTP, in fact) -- but this is as much a technological issue as
a mathematical one.

It's also fairly easy to produce a cryptographic algorithm for which
there is a provable work-factor advantage to having a key -- *however*,
the work factor advantage just isn't sufficient.

	-kitten


Subject: Re: Ritter's paper
Date: Thu, 16 Sep 1999 18:14:07 GMT
From: "Douglas A. Gwyn" <DAGwyn@null.net>
Message-ID: <37E13365.CAA73F9A@null.net>
References: <7rr2h8$2u4$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 20

Patrick Juola wrote:
> My understanding is that there are other cyphers -- the Rip van Winkle
> cypher leaps to mind -- that are "provably secure" in the sense of a
> proven lower bound on the work factor.

Yes, that's the sort of thing I was referring to.

> Of course, these cyphers are also impractical (more impractical than
> the OTP, in fact) -- but this is as much a technological issue as
> a mathematical one.

Yes, since this was a theoretical discussion anyway.

> It's also fairly easy to produce a cryptographic algorithm for which
> there is a provable work-factor advantage to having a key -- *however*,
> the work factor advantage just isn't sufficient.

But one can iterate (compose, concatenate) such encryptions in a
way that raises the relative work factor to any arbitrary level.
There actually are implementations of this approach in real systems.


Subject: Re: Ritter's paper
Date: Thu, 16 Sep 1999 12:44:45 -0700
From: Sundial Services <info@sundialservices.com>
Message-ID: <37E148AD.2990@sundialservices.com>
References: <37E13365.CAA73F9A@null.net>
Newsgroups: sci.crypt
Lines: 21

Douglas A. Gwyn wrote:
> 
> Patrick Juola wrote:
> > My understanding is that there are other cyphers -- the Rip van Winkle
> > cypher leaps to mind -- that are "provably secure" in the sense of a
> > proven lower bound on the work factor.
> 
[...]
> But one can iterate (compose, concatenate) such encryptions in a
> way that raises the relative work factor to any arbitrary level.
> There actually are implementations of this approach in real systems.

I suspect that the weakest link in most crypto implementations is not
the cipher but the key-management.  I mean, if you know that the
fundamental key is, as it probably is, a text-string in printable ASCII
and probably a word out of a dictionary, or some phrase (etc...) as is
probably the case 99.9% of the time -- then THAT is how I would go about
attacking almost -any- cipher.

It don't matter how thick the steel is on the door, if you can open the
darn thing just by saying "Fritos."


Subject: Re: Ritter's paper
Date: Thu, 16 Sep 1999 20:46:22 GMT
From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard)
Message-ID: <37e156d3.17101314@news.prosurfr.com>
References: <37E148AD.2990@sundialservices.com>
Newsgroups: sci.crypt
Lines: 12

Sundial Services <info@sundialservices.com> wrote, in part:

>It don't matter how thick the steel is on the door, if you can open the
>darn thing just by saying "Fritos."

Although that might be just too simple for a learned cryptanalyst in
these suspicious times.

(well-known literary allusion)

John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm


Subject: Re: Ritter's paper
Date: Fri, 17 Sep 1999 22:13:08 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <37E2F534.CB0A135A@aspi.net>
References: <7rr2h8$2u4$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 30

Patrick Juola wrote:

> In article <37e0e7f7.0@ecn.ab.ca>,  <jsavard@ecn.ab.ca> wrote:
> >: (b) Other cipher systems have been described in the open literature
> >: under the appellation "provably secure".  Again, one has to examine
> >: the details to know exactly what that means.
> >
> >In the case of these other ciphers, such as Blum-Blum Shub, the term
> >always means "provably as secure as" a mathematical problem, such as
> >factoring or discrete logarithm, which cannot itself be proved to be truly
> >hard.
>
> My understanding is that there are other cyphers -- the Rip van Winkle
> cypher leaps to mind -- that are "provably secure" in the sense of a
> proven lower bound on the work factor.

Yes, but work factor arguments are suspect.  QC is the threat on the horizon.
There may be other over-the-horizon threats that may compromise a work factor
evaluation.

>
>
> Of course, these cyphers are also impractical (more impractical than
> the OTP, in fact) -- but this is as much a technological issue as
> a mathematical one.

Hmmm.  Does the lower bound proof show a differential effect of technology?
I.e., does using the cipher get easier with the advance in technology faster
than cracking the cipher gets easier?



Subject: Re: Ritter's paper
Date: Fri, 17 Sep 1999 01:04:31 -0600
From: jcoffin@taeus.com (Jerry Coffin)
Message-ID: <MPG.124b64a8a18fffe49896b7@news.mindspring.com>
References: <37e0e7f7.0@ecn.ab.ca>
Newsgroups: sci.crypt
Lines: 23

In article <37e0e7f7.0@ecn.ab.ca>, jsavard@ecn.ab.ca says...

[ ... ] 

> In the case of these other ciphers, such as Blum-Blum Shub, the term
> always means "provably as secure as" a mathematical problem, such as
> factoring or discrete logarithm, which cannot itself be proved to be truly
> hard.

I'd change "cannot itself be proved" to "has not been proven" -- 
TTBOMK, nobody knows a way of proving that these problems have any 
particular level of difficulty, but nobody's shown that a proof of 
their difficulty is impossible either.  I suspect this is what you 
really meant, but when you're talking about things like provable 
security, you just about have to get the wording exactly right, or 
somebody's inevitably going to try to turn it into argument over your 
wording instead of the real topic at hand...

-- 
    Later,
    Jerry.

The Universe is a figment of its own imagination.


Subject: Re: Ritter's paper
Date: Fri, 17 Sep 1999 22:06:54 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <37E2F3BE.AF0C5E1E@aspi.net>
References: <37E08AB3.B866B508@null.net>
Newsgroups: sci.crypt
Lines: 57



Douglas A. Gwyn wrote:

> "Trevor Jackson, III" wrote:
> > There are several gaps here.  The grlaring one is that we have no
> > ciphers (excluding OTP) that are secure.  We have only ciphers that
> > are not secure or whose security we are unable to determine.  Note
> > that last: it does not mean we "think" they are secure.  It means we
> > do not know.
>
> (a) OTP is clearly not secure *in practice*.  In a simplified
> theoretical framework, it has certain mathematical properties
> that are usually summarized by "is secure", but the exact
> formulation is important.

It is also irrelevant.  OTPs are not the topic.

> (b) Other cipher systems have been described in the open literature
> under the appellation "provably secure".  Again, one has to examine
> the details to know exactly what that means.

Usually this means as secure/hard as X where X is "thought to be secure"
or "thought to be hard".  Hardly a convincing manner of proof.

> (c) Shannon showed one way in which degree of security could be
> quantified, in his description of unicity point.  An elaboration
> of this idea can be used to prove certain bounds on insecurity
> for systems on the proper side of the unicity point.  (These
> might not correspond to systems in actual use, but it shows that
> there are non-OTP theoretical counterexamples to your claim.)

No it does not.  The unicity point concept has little bearing on the great
majority of modern block ciphers.  Modern ciphers attempt to
confuse/diffuse/etc until the best attack is brute force.  A cipher that
achieves this is considered secure.  But that achievement does not prevent
an attacker from identifying the actual plain text once he has found it.

A cipher that provided sufficient variation to eliminate the attackers
ability to identify a successful decryption would be immune to brute force
attack.  This is the essential issue addressed by the concept of the
unicity point.  It is one basis for claiming provable security.  I know of
no others.  Do you?

>
>
> (d) By "we" you must mean "Trevor Jackson and people I know about."
> How do you know that point (c), or some other approach, hasn't been
> developed into a full, practical theory by people you *don't* know
> about?

This amounts to a threat of a Blue Queen.  I don't know of any.  I said
so.  Do you know of any?  You have not said so.

 Until there is a specific claim available for inspection and analysis, I
will maintain that there are none such.



Subject: Re: Ritter's paper
Date: 15 Sep 1999 23:32:35 GMT
From: Bodo_Moeller@public.uni-hamburg.de (Bodo Moeller)
Message-ID: <7rpaaj$14d$1%epsilon@news.uni-hamburg.de>
References: <7rmpl1$6li$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 26

David Wagner <daw@blowfish.isaac.cs.berkeley.edu>:

[...]
> Maybe the following will help make the definition of f(R) a bit more
> explicit.  One can imagine running the following thought experiment many
> times: hire some cryptographers to design the best cipher they can with
> resources R, and then ask some "oracle" whether the result is secure.
> Then the idea is that the probability f(R) is the fraction of times that
> the resulting cipher is insecure.
> 
> (In practice, it may be too difficult to check whether the result is
> secure, but in principle, we know there is some truth of the matter
> about whether the cipher is secure, so the value f(R) is well-defined.)

In the multi-cipher scenario, you assume that there's an independent
team for each cipher ("Each cipher breaks with probability f(R/N)",
so the assumption is that effort  R/N  goes into each of the  N
ciphers).  However Terry Ritter's model seems to be that all the
individual designs should be derived from the same `pool' of know-how
(or he wouldn't talk about having "exponentially many" ciphers).

The real discrepancy between your and Terry's opinions might be that
you assume that the bulk of the analysis work can be done only once
there's a fixed design to look at, whereas Terry assumes that lots of
ciphers can be derived from collected knowledge on ciphers without
analysing each of the resulting ciphers in that much detail.


Subject: Re: Ritter's paper
Date: 15 Sep 1999 16:27:29 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David Wagner)
Message-ID: <7rpa11$7j1$1@blowfish.isaac.cs.berkeley.edu>
References: <7rpaaj$14d$1%epsilon@news.uni-hamburg.de>
Newsgroups: sci.crypt
Lines: 13

In article <7rpaaj$14d$1%epsilon@news.uni-hamburg.de>,
Bodo Moeller <Bodo_Moeller@public.uni-hamburg.de> wrote:
> The real discrepancy between your and Terry's opinions might be that
> you assume that the bulk of the analysis work can be done only once
> there's a fixed design to look at, whereas Terry assumes that lots of
> ciphers can be derived from collected knowledge on ciphers without
> analysing each of the resulting ciphers in that much detail.

Good point!  If you can share the workload and develop N ciphers for
less than N times the cost of a single cipher, that changes the model.
I hadn't thought about that possibility.

Many thanks for the excellent observation.


Subject: Re: Ritter's paper
Date: Thu, 16 Sep 1999 00:31:10 GMT
From: "Richard Parker" <richard-parker@home.com>
Message-ID: <iTWD3.4791$tJ1.38932@news.rdc2.occa.home.com>
References: <37dee117.5124278@news.io.com>
Newsgroups: sci.crypt
Lines: 20

daw@blowfish.isaac.cs.berkeley.edu (David Wagner) wrote:
> Bodo Moeller <Bodo_Moeller@public.uni-hamburg.de> wrote:
>> The real discrepancy between your and Terry's opinions might be that
>> you assume that the bulk of the analysis work can be done only once
>> there's a fixed design to look at, whereas Terry assumes that lots of
>> ciphers can be derived from collected knowledge on ciphers without
>> analysing each of the resulting ciphers in that much detail.
>
> Good point!  If you can share the workload and develop N ciphers for
> less than N times the cost of a single cipher, that changes the model.
> I hadn't thought about that possibility.

If one assumed that the workload was shared in the development of the
multiple ciphers, wouldn't this raise the possibility that the ciphers
are not sufficiently independent?  This presumably would suggest that
a catastrophic failure of the multiple ciphers could occur - the
failure mode that Terry Ritter hopes to avoid by not using a single
cipher.

-Richard


Subject: Re: Ritter's paper
Date: Mon, 20 Sep 1999 05:16:30 GMT
From: dianelos@tecapro.com
Message-ID: <7s4fv8$qst$1@nnrp1.deja.com>
References: <iTWD3.4791$tJ1.38932@news.rdc2.occa.home.com>
Newsgroups: sci.crypt
Lines: 97

In article <iTWD3.4791$tJ1.38932@news.rdc2.occa.home.com>,
  "Richard Parker" <richard-parker@home.com> wrote:

> If one assumed that the workload was shared in the development of the
> multiple ciphers, wouldn't this raise the possibility that the ciphers
> are not sufficiently independent?  This presumably would suggest that
> a catastrophic failure of the multiple ciphers could occur - the
> failure mode that Terry Ritter hopes to avoid by not using a single
> cipher.

Using multiple ciphers (choosing one from a pool of candidates) makes
sense *only* if the number of candidates is very large (many thousands
at least), because only then is the analytic capability of the attacker
overwhelmed. As you point out the question now is: how do you build a
large pool of ciphers that are sufficiently independent? Here I discuss
three alternatives:

1. Asking people to submit thousands of ciphers will probably not do.
Designing a cipher is a difficult proposition.

2. A possible solution is to have a "variable" cipher or a "cipher
generator", that produces a different cipher depending on parts of the
key. Maybe it is possible to build a generator so that a sufficiently
large proportion of the ciphers it generates are good enough and
independent enough. Confidence in that generator could be achieved
using the same process that is used to gain confidence about a
particular cipher: open and intensive cryptanalysis. Building such a
generator may be an even more difficult proposition than building a
single good cipher, or maybe not. You see, it would be more important
to show that the generated ciphers are quite independent (i.e. to show
that an attack against a few of the ciphers will not work on the rest),
rather than to show that on average each cipher is very strong. In fact
each individual cipher could be quite weak against a "known cipher"
attack, as long as the attacker cannot gain any knowledge about which
cipher is being used. Suppose, for example, that a generator produces
2^128 ciphers, each of which can be analyzed at a cost of one dollar
and broken with 3 known plaintexts - but that this investment does not
help analyze and break any other of the ciphers. We would still have
very good security, as long as an attacker cannot find out which cipher
is used n each case.

At bottom, of course, a cipher generator is a cipher too, but there is
an important shift in perspective. The designer now does not try to
build one function C=f(K,T) that fulfils one difficult requirement
(strength), but rather a group of functions C=f_K1(K2,T) that fulfil a
different set of requirements (independence and opaqueness), which may
be less difficult to achieve.

3. User-modifiable ciphers. Here we start with one standard cipher,
such as the AES. Suppose now that very knowledgeable cryptanalysts
suggest a series of "transparent" modifications to that cipher which do
not decrease its strength in any way. For example, as far as I can see,
if you take any cipher based on successive rounds, and XOR an
additional secret key to the data stream between two rounds, then you
do not decrease that cipher's strength. Suppose now that over time more
and more approved modifications such as this one are stored in a pool.
Every programmer who writes a security application starts with the AES,
randomly chooses a few modifications, and produces his or her very own
AES variant (at a very low price in speed). The human input in the
process would make the resulting ciphers quite independent. If the
particular set of modifications is keyed then the resulting cipher
would be in principle unknown to the attacker - we would now have a
cipher generator, albeit one that can grow dynamically. In any case, we
would produce a highly chaotic world from the point of view of the
attacker.

In conclusion, even though I do not completely agree with Ritter's
article, I do share his preoccupation about building the information
society of the future on top of a single cipher - it's like putting all
the eggs in the world in a single basket. At the very least, as John
Savard suggests, we should combine AES in series with something else.
The possibilities are many, so I think it would be very useful to have
a standard in place that converts a ciphertext into a self-contained
object that includes information about the methods used in its
encryption. In a networked world, these methods need not form part of
the ciphertext; the ciphertext would only have to point to the methods
stored somewhere in the net. There are plenty of advantages here: a)
everybody could be talking to everybody else without the need for one
particular standard (the AES could be used as the default method
anyway), b) advances in cryptology could reach the market fast, c)
catastrophic failure in one method would become less global, d)
catastrophic failure in one method could be corrected almost
immediately for all future communications and could be corrected
relatively fast for saved data. Here I am making several implicit
assumptions: a) that most encryption in the future will be software
based, b) that a catastrophic failure in one method will be become
public knowledge. The last assumption is very questionable in the
current state of affairs but maybe will be a reality in the future.

This is so complicated! :(

I wish somebody would publish a practical and truly provably secure
cipher, so that we could stop worrying.


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.


Subject: Re: Ritter's paper
Date: Tue, 21 Sep 1999 20:24:39 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-2109992024390001@dial-243-055.itexas.net>
References: <7s4fv8$qst$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 14

In article <7s4fv8$qst$1@nnrp1.deja.com>, dianelos@tecapro.com wrote:


> I wish somebody would publish a practical and truly provably secure
> cipher, so that we could stop worrying.
> 
You should not worry much since there is always a group of nay-sayers. 
The fact is that we are really just calling for more of them, to answer
the objections of different pockets of those who argue against the
possibility of ways that do not use the same patterns that are most
commonly hawked.
-- 
Mark my return, in a somewhat limited way. 
As things get better, I will try to follow more threads.


Subject: Re: Ritter's paper
Date: Tue, 05 Oct 1999 21:06:43 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <37FA4C43.8572AF19@t-online.de>
References: <FIxsoI.88A@bath.ac.uk>
   <37e70b7b.0@ecn.ab.ca>
   <7s4fv8$qst$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 37

Tim Tyler wrote:
> 
> It seems that when using a PRNG as a stream cypher, it would be a
> good idea if possible to use the contents of the message as an additional
> source of entropy, (in addition to the key).
> 
> In other words, rather than keeping the PRNG insulated from the message,
> you should allow these two entities to interact.
> 
> I wonder what the best way of doing this is which retains the ability to
> decrypt the information is.
> 
> It appears that if decryption happens in a largely serial manner,
> entropy from early (decrypted) parts of the message should be available
> to feed into the PRNG as it decrypts later parts of the message.
> 
> Thoughts in this general area would be welcomed.


In a certain restricted sense I have exploited the possibility of 
affecting the PRNG output via the content of the text being processed
(data dependency). In my humble encryption algorithm WEAK3-EX (a 
PRNG-driven block cipher) in each round a certain hash value is 
computed to determine the number of values output by the PRNG that are
to be skipped, i.e. thrown away. This means that different plaintexts 
will, in all probability, be processed differently, since different 
(sub)sequences of numbers output from the PRNG are employed, leading 
to e.g. different substitutions being applied in the round. This is 
admittedly a rather simple method of affecting the PRNG. However, in 
the context of my design, where a large amount of the PRNG output is 
employed in a number of different ways in each round, I believe this 
method is sufficient for serving its purpose and it is not worth the 
effort to devise a more sophisticated method of affecting the PRNG.

M. K. Shen
-------------------------
http://home.t-online.de/home/mok-kong.shen


Subject: Re: Ritter's paper
Date: Wed, 06 Oct 1999 11:59:38 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-0610991159380001@dial-243-015.itexas.net>
References: <37FA4C43.8572AF19@t-online.de>
Newsgroups: sci.crypt
Lines: 43

In article <37FA4C43.8572AF19@t-online.de>, Mok-Kong Shen
<mok-kong.shen@t-online.de> wrote:

> Tim Tyler wrote:
> > 
>....
> > 
> > In other words, rather than keeping the PRNG insulated from the message,
> > you should allow these two entities to interact.
> > 
> > I wonder what the best way of doing this is which retains the ability to
> > decrypt the information is.
> > 
I believe that I have wee captured a method for using randomness in
encription, storing it integrated into the ciphertext, and unraveling its
effects if decription.   The tipoff that information is added is in a
marginal increase in length of ciphertext over plaintext.
> 
....
> In my humble encryption algorithm WEAK3-EX (a 
> PRNG-driven block cipher) in each round a certain hash value is 
> computed to determine the number of values output by the PRNG that are
> to be skipped, i.e. thrown away. 

You must be concerned about length of the pseudorandom series.

This means that different plaintexts 
> will, in all probability, be processed differently, since different 
> (sub)sequences of numbers output from the PRNG are employed, leading 
> to e.g. different substitutions being applied in the round. This is 
> admittedly a rather simple method of affecting the PRNG. However, in 
> the context of my design, where a large amount of the PRNG output is 
> employed in a number of different ways in each round, I believe this 
> method is sufficient for serving its purpose and it is not worth the 
> effort to devise a more sophisticated method of affecting the PRNG.
> 
I figure that I am long on data and short on PRNG, random values being
fewer needed than the size of plaintext.  I can obscure the randomness
with that found in many characters, plaintext and/or intermediates before
cipertext combined.
-- 
Sometimes a small mistake can lead to fortunate reward.
  Charlie Chan


Subject: Re: Ritter's paper
Date: Sun, 19 Sep 1999 00:31:19 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37e42eca.4491688@quake.io.com>
References: <7rpaaj$14d$1%epsilon@news.uni-hamburg.de>
Newsgroups: sci.crypt
Lines: 39


On 15 Sep 1999 23:32:35 GMT, in
<7rpaaj$14d$1%epsilon@news.uni-hamburg.de>, in sci.crypt
Bodo_Moeller@public.uni-hamburg.de (Bodo Moeller) wrote:

>[...]
>In the multi-cipher scenario, you assume that there's an independent
>team for each cipher ("Each cipher breaks with probability f(R/N)",
>so the assumption is that effort  R/N  goes into each of the  N
>ciphers).  However Terry Ritter's model seems to be that all the
>individual designs should be derived from the same `pool' of know-how
>(or he wouldn't talk about having "exponentially many" ciphers).

Not so.  That particular point is that when we have 3 layers of
component cipher, with n possible inner ciphers, we have n**3 overall
"ciphers."  


>The real discrepancy between your and Terry's opinions might be that
>you assume that the bulk of the analysis work can be done only once
>there's a fixed design to look at, whereas Terry assumes that lots of
>ciphers can be derived from collected knowledge on ciphers without
>analysing each of the resulting ciphers in that much detail.

One discrepancy is that I claim it is impossible to extrapolate cipher
strength from unsuccessful cryptanalytic work.  Cryptanalysis can
*only* testify to the weakness of ciphers, and *only* for ciphers
which are "broken," and then only as an upper bound.  Cryptanalysis
does *not* testify about the strength of unbroken ciphers, and those
are the only ones we want to use.  

Another discrepancy is that I protest anyone's "right" to put the
whole information society at risk on the basis of a few opinions on
strength which are not and cannot be based in scientific reason.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: 14 Sep 1999 17:40:49 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David Wagner)
Message-ID: <7rmpuh$6m9$1@blowfish.isaac.cs.berkeley.edu>
References: <37dee117.5124278@news.io.com>
Newsgroups: sci.crypt
Lines: 10

In article <37dee117.5124278@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> I notice that you say I "hope" my ciphers are not broken.

Oops!  I didn't mean to use such a loaded word; my mistake.
Please strike the word "hope".

I hope you will believe me when I say that I intended for this to be a
fair comparison, where -- in both scenarios -- the cryptographers try
their hardest to do the best job possible with the resources available
to them.


Subject: Re: Ritter's paper
Date: Wed, 15 Sep 1999 04:42:44 GMT
From: dscott@networkusa.net (SCOTT19U.ZIP_GUY)
Message-ID: <7rn4k4$2i26$4@news.gate.net>
References: <7rmpuh$6m9$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 23

In article <7rmpuh$6m9$1@blowfish.isaac.cs.berkeley.edu>, daw@blowfish.isaac.cs.berkeley.edu (David Wagner) wrote:
>In article <37dee117.5124278@news.io.com>, Terry Ritter <ritter@io.com> wrote:
>> I notice that you say I "hope" my ciphers are not broken.
>
>Oops!  I didn't mean to use such a loaded word; my mistake.
>Please strike the word "hope".
>
>I hope you will believe me when I say that I intended for this to be a
>fair comparison, where -- in both scenarios -- the cryptographers try
>their hardest to do the best job possible with the resources available
>to them.

  It is obvious you can't do a fair comparison becasue you lack the
over all grasp of what cryptography is all about.



David A. Scott
--
                    SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
                    http://www.jim.com/jamesd/Kong/scott19u.zip
                    http://members.xoom.com/ecil/index.htm
                    NOTE EMAIL address is for SPAMERS


Subject: Re: Ritter's paper
Date: Wed, 15 Sep 1999 14:53:40 GMT
From: "Douglas A. Gwyn" <gwyn@arl.mil>
Message-ID: <37DFB2F4.862426E@arl.mil>
References: <7rn4k4$2i26$4@news.gate.net>
Newsgroups: sci.crypt
Lines: 15

"SCOTT19U.ZIP_GUY" wrote:
> In article <7rmpuh$6m9$1@blowfish.isaac.cs.berkeley.edu>, daw@blowfish.isaac.cs.berkeley.edu (David Wagner) wrote:
> >I hope you will believe me when I say that I intended for this to be a
> >fair comparison, where -- in both scenarios -- the cryptographers try
> >their hardest to do the best job possible with the resources available
> >to them.
>   It is obvious you can't do a fair comparison becasue you lack the
> over all grasp of what cryptography is all about.

That isn't a useful contribution; you should identify at least
one significant error, which would at least lead the discussion
onward toward the truth.  I assume you don't mean that the error
is DW's assumption that cryptographers would try ro do the best
job possible with the available resources, since that seems like
a plausible assumption for such an analysis.


Subject: Re: Ritter's paper
Date: Thu, 16 Sep 1999 00:19:28 -0400
From: "rosi" <rosi@erols.com>
Message-ID: <7rpt8f$s8e$1@winter.news.rcn.net>
References: <37dee117.5124278@news.io.com>
Newsgroups: sci.crypt
Lines: 154

Dear Ritter,

   I see more sense in your side of the argument.

   --- (My Signature)

Terry Ritter wrote in message <37dee117.5124278@news.io.com>...
>
>On 14 Sep 1999 12:55:58 -0700, in
><7rm98e$69h$1@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
>daw@blowfish.isaac.cs.berkeley.edu (David Wagner) wrote:
>
>>In article <37dd996e.3608812@news.io.com>, Terry Ritter <ritter@io.com>
wrote:
>>> There is a copy of the article .PDF on my pages.  It is first in the
>>> list in the Technical Articles section on my top page.  The exact link
>>> is:
>>>    http://www.io.com/~ritter/ARTS/R8INTW1.PDF
>>
>>Thanks for posting!  I think this is an important subject for
>>discussion.
>>
>>However, I don't think your suggestion works.  I'd like to invite
>>you to look over my reasoning and see if you find any errors.
>>
>>Let's think of this as a resource allocation problem (i.e., an
>>economics problem), where our sole goal is to minimize the risk
>>that the adversary can read our traffic.  Then I think a fairly
>>simple calculation shows that your proposed approach is sub-optimal,
>>and that the best strategy is to "follow the crowd".
>>
>>Suppose we have a fixed bound R on the total amount of resources
>>we can apply to the problem (e.g., R man-years, R months of Eli
>>Biham's time, whatever).  Further suppose we have a fixed amount T
>>of traffic to protect.  We have two choices:
>> ("AES")  Design one cipher that you really really believe in; use
>>          it for _all_ the traffic.
>>          In other words, spend all of R on design and analysis
>>          of the cipher, and use it for all of T.
>> (Ritter) Design N ciphers, and hope most of them don't get broken.
>>          In other words, spend R/N on each of the N designs, and
>>          use each cipher to encrypt T/N of the traffic.
>
>I notice that you say I "hope" my ciphers are not broken.  Yet it is
>*I* who can afford to lose a few:  I have exponentially many, you
>know.  On the contrary, it is *you* who must *hope* your cipher is not
>broken, because that is everything.  And you can *only* hope, because
>you cannot *measure* that probability.
>
>
>>I think these scenarios accurately characterize the two approaches
>>we want to compare.  Do you agree with the model?
>
>No.  For one thing, this model is too limited to describe the
>advantage of placing exponentially many ciphers before our Opponents.
>It also slouches toward comparing probabilities which we cannot know
>and thus make no scientific sense to discuss.
>
>
>>Let f(R) be the probability that we apply the resources specified
>>by R to cryptographic design and analysis, and yet the adversary still
>>manages (somehow) to break our cipher.
>
>No, no, no we can't.  We might calculate the economic disaster
>which would result from breaking (and those results would be:
>disaster for the AES approach; a regrettable transient loss in mine),
>but we cannot calculate the probability that a cipher will fail.
>
>
>>We can now calculate the risk of failure for each scenario.
>> ("AES")  With probability f(R), the cipher breaks, and all T of
>>          our traffic is broken.
>>   => Expected loss = T*f(R).
>> (Ritter) Each cipher breaks with probability f(R/N), and each break
>>          reveals T/N of our traffic.
>>          Since expectation is linear, the total expected loss is the
>>          sum of the expected losses; the latter quantity is T/N * f(R/N)
>>          for each cipher, and there are N of them, so...
>>   => Expected loss = N * T/N * f(R/N) = T*f(R/N).
>>Here, I've made the assumption that the "utility function" we want
>>to minimize is the expected amount of compromised traffic.  This is
>>probably an unrealistic assumption, but let's make it for the moment.
>
>Alas, these are false computations.  One hidden -- dare I say
>"sneakily" hidden -- assumption is that adding cryptanalysis resources
>R reduces f.  But where is the evidence for this?  For example:
>
>*  If the cipher is already broken, f = 1.0, and all the R we spend is
>completely wasted to no avail.
>
>*  If the cipher is not broken but will be some day, we are again in
>the same situation, but we just do not know it.  And this may be the
>whole of our universe.
>
>Yet another hidden assumption is that there exists a probability of
>failure, and that we can discuss that.  I assert that while there may
>be some such probability, there is no way to measure it, and no way to
>know if our discussions are correct, and so no scientific use in
>discussing it.  We cannot say when it is reduced, or even what that
>might mean, unless we invent a special case where more attack
>resources break more messages.  Normally we handwave a "break" which,
>when known, exposes "all" messages.
>
>You have also not included the per-cipher resource reduction which
>affects the Opponents, and some sort of effort factor to describe the
>difference between placing twice as much effort into something you
>know as opposed to having to learn some whole new cipher and trying to
>attack that.  One of the advantages of multi-ciphering is that it
>creates exponentially many "ciphers" which may exist.  Another
>advantage is that multiciphering protects each individual cipher
>against known-plaintext attacks against an individual cipher.  If the
>only reasonable attacks are known-plaintext, this alone inherently
>increases strength over any single cipher which is necessarily exposed
>to known-plaintext.
>
>
>>It's hard to tell a priori what the graph of f() will look like,
>>but at least we can be pretty sure that f() is monotonic: doing
>>more analysis will only reduce the risk of catastrophic failure.
>
>This is CERTAINLY false if catastrophic failure already exists, or
>will exist.  It is only true if you BELIEVE that the cipher is strong.
>But if you are satisfied by belief, you don't need crypto -- just
>*believe* your Opponents are not looking.
>
>
>>Thus, we can see that f(R) < f(R/N), and in particular,
>>T*f(R) < T*f(R/N), so the way to minimize the expected loss is to
>>choose the single-cipher strategy (the "AES" approach).  Using lots
>>of ciphers only increases the expected loss.
>
>GIGO.
>
>
>>In the real world, the expected loss is probably not exactly the right
>>function to minimize (probably the harm is a non-linear function of
>>the amount of traffic compromised, where leaking 10% of one's traffic
>>is almost as bad as leaking 90% of it).  Nonetheless, a moment's thought
>>will show that adjusting this assumption to be more realistic will only
>>widen the gap between the two strategies, and will make the "AES"
>>approach even more appealing than the above calculation might suggest.
>
>I would say that "a moment's thought" should be sufficient to show the
>futility of attempting a statistical argument on something which one
>cannot measure, such as cipher "strength," or discussing the
>"probability" that it will be broken, when we have no accounting and
>no evidence relating to real probability.
>
>---
>Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
>Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM
>




Subject: Re: Ritter's paper
Date: Sat, 18 Sep 1999 02:02:56 GMT
From: bryan.olson@uptronics.com
Message-ID: <7rursb$889$1@nnrp1.deja.com>
References: <37dee117.5124278@news.io.com>
Newsgroups: sci.crypt
Lines: 18

Terry Ritter wrote:

[...]
> *I* who can afford to lose a few:  I have exponentially many, you
> know.

Could you clarify: in what parameter is the number of
ciphers increasing exponentially?  The one such
function I see is that the number of composite ciphers
increases exponentially in the number we compose, as
long as we have two or more from which to choose.  But
I don't think that parameter will get very large.

--Bryan


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.


Subject: Re: Ritter's paper
Date: Wed, 15 Sep 1999 00:43:35 GMT
From: dscott@networkusa.net (SCOTT19U.ZIP_GUY)
Message-ID: <7rmmjq$34ti$1@news.gate.net>
References: <7rm98e$69h$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 97

In article <7rm98e$69h$1@blowfish.isaac.cs.berkeley.edu>, daw@blowfish.isaac.cs.berkeley.edu (David Wagner) wrote:
>In article <37dd996e.3608812@news.io.com>, Terry Ritter <ritter@io.com> wrote:
>> There is a copy of the article .PDF on my pages.  It is first in the
>> list in the Technical Articles section on my top page.  The exact link
>> is:
>>    http://www.io.com/~ritter/ARTS/R8INTW1.PDF
>
>Thanks for posting!  I think this is an important subject for
>discussion.
>
>However, I don't think your suggestion works.  I'd like to invite
>you to look over my reasoning and see if you find any errors.
>
>Let's think of this as a resource allocation problem (i.e., an
>economics problem), where our sole goal is to minimize the risk
>that the adversary can read our traffic.  Then I think a fairly
>simple calculation shows that your proposed approach is sub-optimal,
>and that the best strategy is to "follow the crowd".
>
>Suppose we have a fixed bound R on the total amount of resources
>we can apply to the problem (e.g., R man-years, R months of Eli
>Biham's time, whatever).  Further suppose we have a fixed amount T
>of traffic to protect.  We have two choices:
> ("AES")  Design one cipher that you really really believe in; use
>          it for _all_ the traffic.
>          In other words, spend all of R on design and analysis
>          of the cipher, and use it for all of T.
   The fallacy is your spending all your money on a design that is
supose to work in all envornments from credit cards to file portection
as a result you get something that can't be very good. One should
at the very least have different designs for different requirements unless
you real task Mr Wagner is to make everything readable by your
handlers.
   We don't build one vechicle on the road to haul garbage kids and
to go off road it just is not practical.
> (Ritter) Design N ciphers, and hope most of them don't get broken.
>          In other words, spend R/N on each of the N designs, and
>          use each cipher to encrypt T/N of the traffic.
>I think these scenarios accurately characterize the two approaches
>we want to compare.  Do you agree with the model?
   No I think your full of it. He said you can use variuos ciphers. I think
he might even use one of yours in the layer.
>
>Let f(R) be the probability that we apply the resources specified
>by R to cryptographic design and analysis, and yet the adversary still
>manages (somehow) to break our cipher.
>
>We can now calculate the risk of failure for each scenario.
> ("AES")  With probability f(R), the cipher breaks, and all T of
>          our traffic is broken.
>   => Expected loss = T*f(R).
> (Ritter) Each cipher breaks with probability f(R/N), and each break
>          reveals T/N of our traffic.
  Again not if you do them in series.
>          Since expectation is linear, the total expected loss is the
>          sum of the expected losses; the latter quantity is T/N * f(R/N)
>          for each cipher, and there are N of them, so...
>   => Expected loss = N * T/N * f(R/N) = T*f(R/N).
>Here, I've made the assumption that the "utility function" we want
>to minimize is the expected amount of compromised traffic.  This is
>probably an unrealistic assumption, but let's make it for the moment.
>
>It's hard to tell a priori what the graph of f() will look like,
>but at least we can be pretty sure that f() is monotonic: doing
>more analysis will only reduce the risk of catastrophic failure.
>
>Thus, we can see that f(R) < f(R/N), and in particular,
>T*f(R) < T*f(R/N), so the way to minimize the expected loss is to
>choose the single-cipher strategy (the "AES" approach).  Using lots
>of ciphers only increases the expected loss.
>
>In the real world, the expected loss is probably not exactly the right
>function to minimize (probably the harm is a non-linear function of
>the amount of traffic compromised, where leaking 10% of one's traffic
>is almost as bad as leaking 90% of it).  Nonetheless, a moment's thought
>will show that adjusting this assumption to be more realistic will only
>widen the gap between the two strategies, and will make the "AES"
>approach even more appealing than the above calculation might suggest.

   You can wave you hand all you want. His idea was to use some in series.
But with your method we can be almost 100% sure that the NSA will be
pulling the strings for the AES candidate that wins. So it will be weak. 
Unless your foolish enough to belive your government is honest. I can say
with 26 years of direct government experience that the governemnt is not 
honest. Would you buy a used car from Clinton. Sir in the "real world" your
assumptions are worthless. Your forgot politcs. Just as you where so 
ignorant to blatently say your Slide Attack would show scott19u.zip you
are wrong about this. 



David A. Scott
--
                    SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
                    http://www.jim.com/jamesd/Kong/scott19u.zip
                    http://members.xoom.com/ecil/index.htm
                    NOTE EMAIL address is for SPAMERS


Subject: Re: Ritter's paper
Date: Thu, 16 Sep 1999 16:50:04 -0400
From: Jerry Leichter <leichter@smarts.com>
Message-ID: <37E157FC.7FDA@smarts.com>
References: <7rm98e$69h$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 65

"I've made the assumption that the "utility function" we want
to minimize is the expected amount of compromised traffic.  This is
probably an unrealistic assumption, but let's make it for the moment."

Actually, I believe this is the crux of much of your disagreement with
Mr. Ritter.  You're looking at expectations - average values.  For
expections, I believe your arguments are correct.

However, we must also consider what is effectively "the probability of
ruin".  If AES is broken, every message sent using it is broken, and a
major - potentially immense - investment must be made to completely
replace an infrastructure based on it.  On the other hand, even if a
significant fraction of Mr. Ritter's individual ciphers are broken, many
messages remain secure - and in a reasonable design for the infra-
structure, it's possible to eliminate the bad ciphers from future use
without rebuilding the entire infrastructure.

Another way of looking at this is that the cost function is highly
non-linear:  As long a reasonably large fraction of Mr. Ritter's ciphers
are secure, the costs (in broken messages, in the effort needed to weed
out ciphers that have proven to be weak) are small.  The cost grows very
rapidly beyond a certain point, where most combinations are breakable. 
The problem with an AES, of course, is that there's only one "combina-
tion", so you get right to the extremely high cost range.

Ignoring the probability of ruin is at the heart of many bad probabilis-
tic arguments - e.g., many naive arguments about martingales, and all
sorts of bad investment strategies in the real world.

On the other hand, I think there are practical difficulties with Mr.
Ritter's approach.  Even the cryptanalytic attacks known in the public
literature are sufficiently powerful to slice right through most simple
designs.  The ciphers that can survive *even the attacks we know about*
are pretty rare on the ground.  Where will we find a large collection of
reasonably secure ciphers to use for Mr. Ritter's scheme?

Mr. Ritter likes to design parameterized families of ciphers - a
powerful approach, and probably the only way to get a large number of
reasonable cipher designs in hand quickly.  But that opens the door to
attacks against whole families.

If the collection of ciphers to be used in this scheme is fixed up
front, it will be subject to attack - and likely many ciphers will be
picked off.  So there will likely have to be a mechanism to add new
ciphers to the mix.  However, that opens a powerful line of attack to a
knowledgeable opponent:  He can contribute (through apparently unrelated
3rd parties, of course) a large number of apparently very good ciphers
that he knows how to break.  Since no one will be in a position to do
really deep analyses of many different ciphers, it's unlikely that the
"spiked" ciphers will be found:  It took many years to become convinced
that DES doesn't have a trap door, and even today there are people who
retain their suspicions.  (Actually, an attacker of this sort wouldn't
even have to wait for updates:  He would likely be right there at the
initiation of the system, offering up a whole load of neat-looking
ciphers.  It would require a big leap beyond the publically-known state
of the art in cryptography to slip a trap door into a system like AES,
which will be very closely examined by many people *and is expected to
be really strong* - so any weakness that *is* found will immediately
raise a red flag.  On the other hand, it would be relatively easy to
slip many subtly spiked systems into Mr. Ritter's pool, since no one
would look at them very closely - and, besides, even if one, or many, of
the "spikes" were found, how could you distinguish that from those
ciphers just being weak because the person who proposed them wasn't
quite as good at crypto as he thought?)
							-- Jerry


Subject: Re: Ritter's paper
Date: Fri, 17 Sep 1999 03:43:26 GMT
From: dscott@networkusa.net (SCOTT19U.ZIP_GUY)
Message-ID: <7rs9t4$um8$1@news.gate.net>
References: <37E157FC.7FDA@smarts.com>
Newsgroups: sci.crypt
Lines: 93

In article <37E157FC.7FDA@smarts.com>, Jerry Leichter <leichter@smarts.com> wrote:
>"I've made the assumption that the "utility function" we want
>to minimize is the expected amount of compromised traffic.  This is
>probably an unrealistic assumption, but let's make it for the moment."
>
>Actually, I believe this is the crux of much of your disagreement with
>Mr. Ritter.  You're looking at expectations - average values.  For
>expections, I believe your arguments are correct.
>
>However, we must also consider what is effectively "the probability of
>ruin".  If AES is broken, every message sent using it is broken, and a
>major - potentially immense - investment must be made to completely
>replace an infrastructure based on it.  On the other hand, even if a
>significant fraction of Mr. Ritter's individual ciphers are broken, many
>messages remain secure - and in a reasonable design for the infra-
>structure, it's possible to eliminate the bad ciphers from future use
>without rebuilding the entire infrastructure.
>
>Another way of looking at this is that the cost function is highly
>non-linear:  As long a reasonably large fraction of Mr. Ritter's ciphers
>are secure, the costs (in broken messages, in the effort needed to weed
>out ciphers that have proven to be weak) are small.  The cost grows very
>rapidly beyond a certain point, where most combinations are breakable. 
>The problem with an AES, of course, is that there's only one "combina-
>tion", so you get right to the extremely high cost range.
>
>Ignoring the probability of ruin is at the heart of many bad probabilis-
>tic arguments - e.g., many naive arguments about martingales, and all
>sorts of bad investment strategies in the real world.
>
>On the other hand, I think there are practical difficulties with Mr.
>Ritter's approach.  Even the cryptanalytic attacks known in the public
>literature are sufficiently powerful to slice right through most simple
>designs.  The ciphers that can survive *even the attacks we know about*
>are pretty rare on the ground.  Where will we find a large collection of
    I don't belive this. The only one's people like Wagner and Bruce talk
about are those that are bad so they can just make a flat statement about
ameture ciphers. There are many ciphers that can withstand the known
public attacks. You just have to look.
>reasonably secure ciphers to use for Mr. Ritter's scheme?
>
>Mr. Ritter likes to design parameterized families of ciphers - a
>powerful approach, and probably the only way to get a large number of
>reasonable cipher designs in hand quickly.  But that opens the door to
>attacks against whole families.
>
>If the collection of ciphers to be used in this scheme is fixed up
>front, it will be subject to attack - and likely many ciphers will be
>picked off.  So there will likely have to be a mechanism to add new
>ciphers to the mix.  However, that opens a powerful line of attack to a
>knowledgeable opponent:  He can contribute (through apparently unrelated
>3rd parties, of course) a large number of apparently very good ciphers
    That is just what the AES thing is all about. Do you really think that
if a cipher that might get 90% share of the worlds encrypted traffic would
not get thier attension. With there billion of dollars per year budget do you
really think they don't have a trojan horse candidate that is not going to
win. The whole thing sounds 2 FISHY to me. Who says the NSA guys
don't have a since of humor. I bet that a BS method will win.

>that he knows how to break.  Since no one will be in a position to do
>really deep analyses of many different ciphers, it's unlikely that the
>"spiked" ciphers will be found:  It took many years to become convinced
>that DES doesn't have a trap door, and even today there are people who
>retain their suspicions.  (Actually, an attacker of this sort wouldn't
>even have to wait for updates:  He would likely be right there at the
>initiation of the system, offering up a whole load of neat-looking
>ciphers.  It would require a big leap beyond the publically-known state
>of the art in cryptography to slip a trap door into a system like AES,
>which will be very closely examined by many people *and is expected to
>be really strong* - so any weakness that *is* found will immediately
>raise a red flag.  On the other hand, it would be relatively easy to
>slip many subtly spiked systems into Mr. Ritter's pool, since no one
>would look at them very closely - and, besides, even if one, or many, of
>the "spikes" were found, how could you distinguish that from those
>ciphers just being weak because the person who proposed them wasn't
>quite as good at crypto as he thought?)
    Jerry if you think the AES candidate will be hot. What if Ritter used it
in series with one that he thinks is strong. IF you use both methods 
correctly mostly just insuring the the length of data put in each method
matches the lenght of data out and that the keys used with each are
independent. Then you can safely assume the combination will be no
weaker than the stronger of the two methods used.


>                                                        -- Jerry


David A. Scott
--
                    SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
                    http://www.jim.com/jamesd/Kong/scott19u.zip
                    http://members.xoom.com/ecil/index.htm
                    NOTE EMAIL address is for SPAMERS


Subject: Re: Ritter's paper
Date: Sun, 19 Sep 1999 00:46:41 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37e43184.5189896@quake.io.com>
References: <7rs9t4$um8$1@news.gate.net>
Newsgroups: sci.crypt
Lines: 31


On Fri, 17 Sep 1999 03:43:26 GMT, in <7rs9t4$um8$1@news.gate.net>, in
sci.crypt dscott@networkusa.net (SCOTT19U.ZIP_GUY) wrote:

>[...]
>    Jerry if you think the AES candidate will be hot. What if Ritter used it
>in series with one that he thinks is strong. IF you use both methods 
>correctly mostly just insuring the the length of data put in each method
>matches the lenght of data out and that the keys used with each are
>independent. Then you can safely assume the combination will be no
>weaker than the stronger of the two methods used.

I don't recall who pointed this out originally, but it has been widely
discussed, perhaps in the last round on this topic.  See:

   http://www.io.com/~ritter/NEWS4/LIMCRYPT.HTM

Anybody who likes AES can tell their system to use AES as one of the
ciphers and pick the other two "at random" from a local list of
approved ciphers, in negotiation with the other end.  If we use
separate keys for each cipher, the multi-cipher is extremely unlikely
to be weaker than any *one* of the components.  

To claim multiciphering is weaker than any single cipher alternative
is to claim that we cannot use that cipher as a component cipher,
which is almost surely wrong.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: Fri, 17 Sep 1999 22:23:54 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <37E2F7BA.3B312ADC@aspi.net>
References: <37E157FC.7FDA@smarts.com>
Newsgroups: sci.crypt
Lines: 93

Jerry Leichter wrote:

> "I've made the assumption that the "utility function" we want
> to minimize is the expected amount of compromised traffic.  This is
> probably an unrealistic assumption, but let's make it for the moment."
>
> Actually, I believe this is the crux of much of your disagreement with
> Mr. Ritter.  You're looking at expectations - average values.  For
> expections, I believe your arguments are correct.
>
> However, we must also consider what is effectively "the probability of
> ruin".  If AES is broken, every message sent using it is broken, and a
> major - potentially immense - investment must be made to completely
> replace an infrastructure based on it.  On the other hand, even if a
> significant fraction of Mr. Ritter's individual ciphers are broken, many
> messages remain secure - and in a reasonable design for the infra-
> structure, it's possible to eliminate the bad ciphers from future use
> without rebuilding the entire infrastructure.
>
> Another way of looking at this is that the cost function is highly
> non-linear:  As long a reasonably large fraction of Mr. Ritter's ciphers
> are secure, the costs (in broken messages, in the effort needed to weed
> out ciphers that have proven to be weak) are small.  The cost grows very
> rapidly beyond a certain point, where most combinations are breakable.
> The problem with an AES, of course, is that there's only one "combina-
> tion", so you get right to the extremely high cost range.
>
> Ignoring the probability of ruin is at the heart of many bad probabilis-
> tic arguments - e.g., many naive arguments about martingales, and all
> sorts of bad investment strategies in the real world.

If choosing siphers is a game we should consider using the min-max
approach.  It states that we want to minimize the maximum damage that the
opponent can do to us.  In this regard several strong ciphers look vastly
better than one universal cipher no matter how much "better" it is.

Are 1000 ciphers better than (say) 10?  There's no single answer to that
question that will satisfy the majority of the readers of thie NG.  IHMHO,
the answer is yes.


> On the other hand, I think there are practical difficulties with Mr.
> Ritter's approach.  Even the cryptanalytic attacks known in the public
> literature are sufficiently powerful to slice right through most simple
> designs.  The ciphers that can survive *even the attacks we know about*
> are pretty rare on the ground.  Where will we find a large collection of
> reasonably secure ciphers to use for Mr. Ritter's scheme?
>
> Mr. Ritter likes to design parameterized families of ciphers - a
> powerful approach, and probably the only way to get a large number of
> reasonable cipher designs in hand quickly.  But that opens the door to
> attacks against whole families.
>
> If the collection of ciphers to be used in this scheme is fixed up
> front, it will be subject to attack - and likely many ciphers will be
> picked off.  So there will likely have to be a mechanism to add new
> ciphers to the mix.  However, that opens a powerful line of attack to a
> knowledgeable opponent:  He can contribute (through apparently unrelated
> 3rd parties, of course) a large number of apparently very good ciphers
> that he knows how to break.  Since no one will be in a position to do
> really deep analyses of many different ciphers, it's unlikely that the
> "spiked" ciphers will be found:  It took many years to become convinced
> that DES doesn't have a trap door, and even today there are people who
> retain their suspicions.  (Actually, an attacker of this sort wouldn't
> even have to wait for updates:  He would likely be right there at the
> initiation of the system, offering up a whole load of neat-looking
> ciphers.  It would require a big leap beyond the publically-known state
> of the art in cryptography to slip a trap door into a system like AES,
> which will be very closely examined by many people *and is expected to
> be really strong* - so any weakness that *is* found will immediately
> raise a red flag.  On the other hand, it would be relatively easy to
> slip many subtly spiked systems into Mr. Ritter's pool, since no one
> would look at them very closely - and, besides, even if one, or many, of
> the "spikes" were found, how could you distinguish that from those
> ciphers just being weak because the person who proposed them wasn't
> quite as good at crypto as he thought?)

There's a countervailing argument to this in that every compromised cipher
raises the risk of exposure of the person submitting trojans.  Every strong
cipher submitted to camoflage the compromised ones reduces the benefit of
the compromised ones by dilution.

In a large scale implementation of large numbers of ciphers we _expect_ some
to be revealed as weak.  Since such a revelation is expected, we'll simply
deal with it and move on.  Given layers of ciphers around each message the
actual amount of compromised traffic may be very small.

Finally the risk to the trojan submitter is extremely large if the submitter
has a reputation.  If the submitter has no reputation (proxy submission)
there is no reason to fear widespread adoption of a large number of flawed
ciphers.




Subject: Re: Ritter's paper
Date: Sun, 19 Sep 1999 00:31:26 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37e42eda.4507318@quake.io.com>
References: <37E157FC.7FDA@smarts.com>
Newsgroups: sci.crypt
Lines: 141


On Thu, 16 Sep 1999 16:50:04 -0400, in <37E157FC.7FDA@smarts.com>, in
sci.crypt Jerry Leichter <leichter@smarts.com> wrote:

>[...]
>Ignoring the probability of ruin is at the heart of many bad probabilis-
>tic arguments - e.g., many naive arguments about martingales, and all
>sorts of bad investment strategies in the real world.

Yes.  The question is whether we would bet our grandmother's income on
our *opinion* that a particular mathematical conundrum could not be
solved.  Would we do it, and would it be right if we did?

Cryptanalysis simply does not testify to the strength of an unbroken
cipher.  To have everyone use one of those ciphers serves to target
that cipher for more analysis that it will have had.  And if it does
fall (typically in secret), the whole information society is at risk.
Will the cryptanalysts who approved it then compensate the rest of us
for their error?  And if not, is it not time for us to look this gift
horse in the mouth?  


>On the other hand, I think there are practical difficulties with Mr.
>Ritter's approach.  Even the cryptanalytic attacks known in the public
>literature are sufficiently powerful to slice right through most simple
>designs.  The ciphers that can survive *even the attacks we know about*
>are pretty rare on the ground.  Where will we find a large collection of
>reasonably secure ciphers to use for Mr. Ritter's scheme?
>
>Mr. Ritter likes to design parameterized families of ciphers - a
>powerful approach, and probably the only way to get a large number of
>reasonable cipher designs in hand quickly.  But that opens the door to
>attacks against whole families.

Whether you think I like to design parameterized families of ciphers
mostly depends upon what you call a parameter:  I do argue for the use
of scalable ciphers, which would certainly be parameterized in size,
but specifically *not* parameterized in ways which would change their
operation.  I do point out that many new cipher constructions simply
have not been considered by academics, which is a loss for all of us,
not just me.  

I advocate getting all the analysis we can, not using ciphers we think
are weak, and using multiple ciphers in sequence.  It is this last
which quickly expands the body of overall "ciphers," and also tends to
protect individual ciphers from unknown weakness they may possess.  


>If the collection of ciphers to be used in this scheme is fixed up
>front, it will be subject to attack - and likely many ciphers will be
>picked off.  

Anything can be attacked; the question is how successful the attack
will be.  Most modern attacks are forms of known-plaintext or
defined-plaintext which cannot be mounted here.  If a cipher's only
weakness is to known-plaintext, it ceases to be weak when used in a
cipher stack.  

Multiciphering does, by itself, protect component ciphers against
known-plaintext attack, which is a very significant advantage.
Consequently, the (unknown) strength of a multi-cipher using one's
favorite cipher as one component is likely to be far stronger than the
(unknown) strength of that favorite cipher alone.  


>So there will likely have to be a mechanism to add new
>ciphers to the mix.  

Indeed, I see this as a necessary part of increasing the cost of doing
business for our cryptanalytic opponents.  


>However, that opens a powerful line of attack to a
>knowledgeable opponent:  He can contribute (through apparently unrelated
>3rd parties, of course) a large number of apparently very good ciphers
>that he knows how to break.  

I'm not at all sure that this is as easy as it is made to sound here.



>Since no one will be in a position to do
>really deep analyses of many different ciphers, it's unlikely that the
>"spiked" ciphers will be found:  

Again, we all suffer when academics will not address the many new
ciphering constructions which have blossomed in recent years.  


>It took many years to become convinced
>that DES doesn't have a trap door, and even today there are people who
>retain their suspicions.  (Actually, an attacker of this sort wouldn't
>even have to wait for updates:  He would likely be right there at the
>initiation of the system, offering up a whole load of neat-looking
>ciphers.  It would require a big leap beyond the publically-known state
>of the art in cryptography to slip a trap door into a system like AES,
>which will be very closely examined by many people *and is expected to
>be really strong* - so any weakness that *is* found will immediately
>raise a red flag.  

I think the exact same thing would be said for any cipher I would
suggest using.  


>On the other hand, it would be relatively easy to
>slip many subtly spiked systems into Mr. Ritter's pool, since no one
>would look at them very closely 

Again, it is a loss for all of us when academics who claim to study
cryptography do in fact generally restrict their attentions to small
steps around the area of old cryptography.  

On the other hand, we do not use ciphers which we expect are weak on
their own, unless their weakness is simply not exposed in the
multiciphering configuration.  We should not depend upon
multiciphering to shield them in unknown ways and make them stronger
than we already know.  


>- and, besides, even if one, or many, of
>the "spikes" were found, how could you distinguish that from those
>ciphers just being weak because the person who proposed them wasn't
>quite as good at crypto as he thought?)

It is unnecessary to distinguish the motive for a cipher being bad: if
we know a cipher is bad, we don't use it.  If we use it unknowingly,
it is at least in a multiciphering package with two other ciphers.  I
would expect that just having one trick cipher in the stack is not
going to be much help in penetrating the other two.  

Surely we can demand that the basic ciphering engines not expand data,
and thus allow no room for a secondary channel.  

I expect that the current crypto gods would as widely publicize their
own opinions of usable ciphers as they do today.  Many people would
take those recommendations, but others might have their own ideas.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: Mon, 20 Sep 1999 21:00:17 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <37E68441.668D8CD@t-online.de>
References: <37e42eda.4507318@quake.io.com>
Newsgroups: sci.crypt
Lines: 83

Terry Ritter wrote:
> 
> Whether you think I like to design parameterized families of ciphers
> mostly depends upon what you call a parameter:  I do argue for the use
> of scalable ciphers, which would certainly be parameterized in size,
> but specifically *not* parameterized in ways which would change their
> operation.  I do point out that many new cipher constructions simply
> have not been considered by academics, which is a loss for all of us,
> not just me.

I think that a general parametirized cipher by definition can have 
sizes (block sizes, key lengths, table sizes), round numbers and 
operations (statically or dynamically determined) selected by 
parameter values entered by the users. Limiting parametrization to 
sizes or a size is excluding benefits that may accrue from other 
parametrization dimensions. Parametrization delivers a least a part 
of the advantages of using multiple ciphers, for the analyst has to 
figure out the parameter values for attacking the cipher effectively, 
i.e. his work load is increased. Parametrization allows a cipher to 
adapt to advances in technology that become available to the analyst,
e.g. faster processor chips, and thus promises a longer useful 
service life of the cipher. That's why I have never yet understood 
why parametrization is not favoured in the AES project. 

In passing, I want to point out that both parametrization and
multiple ciphers can be subsumed by a concept of obtaining strength
that I like to term as the principle of variability. Due to
variability, the analyst has not a 'constant' target to deal with.
Consequently he needs more resources.

Concerning opinions given in a number of follow-ups in this thread, 
I like to say that my understanding of Mr. Ritter's paper is  
advocating for more openess to new ideas in the field of cipher 
designs. His few sentences about patents may be arguable, but that's 
not the major message of his paper in my view. (In fact, I disagree 
that breaking a patented cipher necessarily means infringement of 
the patent. For it is e.g. at least conceivable that one could under 
circumstances compute the key of a block cipher without actually 
implementing the patented cipher as such and use it. And if a 
employee of a company having a license is capable engough to break
a patented cipher, there is certainly no infringement of the patent 
and there is no cost involved for the analyst.) Mr. Ritter stressed
the advantage of using multiple ciphers (which tends to be ignored 
by the common users due to standardization efforts -- here using the 
forthcoming AES finalist as the single cipher) which in my humble 
opinion is evidently true. It is to be noted that using multiple 
ciphers does not mean deliberately seeking to use a combination of 
the poorer ciphers. It is an implicit assumption that the choice of 
the component ciphers is done with the usual care appropriate for 
the applications at hand. I don't see any reason why, for example, 
I shouldn't do multiple encipherment with the future finalist of AES 
and some of the candidates of AES that fail to be chosen as the 
finalist, excepting that there is probably some processing speed 
disadvantage.
 
In future one has probably on the one side to leave part of the 
current state of affairs exactly as it is, i.e. having the best 
academic cryptographers of the world continue to have their efforts 
concentrated on the analyst of one single cipher, namely the 
finalist of AES (if for no other reason than because it is their 
personal freedom to choose what they like to research), while on 
the other side it is, I believe, sensible and important for those 
who do not share the view of relying on a single standard cipher 
to continue to attempt to bring forth novel designs and to propagate 
the major points of Mr. Ritter's paper to the public so that these 
can be well informed even if they decide to stay always with the 
'golden' cipher for whatever reasons they have.

As an aside, there is one thing that I haven't yet fully understood
till present. There are people who praise the use of a cipher (DES) 
that has withstood long long years of heavily done cracking efforts
of the best of the profession. The same best cryptographers are
there for dealing with AES. But on the first day when the AES
finalist gets applied in the public, there will not yet be that 
amount of man years of analysis spent on it as compared to what 
DES has received up till now. So wouldn't it be sensible that there 
be a transition period where 3DES (since single DES is known to
be weak relative to current state of technology) and the finalist 
of AES co-exist as the 'standard' cipher?

M. K. Shen
----------------------------
http://home.t-online.de/home/mok-kong.shen


Subject: Re: Ritter's paper
Date: Wed, 29 Sep 1999 15:10:22 GMT
From: dscott@networkusa.net (SCOTT19U.ZIP_GUY)
Message-ID: <7st6l2$c9m$3@news.gate.net>
References: <37E68441.668D8CD@t-online.de>
Newsgroups: sci.crypt
Lines: 46

In article <37E68441.668D8CD@t-online.de>, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>Terry Ritter wrote:
>> 
>> Whether you think I like to design parameterized families of ciphers
>> mostly depends upon what you call a parameter:  I do argue for the use
>> of scalable ciphers, which would certainly be parameterized in size,
>> but specifically *not* parameterized in ways which would change their
>> operation.  I do point out that many new cipher constructions simply
>> have not been considered by academics, which is a loss for all of us,
>> not just me.
>
>I think that a general parametirized cipher by definition can have 
>sizes (block sizes, key lengths, table sizes), round numbers and 
>operations (statically or dynamically determined) selected by 
>parameter values entered by the users. Limiting parametrization to 
>sizes or a size is excluding benefits that may accrue from other 
>parametrization dimensions. Parametrization delivers a least a part 
>of the advantages of using multiple ciphers, for the analyst has to 
>figure out the parameter values for attacking the cipher effectively, 
>i.e. his work load is increased. Parametrization allows a cipher to 
>adapt to advances in technology that become available to the analyst,
>e.g. faster processor chips, and thus promises a longer useful 
>service life of the cipher. That's why I have never yet understood 
>why parametrization is not favoured in the AES project. 
>



   Mok
  I thought I would anwser this last question for you. The AES contest
is about finding a WEAK method so that it can be used for all encryption
in all aplications. Even small smart cards. If there was room to allow
parametrization the NSA would have a hader job of reading your files.
It is best for the NSA to have only one cipher in common use that they
can break so this country can maintain a fair competative edge over the
rest of the world. You don't really think we wish to battle the rest of the
world with out knowledge of all there secrets and weaknesses do you.



David A. Scott
--
                    SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
                    http://www.jim.com/jamesd/Kong/scott19u.zip
                    http://members.xoom.com/ecil/index.htm
                    NOTE EMAIL address is for SPAMERS


Subject: Re: Ritter's paper
Date: 30 Sep 99 03:38:21 GMT
From: jsavard@ecn.ab.ca ()
Message-ID: <37f2db2d.0@ecn.ab.ca>
References: <37f254bc.242889542@news.mpinet.net>
   <7st6l2$c9m$3@news.gate.net>
Newsgroups: sci.crypt
Lines: 57

Johnny Bravo (bravo.john@usa.net) wrote:
: On Wed, 29 Sep 1999 15:10:22 GMT, dscott@networkusa.net (SCOTT19U.ZIP_GUY)
: wrote:

: >  I thought I would anwser this last question for you. The AES contest
: >is about finding a WEAK method so that it can be used for all encryption
: >in all aplications. 

:   Please post your proof that the AES candidates are weak.  You can start with
: the ones who were accepted into the second round, since by your logic the strong
: ones would have been discarded first.  Take all the screens you need.

Actually, he is *half* right.

The AES candidate ciphers are very strong ciphers; if I enciphered a
message in any of them - even the ones proven to have flaws, such as
MAGENTA, or LOKI 97, or FROG - and offered a prize to someone who could
crack it, the prize would probably not be claimed.

They are well-crafted, and designed by some of the finest cryptographic
minds ... in the open academic community.

But no, I'm not saying that what's wrong with the AES candidate ciphers is
that they're not designed by the NSA.

A 56-bit key, and (more theoretically) a 64-bit blocksize are weak.

A 256-bit key, and a 128-bit blocksize are certainly much better. And if
the key size or block size were made much bigger, that would limit in what
circumstances the cipher could be used.

But at least in some applications, such as enciphering text on a PC - say,
for E-mail - there is little reason to limit oneself to such a short key,
or such a small block size! It makes sense not to allow such a large key
or block size for the AES competition, since with such parameters it would
be too easy to make something that is - or seems - secure...

but once the advanced design principles needed to attain security under
such restrictive circumstances are elucidated...

well, for _practical_ use, why fail to take advantage of the maximum
security your computer's power can give you?

And it's certainly true that *none* of the AES candidate ciphers even has
a nonlinearly key-dependent S-box with even 65,536 entries, never mind
524,288 entries!

This is why I say that he is _half_ right. Although the AES candidates are
excellent ciphers, the fact that they are, in terms of their key size and
block size, merely one step beyond DES, rather than two or three steps
beyond (say 256 bit block size, keys of 1,024, 2,048, and 4,096 bits)
could make some people nervous. Regardless of whether there's any _real_
justification for such nervousness (and in a world where, understandably,
the *best* cryptanalytic knowlege around is tightly under wraps, it's hard
to be sure there isn't).

John Savard


Subject: Re: Ritter's paper
Date: Thu, 30 Sep 1999 06:22:48 GMT
From: bravo.john@usa.net (Johnny Bravo)
Message-ID: <37f2ea20.10373469@news.mpinet.net>
References: <37f2db2d.0@ecn.ab.ca>
Newsgroups: sci.crypt
Lines: 92

On 30 Sep 99 03:38:21 GMT, jsavard@ecn.ab.ca () wrote:

>Johnny Bravo (bravo.john@usa.net) wrote:
>: On Wed, 29 Sep 1999 15:10:22 GMT, dscott@networkusa.net (SCOTT19U.ZIP_GUY)
>: wrote:
>
>: >  I thought I would anwser this last question for you. The AES contest
>: >is about finding a WEAK method so that it can be used for all encryption
>: >in all aplications. 
>
>:   Please post your proof that the AES candidates are weak.  You can start with
>: the ones who were accepted into the second round, since by your logic the strong
>: ones would have been discarded first.  Take all the screens you need.
>
>Actually, he is *half* right.

  How is he even 1/2 right, he claims that AES is nothing but a scam to get
people to accept a weak crypto method. 

>A 56-bit key, and (more theoretically) a 64-bit blocksize are weak.

  No AES candidate is using a 56 bit key.   And all of the candidates run 128+
bit blocks as well.  The whole reason we need an AES is that 56 bit keys are
weak, we already know this.  128 bit keys have been in common use since the beta
versions of PGP, we've known 56 bits wasn't going to be enough for over two
decades.

>A 256-bit key, and a 128-bit blocksize are certainly much better. And if
>the key size or block size were made much bigger, that would limit in what
>circumstances the cipher could be used.

  Why would you need either a bigger key or a bigger block size?  If you have
any possible proof that either 256 bit keys or 128 bit blocks are insecure the
crypto world would love to hear of it.

>But at least in some applications, such as enciphering text on a PC - say,
>for E-mail - there is little reason to limit oneself to such a short key,
>or such a small block size! It makes sense not to allow such a large key
>or block size for the AES competition, since with such parameters it would
>be too easy to make something that is - or seems - secure...

  There is nothing insecure about 256 bit keys or 128 bit blocks.  One of the
requirements was for the AES to work in a smartcard, we are talking about a 6805
processor with as little as 64 bytes (not kilobyte)s of ram, and 2k of rom.  At
least one of the AES candidates can still encrypt a 128 bit block, with a 256
bit key in less than 9ms under such restrictions with the processor running at
4Mhz.  
  And there is no card coded requirement for you to use a standard AES crypto
for your email program.  Many of the candidates can run keys of over 256 bits
with block sizes of a kilobyte each.  If you feel the need to, use one of those.
  
>but once the advanced design principles needed to attain security under
>such restrictive circumstances are elucidated...

  The restrictions are to ensure an efficient implementation with the present
technology while still retaining enough security to prevent any foreseeable
technology advance from compromising that security.  256 bit keys are thought to
be big enough to resist attack by quantum computers(assuming we ever see one).
The restrictions don't prevent the designs from being secure.

>well, for _practical_ use, why fail to take advantage of the maximum
>security your computer's power can give you?
>
>And it's certainly true that *none* of the AES candidate ciphers even has
>a nonlinearly key-dependent S-box with even 65,536 entries, never mind
>524,288 entries!

  And none of the AES candidates requires that the sender pass along a second
file to the recipient along a separate secure channel consisting of an amount of
data equal to the size of the original message.   Dave's algorithm is 100%
useless for bank issued smart cards, it is 100% useless to email anyone I don't
meet in person if I want to retain security.  
  There was nothing stopping him from submitting his algorithm if he thought it
was good enough.
  
  Dave's algorithm has all the limitations of the one time pad. Since the one
time pad is already 100% proven secure, why would I use anything else than
something already 100% secure against any and every possible cryptanalysis if it
has every single one of the drawbacks.

>This is why I say that he is _half_ right. Although the AES candidates are
>excellent ciphers, the fact that they are, in terms of their key size and
>block size, merely one step beyond DES, rather than two or three steps
>beyond 

  256 bits is not 4.5 times as secure as 56 bits. It is exactly 115,792,089,
237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,
511,950,319,091,712,000 times as secure.  This is a bit more than one step
beyond DES.

  Johnny Bravo



Subject: Re: Ritter's paper
Date: Thu, 30 Sep 1999 14:07:20 GMT
From: dscott@networkusa.net (SCOTT19U.ZIP_GUY)
Message-ID: <7svnb1$1m3g$1@news.gate.net>
References: <37f2ea20.10373469@news.mpinet.net>
Newsgroups: sci.crypt
Lines: 92

In article <37f2ea20.10373469@news.mpinet.net>, bravo.john@usa.net (Johnny Bravo) wrote:

...

>  Why would you need either a bigger key or a bigger block size?  If you have
>any possible proof that either 256 bit keys or 128 bit blocks are insecure the
>crypto world would love to hear of it.
    That is the kind of thinking that we suckered the germans into beliving
in WWII
>
>>But at least in some applications, such as enciphering text on a PC - say,
>>for E-mail - there is little reason to limit oneself to such a short key,
>>or such a small block size! It makes sense not to allow such a large key
>>or block size for the AES competition, since with such parameters it would
>>be too easy to make something that is - or seems - secure...
>
>  There is nothing insecure about 256 bit keys or 128 bit blocks.  One of the
>requirements was for the AES to work in a smartcard, we are talking about a
> 6805
     But way the hell would anyone other than a fool want to use the same
encryption for all applitcations. Unless it was to aid an attacker.
>processor with as little as 64 bytes (not kilobyte)s of ram, and 2k of rom.  At
>least one of the AES candidates can still encrypt a 128 bit block, with a 256
>bit key in less than 9ms under such restrictions with the processor running at
>4Mhz.  
>  And there is no card coded requirement for you to use a standard AES crypto
>for your email program.  Many of the candidates can run keys of over 256 bits
>with block sizes of a kilobyte each.  If you feel the need to, use one of
> those.
>  
>>but once the advanced design principles needed to attain security under
>>such restrictive circumstances are elucidated...
>
>  The restrictions are to ensure an efficient implementation with the present
>technology while still retaining enough security to prevent any foreseeable
>technology advance from compromising that security.  256 bit keys are thought
> to
>be big enough to resist attack by quantum computers(assuming we ever see one).
>The restrictions don't prevent the designs from being secure.
    Really 256 bits is thought to be resistant to foreseeable attacks by 
quantum computers. Sounds the kind of lies some 3 letter group would spread.
But way does one have to use something so small when history has proven
over and over that things in cryptography thought safe till the sum burned out
some how fell short of estimates. Why should this time it by any different.

>
>>well, for _practical_ use, why fail to take advantage of the maximum
>>security your computer's power can give you?
>>
>>And it's certainly true that *none* of the AES candidate ciphers even has
>>a nonlinearly key-dependent S-box with even 65,536 entries, never mind
>>524,288 entries!
>
>  And none of the AES candidates requires that the sender pass along a second
>file to the recipient along a separate secure channel consisting of an amount
> of
>data equal to the size of the original message.   Dave's algorithm is 100%
>useless for bank issued smart cards, it is 100% useless to email anyone I don't
>meet in person if I want to retain security.  
      Actually in most publuc key methods the pyblic key is so large something
much larger than the actully key is sent. Since my method can use a variable
size key you could send the key the way public key enctyption is done know.
As the key sizes get larger for public key encryption as they will do to 
advacnes in factoring and whatever you then send longer keys and use my
method. No problem.
>  There was nothing stopping him from submitting his algorithm if he thought it
>was good enough.
      Yes there was they want it in ps I wanted to send it in Ascii so there
where many blocks. I cheased the carrot for a while but I would not have
sent scott16u it is to strong for the kind of toy cipher the AES wants to
look at.

>  
>  Dave's algorithm has all the limitations of the one time pad. Since the one
>time pad is already 100% proven secure, why would I use anything else than
>something already 100% secure against any and every possible cryptanalysis if
      Actually the key is orders of magnitude smalles than the OTP and the OTP
is really limited to one message per key. Mine does not have that restriction 
but then again you would have to know something about crypto to understand
that.


  Be Brave John



David A. Scott
--
                    SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
                    http://www.jim.com/jamesd/Kong/scott19u.zip
                    http://members.xoom.com/ecil/index.htm
                    NOTE EMAIL address is for SPAMERS


Subject: Re: Ritter's paper
Date: 1 Oct 99 12:51:08 GMT
From: jsavard@ecn.ab.ca ()
Message-ID: <37f4ae3c.0@ecn.ab.ca>
References: <37f2ea20.10373469@news.mpinet.net>
Newsgroups: sci.crypt
Lines: 18

Johnny Bravo (bravo.john@usa.net) wrote:
:   256 bits is not 4.5 times as secure as 56 bits. It is exactly 115,792,089,
: 237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,
: 511,950,319,091,712,000 times as secure.  This is a bit more than one step
: beyond DES.

You've made many good points. It is true that the AES candidates are
highly secure ciphers, and that each additional bit in the key doubles the
time required to crack a cipher by brute force.

I simply point out why some people might want to go even further: after
all, the predecessor to DES, LUCIFER, already had a 128-bit key and a
128-bit block size. Of course, outrageous conclusions, like calling the
AES a scam, aren't 50% right. But that isn't always the meaning of the
phrase "half right": I'm simply noting that even Mr. Scott didn't start
from premises which were completely false.

John Savard


Subject: Re: Ritter's paper
Date: Fri, 1 Oct 1999 18:17:52 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FIxs5s.7ru@bath.ac.uk>
References: <37f2ea20.10373469@news.mpinet.net>
Newsgroups: sci.crypt
Lines: 24

Johnny Bravo <bravo.john@usa.net> wrote:
: On 30 Sep 99 03:38:21 GMT, jsavard@ecn.ab.ca () wrote:

:>Although the AES candidates are excellent ciphers, the fact that they
:>are, in terms of their key size and block size, merely one step beyond
:>DES, rather than two or three steps beyond 

:   256 bits is not 4.5 times as secure as 56 bits. It is exactly 115,792,089,
: 237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,
: 511,950,319,091,712,000 times as secure.  This is a bit more than one step
: beyond DES.

256 bits of key may not be /that/ much stronger.

Your mathematics depends on the assomption that the security of a cypher
depends linearly on the size of its keyspace.  As few cyphers are broken
by brute force searches through all the possible keys, it really is
unlikely to be valid to conclude that increasing the size of the keyspace
increases the security in direct proportion.
-- 
__________
 |im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

Girls seldom show dimples to boys who have pimples.


Subject: Re: Ritter's paper
Date: Mon, 4 Oct 1999 17:15:39 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FJ39A3.MM3@bath.ac.uk>
References: <jgfunj-3009991811140001@dial-243-022.itexas.net>
   <37f254bc.242889542@news.mpinet.net>
   <7st6l2$c9m$3@news.gate.net>
Newsgroups: sci.crypt
Lines: 20

wtshaw <jgfunj@vgrknf.arg> wrote:

: Strength and weakness being relative things, it does seem that the AES
: goals are barely out of the parking lot, much less down the highway.

I feel someone needs to do some block-cypher advocacy on their behalf.

I really have difficulty in seeing what point there was in specifying
in advance that cyphers must encrypt in 128-bit blocks.

: I will likely disagree with many on what strength is, for it is a
: combination of many things.  I continue to fight for a reasonable
: composite definition of strength.

"Strength: ability to resist breaks and cracks"?
-- 
__________
 |im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

2 x 3 x 3 x 37 - prime factorisation of the Beast.


Subject: Re: Ritter's paper
Date: Mon, 04 Oct 1999 14:51:08 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <37F8F71C.A081E33E@aspi.net>
References: <FJ39A3.MM3@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 25

Tim Tyler wrote:

> wtshaw <jgfunj@vgrknf.arg> wrote:
>
> : Strength and weakness being relative things, it does seem that the AES
> : goals are barely out of the parking lot, much less down the highway.
>
> I feel someone needs to do some block-cypher advocacy on their behalf.
>
> I really have difficulty in seeing what point there was in specifying
> in advance that cyphers must encrypt in 128-bit blocks.
>
> : I will likely disagree with many on what strength is, for it is a
> : combination of many things.  I continue to fight for a reasonable
> : composite definition of strength.
>
> "Strength: ability to resist breaks and cracks"?

Yeah.  But how to you measure it?  What are the units of "ability to resist
breaks"?  So far we only have the inverse, which allows us to compare a
subset of the weaknesses of ciphers -- the subset being those weaknesses that
are known, which excludes the subset of weaknesses yet to be discovered.

A strength metric would address the currently excluded subset.  The unknowns.



Subject: Re: Ritter's paper
Date: Tue, 05 Oct 1999 01:06:22 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-0510990106220001@dial-243-058.itexas.net>
References: <37F8F71C.A081E33E@aspi.net>
Newsgroups: sci.crypt
Lines: 30

In article <37F8F71C.A081E33E@aspi.net>, "Trevor Jackson, III"
<fullmoon@aspi.net> wrote:

> Tim Tyler wrote:
> >
> > "Strength: ability to resist breaks and cracks"?
> 
> Yeah.  But how to you measure it?  What are the units of "ability to resist
> breaks"?  So far we only have the inverse, which allows us to compare a
> subset of the weaknesses of ciphers -- the subset being those weaknesses that
> are known, which excludes the subset of weaknesses yet to be discovered.
> 
> A strength metric would address the currently excluded subset.  The unknowns.

It may be hard to put out one scale, like tastes vary in complicated
ways.  But, I have suggested. Normally, all we here is so much time and
how many trials using all the levers one can get to cut those numbers.

In the essence of the Shannon work, how much ciphertext is necessary to
*prove* plaintext is important.  Again these results tend to be empiricle.

Scoring ciphers according to an ideal algorithm may present a balanced
picture that helps people select cryptosystems for specific uses.

Like I said, it is a big topic, so there should be more ways developed to
describe strength as time goes by.  We should not be afraid to try, and
mull them over.
-- 
Sometimes a small mistake can lead to fortunate reward.
  Charlie Chan


Subject: Re: Ritter's paper
Date: Tue, 5 Oct 1999 14:15:48 GMT
From: "Douglas A. Gwyn" <gwyn@arl.mil>
Message-ID: <37FA0814.A0C13A75@arl.mil>
References: <jgfunj-0510990106220001@dial-243-058.itexas.net>
Newsgroups: sci.crypt
Lines: 8

wtshaw wrote:
> In the essence of the Shannon work, how much ciphertext is necessary to
> *prove* plaintext is important.  Again these results tend to be empiricle.

The only thing empirical is the statistical characteristics of the
natural language (e.g. English).  If you have a complete source
model, we know how to *compute* information-theoretic measures
from it.


Subject: Re: Ritter's paper
Date: Tue, 05 Oct 1999 18:08:26 GMT
From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard)
Message-ID: <37fa3e74.8984734@news.prosurfr.com>
References: <37FA0814.A0C13A75@arl.mil>
Newsgroups: sci.crypt
Lines: 20

"Douglas A. Gwyn" <gwyn@arl.mil> wrote, in part:

>wtshaw wrote:
>> In the essence of the Shannon work, how much ciphertext is necessary to
>> *prove* plaintext is important.  Again these results tend to be empiricle.
>
>The only thing empirical is the statistical characteristics of the
>natural language (e.g. English).

Yes, but isn't that enough to make the results empirical, since

>If you have a complete source
>model, we know how to *compute* information-theoretic measures
>from it.

it's rather difficult to produce a complete source model of English
text?

John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm


Subject: Re: Ritter's paper
Date: Sat, 09 Oct 1999 00:49:07 GMT
From: jerome@mycpu.org (jerome)
Message-ID: <slrn7vt4d4.3uf.jerome@jerome.psti.com>
References: <37FE0A00.83468039@arl.mil>
   <jgfunj-0510990106220001@dial-243-058.itexas.net>
Newsgroups: sci.crypt
Lines: 13

On Fri, 8 Oct 1999 15:13:04 GMT, Douglas A. Gwyn (IST/CNS) wrote:
>
>The point is, once one has collected the empirical natural-language
>statistical data, it can be *used* to construct a source model that
>does a decent job of substituting for the actual language.  We just
>had a thread with an example showing that even a simple trigraph
>frequency model already embodies a lot about the language.  With
>more advanced Markov models, especially HMMs (probabilistic functions
>of normal Markov models), we can easily come so close to the actual
>population statistics/information measures that there is no difference
>in practical applications in cryptography.

any reference about the usage of the Hidden Markov Models in cryptography ?


Subject: Re: Ritter's paper
Date: Sat, 09 Oct 1999 03:40:56 GMT
From: "Douglas A. Gwyn" <DAGwyn@null.net>
Message-ID: <37FEB95A.52233E8E@null.net>
References: <slrn7vt4d4.3uf.jerome@jerome.psti.com>
Newsgroups: sci.crypt
Lines: 42

jerome wrote:
> any reference about the usage of the Hidden Markov Models in
> cryptography ?

The applications are numerous, and once you're familiar with the
technology it isn't hard to find opportunities to use it, for
example to classify suspected textual units into functional
categories (noun, verb, consonant, vowel, digit, punctuation,
null, whatever).  The original papers when published in the open
literature around 1967 had all cryptologic applications
carefully expunged, alas.  If you can find a copy of the NSA
Technical Journal "Special Computer and Information Sciences
Issue" (1975), which was an unclassified collection of NSATJ
articles given out to some job applicants etc., pp. 69-86
constitute an article by E. P. Neuburg, "Markov Models for
Phonetic Text", which cites another article by R. L. Cave and
L. P. Neuwirth, "Three New Statistical Models for English",
IDA-CRD Working Paper No. 233 (June 1968).  I doubt you can
get hold of the latter document, but I've seen references in
the open literature to the analysis of English by Cave and
Neuwirth, for example in the syllabus for a course at CMU LTI,
so there may be an open publication somewhere.  You might also
check for a Cave-Neuwirth reference in Jelinek's book,
"Statistical Methods for Speech Recognition" (MIT Press, 1997)
- my copy is at the office.  (Jelinek certainly has a lot to
say about the use of HMMs in *speech signal* analysis [which
tends to be limited to a subset of possible HMM models], but
not in cryptology.)

An interesting paper slanted more toward theory than practice,
but with a suggestive example, is:  S. Kullback, M. Kupperman,
and H. H. Ku, "Tests for Contingency Tables and Markov Chains",
Technometrics, Vol. 4, No. 4 (November, 1962).

There are more relevant unclassified papers in the NSATJ, but
unless you want to go through a tedious FOIA process they're
probably unavailable.  I got one formerly TSC article
declassified (lightly redacted) on 14 Aug. 1998, and there is
a slim chance that a copy has by now found its way into RG 457
in NARA II:  Mary E. D'Imperio, "An Application of PTAH to the
Voynich Manuscript", NSATJ Vol. XXIV, No. 2 (Spring 1979),
pp. 65-92.  Jim Reeds summarizes it briefly in his Voynich page.


Subject: Re: Ritter's paper
Date: 9 Oct 99 14:19:39 GMT
From: jsavard@ecn.ab.ca ()
Message-ID: <37ff4efb.0@ecn.ab.ca>
References: <37FEB95A.52233E8E@null.net>
Newsgroups: sci.crypt
Lines: 22

Douglas A. Gwyn (DAGwyn@null.net) wrote:
: The original papers when published in the open
: literature around 1967 had all cryptologic applications
: carefully expunged, alas.

Well, that's understandable: but if one, from the mathematical literature,
understands the concepts involved, I would think that coming up with at
least some of the simpler cryptologic applications might not be too hard
(even if the most important ones might be missed for a while).

At the moment, I only recall the very simple example of a Markov model
given in Scientific American wherein one, starting with balls numbered
from 00 to 99 in one of two containers, switched a ball from one container
to the opposite one when its number was selected.

That nicely illustrated how pressure would equalize between two vessels
after the valve between them was opened, so it was nice for understanding
thermodynamics and statistical mechanics, but _that_ kind of model
certainly was far away from anything cryptological. Unless one is
enciphering cocktail party conversation which is starting to get boring.

John Savard


Subject: Re: Ritter's paper
Date: 9 Oct 99 20:51:42 GMT
From: jsavard@ecn.ab.ca ()
Message-ID: <37ffaade.0@ecn.ab.ca>
References: <37ff4efb.0@ecn.ab.ca>
Newsgroups: sci.crypt
Lines: 52

jsavard@ecn.ab.ca wrote:
: Douglas A. Gwyn (DAGwyn@null.net) wrote:
: : The original papers when published in the open
: : literature around 1967 had all cryptologic applications
: : carefully expunged, alas.

: Well, that's understandable: but if one, from the mathematical literature,
: understands the concepts involved, I would think that coming up with at
: least some of the simpler cryptologic applications might not be too hard
: (even if the most important ones might be missed for a while).

: At the moment, I only recall the very simple example of a Markov model
: given in Scientific American wherein one, starting with balls numbered
: from 00 to 99 in one of two containers, switched a ball from one container
: to the opposite one when its number was selected.

: That nicely illustrated how pressure would equalize between two vessels
: after the valve between them was opened, so it was nice for understanding
: thermodynamics and statistical mechanics, but _that_ kind of model
: certainly was far away from anything cryptological. Unless one is
: enciphering cocktail party conversation which is starting to get boring.

Thus, instead of the Markov chain, one wants something more "steady-state"
to model a language. My pet model of English text for compression purposes
works like this:

First one draws from a drum packed with word lengths distributed as in
English. This starts a counter.

Then, one draws from a drum with letters distributed according to the
initial letter frequency in English.

Then, as long as the counter allows, one draws from one of 26 drums,
labelled with the previous letter one has drawn.

Thinking of the model this way helps one to see where it is lacking. The
word length is chosen independently of letters, so one should really do
something more 'organic'; first draw for how many syllables are in the
word, then draw from a drum with slips in it labelled v, cv, vc, and cvc,
and then one has drums for the part before the vowel, the vowel, and the
part after the vowel of a syllable...

or, if one doesn't wish to parse syllables when compressing, there is
still the fact that the high frequency of T as an initial letter comes
from short words like "the" and "that", so one should really have a
separate initial-letter drum for each word length...

It seems, though, that Markov models are primarily relevant to cryptology
by helping us improve our compresssion algorithms, from this preliminary
glance.

John Savard

	 <37ff4efb.0@ecn.ab.ca> <37ffaade.0@ecn.ab.ca>

Subject: Re: Ritter's paper
Date: Sun, 10 Oct 1999 02:35:25 GMT
From: "Douglas A. Gwyn" <DAGwyn@null.net>
Message-ID: <37FFFB80.55B6A8BA@null.net>
References: <jgfunj-0510990106220001@dial-243-058.itexas.net>
Newsgroups: sci.crypt
Lines: 24

jsavard@ecn.ab.ca wrote:
> It seems, though, that Markov models are primarily relevant to
> cryptology by helping us improve our compresssion algorithms,
> from this preliminary glance.

No, that's one of their lesser applications.
The thing about a *hidden* Markov model is that
it models internal states of a system that are
seen only indirectly via the output of the system,
and both state transitions and outputs from a
given state are probabilistic.
The Welch/Baum/Eagon algorithm can be used to
"train" the model for a maximum likelihood set of
parameters by feeding it a set of observed data,
e.g. ciphertext.  The resulting model parameters
can tell us all sorts of interesting things about
the operation of the cryptosystem.  For example,
we might find that the states cluster into two
groups, with high mutual transition likelihoods
within each group and low likelihood of transition
from one group to another.  That would be very
interesting information that we didn't have before,
and it might help us figure out how the system
operates.


Subject: Re: Ritter's paper
Date: Wed, 06 Oct 1999 12:38:28 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <37FB7B04.EAB00328@aspi.net>
References: <FJ6tF8.FGn@bath.ac.uk>
   <37F8F71C.A081E33E@aspi.net>
Newsgroups: sci.crypt
Lines: 37

Tim Tyler wrote:

> Trevor Jackson, III <fullmoon@aspi.net> wrote:
> : Tim Tyler wrote:
> :> wtshaw <jgfunj@vgrknf.arg> wrote:
>
> :> : I will likely disagree with many on what strength is, for it is a
> :> : combination of many things.  I continue to fight for a reasonable
> :> : composite definition of strength.
> :>
> :> "Strength: ability to resist breaks and cracks"?
>
> : Yeah.  But how to you measure it?  What are the units of "ability to resist
> : breaks"?
>
> It seems to me that probably the best units in which to measure this
> are monetary ones.

Ahem.  The ultimate in subjective standards.  "The value of a thing is what that
thing will bring".  This does not lead to an engineering figure of merit, nor
even to scientific reproducibility.

Do you believe that it is possible to have an efficient market in crypto
strength?  Never mind the practical aspects that make it impossible, just
consider the theoretical impediments to having an efficient market, defined as
one in which the paricipants have access to all of the information available and
act rationally, in a commodity that is the exact opposite of trust: secrecy.


>
>
> "Time" and "certainty" may also figure in the equation - but are probably
> secondary characteristics most of the time.

Let's see, the two characteristics that crypto customers are paying for are
secondary?



Subject: Re: Ritter's paper
Date: 8 Oct 1999 14:44:48 -0400
From: juola@mathcs.duq.edu (Patrick Juola)
Message-ID: <7tle30$a7b$1@quine.mathcs.duq.edu>
References: <37FE1428.A804351F@aspi.net>
   <37FB7B04.EAB00328@aspi.net>
Newsgroups: sci.crypt
Lines: 22

In article <37FE1428.A804351F@aspi.net>,
Trevor Jackson, III <fullmoon@aspi.net> wrote:
>> : This does not lead to an engineering figure of merit, nor even to
>> : scientific reproducibility.
>>
>> Indeed not.  Do you have a metric which does to propose?  If not I am
>> liable to doubt that such a metric even exists.
>
>I do not.  It appears to me that it may be possible to prove that such a metric
>cannot exist.  But right now the best I can do is mumble about negative information
>space.

I think that I would argue that any attempt to reduce "cypher strength"
to a scalar quantity is ignorant and misguided.  Differen cyphers
have different areas of application, and different strengths depending
on the use.

One might as well try to come up with a metric for the best baseball
player.  Eventually it will come down to a question of how you compare
pitchers to outfielders (or whatever).

	-kitten


Subject: Re: Ritter's paper
Date: Fri, 08 Oct 1999 19:31:27 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <37FE7ECF.D81B4E21@aspi.net>
References: <7tle30$a7b$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 33

Patrick Juola wrote:

> In article <37FE1428.A804351F@aspi.net>,
> Trevor Jackson, III <fullmoon@aspi.net> wrote:
> >> : This does not lead to an engineering figure of merit, nor even to
> >> : scientific reproducibility.
> >>
> >> Indeed not.  Do you have a metric which does to propose?  If not I am
> >> liable to doubt that such a metric even exists.
> >
> >I do not.  It appears to me that it may be possible to prove that such a metric
> >cannot exist.  But right now the best I can do is mumble about negative information
> >space.
>
> I think that I would argue that any attempt to reduce "cypher strength"
> to a scalar quantity is ignorant and misguided.  Differen cyphers
> have different areas of application, and different strengths depending
> on the use.
>
> One might as well try to come up with a metric for the best baseball
> player.  Eventually it will come down to a question of how you compare
> pitchers to outfielders (or whatever).
>
>         -kitten

OK, there are separate application domains whose metrics will always be distinct.  So
pick a single domain, without making it trivially small, and define a domain-specific
metric.

Pitchers can be compared to pitchers along several (~10?) dimensions.  These comparisons
are based on the premise that each pitchers past performance is indicative of his future
performance.  The permise does not appear to apply to cipher strength.  In any domain.



Subject: Re: Ritter's paper
Date: Fri, 08 Oct 1999 23:56:47 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <37FEBCFF.63412C19@aspi.net>
References: <jgfunj-0810992117060001@dial-243-049.itexas.net>
   <37FE7ECF.D81B4E21@aspi.net>
Newsgroups: sci.crypt
Lines: 61

wtshaw wrote:

> In article <37FE7ECF.D81B4E21@aspi.net>, "Trevor Jackson, III"
> <fullmoon@aspi.net> wrote:
>
> > OK, there are separate application domains whose metrics will always be
> distinct.  So
> > pick a single domain, without making it trivially small, and define a
> domain-specific
> > metric.
> >
> > Pitchers can be compared to pitchers along several (~10?) dimensions.
> These comparisons
> > are based on the premise that each pitchers past performance is
> indicative of his future
> > performance.  The permise does not appear to apply to cipher strength.
> In any domain.
>
> Come on now, there are lots of ciphers of relative strengths, some
> stronger than others by any measure you might take.

I disagree.  We can inventory the weaknesses of ciphers, and thus measure the
upper bounds on their strength, but I do not see any way to establish a lower
bound on strength, which is the operational meaning of "known strength".

I am not referring to key length, number of rounds, complexity of rounds,
diffusion rate, etc.  I'm referring to the ratio of the work factor between
having and lacking the key.  If we could rule out catastrophic algorithmic
failures induced by new attacks such as differential, linear, slide,
boomerang, etc. we could thereby establish the minimal work factor ratio.  But
it does not appear that we can rule out those kinds of failure except in cases
where key size meets or exceeds message size.

PRNG-based ciphers are considered insecure for two reasons.  1) The potential
unknown of the initial state is, in principle, reduced by half for each bit of
output generated.  2)  In practice, we have methods of detemining the initial
state given the necessary number of bits of output, e.g., Berklecamp-Massey.

Note that #1 above applies to all modern ciphers given a known plaintext.  The
discovery of a new attack upon a cipher is the discovery of a practical method
of untangling the initial state given some amount of output > the amount of
key.  By this line of reasoning we could define the "efficiency" of an attack
as the ratio of the number of bits of output required over the number of bits
of state to be discovered.

Since all modern ciphers are weak in the sense of #1 above, they may always be
vulnerable to a discovery that reduces the theory to practice.  This is the
sense in which, AFAICS, we cannot prove strength (lower bound), but we can
prove weakness (upper bound).


> To deny the importance
> of looking at these dimension means that *you* will not find them.
>
> Ritter has said that there are no good measures of strength...so, that
> points to something that needs attention, not that we should adopt a
> self-fulfilling prophesy that we will never know.

Agreed.  I'm not claiming that we will never know.  I'm claiming that it looks
pretty bleak.



Subject: Re: Ritter's paper
Date: 9 Oct 99 14:13:24 GMT
From: jsavard@ecn.ab.ca ()
Message-ID: <37ff4d84.0@ecn.ab.ca>
References: <37FEBCFF.63412C19@aspi.net>
Newsgroups: sci.crypt
Lines: 41

Trevor Jackson, III (fullmoon@aspi.net) wrote:
: wtshaw wrote:
: > Ritter has said that there are no good measures of strength...so, that
: > points to something that needs attention, not that we should adopt a
: > self-fulfilling prophesy that we will never know.

: Agreed.  I'm not claiming that we will never know.  I'm claiming that it looks
: pretty bleak.

While I agree that we can learn more about cipher strength - in the sense
of having better *upper* bounds on strengths for a lot of ciphers - as to
the question of a lower bound on the work factor of finding the key, given
theoretically adequate quantities of known plaintext,

there is, I'm afraid, a sense in which it is valid to say we will "never
know". The problem of establishing a lower bound on a cipher's strength
is, I believe, fundamentally equivalent to the famous "halting problem".

This isn't defeatism, any more than the fact that chaos theory prevents us
from giving precise local weather forecasts for a year from now is
defeatism. Knowing what is unlikely or impossible to achieve liberates us
to work on solvable problems, and ask reasonable questions.

If we can't "prove" a cipher is secure for work-factor causes, then we
can:

- use the one-time-pad, if we're really desperate;

- include larger "safety factors" in our designs;

- using multiple layers of encryption that are based on completely
different principles that at least _appear_ to make the prospects for
analysis very dim.

Eventually, however, mathematicians working in complexity theory may make
a fundamental breakthrough that will suggest possibilities, either for
proving cipher strength, or for some kind of "next best thing". In the
meantime, knowing the direct approach to the problem cannot be fruitful
just prevents a lot of wasted time.

John Savard


Subject: Re: Ritter's paper
Date: Sat, 09 Oct 1999 22:39:59 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-0910992240000001@dial-243-018.itexas.net>
References: <37ff4d84.0@ecn.ab.ca>
Newsgroups: sci.crypt
Lines: 50

In article <37ff4d84.0@ecn.ab.ca>, jsavard@ecn.ab.ca () wrote:

> Trevor Jackson, III (fullmoon@aspi.net) wrote:
> : wtshaw wrote:
...
> 
> While I agree that we can learn more about cipher strength - in the sense
> of having better *upper* bounds on strengths for a lot of ciphers - as to
> the question of a lower bound on the work factor of finding the key, given
> theoretically adequate quantities of known plaintext,

Which might be an absurd amount to contemplate....
> 
> there is, I'm afraid, a sense in which it is valid to say we will "never
> know". The problem of establishing a lower bound on a cipher's strength
> is, I believe, fundamentally equivalent to the famous "halting problem".

I think it is fitting to leave an analyst flustered.
> 
> This isn't defeatism, any more than the fact that chaos theory prevents us
> from giving precise local weather forecasts for a year from now is
> defeatism. Knowing what is unlikely or impossible to achieve liberates us
> to work on solvable problems, and ask reasonable questions.

Like discussing why it might be impossible or unlikely to break some ciher
that just does not follow the expectant low amount of ciphertext necessary
to break it. :)

The special case is pushed just because it stands as a mighty oak in a
forest of dandelions.

Not neglecting why one poor cipher is not quite as bad as another one, we can:
> 
> - use the one-time-pad, if we're really desperate;
> 
> - include larger "safety factors" in our designs;
> 
> - using multiple layers of encryption that are based on completely
> different principles that at least _appear_ to make the prospects for
> analysis very dim.
> 
> Eventually, however, mathematicians working in complexity theory may make
> a fundamental breakthrough that will suggest possibilities, either for
> proving cipher strength, or for some kind of "next best thing". In the
> meantime, knowing the direct approach to the problem cannot be fruitful
> just prevents a lot of wasted time.
> 
Pardon the grammar, them is us, and anyone else who might take up the challenge.
-- 
Figures lie, and liars figure.--Daria Dolan


Subject: Re: Ritter's paper
Date: Sun, 10 Oct 1999 16:57:14 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FJECFE.3y1@bath.ac.uk>
References: <37ff4d84.0@ecn.ab.ca>
Newsgroups: sci.crypt
Lines: 35

jsavard@ecn.ab.ca wrote:
: Trevor Jackson, III (fullmoon@aspi.net) wrote:
: : wtshaw wrote:

: : > Ritter has said that there are no good measures of strength...so, that
: : > points to something that needs attention, not that we should adopt a
: : > self-fulfilling prophesy that we will never know.

: : Agreed.  I'm not claiming that we will never know.  I'm claiming that
: : it looks pretty bleak.

: While I agree that we can learn more about cipher strength - in the sense
: of having better *upper* bounds on strengths for a lot of ciphers - as to
: the question of a lower bound on the work factor of finding the key, given
: theoretically adequate quantities of known plaintext,

: there is, I'm afraid, a sense in which it is valid to say we will "never
: know". The problem of establishing a lower bound on a cipher's strength
: is, I believe, fundamentally equivalent to the famous "halting problem".

Turing's halting problem is often used to express hopelessness at finding
an answer - in much the same was as calling a problem NP.

However, it's not clear in what sense you're claiming equivalence.

There are many, *many* computer programs for which we can /prove/ that
they do, or do not halt.

If there were many, *many* cyphers where we could prove they had a
security greater than <X>, then this would be a *big* step forwards...
-- 
__________
 |im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

Meditation is not what you think.


Subject: Re: Ritter's paper
Date: 11 Oct 99 15:51:46 GMT
From: jsavard@ecn.ab.ca ()
Message-ID: <38020792.0@ecn.ab.ca>
References: <FJECFE.3y1@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 14

Tim Tyler (tt@cryogen.com) wrote:
: If there were many, *many* cyphers where we could prove they had a
: security greater than <X>, then this would be a *big* step forwards...

But that's precisely what we cannot do, except for _extremely_ low values
of <X>. Because the requirement for doing this is to know that, no matter
how much new we may learn about mathematics in the future, we will not
find a better way of cracking that particular cipher.

Essentially, we would have to have finished learning all about mathematics
first, and Godel and others have proved that mathematics is limitlessly
open-ended.

John Savard


Subject: Re: Ritter's paper
Date: Mon, 11 Oct 1999 18:44:58 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FJGC2y.7y0@bath.ac.uk>
References: <7tskrk$2q4$1@quine.mathcs.duq.edu>
   <FJECFE.3y1@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 39

Patrick Juola <juola@mathcs.duq.edu> wrote:
: In article <FJECFE.3y1@bath.ac.uk>, Tim Tyler  <tt@cryogen.com> wrote:
:>jsavard@ecn.ab.ca wrote:
:>: Trevor Jackson, III (fullmoon@aspi.net) wrote:
:>: : wtshaw wrote:

:>: there is, I'm afraid, a sense in which it is valid to say we will "never
:>: know". The problem of establishing a lower bound on a cipher's strength
:>: is, I believe, fundamentally equivalent to the famous "halting problem".
:>
:>Turing's halting problem is often used to express hopelessness at finding
:>an answer - in much the same was as calling a problem NP.

: Not by anyone who actually knows what NP or the halting problems
: means....  All NP problems, for instance, are known to be
: solvable; the halting problem and its equivalents are known to
: *NOT* be solvable..

Both the Turing halting problem and calling a problem NP-complete
*are* fairly frequently invoked in conjunction with statements like
"so we may as well give up, then" - tiz a fact ;-)

As I mentioned if finding a lower limit on the strength of a *particular*
cypher were only as hard as determining if a *particular* program halts,
that would be wonderful!

John has subsequently clarified that he meant that, finding a lower limit
on the strength of a *particular* cypher is as hard as determining if
an *arbitrary* program halts - which is known to be an impossible problem.

Now, I'm still rather far from convinced that this analogy is a good one -
and think that for some simple cyphers you /may/ eventually actually be
able to prove minimum bounds for strength to everyone's satisfaction - but
at least it's now very clear what he meant.
-- 
__________
 |im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

Remember, to a computer, 1 + 1 = 10.


Subject: Re: Ritter's paper
Date: Tue, 12 Oct 1999 00:09:44 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-1210990009440001@dial-243-062.itexas.net>
References: <FJGC2y.7y0@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 47

In article <FJGC2y.7y0@bath.ac.uk>, tt@cryogen.com wrote:

> Patrick Juola <juola@mathcs.duq.edu> wrote:
> : In article <FJECFE.3y1@bath.ac.uk>, Tim Tyler  <tt@cryogen.com> wrote:
> :>jsavard@ecn.ab.ca wrote:
> :>: Trevor Jackson, III (fullmoon@aspi.net) wrote:
> :>: : wtshaw wrote:
> 
> :>: there is, I'm afraid, a sense in which it is valid to say we will "never
> :>: know". The problem of establishing a lower bound on a cipher's strength
> :>: is, I believe, fundamentally equivalent to the famous "halting problem".
> :>
> :>Turing's halting problem is often used to express hopelessness at finding
> :>an answer - in much the same was as calling a problem NP.

When you can't break a message, delivering the results comes to a halt.
Exploring wartime evidence, we see lots of actual data about strength, and
when knowing the cipher and having ciphertext was solely not enough.
> 
> : Not by anyone who actually knows what NP or the halting problems
> : means....  All NP problems, for instance, are known to be
> : solvable; the halting problem and its equivalents are known to
> : *NOT* be solvable..
> 
> Both the Turing halting problem and calling a problem NP-complete
> *are* fairly frequently invoked in conjunction with statements like
> "so we may as well give up, then" - tiz a fact ;-)
> 
> As I mentioned if finding a lower limit on the strength of a *particular*
> cypher were only as hard as determining if a *particular* program halts,
> that would be wonderful!
> 
> John has subsequently clarified that he meant that, finding a lower limit
> on the strength of a *particular* cypher is as hard as determining if
> an *arbitrary* program halts - which is known to be an impossible problem.
> 
> Now, I'm still rather far from convinced that this analogy is a good one -
> and think that for some simple cyphers you /may/ eventually actually be
> able to prove minimum bounds for strength to everyone's satisfaction - but
> at least it's now very clear what he meant.
> -- 
> __________
>  |im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com
> 
> Remember, to a computer, 1 + 1 = 10.
-- 
Figures lie, and liars figure.--Daria Dolan


Subject: Re: Ritter's paper
Date: Sat, 9 Oct 1999 14:28:45 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FJCAvx.G8o@bath.ac.uk>
References: <37FEBCFF.63412C19@aspi.net>
Newsgroups: sci.crypt
Lines: 42

Trevor Jackson, III <fullmoon@aspi.net> wrote:

: PRNG-based ciphers are considered insecure for two reasons.  1) The potential
: unknown of the initial state is, in principle, reduced by half for each bit
: of output generated.

The potential unknown of the initial state is surely reduced by at most
one bit for each bit of output generated.  I presume that is what you
meant by a "half"?

: 2)  In practice, we have methods of detemining the initial
: state given the necessary number of bits of output, e.g., Berklecamp-Massey.

So there's no such thing as a cryptographically-secure random number
generator?

Surely some generators are easier to crack than others... and some of them
are /extremely/ difficult to crack.

I see no reason in principle why a PRNG-based cypher should be weak.

Certain PRNG-based stream cyphers have one or two problems associated with
the fact that they make no attempt to "smear" the information present in
each letter spatially across a number of letters in the cyphertext - but
this is not a weakness of using random numbers per se.

: Note that #1 above applies to all modern ciphers given a known plaintext.
: The discovery of a new attack upon a cipher is the discovery of a practical
: method of untangling the initial state given some amount of output > the
: amount of key.  By this line of reasoning we could define the "efficiency"
: of an attack as the ratio of the number of bits of output required over the
: number of bits of state to be discovered.

This "efficiency" is an interesting quantity.  However, I don't think it
corresponds closely to how hard a cypher is to crack.  In some cases,
where lots of cyphertext is available, it will probably not be very
relevant to "strength".
-- 
__________
 |im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

Tend to the molehills and the mountains will look after themselves.


Subject: Re: Ritter's paper
Date: Sun, 10 Oct 1999 11:57:28 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <3800B768.92655E30@aspi.net>
References: <jgfunj-0910992240090001@dial-243-018.itexas.net>
   <37FF5A1A.9E8D8950@aspi.net>
   <FJCAvx.G8o@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 80

wtshaw wrote:

> In article <37FF5A1A.9E8D8950@aspi.net>, "Trevor Jackson, III"
> <fullmoon@aspi.net> wrote:
>
> > Tim Tyler wrote:
> > >
> > > I see no reason in principle why a PRNG-based cypher should be weak.
> >
> > In practice true, but getting less so as time goes on.  In theory false.
>
> As time goes on, I see more and more that ciphers can use PRNG's as
> optional contributing components to key generation.
> > ...
> >
> > The central point is that, in theory, any PRNG has a limited amount of
> state.  As
> > the PRNG operates it discloses that state.  Once you have output >=
> state you can
> > only have one possible state that generated that output.  It's analogous
> to the of
> > unicity point of a cipher.  The initial state is completely determined by the
> > output.
> >
> > Finding the initial state given the output can be difficult in practice,
> but it
> > cannot be made impossible.
>
> It can be made so obscurely in the data that it can be, for practical
> attacks, impossible to recover it.  The special methods I am using are
> like smoke and mirrors, so to speak.  It is in fitting with a tradition of
> deceit in such methods.
> >
> > >
> > >
> > > : Note that #1 above applies to all modern ciphers given a known plaintext.
> > > : The discovery of a new attack upon a cipher is the discovery of a
> practical
> > > : method of untangling the initial state given some amount of output > the
> > > : amount of key.  By this line of reasoning we could define the "efficiency"
> > > : of an attack as the ratio of the number of bits of output required
> over the
> > > : number of bits of state to be discovered.
>
> This is in the spirit of a measure of strength *of a kind*.  If you need
> it in bits, OK, I guess.
>
> I have forwarded a scheme that does the same with *classic* ciphers, which
> is simply because that is where much so useful data is.
> > >
> > > This "efficiency" is an interesting quantity.  However, I don't think it
> > > corresponds closely to how hard a cypher is to crack.  In some cases,
> > > where lots of cyphertext is available, it will probably not be very
> > > relevant to "strength".
>
> It can be very revealing that a particular algorithm requires a
> unreasonable quantity of ciphertext to attack, which, according to my
> calculations in one situation, could be very many times the length of the
> key.  By definition, placing high here means that it is a very good
> algorithm indeed.

This is false.  It is based on the several mixtures above of attack strength (or
efficiency) and cipher strength.

Specifically, a particular [cipher] algorithm does not require an quantity of
ciphertext to attack.  A particular attack on a particular cipher requires a
quantity of ciphertext.  There may be many attacks on a particular cipher, each
attack requiring a different amount of ciphertext or plaintext.  Additionally, some
attacks can be performed more or less efficiently depending upon the amount of
ciphertext available.

Thus placing high in the amount of ciphertext does not tell us anything about the
strength of the cipher.  It tells us something about the lack of power (or
efficiency as defined above) in the attack.  A cipher sustaining no efficient
attacks is not strong.  Its strength is unknown.  A cipher sustaining an eficient
attack is at least as weak as indicated by the most efficient attack.  But that
shows only the upper bound on the cipher's strength, and does not tell us anything
about potentially even more powerful attacks (even weaker spots in the target
cipher).



Subject: Re: Ritter's paper
Date: Sun, 10 Oct 1999 17:07:44 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FJECww.4H9@bath.ac.uk>
References: <37FF5A1A.9E8D8950@aspi.net>
   <FJCAvx.G8o@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 67

Trevor Jackson, III <fullmoon@aspi.net> wrote:
: Tim Tyler wrote:
:> Trevor Jackson, III <fullmoon@aspi.net> wrote:

:> : PRNG-based ciphers are considered insecure for two reasons.  1) The potential
:> : unknown of the initial state is, in principle, reduced by half for each bit
:> : of output generated.

:> : 2)  In practice, we have methods of detemining the initial
:> : state given the necessary number of bits of output, e.g., Berklecamp-Massey.
:>
:> So there's no such thing as a cryptographically-secure random number
:> generator?

: What definition are you using for cryptographically secure?

Well, /hopefully/ the same one that you're using when you are saying that
PRNG-based cyphers are "insecure".  I'm talking about how easy they are
to break, relative to other cyphers.

:> Surely some generators are easier to crack than others... and some of them
:> are /extremely/ difficult to crack.
:>
:> I see no reason in principle why a PRNG-based cypher should be weak.

: In practice true, but getting less so as time goes on.  In theory false.

Getting "less and less so as time goes on"?  What support do you have for
this?

"In theory false"?  How is a PRNG-based cypher any less secure than any
other type of cypher, in principle.

:> Certain PRNG-based stream cyphers have one or two problems associated with
:> the fact that they make no attempt to "smear" the information present in
:> each letter spatially across a number of letters in the cyphertext - but
:> this is not a weakness of using random numbers per se.

: The central point is that, in theory, any PRNG has a limited amount of
: state.  As the PRNG operates it discloses that state.  Once you have output
: >= state you can only have one possible state that generated that output.

...but how do you find out which one?  *If* you have to search through the
whole period of the PRNG for the sequence, then this is directly analogous
to searching through the key-space of a block cypher.

: Finding the initial state given the output can be difficult in practice,
: but it cannot be made impossible.

Of course not.  In the same sense that a brute force search through the
keyspace will "break" any cypher.

The point about a cryptographic RNG is that you can make it /very/ hard to
find short-cuts to kinding the key from the output.  It's the same with
(e.g.) block cyphers - you can't make it impossible to find the key, but
you can make it very, very hard to locate it by methods more rapid than
searching the entire keyspace.

Your posts seem to paint a black picture of PRNG-based cryptography.

Looking more closely, I see absolutely no evidence that they
are (in principle) any less secure than any other modern cypher.
-- 
__________
 |im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

Marketing is sales with a college education.


Subject: Re: Ritter's paper
Date: Sun, 10 Oct 1999 16:27:02 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <3800F696.717262B9@aspi.net>
References: <FJECww.4H9@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 86

Tim Tyler wrote:

> Trevor Jackson, III <fullmoon@aspi.net> wrote:
> : Tim Tyler wrote:
> :> Trevor Jackson, III <fullmoon@aspi.net> wrote:
> :> Surely some generators are easier to crack than others... and some of them
> :> are /extremely/ difficult to crack.
> :>
> :> I see no reason in principle why a PRNG-based cypher should be weak.
>
> : In practice true, but getting less so as time goes on.  In theory false.
>
> Getting "less and less so as time goes on"?  What support do you have for
> this?

In theory the initial state of a PRNG is completely determined by its output.  Thus,
given a sufficiently sophisticated algorithm, one can infer the initial state from the
output.  In the limit ones builds the "inverse machine", feeds it the output in
reverse chronological order, and produces the initial state.

As time goes on the sophistication of analytic algorithms increases whereas the
sophistication any particular PRNG is constant.  Yes, you can increase PRNG
complexity, but it is not clear that that complexity makes the analytic task linearly
harder.

>
>
> "In theory false"?  How is a PRNG-based cypher any less secure than any
> other type of cypher, in principle.

PRNGs are not less secure than small-key ciphers.  They all have unknown strength or
strength relative to problems of unknown strength.

>
>
> :> Certain PRNG-based stream cyphers have one or two problems associated with
> :> the fact that they make no attempt to "smear" the information present in
> :> each letter spatially across a number of letters in the cyphertext - but
> :> this is not a weakness of using random numbers per se.
>
> : The central point is that, in theory, any PRNG has a limited amount of
> : state.  As the PRNG operates it discloses that state.  Once you have output
> : >= state you can only have one possible state that generated that output.
>
> ...but how do you find out which one?  *If* you have to search through the
> whole period of the PRNG for the sequence, then this is directly analogous
> to searching through the key-space of a block cypher.

It depends on the structure of the RNG.  For example, the Berklecamp-Massey algorithm
works on FSR generators.

>
>
> : Finding the initial state given the output can be difficult in practice,
> : but it cannot be made impossible.
>
> Of course not.  In the same sense that a brute force search through the
> keyspace will "break" any cypher.

No, we're discounting brute force, otherwise we'd all settle for long keys.  The
target is an algorithmic attacks such as differential, linear, slide, etc.

>
>
> The point about a cryptographic RNG is that you can make it /very/ hard to
> find short-cuts to kinding the key from the output.  It's the same with
> (e.g.) block cyphers - you can't make it impossible to find the key, but
> you can make it very, very hard to locate it by methods more rapid than
> searching the entire keyspace.

How hard?  To support your claim you need to show that there is a lower bound on the
work factor to find the initial state.  Do you know of such a case?

>
>
> Your posts seem to paint a black picture of PRNG-based cryptography.

I used the word bleak.

>
>
> Looking more closely, I see absolutely no evidence that they
> are (in principle) any less secure than any other modern cypher.

Agreed.



Subject: Re: Ritter's paper
Date: Mon, 11 Oct 1999 19:15:33 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FJGDHx.AsC@bath.ac.uk>
References: <3800F696.717262B9@aspi.net>
Newsgroups: sci.crypt
Lines: 136

Trevor Jackson, III <fullmoon@aspi.net> wrote:
: Tim Tyler wrote:
:> Trevor Jackson, III <fullmoon@aspi.net> wrote:
:> : Tim Tyler wrote:
:> :> Trevor Jackson, III <fullmoon@aspi.net> wrote:

:> :> Surely some generators are easier to crack than others... and some of them
:> :> are /extremely/ difficult to crack.
:> :>
:> :> I see no reason in principle why a PRNG-based cypher should be weak.
:>
:> : In practice true, but getting less so as time goes on.  In theory false.
:>
:> Getting "less and less so as time goes on"?  What support do you have for
:> this?

: In theory the initial state of a PRNG is completely determined by its
: output.  Thus, given a sufficiently sophisticated algorithm, one can
: infer the initial state from the output.

Much the same is true of a block cypher.  Given enough cyphertext, you can
establish how the cypher is scrambling the blocks.

If you consider the analogy between a "full period" PRNG (which cycles
through 2^N states and hits each state only once) and a block
cypher which maps each block of N bits to the successor of that
block as found in the PRNG output, it should be clear that there is
a type of equivalence between such systems.

: In the limit ones builds the "inverse machine", feeds it the output in
: reverse chronological order, and produces the initial state.

You talk as though this is actually feasible.  I view such a task as
completely on par with any other aspect of cryptanalysis.

: As time goes on the sophistication of analytic algorithms increases
: whereas the sophistication any particular PRNG is constant.  Yes, you can
: increase PRNG complexity, but it is not clear that that complexity makes
: the analytic task linearly harder.

This is true of all types of cypher, not just PRNG-based ones.

:> "In theory false"?  How is a PRNG-based cypher any less secure than any
:> other type of cypher, in principle.

: PRNGs are not less secure than small-key ciphers.  They all have unknown
: strength or strength relative to problems of unknown strength.

Hmm, that sounds a bit vague.

There are algorithms like Blum, Blum and Shub, where cracking them is
provably as hard as factoring large composite numbers.

I don't see why you need to compare them to small key cyphers.  You can
make a PRNG-based cypher that's up there with the best of them.

:> :> Certain PRNG-based stream cyphers have one or two problems associated with
:> :> the fact that they make no attempt to "smear" the information present in
:> :> each letter spatially across a number of letters in the cyphertext - but
:> :> this is not a weakness of using random numbers per se.
:>
:> : The central point is that, in theory, any PRNG has a limited amount of
:> : state.  As the PRNG operates it discloses that state.  Once you have output
:> : >= state you can only have one possible state that generated that output.
:>
:> ...but how do you find out which one?  *If* you have to search through the
:> whole period of the PRNG for the sequence, then this is directly analogous
:> to searching through the key-space of a block cypher.

: It depends on the structure of the RNG.  For example, the
: Berklecamp-Massey algorithm works on FSR generators.

Yes, and frequency analysis works on monoalphabetic cyphers.  There is
no general technique for cracking PRNGs.  The task is in theory as hard
as pretty much any other difficult bit of cryptanalysis you care to
mention.

:> : Finding the initial state given the output can be difficult in practice,
:> : but it cannot be made impossible.
:>
:> Of course not.  In the same sense that a brute force search through the
:> keyspace will "break" any cypher.

: No, we're discounting brute force, otherwise we'd all settle for long keys.

"No?"  It can be made impossible??? ... or "No", not in the same /sense/?

Both cannot be made impossible - I don't see much of an issue.

: The target is an algorithmic attacks such as differential, linear,
: slide, etc.

Well, OK, the equivalent operation for other sorts of cypher would be
a known-plaintext attack employing cryptanalytic techniques.

A block-cypher /also/ has a finite complexity and a limited internal
state.  It's typically possible to reverse-engineer these things - in much
the same way as a PRNG - given enough output and enough plaintext.

:> The point about a cryptographic RNG is that you can make it /very/ hard to
:> find short-cuts to kinding the key from the output.  It's the same with
:> (e.g.) block cyphers - you can't make it impossible to find the key, but
:> you can make it very, very hard to locate it by methods more rapid than
:> searching the entire keyspace.

: How hard?  To support your claim you need to show that there is a lower
: bound on the work factor to find the initial state.  Do you know of such
: a case?

I'm not trying to *prove* it - I'm just saying in practice it can be
made very difficult.  Certainly there are PRNGs out there with cash
prizes waiting for people who can crack them.  If finding their
seeds were as simple as all that, no one would be foolish enough to
put up such stakes.

I can no more prove a minumum strength for a PRNG-based cypher than you
can for the alternative (less weak?) cypher of your choice.

:> Your posts seem to paint a black picture of PRNG-based cryptography.

: I used the word bleak.

:> Looking more closely, I see absolutely no evidence that they
:> are (in principle) any less secure than any other modern cypher.

: Agreed.

Perhaps I was misled by your describing PRNG-based cyphers as "weak".

If you meant that they are weak - but no more weak than any other form
of cryptography - then the point under debate seems to me to vanish.
-- 
__________
 |im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

Energizer bunny arrested!  Charged with battery.


Subject: Re: Ritter's paper
Date: Sat, 09 Oct 1999 22:39:48 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-0910992239480001@dial-243-018.itexas.net>
References: <37FEBCFF.63412C19@aspi.net>
Newsgroups: sci.crypt
Lines: 26

In article <37FEBCFF.63412C19@aspi.net>, "Trevor Jackson, III"
<fullmoon@aspi.net> wrote:

> wtshaw wrote:
> >
> > Come on now, there are lots of ciphers of relative strengths, some
> > stronger than others by any measure you might take.
> 
> I disagree.  We can inventory the weaknesses of ciphers, and thus measure the
> upper bounds on their strength, but I do not see any way to establish a lower
> bound on strength, which is the operational meaning of "known strength".
> 
> I am not referring to key length, number of rounds, complexity of rounds,
> diffusion rate, etc.  I'm referring to the ratio of the work factor between
> having and lacking the key.  If we could rule out catastrophic algorithmic
> failures induced by new attacks such as differential, linear, slide,
> boomerang, etc. we could thereby establish the minimal work factor ratio.  But
> it does not appear that we can rule out those kinds of failure except in cases
> where key size meets or exceeds message size.

Still, we have ciphers which can give unambigous results with very little
length. Compound this with a slight keyspace.  You might want to dismiss
these things, but cryptograhic weaknesses in one area tend to knock the
stuffing out strengths in another.
-- 
Figures lie, and liars figure.--Daria Dolan


Subject: Re: Ritter's paper
Date: Sun, 10 Oct 1999 16:39:12 -0400
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <3800F970.D4A6BFBB@aspi.net>
References: <7tqaf2$tj$1@quine.mathcs.duq.edu>
   <37FE7ECF.D81B4E21@aspi.net>
Newsgroups: sci.crypt
Lines: 67

Patrick Juola wrote:

> In article <37FE7ECF.D81B4E21@aspi.net>,
> Trevor Jackson, III <fullmoon@aspi.net> wrote:
> >Patrick Juola wrote:
> >
> >> In article <37FE1428.A804351F@aspi.net>,
> >> Trevor Jackson, III <fullmoon@aspi.net> wrote:
> >> >> : This does not lead to an engineering figure of merit, nor even to
> >> >> : scientific reproducibility.
> >> >>
> >> >> Indeed not.  Do you have a metric which does to propose?  If not I am
> >> >> liable to doubt that such a metric even exists.
> >> >
> >> >I do not.  It appears to me that it may be possible to prove that such a metric
> >> >cannot exist.  But right now the best I can do is mumble about negative information
> >> >space.
> >>
> >> I think that I would argue that any attempt to reduce "cypher strength"
> >> to a scalar quantity is ignorant and misguided.  Differen cyphers
> >> have different areas of application, and different strengths depending
> >> on the use.
> >>
> >> One might as well try to come up with a metric for the best baseball
> >> player.  Eventually it will come down to a question of how you compare
> >> pitchers to outfielders (or whatever).
> >
> >OK, there are separate application domains whose metrics will always be distinct.  So
> >pick a single domain, without making it trivially small, and define a domain-specific
> >metric.
> >
> >Pitchers can be compared to pitchers along several (~10?) dimensions.
>
> ... at least.  Which means that you can't even reliably identify the
> best pitcher, let alone the best ball-player.  You can identify
> the best pitcher *along this dimension*, based on the assumption that
> the future will be like the past.
>
> Funny, that's exactly what modern cryptologists are doing when they
> start looking at things like key lengths and guessing how fast factoring
> algorithms will improve.  You have no way to prove that I won't find
> an O(log n) factoring algorithm tomorrow -- but neither do you have
> any way of proving that the fourth-string pitcher for the Boise Hashbrowns
> won't suddenly find his groove and go 20-0 in the majors every season for
> the next ten years.
>
> >The permise does not appear to apply to cipher strength.
>
> Evidence?  Pick any problem and it looks like there's reasonable evidence
> that our solutions are getting better, but not infinitely so.

I'll offer no evidence.  My observation was based on the fact that progress both flavors of
cryptology appears to be non-monotonic.  The discontinuities make it very hard to use past
experience to predict the future.  There's a self-referential aspect to this in that it
calls for predictions of human ability.  Can we predict genuis?

Could anyone have predicted the solution to the 4-color problem?  Or the progress toward
proving Fermat's Last Theorem?

I agree that there's evidence that suggests our modern cryptology is making progress, but
there is no evidence that does more than suggest.  And the threat of a discontinuity is
cipher strength is real.

Do you have any objective evidence that indicates we are getting closer to being able to
measure cipher strength?




Subject: Re: Ritter's paper
Date: Sun, 10 Oct 1999 23:22:12 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-1010992322130001@dial-243-029.itexas.net>
References: <3800F970.D4A6BFBB@aspi.net>
Newsgroups: sci.crypt
Lines: 16

In article <3800F970.D4A6BFBB@aspi.net>, "Trevor Jackson, III"
<fullmoon@aspi.net> wrote:
> 
> Do you have any objective evidence that indicates we are getting closer
to being able to measure cipher strength?

It all depends on how picky you are with results.  I am satisfied with
such progress as in ciphers can be scaled and some ciphers are obviously
weaker or stronger than others.  

Lots of sophisticated so-called modern ciphers are claimed to be strong by
those who do look to hard at the total meaning of strength, is short many
tend to be misguided even as they are zealous in belief that balanced
recursion will not end in a circle.
-- 
Figures lie, and liars figure.--Daria Dolan


Subject: Re: Ritter's paper
Date: Fri, 08 Oct 1999 21:06:31 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-0810992106320001@dial-243-049.itexas.net>
References: <7tle30$a7b$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 31

In article <7tle30$a7b$1@quine.mathcs.duq.edu>, juola@mathcs.duq.edu
(Patrick Juola) wrote:

> I think that I would argue that any attempt to reduce "cypher strength"
> to a scalar quantity is ignorant and misguided.  Differen cyphers
> have different areas of application, and different strengths depending
> on the use.

Resistance to quantifying strength is really the *pro*-ignorance
position.  If fact, some qualities are rather easily measured.  Too bad
that some popular ciphers just don't measure up in some areas, but there
are some look generally better and would pass a broad criteria of strong.

Trying to deal with strength as a single entity is like calling lots of
different diseases consumption, or bad blood.  It is time for cryptography
to deal realistically  with strength.
> 
> One might as well try to come up with a metric for the best baseball
> player.  Eventually it will come down to a question of how you compare
> pitchers to outfielders (or whatever).
> 
It all depends on how prejudiced you are for or against Pete Rose, a
rather personal point that is the crux of your question.  

A cipher that you might not like does not affect its potential strength. 
And either a baby or AES cipher kissed by the President is not more or
less pristine other than depending on how it was prepared for him in
advance.
-- 
Sometimes a small mistake can lead to fortunate reward.
  Charlie Chan


Subject: Re: Ritter's paper
Date: Sat, 9 Oct 1999 14:43:42 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FJCBKt.HA6@bath.ac.uk>
References: <37FE1428.A804351F@aspi.net>
   <37FB7B04.EAB00328@aspi.net>
Newsgroups: sci.crypt
Lines: 88

Trevor Jackson, III <fullmoon@aspi.net> wrote:
: Tim Tyler wrote:
:> Trevor Jackson, III <fullmoon@aspi.net> wrote:
:> : Tim Tyler wrote:
:> :> Trevor Jackson, III <fullmoon@aspi.net> wrote:
:> :> : Tim Tyler wrote:

:> :> :> "Strength: ability to resist breaks and cracks"?
:> :>
:> :> : Yeah.  But how to you measure it?  What are the units of
:> :> : "ability to resist breaks"?
:> :>
:> :> It seems to me that probably the best units in which to measure
:> :> this are monetary ones.
:>
:> : Ahem.  The ultimate in subjective standards.  "The value of a thing is
:> : what that thing will bring".

[snip]

:> : Do you believe that it is possible to have an efficient market in crypto
:> : strength?
:>
:> I believe it's possible to have an efficient market in crypyanalyisis.
:>
:> Strength /is/ a selling feature of cyphers, but it's not very easy for
:> customers to tell the wheat from the chaff.

: We seemed to agreed above that it's not easy, or even possible, for
: experts to tell the wheat from the chaff.  Since there is no rational
: basis for comparison, how can the market be described as efficient?
: Everyone is equally ignorant?

It's not quite as bad as all that.  The agents have /some/ information.
They can look at past performance of the vendors.  They can try to break
the codes themselves.  They can sometimes look at the history and
development of the products they buy and see who else uses them.

I wouldn't argue that the market is very "efficient" - but it works
well enough for the cost of breaking a cypher to reflect its strength to a
certain extent.

: It appears to me that _claims_ of strength are a selling feature.  But
: strength per se cannot be a selling feature because we cannot measure it.

The claims are not always totally without content.  Although customers
can rarely measure strength directly, there are some clues available.

A proof that a code is "as strong as factoring" provides useful 
information about the circumstances under which the code is likely to
fail, for example.

:> :> "Time" and "certainty" may also figure in the equation - but are probably
:> :> secondary characteristics most of the time.
:>
:> : Let's see, the two characteristics that crypto customers are paying
:> : for are secondary?
:>
:> Secondary to money.
:>
:> If you have a code and want it cracked, the time period involved for the
:> crack is often a secondary consideration to the total cost.

: Here we disagree,  Most of the time there is a time constraint related to the
: lifetime of the information.

Yes.

: Obtaining the protected information after its usefulness has decayed
: to zero means that time is a primary issue.  Also, for the crack to be
: the preferred method, the time period usually has to be shorter than any
: other method of obtaining the information, even cheaper methods.

I largely agree - however the cost of breaking a cypher does generally
reflect the time specified by the "customer" as being available.  Time
and money are partly dependent variables - a cypher which needs to be
cracked quickly will cost more to crack.

In this sense the (monetary) strength of a cypher depends on the type of
information it is expected to be containing.

As you say, if breaking the cypher is not the best way of obtaining the
information, the cypher is "strong enough".
-- 
__________
 |im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

So, it's you again.


Subject: Re: Ritter's paper
Date: Tue, 05 Oct 1999 00:45:33 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-0510990045340001@dial-243-058.itexas.net>
References: <FJ39A3.MM3@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 35

In article <FJ39A3.MM3@bath.ac.uk>, tt@cryogen.com wrote:

> wtshaw <jgfunj@vgrknf.arg> wrote:
> 
> : Strength and weakness being relative things, it does seem that the AES
> : goals are barely out of the parking lot, much less down the highway.
> 
> I feel someone needs to do some block-cypher advocacy on their behalf.
> 
> I really have difficulty in seeing what point there was in specifying
> in advance that cyphers must encrypt in 128-bit blocks.

OK, let's remember why this is so: NIST left lots open in the beginning
for suggestions as to how to proceed in looking for an AES. Those that
were there at the time might remember that I strongly advocated for a
variable length block cipher.  What came out was the result of compromise,
in good faith.

If the result was insufficient, so it maybe.  At least, it appears that
the process will end sometime, somewhere, so the Jim/Ed duo can say that
they met their assignment before passing it off to the mumbo jumbo crew of
loose lipped and oversexed politicians accompanied  by spooks and goblins
who like to scare people.
> 
> : I will likely disagree with many on what strength is, for it is a
> : combination of many things.  I continue to fight for a reasonable
> : composite definition of strength.
> 
 > "Strength: ability to resist breaks and cracks"?

You are on the right trail, but we need to look more for quantitative
answers that qualitative ones.
-- 
Sometimes a small mistake can lead to fortunate reward.
  Charlie Chan


Subject: Re: Ritter's paper
Date: Tue, 5 Oct 1999 23:30:47 GMT
From: "Doug Gwyn (ISTD/CNS) <gwyn>" <gwyn@arl.mil>
Message-ID: <37FA8A27.C126A414@arl.mil>
References: <FJ39A3.MM3@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 8

Tim Tyler wrote:
> I really have difficulty in seeing what point there was in specifying
> in advance that cyphers must encrypt in 128-bit blocks.

NIST wanted to evaluate proposals on a comparable basis.
128 bits was (and is) considered proof against brute-force attack;
too much less and there would be that worry again;
too much more and key management becomes more of a hassle.


Subject: Re: Ritter's paper
Date: Wed, 6 Oct 1999 15:18:02 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FJ6t62.F1I@bath.ac.uk>
References: <37FA8A27.C126A414@arl.mil>
Newsgroups: sci.crypt
Lines: 21

"Doug Gwyn (ISTD/CNS) <gwyn>" <gwyn@arl.mil> wrote:
: Tim Tyler wrote:

:> I really have difficulty in seeing what point there was in specifying
:> in advance that cyphers must encrypt in 128-bit blocks.

: NIST wanted to evaluate proposals on a comparable basis.
: 128 bits was (and is) considered proof against brute-force attack;
: too much less and there would be that worry again;
: too much more and key management becomes more of a hassle.

Key size need not increase hand-in-hand with the block size.

It seems to me that you can gain some security advantages by semaring the
information in a file out through a larger block, /without/ requiring a
larger key.
-- 
__________
 |im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

E Pluribus UNIX.


Subject: Re: Ritter's paper
Date: Wed, 06 Oct 1999 12:03:40 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-0610991203400001@dial-243-015.itexas.net>
References: <37FA8A27.C126A414@arl.mil>
Newsgroups: sci.crypt
Lines: 18

In article <37FA8A27.C126A414@arl.mil>, "Doug Gwyn (ISTD/CNS) <gwyn>"
<gwyn@arl.mil> wrote:

> Tim Tyler wrote:
> > I really have difficulty in seeing what point there was in specifying
> > in advance that cyphers must encrypt in 128-bit blocks.
> 
> NIST wanted to evaluate proposals on a comparable basis.
> 128 bits was (and is) considered proof against brute-force attack;
> too much less and there would be that worry again;
> too much more and key management becomes more of a hassle.

Yea, managing big keys is such a hastle when you don't know how to do it. 
But, it is not such a big deal once you understand the basics.  Too bad
few want to learn, or is it those they commonly look to don't know either?
-- 
Sometimes a small mistake can lead to fortunate reward.
  Charlie Chan


Subject: Re: Ritter's paper
Date: Tue, 14 Sep 1999 20:29:57 GMT
From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard)
Message-ID: <37deaa98.22058899@news.prosurfr.com>
References: <37dd996e.3608812@news.io.com>
Newsgroups: sci.crypt
Lines: 51

ritter@io.com (Terry Ritter) wrote, in part:

>There is a copy of the article .PDF on my pages.  It is first in the
>list in the Technical Articles section on my top page.  The exact link
>is:

>   http://www.io.com/~ritter/ARTS/R8INTW1.PDF

Thanks also. The local public library *doesn't* get Computer, and I
don't make it to the University as often as I used to these days.

You've presented a case with which I agree in many points. However,
Bruce Schneier's paper on "Staying With the Herd" presents many points
I agree with as well.

Extensive past cryptanalytic research does not, as you correctly note,
_prove_ a block cipher unbreakable, but it does reduce the likelihood
of the existence of a break likely to be known to, or able to be found
out by, certain classes of adversary. (That the history of
cryptography is replete with systems that have been proposed for
serious use, but which had serious and obvious flaws, as Bruce noted,
is surely a fact beyond dispute.)

A new design may be relatively untested, and lack this - admittedly
limited - source of at least partial confidence. On the other hand, as
you point out, an adversary has had less opportunity to study a novel
design than one that has become the "standard of the industry", and if
few people are using it, it may not be worth an adversary's while to
study the design in detail.

You did mention multiciphering, but because you did not (appear to?)
acknowledge that the point of view you were criticizing also had some
validity, even if it is imperfect and incomplete, you did not suggest
what I feel is the only rational way to employ novel cipher designs
when security is the primary object: in conjunction with the
well-tested and established designs that Mr. Schneier advocates and
recommends.

Simply because one point of view is partly wrong doesn't mean the
exact opposite must be completely right. And since that is such a
common fallacy, usually both sides in a dispute will tend to fall for
it, and as soon as those on one side have the opportunity to poke a
few holes in an argument for another point of view, they will feel
free to ignore it completely. This is why, when advocating a new point
of view, it is important to be aware of where the old point of view is
valid, so that what one proposes is free of error; it is not a matter
of politeness to adherents of the older view, it is to avoid obvious
mistakes that will prevent one's valid new ideas from being heard.

John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm


Subject: Re: Ritter's paper
Date: Tue, 14 Sep 1999 23:58:13 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37dee10c.5114156@news.io.com>
References: <37deaa98.22058899@news.prosurfr.com>
Newsgroups: sci.crypt
Lines: 84


On Tue, 14 Sep 1999 20:29:57 GMT, in
<37deaa98.22058899@news.prosurfr.com>, in sci.crypt
jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) wrote:

>[...]
>Extensive past cryptanalytic research does not, as you correctly note,
>_prove_ a block cipher unbreakable, but it does reduce the likelihood
>of the existence of a break likely to be known to, or able to be found
>out by, certain classes of adversary. 

You have made an assertion, not a summary of the known reality.  We do
not know the likelihood of any break.  And, if our Opponents have a
break, no amount of cryptographic research is going to change the
probability of that reality.  The only interaction of interest is
between the cipher and The Opponent, and the Opponents are not
talking.  We do not have the evidence to discuss either strength or a
probability of a break.  We cannot even collect data which would
foster academic inquiry into the issue.  


>(That the history of
>cryptography is replete with systems that have been proposed for
>serious use, but which had serious and obvious flaws, as Bruce noted,
>is surely a fact beyond dispute.)

Yes.  But these data do not imply what you think they do.  They have
shown weakness; they do not imply strength in the remaining ciphers.  


>A new design may be relatively untested, and lack this - admittedly
>limited - source of at least partial confidence. 

I would say that, in cryptography, partial confidence is no confidence
at all.  


>On the other hand, as
>you point out, an adversary has had less opportunity to study a novel
>design than one that has become the "standard of the industry", and if
>few people are using it, it may not be worth an adversary's while to
>study the design in detail.
>
>You did mention multiciphering, but because you did not (appear to?)
>acknowledge that the point of view you were criticizing also had some
>validity, 

I have no idea what you are talking about here.  The points which you
bring up in support of "that point of view" are in themselves invalid.


>even if it is imperfect and incomplete, you did not suggest
>what I feel is the only rational way to employ novel cipher designs
>when security is the primary object: in conjunction with the
>well-tested and established designs that Mr. Schneier advocates and
>recommends.

My article was a specific response to the earlier column which
essentially said that new cryptography was bad cryptography.  My
article addresses that issue, and apparently you agree that it needed
to be said.  But, of the two of us, one of us actually said it, and
one of us stood in the background and whines that it was not said just
right.  Well, maybe I'll do better next time.  


>Simply because one point of view is partly wrong doesn't mean the
>exact opposite must be completely right. And since that is such a
>common fallacy, usually both sides in a dispute will tend to fall for
>it, and as soon as those on one side have the opportunity to poke a
>few holes in an argument for another point of view, they will feel
>free to ignore it completely. This is why, when advocating a new point
>of view, it is important to be aware of where the old point of view is
>valid, so that what one proposes is free of error; it is not a matter
>of politeness to adherents of the older view, it is to avoid obvious
>mistakes that will prevent one's valid new ideas from being heard.

I am aware that the old point of view is fundamentally flawed and
scientifically invalid.  It is *not* almost valid.  It is *not* partly
right.  It is *not* right in practice.  It is just wrong.

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: 15 Sep 99 03:02:44 GMT
From: jsavard@ecn.ab.ca ()
Message-ID: <37df0c54.0@ecn.ab.ca>
References: <37dee10c.5114156@news.io.com>
Newsgroups: sci.crypt
Lines: 106

Terry Ritter (ritter@io.com) wrote:
: On Tue, 14 Sep 1999 20:29:57 GMT, in
: <37deaa98.22058899@news.prosurfr.com>, in sci.crypt
: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) wrote:

: >Extensive past cryptanalytic research does not, as you correctly note,
: >_prove_ a block cipher unbreakable, but it does reduce the likelihood
: >of the existence of a break likely to be known to, or able to be found
: >out by, certain classes of adversary. 

: You have made an assertion, not a summary of the known reality.  We do
: not know the likelihood of any break.

I think that I could discuss this point by talking about boxes which have
black and red billiard balls inside them, but I might just end up
"proving" your point of view if I did so.

You are certainly correct that if DES has a fixed _a priori_ probability
of being broken by somebody before 2003, no cryptographic result will
alter that probability.

However, the cryptanalytic effort directed against DES has demonstrated
that it is unlikely - very unlikely - that there is some stupid flaw in
DES that would be obvious to a moderately competent opponent.

: The only interaction of interest is
: between the cipher and The Opponent, and the Opponents are not
: talking.

Yes, but I think that an underworld cabal with cryptanalytic competence
approaching that of the NSA, for example, is a subject for a James Bond
movie, but not a threat analysis. However, not all cryptography is aimed
at mere hackers; one might be involved in human-rights efforts, and not
wish the Chinese government to read one's mail.

My point here is that a cipher beyond the reach of Eli Biham and the like
*is* beyond the reach of a large number of likely opponents.

: >(That the history of
: >cryptography is replete with systems that have been proposed for
: >serious use, but which had serious and obvious flaws, as Bruce noted,
: >is surely a fact beyond dispute.)

: Yes.  But these data do not imply what you think they do.  They have
: shown weakness; they do not imply strength in the remaining ciphers.  

No, they do not. But they imply that weakness is likely in an unexamined
cipher. The ones that have survived winnowing for obvious flaws have been
shown not to have that particular type of flaw.

Thus, in using a "new" cipher, I am taking a risk that a moderately
competent cryptanalyst might be able to break it. In using one that has
been extensively studied, I can - as a rough estimate - hope that it will
take an additional period of study, as long as that to which it has
already been subjected, before a flaw turns up.

(Yes, I am a Bayesian.)

: I would say that, in cryptography, partial confidence is no confidence
: at all.  

You have a point. However, 1000 times zero is still zero. I trust you can
see how that makes your position as untenable as Bruce's by that standard.

: My article was a specific response to the earlier column which
: essentially said that new cryptography was bad cryptography.  My
: article addresses that issue, and apparently you agree that it needed
: to be said.

Well, you seem to have just said that old cryptography is bad
cryptography.

Bruce correctly stated the risks of using untried cipher designs. They
have a significant likelihood of flaws that are relatively easy to find.

: I am aware that the old point of view is fundamentally flawed and
: scientifically invalid.  It is *not* almost valid.  It is *not* partly
: right.  It is *not* right in practice.  It is just wrong.

You are correct in saying that certainty of a type recognized in
mathematics is absent here. Many situations in life involve an absence of
certainty. There are ways in which people respond rationally to such a
condition.

Bruce recommends one form of response: gather as much corroborating
evidence as one can, even if it is of a kind with a fundamental
limitation.

You recommend other responses: use multiple ciphers, use a cipher few
other people are using so as to limit the amount of effort expended
against it.

Your recommendations are sound *additional* measures to take in this
situation of uncertainty. But because you are emphasizing that Bruce's
approach doesn't produce logical certainty, you appear to imply that his
strategy of response to the uncertainty can, and perhaps even should, be
neglected.

Obviously, you don't really mean that. You would not seriously offer to
the public an encryption program that enciphered people's messages using
10 algorithms taken from a pool of 1000 algorithms - that you had
developed for you by a local Grade Five class. You wouldn't do that;
nobody would. And the reasons you don't are the same reasons that are
behind what Bruce had said. So Bruce is not "just plain wrong".

John Savard


Subject: Re: Ritter's paper
Date: Wed, 15 Sep 1999 13:39:04 GMT
From: dscott@networkusa.net (SCOTT19U.ZIP_GUY)
Message-ID: <7ro41q$4o4$1@news.gate.net>
References: <37df0c54.0@ecn.ab.ca>
Newsgroups: sci.crypt,talk.politics.crypto
Lines: 177

In article <37df0c54.0@ecn.ab.ca>, jsavard@ecn.ab.ca () wrote:
>Terry Ritter (ritter@io.com) wrote:
>: On Tue, 14 Sep 1999 20:29:57 GMT, in
>: <37deaa98.22058899@news.prosurfr.com>, in sci.crypt
>: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) wrote:
>
>: >Extensive past cryptanalytic research does not, as you correctly note,
>: >_prove_ a block cipher unbreakable, but it does reduce the likelihood
>: >of the existence of a break likely to be known to, or able to be found
>: >out by, certain classes of adversary. 
>
>: You have made an assertion, not a summary of the known reality.  We do
>: not know the likelihood of any break.
>
>I think that I could discuss this point by talking about boxes which have
>black and red billiard balls inside them, but I might just end up
>"proving" your point of view if I did so.
>
>You are certainly correct that if DES has a fixed _a priori_ probability
>of being broken by somebody before 2003, no cryptographic result will
>alter that probability.
>
>However, the cryptanalytic effort directed against DES has demonstrated
>that it is unlikely - very unlikely - that there is some stupid flaw in
>DES that would be obvious to a moderately competent opponent.
     Actually anyone aware of the state of electronics at the time DES
was employed. I am talking custom hardware not computers. Realizes
that DES could be easily broken by a realtime brute force search. Just
becasue it took deveral years for the domestic computer front to reach
that stage does not mean that it was not done decades before. Many
even at the time the governemnt moded it from 64 bits to the strange
56 bits realized this at that time.  SInce then it is very likely a group
like the NSA may have found a very simple break other than brute
force search. You can't blindly say that just becasue some one in the
public domain has not found one. That one does not exist.
>
>: The only interaction of interest is
>: between the cipher and The Opponent, and the Opponents are not
>: talking.
>
>Yes, but I think that an underworld cabal with cryptanalytic competence
>approaching that of the NSA, for example, is a subject for a James Bond
>movie, but not a threat analysis. However, not all cryptography is aimed
>at mere hackers; one might be involved in human-rights efforts, and not
>wish the Chinese government to read one's mail.
      It might be very possible that there is a sweet old lady much like
the British equivalent in the NSA giving Chinese all the NSA secrets.
My government is a total fool when it comes to catching spys. The
security types look very hard into people like me who question many
of the dumb pratices. They are to blind and arragant to catch real spys
they would rather chase after those who offer advice or who question
things. It was that way with the Brits witness the old lady spy and it
is that way with the US government. Sure after years and years a
jealous wife can cause a Walker case but that is the tip of the iceberg.
   With a Clinton administartion afraid to search the personnal computer
of a person of chinese origin who signed away his right to keep his
computer private so that that person can have access to our nuclear
arsenal for fear of looking bad becasue it may be viewed as attacking
a minority. 
>
>My point here is that a cipher beyond the reach of Eli Biham and the like
>*is* beyond the reach of a large number of likely opponents.
>
>: >(That the history of
>: >cryptography is replete with systems that have been proposed for
>: >serious use, but which had serious and obvious flaws, as Bruce noted,
>: >is surely a fact beyond dispute.)
>
>: Yes.  But these data do not imply what you think they do.  They have
>: shown weakness; they do not imply strength in the remaining ciphers.  
>
>No, they do not. But they imply that weakness is likely in an unexamined
>cipher. The ones that have survived winnowing for obvious flaws have been
>shown not to have that particular type of flaw.
>
>Thus, in using a "new" cipher, I am taking a risk that a moderately
>competent cryptanalyst might be able to break it. In using one that has
>been extensively studied, I can - as a rough estimate - hope that it will
>take an additional period of study, as long as that to which it has
>already been subjected, before a flaw turns up.
>
>(Yes, I am a Bayesian.)
>
>: I would say that, in cryptography, partial confidence is no confidence
>: at all.  
>
>You have a point. However, 1000 times zero is still zero. I trust you can
>see how that makes your position as untenable as Bruce's by that standard.
>
>: My article was a specific response to the earlier column which
>: essentially said that new cryptography was bad cryptography.  My
>: article addresses that issue, and apparently you agree that it needed
>: to be said.
>
>Well, you seem to have just said that old cryptography is bad
>cryptography.
>
>Bruce correctly stated the risks of using untried cipher designs. They
>have a significant likelihood of flaws that are relatively easy to find.
     Actually Bruce is a little high on himself or haven't you noticed.
So is Mr Wagner.  But now that I know Mr Wagner is listed on Bruces
own site as an employee it makes persfect sense as why the two seem
to speak with one voice. THey can attack a certain class of tried ameture
ciphers becasue they get invented over and over. Then they make sweeping
statements that if it is not thought of by people with there narrow training
and background it is no good. 
  Well the truth is that both can make shallow attacks against my cipher
and people are dumb enough to belive them. David has stated publicly that
my method is weak. Yet when push came to shove. HIs blesed (my Bruce)
Slide attack that he said would show my method scott19u or scott16u wiould
be dead was wrong. He know admits he can't even decipher working C code.
What kind of expersts are these  2 guys. 
>
>: I am aware that the old point of view is fundamentally flawed and
>: scientifically invalid.  It is *not* almost valid.  It is *not* partly
>: right.  It is *not* right in practice.  It is just wrong.
>
>You are correct in saying that certainty of a type recognized in
>mathematics is absent here. Many situations in life involve an absence of
>certainty. There are ways in which people respond rationally to such a
>condition.
>
>Bruce recommends one form of response: gather as much corroborating
>evidence as one can, even if it is of a kind with a fundamental
>limitation.
   Bruce and his employes are only capable of looking in very narrow
areas. He once stated on a post he found it harder to design large key
systems than the ones he designs. This is an obvious lie or maybe Bruce
needs to take a few more math classes. Bruce and his emplyess are to
lazy to look at new methods. His last excuse was that he was busy with
AES methods to look into the real world of ciphers that are different like
mine.

>
>You recommend other responses: use multiple ciphers, use a cipher few
>other people are using so as to limit the amount of effort expended
>against it.
>
>Your recommendations are sound *additional* measures to take in this
>situation of uncertainty. But because you are emphasizing that Bruce's
>approach doesn't produce logical certainty, you appear to imply that his
>strategy of response to the uncertainty can, and perhaps even should, be
>neglected.
>
>Obviously, you don't really mean that. You would not seriously offer to
>the public an encryption program that enciphered people's messages using
>10 algorithms taken from a pool of 1000 algorithms - that you had
>developed for you by a local Grade Five class. You wouldn't do that;
>nobody would. And the reasons you don't are the same reasons that are
>behind what Bruce had said. So Bruce is not "just plain wrong".

 But the liekly hood of only using NSA approved ciphers goes up when one
uses a very limited number of blessed ciphers made by people with the
same narrow mindset. Because it in the interest of the NSA to control
crypto by all meanes and if the eggs are in one basket that is the basket
the NSA will surely infect.
 What is need is many ciphers of different design uses serially since if
desinged by more that one school of thought those in the other school
will try to break them and publish the breaks to embarasse the other
side. But with one school of thought it will become potitically corrupt
has the system is today.
 Since Bruce and David can say mine is waek yet few question there
lies even when they fail on there only known public attempt to break
my code. Yes they will continue to say they are to busy. But the
truth of the matter a large key system like mine is far better at secureing
files than there weak short key methods. And yes mine might not be
best for credit cards systems. SO what it is desingned for FILES.




David A. Scott
--
                    SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
                    http://www.jim.com/jamesd/Kong/scott19u.zip
                    http://members.xoom.com/ecil/index.htm
                    NOTE EMAIL address is for SPAMERS


Subject: Re: Ritter's paper
Date: Sun, 19 Sep 1999 00:42:36 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <37e430d0.5009838@quake.io.com>
References: <37df0c54.0@ecn.ab.ca>
Newsgroups: sci.crypt
Lines: 192


On 15 Sep 99 03:02:44 GMT, in <37df0c54.0@ecn.ab.ca>, in sci.crypt
jsavard@ecn.ab.ca () wrote:

>Terry Ritter (ritter@io.com) wrote:

>[...]
>However, the cryptanalytic effort directed against DES has demonstrated
>that it is unlikely - very unlikely - that there is some stupid flaw in
>DES that would be obvious to a moderately competent opponent.

Saying that something we do not know is "unlikely" implies an
unwarranted and unfortunate extrapolation from what we do know to what
we do not.  That is inductive reasoning, and it must be handled very
carefully, because it is very easy to get wrong.  Normally, inductive
reasoning must be backed up by deduction from the conclusion, which is
not possible here.  So in this case, it is bad Science.  


>: The only interaction of interest is
>: between the cipher and The Opponent, and the Opponents are not
>: talking.
>
>Yes, but I think that an underworld cabal with cryptanalytic competence
>approaching that of the NSA, for example, is a subject for a James Bond
>movie, but not a threat analysis. However, not all cryptography is aimed
>at mere hackers; one might be involved in human-rights efforts, and not
>wish the Chinese government to read one's mail.
>
>My point here is that a cipher beyond the reach of Eli Biham and the like
>*is* beyond the reach of a large number of likely opponents.

And you apparently recommend that same cipher for tasks which *would*
engage NSA and organized crime as well as for ordinary business and
personal use.  Then, if the cipher *is* broken (in secret), why do you
think that the technology would be applied against only serious
communications?

Moreover, the basic concept is wrong.  What is beyond Biham now may
not be beyond the ordinary hacker after new technology is published.
So when I say that we do not know strength, I mean we *really* do not
know cipher strength.  It is not that we know some minimum strength
and someone may eventually have the tools to surmount that.  


>: >(That the history of
>: >cryptography is replete with systems that have been proposed for
>: >serious use, but which had serious and obvious flaws, as Bruce noted,
>: >is surely a fact beyond dispute.)
>
>: Yes.  But these data do not imply what you think they do.  They have
>: shown weakness; they do not imply strength in the remaining ciphers.  
>
>No, they do not. But they imply that weakness is likely in an unexamined
>cipher. The ones that have survived winnowing for obvious flaws have been
>shown not to have that particular type of flaw.

Then I would suggest that you demand that paid academics who claim
expertise in this area start serving the public good by performing
such analysis on a broad scale.  


>Thus, in using a "new" cipher, I am taking a risk that a moderately
>competent cryptanalyst might be able to break it. In using one that has
>been extensively studied, I can - as a rough estimate - hope that it will
>take an additional period of study, as long as that to which it has
>already been subjected, before a flaw turns up.
>
>(Yes, I am a Bayesian.)

Yet that still does not make your logic correct.


>: I would say that, in cryptography, partial confidence is no confidence
>: at all.  
>
>You have a point. However, 1000 times zero is still zero. I trust you can
>see how that makes your position as untenable as Bruce's by that standard.

No, I do not.  I do not claim absolute security.  However, I do claim
that a multicipher is inherently *more* protective of its ciphering
components than any single component by itself.  Being protected is
not the same as being fully exposed, and that is true even if we don't
know the strengths of the component ciphers.


>: My article was a specific response to the earlier column which
>: essentially said that new cryptography was bad cryptography.  My
>: article addresses that issue, and apparently you agree that it needed
>: to be said.
>
>Well, you seem to have just said that old cryptography is bad
>cryptography.

Certainly the old ideas about cryptography are bad cryptography.

Cryptanalysis is not how we know cipher strength; we have no such
tool.  In fact, cryptanalysis is how we know cipher weakness (and then
only an upper bound -- the "real" strength may be far less) for
ciphers we will not then use.  For the untouched ciphers we *will*
use, cryptanalysis has not testified *at* *all* about strength.  


>Bruce correctly stated the risks of using untried cipher designs. They
>have a significant likelihood of flaws that are relatively easy to find.

Schneier clearly supports the AES approach to the selection of a
single cipher.  That cipher immediately becomes a universal target.
This approach is fundamentally wrong.  


>: I am aware that the old point of view is fundamentally flawed and
>: scientifically invalid.  It is *not* almost valid.  It is *not* partly
>: right.  It is *not* right in practice.  It is just wrong.
>
>You are correct in saying that certainty of a type recognized in
>mathematics is absent here. Many situations in life involve an absence of
>certainty. There are ways in which people respond rationally to such a
>condition.

Alas, the evidence we have from cryptanalysis is not the sort which
allows prediction of strength.  The same logic we might use to decide
about automobile reliability or make use of faulty software simply
does not apply in this situation.  

In most risk situations which we know from real life, we have some
understanding of the value we risk, and the probability of failure.
But in crypto, we cannot realistically hope to know the probability of
failure, and extrapolating that from cryptanalytic experience is just
flat wrong and bad Science.  Moreover, the value being risked here is
not just one person or one company, but nothing less than the entire
content of our information society: the simple selection of a single
standard cipher thus becomes a threat instead of an advantage.   


>Bruce recommends one form of response: gather as much corroborating
>evidence as one can, even if it is of a kind with a fundamental
>limitation.

I agree with that.  But knowing the limits of this, I disagree that it
is sufficient, and there has been no Schneier proposal to address the
problem.  Quite the contrary, the Schneier proposal is that we do not
use new cryptography, and that we all rely upon one of the few ciphers
which are academically well-regarded.  I find this last especially
ironic, since we would normally expect academics to enforce tight
reasoning and good Science.  


>You recommend other responses: use multiple ciphers, use a cipher few
>other people are using so as to limit the amount of effort expended
>against it.
>
>Your recommendations are sound *additional* measures to take in this
>situation of uncertainty. But because you are emphasizing that Bruce's
>approach doesn't produce logical certainty, you appear to imply that his
>strategy of response to the uncertainty can, and perhaps even should, be
>neglected.

I not only imply, I directly state that the claim that a cipher is
strong because it survives cryptanalysis is simply false.  The idea
that we would bet our information society on any particular opinion
about strength is frankly appalling.  


>Obviously, you don't really mean that. You would not seriously offer to
>the public an encryption program that enciphered people's messages using
>10 algorithms taken from a pool of 1000 algorithms - that you had
>developed for you by a local Grade Five class. You wouldn't do that;
>nobody would. And the reasons you don't are the same reasons that are
>behind what Bruce had said. So Bruce is not "just plain wrong".

While I appreciate your attempts to get Schneier and myself to duke it
out while you watch, this is a fundamental issue for cryptographic
science, and not some sort of battle between sides.  Schneier merely
represents and promotes the currently accepted but false beliefs about
what ciphers should be.  To that same extent, the other side deserves
to be heard, and you will not hear about another side in his works or
writings, and I call that deceptive.  

I find it difficult to credit Schneier for advocating that we not do
something which nobody would do anyway.  Instead, the issue before us
is the opinion he offers as an expert and the process he supports to
provide guidance to the rest of society beyond what they would
normally do.  In my view, that opinion and process are fundamentally
flawed in a clear, logical, scientific way that almost everyone can
understand.  This is what it means to be just plain -- and completely
-- wrong.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM


Subject: Re: Ritter's paper
Date: Sat, 18 Sep 1999 22:29:32 -0700
From: Sundial Services <info@sundialservices.com>
Message-ID: <37E474BC.279F@sundialservices.com>
References: <37e430d0.5009838@quake.io.com>
Newsgroups: sci.crypt
Lines: 26

Terry Ritter wrote:
>
> >Well, you seem to have just said that old cryptography is bad
> >cryptography.
> 
> Certainly the old ideas about cryptography are bad cryptography.
> 
> Cryptanalysis is not how we know cipher strength; we have no such
> tool.  In fact, cryptanalysis is how we know cipher weakness (and then
> only an upper bound -- the "real" strength may be far less) for
> ciphers we will not then use.  For the untouched ciphers we *will*
> use, cryptanalysis has not testified *at* *all* about strength.
> 
> >Bruce correctly stated the risks of using untried cipher designs. They
> >have a significant likelihood of flaws that are relatively easy to find.
> 
> Schneier clearly supports the AES approach to the selection of a
> single cipher.  That cipher immediately becomes a universal target.
> This approach is fundamentally wrong.


As a pure aside to all this conversation...  NONE of us are really "at
odds" with one another... not Mr. Ritter, not Mr. Schneier...  It's
academic debate.  It's purely aimed at advancing the non-classified
knowledge and state of the art.  Personalities have nothing to do with
it.  Zippo.


Subject: Re: Ritter's paper
Date: 19 Sep 99 08:58:48 GMT
From: jsavard@ecn.ab.ca ()
Message-ID: <37e4a5c8.0@ecn.ab.ca>
References: <37e430d0.5009838@quake.io.com>
Newsgroups: sci.crypt
Lines: 100

Terry Ritter (ritter@io.com) wrote:
: Moreover, the basic concept is wrong.  What is beyond Biham now may
: not be beyond the ordinary hacker after new technology is published.

Yes, I agree with that. Thus, I think we should use "unreasonably large"
key sizes, for example.

John:
: >: >(That the history of
: >: >cryptography is replete with systems that have been proposed for
: >: >serious use, but which had serious and obvious flaws, as Bruce noted,
: >: >is surely a fact beyond dispute.)

Terry:
: >: Yes.  But these data do not imply what you think they do.  They have
: >: shown weakness; they do not imply strength in the remaining ciphers.  

John:
: >No, they do not. But they imply that weakness is likely in an unexamined
: >cipher. The ones that have survived winnowing for obvious flaws have been
: >shown not to have that particular type of flaw.

Terry:
: Then I would suggest that you demand that paid academics who claim
: expertise in this area start serving the public good by performing
: such analysis on a broad scale.  

Rather than come up with a pseudo-Libertarian counterargument, upon
reflection I find that isn't that bad a suggestion, as long as one doesn't
use too broad a definition of "broad".

I'll settle for a much smaller request: that those cipher designers who
are currently respected design ciphers that are scaled up a bit more,
that include greater diversity of design, and that try to be more
fundamentally nonlinear or irregular.

: >Thus, in using a "new" cipher, I am taking a risk that a moderately
: >competent cryptanalyst might be able to break it. In using one that has
: >been extensively studied, I can - as a rough estimate - hope that it will
: >take an additional period of study, as long as that to which it has
: >already been subjected, before a flaw turns up.

: >(Yes, I am a Bayesian.)

: Yet that still does not make your logic correct.

It isn't ironclad like deductive logic, no.

: I agree with that.  But knowing the limits of this, I disagree that it
: is sufficient, and there has been no Schneier proposal to address the
: problem.

At least *once* he acknowledged the existence of the problem, as I
recently remembered: he noted that we don't have enough well-analyzed
ciphers to choose from.

: I not only imply, I directly state that the claim that a cipher is
: strong because it survives cryptanalysis is simply false.  The idea
: that we would bet our information society on any particular opinion
: about strength is frankly appalling.  

A cipher is not proven strong by surviving cryptanalysis. Such survival is
merely weak corroborating evidence of strength, which is the best thing we
have. It is not to be blindly relied upon - here you are correct - but
neither is it to be disdained.

quoting me again:
: >Obviously, you don't really mean that. You would not seriously offer to
: >the public an encryption program that enciphered people's messages using
: >10 algorithms taken from a pool of 1000 algorithms - that you had
: >developed for you by a local Grade Five class. You wouldn't do that;
: >nobody would. And the reasons you don't are the same reasons that are
: >behind what Bruce had said. So Bruce is not "just plain wrong".

: While I appreciate your attempts to get Schneier and myself to duke it
: out while you watch,

Well, I thought I've been doing exactly the opposite: stepping right into
the middle of the debate in order to get the advocates of both points of
view to recognize what is valid in the other side's perspective.

: this is a fundamental issue for cryptographic
: science, and not some sort of battle between sides.

Because I firmly believe that an ideological war is *not* the best climate
for the search for truth. There are two schools of thought, and in my
opinion each is incomplete.

: Schneier merely
: represents and promotes the currently accepted but false beliefs about
: what ciphers should be.  To that same extent, the other side deserves
: to be heard, and you will not hear about another side in his works or
: writings, and I call that deceptive.  

They are largely aimed at people who may lack cryptological
sophistication, and so they teach safe practice without exposing their
student to alternatives. This should perhaps be more clearly labelled, but
I wouldn't call a textbook on Strict Counterpoint deceptive.

John Savard


Subject: Re: Ritter's paper
Date: 19 Sep 99 20:25:50 GMT
From: jsavard@ecn.ab.ca ()
Message-ID: <37e546ce.0@ecn.ab.ca>
References: <37e430d0.5009838@quake.io.com>
Newsgroups: sci.crypt
Lines: 44

Terry Ritter (ritter@io.com) wrote:
: But in crypto, we cannot realistically hope to know the probability of
: failure, and extrapolating that from cryptanalytic experience is just
: flat wrong and bad Science.  Moreover, the value being risked here is
: not just one person or one company, but nothing less than the entire
: content of our information society: the simple selection of a single
: standard cipher thus becomes a threat instead of an advantage.   

: I not only imply, I directly state that the claim that a cipher is
: strong because it survives cryptanalysis is simply false.  The idea
: that we would bet our information society on any particular opinion
: about strength is frankly appalling.  

The best we can conclude, using Bayesian statistics, from the fact that a
cipher has withstood X man-hours of analysis by qualified academics is
that our best estimate of the probability that a given man-hour of
analysis by other academics of similar qualification will uncover its
crack is 1/(2X). (This assumes the man-hours are cumulative, not
independent.)

It is in this sense that I say "if it's lasted five years, we can expect
it to last another five". That expectation isn't a certain one, and the
apparent probability of a break is not reduced to an acceptably low level.

Thus I can't deny that you are basically right.

I think, though, that there are other reasons for some degree of
confidence in a well-designed cipher besides raw Bayesian statistical
evidence: one can extrapolate, for example, on the large volumes of known
plaintext required to perform differential cryptanalysis, or on the
general state of mathematical knowledge in this area.

My personal perspective is that selecting from a large pool of ciphers
does produce some benefit, but using a few at once is more important and
less risky. One thing obviously lacking in the well-analyzed designs
(Bruce Schneier's own Blowfish being the conspicuous exception) is a large
key size and things like large key-dependent S-boxes. Another thing I
think we need is steps with extra complexity and indirection, so as to
make the prospects of a way to even begin analyzing the cipher for
weakness seem dim. The FROG design submitted to the AES process was an
attempt to do this, and I've been trying to suggest other ways of
achieving this in my own designs in the Quadibloc series.

John Savard


Subject: Re: Ritter's paper
Date: Wed, 15 Sep 1999 16:29:25 GMT
From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard)
Message-ID: <37dfc843.9044374@news.prosurfr.com>
References: <37dee10c.5114156@news.io.com>
Newsgroups: sci.crypt
Lines: 16

ritter@io.com (Terry Ritter) wrote, in part:

>But, of the two of us, one of us actually said it, and
>one of us stood in the background and whines that it was not said just
>right.  Well, maybe I'll do better next time.  

My position on these issues does not make exciting reading, as it
consists of sitting resolutely on the fence. While I don't feel I have
the credentials to have an opinion piece from me published in a major
publication, I have now taken some space on my web page to address
these issues, in response to this suggestion, at:

http://www.ecn.ab.ca/~jsavard/mi0609.htm

John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm

Terry Ritter, his current address, and his top page.

Last updated: 2001-06-04