Cryptography-Digest Digest #941, Volume #11 Sun, 4 Jun 00 22:13:01 EDT
Contents:
Re: Could RC4 used to generate S-Boxes? (tomstd)
Rectification (Ake Tyvi)
Re: AES times on the Alpha 21164 with Parallel encryption (Kenneth Almquist)
Re: Could RC4 used to generate S-Boxes? ([EMAIL PROTECTED])
Re: Could RC4 used to generate S-Boxes? (tomstd)
Re: Could RC4 used to generate S-Boxes? ("Scott Fluhrer")
Donald Davies has died ([EMAIL PROTECTED])
Re: Improving DES based MAC ("Scott Fluhrer")
Improved Tiny Crypto Lib (tomstd)
Re: Observer 4/6/2000: "Your privacy ends here" (Charles Bryant)
Re: RSA Algorithm ("Joseph Ashwood")
Re: RSA Algorithm (tomstd)
Re: RSA Algorithm (S. T. L.)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Dave Howe)
Re: Concerning UK publishes "impossible" decryption law (Dave Howe)
Re: RSA Algorithm ("Joseph Ashwood")
Re: AES times on the Alpha 21164 with Parallel encryption (Helger Lipmaa)
----------------------------------------------------------------------------
Subject: Re: Could RC4 used to generate S-Boxes?
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 04 Jun 2000 15:07:05 -0700
In article <8hej6v$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Guy Macon) wrote:
>tomstd wrote:
>>
>>
>>In article <8hdt3k$apl$[EMAIL PROTECTED]>, Simon Johnson
>><[EMAIL PROTECTED]> wrote:
>>>I've read somewhere that RC4 is secure against both diff & lin
>>>cryptanalyis. I figure this secuirty must be derived from its
s-
>>box. My
>>>real question is, is the secrecy of the s-box that makes it
>>secure or
>>>does the algorithm generate diff & lin optimized s-boxes?
>>
>>Chances are you have a bit of reading todo on sbox
construction.
>>
>>The reason RC4 is secure is that it's hard to model the
internal
>>state based on output only. Some 'weak keys' have been
>>identified which leak more information about the state.
>>
>>The sboxes RC4 makes are by no means secure on their own (i.e
in
>>a feistel cipher), and don't always have optimial cryptographic
>>properties (SAC, BIC, non-linear, bijective, low xor-pairs).
>>
>>Tom
>
>Sorry for being a bother, but I am a clueless newbie who has a
>special interest in RC4 (the ciphersaber implementation, really)
>and the above went over my head. Could someone explain the
above
>in simple terms?
>
Sure no prob. RC4 is a STREAM CIPHER, not a sbox generator.
The only reason RC4 is secure is that it's hard to model the
internal state (i.e the table) from only the output.
RC4 does not always make secure sboxes for block ciphers or
other components. In a block cipher generally you use the same
sbox over and over (without any change) so it has to have some
ideal cryptographic properties. Such as being non-linear (avoid
the output and keybits being expressed by one boolean expression
with a higher probability), or low input-output xor pairs to
avoid differential cryptanalysis (all pairs are equally low
probable), or satisfy SAC which states "If bit j of the input
changes bit i of the output will change with prob 1/2", or BIC
which states "bit j and i (j != i) of the output are not
linearly dependant". RC4 is not designed to make 8x8 boxes that
fulfill these requirements.
Asides from that RC4 is not a super prng anyways, it's better
then nothing but that's about it.
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!
------------------------------
Date: Mon, 05 Jun 2000 01:09:42 +0300
From: Ake Tyvi <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: alt.discuss.computers,comp.security.misc
Subject: Rectification
Dear Sirs,
Yes Sir, the place is actually called Institute of Information Technology,
even it should be called Institute of Information Science, since
universities do not give damn about these things at Finland.
Yes Sir, the letter in only memorandum with typing mistakes.
Thank You.
Mr �ke Tyvi
------------------------------
From: [EMAIL PROTECTED] (Kenneth Almquist)
Subject: Re: AES times on the Alpha 21164 with Parallel encryption
Date: Sun, 04 Jun 2000 22:20:18 GMT
[EMAIL PROTECTED] (Jonathan Thornburg) wrote:
> Why compare times on obselete chips? [...]
>
> A comparison using reasonably contemporary chips would be much more
> interesting, i.e. any of Pentium III, AMD K7, Alpha 21264 EV67, and
> their kin. Unlike the 21164, these chips are all heavily out-of-order,
> so their relative performance might be quite different.
Unfortunately, any chip available today will be obsolete during most
of the lifetime of the AES. I would have used the Alpha 21264 EV67
or the Intel Itanium as the basis for comparison if I had had access
to information concerning these chips when I started this project. The
Pentium III and AMD K7 processors are designed to be backward compatable
with a chip designed twenty years ago, so I do not consider them to be
particularly good representatives of the current state of the art.
Out of order execution is only relevant if the optimal execution order
is data dependent. Two of the AES candidates (DEAL and Loki) used
more data than would fit in the 8K byte primary data cache, and thus
could experience data dependent cache misses. With DEAL, I preloaded
the data, so the effect is small. Loki is so slow on the Alpha 21164
that I merely extablished a lower bound on its execution time and
ignored the caching issues. Neither of these candidates were selected
as finalists. Therefore, out of order execution is not signficant.
What probably is a signficant issue is the amount of parallelism. The
21164 can dispatch two integer instructions per cycle. The trend appears
to be in the direction of increasing parallelism. This favors algorithms
with lots of internal parallelism, unless you consider implementations
which encrypt multiple blocks in parallel (which is how this thread
started). The difficulty with generalizing here is that a great deal
depends on how many of each type of instruction can be executed in
parallel. For example, if one believes that future processors will
have more functional units, but stick to the dual ported primary
cache design used in the 21164, then Rijndael, which has lots of
internal parallelism, might become limited by its S-box lookups, and
Twofish (which has fewer S-box lookups and more other operations than
Rijndael) might perform significantly better than Rijndael.
Kenneth Almquist
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Could RC4 used to generate S-Boxes?
Date: 4 Jun 2000 22:22:30 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (tomstd) wrote:
> The reason RC4 is secure is that it's hard to model the internal
> state based on output only. Some 'weak keys' have been
> identified which leak more information about the state.
>
> The sboxes RC4 makes are by no means secure on their own (i.e in
> a feistel cipher), and don't always have optimial cryptographic
> properties (SAC, BIC, non-linear, bijective, low xor-pairs).
Would these be relevant if the s-box were different for each
message? (ie were generated from a one-time session key)
Keith
http://www.cix.co.uk/~klockstone
------------------------
'Unwise a grave for Arthur'
-- The Black Book of Carmarthen
------------------------------
Subject: Re: Could RC4 used to generate S-Boxes?
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 04 Jun 2000 15:27:07 -0700
In article <8hekr6$t5u$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] (tomstd) wrote:
>
>> The reason RC4 is secure is that it's hard to model the
internal
>> state based on output only. Some 'weak keys' have been
>> identified which leak more information about the state.
>>
>> The sboxes RC4 makes are by no means secure on their own (i.e
in
>> a feistel cipher), and don't always have optimial
cryptographic
>> properties (SAC, BIC, non-linear, bijective, low xor-pairs).
>
>Would these be relevant if the s-box were different for each
>message? (ie were generated from a one-time session key)
>
Depends on several things, a) how you use the sbox, b) how long
the message is, c)...
If you took these sboxes and put them (and their inverse) into
SAFER for example, it could make the system easily breakable.
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: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Could RC4 used to generate S-Boxes?
Date: Sun, 4 Jun 2000 15:14:51 -0700
Simon Johnson <[EMAIL PROTECTED]> wrote in message
news:8hdt3k$apl$[EMAIL PROTECTED]...
> I've read somewhere that RC4 is secure against both diff & lin
> cryptanalyis. I figure this secuirty must be derived from its s-box.
Errr, no. Have you looked at RC4? It doesn't use any sboxes, that is,
there is no static tables, either predefined or key-dependant.
There is a state-dependent permutation, but it changes over time. In
addition, we don't know of any permutations of 0-255 that will definitely
not show up at some point in the cipher [1]. So, it's hard to call it
"optimized" when it might take on any setting at all.
> My real question is, is the secrecy of the s-box that makes it secure
> or does the algorithm generate diff & lin optimized s-boxes?
Neither. My best guess as to why it's secure is that it is very good at
dissipating any partial state throughout the rest of the cipher. It is
indeed possible to get some information about the state of the permutation
at some points of time -- however, advance the cipher 256 steps, and the
permutation is effectively reshuffled. This means that partial information
at various points don't really accumulate, unless you have a *lot* of
information at some point. In contrast, a block cipher is effectively a
static object, and so partial information from different characteristics do
add up.
[1] If you include the states of the indicies as well, then yes, there are
some states that are known not to happen. I was just talking about only the
permutation, which is the thing that even remotely resembles an sbox.
--
poncho
------------------------------
From: [EMAIL PROTECTED]
Subject: Donald Davies has died
Date: 4 Jun 2000 22:50:39 GMT
According to reports, Donald Davies has died at the age of 75:
http://www.it.fairfax.com.au/breaking/20000601/A31536-2000Jun1.html
I picked this up on Slashdot:
http://slashdot.org/article.pl?sid=00/06/01/0418250&mode=thread
Reputedly the first to use the term 'packet switching' he can
be considered one of the fathers of the internet. He also
contributed much in the area of security, such as the first
message authenticator algorithm.
Keith
http://www.cix.co.uk/~klockstone
------------------------
'Unwise a grave for Arthur'
-- The Black Book of Carmarthen
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Improving DES based MAC
Date: Sun, 4 Jun 2000 16:06:59 -0700
Tor Rustad <[EMAIL PROTECTED]> wrote in message
news:zyu_4.19340$[EMAIL PROTECTED]...
> The world is still DES based, and upgarding the HW infrastructure is very
> expensive in many cases.
>
> 2. Two-key triple DES has been stated as less secure than three-key triple
> DES, but as far as I can see it, two-key triple DES is secure for all
> practical purposes due to the storage requrements on the attack.
The computational costs for 3 key 3DES is no less than for 2 key 3DES, and
in many applications, the additional key bits are available anyways. Since
3 key 3DES is believed to be strictly more secure than 2 key 3DES, and has
(for those "many applications") no disadvantages, why go with 2 key 3DES?
> 4. In many cases the space is limited in devices, what is the security
> implications in DESX of setting
> a) k = k1 = k2
> b) k = k1
> c) k = k2
> (in context of brute force attack)
None of these is much stronger than DES -- they can all be broken in
O(2**64) operations, with neglicable memory, and 2 known plaintex/ciphertext
pairs. To take case b, you take your known plaintext/ciphertext pairs
(P1,C1) and (P2,C2), and rearrange the equations:
C1 = k2 XOR (DESk( k XOR P1 ))
C2 = k2 XOR (DESk( k XOR P2 ))
C1 XOR C2 = DESk( k XOR P1 ) XOR DESk( k XOR P2 )
Then, you iterate through the various possible values of k until you find
values that satisfy this last equation.
--
poncho
------------------------------
Subject: Improved Tiny Crypto Lib
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 04 Jun 2000 16:38:34 -0700
I am working on a newer version of CB called MicroCrypt which
offers the same idea (ciphers+hashes+rng+compression+...) but
the idea is to have this a bit more compact (i.e not link all
ciphers+hashes) and make the ciphers directly accessible.
Anyways...
I am trying to implement Safer-K64/Safer-K128 and I cant
understand one thing in Applied Crypto. (p341) he says the
rotations are 'byte per byte' (in the key schedule) is that
literally just
for j = 0 to 7 do
key[j] = key[j] <<< 3
(key[0..7] is the key bytes)
Or is it a full 64-bit rotate? I think it's the former but I am
not sure.
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: Charles Bryant <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,alt.security.scramdisk,uk.telecom
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
Date: 4 Jun 2000 22:45:26 -0000
In article <511.393a83f0.6d2e@scgf>, Phillip Deackes <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>, B Labour wrote:
>>http://www.observer.co.uk/focus/story/0,6903,328071,00.html
>>
>>Your privacy ends here
>>
>>A Bill which is slipping through the House of Lords will allow MI5 access to
>>all our online communications, says John Naughton. It could mean we're all
>>guilty until proven innocent. So why don't we care more?
>>
>>Free speech on the net: special report
>>
>
>The answer is simple. A massive campaign to get all email users to
>include certain words in every email they send. The words should be
>those MI5 might be looking for. Secondly, *all* email users should
>encrypt their emails and *refuse* to hand over the keys. The legal
>forces can deal with a few cases of law-breaking, but they *cannot* deal
>with mass civil disobedience.
They can't? So why haven't speed limits been abolished? About 70% of
people break the speed limit at some time or another.
--
Eppur si muove
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: RSA Algorithm
Date: Sun, 4 Jun 2000 17:33:52 -0700
Perhaps I need to summarize exactly what I claimed.
I claim:
One cannot compress beyond the space needed to store
the entropy (a simple truth)
If one can compress the output of a cipher across
keys and input, there is a flaw in the algorithm
One way of interpretting a cipher is to consider it as a
black box that makes the apparent entropy equal to the
length, so the second statement is effectively a restatement
of the first as applied to cryptography. If the output of
the cipher can be compressed than it obviously is leaking
information about the plaintext, or information about the
key, either of which makes it weak encryption.
Joe
> That's not true. If you make a crypto-system where the
> ciphertext is larger then the plaintext the ciphertext
will have
> less information then the input (well if you don't count
the key
> bits). That doesn't mean it's insecure, just inefficient.
------------------------------
Subject: Re: RSA Algorithm
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 04 Jun 2000 17:52:23 -0700
In article <uX45YXoz$GA.326@cpmsnbbsa09>, "Joseph Ashwood"
<[EMAIL PROTECTED]> wrote:
>Perhaps I need to summarize exactly what I claimed.
>I claim:
> One cannot compress beyond the space needed to store
>the entropy (a simple truth)
> If one can compress the output of a cipher across
>keys and input, there is a flaw in the algorithm
>
>One way of interpretting a cipher is to consider it as a
>black box that makes the apparent entropy equal to the
>length, so the second statement is effectively a restatement
>of the first as applied to cryptography. If the output of
>the cipher can be compressed than it obviously is leaking
>information about the plaintext, or information about the
>key, either of which makes it weak encryption.
Your assumption is only true if the ciphertext and plaintext are
the same size. It would be perfectly valid for me to designed a
cipher that takes 3DES and puts eight zero bits between each of
the real ciphertext bits. In this case it would be no weaker
(since I am still using 3des) but be compressible.
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] (S. T. L.)
Subject: Re: RSA Algorithm
Date: 05 Jun 2000 01:09:55 GMT
<<Due to the fact that that encryption seems to lower the entropy,
it appears to be possible to compress the message.>>
You mean lowers the entropy per bit. What's the problem here? I don't see the
point.
-*---*-------
S.T.L. Quotes page: http://quote.cjb.net Now playing: Half-Life
"Never invest in something that violates a conservation law" - John Walker
"If anyone wants a hole in the ground, nuclear explosives can make big holes" -
Edward Teller
------------------------------
From: Dave Howe <DHowe@hawkswing>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Mon, 05 Jun 2000 02:14:06 +0100
Reply-To: DHowe@get_email_from_sig
In our last episode (<alt.security.pgp>[Sun, 4 Jun 2000 14:44:45
+0100]), David Hartley <[EMAIL PROTECTED]> said :
>In article <[EMAIL PROTECTED]>, Adrian Kennard
><[EMAIL PROTECTED]> writes
>
>>... the individual may not wish to disclose a key
>>which can then be used to decode everything they have ever
>>recevied regardless of relevance, and sign things with their name, etc.
>
>Does the bill actually require this? i.e. disclosure of your private PGP
>key. I presume that offering the plain texts would not be sufficient
>unless they can be verified, but how about offering the session key
>(right technical term?) for each message demanded. That's the key which
>has been used to encrypt the body of the message, so presumably that's
>the key that's covered by the bill. IANAP but I assume it would be
>straightforward to write a small program that could do this. The
>practical difficulty comes in entering your passphrase if the room is
>full of policemen.
Hmm. in principle, a session key should always be ok. However, if
plod WANTS your main key, he can do the following:
a) Demand it on the basis of future traffic; you don't have session
keys for that yet, so can't provide them
b) Demand it for messages you don't have, and that he is not going to
give you; you don't have the headers, so can't provide a session key
c) Define the SESSION KEY as the encrypted message, then demand the
key to that
d) just demand it anyhow
------------------------------
From: Dave Howe <DHowe@hawkswing>
Crossposted-To:
alt.security.pgp,comp.security.pgp.discuss,alt.security.scramdisk,alt.privacy
Subject: Re: Concerning UK publishes "impossible" decryption law
Date: Mon, 05 Jun 2000 02:14:11 +0100
Reply-To: DHowe@get_email_from_sig
In our last episode (<alt.security.pgp>[Sun, 04 Jun 2000 17:35:52
-0400]), jungle <[EMAIL PROTECTED]> said :
>no ...
>Jim wrote:
>> >128 bit PGP has been cracked according to announcements
>> >posted here some time ago.
>> I don't think anyone saw any proof of this, did they?
>no ...
But a 128 bit key is pretty lousy by today's standards. I would be
horrified to think that anyone would consider 128 bit RSA trustworthy.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: RSA Algorithm
Date: Sun, 4 Jun 2000 18:33:12 -0700
That would of course result in a cipher that would be less
than perfect because it would very clearly reveal the
difference between your encrypted stream and random data,
thus what you have proposed is a method of weakening triple
DES. It is well known that one can through untelligent moves
weaken security.
Joe
> Your assumption is only true if the ciphertext and
plaintext are
> the same size. It would be perfectly valid for me to
designed a
> cipher that takes 3DES and puts eight zero bits between
each of
> the real ciphertext bits. In this case it would be no
weaker
> (since I am still using 3des) but be compressible.
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: AES times on the Alpha 21164 with Parallel encryption
Date: Mon, 05 Jun 2000 03:36:14 +0300
Kenneth Almquist wrote:
>
> What probably is a signficant issue is the amount of parallelism. The
> 21164 can dispatch two integer instructions per cycle. The trend appears
> to be in the direction of increasing parallelism. This favors algorithms
> with lots of internal parallelism, unless you consider implementations
> which encrypt multiple blocks in parallel (which is how this thread
> started). The difficulty with generalizing here is that a great deal
> depends on how many of each type of instruction can be executed in
> parallel. For example, if one believes that future processors will
> have more functional units, but stick to the dual ported primary
> cache design used in the 21164, then Rijndael, which has lots of
> internal parallelism, might become limited by its S-box lookups, and
> Twofish (which has fewer S-box lookups and more other operations than
> Rijndael) might perform significantly better than Rijndael.
> Kenneth Almquist
A good (I hope) overview of the problems that occur when implementing
different AES finalists on the Pentium II processor is given in the paper
"Fast Implementations of AES Candidates" (Kazumaro Aoki and me, AES3
conference, available from http://www.tcm.hut.fi/~helger). Interestingly,
implementations of MARS, Twofish and Rijndael all took about the same
number of microoperations (572, 595 and 601, correspondingly), while the
actual number of cycles per block encryption differed significantly. For
example, my current Rijndael implementation for Pentium II achieves 2.6 uops
per cycle (an updated number, compared to that in the paper), which is a
_very_ good sign of its parallelism. While the maximum parallelism that is
(in general) possible on Pentium II is 3.0 uops per cycle, this number is
almost never achieved in practice. (In many cases, the bottleneck is
decoder. In other cases, ROB. Etc). For comparison, Twofish achieves 2.15
uops per cycle, MARS 1.87 and RC6 --- 1.48. Now, the last number does not
show that RC6 does not have internal parallelism, in fact it does. Just the
multiplication has high latency. And Rijndael has as high upc number only
since its implementation does almost exactly 2 ALU operations per every
memory load, so that at almost every tact three execution ports are
loaded. This _is_ amazing, but it also shows that Rijndael cannot gain much
speed from a single added ALU if another memory load port is not added at
the same time.
Helger
http://www.tcm.hut.fi/~helger
------------------------------
** 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
******************************
