Cryptography-Digest Digest #12, Volume #12 Mon, 12 Jun 00 19:13:00 EDT
Contents:
Re: AES attacks (was: How does DES work?) (John Myre)
Re: Q: Using two DES modules (Bryan Olson)
Re: Matsui Style Sboxes (tomstd)
Re: Encoding 56 bit data ---HELP--- ("Kasper Pedersen")
More papers online (tomstd)
Re: Homophones (Mok-Kong Shen)
Re: randomness tests (Mok-Kong Shen)
Re: encoding of passwords (Mok-Kong Shen)
Re: Enigma Variations (John Spicer)
Re: help for rc5 cryptanalysis (Anton Stiglic)
Re: Secret Spliting - Theshold shemes. (Bryan Olson)
Re: matrix question ("Matt Timmermans")
Re: a couple of qutions on 3DES (Albert P. Belle Isle)
Re: Q: Using two DES modules (Mok-Kong Shen)
Re: help for rc5 cryptanalysis (James Felling)
Re: Multiple encryptions (AllanW)
Re: Random sboxes... real info (Rex Stewart)
Re: More papers online ("Joseph Ashwood")
Session key transmission (Mok-Kong Shen)
Re: More papers online (tomstd)
----------------------------------------------------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: AES attacks (was: How does DES work?)
Date: Mon, 12 Jun 2000 14:06:36 -0600
Joseph Ashwood wrote:
<snip>
> Every AES finalist has been shown to have
> extremely minor weaknesses against something...
<snip>
> I find it encouraging that the attacks are so close to the
> difficulty of a brute force search.
I think this is somewhat misleading. Most of the published
attacks on the AES finalists are on reduced versions. Actually,
I can't recall *any* attacks better than brute force on any of
the AES finalists with 128 bit keys.
Corrections or clarifications, anyone?
John M
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Q: Using two DES modules
Date: Mon, 12 Jun 2000 20:24:57 GMT
Mok-Kong Shen wrote:
>
> Given two two DES modules and two keys, which of the following
> schemes is to be preferred, (a) in ECB and (b) in CFB?
>
> 1. Superencipherment (2DES).
>
> 2. Use one DES in full OFB for preprocessing the plaintext
> with xor before input to the other DES.
>
> 3. Use one DES in full OFB to generate keys for the other
> DES.
One and two are currently intractable (no one can afford the
space for the time-space tradeoff).
Three is breakable.
What's the point?
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: Matsui Style Sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 13:29:46 -0700
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
>What about using sboxes of the same stye in GF(p^n) where p !=
2?
>
>For example using multiplicative inversion in GF(4^2) would get
>you a 8x8 sbox. I will try to modify some exisiting code todo
>this...
>
>any insight though?
Hehehe, after failing to create primitive polynomials in GF
(16^n) (obviously because their can't be inverses for the
coefficients modulo a composite) I think I know hy 2 was chosen
for the coefficients...
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Kasper Pedersen" <[EMAIL PROTECTED]>
Subject: Re: Encoding 56 bit data ---HELP---
Date: Mon, 12 Jun 2000 20:43:01 GMT
"tomstd" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> It shouldn't. There are (2^64)! possible ways to permute 64-bit
> blocks... that is way more then 2^64, 2^128 or even 2^256...
>
> Tom
Yeah.. About a year ago I calculated (2^32)!, and it's indeed a totally
unrealistic number of mappings.
It's so many bits that I don't remember. Something like 130*10^9 bits.
(2^64)! is something close to 2^(10^(10^21)).
Note that just expanding (10^(10^21)) yields a 3.3*10^21 bit long number.
And we haven't even done the 2^n part..
very big number.
That huge number is the number of sets required to describe a
transformation. Or, a cipher using that as a key could emulate any
64-bit-block cipher.
So yes, the perfect cipher can use all the key bits you are able to throw at
it.
It all depends on how many times you use the same key.
/Kaper
------------------------------
Subject: More papers online
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 14:04:17 -0700
I added a few more papers (not my own papers) to the website...
you can find them at
http://tomstdenis.com/crypto/
A while back I found a nice site that had a list of all
published crypto-authors and their papers. It was all on one
webpage... really impressive work. Of course I lost the link :-(
If anyone has a good easy to access collection of papers please
post the links :-)
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Homophones
Date: Mon, 12 Jun 2000 23:19:15 +0200
Mack wrote:
> Actually this is an excellent technique. Even if the
> Potential mappings are known but they are chosen
> using a method that appears random (ie. a random
> number generator of some kind [secure])
> this equates to adding some additional bits to the
> key. Since most modern methods depend on
> differential attack this complicates the attack
> by at least a factor of 3 (70/256>3).
> Furthermore since the mappings are known
> no additional material need be transmitted.
>
> Unfortunately it adds extraneous data to the content
> increasing its length.
>
> Another method that would be just as effective is
> compressing the data then adding a random byte
> per block of data at regular intervals (irregular intervals?)
>
> The method of creating the random bytes does
> not need to be known by the receiver only their
> location.
My position is a little bit different from yours. I mean a normal
text file in ASCII is stored with one byte pro character anyway.
But most of the 8-bit space is not used, in which case one can
use homophones to improve the utilization without increasing the
number of bytes. Compression is a (alternative) technique that
attempts to achieve the same goal (enhancing efficiency of
encryption) in a different manner with the advanatage (among
others) of reducing the transmission volume in most cases.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: randomness tests
Date: Mon, 12 Jun 2000 23:19:27 +0200
tomstd wrote:
> Bingo, right on the button. As well as other non-trivial
> contrived tests. For example LFG's will fail the birthday
> spacing test but a BBS won't. Both are PRNG's, both can be
> usefull (depending on context). But since the LFG fails the BST
> does that mean it's useless?
>
> That's like saying your new car is useless because it can't do 0-
> 60 in 0.4 seconds... You don't need that "feature" so it doesn't
> hamper the appeal. Similarly you may not need
> statistically "random" numbers that pass the BST.
I was wrongly interpreting your previous statement to mean
that you could devise statistical tests to show that a given PRNG
fails these (particularly designed) tests (I vaguely remember
that someone else previously made a similar statement)
and hence was curious enough to learn how it could be done.
That the usefulness of a nontrivial computing algorithm depends
on the application is certainly true. I agree fully with you in that.
(It may however be of interest to note that not everyone seems
to be that 'liberal'. Elsewhere, for example, I read catgegorical
claims that DES is useless because it has been bruteforced.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: encoding of passwords
Date: Mon, 12 Jun 2000 23:19:22 +0200
Mark Wooding wrote:
> You're right: the Unix DES crypt(3) function doesn't use `standard' DES.
> The salt is a 12-bit number, which is used to define a bit permutation
> applied immediately after the standard expansion permutation E in the
> DES round function. Each salt bit is associated with two bits from the
> 48-bit output of E: if the salt bit is set then the bits are swapped.
2*12=24. So I suppose that 24 remaining bits are unaffected by
the salt. Is that right? Is there any literature on the effect of this
modification of the standard DES in respect of its strength? Thanks.
M. K. Shen
------------------------------
Date: Mon, 12 Jun 2000 09:07:05 +0100
From: John Spicer <[EMAIL PROTECTED]>
Subject: Re: Enigma Variations
That probably explains it! I have read through the paperback version of
"The Codebreakers", which I agree didn't seem to say much about this
area. I'll have to try to get hold of the HB version.
John
Paul Koning wrote:
> Jim wrote:
> > ...
> > Read Kahn, 'The Codebreakers' the non-abridged version if possible,
>
> I would put it more strongly. The paperback version is
> utterly worthless. I once made the mistake of buying it,
> and actually threw it into the trash -- which is a very
> rare event indeed for a bookworm like me.
>
> paul
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: help for rc5 cryptanalysis
Date: Mon, 12 Jun 2000 17:18:49 -0400
James Felling wrote:
>
> Just a note in addition not all key/plaintext pairs produce a valid "Encrypted
> plaintext" with 8-rounds of non- rotated RC5.
>
> E.g. All S's are 0. then All plaintexets encode to 0.
Looks like you forgot the first step of the encryption algorithm, that
is
A = A + S[0];
B = B + S[1];
( + is addition mod 2^32)
In fact, with 8 round RC5 with no rotations, defining the S[i]s to be
all
0s and say that the plaintext blocks are (a, b), you will in fact get
the
cipherblocks (b, a^b).
In fact, you can see the result by going trough the algo like this
(r = 0) A = a;
B = b;
r = 1: A = a^b
B = b^(a^b) = a
r = 2: A = a^b^a = b
B = a^b
r = 3: A = b^a^b = a
B = a^b^a = b
step 3 is in fact similar to what you get at "step 0", so you can see
that step 8 will be similar to step 2, and thus the result.
Anton
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Secret Spliting - Theshold shemes.
Date: Mon, 12 Jun 2000 21:08:38 GMT
Simon Johnson wrote:
> Just to insure you know what i'm talking about, i'll include the
> description of the threshold sheme i am refering to:
>
> To split message C, amoung x users such that n shadows can recover the
> message do the following:
>
> 1.) Choose a number greater than C (a prime would be optimal) for the
> mod, p.
The polynomial method requires a field over which to define
the polynomial, so a composite doesn't work at all. I find
it more convenient to work in a smaller field and break the
secret into pieces. GF(2^8) is good.
> 2.) Choose random coeffients for the following equation
>
> t = ax^n-1 + bx^n-2 ......... + c mod p
>
> 3.) increment X and calculate t to generate the shadows.
It goes without saying (but I'll say it) that of course
you don't give anyone f(0). I don't like using x as the
both polynomial parameter and the number of users. Most
references will refer to an "m of n" scheme.
> Now my question is this: Is there a quick way to recreate the equation
> using a the correct number of shadows?
>
> My method use simple sequence finding techiques:
I didn't study your method well enough to comment on it. You
can reconstruct the polynomial using Lagrange's
interpolation formula in O(m^2) time, where m is the number
of shares to reconstruct the secret. The direct application
of Lagrange's formula comes out O(m^3), which is fine up to
m=several.
The time to multiply usually increases as the square of the
size of a field element. Chopping up the secret and using a
smaller field is therefore faster.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: matrix question
Date: Mon, 12 Jun 2000 17:04:45 -0400
Benjamin Goldberg wrote in message <[EMAIL PROTECTED]>...
> [...]
> /* out = in1 x in2, with dimensions [a x c] = [a x b] x [b x c] */
> [...]
> out[ out_a*a + out_c ] = out_ac;
column out_a, row out_c is out[out_a*c + out_c], because each of the a rows
has c items.
You did this everywhere, but when your matrices were square, c == a, so the
problem didn't show.
------------------------------
From: Albert P. Belle Isle <[EMAIL PROTECTED]>
Subject: Re: a couple of qutions on 3DES
Date: Mon, 12 Jun 2000 17:51:49 -0400
Reply-To: [EMAIL PROTECTED]
On Mon, 12 Jun 2000 16:17:49 GMT, dexMilano <[EMAIL PROTECTED]>
wrote:
>Do you know if there are some constrains among 3 keys for use them into
>3des?
>
If you are using EDE you should ensure that the middle 8 bytes are not
identical to either (or especially both) of the first 8 bytes or the
last 8 bytes.
We also check to see if any of these single-DES keys is one of the 4
weak keys or 12 semi-weak keys specified in FIPS Pub 74.
This slightly reduces the size of the keyspace (by a trivial amount)
but is useful in catching some kinds of spiking.
Albert P. BELLE ISLE
Cerberus Systems, Inc.
================================================
ENCRYPTION SOFTWARE with
Forensic Software Countermeasures
http://www.CerberusSystems.com
================================================
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Using two DES modules
Date: Tue, 13 Jun 2000 00:04:11 +0200
Bryan Olson schrieb:
> Mok-Kong Shen wrote:
> >
> > Given two two DES modules and two keys, which of the following
> > schemes is to be preferred, (a) in ECB and (b) in CFB?
> >
> > 1. Superencipherment (2DES).
> >
> > 2. Use one DES in full OFB for preprocessing the plaintext
> > with xor before input to the other DES.
> >
> > 3. Use one DES in full OFB to generate keys for the other
> > DES.
>
> One and two are currently intractable (no one can afford the
> space for the time-space tradeoff).
>
> Three is breakable.
>
> What's the point?
To find out whether using two DES modules would be sufficient in
place of three DES modules as in 3DES and hope that the same
result could be transferred to other block ciphers.
I am not sure of having understood the meaining of your term
'breakable' in the present context.. Does your 'currently intractable'
mean 'unbreakable' or does it mean 'breakable', or is it something
inbetween? Could you substantiate your claim of difference between
(1) and (2) on the one side and (3) on the other side? Many thanks
in advance.
M. K. Shen
>
> --Bryan
> --
> email: bolson at certicom dot com
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: help for rc5 cryptanalysis
Date: Mon, 12 Jun 2000 16:53:36 -0500
Nope. I made an even more bizzare error. I applied the operations simultaneously
--
I did round 0, but when round 1 rolled around, I got (assume all S(i)=0)
A=(a^b ), B=(a^b), then round2
A=(a^b)^(a^b) =B=0
I knew I had a different impression the first time I went through this, but I could
not for the life of me remember WHY.
Thanks for the help.(AArgh! must get more sleep before analysis.)
Anton Stiglic wrote:
> James Felling wrote:
> >
> > Just a note in addition not all key/plaintext pairs produce a valid "Encrypted
> > plaintext" with 8-rounds of non- rotated RC5.
> >
> > E.g. All S's are 0. then All plaintexets encode to 0.
>
> Looks like you forgot the first step of the encryption algorithm, that
> is
> A = A + S[0];
> B = B + S[1];
>
> ( + is addition mod 2^32)
> In fact, with 8 round RC5 with no rotations, defining the S[i]s to be
> all
> 0s and say that the plaintext blocks are (a, b), you will in fact get
> the
> cipherblocks (b, a^b).
>
> In fact, you can see the result by going trough the algo like this
> (r = 0) A = a;
> B = b;
> r = 1: A = a^b
> B = b^(a^b) = a
> r = 2: A = a^b^a = b
> B = a^b
> r = 3: A = b^a^b = a
> B = a^b^a = b
> step 3 is in fact similar to what you get at "step 0", so you can see
> that step 8 will be similar to step 2, and thus the result.
>
> Anton
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: Multiple encryptions
Date: Mon, 12 Jun 2000 22:07:45 GMT
Thank you all for your responses.
I think that the general consensus is that E o D is OFTEN
more secure than either E or D, other than degenerate cases.
But there's a sense that we don't know how much more secure
it is, and some concern that if we've stumbled across one of
the degenerate cases we might not realize it. So we need to
spend effort ensuring that D and E use algorithms that aren't
related to each other. Using D=E, even with different keys,
is a Bad Thing(tm). Using one symmetric key algorithm with
one asymmetric key algorithm might be enough to ensure
success, although of course nobody's making any promises.
Have I got this right?
Thanks again for your feedback.
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: Random sboxes... real info
Date: Mon, 12 Jun 2000 22:29:26 GMT
Writing software to output "good" or "great" S-boxes might be
a good idea. But knowing Tom, he'd only keep the "great" ones
around :-) His standards seem pretty steep.
Now, for the real question. Am I still reading this wrong, or
did your overnight test fail virtually all of the S-boxes on
LP-max and ALL of them on DP-max? If that IS the case, maybe
there SHOULD be some work on an algorythm to output S-boxes that
always pass these tests. (But not until after final exams.)
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
In article <8i301b$8ic$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> tomstd <[EMAIL PROTECTED]> wrote:
> > I.e is my point comming through? Random sboxes are hardly ideal.
>
> Ok Tom -- new assignment. Random S-boxes are bad. So, write some
> software to output "ok" S-boxes. (Save the program to output "good"
and
> "great" sboxes either for yourself, or to sell. :)
>
> :)
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: More papers online
Date: Mon, 12 Jun 2000 15:37:50 -0700
> If anyone has a good easy to access collection of papers please
> post the links :-)
I've found Counterpane's to be very good:
http://www.counterpane.com/biblio/
Joe
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Session key transmission
Date: Tue, 13 Jun 2000 00:58:16 +0200
I have difficulty to fully understand the following from
Schneier's AC, p.33:
With symmetric crpytography, the data encryption key
sits around until it is used. If Eve ever gets her hand
on it, she can decrypt messages encrypted with it. With
the previous protocol [employing public key], the
session key is created when it is needed to encrypt
communications and destroyed when it is no longer needed.
This drastically reduces the risk of compromising the
session key. Of course, the private key is vulnerable
to compromise, but it is at less risk because it is only
used once per communication to encrypt a session key.
Certainly, if the communication partners have no way of
obtaining a shared secret key, then using public key is
a necessity. Suppose, however, they have a secret key. Then
they can use that as a master key to create the session key
when it is needed through encrypting a random number with
an algorithm (the same as used to encrypt the message proper
or a different one) and prefix the random number to the
ciphertext (obtained with the session key). The receiver first
uses the random number to get the session key and then
decrypts the ciphertext. In that way, the risk of the master
key being compromised would be the same as that for the
private key, I suppose. (On the other hand, I can see an
essential advantage of the public key in case n persons need
to communicate with one another, since only n private keys
need be kept secret, while there are n(n-1) secret keys
(n(n-1)/2 different ones) with symmetric cryptography.)
Thanks for you help in advance.
M. K. Shen
------------------------------
Subject: Re: More papers online
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 16:03:57 -0700
In article <eZ$Qk7L1$GA.328@cpmsnbbsa07>, "Joseph Ashwood"
<[EMAIL PROTECTED]> wrote:
>> If anyone has a good easy to access collection of papers
please
>> post the links :-)
>I've found Counterpane's to be very good:
>http://www.counterpane.com/biblio/
> Joe
It is, but that's not the site I was thinking of.
Thanks for posting the link.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
** 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
******************************
