Cryptography-Digest Digest #510, Volume #9 Thu, 6 May 99 20:13:03 EDT
Contents:
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(John Savard)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Terry Ritter)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(John Savard)
Re: Some thoughts on Diffusion (wtshaw)
Re: Fast random number generator (Terry Ritter)
Re: AES (Terry Ritter)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(John Savard)
Re: AES (Patrick Juola)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Thu, 06 May 1999 19:03:51 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote, in part:
>We would surely prefer to have both strength and independent messages.
>But since we cannot know strength, we must look to the consequences of
>weakness: If we have a plethora of ciphers and use new ones for each
>message, each cipher break exposes one message. If we just use one
>cipher, a cipher break potentially exposes all messages over all time.
>Breaking the cipher in a one-cipher system will expose future use of
>that cipher. But breaking the current cipher in a many-cipher system
>exposes only the current message and not future messages. Which do we
>prefer?
Since we can know weakness, those who are objecting to your scheme do
so on the basis that it makes the use of some weak ciphers more
likely, or even a virtual certainty.
I have to admit that I find that argument to have considerable
validity, and yet I don't see it as fatal; multi-ciphering and care in
the ensemble of ciphers to use, and perhaps some other measures as
well, can address the problem.
But here you have reminded me of why a system such as yours would be
beneficial. We cannot know strength. Relying on any one cipher, then,
is a gamble.
How can we use more than one cipher, and yet not wind up with a chain,
as strong as its weakest link, with many links? _That_ is the question
that needs to be answered, and multiple encipherment is an important
part of the answer.
Despite finding the objections to have some validiity, I also have to
agree with you that just settling on one cipher that "everybody", or,
more specifically, those who are respected and competent, thinks is
strong is not a valid answer either. Even the experts do get
surprised. Your objection to the conventional way of doing things is
valid too.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Thu, 06 May 1999 19:19:24 GMT
On Wed, 5 May 1999 16:48:40 -0600, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (Jerry Coffin) wrote:
>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>[ ... ]
>
>> The process starts off with agreement on keys and cipher in the normal
>> way: either transported as a secure secret, or under a certified
>> public key.
>
>If it/they are transported under a public key, then the number of
>other forms of encryption may be moot -- if the public key encryption
>is broken, the key(s) can be recovered, and the attacker can decrypt
>the rest of the message without breaking any other forms of
>encryption. You'd have a situation similar to that of PGP at the
>present time: the security of the system overall is no better than
>that of the system used to encrypt the key. You might (as PGP does)
>get improvements in speed over using PK cryptography on the entire
>message, but you wouldn't get any real improvement in the system's
>security.
Any time we have one cipher depending on another, one of those ciphers
is going to be weaker than the other. If we "know" the public key
system is weaker, and increase the public key strength beyond that,
then the secret key system is weaker. This never ends.
One way to reduce public key vulnerability is to have an especially
large public-key and use that to transmit a single main key once.
Such a large public key could be intrusive, but unless one needs
public key features in every message, there may be no need to
continually use such keys beyond establishing a secure secret on both
ends once. Subsequent communications could be strictly secret-key:
each message would encipher a random message key value under the main
key, then use the plaintext message key value as the key for
enciphering data, perhaps under a different cipher. Any such peculiar
ciphering arrangement would be just another named metacipher agreed
upon at both ends.
Certainly the cipher system could start out with secret keys, and in
many cases they could be the method of choice. But many people think
cryptography means "public key" and we wouldn't want to disappoint
them. In any case, the cipher system should encapsulate capabilities
needed by ciphers, and not unduly restrict the type of ciphers used,
or metacipher designs. This sort of design is harder than it looks,
but I believe it is well within reach. The more significant issue is
how -- in an environment of free ciphers -- can we possibly compensate
professional design efforts if we want professional results.
>> Instead of a cipher name, the cipher itself could be
>> sent, as C, binary, or whatever.
>
>This seems to be to form a problem of its own -- sending such a
>message from within the USA to outside the USA would involve exporting
>the encryption (or at least the decryption) code, for which one would
>apparently have to obtain a license, at least if (s)he wanted to send
>such messages legally. Given the likelihood of all users obtaining
>such licenses, (essentially nonexistent) it's fair to say that almost
>anybody in the US who used such a system would become a criminal.
First, I have trouble seeing a high-security systems in the context of
a broadcast to "all users." High security is point-to-point or
user-to-user, not user-to-everybody. When many people know, true
secrecy is simply not possible, no matter what cipher we have. So in
my view, the issue of broadcasting cipher code to "all users" does not
arise.
Next, sending the cipher is an *option*. One alternative is to
specify some cipher by name. Another alternative is to use the
default cipher (whatever that name has been set to be). Many users
would use Triple-DES, unless that suddenly implodes, in which case
they would use something else. Both ends to a transmission can agree
upon the cipher in pretty much the same way that they now get the same
system and then agree upon the key. There need be nothing more there
than what we do now.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Thu, 06 May 1999 19:08:14 GMT
[EMAIL PROTECTED] (D. J. Bernstein) wrote, in part:
>Once again: What do you do when the attacker notices that most of the
>amateur designs incorporated into your system are vulnerable to simple,
>easily automated differential attacks?
I don't think Terry Ritter is claiming he can turn a sow's ear into a
silk purse. One does have to start with ciphers that are _not_ already
known to be weak.
He is more optimistic about being able to find sufficiently strong
ciphers in the required quantity. I think that there are conditions
under which such optimism is justified: but I don't deny that this
point needs to be addressed.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Some thoughts on Diffusion
Date: Thu, 06 May 1999 13:39:50 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
>
> I can envisage an attack on Grandview with *one* keyletter, if a large
> number of messages are all sent with the same key.
Remember, three *keys* are at work, cylinder, pathcode, and the offset
schedule. The beauty of the cipher is that the last one can be varied,
should be, and consistent use of the same initial letters in ciphertext
would tipoff a fauxsolution.
> If one has enough
> messages of the same length to get statistics on their first and last
> letters, progress is possible. But it certainly *is* a system of
> considerable security. Done manually, one can improve security by
> getting rid of the = sign at the start, and use a conventional
> cylinder. (Since the = sign is always at the end of the message, one
> could actually use an extra keyletter; it could even be a common
> letter like A without interfering, since any A not at the end of the
> message must be text. So the = sign can even be eliminated for a
> computer.)
It was a compromise choice. I suppose that there are subtilities that may
be different. The important thing was some standardization so I would not
wander around for another decade or so before presenting it.
The reasoning behind ending on a space was to insure complete words were
in each block, spaces not occuring between words. If a few ending
characters of a block are lost or corrupte, one can back up character at a
time until a space is reached, and the block should solve itself normally
with a partial block. Losing intermediate characters means adding
anything back, and corruptin of intermediate characters are usually seen
as trivial mispellings. Messing up the first few characters would cause
the most damage, perhaps unrecoverable for an isolated block, but I like
the survivability of redundancy in a communication.
>
--
What's HOT: Honesty, Openness, Truth
What's Not: FUD--fear, uncertainty, doubt
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Fast random number generator
Date: Thu, 06 May 1999 19:20:54 GMT
On Wed, 05 May 1999 17:56:55 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (John Savard) wrote:
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
>
>>>The classical shuffling algorithm depends on a good random number
>>generator to produce small random numbers in the range [0, size-1].
>
>No, it needs more than that.
>
>It needs one random number in the range {0, 1, 2, ... size-1 }, and
>then it needs one random number in the range {0, 1, 2, ... size-2 },
>and then one in the range {0, 1, 2, ... size-3 }.
>
>Usually, the classical shuffling algorithm is implemented using a
>generator of random numbers in the range [0,1), which cnn then be
>converted easily to random integers from any range desired.
>
>My algorithm, though, only requires random bytes, and doesn't need to
>do multiplication or division to convert them to other ranges.
I assume you know that I have long used shuffling with random integers
(produced by nonlinear filtering huge Additive RNG's) to produce the
keyed tables used in all my stuff from the very beginning over a
decade ago; for example, see:
http://www.io.com/~ritter/KEYSHUF.HTM
at the bottom of the page.
In particular, an appropriate way to develop a random value of
arbitrary range is to first mask the random value by the next higher
power of 2 less one, and then reject any value beyond the desired
range. For shuffling, as the range decreases, we change the mask so
that most random values continue to be in the appropriate range. As a
result, we have no rejection at the beginning of a range, only half
rejection at the end, and so expect about one-quarter rejects overall.
No multiplication or division are needed or used; in fact, doing that
correctly is trickier than it looks. I think the masking technique is
well known.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: AES
Date: Thu, 06 May 1999 19:21:23 GMT
On Wed, 05 May 1999 14:13:47 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Bruce Schneier) wrote:
>On Wed, 05 May 1999 04:46:48 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>
>>
>>On Tue, 04 May 1999 21:39:14 GMT, in
>><[EMAIL PROTECTED]>, in sci.crypt
>>[EMAIL PROTECTED] (Bruce Schneier) wrote:
>>
>>>On Fri, 30 Apr 1999 13:12:52 -0500, "Anthony King Ho"
>>><[EMAIL PROTECTED]> wrote:
>>
>>>[...]
>>>>and algorithm such as Triple-DES is proven
>>>>to be very secure.
>>>
>>>Agreed.
>>
>>Sorry. There is NO proof of strength for Triple-DES or any other
>>cipher in cryptography.
>
>Sorry. I thought he meant "proven" in the vernacular, as in "this
>meal has proven to be very tasty." I agree that there is no
>mathematical proof of the strength of triple-DES, which has
>nonetheless proven to be very secure (ans tasty).
It turns out to be difficult to justify such a statement even using a
non-mathematical definition of "proof." For example:
We can say a race car is "proven" in practice: We can see it run for
some time at some speed and compare it to other entrants. Basically a
car is movement at speed and we can see that.
We can say a cipher program is "proven" in practice: We can see it
encipher data, produce junk, then recover the original data. We can
see whether or not the program crashes. We thus see the program
perform its functions.
But the function of a cipher is to hide information from others.
Simply using a cipher for a long time while not specifically knowing
that it exposes secrets hardly means the secrets are secure. We have
no way to *see* whether or not hiding occurs; we have no way to see a
cipher perform its function. So we simply do not have the same sort
of practical experience that we commonly call "proven."
I would say that simply using a cipher for a long time -- and not
specifically knowing it is broken -- does *not* constitute "proven
security," by any definition of "proof."
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Thu, 06 May 1999 19:25:08 GMT
[EMAIL PROTECTED] wrote, in part:
>I do believe that amateurs can design strong symmetric ciphers,
>provided they know some fundamentals, work carefully, and build
>in large safety factors.
This makes it possible that one _could_ get around the basic objection
to his proposed scheme.
>To me, a strong cipher is one for which there is no tractable
>break. If a devastating attack exists, the difficulty of finding
>it does not, in my view, have anything to do with the strength of
>the cipher.
Once it's found, it's found, so that is a valid point of view: the
difficulty of finding the break is unlikely, in reality, to approach
the difficulty of breaking a cipher without a break.
>How would you go about breaking any of 1000 given ciphers?
>Would you choose a cipher and work only on that one until you
>found a fully practical break or died?
No, certainly not.
>I'd try to approximate
>a "best first search". I'd start work on a cipher by trying
>to distinguish the permutations induced by the keyspace from
>random permutations, perhaps using weakened variants. I'd take
>the ciphers for which I succeeded and try progressively more
>practical attacks on variants that were closer and closer to
>the full versions. I don't think hiding a weak cipher among
>a thousand strong ones buys much.
A solution is needed to the "weakest link" problem. That is true, but
it is a worthwhile thing to seek.
>And not in the way people seem to think. Ciphers by themselves
>offer poor authentication, and the authentication of the selection
>channel is far more important than its privacy. If I can find a
>way to forge, I can get you to use _my_ choice of your ciphers.
I don't believe the system is to be designed so as to allow either
user to control the other user's choice of ciphers: agreement is
required from both. Once the pool of ciphers is established, the
sender would be the one making the random choice, just as the sender
generates the session key.
Given a private selection channel, and the use each time of three
ciphers taken from a pool of 1000, for example, one has:
- added 30 bits to the difficulty of a brute-force search,
- reduced the probability that the three weakest ciphers will be those
chosen to an acceptable level.
If 500 out of the 1000 ciphers are weak, one still has a problem. If
one has taken sufficient precautions to avoid that, and the remaining
risk is just that one or two ciphers in the pool might be
significantly weaker than the others, I think this approach has
succeded in improving things. Remember that even when a differential
attack exists, a considerable amount of corresponding plaintext and
ciphertext is required. A weak cipher occasionally used as a single
layer in triple encryption, however, does not have the opportunity to
be a threat to security.
Finding a sufficiently secure medium of key exchange to keep up with
the ambitious goals of this approach may well be a problem.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: AES
Date: 6 May 1999 15:45:16 -0400
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>
>On Wed, 05 May 1999 14:13:47 GMT, in <[EMAIL PROTECTED]>,
>in sci.crypt [EMAIL PROTECTED] (Bruce Schneier) wrote:
>
>>On Wed, 05 May 1999 04:46:48 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>>
>>>
>>>On Tue, 04 May 1999 21:39:14 GMT, in
>>><[EMAIL PROTECTED]>, in sci.crypt
>>>[EMAIL PROTECTED] (Bruce Schneier) wrote:
>>>
>>>>On Fri, 30 Apr 1999 13:12:52 -0500, "Anthony King Ho"
>>>><[EMAIL PROTECTED]> wrote:
>>>
>>>>[...]
>>>>>and algorithm such as Triple-DES is proven
>>>>>to be very secure.
>>>>
>>>>Agreed.
>>>
>>>Sorry. There is NO proof of strength for Triple-DES or any other
>>>cipher in cryptography.
>>
>>Sorry. I thought he meant "proven" in the vernacular, as in "this
>>meal has proven to be very tasty." I agree that there is no
>>mathematical proof of the strength of triple-DES, which has
>>nonetheless proven to be very secure (ans tasty).
>
>It turns out to be difficult to justify such a statement even using a
>non-mathematical definition of "proof." For example:
>
>We can say a race car is "proven" in practice: We can see it run for
>some time at some speed and compare it to other entrants. Basically a
>car is movement at speed and we can see that.
>
>We can say a cipher program is "proven" in practice: We can see it
>encipher data, produce junk, then recover the original data. We can
>see whether or not the program crashes. We thus see the program
>perform its functions.
>
>But the function of a cipher is to hide information from others.
>Simply using a cipher for a long time while not specifically knowing
>that it exposes secrets hardly means the secrets are secure. We have
>no way to *see* whether or not hiding occurs; we have no way to see a
>cipher perform its function. So we simply do not have the same sort
>of practical experience that we commonly call "proven."
But it's no more difficult than Bruce Schneier's original example :
"this meal has proven to be very tasty." There's no objective
standard for "tasty"; the only "proof" I can offer is that I got
a hundred people together and fed them the meal, and they all
responded positively about how it tasted.
This examples illustrates nicely some of the issues involved :
at one level of "proof", all it really means is that *I* liked the
meal, and you have no reason to believe me or to trust my judgement.
(Are you paying attention, Mr. Scott?) If I tell you I made egg-and-olive
ice cream and it proved delicious, you may not regard this as sufficient
evidence. Certainly not if you were TCBY and looking for new flavors.
At another level, I could present my meal to a large collection of people
and see what they all said. Yes, some of them might lie. Yes, some of
them might not like the meal -- but if 99% of the people said that they
liked it, that might be sufficient for you (or TCBY) to believe
that it's "tasty."
A third level of "proof" might involve a carefully selected group of
food critics and chefs known for their discriminating palettes; when
they say it's "tasty", that means even more than when the man on the
street says so.
>I would say that simply using a cipher for a long time -- and not
>specifically knowing it is broken -- does *not* constitute "proven
>security," by any definition of "proof."
Simply using a cypher? No. But a lot of experts -- read : food
critics and chefs -- have looked at DES for a long time, and so
far no one has gone on record as saying they regard it as "not
tasty." If you look at 20 years worth of restaurant reviews regarding
a particular restaurant, and without exception every one of them was
good, wouldn't that constitute effective "proof" that the restaurant
served good food?
-kitten
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
