Cryptography-Digest Digest #368, Volume #14 Wed, 16 May 01 17:13:01 EDT
Contents:
Re: PRNG question from newbie ("Paul Pires")
Re: PRNG question from newbie (John Myre)
Re: PRNG question from newbie ("Henrick Hellström")
Re: Not a realistic thing to do......Why? (John Savard)
Re: PRNG question from newbie ("Paul Pires")
Re: PRNG question from newbie ("Paul Pires")
What is a group? [Re: OAP-L3: "The absurd weakness."] (Alan Mackenzie)
Re: MISTY -- no simple truncated difs ("Tom St Denis")
Re: Karnaugh Maps ("Tom St Denis")
Re: Karnaugh Maps ("Tom St Denis")
Re: TC15 analysis ("Tom St Denis")
----------------------------------------------------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: PRNG question from newbie
Date: Wed, 16 May 2001 11:48:57 -0700
John Myre <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> David Wagner wrote:
> <snip>
> > If you mean something that stretches a short, truly random,
> > uniformly distributed seed to a long pseudorandom keystream,
> <snip>
> > If you mean something that collects entropy from various
> > sources of questionable quality and unknown statistical
> > distribution and attempts to distill this down to a uniformly
> > distributed value,
> <snip>
>
> If I understand Daemen's contention correctly, it is that the
> cryptographic community should study/attempt a single primitive,
> instead of breaking it down as above. That is, instead of
> helping the PRNG by promising that it's input is a nice
> compact key, or helping the hash function by only requiring
> a fixed (small) output, we should ask for a function that
> takes any amount of input and gives back any amount of output,
> preserving the entropy of the input, and making the output
> look pseudo-random and uniformly distributed. I think.
Isn't this just a stream cipher with a good key setup routine?
If not, what's the difference?
Paul
>
> Have you heard of this, or have opinions on the idea? How
> is this related to the concept of a PRF?
>
> (And if you know I got this wrong...
> well, ok, tell me.)
>
> JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: PRNG question from newbie
Date: Wed, 16 May 2001 13:22:32 -0600
Paul Pires wrote:
<snip>
> Isn't this just a stream cipher with a good key setup routine?
> If not, what's the difference?
<snip>
I think that's the deep question to address. How are the
requirements for the output of a PRNG (stream cipher) and
a hash function different? Can an *efficient* algorithm
do either job, securely? Or is it inevitable that we need
two algorithms (even if related), one for each job?
There are other related concepts (e.g., pseudo-random
functions). Can the whole thing be unified? (Don't
ask me!)
JM
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: PRNG question from newbie
Date: Wed, 16 May 2001 22:06:11 +0200
"Paul Pires" <[EMAIL PROTECTED]> skrev i meddelandet
news:hZzM6.32165$[EMAIL PROTECTED]...
>
> John Myre <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> > David Wagner wrote:
> > <snip>
> > > If you mean something that stretches a short, truly random,
> > > uniformly distributed seed to a long pseudorandom keystream,
> > <snip>
> > > If you mean something that collects entropy from various
> > > sources of questionable quality and unknown statistical
> > > distribution and attempts to distill this down to a uniformly
> > > distributed value,
> > <snip>
> >
> > If I understand Daemen's contention correctly, it is that the
> > cryptographic community should study/attempt a single primitive,
> > instead of breaking it down as above. That is, instead of
> > helping the PRNG by promising that it's input is a nice
> > compact key, or helping the hash function by only requiring
> > a fixed (small) output, we should ask for a function that
> > takes any amount of input and gives back any amount of output,
> > preserving the entropy of the input, and making the output
> > look pseudo-random and uniformly distributed. I think.
>
> Isn't this just a stream cipher with a good key setup routine?
> If not, what's the difference?
Most ciphers have a maximum key size - unless the user key is hashed first,
of course, but then you really don't have a single primitive.
An error propagating cipher would do if the error propagation is secure - by
definition, because secure error propagation ought to be defined as if the
function F_x(y) is secure for any length of x and y, where x is the first
part of the message and y is the last part of the message. If this is so,
then the primitive could be constructed as G^n(x) = F_x(0^n), where x is the
input and n is the desired length of the output. (0^n should be interpreted
as a string of n zeroes.)
That's what e.g. Steak does.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Not a realistic thing to do......Why?
Date: Wed, 16 May 2001 20:19:17 GMT
On Wed, 16 May 2001 13:05:39 -0500, James Felling
<[EMAIL PROTECTED]> wrote, in part:
>Might make a good hash though.
>From the description, however, it's a way to split a document into
three pieces - so it probably isn't deterministic. (i.e., two pieces
are random, the third piece is the other two pieces XOR the plaintext,
then encrypted or something like that)
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: PRNG question from newbie
Date: Wed, 16 May 2001 13:15:53 -0700
John Myre <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Paul Pires wrote:
> <snip>
> > Isn't this just a stream cipher with a good key setup routine?
> > If not, what's the difference?
> <snip>
>
> I think that's the deep question to address. How are the
> requirements for the output of a PRNG (stream cipher) and
> a hash function different? Can an *efficient* algorithm
> do either job, securely? Or is it inevitable that we need
> two algorithms (even if related), one for each job?
>
> There are other related concepts (e.g., pseudo-random
> functions). Can the whole thing be unified? (Don't
> ask me!)
To me, It seems that there might be a third thing, a
superset that encompasses both needs and functions.
I'm just trying to get my arms around what this
mytical beast might look like. I have been trying for
quite awhile :-) It's a multi-dimensional problem.
once you get what looks like the functional answer
then a bunch of other competing concerns kick in.
Bad keys, collision avoidance, various proofs desired
for confidence, minimum cycle length, yada. yada. yada.
Couldn't you look at a stream cipher as just a hash function
with a variable hash size? Going the other way it seems
that a hash function would be a very specialized case of
a stream cipher.
Seems like making a stream cipher out of a hash function
would be much less constrained than making a hash from
a stream cipher.
A newbies simple view of life, the Universe and
everything.
Paul
>
> JM
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: PRNG question from newbie
Date: Wed, 16 May 2001 13:18:00 -0700
Henrick Hellström <[EMAIL PROTECTED]> wrote in message
news:9dumis$s30$[EMAIL PROTECTED]...
> "Paul Pires" <[EMAIL PROTECTED]> skrev i meddelandet
> news:hZzM6.32165$[EMAIL PROTECTED]...
> >
> > John Myre <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > > David Wagner wrote:
> > > <snip>
> > > > If you mean something that stretches a short, truly random,
> > > > uniformly distributed seed to a long pseudorandom keystream,
> > > <snip>
> > > > If you mean something that collects entropy from various
> > > > sources of questionable quality and unknown statistical
> > > > distribution and attempts to distill this down to a uniformly
> > > > distributed value,
> > > <snip>
> > >
> > > If I understand Daemen's contention correctly, it is that the
> > > cryptographic community should study/attempt a single primitive,
> > > instead of breaking it down as above. That is, instead of
> > > helping the PRNG by promising that it's input is a nice
> > > compact key, or helping the hash function by only requiring
> > > a fixed (small) output, we should ask for a function that
> > > takes any amount of input and gives back any amount of output,
> > > preserving the entropy of the input, and making the output
> > > look pseudo-random and uniformly distributed. I think.
> >
> > Isn't this just a stream cipher with a good key setup routine?
> > If not, what's the difference?
>
>
> Most ciphers have a maximum key size - unless the user key is hashed first,
> of course, but then you really don't have a single primitive.
>
> An error propagating cipher would do if the error propagation is secure - by
> definition, because secure error propagation ought to be defined as if the
> function F_x(y) is secure for any length of x and y, where x is the first
> part of the message and y is the last part of the message. If this is so,
> then the primitive could be constructed as G^n(x) = F_x(0^n), where x is the
> input and n is the desired length of the output. (0^n should be interpreted
> as a string of n zeroes.)
>
> That's what e.g. Steak does.
I'll make you a deal. I'll look at yours and comment if you'll
do the same with mine :-)
Paul
>
>
> --
> Henrick Hellström [EMAIL PROTECTED]
> StreamSec HB http://www.streamsec.com
>
>
------------------------------
From: Alan Mackenzie<[EMAIL PROTECTED]>
Crossposted-To: alt.hacker,talk.politics.crypto
Subject: What is a group? [Re: OAP-L3: "The absurd weakness."]
Date: Wed, 16 May 2001 20:43:51 +0000
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote on Tue, 15 May 2001
12:59:47 -0700:
> James Felling wrote:
[ .... ]
> Just do this one point. Or choose perhaps a simpler one like,
> "Scramble is a group" and tell us what you mean and how this
> somehow supports your claims.
A group is a mathematical entity consisting of a set of objects (let's
call them A, B, C, ...) and an binary operation (let's call it *) on
these objects such that:
(1) For all A, B in the set, A * B is also in the set;
(2) For all A, B, C in the set, A * (B * C) = (A * B) * C;
(3) There is an element I (called the "identity"), in the set, such
that, for all A in the set, I * A = A * I = A;
(4) For each A in the set, there is an element A' (called the "inverse"),
such that A * A' = A' * A = I.
Examples of groups:
(1) The whole numbers with the operation of addition. The identity is
zero and the inverse of, say, 5, is -5.
(2) Mixups of the Rubik cube (or, rather, sequences of moves which result
in these mixups), the operation being concatenating the mixups.
(3) Permutations on finite sets (where "permutation" is to be though of
more as "the operation of rearrangement" rather than "an
arrangement"), with the operation of composition. For example, if A
= (123)(45), and B = (12)(35), the A * B = (2543) and B * A = (1345).
It is the third example which here is pertinent. If I understand
correctly, the notion of a group arose originally from abstracting the
essence of permutations. There is an extensive theory about groups (this
is an understatement, by the way) and it is fair to say that having a
grasp of this theory is a prerequisite to making judgements upon the
security of any cypher based upon permutations.
By "Scramble is a group", I think James meant that there is a group whose
members are "scrambling with a particular key" and whose operation is
composing two scrambles. In otherwords, no matter how many times you
scramble, S(A) * S(B) * .... * S(K), there is a key, Z, such that this
composite operation is equivalent to S(Z), i.e. the multiple scramble is
no better than a single scramble.
It's well worth while reading up about groups. A book I found very
helpful when I was at university was "A First Course In Abstract Algebra"
by John B. Fraleigh (published by Addison-Wesley 1967, ISBN unknown,
"Library of Congress Catalog Card No." (whatever that is) 67-17258). I
don't know if this book's still available.
Hope this helps.
> Thank you.
--
Alan Mackenzie (Munich, Germany)
Email: [EMAIL PROTECTED]; to decode, wherever there is a repeated letter
(like "aa"), remove one of them (leaving, say, "a").
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: MISTY -- no simple truncated difs
Date: Wed, 16 May 2001 21:00:19 GMT
"jlcooke" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> > Wow man the sboxes in MISTY are keen. They have a very low dpmax of
2/512
> > and 2/128 respectively... cubing in GF(2^n) n=odd is obviously very
> > effective :-)
>
> n = prime. or (2^n)-1 = mersenne prime maybe what you're looking at.
According to Matsui if n is odd then cubing in GF(2^n) has a maximally low
dp and lp bias for any bijective function.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Karnaugh Maps
Date: Wed, 16 May 2001 21:02:06 GMT
"Sam Simpson" <[EMAIL PROTECTED]> wrote in message
news:SfvM6.19485$[EMAIL PROTECTED]...
> Dr Gladman has done a lot of work finding optimal boolean terms for
S-Boxes
> for Serpent Tom - he may have some source code that you could use if your
> going to do a lot of this kind of thing.
Well I am keener on learning how todo more than just having tools todo it.
Thanks though...
Gladman's code is horrible though (unlike his AES implementation) since it's
not well commented, huge and written in C++...arrg!
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Karnaugh Maps
Date: Wed, 16 May 2001 21:03:50 GMT
"Xcott Craver" <[EMAIL PROTECTED]> wrote in message
news:ddtM6.85005$[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> >Ok here is my first attemp to optimizing a boolean decomposition . This
is
> >the lsb of the TC15 sbox..
> >
> >dc ba 00 01 10 11
> >-----------------------------------------
> >00| 1 0 0 1
> >01| 0 1 1 0
> >10| 0 1 1 0
> >11| 0 1 1 0
>
> Hi,
>
> For k-maps, it's best to put the variables in Gray code order:
>
> >dc ba 00 01 11 10
> >-----------------------------------------
> >00| 1 0 1 0
> >01| 0 1 0 1
> >11| 0 1 0 1
> >10| 0 1 0 1
>
> This causes simple regions on the map to correspond to
> simple expressions. The middle square of 4 bits, for example,
> are the outputs for which ac==1.
>
> Are you allowed to use XORs as a primitive? Because this is
> very XOR-friendly: the expression is (a^b)^(~(d|c)).
The original expression was
y0 = a ^ b ^ (c&d)
But I want to only use OR, AND and NOT gates.
Thanks for the reply,
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: TC15 analysis
Date: Wed, 16 May 2001 21:09:10 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9du4hf$5e1$[EMAIL PROTECTED]...
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:sOiM6.101727$[EMAIL PROTECTED]...
> >
> > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > news:9dsd5f$97b$[EMAIL PROTECTED]...
> > >
> > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > news:s8gM6.100647$[EMAIL PROTECTED]...
> > > >
> > > > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > > > news:9drhq3$vaa$[EMAIL PROTECTED]...
> > > > >
> > > > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > > > news:4zeL6.76746$[EMAIL PROTECTED]...
> > > > > > I started my analysis of TC15 (more than just poking). I am
> looking
> > > for
> > > > > low
> > > > > > hamming weight differentials (i.e low active sbox count).
> > > > > I just verified that there are no single round iterative
> differentials
> > > (at
> > > > > any probability level) with hamming weight 6 or less.
> > > >
> > > > May I ask *how* you analyzed it. That's more meaningful then just
the
> > > > results.
> > >
> > > Ok, I considered all possible differentials into the start of a round
> with
> > > Hamming weight of 6 or less (well, 7 now, as my computer completed
> > searching
> > > over 7 since I last posted). Since the cipher is circularly symmetric
> as
> > > far as differentials are concerned (rotating all the variables by the
> same
> > > amount preserves the differential behavior), that reduced the search
> > > somewhat. For each such differential, I computed how it would flow
> > through
> > > the linear transform, and then see if the sbox could possibly
transform
> > that
> > > differential back to the original one (possibly circularly rotated).
> >
> > I dunno what you mean by "rotating all the variables by the same amount
> > pre...". my LT doesn't do a simple rotate...Maybe I am looking at it
> > wrong...
> TC5 consists of three different operations:
> - Xoring in of key material
> - Fixed 32 bit rotates
> - 32-bit-wide xors/and/ors
>
> For all these three operations, if you take a differential input, and
apply
> a rotate of (say) 7 bits to the right, then the output differential will
> also be rotated 7 bits to the right. And hence, the entire cipher has the
> property that if you have a differential (a,b,c,d) to (x,y,z,w) with
> probability p, then you also have a differential (a>>>7,b>>>7,c>>>7,d>>>7)
> to (x>>>7,y>>>7,z>>>7,w>>>7) with probability p.
This is true.
>
> Question for the student: this property does not hold for direct inputs:
if
> (a,b,c,d) encrypts to (x,y,z,w), then (a>>>7,b>>>7,c>>>7,d>>>7) might not
> encrypt to (x>>>7,y>>>7,z>>>7,w>>>7). Why not?
Off hand I don't know, but I would have to say it's because the
substitutions will replace the a,b,c,d with different values then
a<<<7,b<<<7,etc... Also the key material will be diff at diff bit rotations.
You would have to rotate all the keys too?
Am I remotely close?
>
> >
> > I have a relatively fast PC, maybe you could send me the source and I
> might
> > be able to learn from it/use it.
> I won't bore the rest of the newsgroup with it -- I'll email it to you.
>
> >
> > > > > My next step: two round iterative differentials...
> > > >
> > > > Ahh keen.
> > > It'll be a lot of work. Likely, I won't be able to do anything
> > > exhaustive -- some pruning will be required to keep it feasible.
> > > >
> > > > So you found 1R differentials with 7 active sboxes? That would be
> > > 16*7=112
> > > > active sboxes ... way over the 64 limit.
> > > No -- at that point, my computer completed the search to that extent,
> and
> > > I'm not working with "active sboxes", but input Hamming weight. It
> still
> > > hasn't found *any* 1R differentials. I found several differentials
that
> > > almost work -- it feels like there might be some simple reason why
such
> a
> > > differential can't exist, but that reason escapes me so far.
> >
> > Well if you OR the four words together the hamming weight over GF(2^32)
is
> > the number of active sboxes. So if you have a HW of 7 that means 7
sboxes
> > are active does it not? Or are you assuming differences occur in
parallel
> > bits?
> No, a Hamming Weight of 7 means that there are 7 one's in the input
> differential.
>
> In any case, it turns out there was a bug in my program -- I had the sbox
in
> backwards (which brings up an obvious question -- would the cipher
actually
> be stronger if you inverted the sbox? Probably not). When I fixed that,
it
> did find a one round differential at hamming weight 7 (with probability
> 2**-15). The differential at the beginning of a round is (in binary):
> 00000000000000000000010000010001
> 00000000000000000000001000010000
> 00000000000000000000000000000000
> 00000000000000000000001000001000
>
> The linear transform turns it into:
> 00000000000000000000000000000001
> 00000000000000000000000000011000
> 00000000000000000000001000011000
> 00000000000000000000010000001001
>
> And each of the 5 active sboxes has a 2**-3 probability of turning the
bits
> within its column back into the column settings of the original
> differential.
>
> Obviously, this particular differential is not really a concern against
the
> full cipher. However, given a full code book, the fact that this
> differential really is 32 different differentials (by rotational symmetry)
> and the fact that the cipher doesn't avalanche all that well, I suspect
that
> this can be used to attack 10 or 11 rounds, by having the differential go
> through the first 8, and the last 2-3 rounds not quite covering up the
> evidence well enough.
That is not true. Let's say you found one pair called (a,b,c,d) and
(a',b',c',d') such that they are a correct pair, then
(a<<<7,b<<<7,c<<<7,d<<<7), etc... is not nessesarly a correct pair.
> > May I ask what you think about the cipher so far? Good/bad?
> Well, it is certainly elegant, and has no profoundly obvious weaknesses
> (although the differential above cuts too close into the safety margin for
> me to be comfortable -- a few more rounds may be warrented). A quick
cycle
> count implies that it has a respectable, but not outstanding, speed in
> software. However, the program should be shortish (the expanded key
> schedule is too large to be called really short), and assuming the key
setup
> isn't too obnoxious, a hardware implementation would appear to take up
> hardly any transistors at all.
Hmm well I want to improve my LT to avoid all simple 1R differentials
involving under 6 or so sboxes. Although if the best 1R diff has 5 sboxes
then I still win since the prob is out of bounds... :-)
The key schedule is based on the cipher itself so I would think the entire
cipher would have a lot foot print.
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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
