Cryptography-Digest Digest #356, Volume #14 Tue, 15 May 01 03:13:00 EDT
Contents:
Re: PRNG question from newbie ("Henrick Hellström")
Re: Hughes DH variant ("Tom St Denis")
Re: Hughes DH variant (Paul Rubin)
Re: Hughes DH variant ("Tom St Denis")
Decorrelation is why Galois Fields are important. (John Savard)
Re: Decorrelation is why Galois Fields are important. ("Tom St Denis")
Re: Optimizing AES throughput ([EMAIL PROTECTED])
TC15 x86 code on non-athlons? ("Tom St Denis")
Re: What Is the Quality of Randomness? ("Trevor L. Jackson, III")
Re: Decorrelation is why Galois Fields are important. (John Savard)
Re: Decorrelation is why Galois Fields are important. ("Tom St Denis")
linear cryptanalysis of Noekeon ("Tom St Denis")
Re: Key escrow based on BBS (Bryan Olson)
Re: Security proof for Steak (Benjamin Goldberg)
Re: Are low exponents a problem with RSA? ("Roger Schlafly")
Re: Are low exponents a problem with RSA? ("Roger Schlafly")
Re: ISO 9796-1:1991 (Ulrich Kuehn)
Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm) (Arturo)
The GQ signature scheme ("Guy-Armand kamendje")
----------------------------------------------------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: PRNG question from newbie
Date: Tue, 15 May 2001 01:16:14 +0200
"John Myre" <[EMAIL PROTECTED]> skrev i meddelandet
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.
>
> Have you heard of this, or have opinions on the idea? How
> is this related to the concept of a PRF?
There is an algorithm that does this, namely our cipher Steak. You might
want to have a look at
http://www.streamsec.com/salgo.asp
http://www.streamsec.com/keysetup.asp and
http://www.streamsec.com/sattacks.asp
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Hughes DH variant
Date: Mon, 14 May 2001 23:44:18 GMT
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Randy Langer <[EMAIL PROTECTED]> writes:
> > "z = y^-1". A true (floating point) inversion, or mod something??? As I
say, it
> > looks a little incomplete. I assume it's suppose to be (mod p), but I
always
> > like confirmations...
>
> Yes, mod p. If you have to ask questions like that, better study some
> math before beginning implementation.
Um you solve the inverse exponents modulo p-1.
Tom
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Hughes DH variant
Date: 14 May 2001 16:58:50 -0700
"Tom St Denis" <[EMAIL PROTECTED]> writes:
> > Yes, mod p. If you have to ask questions like that, better study some
> > math before beginning implementation.
>
> Um you solve the inverse exponents modulo p-1.
oops.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Hughes DH variant
Date: Tue, 15 May 2001 00:25:37 GMT
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> writes:
> > > Yes, mod p. If you have to ask questions like that, better study some
> > > math before beginning implementation.
> >
> > Um you solve the inverse exponents modulo p-1.
>
> oops.
I've done that before... hehehehe no harm done.
Tom
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Decorrelation is why Galois Fields are important.
Date: Tue, 15 May 2001 00:48:37 GMT
A while back, I made a post entitled "Why Galois Fields are Important
in Cryptography". It was greeted by some controversy; in it, I noted
that because Galois Field multiplication distributes over XOR,
combining the two operations allows one to create multiple pathways
between a given input and a given output - all of which will produce
different outputs for any other one input.
It turns out this property is the one called 'decorrelation', and used
in the Decorrelated Fast Cipher, as I have seen recently from
discussion in the thread 'Countermeasures to Differential
Cryptanalysis'.
Well, I have added a note to that effect to my description of the DFC,
at
http://home.ecn.ab.ca/~jsavard/crypto/co040812.htm
but I am surprised the replies to my post tended to state my notion
was unimportant, and no one mentioned decorrelation.
Of course, I initially presented it in connection with making the OTP
maximally resistant to bit-flipping, and so that provoked a natural
response (we have hash functions to authenticate messages!) which
neglected other possible uses of this property.
Or maybe just mentioning the OTP in my example raised the red flag of
crankdom...
John Savard
http://home.ecn.ab.ca/~jsavard/
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Decorrelation is why Galois Fields are important.
Date: Tue, 15 May 2001 00:52:12 GMT
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> A while back, I made a post entitled "Why Galois Fields are Important
> in Cryptography". It was greeted by some controversy; in it, I noted
> that because Galois Field multiplication distributes over XOR,
> combining the two operations allows one to create multiple pathways
> between a given input and a given output - all of which will produce
> different outputs for any other one input.
>
> It turns out this property is the one called 'decorrelation', and used
> in the Decorrelated Fast Cipher, as I have seen recently from
> discussion in the thread 'Countermeasures to Differential
> Cryptanalysis'.
>
> Well, I have added a note to that effect to my description of the DFC,
> at
DFC doesn't use GF math btw.
Also decorrelated functions are not magic. See my MDFC paper.
Tom
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Optimizing AES throughput
Date: Tue, 15 May 2001 03:23:57 +0300
Harshal Chhaya wrote:
> I guess I should have given some background. I am trying to find the
> suitability (not in crypto terms) of AES in a communications network.
> At high data rates, it seems like the encryption, if done in s/w,
> could be a bottleneck. The 70 Mbps figure (on a 200MHz PPro) in the
> Rijndael paper looked good till I started extrapolating it to
> communication processors running at lower speeds. A h/w implementation
> is the best option but I was hoping that a s/w solution might suffice
> till the h/w is done.
My software implementation for Pentium III (that Brian Gladman was pointing
at) works at 445 Mbit/s on a 800 MHz P3. If you scale it to the 1.13MHz
version you already surpass the NSA hardware implementation. (628 Mbit/s vs
605 Mbit/s) However, the fastest hardware implementation that I know (by
Mitsubishi) works at 1950 Mbit/s.
An online crosstable of all implementations of AES candidates, known to me,
is given at http://www.tml.hut.fi/~helger/aes
Help that hopes,
Helger
http://www.tml.hut.fi/~helger
>
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: TC15 x86 code on non-athlons?
Date: Tue, 15 May 2001 01:56:38 GMT
I've updated my x86 assembly code to reflect the changes in the sbox I made.
I also optimized this a bit (trial and error) and got it downto 295 cycles
per block on my Athlon T-bird. That's about 500 mbit/sec at 1.2ghz
(assuming this is linear this amounts to about 290 Mbit @ 700mhz).
I was wondering if anyone could see any further Athlon optimizations or
possibly write a Intel specific version of the code? That would be very
keen. I think i've done my "homework" in this instance...
The assembly code is at
http://tomstdenis.home.dhs.org/tc15_asm.zip
You need DJGPP and NASM to compile/test it (should work under linux using
gcc and nasm)
The C code is at
http://tomstdenis.home.dhs.org/tc15.c
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Tue, 15 May 2001 02:01:18 GMT
Tim Tyler wrote:
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>
> : There is no such thing as a random sequence, only a random source.
>
> Well, "random sequence" is a meaningul term - provided one uses the notion
> of randomness that derives from Chaitin and Kolmogorov, rather than from
> Shannon.
I disagree. Chaitin's usage of the term random encompasses at least three
otherwise distinct meanings. There is less there than meets the eye.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Decorrelation is why Galois Fields are important.
Date: Tue, 15 May 2001 02:20:52 GMT
On Tue, 15 May 2001 00:52:12 GMT, "Tom St Denis"
<[EMAIL PROTECTED]> wrote, in part:
>DFC doesn't use GF math btw.
No, it uses multiplication and addition in the ordinary sense instead,
to achieve the same result.
John Savard
http://home.ecn.ab.ca/~jsavard/
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Decorrelation is why Galois Fields are important.
Date: Tue, 15 May 2001 02:33:01 GMT
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Tue, 15 May 2001 00:52:12 GMT, "Tom St Denis"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >DFC doesn't use GF math btw.
>
> No, it uses multiplication and addition in the ordinary sense instead,
> to achieve the same result.
I would argue that the idea is similar but the result is not.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: linear cryptanalysis of Noekeon
Date: Tue, 15 May 2001 02:41:29 GMT
In the original sbox from Noekeon the first output bit is equal to the first
input bit 0.75 of the time. Now if theta doesn't throw off this probability
couldn't an attack be mounted with a prob of (0.75)^16 = 2^(-6.64)?
I never have mounted a linear attack before. Could someone explain the
basics of one? I would like to see if this approx can be exploited...
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Key escrow based on BBS
Date: Mon, 14 May 2001 20:07:17 -0700
Tom St Denis wrote:
> Bryan Olson wrote in message...
> > With public information you can find a square root of K?
> > Note that you didn't say anything about publishing the
> > factorization of N, and doing so would destroy the system.
> > Please do tell how.
>
> What the heck? You're distorting everything I am saying.
No, I'm saying what I said in the first place. A good (from
a technical point of view) scheme for mandatory key escrow
will have important properties that these trivial schemes
lack. In particular, one should be able to tell from the
[transmitted] message and public information (and assuming
no other channels) that the escrow authority can recover the
same [plaintext] message as the recipient.
> The only thing my system provides is a way for the Host to
> read all messages too.
Provided the sender cooperates.
> It would be hard to get away with faking the last K value.
That is only true if the escrow authority routinely attempts
message recovery to check for faked K values. I am an
opponent of key escrow/recovery, but I doubt that even most
advocates would support unlocking messages just to check for
compliance.
--Bryan
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Security proof for Steak
Date: Tue, 15 May 2001 00:20:38 -0400
Henrick Hellström wrote:
>
> "Benjamin Goldberg" <[EMAIL PROTECTED]> skrev i meddelandet
> news:[EMAIL PROTECTED]...
> > Henrick Hellström wrote:
> > > The table in the source code is the expansion of a 32x32 linear
> > > bit matrix, so that only four lookups will be needed for each 32
> > > bit input (one for each byte of the input). The design rationale
> > > for choosing that particular matrix is purely empirical, but it
> > > might be re-created in a few steps:
> > > a) Start with the 4x4 MDS matrix of TwoFish.
> > > b) Apply a quadruple of s-boxes so that the matrix degenerates
> > > into a 32x32 invertible bit matrix over GF(2).
> > > c) Transpose the rows and then the columns of the 32x32 matrix
> > > according to a pair of constant permutations.
> >
> > How much code would it take to do this? How does that compare to
> > the size of writing the tables into your source directly?
> >
> > You've explained it only partially. You haven't said what those
> > four sboxes are, and you haven't said what the permutations are.
>
> Oh, you mean the s-boxes and transpositions that will get you from the
> TwoFish matrix to the Steak matrix?
>
> 1. The s-boxes are easy to represent in code: Expand the TwoFish MDS
> matrix to it's 4 times 256 dword representation. Sort each of the four
> rows of this table. (Three of the rows should be sorted using regular
> arithmetic comparison. The second row has to be sorted modulo 2^16.)
> The resulting table is such that the elements [i,2^j] will generate
> the entire table. (Hm!? Could this fact be used in a differential
> attack on TwoFish? Perhaps if the key space is expanded carelessly.))
>
> 2. The transposition of the columns of the bit matrix was the "black
> box" output of an experimental comparison of different permutations.
> Its map representation is <0 8 9 16 2 24 25 17 10 18 26 11 2 19 27 3
> 28 4 20 29 21 5 12 13 22 30 6 7 14 15 23 31>. The transposition of the
> rows was a rotate right by one. (A clarification: The row
> transposition, i.e. the ror by one of the table values, was applied
> prior to the column permutation.)
Step 1 seems ok, but I don't like step 2 -- it looks to me that there's
more muddle than math going on here. You say you got the permutation of
columns through experiment... couldn't you do anything better than that?
Some simple looking formula which would give just as good results? I
bet that if you did a multiplication by 0xdeadbeef in GF(2^32) would be
just as good (or some other constant, it doesn't matter much). The
result would no weaker than transposition, assuming the right multiplier
and field were used.
--
Customer: "I would like to try on that suit in the window."
Salesman: "Sorry sir, you will have to use the dressing room."
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: Are low exponents a problem with RSA?
Date: Tue, 15 May 2001 04:02:25 GMT
"David Wagner" <[EMAIL PROTECTED]> wrote in message
news:9dfj1o$fn8$[EMAIL PROTECTED]...
> Matthew Kwan wrote:
> >Given the encryption function C = (P^e) mod n where (e,n) is
> >the public key, is there any security weakness in choosing a small
> >value of e?
> If P is your message, without padding, there are issues. Use OAEP,
> and they go away.
> (There is also theoretical work which might be viewed as evidence that
> RSA could be less secure with e=3 than with general e, but personally
> I'm happy to stick with e=3 for the moment.)
Shoup has a new paper that argues that OAEP is not as secure as is
widely thought, but that RSA-OAEP with e=3 is ok. It raises the
possibility that RSA-OAEP with large exponent might be *less* secure
than e=3. See:
http://shoup.net/papers/oaep.pdf
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: Are low exponents a problem with RSA?
Date: Tue, 15 May 2001 04:54:24 GMT
"Roger Schlafly" <[EMAIL PROTECTED]> wrote
> Shoup has a new paper that argues that OAEP is not as secure as is
> widely thought, but that RSA-OAEP with e=3 is ok. It raises the
> possibility that RSA-OAEP with large exponent might be *less* secure
> than e=3. See:
> http://shoup.net/papers/oaep.pdf
After posting this, I see he refers to another paper that gives an
argument for the security of RSA-OAEP with other exponents.
This apparently attempts to fill some gaps in the Bellare-Rogaway
arguments. See:
http://eprint.iacr.org/2000/061.pdf
------------------------------
From: Ulrich Kuehn <[EMAIL PROTECTED]>
Subject: Re: ISO 9796-1:1991
Date: Tue, 15 May 2001 08:35:26 +0200
Reply-To: [EMAIL PROTECTED]
Shai Halevi wrote:
>
> ISO 9796-1 was withdrawn because it is (badly) broken. See details in
> the paper "A Chosen Messages Attack on the ISO/IEC 9796-1 Signature
> Scheme" by François Grieu, in Eurocrypt'2000, LNCS 1807, Springer,
> 2000, pp. 70-80.
>
> Are you sure you want to implement it? It may be a security problem.
>
The OP had to implement HBCI which is currently specified to use ISO
9796:1991, but it uses it in a nonstandard way: The message to be signed
is purely a hash of the message, being done with RIPEMD-160.
This gives the somewhat funny situation that they basically tried to
reinvent ISO 9796-2, using a signature format that was designed when no
hash function was standardised.
I think that using the hash has a certain usable security margin
against the attacks that ended ISO 9796:1991, but maybe one of the
authors of the attacks can comment on this?
Regargs,
Ulrich
------------------------------
From: Arturo <aquiranNO$[EMAIL PROTECTED]>
Subject: Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm)
Date: Tue, 15 May 2001 08:34:08 +0200
On Sat, 12 May 2001 15:06:43 -0600, [EMAIL PROTECTED] (wtshaw) wrote:
>In article <[EMAIL PROTECTED]>, Jim D wrote:
>
>In elementary school, we had 4-10's and 22's and caried them to class
>occasioinally, shot them at recess, took bullets apart, ignited contents
>and fired the caps with a rock. The powder sometimes went into bombs,
>most that fizzled. We shot firewirks, including banned ones from
>Oklahoma, made our own cannon that fired projectiles of sticks, grass, and
>rocks as we played war games with old building materials. In high school,
>we had our own rocket club and some of these thing went for miles. We had
>not adult supervision, made our own membership cards, and met to try out
>our latest projects.
Gosh, if the soviets did it, you guys yell out to the entier world how
bellicous and committed to world domination are. But since it´s you, there´s
nothing wrong? If you want them to defend their country, do it right: just send
them to compulsory military service, then have then re-train and do field
exercises every year under strictly military supervision, a la Swss. You won´t
convince me than pre-teenagers playing McGyver or A-team will do better than
blowing up Fed buildings.
>Otherwise, nobody cared, we were learning lot about physics, not trying to
>bump each other off.
I´ve teaching physics for well over a decada, and I can tell you,
there´s no need to shoot a rifle in order to understand momentum or ballistic
motion.
------------------------------
From: "Guy-Armand kamendje" <[EMAIL PROTECTED]>
Subject: The GQ signature scheme
Date: Tue, 15 May 2001 08:43:02 +0200
Is there a reason why the Guillou-Quisquater signature scheme was never
mentioned in the IEEE p1363x (unless I have overseen it)?
I mean:
0) relevant security flaws
1) patents issues
2) the algorithm was never submitted to the IEEE p1363 board....
thanks Guy-A
------------------------------
** 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
******************************
