Cryptography-Digest Digest #309, Volume #14 Mon, 7 May 01 12:13:01 EDT
Contents:
Re: A Question Regarding Backdoors (SCOTT19U.ZIP_GUY)
Re: Modification of S-Box attack ("gilles")
Re: Tiny s-boxes (Mok-Kong Shen)
Re: Free Triple DES Source code is needed. (Luis Duarte)
Re: free en/decryption library (Luis Duarte)
Back to the Drawing Board (John Savard)
n-ary Huffman Template Algorithm (Alex Vinokur)
Re: GF(2^W) sboxes timings (Tim Olson)
Re: LUCIFER ("Henrick Hellström")
Re: Cryptanalysis Question: Determing The Algorithm? (Bo Dömstedt)
Re: GF(2^W) sboxes timings (Mark Wooding)
Re: ECC question (Mark Wooding)
Re: SRP attack? (John Myre)
Re: ECC question ("Anthony Mulcahy")
Re: Modification of S-Box attack (Mark Wooding)
Re: Tiny s-boxes (Tim Tyler)
Re: Modification of S-Box attack ("Scott Fluhrer")
ISO 9796-1:1991 (Uwe Guenther)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: A Question Regarding Backdoors
Date: 7 May 2001 12:03:49 GMT
[EMAIL PROTECTED] (Trevor L. Jackson, III) wrote in
<[EMAIL PROTECTED]>:
>Consider the variation suggested by RW: non-backdoored crypto is
>outlawed. Such a draconian restriction would present the choice of
>crippled crypto or jail to anyone promoting (in the vague DCMA sense)
>non-bacdoored crypto. In that situation any professional with integrity
>should visit jail in the tradition of Thoreau, Parks, & Zimmerman.
>
A professional with integrity isn't that kind of an oxymoron.
A person is usually considered a profession if he sells out.
If a personhas integrity they don't sell out.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: "gilles" <[EMAIL PROTECTED]>
Subject: Re: Modification of S-Box attack
Date: Mon, 7 May 2001 14:12:08 +0200
if you compress the file with
UPX the attack is most difficult
not ??
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: Mon, 07 May 2001 14:34:20 +0200
Tim Tyler wrote:
>
> I've recently become interested in the use of tiny s-boxes again.
>
> This post is mainly intended to stimulate some discussion on the matter.
>
> I have the impression that it is generally thought that large s-boxes are
> best.
>
> Since "Gordon, J. and H. Retkin's "Are Big S-Boxes Best?" in 1982, there
> have been numerous studies of the properties of large s-boxes, most of
> them showing that fraction of good s-boxes, with regard to defending
> against linear and differential cryptanalysis, increases dramatically
> with s-box size - and consequently, choosing an s-box at random becomes
> increasingly safe as the size of the box grows.
>
> However, large, random s-boxes are expensive to implement - with an nxn
> box effectively requiring a LUT of n * 2^n bits in size. This means that
> while a 4x4 s-box needs a 64-bit LUT, an 8x8 s-box needs a 2048 bit LUT.
[snip]
For larger S-boxes, more severe size requirement results.
I guess that a certain optimum in substitution effects
could be reached by choosing some moderately large size of
S-boxes and generating a sufficient number of these
(pseudo-)randomly and using them (pseudo-)randomly.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Luis Duarte)
Subject: Re: Free Triple DES Source code is needed.
Date: Mon, 07 May 2001 11:53:44 GMT
ok, ok...
mr. know-it-all
you really think you're the owner of this newsgroup...
shame on you...
On Thu, 03 May 2001 23:11:00 GMT, "Tom St Denis"
<[EMAIL PROTECTED]> wrote:
>
>Second what is this C/C++ thing you talk about? It's C *OR* C++ not both.
>That's like saying I eat apple-pears instead "i eat apples and/or pears".
>The combo is non-existant.
>
------------------------------
From: [EMAIL PROTECTED] (Luis Duarte)
Subject: Re: free en/decryption library
Date: Mon, 07 May 2001 11:55:55 GMT
In case you didn't notice, Jack was just kidding...
On Sun, 06 May 2001 19:48:20 GMT, "Tom St Denis"
<[EMAIL PROTECTED]> wrote:
>
>"Jack Lindso" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> I think it's very noble of you Tom to volunteer for the job of this
>> newsgroup's guard.
>> Cheers.
>
>I do what I can :-)
>
>Tom
>
>
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Back to the Drawing Board
Date: Mon, 07 May 2001 13:34:11 GMT
After not having added a new cipher to the Quadibloc family, it
happened that I chanced to investigate how many characters could be
represented by a 5 out of 10 code.
It turned out the answer was 252.
This gave me the idea of dividing a 128-bit block into a 48-bit part
and an 80-bit part, and using 8-bit bytes from the 48-bit part to
select entries from an S-box containing 5 out of 10 code values (with
four duplicates, randomly chosen) to perform ICE-type swaps in the
encryption performed on the 80-bit part.
However, I then thought this wouldn't work so well, so I decided I
needed to double the block size.
OK, 96 bytes: this lets me have three 32-bit parts, so I could use the
traditional Quadibloc f-function there, and the f-function of one part
would control nonlinearly a pair of Feistel rounds involving the other
two. The sort of structure I tried for in Quadibloc II, but had to
compromise because I had four parts instead of three.
The other 160 bytes would be manipulated as groups of 10 bits. Hmm,
sixteen of them. This gives me the chance to try something inspired by
Rijndael, instead of a Feistel structure.
My idea of doing a Rijndael-like cipher would be to combine ideas from
Rijndael and Square. Do a Mix Column step, followed by a Mix Row step,
then Shift Diagonals by different amounts.
Mix Column would use a SAFER-like structure of ICE-type swaps preceded
and followed by substitutions in a key-dependent bijective S-box with
1024 entries, while Mix Row would be like Rijndael's Mix Column, but
over GF(2^10).
The Shift Diagonal step would correspond to swap halves in DES, and
would also include an exchange of bits with the 96-bit part. I figured
it would work this way: a 10-bit unit chosen to interact with one of
the twelve bytes of the 96-bit part would send eight bits out, retain
the two LSBs, but move them to the MSB positions, and then take eight
bits in.
Then I realized that to ensure that every bit went through each part
of the cipher an equal number of times, the number of rounds would
have to be:
- a multiple of three, because of how the 96-bit part is enciphered
- a multiple of four, because of how the 160-bit part works, and
- a multiple of five, because of the way bits are exchanged between
the two.
*Sixty* rounds, each round really being more like _two_ rounds in a
more typical cipher? While I do want to illustrate what the ciphers of
the future, when computers are more powerful, might look like, this
seems to be something that might be regarded as rather excessive.
(Naturally, the boomerang attack implies that the real number of
rounds actually ought to be four times as great...)
John Savard
http://home.ecn.ab.ca/~jsavard/
------------------------------
From: Alex Vinokur <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.image.processing,comp.graphics.algorithms
Subject: n-ary Huffman Template Algorithm
Date: Mon, 07 May 2001 16:35:02 +0200
i,
1. Page containing description of 'n-ary Huffman Template Algorithm'
has moved.
Reason: Server HomePage.com which held the page has shut down.
2. New URL-address of the 'n-ary Huffman Template Algorithm' page is :
----------------------------------
http://visitweb.com/alexvn.huffman
http://www.bigfoot.com/~alexvn/huffman_template_algorithm.html
----------------------------------
Note. Both URL-addresses above are aliases to the same actual address.
Regards,
=====================
Alex Vinokur
mailto:[EMAIL PROTECTED]
mailto:[EMAIL PROTECTED]
http://go.to/alexv_math
=====================
------------------------------
From: [EMAIL PROTECTED] (Tim Olson)
Subject: Re: GF(2^W) sboxes timings
Date: Mon, 07 May 2001 08:44:30 -0500
In article <6QfJ6.29036$[EMAIL PROTECTED]>, "Tom St
Denis" <[EMAIL PROTECTED]> wrote:
| /* Perform a multiplication in GF(2^32) returning ab */
| unsigned long gf_mul(unsigned long a, unsigned long b)
| {
| unsigned long result = 0;
| while (a) {
| if (a & 1)
| result ^= b;
| a >>= 1;
| if (b & 0x80000000ul)
| b = (b << 1) ^ 0xd59c382dul;
| else
| b <<= 1;
On deeply-pipelined processors like Athlon and Pentium-III, the
if-then-else tests in the middle of the loop are going to cause a lot of
branch mispredictions with large mispredict penalties. You might be able
to speed up the loop quite a bit if you do the following trick to get rid
of the conditional branches:
unsigned long gf_mul(unsigned long a, unsigned long b)
{
unsigned long result = 0;
long signB, lsbA;
while (a) {
lsbA = ((long)a << 31) >> 31;
result ^= (b & lsbA);
a >>= 1;
signB = (long)b >> 31;
b = (b << 1) ^ (0xd59c382dul & signB);
}
}
--
-- Tim Olson
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: LUCIFER
Date: Mon, 7 May 2001 15:56:26 +0200
"Henrick Hellström" <[EMAIL PROTECTED]> skrev i meddelandet
news:9d5kk4$6e7$[EMAIL PROTECTED]...
[snip]
> You cannot combine this property
> with the first if there is only a single cycle, but you could obtain both
> properties with 8 disjoint cycles.
That would be 4 disjoint cycles, of course. I must have thought of bytes
instead of nibbles.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: [EMAIL PROTECTED] (Bo Dömstedt)
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Reply-To: [EMAIL PROTECTED]
Date: Mon, 07 May 2001 13:57:23 GMT
> Bo Dömstedt" wrote:
> > ... What you can do is to sequentially test different assumptions,
Douglas Gwyn wrote:
> If you have a whole team, they can test various possibilities in
> parallel, and when one of them succeeds in making a definite break
> into the system, the rest of the team can be retasked.
Sorry, "sequentially" is humoristic. If you have a function
with N bit input and N bit output, you may (in principle) implement
that function with a table with 2^N rows, and store an N bit number
on each row. Then there could be 2^( N*( 2^N)) different
such functions.
If you use an N-bit bit transposition, then there are N!=
=N*(N-1)*(N-2)*...*2*1different possible transposition functions.
The problem for the cryptanalyst is that efficient cryptanalysis
methods directly exploit some structure in the target cipher.
For an unknown cipher, these methods do not apply.
The problem for the cryptographer, is to prevent the structure
of the cipher to become known, if a cipher machine would fall
into the hands of the enemy (Kerckhoffs principle). This may
be accomplished using both cryptographic and implementation
techniques and methods.
Is it more clear now ?
Bo Dömstedt
Chief Cryptographer
Protego Information AB
Ideon Gamma Science Park
http://www.protego.se
Visit us 10-11 May:
http://www.ideon.se/ideondagarna
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: GF(2^W) sboxes timings
Date: 7 May 2001 14:59:45 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> Well reduction is just xor in this field... I never thought of using the
> luts though...
My point is that, if your polynomial is, say, a trinomial, you can reduce a
multiplication or square result in about three XORs. At the moment, you
require something like 16 XORs per multiply or square, just for the
reduction.
Let's think how this is working in the polynomial ring F_2[x] for a bit.
Let's say that you have an irreducible trinomial p(x) = x^d + x^y + 1 of
degree d. Suppose we're given a polynomial f(x) = g(x) + x^d h(x) of
degree d' > d (where g(x) has degree less than d). Clearly finding g(x)
and h(x) is trivial. Then
f(x) = g(x) + h(x) + x^y h(x) (mod p(x))
is a congruent polynomial with degree d' - d + y
Warning to people wanting to put this kind of thing in a cipher: watch
for interpolation attacks.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: ECC question
Date: 7 May 2001 15:03:00 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> Would something like nP - kP (say k=n) be the point at infinity?
Yes, iff k and n are congruent modulo the order of P.
-- [mdw]
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: SRP attack?
Date: Mon, 07 May 2001 08:58:12 -0600
David Wagner wrote:
>
> Michael Scott wrote:
> >In fact a masquerading server, Stevie, can eliminate two candidate passwords
> >P1 and P2 at once.
<snip>
> Anyway, I don't view it as a problem: The main reason to use a
> protocol like SRP is to force a would-be password-guesser to go
> online, so that you can rig the server with a mechanism that locks
> out the attacker after too many failed attempts to log in.
<snip>
Note that the attacker is masquerading as the server, so the
threshold that counts is the client's. Normally the client
software would make one attempt per human interaction, which
would of course effectively limit the client's retries. It
does show that the client software should not make a lot of
retries of the protocol automatically - a sensible precaution
regardless.
JM
------------------------------
From: "Anthony Mulcahy" <[EMAIL PROTECTED]>
Subject: Re: ECC question
Date: Mon, 7 May 2001 23:52:30 +0900
"Tom St Denis" <[EMAIL PROTECTED]> wrote
> I was just wondering about subtracting two points...
>
> Let's say you have the points P=(x1,y1) and Q=(x2,y2). If you wanted P-Q
> would you simply do P+(-Q) where -Q is (x2,-y2)?
P + (-Q) is the correct way of writing it, because subtraction is defined as
adding the inverse, however the formula -Q = (x2, -y2) is only for elliptic
curves over rational numbers.
ECC uses curves over finite fields and the general formula for that case is:
-Q = (x, -y-a1x-a3)
where Q = (x, y) and the equation of the curve is
y^2 + a1xy + a3y = x^3 + a2x^2 + a4x + a6
Since the curves used in ECC are usually of the form
y^2 = x^3 + a4x + a6 (over Fp) or
y^2 + xy = x^3 + a2x^2 + a6 (over F2m)
the equation for -Q reduces to:
-Q = (x, -y-x) = (x, y+x)
> Would something like nP - kP (say k=n) be the point at infinity?
> Basically I am toying with the idea of an attack based on guessing
> the multiplicand and subtracting. It's nothing serious just toying with
> the math.
nP - kP would be equal to the point at infinity if (n-k) is congruent to 0
modulo the order of the group of points on the curve (or the order(s) of the
subgroup(s) containing P). Basically, nP - kP is equal to the point at
infinity, if (n-k) is a multiple of the number of points on the curve.
> Too much to learn, so little time.... hehehehe
Be careful, elliptic curves are very addictive and the more you learn about
them, the more you will want to learn, in a never ending cycle.
Anthony Mulcahy
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Modification of S-Box attack
Date: 7 May 2001 15:17:04 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
> Because DES's s-box are so small, 6x4, a small change to their structure
> (say the swapping of two elements of the box) has massive implications to
> the effectiveness of differential and linear cryptanalysis. Thus, I propose
> an aggressive attack (which in practice would probably be delivered by
> Virus) where one actually swaps two of the elements in the one or more of
> the DES s-boxes, in a compiled implementation.
This reminds me of `Deletion Cryptanalysis', by Lars Knudsen and Fauzan
Mirza (Journal of Craptology, 1998).
-- [mdw]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Reply-To: [EMAIL PROTECTED]
Date: Mon, 7 May 2001 15:32:22 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
: Of course the next question is, can we make an algebraic 64x64 s-box that
: behaves as a random premutation and can not be 'decomposed' into small
: s-boxes to be analysed?
Not very easily ;-)
As I mentioned, IDEA has a sort-of 16x16 bit algebraic s-box (which is
/quite/ large in my book) - but it iteratively combines it with other
operations in an attempt to prevent direct attacks on its regularities.
As you noted, the art of making huge random s-boxes practically *is* the
art of making block cyphers; and it seems that there, very frequently,
a number of smaller s-boxes are involved.
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Modification of S-Box attack
Date: Mon, 7 May 2001 08:31:14 -0700
Simon Johnson <[EMAIL PROTECTED]> wrote in message
news:9d60o4$hsb$[EMAIL PROTECTED]...
> A lot of people use DES and/or its variants... I've not actually checked
if
> this would work.. but in theory it should work perfectly.
>
> Because DES's s-box are so small, 6x4, a small change to their structure
> (say the swapping of two elements of the box) has massive implications to
> the effectiveness of differential and linear cryptanalysis. Thus, I
propose
> an aggressive attack (which in practice would probably be delivered by
> Virus) where one actually swaps two of the elements in the one or more of
> the DES s-boxes, in a compiled implementation.
The problem with this attack is if the attacker tweaks Alice's s-boxes, then
Bob (who is using standard DES) can't read Alice's messages, and once they
notice that, Alice will fix the program.
Once you get a virus onto Alice's computer, there are several better ways of
attack, such as:
- Reducing Alice's random-number-generator to something that can be brute
forced.
- Stealing Alice's keys, and emailing them to somewhere the attacker can get
at (but also something that won't point at the attacker, unless he doesn't
care if he gets caught).
- Stealing the plaintext, and emailing that.
I claim that these sorts of attacks are better (from the attacker's
perspective), in that they're likely to be undetected for long periods of
time.
--
poncho
------------------------------
From: Uwe Guenther <[EMAIL PROTECTED]>
Subject: ISO 9796-1:1991
Date: Mon, 07 May 2001 16:40:18 +0200
Hello,
I have to implement an client that uses german HBCI-Protocol
(HomeBankingComputerInterface). There are references to
the ISO 9796-1:1991(formating and signing). Since this standard
are withdrawn, there is no way to get the standard from ISO.
Has some one any ideas where I can get the withdrawn ISO standard.
I know that there some security problems with the use of the standard.
But there is now other way to implement HBCI.
--
Uwe
mailto:uwe_at_cscc_dot_de
------------------------------
** 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
******************************
