Cryptography-Digest Digest #879, Volume #12 Mon, 9 Oct 00 13:13:01 EDT
Contents:
Re: Rijndael has a very good S-Box (John Savard)
Re: Choice of public exponent in RSA signatures (DJohn37050)
Re: Rijndael has a very good S-Box (John Savard)
Re: A new paper claiming P=NP (David C. Ullrich)
Re: education where ???please help ("Sam Simpson")
Re: Rijndael test vectors (Tim Tyler)
Re: Looking Closely at Rijndael, the new AES (Tim Tyler)
Re: It's Rijndael (Tim Tyler)
Re: Choice of public exponent in RSA signatures (Francois Grieu)
Re: A new paper claiming P=NP (Rajarshi Ray)
Re: A new paper claiming P=NP (David C. Ullrich)
Re: Looking Closely at Rijndael, the new AES (John Myre)
Re: Why trust root CAs ? (Anne & Lynn Wheeler)
Re: Rijndael test vectors (John Myre)
new SNAKE web page ([EMAIL PROTECTED])
Re: Why trust root CAs ? (Vernon Schryver)
Re: Requirements of AES (Rob Warnock)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Rijndael has a very good S-Box
Date: Mon, 09 Oct 2000 12:43:19 GMT
On Mon, 09 Oct 2000 12:28:27 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>The differential behavior of the Rijndael S-box is simply astounding.
>If you consider S(i) xor S(i xor diff), for all 256 values of i, this
>expression will often take on a value zero or two times instead of
>once, as is ideal...and may take on one value _four_ times.
The same is true of the inverse S-box.
109 * x xor 77 is the best GF(2^8) approximation of the inverse S-box,
and it is true 10 times out of 256. For the inverse S-box, however,
clumps of approximations with different xor constants do not appear.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Choice of public exponent in RSA signatures
Date: 09 Oct 2000 13:29:03 GMT
In ISO 9796-2 draft and IEEE P1363a, PSS using no RN is being thought of as
"similar" to FDH. They are not identical, but this simplifies things if no RN
is available.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Rijndael has a very good S-Box
Date: Mon, 09 Oct 2000 13:30:54 GMT
On Mon, 09 Oct 2000 12:28:27 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>For a=1 and a=23, there are multiple "approximations" that show up,
>and most commonly they are true around 8 times.
There was a bug in my program; I didn't use logarithms in G(2^8)
properly.
When corrected, no linear approximation is true more than 6 times for
the S-box - and the same, of course, applied, as it must, to the
inverse S-box as well. Neither was the "clumping" behavior observed,
although for some values of a, four values of b produced
approximations.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (David C. Ullrich)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Mon, 09 Oct 2000 13:43:30 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 09 Oct 2000 04:47:22 GMT, Rajarshi Ray <[EMAIL PROTECTED]>
wrote:
[...]
>Is it not possible to implement the presented algorithm and try it out
>on examples to see the growth rate, just as a preliminary check?
No. Suppose that a(n) is a sequence of integers and
a(n) = 2^(2^(^n)) for all n less than 10^(10^10). Does a(n)
have polynomial growth?
>--
>"The most incomprehensible thing about the universe is
> that it is comprehensible."
>
> - Albert Einstein
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: education where ???please help
Date: Mon, 9 Oct 2000 14:50:56 +0100
Royal Holloway (near Egham, that's near you, right?) offers
postgraduate courses (including M.Sc).
They've got / had a few "big names" there, including Prof F.Piper,
Sean Murphy, D.Gollmann and Matt Robshaw. Course details are
available at: http://isg.rhbnc.ac.uk/
--
Sam Simpson
http://www.scramdisk.clara.net/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
simon <[EMAIL PROTECTED]> wrote in message
news:8rqd3m$pl6$[EMAIL PROTECTED]...
> dear group i live in surrey uk and wish to learn about cryptography
> but i cannot find anywhere that offers any courses please could
anybody
> point me in a direction
> i would be very grateful
> SIMON P.........................
>
>
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Rijndael test vectors
Reply-To: [EMAIL PROTECTED]
Date: Mon, 9 Oct 2000 11:50:04 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: Let me tell you a little story.
: In the course of my previous employment, a programmer in a neighboring
: office was trying to write a program in BASIC to draw pie charts on
: his new plotter with his shiny new IBM Personal Computer AT.
: But the pie charts were not coming out right.
: It turned out that he was submitting arguments to the trigonometric
: functions that were in degrees, rather than in radian measure, as
: required.
: If they let "people like _that_" program computers [...]
;-)
Degrees are still in use in some places:
Java's "Graphics2D" class uses radians for it's rotate() method, and
degrees for it's drawArc() method. Go figure ;-)
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Looking Closely at Rijndael, the new AES
Reply-To: [EMAIL PROTECTED]
Date: Mon, 9 Oct 2000 12:01:31 GMT
Paulo S. L. M. Barreto <[EMAIL PROTECTED]> wrote:
:TT: A small secure cypher would be a sort of cryptographic magic
:TT: bullet. I don't think it exists - you need a certain degree of
:TT: complexity to poroduce enough confusion to properly resist
:TT: analysis.
:
: You don't think it exists? Then let me introduce "One-Time Pad".
: Can you think of anything smaller or faster? Yet if you don't accept
: that as secure, then just forget *anything* else.
My comments were intended to refer to cyphers with reasonable size keys.
However, it so happens that they can also be applied to the OTP.
In practice, a simple OTP is neither small (if you take the key
generation and distribution mechanism into account) nor terribly secure
(because of problems with authentication and secure key distribution).
There's absolutely no way it qualifies as a "cryptographic magic bullet".
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: It's Rijndael
Reply-To: [EMAIL PROTECTED]
Date: Mon, 9 Oct 2000 12:06:17 GMT
Paulo S. L. M. Barreto <[EMAIL PROTECTED]> wrote:
[does the Rijndael key to encript ****RIJNDAEL*** to *AES*WINNER*AES* exist?]
: Yes, it does exist, because 128-bit keys define a permutation over the
: AES codebook.
As Joseph Ashwood mentioned, this isn't correct.
: I hope nobody is foolish enough to start a contest for it. Unlike the
: contests under way to break 64-bit keys, the case for 128-bit keys is futile,
: and will remain so until quantum computers are widespread.
...assuming Rijndael is a properly secure 128 bit block cypher.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: Choice of public exponent in RSA signatures
Date: Mon, 09 Oct 2000 16:15:24 +0200
[EMAIL PROTECTED] (DJohn37050) wrote:
> I think Gus Simmons discovered that any sig system has a covert channel
> that cannot be eliminated, when he was designing an a-bomb/earthquake
> sensor message machine and he tried to prove it was NOT sending any data
> it was not supposed to send. He found to his surprise he could not prove
> it and proved the contrary instead.
I can not find a covert channel in ISO/IEC 9796-2, for example. It appears
the standard is crafted such that any message has only one valid signature.
Can someone point the assumptions in the proof ?
Francois Grieu
------------------------------
From: Rajarshi Ray <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Mon, 09 Oct 2000 14:36:57 GMT
"David C. Ullrich" wrote:
>
> On Mon, 09 Oct 2000 04:47:22 GMT, Rajarshi Ray <[EMAIL PROTECTED]>
> wrote:
>
> [...]
> >Is it not possible to implement the presented algorithm and try it out
> >on examples to see the growth rate, just as a preliminary check?
>
> No. Suppose that a(n) is a sequence of integers and
> a(n) = 2^(2^(^n)) for all n less than 10^(10^10). Does a(n)
> have polynomial growth?
Well, I suppose it could be polynomially growing after 10^(10^10). Do
you mean to say that empirical testing wouldn't reveal its polynomial
behavior for n->oo, which is what we really mean by polynomial growth?
--
"The most incomprehensible thing about the universe is
that it is comprehensible."
- Albert Einstein
------------------------------
From: David C. Ullrich <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Mon, 09 Oct 2000 15:26:59 GMT
In article <[EMAIL PROTECTED]>,
Rajarshi Ray <[EMAIL PROTECTED]> wrote:
> "David C. Ullrich" wrote:
> >
> > On Mon, 09 Oct 2000 04:47:22 GMT, Rajarshi Ray
<[EMAIL PROTECTED]>
> > wrote:
> >
> > [...]
> > >Is it not possible to implement the presented algorithm and try it
out
> > >on examples to see the growth rate, just as a preliminary check?
> >
> > No. Suppose that a(n) is a sequence of integers and
> > a(n) = 2^(2^(^n)) for all n less than 10^(10^10). Does a(n)
> > have polynomial growth?
>
> Well, I suppose it could be polynomially growing after 10^(10^10). Do
> you mean to say that empirical testing wouldn't reveal its polynomial
> behavior for n->oo, which is what we really mean by polynomial growth?
Yes. (And it's not just a theoretical thing: It happens all the
time that an algorithm that takes time O(n^2) is actually much
faster than one that takes time O(n).)
> "The most incomprehensible thing about the universe is
> that it is comprehensible."
>
> - Albert Einstein
>
--
Oh, dejanews lets you add a sig - that's useful...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Looking Closely at Rijndael, the new AES
Date: Mon, 09 Oct 2000 09:48:00 -0600
Brian Gladman wrote:
<snip>
> Interestingly the AES "Modes of Operation" workshop will meet shortly and
> there are proposals for new modes designed to provide 'almost free'
> authentication as a byproduct of secrecy.
FYI sci.crypt, see
http://csrc.nist.gov/encryption/aes/modes/jutla-auth.pdf
which is referenced from
http://csrc.nist.gov/encryption/aes/modes/#Materials
The very last page has a nice diagram to get started.
For those who want a thumbnail, the idea is roughly to
whiten the text with material that is cheaply derived
from a second key (cheap as in not requiring a whole
encryption per block).
They give two modes; one is basically CBC with post-whitening,
and the other is ECB with both pre- and post-whitening.
Authentication comes from appending an XOR of all the plaintext
blocks, and encrypting it along with the rest of the message.
They also give two methods for generating the whitening
material. One is to generate 2^n whitening blocks from
n encryptions (from all combinations; actually I guess
they leave out the null subset). The other method is even
cheaper: they do two encryptions to get A and B, then the
whitening blocks are (A + i*B) modulo (2^128 - 159).
For corrections and amplifications, read the paper.
> However it is not clear to me that they do what is claimed since I am always
> somewhat suspicious of getting something for (almost) nothing.
Yes. Not that I understand it, but they do offer a "proof
of security" at http://eprint.iacr.org/2000/039.ps from
which the above paper seems to be derived. I suspect NIST
will want more cryptanalysis, too (witness their comments
on AES block sizes). Maybe they (and we) will get some at
the workshop.
> Perhaps
> worse, I think IBM has patented them and this might cause problems if they
> were adopted.
Yuck.
JM
------------------------------
Subject: Re: Why trust root CAs ?
Reply-To: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
From: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
Date: Mon, 09 Oct 2000 15:57:33 GMT
[EMAIL PROTECTED] (Vernon Schryver) writes:
> There's promise there, but also problems. I've not been keeping up, but
> I understand that one problem is that they've not figured out how to sign
> all of the RR's in .com before it's time to sign them all again. It takes
> time to sign 30,000,000 records with a public key. Another problem is
> that adding signatures make packets on the wire a lot bigger.
... also there are a number of different places/transaction where
public key & digital signatures might benefit domain name infrastructure.
at its simplest the example was registering public keys at the same
time as the domain name was registered. this would benefit the SSL
domain name certificates ... since domain name infrastructure could
require that changes to domain name info has to be signed ... making
domain name hijacking much harder (i.e. i can't hijack a domain name and
then get a valid ssl certificate for that domain).
on the other hand, with such keys registered as part of the domain
name entries ... clients could optionally request the key be returned
in addtion to host->ip-number. using that public key as part of server
authentication and SSL session setup would reduce the bits on the wire
compared to the existing client/server SSL handshaking.
... i.e. the solution to improving integrity for domain name SSL
certificates is also a solution for making domain name SSL
certificates obsolete, redundant and superfulous.
--
Anne & Lynn Wheeler | [EMAIL PROTECTED]
http://www.garlic.com/~lynn/
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Rijndael test vectors
Date: Mon, 09 Oct 2000 10:03:42 -0600
John Savard wrote:
<snip>
> Oh, and BTW: the nature of the Rijndael spec - its failure to
> explicitly exhibit such things as the S-box, the inverse Mix Column
> matrix - while, I suppose, could be justified on the basis of not
> allowing a typo to influence the cipher, could also have somewhat
> discouraged people from concentrating on it for cryptanalysis during
> the selection process.
<snip>
While I'd agree that the NIST spec should probably have
explicit help for the poor implementer, I don't think
the nature of the submission discouraged anyone whose
cryptanalysis would be worth anything.
JM
------------------------------
From: [EMAIL PROTECTED]
Subject: new SNAKE web page
Date: Mon, 09 Oct 2000 16:15:01 GMT
The old SNAKE web page died of natural causes a while back,
and Ive just found some space for it...
SNAKE:
http://www.kripto.org/snake
It hasnt changed much in recent times, but I guess thats a
good thing :-)
You might also be interested in Blocks, a distributed anonymous
file distribution application/system which shares some SNAKE
code...
BLOCKS:
http://www.kripto.org/blocks
As always, all comments are welcome. Blocks has a sourceforge
mailing list set up which is linked from the Blocks page.
ttfn
PG.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: Why trust root CAs ?
Date: 9 Oct 2000 10:27:37 -0600
In article <[EMAIL PROTECTED]>,
Anne & Lynn Wheeler <[EMAIL PROTECTED]> wrote:
>
>[EMAIL PROTECTED] (Vernon Schryver) writes:
>> There's promise there, but also problems. I've not been keeping up, but
>> I understand that one problem is that they've not figured out how to sign
>> all of the RR's in .com before it's time to sign them all again. It takes
>> time to sign 30,000,000 records with a public key. Another problem is
>> that adding signatures make packets on the wire a lot bigger.
>
>DNS does allow for different types of requests with different types of
>information returned.
Reasonable clients should now not be asking for anything they don't need,
so I don't see how that helps.
Requiring clients to make more than one pass at a given server for a single
set of answers opens cans of worms. For example, what if the TTL expires
on the first part of the answers before the last arrives? Given current delays
from some DNS servers (including network delays) and some efforts for
"dynamic" DNS (and so tiny TTL's), I suspect that's not an entirely
academic concern.
> for part of the issue, clients can selectively
>request keys & signatures (like they do today in SSL).
The CPU costs even to the clients of DNS signatures is something to worry
about. On the other hand, if you have an application (as I do) that
occasionally needs to gethostbyname() on several dozen to a few 100 name,
you soon learn that delays for CPU cycles are the least of your worries.
> increase of
>bits on the wire has got to be significantly less than the current SSL
>setup.
Within the last week or two, someone in one of the IETF lists said
something I wish I'd saved. I believe he said when you add signatures to
the DNS/UDP/IP packet containing the list of roots, you not only have
trouble with IPv4 UDP/IP packet sizes but also IPv6. It may have been on
the IRTF's end-to-end list.
Isn't there something about the not IP-fragmenting some DNS/UDP answers?
Note that in my view, all of those are nits. If you need to authenticate
an IP address--DNS name association (and sometimes you must), then the
place to do it is in DNS, not in some other protocol that involves third,
fourth, and more parties. I think most (but not quite all) of what
Verisign/Thawte is peddling snake oil. I consider the business connection
between Network Solutions and Verisign proof of their common nature.
--
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Subject: Re: Requirements of AES
Date: 9 Oct 2000 10:00:56 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
+---------------
| Jim Gillogly <[EMAIL PROTECTED]> wrote:
| > Fifth, Rijndael and Serpent use operations that are easier to
| > defend against power and timing attacks. Twofish's addition op
| > is harder to defend against those attacks, and RC6 and MARS are
| > difficult to defend because of mults, variable rots, and addition.
|
| That's bs to. Twofish can be done with xors, ors and look ups.
+---------------
What? You're going to use table lookups to do 32-bit addition? NOT.
[The Twofish PHT needs at least two 32-bit adds.]
-Rob
=====
Rob Warnock, 31-2-510 [EMAIL PROTECTED]
Network Engineering http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. PP-ASEL-IA
Mountain View, CA 94043
------------------------------
** 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
******************************
