Cryptography-Digest Digest #294, Volume #9 Sun, 28 Mar 99 08:13:02 EST
Contents:
Re: Live from the Second AES Conference (Bruce Schneier)
Re: Live from the Second AES Conference (Bruce Schneier)
Re: Live from the Second AES Conference (Bruce Schneier)
Re: Is TEA Algorithm safe???? (Bruce Schneier)
Re: Symmetric vs. public/private (Bo Dömstedt)
Re: Live from the Second AES Conference (David Crick)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Live from the Second AES Conference
Date: Sun, 28 Mar 1999 11:28:19 GMT
>Subject: Re: Live from the Second AES Conference
>Date: Wed, 24 Mar 1999 14:18:38 GMT
>From: [EMAIL PROTECTED]
>Newsgroups: sci.crypt
>
> Sean Murphy described properties of Twofish pertaining to its key
> schedule. First it was shown that the whitening keys (XORed with
> the data before and after the main cipher) are not uniformly
> distributed, i.e. take not all possible values. In a similar vain,
> each 8-byte round subkey also cannot take all possible values.
> Ideally, of course, all key material within a cipher should be as
> close to random as possible, otherwise an attacker gains some
> predictive power. Later in the afternoon workers from the Twofish
> team explained exactly how much entropy was lost: the whitening
> key has 117 bits of entropy (instead of the optimal 128) and each
> round key has 63.2 bits of entropy (instead of 64). They claimed
> this is not a useful cryptanalytic property which does seems
> reasonable.
This was a really nice result, by the way. They sent us a draft of
the paper some weeks before the conference, and we were able to
investigate what they found further. The whitening issue is not a
problem because all you need cryptographically out of a whitening
function is half the length of the block in entropy. Hence, for AES
candidates only 64 bits of entropy are needed. For example, RC6
only bothered using whitening on half the block for this reason. We
decided to whiten the entire block, but still this is not an issue
The other thing they noticed is that sequential round subkeys do
not have full entropy. This is, of course, true, as it is for pretty
much any cipher with round subkeys. DES has this feature even more
severely. There's no attck here; never has been against any cipher.
Copies of our report discussing this observation and its ramifications
can be found on the Twofish homepage:
http://www.counterpane.com/twofish.html
> Then came David Wagner's exposition of the attack on Frog. David,
> by the way is still only a student in California. I liked his
> description of Frog as a cipher where the "wires" are parametrized
> to the key. This means that Frog looks like a large collection of
> individual ciphers with different internal wiring.
This is really the proper way to look at ciphers with key-dependent
diffusion properties.
> The basic point
> is that the attacker can search and choose the instances where
> this wiring defines a weaker cipher, and then mount an attack on
> the weak key that gave rise to this configuration. (For those
> familiar with Frog the weak wiring happens when the bombpermu
> pointer addresses the previous byte.) It turns out that 2^(-33) of
> the keys are now weak and that in these cases the key can be
> broken with 2^58 chosen plaintexts. The decryption function of
> Frog has much slower diffusion (something first noticed by John
> Savard, a frequent participant in sci.crypt) which allows for a
> more successful attack that requires 2^36 chosen ciphertexts and
> works for 2^(-29.3) of the keyspace. A linear attack on Frog was
> also described.
Look at CAST-256 and Mars, and you can see what a cipher looks like
when it has balanced diffusion in both directions.
> Frog-like ciphers do have this kind of problem: by putting some or
> most of the functional definition of the cipher within the key,
> the possibility exists that some of these functions will be weak.
> I suppose there are ways to fix Frog in order to strengthen it
> against the differential and lineal characteristics discovered by
> Wagner and achieve a much lower or zero number of weak keys,
> trivially: suppress the weak wiring configurations. (I did ask him
> to propose a fix but he was not forthcoming - I wonder whether
> using ADDs instead of XORs for diffusion would cut it).
Better would be to get rid of the key-dependent permutation. Figure
out which permutation gives you the best diffusion and use that for
all the keys. Why make some of the keys worse than the others?
> The really
> interesting question though is to find out if a generalized
> version of Frog that just follows its design principles to a
> higher degree would increase or decrease the frequency of Wagner
> weak keys. The whole idea in Frog is to do nothing designed
> specifically as a defense against a particular attack. So if
> Generalized Frog turns out to be weaker against Wagner's attack
> then it is bad news for the basic idea. But, if it turns out that
> "purer" (even less structured) forms of Frog are more resistant,
> then confidence in Frog's design principle will increase. So
> Wagner's attack can be used as a platform to evaluate the design
> methodology, something even more important than the candidate
> cipher itself.
I think that extending this type of design strategy will end up with a
weak cipher. If you take a design element and make it key dependent,
then you run the risk of having weak keys. Diffusion is a
particularly bad thing to make key dependent.
Some years ago a cryptographer proposed RDES, a variant of DES
where the left-half/right-half swapping was key dependent. It was
broken using exactly this same kind of "weak key" cryptanalysis.
> Kazukuni Kobara next discussed a very theoretical paper on
> pseudorandomness. After her talk somebody had to ask her how this
> work relates to E2, to which she answered, as if just remembering,
> that E2 does indeed achieve optimal pseudorandomness after two
> rounds. It is interesting to observe how cultural characteristics
> have an impact in this international process. The designers of the
> Asian candidates (E2 and Crypton) are really far too modest and
> this, I think, hurts their chances. American designers, of course,
> are the most crass, and I think this is a winning strategy.
I agree that E2 is faring worse than it deserves to.
> Next came lunch. Today I sat with a guy who works with a large
> organization that builds encryption hardware for the government!
> Sorry, not NSA; I never met any of these guys even though they
> were there - they appeared to be playing No Such Agency.
I thought the half-dozen or so NSA people were very open and
forthcoming. I think you were just unlucky not to run into one of
them.
> Later, I happened to speak to one of the top cryptographers of the
> world and I asked him one of my favourite questions: First assume
> two very good ciphers A and B, say two of the better AES
> candidates. If your life depended on it and you had to choose
> between A.A (doubling A's rounds), B.B (doubling B's rounds) or
> A.B (sequentially executing both ciphers), what would you do? The
> standard answer is that mixing ciphers is a bad idea because the
> resulting cipher could be weaker than each individual one, that
> the resulting cipher would be a completely new cipher which would
> require fresh analysis which is the only way to gain trust, etc.
> Well my companion's answer was "A.B", and he gave precisely the
> reasons I expected: a future attack that may work against A could
> very well stop at B's gate.
I agree with this, and I suspect that most cryptographers would.
While it cannot be proven that a cascade of A B is no more secure than
A, and could possibly be weaker than A, in realilty that just won't
happen. Your analysis is sound.
> Then came a long discussion about intellectual rights (IP) issues.
THe only really outstanding IP issue are the data-dependent rotations.
RSADSI has a patent on them in their RC6 patent. IBM claims that
they have a prior patent on the technique. IBM has NOT AGREED that
it would not sue AES if RC6 is chosen. This is a big problem, and
needs to be resolved.
> Smart cards. Several people expressed that the importance that was
> given to implementation issues of the AES on a low end smart card
> was not reasonable. The standard argument in favor of very tight
> implementations on smart cards was that there are cases where
> millions of smart cards are needed where even a small price
> difference has a large impact. Against that, somebody from the
> audience presented the following strong argument: cases where the
> AES is going to be used in a smart card are cases where you want
> to protect information that is valuable - otherwise you don't
> really need a 128 bit key and can use any of well known medium
> range ciphers. If you are protecting information that is valuable,
> then spending one dollar more for each card is a reasonable
> investment.
This only makes sense if the analysis is weak+cheap vs fast+expensive.
We don't have to make that tradeoff in this process. We can choose
an AES that is strong and cheap on smart cards, or one that is strong
and expensive on smart cards. Given that trade-off, it makes no sense
to tax smart-card applications even though those applications might be
willing to spend the money if forced.
> This gave me the idea that
> instead of trying to normalize security (a difficult proposition)
> and then comparing speeds, a better methodology could be to
> normalize speed (best assembly implementation on one or two
> reference platforms) and then compare security. After all,
> optimized speed on a given platform gives a good idea about an
> algorithm's workload. Also, speed could be normalized at such a
> high level that ALL competing ciphers would be pushed into
> insecurity which would then allow more or less reasonable
> quantitative comparisons to be made about their relative
> "structural" strenght. It is clearly too late to use this
> methodology in the first round but maybe it could be used in the
> second. I feel like sending NIST an official comment in this
> sense. I wonder what the reader thinks about this?
Someone told me you made this suggestion, and I think it is an
interesting idea.
The one thing you forgot to mention is the straw poll. At the end
of the day, Miles asked everyone to vote for the various candidates.
You could either vote "yes," as in "yes it should make it into the
second round, "no," or "maybe." This vote was unofficial and
anonymous.
At the rump session of FSE two days later, Miles presented the
results. (My apologies if this doesn't format well on your
particular netnews readers. I formatted it quickly for my machine.)
Out of the 170 or so participants, 104 filled the survey out. The
first column is the number of people who left the space blank.
Then, the number of people who said yes, this algorithm should
go into the second round. Then, the number of people who were
unsure. Then, the number of people who said no. The next
column contains the yes votes minus the no votes; this gives
the algorithm a relative rank in the ordering.
blank yes ??? no yes-no rank
Rijndael 7 77 19 1 +76 1
RC6 4 79 15 6 +73 2
Twofish 9 64 28 3 +61 3
Mars 5 58 35 6 +52 4
Serpent 6 52 39 7 +45 5
E2 11 27 53 13 +14 6
CAST-256 12 16 58 18 -2 7
SAFER+ 13 20 47 24 -4 8
DFC 12 22 43 27 -5 9
Crypton 14 16 43 31 -15 10
DEAL 10 1 22 71 -70 11
HPC 12 1 13 78 -77 12
Magenta 9 1 10 84 -83 13
Frog 11 1 6 86 -85 14 tie
Loki98 10 1 7 86 -85 14 tie
What is interesting is that the algorithms divide pretty neatly
into five categories:
Overwheming Yes: Rijndael, RC6, Twofish, Mars, Serpent
Mild Yes: E2
Middle-of-the-Road: CAST-256, SAFER+, DFC
Mild No: Crypton
Overwhelming No: DEAL, HPC, Magenta, Frog, Loki97
You should have stayed for FSE. The best analysis papers of
the AES algorithms were presented there, and there were a lot
more interesting papers.
And I did notice that your six picks were the same top six picks
from the survey.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Live from the Second AES Conference
Date: Sun, 28 Mar 1999 11:29:06 GMT
On 24 Mar 1999 16:14:17 +0000, Alan Braggins <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] writes:
>> it appears that the very fastest code is self-modifying - this may
>> look "unpure" to some but I think that it is a valid optimization
>> technique).
>[...]
>> improvement. As expected the answer is no, because one of the
>> easiest things to read from a card is the "signature" of the
>> instructions being executed.
>
>Any ideas whether self-modifying code would make reading instruction
>signatures easier or more difficult?
It doesn't matter. Sometimes techniques like this require a little
smarter measuing; sometimes they require a little smarter analysis.
None of them help.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Live from the Second AES Conference
Date: Sun, 28 Mar 1999 11:30:53 GMT
On Wed, 24 Mar 1999 09:15:06 -0800, Jim Gillogly <[EMAIL PROTECTED]> wrote:
>Thanks very much for the reports from the AES conference.
>Your views and notes are invaluable, as they were from the
>first conference. Well done!
>
>[EMAIL PROTECTED] wrote:
>> rounds. It is interesting to observe how cultural characteristics
>> have an impact in this international process. The designers of the
>> Asian candidates (E2 and Crypton) are really far too modest and
>> this, I think, hurts their chances. American designers, of course,
>> are the most crass, and I think this is a winning strategy.
>
>Ouch!
Unfortunately, I agree with him. I think both of ciphers have
gotten less support than they deserve. With Crypton there was also a
cultural barrier; I believe the designer misunderstood the rules, and
hence has been redesigning his cipher for the past year. E2 is one
of the ciphers I really like, and I will be disappointed if it does
not make it into the second round.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Is TEA Algorithm safe????
Date: Sun, 28 Mar 1999 12:08:45 GMT
On Sat, 13 Mar 1999 14:22:54 -0000, "melih" <[EMAIL PROTECTED]> wrote:
>Can anyone tell me if TEA algorithm is safe (I am told it is not safe
>however the reason as to why is what I am after).
>
>If not, does TEA Extensions solve the problems that made the TEA unsafe?
There have been no published attacks against TEA, but that does not
mean that it received extensive cryptanalysis. I would stay away from
it unless you application cannot use anything else. I don't think
anyone has even looked at XTEA; it never appeared in a conference or
journal.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (Bo Dömstedt)
Subject: Re: Symmetric vs. public/private
Reply-To: [EMAIL PROTECTED]
Date: Sun, 28 Mar 1999 12:57:11 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
>I'm happy you find me to be well informed. The question wasn't
>really rhetorical, since I was unsure how you would answer. As I
>recall, the one time we both wrote of the issues before was when
>you wrote the post at,
>
>http://x17.dejanews.com/[ST_rn=ap]/getdoc.xp?AN=413983975.1&search=thread&threaded=1&CONTEXT=922333383.512819295&HIT_CONTEXT=922333093.512753688&HIT_NUM=16&hitnum=14
>
>and I responded with the one at,
>
>http://x17.dejanews.com/[ST_rn=ap]/getdoc.xp?AN=415052768&search=thread&threaded=1&CONTEXT=922333383.512819295&HIT_CONTEXT=922333093.512753688&HIT_NUM=16&hitnum=15
>
>Despite using three news sources, I still miss posts. Did you
>ever write a follow-up?
I did not write any follow-up. I continued, in another thread,
by announcing that our Minister of Defence has written a
public statement where he declares that: those algorithms
being used on (example:) Internet for electronic commerce
is not approved by Swedish Defence to protect military
confidential information. (!!!)
...and got an answer
from [EMAIL PROTECTED] Don Johnson
>Please give the exact reference for a paper saying that RSA security was
>too low for defence communications. Thanks
I hope that he will accept the official government site.
Bryan Olson:
>One minor disagreement: it's not essential this happen "when
>transferring a public key", only by the time the certificate
>is actually used.
Accepted. But we are discussing the physical construction
of the certificates - especially the initial ones. Clearly, when you
have certificates you can transfer more keys/certificates if
you wish.
>Public key standards include a "not before"
>date in certificates, and call for use of certificate revocation
>lists. The system can therefore ensure that no certificate will
>in fact be used before a date that can be later than the time
>of key transfer. This is significant because we can audit that
>the public key was transferred intact.
Please explain that - this is getting interesting...
Bryan Olson:
>I discourage my customers from treating public
>keys as sensitive to disclosure.
...
>Authentication is a strictly a weaker condition than secrecy and
>authentication. I know of no technology that could deceive me
>into thinking I'm talking on the phone to a known co-worker when
>in fact my adversary controls the other end. Man in the middle
>attacks are vastly harder than mere passive eavesdropping.
Excuse me, but I find this phone conversation humouristic. But
I accept your point - if you are willing to bet your life on it.
This will, however, not solve the problem when the node is a
machine or a service provider. A computer cannot talk in the
phone...
Additional comment: Do you and your "co-worker" ever meet
in person? You could give him a fresh symmetrical key when
you meet?
>Conducting an independent audit that the true public key was
>transferred is trivial - send the auditor to both nodes.
Aha! What is an "auditor" ? Which nodes are "both nodes"?
How would (an computer/pl. describe preferred system configuration)
identify these "nodes"? Does "send" include unsafe asynchronous
networks like the Internet?
>I'm not sure how to audit that a secret key was never disclosed.
I will tell you about it someday...the military people know how to do
this. There is even an on-line military instruction manual out there,
somewhere?
>> (Quote from [3])
>> ..."the advantages of public key systems evaporate when one
>> actually integrates them into a larger system."
>
>That was 1979, a few years after public key cryptography was
>invented and before certificates were well understood.
Of course. Note that this report was selected for reprinting.
But the proof, of the report, is that the trust model of a
symmetrical key key transfer is identical to the trust model of
a public key key transfer. Could any particular construction of
a public key key transfer make this proof invalid?
Independent of method selected /public vs secret/, the security
requirements of my customers require a secure key transfer. If I have
to transfer the keys by courier, anyway, what use do I have of public
key cryptology? Incresed sales?
>I suppose I should point out that I now work for Certicom, a
>company that sells public-key technology. Uptronics merged into
>certicom in November of last year.
>
>--Bryan
..."the advantages of public key systems evaporate when one
actually integrates them into a larger system."
Bo Dömstedt
Cryptographer
Protego Information AB
http://www.protego.se
References:
[3]
Kline, C.S. and Popek, G.J.
"Public Key vs Conventional Key Encryption"
AFPS Conference Proceedings,
Vol 48, 1979 NCC Pages 831-837
(c) 1979 by AFIP Press.
Reprinted by permission in
"Advances in Computer System Security"
by Rein Turn (editor) Chapter 6.2, pages 291-297
(c) 1981 by Artech House, Inc.
ISBN 0-89006-096-7
------------------------------
Date: Sun, 28 Mar 1999 13:23:47 +0000
From: David Crick <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Live from the Second AES Conference
Bruce Schneier wrote:
>
> To me the big suprise was the complete lack of attention that Mars
> has been receiving. It just wasn't talked about.
One for the conspiracy theorists? (remember the NSA/IBM angle of DES)
David.
--
+---------------------------------------------------------------------+
| David Crick [EMAIL PROTECTED] http://members.tripod.com/~vidcad/ |
| Damon Hill WC '96 Tribute: http://www.geocities.com/MotorCity/4236/ |
| Brundle Quotes Page: http://members.tripod.com/~vidcad/martin_b.htm |
| PGP Public Key: (RSA) 0x22D5C7A9 00252D3E4FDECAB3 F9842264F64303EC |
+---------------------------------------------------------------------+
------------------------------
** 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
******************************
