Cryptography-Digest Digest #442, Volume #9 Wed, 21 Apr 99 21:13:03 EDT
Contents:
Re: Question on confidence derived from cryptanalysis. (Terry Ritter)
Re: SNAKE#14... (Peter Gunn)
Re: Magenta and DFC descriptions added to web site (John Savard)
Re: A Puzzle To Solve ("Dan")
Re: A Puzzle To Solve (Ian L. Morkey)
Re: Question about DH keys? ("Arthur N. Klassen")
Re: Question on confidence derived from cryptanalysis. (John Savard)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(John Savard)
Re: Free chapters from Handbook of Applied Cryptography (Ian L. Morkey)
Re: Question on confidence derived from cryptanalysis. (John Savard)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Question on confidence derived from cryptanalysis.
Date: Wed, 21 Apr 1999 21:33:47 GMT
On Wed, 21 Apr 1999 19:07:13 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (Earth Wolf) wrote:
>On Mon, 19 Apr 1999 19:05:13 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>
>>I have just previously covered my main argument, which is basically
>>that IN MY OPINION, with a single standard cipher, there will be far
>>too much value at risk to endure even a small possibility of
>>single-cipher failure.
>
>Depends on what you're trying to protect. Is it tactical or strategic
>information? i.e. does it have to be kept secret for the next
>millennium, or will it be public knowledge at 9:00 a.m. next Tuesday?
>If this secret is revealed, will I lose a hundred dollars on the stock
>market, or will the world be sucked into a black hole?
I guess "yes." If there is just one standard cipher, the issue is not
so much what any one of us has to lose as it is what society as a
whole has to lose.
>Is my quest for
>the "ultimate" cryptosystem going to be so horrendously cumbersome
>that the users will refuse to use it? Is the decrease in bandwidth
>going to prevent vital information from being disseminated in a timely
>fashion?
I see no particular reason why good cryptography cannot be relatively
efficient. There might be some control overhead which might average 5
or 10 percent. Some particular ciphers might well elect to insert
"null's" to a greater extent that we have seen. But if users can
select ciphers, they can choose to not select those which have the
problems that matter to them.
>Remember Pearl Harbour, where warning of the impending attack arrived
>by messenger amid the smoking aftermath? A clear case of how too much
>security can be almost as bad as none at all. Real world security
>deals with these kinds of trade-offs in a way that your ivory tower
>thinking can never comprehend, I'm afraid.
I see a future in which most cryptography is mostly hidden, and is a
minor overhead to communications. I see homes and businesses in which
every wall switch and every lamp control is a networked device. And
if we want to control those from the Internet, all of that stuff will
need good crypto. Every light switch.
>>1) I dispute the idea that by applying various attacks to a cipher we
>>somehow can predict how it will perform on future unknown and
>>potentially unrelated attacks. (And if this were true, we should be
>>able to see the effect with respect to past ciphers. This should be
>>measurable and quantifiable in a scientific sense. But we have no
>>such reports.)
>
>What kinds of reports are you looking for? There are lots of archaic
>ciphers which were considered unbreakable in their day which are
>child's play to solve with modern technology. The Jefferson wheel, for
>example. What more were you looking for?
The question is not what *I* am looking for. My position is that no
rational extrapolation of past tests to future strength is possible.
The lack of literature containing such a thesis is consistant with my
position, and inconsistant with the alternative.
>>In summary: 1) We cannot estimate the probability that an effective
>>attack exists which we did not find;
>
>Of course we can. I estimate it to be 17.375%. It may not be the most
>reliable estimate, of course :-)
Yes. Quite amusing.
>>I thus claim that we CAN know nothing of the
>>probability of future cipher failure, and cannot even reason that this
>>probability is "small." The practical consequence of this is that we
>>cannot trust any cipher.
>
>I'll trust DES a heck of a lot more than I trust ROT-13. And I'll
>trust 3DES a heck of a lot more than I trust DES.
You are free to do as you will, including your own interpretation of
trust. However, I suspect that your meaning of "trust" for
cryptography will differ than the "trust" of other things.
My guess would be that you "trust" DES because nobody has openly
demonstrated that they can break it. So if you worry that your
information will be stolen by academics, you *can* have some
reasonable degree of trust in DES.
But if you use cryptography to protect your information from those who
operate in secret and hide their successes, you have no data upon
which to base trust. As Savard has pointed out, these people cannot
be *less* capable than academics (unless they cannot read); that means
it is *quite* likely that they are indeed *more* capable. Since you
can have no published experience to guide you on the risk of using DES
in such an environment, how will you gain any "trust" in it at all?
>>IF we were willing to assume that our Opponents would use only the
>>attacks we know and have tried, presumably we *could* have insight
>>into the amount of effort needed to break a cipher (although we might
>>have screwed up in testing). But I am of the opinion that we cannot
>>assume that our Opponents have our limitations. Indeed, I think this
>>is very basic cryptography.
>
>No, basic cryptography involves making your best estimate of your
>opponents' capabilities and desiging a cipher which, to the best of
>your knowledge, will be impervious to those capabilities for as long
>as it needs to be.
No, that is basic *military* cryptography, where we have known
opponents and can better estimate both the probability and
consequences of cipher failure.
Basic *social* cryptography (for lack of a better term) must concern
itself with every non-military use for hiding data. Much of this will
be financial and industrial data which is as much or more of a part of
the strength of society than pure military power. Those who might
attack such data are quite diverse, each with their own motives. And
the consequences of a successful attack could be almost universal.
>From this I conclude that the use of a single standard cipher
throughout society would be an unthinkable risk.
>>And upon what evidence do you base you opinion that we *can* predict
>>what our Opponents can do?
>
>Basically, the same way we can predict what the surface temperature is
>on Mercury, or anything else that cannot be measured directly. We take
>what observations we can and attempt to extrapolate what we *don't*
>know.from what we *do* know.
And this is the same sort of answer we have had several times before
with the driving analogy: when we drive, we know the consequences.
When we measure temperature, we are sensing reality. But when a
cipher fails we have no indication of failure.
When there is no indication of failure, there is nothing to
extrapolate. And when there is no measure for the thing which fails,
there is no meaning to extrapolation.
>That's basic physics, btw. :-)
And we see just how well it did.
>>Presumably, you would handwave about what our Opponents can do both
>>now and in the future and say that caution is silly. But that
>>conclusion is based on your opinion that we can predict what others
>>may do in the future, which I find very strange. If that were true in
>>general, we could put criminals in jail before they did anything.
>
>This author makes no distinction between being able to predict
>something with 100% accuracy and being able to predict something with
>lesser accuracy. For example, magician and card-sharp John Scarne once
>described playing gin rummy (for money) with a player who, after
>shuffling the cards, would square up the deck with the bottom facing
>towards him. An innocent-seeming idiosyncracy, except that he now knew
>the bottom card in the deck (which in gin rummy never comes into
>play). Suppose this card were the 8 of hearts; the player cannot
>predict, with 100% accuracy, what the next card in the deck will be,
>but he knows it will not be the 8 of hearts. This seemingly
>insignificant piece of information gives him a huge advantage; he
>knows that there is little percentage in trying to fill a meld of 8's
>or a run of 6-7-8 or 8-9-T of hearts, and none whatsoever in trying to
>fill an inside run of 7-8-9.
>
>In studying PRBGs, ability to predict the next bit with a probability
>of 0.5 + epsilon, where epsilon is a small number (usually on the
>order of 1/polynomial(log n) ) can be a huge advantage.
I assume this analogy is intended to show that in some cases one can
use past observations to usefully predict the future. Such is the
role of most industrial knowledge. But this analogy is inappropriate
for the issue being discussed.
The issue is whether cryptanalytic results can be used to compare the
strength of ciphers with respect to the future abilities of unknown
Opponents. In the above analogy, the Opponent is known, his weakness
already judged, and ongoing results measurable. The cryptography
issue has no such convenient touchstones.
>>With respect to the problem of potential catastrophic failure from a
>>single-cipher system, no amount of cryptanalysis can prevent such
>>failure. Both untested ciphers and massively-tested ciphers are the
>>same in the sense that neither can be trusted.
>
>Rubbish. I don't trust Charlie the counterfeiter, Ernie the embezzler,
>Rocco the rapist, or Sammy the serial killer. But I can give you a
>rough estimate of who I'd *least* like to crash my sister's slumber
>party.
I have no idea what this means.
I see no reason to change my statement, since it is correct as it
stands.
I suppose the issue here is your interpretation of "trust," which I
touched on earlier.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Peter Gunn <[EMAIL PROTECTED]>
Subject: Re: SNAKE#14...
Date: Wed, 21 Apr 1999 22:57:51 +0100
Thomas Wu wrote:
> Peter Gunn <[EMAIL PROTECTED]> writes:
> >
> > Thats no fun at at all, and well, its been facinating
> > investigating all this stuff, and the associated maths
> > (not that I fully understand it all (yet?) :-)
> >
> > Anyways, Ive had a good think about it and I've got an idea
> > or two yet... have a look at SNAKE#14...
> >
> > A,T,B,R are random
> > H() is a one way hash
> > P=H(password)
> > E[k](x) is x encrypted with key k
> > U is the user identifier
> >
> > all arrith mod p, a large safe prime
> >
> > 1) A->B: g^AT, U, g^TP
> > 2) B->A: g^BR, g^RP
> > 3) A->B: E[H(g^ATBR)](E[P](A))
> > 4) B->A: E[H(g^ATBR)](E[P](B))
>
> *sigh* MITM at step (3) has E[P](A), takes messages g^AT and g^TP
> from step(1), guesses P':
>
> A' = D[P'](E[P](A))
> x = (g^AT) ^ (A'^-1)
> y = (g^TP) ^ (P'^-1)
>
> If P == P', then A == A' and x == g^T == y. It doesn't matter that
> T is secret, it's all still broken.
>
> > if B is a MITM and tries to guess all values for
> > P, he needs to be able to check that E[P'](A)
> > decrypts to the correct value... I dont think he
> > can check against g^AT since he doesnt have T,
> > and he cant check against g^TP, and combining
> > things doesnt seem to help.
>
> Invalid hand-waving, as shown above.
>
> > All comments appreciated :-)
>
> Could you at least spend a little time analyzing your protocols
> before posting them? Of the fourteen SNAKEs you've posted, at
> least ten of them have all been broken by basically the same
> attack. I hope your client/employer doesn't have DejaNews...
Careful :-)
That could easily be misread as a very arrogant and
presumtuous insinuation that you are in no position to
make, but I'm sure you mean you hope my employer doesnt
think I'm wasting my time at work investigating encrypted
key exchanges when I should be doing something productive?
As you'll see from the time of posting its nearly all
eventing/weekend stuff, and it is a purely academic
pursuit.
I'm sure you'll find that the issue of key exchanges
(or the maths involved) isnt as well understood by the
general (even technically oriented) populous as its
is by yourself, and David. In fact most folks Ive
chatted with (albeit other laymen), including those
interested in cryptography, either dont believe its
possible to have a strong session with a short key,
or the issue is of significant value compared with
traditional symmetric or public key encryption.
However, I think its one of the most significant
things Ive come across in my very brief investigation
of cryptography, but, I suppose this is a matter for
talk.politics.crypto :-)
Thanks for your help anyways, I'll shut up now.
ttfn
PG.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Magenta and DFC descriptions added to web site
Date: Tue, 20 Apr 1999 18:38:19 GMT
[EMAIL PROTECTED] (John Savard) wrote, in part:
>The description of Magenta will need to be improved by adding some more
>diagrams; as it is, there is one diagram, added to a page largely derived
>from some of my recent posts.
Now, at
http://members.xoom.com/quadibloc/co040811.htm
a diagram has been added showing how an entire Magenta round works. It is
one of the more detailed and intricate diagrams on the site...
John Savard ( teenerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: "Dan" <[EMAIL PROTECTED]>
Subject: Re: A Puzzle To Solve
Date: Wed, 21 Apr 1999 19:15:18 -0400
Sorry if the file attachment was a problem. I didn't think that 120 K would
be a problem.
It was the easiest way that I could think of to convey the information that
the message refers to. The file is plain HTML so anyone should be able to
read it.
Dan [EMAIL PROTECTED]
Ian L. Morkey wrote in message <[EMAIL PROTECTED]>...
>This is the above referenced message without the attachment, for those who
>don't want to download a 2092 line message just to see what it is:
>
------------------------------
From: [EMAIL PROTECTED] (Ian L. Morkey)
Subject: Re: A Puzzle To Solve
Date: Wed, 21 Apr 1999 22:28:10 GMT
This is the above referenced message without the attachment, for those who
don't want to download a 2092 line message just to see what it is:
"Dan" <[EMAIL PROTECTED]> wrote:
>Hello All,
>I am relatively new to the world of encryption and am learning more every
>day. Much of which I have learned from a friend of mine, who has sent me an
>interesting puzzle to solve.
>
>The object is to figure out the original text for the encrypted text,
>however I am stumped.
>
>In the attached HTML file you will find a table with a series of fields the
>first of which contains the input text, the next field contains the
>encrypted text, and the tables following that contain the asc() character
>codes of each character in the encrypted field numbered 1, 2, 3, etc... One
>interesting thing is that the input text has a maximum length of 14
>characters but the output (encrypted) text contains 16 characters and seems
>to be divided in half 8 and 8 judging from the obvious pattern in the asc()
>character codes, and perhaps even reversed like "ABCDEF" = "CBAFED"
>
>The last record is the one to be finally decrypted "To Be Decrypted>" Also,
>one final note. The field containing the "f" does actually have a null
>output.
>
>Well, thats it. Any help in solving this puzzle will be greatly appreciated.
>Thanks,
>Dan [EMAIL PROTECTED]
------------------------------
From: "Arthur N. Klassen" <[EMAIL PROTECTED]>
Subject: Re: Question about DH keys?
Date: Thu, 22 Apr 1999 00:11:43 GMT
John Matzen wrote:
>
> Are the keys in Diffie-Hellman interchangable? That is, can I encode a
> session key with the public key and decode it with the private key, and
> vise versa?
Yes. That is how PGP signatures are done. Some information about a
message, including time and a secure hash of the message is generated.
This is encrypted with your private key. The recipient can decrypt it
with your public key and know that -you- said -that-, whatever possibly
silly, benighted thing it was you said. :)
cheers...ank
--
[EMAIL PROTECTED] | The word "mercy"'s gonna have a new meaning
<*> | +t+ -> | |0 !! | when we are judged by the children of our slaves
PGP: **** 2047/DCDF9341:E273 AD0E F99A 8869 050B 5E92 0E47 C151 **** two
finger- *** 30DF 376C 43D0 DA74 F33F 752C 192E 3711 5E52 02BF *** prints
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Question on confidence derived from cryptanalysis.
Date: Thu, 22 Apr 1999 00:21:12 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote, in part:
>On Tue, 20 Apr 1999 20:35:53 -0400, in <[EMAIL PROTECTED]>,
>in sci.crypt Geoff Thorpe <[EMAIL PROTECTED]> wrote:
>>Before I get accused of doing precisely what I don't want to do (lock
>>horns, duke it out, etc) ... let me just say that I really am warming to
>>an idea implicit in all of this - and I believe it is one of yours,
>Son of a gun, it *is* one of mine. Why, what a surprise!
>>though it was Trevor I think who recently illustrated it quite well ...
>>namely the employment of a standard bank of ciphers that can be invoked
>>on demand in any number of possible configurations eg strung together in
>>a different order every time, utilising the different modes of
>>operation, etc etc.
I've caught myself stealing some of your ideas - usually in E-mail
discussions - and although I suspect what I've done in Mishmash (see
Quadibloc III) isn't really the same idea, it uses _part_ of it, in a
limited form so as to fit within the framework of a "conventional" block
cipher.
>>And frankly, I still place a lot of stock in what *I* rank as
>>ciphers of tested strength and wouldn't want any system of mine having
>>too many "new toy" ciphers creeping in. Perhaps we need to agree to
>>disagree.
>First, we want to be able to plug in arbitrary ciphers.
>Next, we want to be able to accommodate essentially unlimited future
>ciphers, and do so in a way which does *not* require a central
>registration facility (which thus must be operated and funded), with
>its inherent submission, approval, and listing delays.
>Then we want to satisfy users desire for particular ciphers, or to
>*not* use particular ciphers.
Which is indeed the point where agreement is restored.
>Next, we want to support changing ciphers mid-conversation.
This makes it clear enough that you are in a different and more advanced
realm than what I was worried about having "stolen".
While there will be pressure to adopt the standard ciphers for
interoperability, such a system definitely does allow for a new cipher to
become a new part of the set.
>We can no more have absolute "trust" or absolute "confidence" in the
>strength of a layered system than any one cipher. But what I think we
>*can* say is: 1) the stack is not weaker than any of the components,
>and 2) the stack prevents single-component failure from being an
>overall failure. We might *speculate* that this "lessens" the
>probability of failure. But since we cannot measure any of these
>strengths or probabilities, that seems like yet another chimera just
>better ignored.
Unless we fall for that chimera - unless we believe that adopting a layered
system will do some good, and reducing the probability that our messages
will be read is indeed the only goal pursued here - why bother? Of course,
(1) and (2) are valuable in themselves: essentially, (2) is worthwhile
pursuing because of the _possibility_ (absent any provably existing nonzero
probability) that it will _reduce the probability of failure_.
Even when no progress towards a goal can be proven to have taken place, it
is impossible to avoid, however chimerical it may be, evaluating measures
taken to achieve a goal in terms of that goal. Even when all we have are
possibilities instead of probabilities.
And just as using a layered system doesn't *prove* anything, so does using
ciphers that have been studied and found to be resistant against a variety
of known attacks. Yet it seems like a sensible thing to do, for want of
anything better.
Using a secret cipher of your own for your own communications *also* makes
sense, for different reasons, and using the latest and greatest design, not
very well tested yet, because it has a larger key size also makes some
sense, and so does using an obscure cipher that attackers may not have
bothered with. Because there _are_ different "sensible" things to do than
are necessarily popular or respectable - and more sensible things to do
than any one cipher can embody - the layered use of multiple ciphers is a
good idea. Even if it proves nothing.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Wed, 21 Apr 1999 23:41:13 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote, in part:
>[EMAIL PROTECTED] (John Savard) wrote:
>>Given that a cipher highly resistant to known attacks (i.e., differential
>>cryptanalysis) _could_ still be very weak, as far as we know, what can we
>>do about it? The closest thing to a sensible suggestion I can make is this:
>>make our ciphers stronger (that is, use more rounds) and more intrinsically
>>difficult to analyze (use complicated, highly nonlinear, constructs) than
>>the known attacks indicate is necessary.
>We could hardly disagree more.
>I find "rounds" (the repeated application of the same operation) silly
>and I don't use them. I do use "layers" in which different operations
>are applied in each layer.
>And I think that making a cipher more difficult to analyze can only
>benefit the Opponents who have more resources for analysis.
>Personally, I try to make ciphers as conceptually *simple* as possible
>(though not simpler). Simple does not mean weak; simple means
>appropriately decomposing the cipher into relatively few types of
>substantial subcomponent which can be understood on their own, then
>using those components in clear, structured ways.
It certainly does make sense to understand the parts of a cipher, to ensure
that the cipher is providing, as a minimum, some basic level of "security":
that is, for example, one might know that one's cipher is at least as
secure as DES, even if one doesn't know for sure that the effort required
to break DES is not trivial.
The original poster - Sundial Services - praised your Dynamic Substitution
because it "buries a lot more information" than ordinary designs, and this
is the sort of thing I'm thinking of. When I got past his first paragraph,
where he seemed to have forgotten about S-boxes, and saw that DynSub and
the SIGABA were the kinds of designs he praised, I saw that the kinds of
ciphers that appeal to him were the same ones as appeal intuitively to me.
Precisely because you have noted that we don't have a way to put a good
lower bound on the effort required to break a cipher, I find it hard to
think that I could achieve the goal, for a cipher, that is indeed
appropriate for a scientific theory, of making it "as simple as possible,
but no simpler"; if I am totally in the dark about how strong a cipher
really is, and how astute my adversaries are, that seems an inadvisable
goal, because I can never know what is necessary.
Since I have an upper bound instead of a lower bound, unless there is some
way to resolve that problem, and your researches may well achieve something
relevant, even if not a total solution, all I can do is try for a generous
margin of safety. True, it's not proof. But proof isn't available, except
for the one-time pad.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (Ian L. Morkey)
Subject: Re: Free chapters from Handbook of Applied Cryptography
Date: Thu, 22 Apr 1999 00:31:05 GMT
[EMAIL PROTECTED] (Alfred John Menezes) wrote:
>As some of you may know, we recently made available the following 5
>chapters:
...
>from our "Handbook of Applied Cryptography" for free download from
>our web site: www.cacr.math.uwaterloo.edu/hac/
I think that URL is wrong. The one in your signature works, though:
> www.cacr.math.uwaterloo.ca/hac/
--
"Ian L. Morkey" better known as [EMAIL PROTECTED]
012 3 456789 <- Use this key to decode my email address.
Fun & Free - http://www.5X5poker.com/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Question on confidence derived from cryptanalysis.
Date: Wed, 21 Apr 1999 23:58:27 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote, in part:
>I guess "yes." If there is just one standard cipher, the issue is not
>so much what any one of us has to lose as it is what society as a
>whole has to lose.
>From this I conclude that the use of a single standard cipher
>throughout society would be an unthinkable risk.
Here, you and I are in agreement. New attacks are being found against
symmetric block ciphers, such as the boomerang attack and the slide attack.
Also, one of the papers on the NIST site is called "Future Resiliency", and
it is a defense of that point of view.
However, I don't think that for the AES process to pick one winner will
lead to that situation, any more than the existence of DES has stopped
people from using IDEA or Blowfish.
If anything, I'm more worried about a lot of messages suddenly becoming
readable through a catastrophic failure of public-key cryptography. But
such a failure at least is likely to become public knowledge; an
organization doing the precomputation required, or finding a hidden flaw,
and secretly breaking "the" block cipher without anyone knowing certainly
is a real possibility.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
** 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
******************************
