Cryptography-Digest Digest #836, Volume #12 Wed, 4 Oct 00 09:13:01 EDT
Contents:
Re: Any products using Rijndael? (Tom St Denis)
Re: Rijndael cracked by Biham! (Tom St Denis)
Re: Josh MacDonald's library for adaptive Huffman encoding (Kent Paul Dolan)
Re: Requirements of AES (Tom St Denis)
Re: Rijndael cracked by Biham! ([EMAIL PROTECTED])
Re: NTRU inversion (Rasmus Faber Larsen)
Re: Rijndael cracked by Biham! (Daniel Leonard)
Re: Rijndael: making the "flaw" plainer (John Savard)
Leighton-Micali: I must be missing something (John Savard)
Re: It's Rijndael (John Savard)
Re: Advanced Encryption Standard - winner is Rijndael (John Savard)
Re: Rijndael cracked by Biham! (John Savard)
Re: Requirements of AES (Tim Tyler)
Re: Rijndael cracked by Biham! (Dido Sevilla)
Re: SHA C++ Implementation (Dido Sevilla)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Any products using Rijndael?
Date: Wed, 04 Oct 2000 11:13:32 GMT
In article <8rf0ej$2oc1$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Thomas Pornin) wrote:
> According to Tom St Denis <[EMAIL PROTECTED]>:
> > I heard that trimming the DES key from 112 bits to 56 was ok...
cause
> > nobody can guess a 56 bit key in 10 quadrillion billion years.
>
> Whoever told that, even 25 years ago, was either drunk or incompetent.
> The cost of a 56-bit key search has been well estimated and
anticipated
> since the early seventies.
I wasn't alive in the 70's so don't blame me, but they still reduced
the key size despite critism.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Rijndael cracked by Biham!
Date: Wed, 04 Oct 2000 11:12:28 GMT
In article <8rf1m6$jvk$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> The article on :
>
> http://sectedesax.ctw.cc
>
Where? My French is very rusty...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Crossposted-To: comp.compression,comp.theory
Subject: Re: Josh MacDonald's library for adaptive Huffman encoding
Reply-To: [EMAIL PROTECTED] (Kent Paul Dolan)
From: [EMAIL PROTECTED] (Kent Paul Dolan)
Date: Wed, 04 Oct 2000 11:24:45 GMT
So far the funniest part of this series of David destroying his reputation
on the Internet is this part:
Organization: Retired US Government Real Time computer Xpert
Happening to be retired from US Government service, still a real time
computer programmer, as occasion demands, and disavowed to be an
"expert" at anything because even in my case, when it comes to my
profession rather than my personal life, humility works better than
hubris, I have to say that the "prime" skill in being a "computer
expert" is clear communication. David is clearly no expert.
Oh, and do your short fused best David, I retired from sea service,
The foul language you bandy about was my daily vocabulary for a couple
of decades. I grew out of it before I left service, and your ability
to insult me doesn't exist. You do make me laugh, however, so carry on
as you wish.
Cheers!
xanthian.
===== random quote by or about this author =====
I liked your flame. It was sick and twisted and funny.
-- Sue {"suZee lye", "Kay Caustic",
[EMAIL PROTECTED]} Kramer
--
Kent Paul Dolan.
<[EMAIL PROTECTED]> <[EMAIL PROTECTED]> <[EMAIL PROTECTED]>
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Requirements of AES
Date: Wed, 04 Oct 2000 11:19:46 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : [EMAIL PROTECTED] wrote:
>
> :> Twofish has a related key attack on 11 rounds. The best practical
> :> attack is on 6 rounds. 16/6 is a good margin, but 16/11 is more
like a
> :> Rijndael margin, actually worse.
>
> : What attack on Twofish has a 16/11 advantage? [...]
>
> According to 3.2.1.5 of the NIST report they know of no such attack.
>
> They reference:
>
> http://csrc.nist.gov/encryption/aes/round2/comments/20000501-
nferguson-1.pdf
>
> "A Twofish Retreat: Related-Key Attacks Against Reduced-Round Twofish"
> Niels Ferguson, John Kelsey, Bruce Schneier and Doug Whiting - for the
> best known related key attack on Twofish.
>
> There /was/ a 10-round attack suggested in the original Twofish paper.
> Apparently it fails to work.
Maybe I am just a troll, but doesn't that mean people *tried* to break
Twofish?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Rijndael cracked by Biham!
Date: Wed, 04 Oct 2000 11:25:43 GMT
So where exactly is the information you mention 'cos from what i see,
this is just about some sect.
Brice.
In article <8rf1m6$jvk$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> The article on :
>
> http://sectedesax.ctw.cc
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Rasmus Faber Larsen <[EMAIL PROTECTED]>
Subject: Re: NTRU inversion
Date: Wed, 4 Oct 2000 14:04:05 +0200
On Wed, 4 Oct 2000, Benjamin Goldberg wrote:
> I've written some C code for doing NTRU inverses, by translating the
> psuedocode in NTRUTech001.ps.gz (from the ntru web site), but there are
> some parts I don't understand. Lines that I couldn't convert to C code
> are marked with @@, with the particulars surrounded by @? and ?@.
> Security parameters (particularly N) are in the .h file, part of which
> I'll include here. Would someone please help?
> @@ NTRU_trp b = @? X**N-1 ?@;
I assume you are doing the polynomial calculations by treating polynomials
as a vector/array. What this basically says is (if I understand your
type-definitions correctly) is, that b.value[N]=1,
b.value[N-1]=...b.value[1]=0 and b.value[0]=-1.
> @@ @? write d = v_3 * q + t_3 (mod P)
> @@ with deg(t_3) < deg(v_3) ?@
> // This is long division of polynomials in (Z/PZ)[X].
Here you need a subalgorithm to take care of division of polynomials. You
are supposed to divide d by v_3 putting the quotient in q and the
remainder in t_3. A textbook concerning polynomial algorithms
should contain such an algorithm (basically it is the same as doing long
division with integers). If you cant find it, let me know, and I will dig
up a reference for you.
> for( i = N; i--; )
> t_1.value[i] =
> @@ u.value[i] - @? q ?@ * v_1.value[i];
Well, with the above, this should be rather obvious. You have to muliply
the polynomial q with the polynomial v_1. It should read more like this,
though:
for( i=N; i--; ){
t_1.value[i]=u.value[i];
for( j=i; i--; )
t_1.value[i]=t_1.value[i]-q.value[i-j]*v_1.value[j];
}
> 2) The q in the 4th problem line seems to come out of nowhere... I think
> it's a typo.
No, it is the result from the division in the line above.
> 3) After the assignment of b to v_3, b is no longer used. Is this a
> mistake? Why not assign to v_3 in the first place, and save space?
Well, b=x^N-1 will probably be used in most, if not all, of your
algorithms, so I assume the authors use it as a global constant, and then
assign it to the variable v_3 in this algorithm.
> 4) v_2 and t_2 don't appear anywhere. What's up with that? Did they
> exist in a prior version?
I think (not certain) that they come from the algorithm described in
Cohen's book, as refered to in the comments.
> 5) f and g (in key generation) are supposed to be generated in a manner
> similar to how phi (in encryption) is generated, according to the HTML
> description of the system. The psuedocode gives a different way of
> generating them. Why?
There seems to be different versions of the cryptosystem floating around.
But the most recent article uses the collections L(d_1,d_2)={F \in
Z[X]/(X^N-1) | F has d_1 coefficients of 1, d_2 coefficients of -1 and
N - d_1 - d_2 + 1 coefficients of 0}, and then choosing f \in L(d_f,d_f-1)
, g \in L(d_g,d_g) and \phi \in L(d,d) for a fitting choice of d_f, d_g
and d. (See Hoffstein, Pipher and Silverman : NTRU: A Ring-Based Public
Key Cryptosystem, p.5 pp).
This restricts the keyspace corresponding to a choice of N a bit, but
ensures that the probability of decryption failure can be estimated (and
this kept to an acceptable level).
You might also want to take a look at Technical Report #14, which
describes a faster algorithm for finding polynomial inverses. - And if you
use this one, you will not have to look up the polynomial division
algorithm. (Incidentally, the C-code I sent yesterday is based on this
algorithm, and not the more common one described in report #1).
Good luck with your project, and feel free to contact me with any
questions.
Kind regards
Rasmus Faber Larsen.
********************************************************************
* Rasmus Faber Larsen * e-mail: [EMAIL PROTECTED] *
* Department of Mathematics * http://www.dfi.aau.dk/~faber *
* DK-8000 Aarhus C * office: F2.12 phone: (+45) 8942 3488 *
********************************************************************
------------------------------
From: Daniel Leonard <[EMAIL PROTECTED]>
Subject: Re: Rijndael cracked by Biham!
Date: Wed, 04 Oct 2000 12:12:51 GMT
On Wed, 4 Oct 2000, Tom St Denis wrote:
> In article <8rf1m6$jvk$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > The article on :
> >
> > http://sectedesax.ctw.cc
> >
>=20
> Where? My French is very rusty...
>=20
> Tom
>=20
>=20
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>=20
Don't even bother to translate.
==========
Daniel L=E9onard
OGMP Informatics Division E-Mail: [EMAIL PROTECTED]
D=E9partement de Biochimie Tel : (514) 343-6111 ext 5149
Universit=E9 de Montr=E9al Fax : (514) 343-2210
Montr=E9al, Quebec Office: Pavillon Principal G-312
Canada H3C 3J7 WWW : http://megasun.bch.umontreal.ca/~leonard
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Rijndael: making the "flaw" plainer
Date: Wed, 04 Oct 2000 11:57:29 GMT
On Wed, 04 Oct 2000 07:20:58 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>On the other hand this Byte Sub is a constant substitution,
>while with the Feistel ciphers one uses one half to
>control the substitution of the other part and with two
>rounds the whole gets modified. I don't yet see why do
>you feel that Byte Sub is more 'complicated' or 'stronger'
>in some sense. Or am I misunderstanding you?
It is true that the f-function in DES has some advantages over a pure
substitution: it is stronger than the one in GOST, for example. But
the Mix Column step is stronger than simply XORing the f-function
output with the other half.
So as far as that weakness is concerned, it balances out.
What is stronger is the specific fact that the substitution is
actually applied to the source byte, changing it. This may only appear
stronger, of course, since after two rounds, in a Feistel cipher, the
half that was the source in the first round then gets affected
nonlinearly by itself.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Leighton-Micali: I must be missing something
Date: Wed, 04 Oct 2000 12:10:36 GMT
I had always thought that Kerberos was designed for a rather specific
network setup. For the general case where you have one trusted central
computer, T, and a bunch of users, including A, B..., and each user
shares a secret key K(A), K(B)... with T, and the goal is to set up
secure communications between two arbitrary users with T's help,
as opposed to the Kerberos case, where communications are between a
user and a computational server, and the two-level hierarchy is to
allow project groups to have control over the passwords to their own
machines,
wouldn't the "standard" protocol be the following:
A: "A", E("B", K(A)) -> T
T: E( S, K(A) ) -> A
T: E( [ S, "A" ], K(B) ) -> B
where the function E( text, K(whoever) ) can actually involve its own
session key, using E(whoever) only as a key-exchange key, as well as
including a timestamp?
Of course, that is encryption-based.
In the case of Leighton-Micali, while it is all very clever to store
in a table of size O(n^2) the two entries E( S(A,B), K(A) ) and E(
S(A,B), K(B) ) xor E( S(A,B), K(A) ) xor E( "B", K(B) ), if the
encryption function E is resistant to known-plaintext attacks, I am
really failing to see the point of not making the second entry E(
S(A,B), K(B) ) and just choosing the S(A,B) values as true random
numbers rather than hashes of "A" and "B".
And, of course, A and B would use S(A,B) as a key-exchange key; that
much is noted in Leighton-Micali, of course.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: It's Rijndael
Date: Wed, 04 Oct 2000 12:34:40 GMT
On Wed, 4 Oct 2000 10:29:57 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote, in
part:
>John Savard <[EMAIL PROTECTED]> gets quoted as saying:
>: It *helps* if the computers of the world all use the U.S. designed
>: Microsoft Windows operating system [...]
>This is "helps" in the sense of "hinders", I presume ;-)
It "helps" one in the goal of hindering non-U.S. persons from writing
encryption software. (As was, of course, evident from the context.)
So it is not necessarily "a new meaning of the word" 'help' "of which"
you "had not previously been aware".
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: alt.security.scramdisk
Subject: Re: Advanced Encryption Standard - winner is Rijndael
Date: Wed, 04 Oct 2000 12:30:32 GMT
On Tue, 03 Oct 2000 22:12:10 -0700, David Schwartz
<[EMAIL PROTECTED]> wrote, in part:
> The English language does not provide a good way to make statements
>without making implications. But the implied claims are merely implied,
>and you can't treat them the same way. If the NSA says "all the AES
>candidates are suitable for level 3" that's what it means. Does it mean
>they're unsuitable for level 2? No. Does it mean any of them _are_
>suitable for level 2? No. It means they're all suitable for their
>intended purpose. No more. No less.
This relates to a point I was making about the NSA's only statement
about the security of the AES algorithms.
It said that it had "no objection to any of the finalists from the
standpoint of security". That tortured wording failed to imply a great
deal: it was, for example, consistent with the hypothesis that the NSA
was happy with all the finalists because it could break all of them.
NIST has been more talkative. It noted that the "security margin" of
Rijndael was lower than that of some other algorithms, in the sense
that reduced-round variants of Rijndael were broken with
proportionately less reduction in rounds than some other candidates.
It also noted that, since all five finalists had satisfactory
security, the specific choice of Rijndael was due to the fact that its
speed was the highest, and its memory requirements were the lowest.
If a construction material is specified as being satisfactory to a
temperature of 0, that does not imply that it is not suitable to -30.
But if I need it to be satisfactory to -30, then I should choose
something specified for -30. Also, if the specific construction
material was not only specified to 0 degrees, but was obtained from
the *lowest bidder* for supplying something to meet that spec, I would
say the chances of it also working at -30 are ... diminished.
As the "standard", the AES is going to be used to protect medical
records, for example. It's *going* to be used, therefore, for jobs
that _require_ the same effective lifespan as ciphers protecting TOP
SECRET, rather than SBU, material. So, if there is reason to be
concerned that it may not be suitable for such an application, that is
not an irrelevancy, but a genuine problem.
Also, while the AES process has been lengthy, and there is a law of
diminishing returns, since cryptanalytic results against Rijndael have
improved over time - the latest coming from Counterpane Labs less than
a week before the final decision - is it not prudent to at least
consider the possibility of further improvements in attacks on it,
particularly now that, as the standard, much more attention will be
concentrated on it?
Since none of 9, 11, or 13 is a multiple of either 4, 6, or 8,
Rijndael is somewhat like a Feistel cipher with an odd number of
rounds, and this, at least in the case of DES, has aided attacks. The
thoroughness of the Mix Column step, or the in-line nature of the Byte
Sub step may mean this is not a weakness in Rijndael, but I think I'll
give people like Eli Biham and David Wagner another year to work on it
before having any measure of confidence.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Rijndael cracked by Biham!
Date: Wed, 04 Oct 2000 12:36:16 GMT
On Wed, 04 Oct 2000 10:44:22 GMT, [EMAIL PROTECTED] wrote, in part:
>The article on :
>http://sectedesax.ctw.cc
And to think I had a hand in helping to set people up to be decieved
by the title of your post.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Requirements of AES
Reply-To: [EMAIL PROTECTED]
Date: Wed, 4 Oct 2000 12:35:26 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote:
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : 1, Security
:> : 2, Versatility
:> : 3, Security
:>
:> : I fail to see how Serpent or Twofish failed to beat Rijndael with
:> : those restrictions. [...]
:>
:> From the conclusion of the AES report, this is how:
: Perhaps I should rewrite the question in a form you can understand.
: Why wasn't Serpent or Twofish picked?
That was the summary of the conclusion of the AES report, explaining why
they chose Rijndael. Necessarily the choice of Rijndael excluded the
other candidates.
``NIST selected Rijndael as the proposed AES algorithm at the
end of a very long and complex evaluation process.''
The details of the evaluation process are discussed in some depth
in the report I referenced:
http://csrc.nist.gov/encryption/aes/round2/r2report.pdf
If you want to know the exact reasons why Serpent or Twofish were not
picked, looking at that document is probably the best thing you can do.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: Rijndael cracked by Biham!
Date: Wed, 04 Oct 2000 20:49:32 +0800
[EMAIL PROTECTED] wrote:
>
> The article on :
>
> http://sectedesax.ctw.cc
>
One word: TROLL.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: SHA C++ Implementation
Date: Wed, 04 Oct 2000 20:54:56 +0800
[EMAIL PROTECTED] wrote:
>
> Hi. I was wanting to know if there is any source
> code for C++ that implements SHA(Secure Hash
> Algorithm), aka SHS(Secure Hash Standard). I have
> found some C implementations, but they do not seem
> to work. Could someone please help? Thanks.
>
What mean you by "do not seem to work"? I used the code from the
ftp.funet.fi archive, and it works just fine, except that it's code
implementing the OLD Secure Hash Algorithm (SHA) as described in FIPS
180, and requires setting a compile time conditional for it to become
FIPS 180-1-compliant. What platform are you testing it on? The C
implementations you've found probably work well enough, only you might
not be using them properly.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
** 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
******************************
