Cryptography-Digest Digest #379, Volume #12 Tue, 8 Aug 00 09:13:00 EDT
Contents:
Re: Questions about Rijndael (Mok-Kong Shen)
Re: Simple Cypher? (Simon Johnson)
Re: Last secret conversation (maybe more if time permits) (Mok-Kong Shen)
Re: Physical RNG (Guy Macon)
Re: Questions about Rijndael (Mark Wooding)
Re: Questions about Rijndael (Mark Wooding)
Re: Discret Logarithm (Simon Johnson)
Re: More Secret Conversations (Simon Johnson)
Re: chap authentication scheme? (Mark Wooding)
Re: Discret Logarithm (Mark Wooding)
Re: RC5 / 4 (Simon Johnson)
Re: chap authentication scheme? ("Tomas Rosa")
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Questions about Rijndael
Date: Tue, 08 Aug 2000 13:33:57 +0200
All the points in my previous post are summerizable into two
(abstract) points that seem to apply to other finalists of
AES more or less as well:
1. There is no or little 'variability' (e.g. one single
S-box in Rijndael) that could potentially further enhance
the strength of the cipher.
2. The documentation does not give the rationales at
sufficiently detailed level. Thus the reader is not very
much better off than with the DES design (which has
no official release of design rationales at all).
That Serpent has only eight S-boxes and Twofish has only one
MDS matrix are facts inline with (1).
As to (2), Twofish has a comparatively better explanation
of rationales than Rijndael and Serpent and. Its document
seems to be a good foundation for later being expanded into
one with more details to fulfill additional desires from the
inquiring readers. I believe that for a winner of AES (that
is to be 'universally' used) the final document should be
such that, with it, the derivation of ALL constants involved
in the algorithm should be able to be reproduced by the
reader, just like a detailed report about a physical or
chemical experiment. This is all the more important in view
of the ancient veil of secrecy which the science of crypto
has not yet succeeded to wholly dispose off (thanks to the
'efforts' of certain authorities). There is one sentence in
the Twofish document, though, that continues to confuse me.
It says that it uses key-dependent S-boxes but states also
that 'However, there is really no such thing as a key-
dependent S-box'. Now, whether its S-boxes are key-dependent
or not is obviously a binary, not a fuzzy, issue. If there
ever exist two different keys that lead to different S-boxes,
then there is key-dependency, otherwise there is no key-
dependency, isn't it? (I should appreciate it, if someone
would like to enlighten me in this point.)
M. K. Shen
===========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
Subject: Re: Simple Cypher?
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Tue, 08 Aug 2000 04:20:32 -0700
Yup, build your own. That way, you know what you're programs
don't have backdoors etc.
Note, using Public/Private key cryptography to encode whole
messages is a bad idea:
1. Its very slow.
2. If a file contains a standard-header then this will encrypt
to an identical cipher-text block. Allowing easy reply material
for an attacker.
A better method to use is:
1. Encrypt the body of the document with a good symetric
algorithm, in CBC mode, with a unique IV and a random passkey.
2. The sender of the message encrypts the random passkey with
your public key and appends it to the message. He/she then sends
the message.
3. You, with your private key, recover the passkey and decrypt
the message.
This prevents reply, and is miles faster than the above mechnism.
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Last secret conversation (maybe more if time permits)
Date: Tue, 08 Aug 2000 13:39:39 +0200
According to the title that should be the 'Last'!!! I hope
that should also be the last 'open' conversation of this
genre. This is sci.crypt group, not one about phylosophy or
religion!!!
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Physical RNG
Date: 08 Aug 2000 11:49:40 GMT
Ed wrote:
>
>Hello,
>
>I'm searching for a physical random number generator.
>But I've have important constraint :
> - it should be plugged in a PCI bus
> - it should be useable under Solaris system ( or Unix system)
>
>If you know a physical RNG that don't match these criteria,
>it could help me.
I just went to www.yahoo.com and searched on "pci" "random number".
The first three hits were PCI RNGs:
http://www.hifn.com/products/6500.html
http://hlhp1.physik.uni-ulm.de/~freitag/spinoffs.html
http://slashdot.org/articles/99/12/06/2258246.shtml
Total time: about 2 minutes.
>Please send any information to : [EMAIL PROTECTED]
Not doing a simple search I can attribute to ignorance, but posting
a question in a newsgroup and expecting an email reply implies that
you are too lazy to read the newsgroup for answers.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Questions about Rijndael
Date: 8 Aug 2000 11:57:07 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> In another thread David Wagner has posed a question about Rijndael's
> S-box. I like to elaborate that a little bit and add a few questions
> of my own for discussion.
A lot of the less-well-explained parts of Rijndael are elucidated in the
authors' earlier paper with Lars Knudsen on `The Block Cipher SQUARE'.
It also misses several details I've only been able to find by looking at
implementations, such as the polynomial used in the GF(2^8)
representation and the actual affine transform used in the S-box
(S_\gamma, in Square).
Executive summary: they'd be massive performance hits for some target
platforms which wouldn't be worth the extra cryptographic security.
> 1. In ByteSub only one 8-bit S-box is used, which is defined
> by an inversion in GF(2^8) and an affine transformation.
>
> a. How has the affine transformation been chosen? Wouldn't
> a random invertible boolean matrix and a random boolean
> vector do as well?
Quite possibly. I've not seen any particular analysis of this part of
Rijndael. The idea is that the affine transformation should be
sufficiently complicated in GF(2^8) to thwart interpolation attacks.
There is a certain amount of structure in the affine transform used in
Square, but less than Rijndael's ByteSub box. The simplification
reduces the memory requirement in software implementations slightly, and
(probably) makes hardware design a bit easier too. The final XOR mask
doesn't seem to do very much good: it's linearly and differentially
inert and has a simple expression in GF(2^8). Its only purpose, I
believe, is to remove the fixed point 0 |-> 0 in the S-box.
> b. Wouldn't it be advantageous to have more than one affine
> transformations, thus rendering more S-boxes available,
> which may even be used differently in different rounds?
Maybe, from a cryptographic point of view; definitely not for
implementation efficiency. Fast Rijndael implementations work by
combining the ByteSub and MixColumn operations (Square \gamma\ and
\theta) in a single 8 x 32 bit table. Putting in extra S-boxes would
mean multiple tables. It also imposes a much larger burden on low-end
8-bit software implementations -- 256-byte tables aren't actually
cheap. It would be possible to compute the affine transformations by
hand, but that would be an unwelcome performance penalty.
If you don't care about low-end software, you might be able to get away
with having four S-boxes and use one of them in each of the four rows of
the state. You can then combine the column of four S-boxes with the
\theta-operation in four tables, which would use the same amount of
memory as optimized Square and Rijndael implementations use anyway. I
believe (and maybe David Wagner or someone else clever will correct me
if this is wrong) that this will offer much improved resistance to the
Square attack[1].
Using different arrangements in different rounds makes non-pipelined
hardware painful and expensive. It's a bad idea.
> 2. In ShiftRow shifting of bytes are specified for the four
> rows.
>
> a. Wouldn't it be better to shift different amounts in
> different rounds?
No, probably not. It doesn't seem to make a great deal of difference,
actually. The only reason the 256-bit block case is different is to
encourage diffusion to far parts of the block more rapidly.
> b. Why does one use shifting of bytes and not shifting
> of (arbitrary number of) bits?
Have you tried implementing Rijndael?
It's vitally important in Rijndael's design that the data in a column is
held together, and relationships between columns are weak. This means
you can keep a column in a 32-bit machine word, and everything goes very
rapidly. You do the ShiftRow operation by picking bytes from the state
in a funny order and pushing them through the combined ByteSub/MixColumn
table. If the ShiftRow operation does shifting by arbitrary numbers of
bits there's a *horrific* amount of bit twiddling needed, and your
performance will fall through the floor.
> c. (Non-technical): Wouldn't shifting of bytes, which is
> a circular shift by 8 or multiple of 8 bits, also be
> in conflict with the Hitachi's patent claims about
> circular shift, just as the other AES candidates do?
No idea. Maybe a passing patent lawyer will comment. Ed? ;-)
> 3. In MixColumn the columns are multipled by a 3rd degree
> polynomial with coeffcients in GF(2^8) and reduced
> modulo a 4th degree polynomial.
>
> a. How has the 3rd degree polynomial been chosen (besides
> the invertibility)?
Read the Square paper. Basically, it's been chosen for simplicity of
computation on low-end 8-bit processors.
> b. Wouldn't it be advantageous to have more than one
> such polynomials available for the various columns,
> which may even be used differently in different rounds?
No. The precomputed tables for fast software implementations will
become much larger, which isn't good -- it might not all fit in cache on
cheaper 32-bit processors for example. It'll also make low-end hardware
more expensive.
[1] This has given me ideas. By generating four key-dependent S-boxes,
and using the basic structure of Rijndael, we can create...
Squarefish!
Let's say that our worst differential is 24/256 ~= 2^{-3.41}. We
get 25 active S-boxes in four rounds, so the best differential
characteristic through four rounds has probability less than
2^{-85.3}. Another four rounds pushes this well over the 2^{-128}
barrier. Eight rounds of this should be completely adequate for
security, and will run faster than either Rijndael or Twofish.
Now all I need is a key schedule. ;-)
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Questions about Rijndael
Date: 8 Aug 2000 12:16:06 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> All the points in my previous post are summerizable into two
> (abstract) points that seem to apply to other finalists of
> AES more or less as well:
>
> 1. There is no or little 'variability' (e.g. one single
> S-box in Rijndael) that could potentially further enhance
> the strength of the cipher.
Too much `variability', as you call it, increases memory and code
footprints of software implementations and means you need more chunks of
hardware in a minimal implementation. Remember that AES is meant to be
fast and cheap as well as secure.
> 2. The documentation does not give the rationales at
> sufficiently detailed level. Thus the reader is not very
> much better off than with the DES design (which has
> no official release of design rationales at all).
>
> That Serpent has only eight S-boxes and Twofish has only one
> MDS matrix are facts inline with (1).
Ewww. Adding more MDS matrices to Twofish would be awful! Each matrix
needs four 8 x 32 bit tables *per key* in an optimized software
implementation. Each matrix needs separate code or gates to handle in
low-end software and hardware.
> As to (2), Twofish has a comparatively better explanation
> of rationales than Rijndael and Serpent and.
The Twofish paper was undoubtedly the best presented. The wealth of
analysis gave me an extremely good feeling about how carefully the
cipher had been designed. (I learned differential cryptanalysis from
that paper, by the way. ;-) )
It helps if you understand the Square design before you read the
Rijndael paper.
Oh, you should probably *implement* ciphers before you start criticising
their design. Actually writing the code gives a much sharper and deeper
understanding of the cipher's structure and the way in which the various
components fit together.
On the other hand, Rijndael actually has a lot less to explain. The
reasons for almost all of the decisions are given in the submission
document, the Square paper, or are obvious when you actually understand
the design.
> There is one sentence in the Twofish document, though, that continues
> to confuse me. It says that it uses key-dependent S-boxes but states
> also that 'However, there is really no such thing as a key-dependent
> S-box'. Now, whether its S-boxes are key-dependent or not is obviously
> a binary, not a fuzzy, issue. If there ever exist two different keys
> that lead to different S-boxes, then there is key-dependency,
> otherwise there is no key- dependency, isn't it? (I should appreciate
> it, if someone would like to enlighten me in this point.)
Ahh, but what's an S-box? ;-)
Consider Twofish. Are the S-boxes really the little 4-bit t-boxes? Or
the fixed 8-bit q-boxes? Or the key-dependent S-tables constructed by
XORing key bytes between q-box substitutions? Or even the S-tables
combined with the following MDS multiply?
Consider Blowfish. Is there really an S-box there at all? What's
usually implemented as a table lookup is really a (really horrible)
complex function of the key and the constant \pi.
Wherever you see a `key-dependent S-box', look more deeply. It's
constructed somehow. You can think of it as some nasty function of some
constant stuff and user-supplied key bits. The `trick' in building key-
dependent S-boxes is to make the construction function sufficiently
horrible that it's best to analyse it as a random secret function.
Blowfish succeeds here, more or less. Twofish is a boundary case. The
S-box construction is extremely simple, and doesn't preserve
differential and linear properties of the underlying q-boxes very well.
-- [mdw]
------------------------------
Subject: Re: Discret Logarithm
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Tue, 08 Aug 2000 05:18:57 -0700
Just a related question:
Is there a simple, but probably woefully slow, algorithm to find
the discret logrithm in a finite field?
A URL would be prefered over a book reference.
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: More Secret Conversations
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Tue, 08 Aug 2000 05:41:07 -0700
deadman19 <[EMAIL PROTECTED]> wrote:
>bravo! nice dialogue.
>
>however, no matter how considered your writing, you have only
>succeeded in revealing that you are the disciple.
>
>why not wait until someone asks you to teach them to become a
>master?
>
>p.s. By The Way, whose disciple are you, eh?
>
I follow the path of the lightened ones - I am a disciple of the
prinicples of Shannon. ;)
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: chap authentication scheme?
Date: 8 Aug 2000 12:44:55 GMT
Bill Unruh <[EMAIL PROTECTED]> wrote:
>
> One of the great advantages of the unix password authentication is tht
> the attacker cannot figure out the password from the information stored
> on the server in any way but brute force. It has the disadvantage that
> it requires the cleartext delivery of the password.
> The chap ppp authentication goes the other way-- by delivering a hashed
> response to a challenge, the attacker cannot figure out the password
> from the publically exchanged data. However the passwords need to be
> stored in the clear on the server.
>
> Would the following scheme work to overcome both? (I know srp already
> does, but it requires multiple responses which I do not believe fit
> within the chap standards.)
>
> The authenticator has a modulus N (prime?) and a generator g. The stuff
> stored in the database is
> username, salt s, g, N, g^ps modN
> The challenge to theuser is
> s,N, g^x modN where x is a random number
> Response is
> (g^x modN)^ps modN
> which the authenticator can compare with (g^sp modN)^x modN
>
> Does knowing g^x modN and g^xps modN for multiple (unknown) x help to
> find ps?
No.
Change the notation. Let G be some cyclic group with prime order q in
which the discrete log problem is hard, and let g be a generator of the
group. For each user, choose g' = g^s for some random salt s. The
user's password, 0 < p < q, is his public key. Store g'^p as the user's
public key.
Breaking this system is as hard as computing discrete logs, *if* p is
chosen uniformly at random.
Suppose that an adversary A can find p using t modexps and n queries to
an oracle which yields a pair (g^x, g^{spx}) for a random constant s.
Here's how to construct an adversary A' which computes discrete logs to
the base g.
* Let y = g^p, where p is the discrete log we want to find. Choose a
random s.
* We supply A with an `oracle' which responds to each query by making
up a random x and returning the pair (g^x, y^{sx}).
Running A then yields our desired value of p in t + 2 * n modexps.
(This is the first time I've done this sort of thing. Feel free to
point out mistakes.)
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Discret Logarithm
Date: 8 Aug 2000 12:52:20 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
> Just a related question:
>
> Is there a simple, but probably woefully slow, algorithm to find
> the discret logrithm in a finite field?
Exhaustive search is simple but woefully slow. Pollard's rho finds
collisions which yield discrete logs, but takes time proportional to the
square root of the group order. Index calculus methods should work on
all finite fields.
> A URL would be prefered over a book reference.
See http://www.cacr.math.uwaterloo.ca/hac/, chapter 3 for descriptions
of all of the above. Pollard's rho is implemented in Catacomb
(available from http://www.excessus.demon.co.uk/misc-hacks/#catacomb),
`rho.c'.
-- [mdw]
------------------------------
Subject: Re: RC5 / 4
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Tue, 08 Aug 2000 05:53:40 -0700
Tom Anderson <[EMAIL PROTECTED]> wrote:
>On Fri, 4 Aug 2000, David Hopwood wrote:
>
>> John Myre wrote:
>>
>> > tomstd wrote:
>> >
>> > > Note: RC5 is the holy grail of RSA so unless you want to
start a
>> > > war with them I would avoid it.
>> >
>> > Hm. This analogy isn't exactly right;
>>
>> "Crown jewels." (Not that this is really appropriate for RC5.)
>
>more appropriate than you might think; in some parts of the
world it's
>slang for, er, well, look it up yourselves ...
>
>http://www.australiatravelsearch.com.au/trc/slang.html
>
>tom
Well, anything that patented i give the classifaction of:
PANTS - Regardless of cryptographic security.
Then i implement it anyway, just to spite them ;-)
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "Tomas Rosa" <[EMAIL PROTECTED]>
Subject: Re: chap authentication scheme?
Date: Tue, 8 Aug 2000 14:48:32 +0200
> The authenticator has a modulus N (prime?) and a generator g. The stuff
> stored in the database is
> username, salt s, g, N, g^ps modN
Note about the salt: I suppose that you want to use the salt to hide the
property that two users with the same p will have the same entry in the
account database. But when N is prime (more precisely, when the order of
multiplicative group Z/N is known) then it is easy to compute r, such that
r*s mod phi(n) = 1 and then to compute g^p mod N = (g^ps)^r mod N.
Now is the attacker able to determine accounts wiht the same authentication
secret p.
Tom
------------------------------
** 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
******************************
