Cryptography-Digest Digest #955, Volume #8 Sat, 23 Jan 99 15:13:03 EST
Contents:
Re: Metaphysics Of Randomness (Alan DeKok)
Re: Cryptanalysis of Simple Block Ciphers ("Trevor Jackson, III")
Re: S-box cycles (David Hamilton)
Re: Who will win in AES contest ?? (Paul Crowley)
Re: Pentium III... (fungus)
Re: Pentium III... (Daniel James)
Re: Who will win in AES contest ?? (Fabrice Noilhan)
Nulls, Part IV (wtshaw)
The Performance of Meet-in-the-Middle ([EMAIL PROTECTED])
Re: Cryptanalysis of Simple Block Ciphers (James Pate Williams, Jr.)
Can anyone offer opinions on TEA, XTEA? (Thomas A. Oehser)
Re: Cryptanalysis of Simple Block Ciphers (James Pate Williams, Jr.)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Alan DeKok)
Subject: Re: Metaphysics Of Randomness
Date: 23 Jan 1999 10:31:17 -0500
In article <[EMAIL PROTECTED]>, Boson <[EMAIL PROTECTED]> wrote:
>
>Your over-use of the adjective "true" is a gradeschool error. Next we
>will need super-duper random number generators: SDRNG. Then Ultra-Pure
>Random Number Generators: UPRNG.
This sort of frothing at the mouth only shows how little you
understand of the topic.
>If I gave you two sequences, could you clasify them as coming from a RNG
>vs. a TRNG? No.
Sorry, the true answer is "Very often, yes."
> A random number generator produces random sequences of
>numbers.
"apparently random" sequences, perhaps.
There are different classes of random number generators:
True, Pseudo, and Cryptographically secure. (To name a few).
These have different properties and different biases. These biases
often allow you to tell a PRNG from a TRNG.
> If you have to puff yourself up like an insecure simpleton by
>adding "true" to it, then you are uselessly posting immense amounts of
>crap. Or to use your notation, true crap.
A 'True' RNG generates random numbers via *observational* methods.
e.g. Watching decays from a radioactive source.
A 'Pseudo' RNG generates random numbers via an *algorithm*. The
simpler the algorithm, the more biased the random numbers.
A 'Cryptographically secure' RNG generates random numbers via a
*non-deterministic* algorithm. The output of any one generator is
unpredictable even knowing the algorithm and all initial conditions.
Alan DeKok.
------------------------------
Date: Sat, 23 Jan 1999 13:00:11 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalysis of Simple Block Ciphers
James Pate Williams, Jr. wrote:
> I am using a genetic algorithm (steady-state uniform crossover
> mutation rate of 10%) to find the key to the simple n-bit xor
> block cipher (C = P xor K) using a single known plaintext. This
> is just to test the applicability of GAs to simple block ciphers.
> I realize that with P and C known it is simple matter to calculate
> K (K = P xor C since P xor P = 0 and 0 xor K = K), however,
> I am using a GA to "intelligently" search the key space. The
> preliminary results do not look very promising since the number
> of keys correctly found tends to decrease exponentially with
> increased block size. Does anyone have any simple 8-bit
> block ciphers that are marginally (or perhaps) better than the
> simple xor cipher, if so, then please post them here or get in
> contact with me at the following e-mail address, I will share
> the code I generate from the algorithm and also I am willing
> to share my xor GA.
I think the whole GA is more than necessary. I'd be interested in your
fitness function and the theory behind it. How do you make is
algorithm-independent without exponential evaluation costs?
------------------------------
From: [EMAIL PROTECTED] (David Hamilton)
Subject: Re: S-box cycles
Date: Sat, 23 Jan 1999 18:10:39 GMT
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
(snip)
>You end up with the identity transform
>which even some one with no brains like Hamilton would condsider
>weak.
It doesn't take brains to ask David A. Scott the 6 questions on cryptography
that he is afraid to answer. It may well take brains to answer some of them
though ... no answers yet.
(See message-ID: <[EMAIL PROTECTED]> in the thread 'Re: What
is better : Blowfish, Des, Tripple-Des' posted in sci.crypt on 13th January
for the half a dozen quesions.)
David Hamilton. Only I give the right to read what I write and PGP allows me
to make that choice. Use PGP now.
I have revoked 2048 bit RSA key ID 0x40F703B9. Please do not use. Do use:-
2048bit rsa ID=0xFA412179 Fp=08DE A9CB D8D8 B282 FA14 58F6 69CE D32D
4096bit dh ID=0xA07AEA5E Fp=28BA 9E4C CA47 09C3 7B8A CE14 36F3 3560 A07A EA5E
Both keys dated 1998/04/08 with sole UserID=<[EMAIL PROTECTED]>
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
Comment: Signed with RSA 2048 bit key
iQEVAwUBNqn+d8o1RmX6QSF5AQERAgf/ZSaNlrIYSssUFQXHyGT2vh8wxvFtOiua
k9c4apFOZTm3lAppzRIBCVr38J41P+hO9eEUIKlK8HSFp0JBV9QAmNVGNWIfIR+h
3X1uPxhip2YabWDLttt3lnEwZwxJF4Trjoi0ciEDdB2Y9iEw7QeWdfJ/iFOdKS6v
AH8GrYbDbMczvCwmvy4xLiB9ilCbierVXGsLxFBCGjXgTHIRdChVQSNIGZOllCpB
Qj2zw+MLvdDgQudq5jlKVzF9SlB3ZLIsuVBED/e1yjcmp5CGZwr/UaJUYojx8Ovh
6Oxs4oCOr5viYcno7m1dkcMonB7pD/dfz/30siGNxu/h1j70WYEOsw==
=JG6D
=====END PGP SIGNATURE=====
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Who will win in AES contest ??
Date: 23 Jan 1999 13:58:55 -0000
Robert Harley <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] (Piotr Kulinski) writes:
> > What do you think who will win in AES contest ???
> > My type is Twofish....
>
> Why do you think it would be Twofish? Because Bruce Schneier wrote a
> very popular book? Twofish is quite a complex, non-obvious cypher. No
> offense intended to its inventors, but I don't think it is a
> "front-runner". If you care about speed first and security second
> then Mars or RC6 are likely candidates. If you care about security
> first and speed second then DFC looks good.
I think it is a front runner. 15 ciphers were submitted to NIST for
the AES contest:
CAST-256, CRYPTON, DEAL, DFC, E2, FROG, Hasty Pudding, LOKI97, MARS,
MAGENTA, RC6, Rijndael, SAFER+, SERPENT, Twofish.
Of these, four have sufficiently serious results against them to fall
by the wayside: MAGENTA, LOKI97, FROG, and DEAL (I got this from
http://www.ii.uib.no/~larsr/aes.html - the AES sofa in the block
cipher lounge). For reasons I don't fully understand, the
equivalent-key result against MARS isn't being taken as damning, but
I'll go with the flow here. This leaves:
CAST-256, CRYPTON, DFC, E2, Hasty Pudding, MARS, RC6, Rijndael,
SAFER+, SERPENT, Twofish.
The rest people seem generally happy with the security, so I'll move
straight onto performance issues. I've looked in three places for
performance information: CAESAR's performance comparisons, Brian
Gladman's C implementations, and the performance comparison
paper by the Twofish team:
http://www.dice.ucl.ac.be/crypto/CAESAR/performances.html
http://www.seven77.demon.co.uk/aes.htm
http://www.counterpane.com/twofish/
CAESAR's comparisons on the target Pentium Pro processor make it clear
we can forget about DEAL and SAFER+ on performance grounds: they don't
seem to have advantages over the other candidates that justify paying
that huge performance price. DEAL went earlier anyway on security
grounds. Hasty Pudding and DFC also look a little dodgy here but I'll
let them through. This leaves:
CAST-256, CRYPTON, DFC, E2, Hasty Pudding, MARS, RC6, Rijndael,
SERPENT, Twofish.
Now time for the real cull: smart card memory requirements. These
figures are taken from the Counterpane paper, but they're backed up by
figures from the original paper and close argument and I'd be
interested to hear about any problems with them. Seven of the
algorithms (CAST-256, Crypton, DEAL, Rijndael, SAFER+, Serpent,
Twofish) require 60 bytes of memory or less. The remaining algorithms
either require at least 195 bytes (DFC, E2, Frog, MARS, RC6), or do
not discuss this requirement in the presentation papers (HPC, Loki97,
Magenta) - it seems that HPC at least would require 2K of key tables.
This leaves only:
CAST-256, Crypton, Rijndael, Serpent, Twofish
Two very popular candidates just got dropped: MARS and RC6. Schneier
et al argue that while their key setup requirements might fit into a
256-byte CPU, so little memory would be left (no more than 61 bytes)
that no practical application could use them. They do look very
impressive on high-end processors, and I hope the inventors decide to
release the patents so we can use them on such applications, but the
AES winner has to be flexible enough to run in a wider variety of
environments. Again, I'm interested to hear counterarguments, since
this is controversial.
This gives us five front runners. Here are Schneier et al's figures
on their performance:
CAST-256 Crypton Rijndael Serpent Twofish
4300 360 2100 2500 8000 Key setup PPro in C
660 480 440 1030 400 Encrypt PPro in C
600 390 320 900 285 Encrypt PPro in ASM
600 390 320 1100 290 Encrypt Pentium in ASM
(Figures in clocks from Table 2 of the Schneier et. al. paper.
Note that faster ASM versions of Twofish have been developed since
this came out.)
My eyes hurt, so I'm not going to try and summarise the results on the
CAESER or Brian Gladman pages; I encourage you to go and look. I don't
think that CAST or Serpent have enough to recommend them to justify
the performance cost; this basically leaves Crypton, Rijndael, and
Twofish as likely winners. I find through writing this that I haven't
been paying enough attention to Crypton in this contest and I'll have
to find out more about it - Schneier et al say it's the most hardware
friendly. Rijndael is rather nice. However, I agree with the
previous poster that Twofish is the most likely contest winner - it's
the best performer on 32-bit processors, very competitive everywhere
else, and offers a wide variety of useful implementation tradeoffs.
It also has the most comprehensive submission document.
--
__
\/ o\ [EMAIL PROTECTED] http://www.hedonism.demon.co.uk/paul/ \ /
/\__/ Paul Crowley Upgrade your legacy NT machines to Linux /~\
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Pentium III...
Date: Sat, 23 Jan 1999 17:06:32 +0100
[EMAIL PROTECTED] wrote:
>
> It would be very nice if there was a true random source since one
> could use it to raise the entropy of messages before they are encrypted.
Huh?
> But in reality. It would be very hard to check from a user point
> of view as to the fact that it is a true random number generator.
> Remember how the NSA cooked the Swiss crypto stuff. That was
> overseas. With intel being here in the US. The odds of no NSA
> involwment begins to approach that of a snowball in hell.
>
By similar logic, I can say the NSA were more than likely involved
in ScottXX.zip.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Daniel James <[EMAIL PROTECTED]>
Subject: Re: Pentium III...
Date: Sat, 23 Jan 1999 18:50:52 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Trevor Jackson, III wrote:
> Read the fine print. The purpose is to *identify* the user, not assist him.
>
The serial number in the chip is to help control the trade in stolen CPUs,
which is a big moneyspinner in certain parts of the criminal world.
Cheers,
Daniel James
Daniel at sonadata.demon.co.uk
------------------------------
From: [EMAIL PROTECTED] (Fabrice Noilhan)
Subject: Re: Who will win in AES contest ??
Date: 23 Jan 1999 18:48:49 GMT
According to Paul Crowley <[EMAIL PROTECTED]>:
> http://www.dice.ucl.ac.be/crypto/CAESAR/performances.html
> http://www.seven77.demon.co.uk/aes.htm
> http://www.counterpane.com/twofish/
May I add http://www.dmi.ens.fr/~granboul/recherche/AES.html ?
There are comparisons for Intel, Sparc and AXP processors.
You have to compare using real encryption times, i.e. using best
internal ciphering routine. Some of these comparisons deal with ANSI
C-code. This does not really matter if you use a good compiler which
make full use of your processor (f.i. DEC's cc for alphas) but this is
really quite annoying for comparisons purposes. The NIST platform was a
PPro 200 with Borland C compiler. This does not lead to serious results
as to the speed of candidates. See MARS submission paper for instance.
> Now time for the real cull: smart card memory requirements. These
> figures are taken from the Counterpane paper, but they're backed up by
> figures from the original paper and close argument and I'd be
> interested to hear about any problems with them.
The major drawback is that this paper is really biased as the authors
say in the conclusion (and all AES candidates' papers will be!). Of
course, the memory requirement for smartcards implementations is an
important issue. But, don't forget that by the time the AES process
is ended, smartcards won't be the same as nowadays. It is reasonable
*today* to find smartcards with 200 bytes of RAM. You have not to forget
this in your study. Furthermore, 32 bit processors are already being
sold for smart cards. Thus, it may be safe to study the amount of RAM
needed, but you have to be careful in your conclusions. DFC needs only
100 bytes; I don't think you can forget MARS and RC6 this way.
My point is that for processors and for smart card requirements, you
should look into the future. I would not drop candidates only because
they use 100 more bytes of RAM. This is likely to be negligeable in
the near future. I'm more concerned about processors tricks (e.g.
data-dependant rotations) which may not be used in the next processors.
Anyway, I don't want to argue about this any longer since I'm not really
aware of all this stuff. You'd better see AES2 conference for more
papers. Thus, you will have a safer view of the situation.
Fabrice
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Nulls, Part IV
Date: Sat, 23 Jan 1999 10:24:33 -0600
I've made four ciphers, scaled in two ways, by base, and within each one,
by block size. They are: For base 22, Rimfire 8/12/16/20/24; for base 18,
Balsas 10/20; for base 16, Ping 6/12/18/24; and, for base 14, Bangkok
8/16/24. In reality, this is 14 different ciphers. For these ciphers
text input is in base 100, using all normal keyboard characters, 95, plus
a few assorted others.
All use two keys, a substitution key based on the 26 letters, and a
transposition key using from 6 to 24 letters as required. These keys are
usually deranged permutations of the available characters. The keys can
be default, offering no strength in themselves, be entered/generated
independently, or be put in place through a single step. The key
structures are use the THF technique, Transparent Hash Function, whereby
the key(s) can be hashed from text, or, through the same process, simply
be stored from their summary form.
The first number of letters in the substitution key equal to the size of
the base are used as ciphertext characters, and the remainder are
optionally available as nulls. The 26 letter may be used in any
permutation.
In Shannon's equations, one part is knowing the information content of the
keys. According to this thinking, if the 26 letters are in simple
permutations, one might think that they would all be equivalent, which
they are clearly not.
Oversimplifications may be pleasing to those who don't want to be bothered
with details, but we know, as always, the devil is in the details.
The range of the transposition keylengths which might be selected speaks
for itself, except again, that there are weaker keys, and for it alone,
equivalent keys. Consider that the size of the key sets the number of
internal digits that are transposed. For simplification, if we had a
Rimfire 4, then badc would be equivalent to a Rimfire 8 key of badcfdhg.
The steps of operation of all these ciphers is: Select the size of the key
if not the default, and build the key structure; put text in the main
edit-field; use Preformat to put the text into appropriate size blocks,
spaces be represented by triangles; complete the last block to the
necessary size; encrypt; optionally, add nulls which also puts the
ciphertext into five-character groups.
For decryption, with keys generated, and ciphertext in the edit-field,
select decrypt. Nulls are stripped out and formated text is produced; To
regain original format, select Post format.
---
Don't get me wrong, these algorithms are on the primative side. Yet,
there is something to learned from them and some general statements we can
make. Obviously, ciphertext in them is guaranteed to have more characters
than plaintext; adding nulls makes that even worse.
If the question is security, than the size of ciphertext is of no concern.
And, content speaking, less dense low base ciphertext can be thought of as
somewhat equivalent to higher information content of characters in a
higher base. Then, if we consider the expected fraction of null
characters, we get: For base 22, 4/26; for base 18, 6/26; for base 16,
10/26; and, for base 14, 12/26. The null structure can be very important
in making ciphertext harder to attack.
My choice of base 100 for plaintext is simply to use the most naturally
available input format. The problem is that lopsided frequencies of
character usages present a weakness. To counter this, one could use a
more appropriate base, one in which the most important characters
represented the greater part of the set. I will be using other plaintext
bases eventually, but I should probably stick to 100 to complete all the
easy options for it first.
My choice of bases 22/18/16/14 was that they could be all used to easily
produce 26-character output. With the same null structure, no others are
indicated. The size of the mathematics did increase, from handling 4
digits in 22, 5 in 18, 6 in 18, and 8 in 14.
The next natural step is 9 digits in base 13, but continuing the same null
structure is less attractive than using another ciphertext varying
technique. I plan to try that next, where in ciphertext, any character
can have a simple single alternate form, using all 26 letters in
ciphertext with no increase in ciphertext after introducing the
variabiltity.
Then, if I keep with base 100 input, I need to explore higher easy bases
for ciphertext. First, base 27 with 10 digits, a test for my programming
language, and as many natural steps above base 27 as below it; certainly,
the math is no more difficult to getoutput in bases 32/40/47/57/64. If I
run into problems handling a certain number of digits, I should not
according to the book, I'll just move on to those that I can handle.
Base 22 is the lowest base that can accept readable messages, with some
limitations. Bases 27 and above require fewer compromises.
If bases can be down converted, they can go up as well. Going up in base
can result in shorter ciphertext than plaintext.
There are sometimes limitations to base-translation techniques that need
special treatment. An easy way out sometimes is to originate in an
inferior member of a base pair, ex: using 46 for plaintext rather than 47,
which is better for ciphertext. I shall try to stay with the digit
translations for the time, but, occasionally, or in a fit of diversion, I
may offer up some unexpected contributions, or do something quick and
dirty out of pattern.
Sometimes an awkward block size is required for some of these
translations, so I will go after the easy ones if I can. And, I like to
include multiple block sizes. One goal is to make these programs
available, as I have done in the past. For now, pushing for more
functional code seems most important, as experience itself presses the
importance of generic functions, which made Bangkok lots easier than those
before it.
--
A much to common philosophy:
It's no fun to have power....unless you can abuse it.
------------------------------
From: [EMAIL PROTECTED]
Subject: The Performance of Meet-in-the-Middle
Date: Sat, 23 Jan 1999 19:39:20 GMT
The meet-in-the-middle attack (MITM) provides an important time-memory
tradeoff when attacking a product cipher. As it is commonly described, it
is based on a tacit assumption which fails in the general case. While it
is *still* true that for DES and similar ciphers, only O(2^(k+1)) time
complexity is required to determine the key, certain conditions need to be
met for this to happen. The two most comprehensive crypto references, HAC
[1] and AC [2] seem to gloss over this subtlety (or perhaps did not
anticipated it at all).
Counterexamples are presented in [3] and [4], where even granting the
storage requirements of MITM, nearly O(2^(2k)) time complexity is required
to determine key. In other words, after buying all that memory, you may
still end up with an exhaustive key search.
I refer readers to [4] for further detail, but let me state what the
subtlety boils down to. Here is MITM for an attack against product XY
where the adversary has a plaintext-ciphertext pairs (p,c):
FOR Ky in the keyspace of Y DO
Write (Ky, E(Ky,p)) to a table indexed by E(Ky,p).
DONE
FOR Kx in the keyspace of X DO
Use D(Kx,c) as an index to retrieve (Ky', D(Kx,c)).
IF E(Kx,E(Ky', *)) is the correct product THEN
return (Kx,Ky').
ENDIF
DONE
The problem is that there may be multiple Ky in the keyspace of Y which
encrypt p to the same intermediate message block. This situation is far
from a pathological case, and in fact can be proven to be desirable for
secure block ciphers [3]. When it happens, one must add an additional
for-loop nested within the second for-loop to check the multiplicity of
candidates, Ky'. Of course, inserting this additional for-loop will change
the expected performance of the attack. This new expected time complexity
T can be shown to be bounded by
W(XY|c,p) <= T < 2^(2k),
where W(XY|c,p) is the conditional guesswork of the product (conditional
``guessing entropy'' if you like), and where each component has k key
bits.
John Pliam
[EMAIL PROTECTED]
http://www.ima.umn.edu/~pliam
refs:
[1] A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied
Cryptography, CRC Press, 1997.
[2] Bruce Schneier, Applied Cryptography, Wiley & Sons, 1996.
[3] John Pliam, Ciphers and their Products: Group Theory in Private Key
Cryptography, PhD in preparation, 1999.
URL: http://www.ima.umn.edu/~pliam/doc
[4] ___, section 6.5 of [3], "About the MITM Attack".
URL: http://www.ima.umn.edu/~pliam/doc/mitm.ps.Z
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Cryptanalysis of Simple Block Ciphers
Date: Sat, 23 Jan 1999 17:41:02 GMT
Reply-To: [EMAIL PROTECTED]
I am using a genetic algorithm (steady-state uniform crossover
mutation rate of 10%) to find the key to the simple n-bit xor
block cipher (C = P xor K) using a single known plaintext. This
is just to test the applicability of GAs to simple block ciphers.
I realize that with P and C known it is simple matter to calculate
K (K = P xor C since P xor P = 0 and 0 xor K = K), however,
I am using a GA to "intelligently" search the key space. The
preliminary results do not look very promising since the number
of keys correctly found tends to decrease exponentially with
increased block size. Does anyone have any simple 8-bit
block ciphers that are marginally (or perhaps) better than the
simple xor cipher, if so, then please post them here or get in
contact with me at the following e-mail address, I will share
the code I generate from the algorithm and also I am willing
to share my xor GA.
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: [EMAIL PROTECTED] (Thomas A. Oehser)
Subject: Can anyone offer opinions on TEA, XTEA?
Date: 23 Jan 1999 12:04:08 -0500
Has there been any further review of the tea/xtea algorithm?
I saw only a comment that it was "too new to comment on", but,
that was a long time ago... has it just been forgotten?
-Tom
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Cryptanalysis of Simple Block Ciphers
Date: Sat, 23 Jan 1999 19:20:41 GMT
Reply-To: [EMAIL PROTECTED]
"Trevor Jackson, III" <[EMAIL PROTECTED]> wrote:
>James Pate Williams, Jr. wrote:
>> I am using a genetic algorithm (steady-state uniform crossover
>> mutation rate of 10%) to find the key to the simple n-bit xor
>> block cipher (C = P xor K) using a single known plaintext.
>I think the whole GA is more than necessary. I'd be interested in your
>fitness function and the theory behind it. How do you make is
>algorithm-independent without exponential evaluation costs?
Suppose the encryption function is:
C = f(P, K)
Then the fitness function I am using is | C' - C | where C' = f(P,K')
is a guess at the key and C is the known ciphertext. In the algorithm
I hope to converge to a zero of the fitness function or at least to a
local minimum which provides a lower and upper bound for the
key. From the preliminary results using the XOR cipher the time
complexity seems to exponentially increase with the number of
bits in the block, not a good sign. Also the number of correctly
found keys seems to exponentially decrease with increase in
block size. I plan on trying some learning techniques such as
multilayer feedback neural networks to the problem.
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
** 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
******************************
