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