Cryptography-Digest Digest #859, Volume #11 Thu, 25 May 00 13:13:01 EDT
Contents:
AEES-Quadrate ([EMAIL PROTECTED])
Re: RSA/PK Question (DJohn37050)
Re: Yet another block cipher: Storin ([EMAIL PROTECTED])
Re: RSA/PK Question (tomstd)
Re: More on Pi and randomness ("Douglas A. Gwyn")
Re: bamburismus ("Douglas A. Gwyn")
Re: Modulu arithmetic additive stripping? ("Douglas A. Gwyn")
Re: Chosen Plaintext Attack (Baruch Even)
Re: Yet another block cipher: Storin (Mark Wooding)
Re: RSA/PK Question ("Rich Ankney")
Re: RSA/PK Question (DJohn37050)
Re: AES final comment deadline is May 15 (Kenneth Almquist)
Re: RSA/PK Question (tomstd)
Re: pentium timings (Jerry Coffin)
Re: RSA/PK Question (David A Molnar)
list of prime numbers (Daniel)
Re: More on Pi and randomness ("Tony T. Warnock")
Re: list of prime numbers ("Tony T. Warnock")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: AEES-Quadrate
Date: Thu, 25 May 2000 14:00:19 GMT
AEES-Quadrate is 512-bit DES-like block cipher, where
quadrate looking composition of F-functions is used instead
of rounds.
Performance of AEES-Quadrate excluding I/O operations was measured
sending for encryption 410Mb in a loop. It is about 1.2 Mb/sec.
There is followning architecture of F-fubction:
256 byte key length
S-box is multiplication table of a group of the order 65536
9 sub-keys 256 bytes length
EP and P are sub-key dependent
XOR with current sub-key
XOR with left part of input
The Avalanche Effect of AEES-Quadrate.
A desirable property of any encryption algorithm is that a small
change in either the plaintext or the key should produce a
significant change in the ciphertext. Change only one bit in plain
text leads to 51.2% changed bits in cipher text. Change only one
bit of key leads to 48.2% changed bits in cipher text.
Algorithm description and source code can be found
at <www.alex-encryption.de>
Please follow download or view link for 'AEES-Quadrate'.
Best regards.
Alex.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: RSA/PK Question
Date: 25 May 2000 14:23:14 GMT
Large RSA keys are not totally crazy.
By one method of computing difficulty (considering only TIME), a 15K bit RSA
key is appropriate for protecting a 256-bit AES key.
Don Johnson
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Yet another block cipher: Storin
Date: Thu, 25 May 2000 14:22:02 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mark Wooding) wrote:
> [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
> > Also, Storin does not have the secret sboxes. The weak key is easy
to
> > identify in Storin.
>
> I'm not entirely convinced it's a `weak' key. One plaintext is
> unconcealed, although that can happen anyway. You can detect that
it's
> (likely) to have been used with one chosen plaintext, but you can do
> that anyway. It's a bit like saying that the key 04b915ba43feb5b6 is
> weak in Blowfish, because if I encrypt 42fd443059577fa2 with it then I
> get 353882b109ce8f1a.
>
> In any case, I've amended my version of the paper to require a key of
28
> words or less, mainly to fix the situation I described elsewhere of
the
> second round key not depending on the first. I'm not submitting a
> `tweak', because I want to see how well the original actually lasts.
>
> -- [mdw]
>
Mr. Wooding,
Even if the key is 'weak', the weakness is the cipher is slight.
I believe any other text could be detected as well. Since the cipher is
essentially unkeyed, it will be a known bijective transform due to the
fixed matrix. Also, with all the round keys equal, the slide attack
would reveal the last round key.
On to more fertile ground, I cannot see a good way to break even two
rounds without guessing 96 bits. The SP network seems tougher than the
Feistal network in this regard.
The best idea I have had so far is to find collisions for one of the
four output. Since the sbox is known, the possible 96 bit input that
lead to a collision can be calculated. There are about 2^48 per 24 bit
output. By guessing the whitening key and finding a collision, perhaps
the other whitening keys can be calculated.
--Matthew
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: RSA/PK Question
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 25 May 2000 07:32:18 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (DJohn37050) wrote:
>Large RSA keys are not totally crazy.
>By one method of computing difficulty (considering only TIME),
a 15K bit RSA
>key is appropriate for protecting a 256-bit AES key.
>Don Johnson
How did you figure that out?
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: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: More on Pi and randomness
Date: Thu, 25 May 2000 13:49:00 GMT
Jonathan Thornburg wrote:
> Such "probabilistic" is *very* dangerous, because it almost invariably
> neglects correlations between the errors in different variables.
True; one should use such methods only when the quantities being
combined have independent errors, or when one can explicitly
treat any correlation that may exist.
Interval arithmetic has a similar problem in the opposite direction.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: bamburismus
Date: Thu, 25 May 2000 13:54:26 GMT
Mok-Kong Shen wrote:
> I conjecture from the tenor of what you wrote that there is a
> probability that you are free to publish part of your ideas
Unfortunately, it is almost impossible to get research published
if it hasn't "produced results", no matter how interesting the
ideas might be. I have communicated via e-mail with a few people
who were interested in pursuing such work, and actually there was
some progress many years ago by a fellow who seems to have since
vanished.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Modulu arithmetic additive stripping?
Date: Thu, 25 May 2000 13:58:04 GMT
Runu Knips wrote:
> "Douglas A. Gwyn" wrote:
> > That's like a computer programmer not having Knuth's TAOCP.
> Hu ? I don't have one ? Old book, quite big and expensive,
> with a strange and hard to read pseudo assembly language.
Then you have indeed missed the boat, as well as not being
up to date on the current state of TAOCP.
------------------------------
From: Baruch Even <[EMAIL PROTECTED]>
Subject: Re: Chosen Plaintext Attack
Date: Thu, 25 May 2000 12:34:45 +0200
In article <8ghtig$c2b$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> Mark Wooding wrote:
>> David A. Wagner <[EMAIL PROTECTED]> wrote:
>> > This is the point where it is probably best to refer you to Biham and
>> > Shamir's book, Differential Cryptanalysis of the Data Encryption
>> > Standard, which gives all the gory details.
>>
>> This is now out of print (at least, according to Amazon it is). Where
>> could I get a copy from?
> [Snipped]
> I'm sure there must be other "survey"-style introductions to
> differential cryptanalysis on the net, but I can't think of them off the
> top of my head.
One can also read the slides that ELi Biham prepared, they are
available at the web site of a course he delivers this semester
at http://www.cs.technion.ac.il/~cs236606/
The slides are devoid of quite a few details and do not go enough
in depth to understand the material from them but they are pretty
good if you need an introduction or overview. You'll need then to
read a good technical paper to get the actual details. or more likely
think of them yourself as they are usually omitted from most
technical papers.
For linear characteristic details I found the slides and his article
"On Matsui's Linear Cryptanalysis" (and his class lectures) to be
sufficient. Though I do not know how helpfull they are without
being in the lectures themselves.
Baruch
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Yet another block cipher: Storin
Date: 25 May 2000 15:23:06 GMT
[EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
> I believe any other text could be detected as well. Since the cipher is
> essentially unkeyed, it will be a known bijective transform due to the
> fixed matrix. Also, with all the round keys equal, the slide attack
> would reveal the last round key.
The following is pedantry. I'm very grateful for your analysis, and the
behaviour you've noticed is interesting.
However, isn't it true that with *any* fixed and known key, the cipher
becomes a `known bijective transform'? And in this case, the key is
merely guessed (for if we knew the key, we'd not be bothering to
cryptanalyse the cipher). So how is this particular chosen-plaintext
test for a particular key fundamentally different from any other, apart
from the (undeniably interesting) fact that you computed the ciphertext
from the plaintext in your head rather than by running the algorithm?
You're right about the slide. I think my proposal of limiting the key
to 28 words eliminates this effectively. There will still (probably) be
keys which are slidable, but they're not predictable easily.
> On to more fertile ground, I cannot see a good way to break even two
> rounds without guessing 96 bits. The SP network seems tougher than the
> Feistal network in this regard.
I used to be a devotee of the Feistel structure. Something about the
Rijndael structure struck me while I was implementing it, though, and I
think I prefer its layered structure to Feistel networks. Also, the
cryptanalysis of ciphers like DEAL are making me a bit cautious about
the Feistel network in general.
> The best idea I have had so far is to find collisions for one of the
> four output. Since the sbox is known, the possible 96 bit input that
> lead to a collision can be calculated. There are about 2^48 per 24 bit
> output. By guessing the whitening key and finding a collision, perhaps
> the other whitening keys can be calculated.
Hmm, interesting.
I was thinking about differential attacks against the two-round variant.
There's a differential
(0x800000, 0x800000, 0x800000, 0) -> (0, 0, 0x800000, 0)
through the matrix. Applying the linear transform to that gives
(0, 0, 0x800000, 0) -> (0, 0, 0x800800)
We push this through the matrix again, and end up with the truncated
differential
(0, 0, 0x800800, 0) -> (0x???000, 0x???800, 0x???800, 0x???800)
again with probabliity 1. The following linear transform can be
commuted with the postwhitening by applying a trivial reversible
transformation to the postwhitening keys; by doing this, we can push our
characteristic all the way through both rounds and the post-whitening,
giving us, finally, a two round truncated differential
(0x800000, 0x800000, 0x800000, 0) ->
(0x???000, 0x???800, 0x???800, 0x???800)
with probablity 1. This is stubbornly non-iterative.
(This just restates the analysis I did to ascertain the cipher's
avalanche effect in terms of differential characteristics.)
I can't extend my characteristic to three rounds -- the linear
transformation between rounds 2 and 3 can no longer be elided and the
matrix multiplication in round 3 splurges everything everywhere.
-- [mdw]
------------------------------
From: "Rich Ankney" <[EMAIL PROTECTED]>
Subject: Re: RSA/PK Question
Date: Thu, 25 May 2000 11:54:22 -0400
This would probably be "Selecting Cryptographic Key Sizes" by
Lenstra and Verheul, on www.cryptosavvy.com . Bob Silverman
has a paper on alternative ways to do this (considering both TIME
and SPACE), in the RSA Labs area of www.rsasecurity.com .
/ Rich
tomstd wrote in message <[EMAIL PROTECTED]>...
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] (DJohn37050) wrote:
>>Large RSA keys are not totally crazy.
>>By one method of computing difficulty (considering only TIME),
>a 15K bit RSA
>>key is appropriate for protecting a 256-bit AES key.
>>Don Johnson
>
>How did you figure that out?
>
>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: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: RSA/PK Question
Date: 25 May 2000 15:45:22 GMT
Note that the original TIME sizes were from the DSA-2 draft (with longer key
sizes). Recall DLP is considered harder than IFP. The comparable key lenghs
chart (under TIME) can be found in my "Future Resiliency" paper at
www.certicom.com in the white papers section.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Kenneth Almquist)
Subject: Re: AES final comment deadline is May 15
Date: Thu, 25 May 2000 15:56:47 GMT
Scott Fluhrer wrote:
> For the record, Rinjdael and Serpent in encrypt mode, and Twofish
> bidirectionally makes it relatively simple for hardware to do key
> scheduling on the fly, making the cost of changing a key zero.
With Serpent the calculation of the end of the key schedule can be
calculated efficiently; it is not necessary to calculate the full
key schedule. This is not mentioned in the Serpent AES submission,
presumably because the designers of Serpent were not aware of it.
In the NIST implmenetations, the cost of changing a key is small
but nonzero for Serpent and Twofish, because some time is required
to calculate the subkeys for the first round.
Kenneth Almquist
------------------------------
Subject: Re: RSA/PK Question
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 25 May 2000 08:59:01 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (DJohn37050) wrote:
>Note that the original TIME sizes were from the DSA-2 draft
(with longer key
>sizes). Recall DLP is considered harder than IFP. The
comparable key lenghs
>chart (under TIME) can be found in my "Future Resiliency" paper
at
>www.certicom.com in the white papers section.
>Don Johnson
But factoring numbers beyond 768 bits is not currently possible,
and 1kbit won't be for a long time, how do you reason that
8+kbit keys are comporable to a 256 bit symmetric key?
People seem to forget that theoretical does not always mean
practical. Yes theoretically your stmt may be true, but to
actually *implement* the attack is not possible.
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: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Thu, 25 May 2000 10:26:59 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> This appears to be a violation of the single constraint you mentioned earlier in
> this thread. If your description is true (and I have no reason to believe that
> it is not), then the more recent implementations of RDTSC are flawed in that they
> should have the moral equivalent of an implicit "sequence point". Out-of-order
> execution, which is usually accompanied by speculative execution, can give truly
> ridiculous result such as both paths of a branch/merge producing the same timing
> result.
I'm not sure what constraint I mentioned earlier that could be
violated. In any case, I'm pretty sure the two would never really
execute in reverse order, but this is more or less by accident, not
design -- basically the execution units simply look at instructions
in order until they find one they can execute, so instructions will
only get executed out of order if they have different resource
constraints.
For the most part, I agree: it would have made a great deal more
sense to make rdtsc a serializing instruction -- there are VERY few
purposes to which it can be put and have it make sense to execute it
out of order.
[ ... ]
> How do you feel about the approach to timing suggested by Kernigan and Pike?
> They advocated timing elementary functions with many (1e6+) iterations.
That depends. If you can use something like times (UNIX) or
GetProcessTimes/GetThreadTimes (Win32) it can work quite well. If
you use wall time, then it's almost certain that your time will
include various other code unrelated to what you're trying to
measure. If you can ensure that the system is lightly enough loaded,
that's probably not a major problem, and may help give some idea of
speed.
OTOH, if your system is doing unpredictable amounts of unrelated work
you nearly need to filter out the unrelated work before you can get
meaningful results from a profile.
Of course, some of what it's reasonable to advocate depends on the
capabilities you have available as well. Without the ability to
measure things at the level of a single clock cycle (or very close to
it) you've got little choice but to execute the code often enough for
it to take at least several cycles of the fastest clock you can use.
If that happens to be 55 ms, and you're trying to measure the speed
of things that only take a fraction of a microsecond or so, then
you're left with little choice but to execute them VERY often and put
up with knowing that your results are going to be off.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: RSA/PK Question
Date: 25 May 2000 16:14:26 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> People seem to forget that theoretical does not always mean
> practical. Yes theoretically your stmt may be true, but to
> actually *implement* the attack is not possible.
Not possible toay. The charts at cryptosavvy and elsewhere represent
the efforts by various people to estimate what may be possible tomorrow.
Perhaps this is an odd notion of "possible," but it seems like what
we have to go on short of using info-theoretically secure systems
(and even then we have the wonderful world of implementation failures
to look forward to).
-David
------------------------------
From: [EMAIL PROTECTED] (Daniel)
Subject: list of prime numbers
Date: Thu, 25 May 2000 16:46:17 GMT
I don't know if this is public domain or not, but can we get a list
with the (recent) prime numbers (up to 150 digits)?
All help greatly appreciated
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: More on Pi and randomness
Date: Thu, 25 May 2000 10:55:25 -0600
Reply-To: [EMAIL PROTECTED]
"Douglas A. Gwyn" wrote:
> Jonathan Thornburg wrote:
> > Such "probabilistic" is *very* dangerous, because it almost invariably
> > neglects correlations between the errors in different variables.
>
> True; one should use such methods only when the quantities being
> combined have independent errors, or when one can explicitly
> treat any correlation that may exist.
>
> Interval arithmetic has a similar problem in the opposite direction.
Actually interval arithmetic does not have this problem. This is because
intervals are the most pessimestic way of viewing things. Enclosure is the
primary virtue of interval arithmetic. If no divisions or intersections (or
some other operations) are done, the intervals expand proportionally to the
number of operations. The statistical errors expand proportional to the
square root of the number of operations.
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: list of prime numbers
Date: Thu, 25 May 2000 10:56:42 -0600
Reply-To: [EMAIL PROTECTED]
I have such a list, but the page is too small to write them on.
------------------------------
** 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
******************************
