Cryptography-Digest Digest #335, Volume #11 Wed, 15 Mar 00 02:13:02 EST
Contents:
Re: NIST, AES at RSA conference ("Trevor L. Jackson, III")
Re: how to introduce hs students to cryptography (David A Molnar)
Re: why xor?(look out,newbie question! :) ("Douglas A. Gwyn")
Re: NIST, AES at RSA conference ("Joseph Ashwood")
pedagogical provably stupid protocols (David A Molnar)
Linear Cryptanalysis and Walsh transform (Raphael Phan Chung Wei)
Re: streaming cyphers (No Brainer)
Re: Assistance needed With finding an algy that does not (NFN NMI L.)
Re: streaming cyphers (No Brainer)
Re: new Echelon article (jungle)
Re: pedagogical provably stupid protocols (D. J. Bernstein)
Re: how to introduce hs students to cryptography ("Douglas A. Gwyn")
Re: Q: Coding of music notes ("Douglas A. Gwyn")
----------------------------------------------------------------------------
Date: Wed, 15 Mar 2000 00:31:50 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Bryan Olson wrote:
> Terry Ritter wrote:
> >
> > Bryan Olson wrote:
> > >There is the seed of a reasonable proposal there: design a
> > >cipher with three layers each of a different structure and
> > >each somewhat larger than needed to resist all known attacks
> > >absent the other layers. This is a plausible approach to
> > >defending against unknown attacks and a defensible tradeoff
> > >between resources and confidence in security.
> >
> > That might be a good proposal for a new cipher design. But my
> > proposals are not about new cipher designs, but instead address how t=
o
> > use the ciphers we already have.
>
> The point is that the composition of three ciphers is a
> cipher. The distinction is artificial; it's only in your
> mind and not in the encryption function.
But there is a practical distinction. We use operations (transforms) to =
compose ciphers. We do not have a "cipher" until the collection of opera=
tions passes some threshold of cryptanalysis. This provides, in a practi=
cal but not theoretical sense, a floor on the strength of the cipher. Wh=
en we compose a stack of ciphers out of individual ciphers we are attempt=
ing to sum their strengths.
> It makes no sense
> to say any cipher a single point of failure while the stack
> is not. The set of ciphers contains the set of stacks.
True, but the set of all ciphers can be partitioned into "atomic" ciphers=
that have just enough operations to pass the threshold described above, =
those that have excess operations but may not have excess strength, and t=
hose that are composites of atomic ciphers. One can view a stack as a co=
llection of operations, by which definition every stack is a cipher. But=
this perspective is one that purposefully ignores the whole point of sta=
cking ciphers. If ciphers have any strength at all then composing a stac=
k of them will add their strengths. This is in contrast to adding more o=
perations to a cipher. Individual operations cannot be characterized as =
having any strength in a practical sense, so stacking operations cannot b=
e expected to add up to anything useful. Only a carefully orchestrated s=
et of operations makes a cipher. But any non-pathological collection of =
ciphers is probably better than an individual cipher alone.
I chose the verb orchestrated for a reason. Metaphorically data transfor=
mation operations are like musical instruments. To make music (a cipher)=
all the parts have to work together in just the right way. Making good =
music (strong ciphers) is a high art. We cannot measure either. But sel=
ecting the pieces to be played at a recital is a distinctly different pro=
cess from composing a musical piece. You could look at the entire perfor=
mance as a collection of individual notes played by various instruments.=
But you would be ignoring the difference between a piece of music and a=
collection of music even though every collection of musical pieces can b=
e considered a musical piece. Operations are not ciphers just as notes a=
re not music. Thus a cipher stack is more than an (atomic) cipher, just =
as an opera is more than a single song.
>
>
> > One goal is to use the ciphers we already have to provide a secure
> > system even if we happen to use one or two weak ciphers.
> >
> > Another goal is to terminate any existing break by changing to other
> > ciphers. This requires multiple ciphers.
>
> As previously pointed out, changing ciphers does not
> terminate breaks - it only limits the quantity of
> ciphertext. Attackers can work on any of the ciphers
> for as long as they want. Real traffic is redundant,
> so the level of protection tends toward the weakest
> system.
>
> > >But the proposals I've seen from Ritter are for the
> > >arbitrary, or even random composition without regard to the
> > >internals of the individual ciphers. What matters is the
> > >structure of the cipher we actually use, not whether we
> > >choose to view it as one cipher or three. We we want a
> > >cipher that will resist future breaks of certain classes of
> > >ciphers, then we should choose these layers because their
> > >functions are fundamentally different, not because they were
> > >once packaged separately and given different names.
>
> > That does
> > leave open the possibility that essentially similar ciphers might hav=
e
> > different names and would be used. Of course each of the ciphers in a=
> > stack would have different keys, so the issue is not one of a possibl=
e
> > weakness of composition, but instead the extent to which multiple
> > ciphers protect against attack.
> >
> > In my experience, real attacks are customized against particular
> > ciphers, not classes of ciphers.
>
> Look at differential cryptanalysis. It's applicable to
> a wide variety of ciphers, and even hash functions.
>
> > Perhaps you would be so kind as to
> > give an example of a practical attack other than brute force which
> > works in general against, say, any Feistel cipher.
>
> An absurd point for several reasons. First, if the
> inability to "give an example of a practical attack" implies
> we don't need to worry about them, then the whole thing is
> moot, since we can't name an attack that works against,
> say, Blowfish. Second, if there's one example of a
> construct without a general weakness, that in no way means
> that a few arbitrary instances should resist any attack.
> Third, in the case of Feistel ciphers we know that simple
> round structures can generate the alternating group, and
> that in the super-polynomial model of tractability, the
> existence of one-way functions implies the existence of
> Feistel ciphers without tractable breaks. A general break
> of the Feistel construct would therefore imply a break of
> essentially all the structures we use in symmetric ciphers.
>
> I find it somewhat amusing that the one person from whom
> I've read worries about a general attack on Feistel ciphers
> has also ridiculed the very possibility of a general attack
> on all complexity-based ciphers. That person is of course
> you, Mr. Ritter.
>
> > >> The issue is not *my* favorite encryption function, the issue is
> > >> *your* favorite encryption function: Whatever "simpler, faster"
> > >> function you like can be one of the three ciphers in a cipher
> stack.
> > >
> > >The issue is encryption function we use. A cipher stack is
> > >a cipher. If we can call a cipher a single point of failure
> > >without consideration of its internals, then the Ritter
> > >cipher stack is also a single point of failure.
> >
> > Just as there can be no proof of strength for a cipher, there is also=
> > no proof of strength for a cipher stack. But that hardly means both
> > cases have the same probability of weakness.
>
> You missed the point. A an instance of cipher stack _is_ a
> cipher. Is the single cipher designed with three sections,
> each strong enough to resist all known attacks a "single
> point of failure". If so, then so is the stack. If not,
> then your logic is in error from the beginning where you
> assumed any individual cipher is a single point of failure.
You are treating the condition "strong enough to resist all known attacks=
" as a constant. That is an error.
>
>
> > We have all learned about attacks on ciphers, yet I am unaware of man=
y
> > attacks that will succeed against ciphers when they are used in a
> > multiciphering stack. Any such attacks will have to make do with far
> > less information than is available when a single cipher is used alone=
=2E
>
> You are also unaware of attacks which will succeed against
> Blowfish. The issue is not attacks of which we are aware.
> In any case, a single cipher designed so its sections should
> not fall to the same sort of attack should be at least as
> good as one in which the sections are choose simply because
> the designers once packaged them as different ciphers.
>
> >
> > >> In practice, that stack will be at least as strong as your cipher.=
> > >
> > >And the square of Terry Ritter can make the same argument
> > >with the same force to justify a stack of three of Ritter's
> > >stacks.
> >
> > The point of a 3-level cipher stack is to provide security while usin=
g
> > one or even two weak cipher designs. It is true that this solution
> > does not provide security if we use three ciphers which are so weak
> > that they can be attacked in the stack.
> >
> > But since you have previously questioned the entire concept on the
> > basis that current ciphers are strong enough, it does seem rather
> > strange for you to now be suggesting that *all* the ciphers in a stac=
k
> > may be weak. Any cipher you think is strong can be present in the
> > stack, and you could demand that cipher be used in every cipher stack=
> > your system negotiates.
>
> You didn't understand my position. For any tradeoff we
> choose between resources and safety, we can do better with a
> single carefully designed cipher than with your stack.
False. A cipher stack by your definition is a carefully designed cipher.=
>
>
> > >Dan Bernstein is correct: the distinction between building
> > >ciphers from simple operations and encryption functions from
> > >ciphers is artificial.
> >
> > A distinction is hardly artificial when all practical attacks apply
> > only to one side of the distinction.
>
> Which is not the case here. If we design a layered cipher
> following the "reasonable approach" I described above, your
> stack of three might result in the very same encryption
> function. The fact that you view yours as three ciphers has
> nothing to do with what attacks will work. On the other
> hand, the fact that you choose three arbitrarily, where the
> single cipher is designed so the layers are radically
> different, suggests that the designed approach should do
> better at resisting unknown attacks.
Ridiculous. There is no sense in which careful design can be shown to be=
better against "unknown attacks" than random composition. If the attack=
s are unknown the "careful design decision are indistinguishable from ran=
dom selections.
>
>
> [...]
> > >The significant issue is the structure of one's
> > >favorite cipher, not the fact that we can always make it
> > >more complex by adding stuff.
> >
> > I would agree with that, except that I think it is intended to imply
> > more than it says.
>
> Of course. In response to Dan Bernstein, you actually wrote:
> > >> The issue is not *my* favorite encryption function, the issue is
> > >> *your* favorite encryption function: Whatever "simpler, faster"
> > >> function you like can be one of the three ciphers in a cipher
> > >> stack.
>
> Given this new stack of three, we can still make a simpler,
> faster function with at least as good a case for security.
> Your claim is like a child's boast that he can name a higher
> number than anyone else, provided he gets to go last.
You appear to be the one claiming that there is always a better way. Tha=
t careful selection of transform operations is superior to careful select=
ion of believed strong collections of transform functions. Will you next=
treat us to a rendering of "Su Madre"?
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: how to introduce hs students to cryptography
Date: 15 Mar 2000 05:28:41 GMT
Rob Kings <[EMAIL PROTECTED]> wrote:
> Well for my 2 pence worth, I don't know how old 12th grade is (being
> English) but starting with lectures on number theory sounds a bit heavy. I
Just so you and any other non-US posters know -- 12th grade is the last
year of high school in the US. The students will be in the neighborhood
of 17 to 18 years old. The original poster is in a better position to
write about their math preparation than I am, since that varies widely
from school to school and student to student.
Thanks,
-David
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: why xor?(look out,newbie question! :)
Date: Wed, 15 Mar 2000 04:47:13 GMT
"r.e.s." wrote:
> That there may be several such "rules of thumb" doesn't affect the
> conclusion that to use either Kullback's statistic or Pearson's
> chi-square, the same caveat applies -- viz., that the categorized
> random variables be independent.
They don't have to be independent; in fact, Kullback & Gokhale
wrote a book about how to use the information statistic much
like ANOVA.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Tue, 14 Mar 2000 21:48:43 -0000
My basic point is that it is important to always sign the
plaintext, signing the ciphertext only presents another like
of attack.
Joe
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: pedagogical provably stupid protocols
Date: 15 Mar 2000 05:55:34 GMT
Does anyone know of any simple examples of protocols which can be
"proved" or otherwise convincingly and *correctly* argued as "good" --
but according to a fatally flawed definition of goodness?
This question is motivated by an attack I heard about on an optimistic
contract signing protocol. In this protocol, parties send messages back
and forth, and have the option of invoking a trusted third party if
anything goes wrong. In normal operation, the third party will look at
its log of received messages and either abort the protocol or provide
both parties with a mutually signed contract.
The problem was that one party could wait until after it had received
a signed contract, then invoke the trusted third party. Under some
special circumstances, this could cause an abort and leave only one
party with a mutually signed contract. The definition of "fair
exchange" used for the proof of this protocol didn't
take this into account. As a result, while the protocol was
"provably" fair, you could acheive a manifestly UNfair result from it.
That's the idea, anyway. I don't have it written down anywhere, so I am
sure I have the details wrong. If the details are around, I'd love to
know where.
Another example comes from Birgit Pfitzmann's classic paper (ok,
1995) on "How To Break ANOTHER 'Provably Secure' Payment
Scheme". Here, the problem was that the payment scheme enforced
anonymity and security by making use of zero-knowledge proofs which were
not themselves anonymous. While not exactly the same kind of "flawed
definition" as the previous case, it's still an example of what I'm
looking for : good proofs, bad definitions, worse consequences.
The problem is that both these examples are fairly sophisticated. I
would like something I can show to my not so cryptographically oriented
friends and have them understand without too much handwaving.
In addition, I am now writing columns for the ACM Crossroads magazine,
and would like to put together something clear and accessible to a wide
audience on the problem of crypto definitions.
Has anyone seen any such protocols?
Thanks,
-David Molnar
------------------------------
Date: Wed, 15 Mar 2000 14:14:54 +0800
From: Raphael Phan Chung Wei <[EMAIL PROTECTED]>
Subject: Linear Cryptanalysis and Walsh transform
Hi,
It is stated that the Walsh transform can be used as a measure of the
linearity of a boolean function. It is used to determine the
correlation of a number of input bits to an output bit.
How do we use the Walsh transform to do that? How do we use Walsh
transform on a nonlinear equation such as
F(A, B, C) = ABC xor BC xor B xor C in order to obtain server linear
approximations with probability not equal to 1/2 ?
--
Regards,
Raphael Phan
Faculty of Engineering
Cyberjaya Campus
Multimedia University
+603-83125314
------------------------------
From: No Brainer <[EMAIL PROTECTED]>
Subject: Re: streaming cyphers
Date: Wed, 15 Mar 2000 14:04:06 +0800
Steve,
On Tue, 14 Mar 2000 09:00:06 -0800, "Steve A. Wagner Jr."
<[EMAIL PROTECTED]> wrote:
> If I understand correctly, you are concerned that each block is legitimate and
> you imply that sender address can be forged and intercepted so that
> simultaneously two or more parties could be sending packets supposedly from a
> valid source.
Basically, yes (if you are talking about the middle man).
> I recommend some PRNG seeded by the first packet as a running key to decrypt
> each proceeding packet.
Understand this.
> The first packet would contain a public key encrypted session key that would
> then be used to generate subsequent keys.
If you had a PRNG that ALWAYS produced CERTAIN session keys based on a
particular seed then this would be OK, however I thought that's what a PRNG was
NOT supposed to do - that is, always producing a particular session key based on
the seed? Please correct me if I'm wrong.
> Each packet could contain a hash of the decrypted information to know whether
> to proceed in cycling to the next random key.
Yep, I can understand this too :)
> Or.. you could just send any RIV's and public key encrypted and signed packet
> along with hash values of each subsequent ciphertext block as the first
> packet, and decrypt accordingly.
So you're saying just use one session key? I thought of this, however I read
somewhere that having multiple packets encrypted with the same key can make
cryptoanalysis easier?
> Hope that has helped. Anyone have better idea?
> --SAW
Well if your first suggestion re PRNG's and predictable session key outputs
using constant seeds, then yes, it will certainly help.
Thanks.
> No Brainer wrote:
>
> > To all,
> >
> > I was wondering what is the best method to encrypt/decrypt/create a
> > message digest/sign data etc...if all you have is a small window to
> > encrypt/decrypt/digest and sign the data with?
> >
> > For example, if someone wanted to stream video to another person and the
> > receiver had to check the validity of the sender but could only receive
> > (and HAD to process in stream format) approx. 2k at a time, how would it
> > be best done? Remember that the receiver cannot receive the whole
> > message to check the sig?
------------------------------
From: [EMAIL PROTECTED] (NFN NMI L.)
Subject: Re: Assistance needed With finding an algy that does not
Date: 15 Mar 2000 06:15:37 GMT
My GOD, that post was nearly incomprehensible.
S.T.L.
------------------------------
From: No Brainer <[EMAIL PROTECTED]>
Subject: Re: streaming cyphers
Date: Wed, 15 Mar 2000 14:11:11 +0800
Paul,
On Mon, 13 Mar 2000 17:46:04 -0500, Paul Koning <[EMAIL PROTECTED]> wrote:
> > No Brainer wrote:
> >
> > > To all,
> > >
> > > I was wondering what is the best method to encrypt/decrypt/create a
> > > message digest/sign data etc...if all you have is a small window to
> > > encrypt/decrypt/digest and sign the data with?
> > >
> > > For example, if someone wanted to stream video to another person and the
> > > receiver had to check the validity of the sender but could only receive
> > > (and HAD to process in stream format) approx. 2k at a time, how would it
> > > be best done? Remember that the receiver cannot receive the whole
> > > message to check the sig?
> Yes, there's a simple solution. IPSEC does essentially this:
> each packet is separately authenticated, because there is no
> assumption that all packets will be delivered.
>
> You can do this efficiently by arranging for a shared secret
> (for example, by Diffie-Hellman key agreement, but be sure to
> authenticate the other end and guard against men in the middle).
> Then you use that shared secret as the key for a keyed hash,
> such as HMAC-MD5. That can be calculated efficiently and
> works well even for modest size blocks.
>
> Take a look at the IPSEC specs (RFC 2401 and friends) for more.
Thanks Paul...I'm looking at the RFC right now :)
------------------------------
From: jungle <[EMAIL PROTECTED]>
Crossposted-To: alt.politics.org.cia,alt.politics.org.nsa
Subject: Re: new Echelon article
Date: Wed, 15 Mar 2000 06:22:08 GMT
the correct link is
http://www.wired.com/news/politics/0,1283,34932,00.html
[EMAIL PROTECTED] wrote:
>
> http://www.wired.com/news/politics/
> 0,1283,34932,00.html
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: pedagogical provably stupid protocols
Date: 15 Mar 2000 06:26:33 GMT
David A Molnar <[EMAIL PROTECTED]> wrote:
> Does anyone know of any simple examples of protocols which can be
> "proved" or otherwise convincingly and *correctly* argued as "good" --
> but according to a fatally flawed definition of goodness?
The standard example is the original RSA system, which didn't hash the
message being signed.
Forging a signature on a chosen message was extremely difficult. In some
variants of the system, forgery was provably as difficult as factoring.
But the system was horribly insecure: an attacker could trivially forge
signatures on random messages, or on various alterations of previously
signed messages.
---Dan
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: how to introduce hs students to cryptography
Date: Wed, 15 Mar 2000 05:10:54 GMT
Scott Contini wrote:
> I would suggest starting by introducing students to "classical
> cryptography" and breaking such cryptosystems. It is worth
> spending a lot of time on this subject so students understand
> the difficulty of creating a secure cryptosystems, and the tricks
> an adversary will try to break a cipher. They should be able to
> easily write programs that can assist them in breaking simple ciphers,
> such as Vigenere cipher. The more experience they get doing actual
> cryptanalysis by themselves, the better (in terms of knowledge
> gained and enjoyment) it will be for them.
I agree in general with this sentiment. It is insane to try to
teach youngsters professional-level *any*thing. They need material
they can readily *master* (if they apply themselves), not
frustration. The absolutely first step should be exploring the
simple substitution cipher (use a key to produce the keyword-mixed
alphabet), then how to break it using patterns and frequency analysis.
That motivates more complicated systems, e.g. periodic polyalphabetic
(use the key to select among shifted standard alphabets), and
discovering how to break them can be quite enlightening, bringing in
ideas of correlation (which can be tied into chi-square). Computer
programs to implement attacks on such systems are simple enough to be
feasible at the high-school level. You could then explore the idea
of an "uncrackable" cipher, resulting in the non-repeated key idea
(OTP), and show what happens when the same random key is used (use
shifted standard alphabets) for two messages, and even see if they
can find the alignment for partial overlap (applying the principle
of correlation). Throughout, ideas of probability and simple
statistics can be introduced.
Reynard's "Secret Code Breaker" series can provide good, affordable
instructional materials for such a course:
http://codebreaker.dids.com/fbooks.htm
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Q: Coding of music notes
Date: Wed, 15 Mar 2000 05:12:02 GMT
Mok-Kong Shen wrote:
> Could someone give links on coding of music notes for computer
> processing? Are there any coding standards? Thanks.
MIDI is the nearly universal standard for this.
A Web search should turn up *plenty* of references.
------------------------------
** 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
******************************
