Cryptography-Digest Digest #297, Volume #14 Sat, 5 May 01 20:13:00 EDT
Contents:
Re: Cryptanalysis Question: Determing The Algorithm? (Bill Unruh)
Re: Tiny s-boxes (David Wagner)
Re: A Question Regarding Backdoors ("Roger Schlafly")
Re: Cryptanalysis Question: Determing The Algorithm? (wtshaw)
Re: Cryptanalysis Question: Determing The Algorithm? (SCOTT19U.ZIP_GUY)
Re: Tiny s-boxes ("Tom St Denis")
Re: Cryptanalysis Question: Determing The Algorithm? ("Tom St Denis")
Re: Cryptanalysis Question: Determing The Algorithm? (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: 5 May 2001 18:32:44 GMT
In <[EMAIL PROTECTED]> "Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
>"Bo Doemstedt" wrote:
>> ... What you can do is to sequentially test different assumptions,
Since there are only somewhere in the tens of different algorithms, this
would only increase the work by that factor. Ie, would be equivalent to
mayme 4 or 5 bits of extra password length. Choosing amongst different
algorithms is not a very efficient way of making the system more secure.
Now sequentially using algorithms might, but then that costs an extra
password length each additional algorithm, and I doubt that you get say
128 bit extra security by using say IDEA+AES than AES on its own. Ie,
for the cost in secret password length, it would probably be more
efficient to design a system using the longer password.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Tiny s-boxes
Date: 5 May 2001 20:24:01 GMT
If you like tiny S-boxes, you might like 3WAY, or any of several
other of Joan Daemen's ciphers.
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Sat, 05 May 2001 20:20:39 GMT
"Trevor L. Jackson, III" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Rick Wash wrote:
> > No, it is not. At the very least, the US government has made some
> > very serious proposals for backdoors into cryptosystems. For example,
> > look at the proposed Key Escrow systems. One of the drawbacks of
> > these systems is that they only work if everyone plays by the rules,
> > and to get everyone to play by the rules the government will have to
> > outlaw non-backdoored crypto. If a serious cryptographer plans to
> > continue being a serious cryptographer, then he/she should be careful
> > to obey the law and not end up in jail.
> This is a questionable suggestion. Consider the conversation between
Emerson
> and Thoreau that ensued when Emerson visited Thoreau in jail. Emerson
asks
> "What are you doing in jail?", meaning that Thoreau was an unpstanding
> citizen who could easily have avoided incarceration. In response Thoreau
> asked "What are you doing out of jail?", meaning that the civic situation
was
> so dire that any citizen with integrity should be in jail.
> In general obeying bad laws is a bad idea.
Ok, civil disobedience is occasionally appropriate. But what US crypto laws
are so dire as to justify going to jail?
I'd say the worst is the DCMA, but so far there has been no enforcement
that is worth going to jail over.
(I understand the situation is worse in countries like UK and China.)
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: Sat, 05 May 2001 15:23:26 -0600
In article <9d1h0c$1pp$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Bill Unruh) wrote:
> In <[EMAIL PROTECTED]> "Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
>
> >"Bo Doemstedt" wrote:
> >> ... What you can do is to sequentially test different assumptions,
>
> Since there are only somewhere in the tens of different algorithms....
Wrong. There is a infinite number of algorithms. I know of maybe a
thousand and many are not talking at all.
--
How many good wells were shut in by the VP's company so that oil
prices would raise? It's obvious who did what and why.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: 5 May 2001 20:54:04 GMT
[EMAIL PROTECTED] (Bill Unruh) wrote in
<9d1h0c$1pp$[EMAIL PROTECTED]>:
>In <[EMAIL PROTECTED]> "Douglas A. Gwyn" <[EMAIL PROTECTED]>
>writes:
>
>>"Bo Doemstedt" wrote:
>>> ... What you can do is to sequentially test different assumptions,
>
>Since there are only somewhere in the tens of different algorithms, this
>would only increase the work by that factor. Ie, would be equivalent to
>mayme 4 or 5 bits of extra password length. Choosing amongst different
>algorithms is not a very efficient way of making the system more secure.
>Now sequentially using algorithms might, but then that costs an extra
>password length each additional algorithm, and I doubt that you get say
>128 bit extra security by using say IDEA+AES than AES on its own. Ie,
>for the cost in secret password length, it would probably be more
>efficient to design a system using the longer password.
>
Actully that is true because modern crypto sytems are so poorly
designed. I suspect on purpose. But take a system non bijective system
based on AES ( 256 bit Rijndael ) It works great in the
forward direction. And lets assume that that for any real input FILE
it writes an output file.
But what about the reverse direction for given keys there are files
that can't be reveresed. By reverse I mean that can't be mapped back
to an input file through the decryption process with a key.
In any nonbijective encryption system there are many such key
file compbinations that can't be reversed. When you put two of
these poor system together. You get all the file key combinations
from second system that can't be reveresed though it Plus every
file key combination that could not be reverese from the frist
system Maps through the second system so the density of possible
files in the finial output starts droping.. Since it was not bijective to
begin with. So one could hardly expect the combined system to be
of comparable quality to one based on a key as long as the two
systems combined.
Is there a way out? Yes and the big boys most likely wont even try
to refute since its so obvious. Lets pretend RIJNDEAL 128bit block
256 bit key is for real. And that its a safe system. One can easily
build a 512 bit sytem where the whole file is a single block.
If RIJNDEAL is a true 256 bit system then the combined system is
a true 512 bit system that workd on any file.
The key to doing this is to use BICOM its the only TRUE BIJECTIVE
AES based RIJNDAEL cyrpto system that used full 128bit blocsk with
a 256 bit key. This system takes any input file and maps to the
set of binary files. Like wise take any binary file use any key and
then decrypt it. It is a full bijective mapping of every file to
every file.
After the first encryption use my reverse or you own. ( front of
file is back ). Then encrypt again. With second key. What you know
have is a 512 bit crypto system. Where the whole file is treated
as a single block. If the first was a true 256 bit system then so
is the second.
To prove me wrong one would have to find 2 seperate sets of key
values that map the set of input files to set of output file in
the same way fat chance. Since both the methods are working in
different direction on the file and you have the PPM thing adding
to it and every file coverd in both directions.
If one can find such a set. Assuming RIJNDAEL maps as a true 256 bit
crypto system. I will stop posting on sci.crypt
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: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: Sat, 05 May 2001 23:11:01 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> I've recently become interested in the use of tiny s-boxes again.
Good, if used properly a decent design can arise :-)
> 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.
Generally this is not true. If you want to have some DP or LP bound that is
low (say 4/2^n or something for DP) then random boxes will not do. If you
merely need some higher bound (say 16/2^n) it's easy. As an experiment try
to find a random 8x8 with a DPmax of 6/256. It can be done but takes a very
long time on average even with a decently optimized piece of code (cheap
plug my sboxgen is somewhat ideal but not perfect).
> 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.
Also in software. A 8x8 is typically good for software since alot of cpus
have byte-wise read/modify. Things like 4x4 and 16x16s are not ideal for
software designs. (Note: typical gost implementations make the round
function a series of four 8x32 transforms).
> In terms of hardware implementation that means that instead of a single
> 8x8 s-box, you can afford (very approximately) 32 4x4 s-boxes. Also,
> crude back-of the envelope calculations suggest that 4x4 s-boxes should be
> able to execute over 5 times faster than 8x8 s-boxes in hardware
> consisting of 2D physical substrates.
I dunno about this but I would think a smaller lookup would be faster since
there are less things to keep synchronous.
> Now there is are well established mechanisms for building large boxes
> from very little - except smaller boxes. For example, the field of bblock
> cypher design contains (as a sub-field) an area known as
> substitution-permutation networks (established over fifty years ago),
> which is concerned largely with this.
>
> Also, there are now some strong cyphers that employ many iterations of
> large numbers of very small s-boxes. The first such popular cypher that
> I'm aware of that fits this description was GOST - and now we have Serpent
> - which looks like an ocean of 4x4 s-boxes.
I wouldn't include GOST in the set of "good ciphers". If you want some
ideal ciphers with small sboxes look at Square, Rijndael, Twofish, DES,
Serpent...
> Nevertheless, it seems to me that the art of building large boxes out of
> smaller ones has been neglected. There are two areas that I'm interested
> in in particular.
>
> One is building very small cyphers, using tiny s-boxes, in order to better
> understand how well they approximate the theoretical ideal of a random
> permutation.
You need some knowledge of finite for this one. For a random n-bit function
all output differences should occur with a prob of 1/((2^n)-1). In a
Feistel if the round function is bijective then it cannot be a perfectly
random function since not all output differences are equally probable (they
can't be). However, the lower your DP and LP maximums are the more closely
the Feistel becomes random.
> It seems to me the modern cryptography is obsessed with scaling by
> modification of the number of rounds. To my eyes, this is hardly
> proper scaling at all - *every* aspect of a cypher needs to be
> reduced in order to facilitate proper study.
Generally the idea is towards a moderately secure round function and repeat
as required. It's not a simple as just randomly making a round function
*then* finding how many rounds you need.
> The other is *tiny* s-boxes themselves.
>
> I hypothesise that part of the reason for the interest in 4x4 and 8x8
> boxes is to do with the obsession of computer scientists with powers
> of two. While I can see how it might be somewhat desirable to have
> s-boxes of a size that divides exactly into the block size of the
> cypher (which I don't expect to change), I don't think this is a
> good reason for not examining more closely what seems to me to be
> the most obvious object of study for those interested in an atomic
> approach to adding confusion via non-linearity - namely the 3x3 s-box.
>
> In previous discussions I have received the impression that nobody thinks
> the 3x3 s-box is remotely interesting - since balanced 3x3 boxes have such
> a low maximum non-linearity - and increasing non-linearity is the major
> function of s-boxes.
You can have nonlinear 3x3's for example
The following sbox { 6, 0, 5, 2, 3, 7, 4, 1 } gives us
Walsh-Transform Output:
0 0 0 0 0 0 0 0
0 0 0 0 2 2 2 -2
0 0 2 -2 0 0 -2 -2
0 0 2 2 -2 2 0 0
0 -2 0 2 0 -2 0 -2
0 2 0 2 2 0 -2 0
0 -2 -2 0 0 2 -2 0
0 -2 2 0 2 0 0 2
Pairs XOR Distribution Table:
8 0 0 0 0 0 0 0
0 0 0 0 2 2 2 2
0 0 2 2 0 0 2 2
0 0 2 2 2 2 0 0
0 2 0 2 0 2 0 2
0 2 0 2 2 0 2 0
0 2 2 0 0 2 2 0
0 2 2 0 2 0 0 2
Which has the lowest possible DP and LP maxes for any 3x3 bijective function
(or bent function for that matter).
> Any objection along the lines of "there are no 3x3 boxes with
> normally-desirable s-box propertly X", need to take into
> account the notion that a much larger number of rounds
> can be afforded, and consequently any resulting differentials,
> swamped.
The problem with 3x3's is that they cannot be used to make (easily) any
power of two function since gcd(3,2^n) is always 1 for any n.
You're right that small (i.e 4x4 => 8x8) sboxes should be used more often
then larger ones but typically that's what alot of ciphers that are popular
do.
Note that "Threeway" aka 3WAY is a design that use a 3x3 sbox in bitslice
mode ...
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: Sat, 05 May 2001 23:15:13 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Actully that is true because modern crypto sytems are so poorly
> designed. I suspect on purpose. But take a system non bijective system
> based on AES ( 256 bit Rijndael ) It works great in the
> forward direction. And lets assume that that for any real input FILE
> it writes an output file.
I agree that alot of cryptosystems (not crypto algorithms) are poorly
written. But I don't agree it's because they don't use "bijective"
functions (note that AES is in fact a bijection it has to be).
> But what about the reverse direction for given keys there are files
> that can't be reveresed. By reverse I mean that can't be mapped back
> to an input file through the decryption process with a key.
> In any nonbijective encryption system there are many such key
> file compbinations that can't be reversed. When you put two of
> these poor system together. You get all the file key combinations
> from second system that can't be reveresed though it Plus every
> file key combination that could not be reverese from the frist
> system Maps through the second system so the density of possible
> files in the finial output starts droping.. Since it was not bijective to
> begin with. So one could hardly expect the combined system to be
> of comparable quality to one based on a key as long as the two
> systems combined.
I agree brute force is possible. You have to realize the number of possible
keys is huge. For a 128-bit block you expect to randomly see an ascii
output from a guessed key about 2^-16 of the time. So if you check 2^40
keys in one day about 2^24 may be the real key. If you check all keys about
2^112 keys will survive. In fact if you had enough time (which is a big
question) you could use 16 known pairs and brute force the key space
repeatedly to find the single remaining key. That would require a bit over
2^128 work for a 128-bit key though and is completely impractical.
Tom
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: 5 May 2001 23:43:24 GMT
[EMAIL PROTECTED] (Tom St Denis) wrote in
<5Q%I6.23930$[EMAIL PROTECTED]>:
>
>"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> Actully that is true because modern crypto sytems are so poorly
>> designed. I suspect on purpose. But take a system non bijective system
>> based on AES ( 256 bit Rijndael ) It works great in the
>> forward direction. And lets assume that that for any real input FILE
>> it writes an output file.
>
>I agree that alot of cryptosystems (not crypto algorithms) are poorly
>written. But I don't agree it's because they don't use "bijective"
>functions (note that AES is in fact a bijection it has to be).
Actually as usually you didn't read what I said. I think its on
purpose it happens so often. Yes of course its a bijection to blocks
that it encrypts. The point is all that is trashed by the time one get
to a PGP or any other type of encryption system. The topic last
brought was about chaining more than one method together. It was
noted that this is usually a poor idea. It usually better to just
try to find one with a longer key. I showed why its usually bad
and a good way to get around it.
I explained and I assume it was over your head. That if Rijndael
is a true 256 bit bijective encryption. Then using a software like
BICOM one can build a true 512 bit system where the whole file
is considered as a full block. This is not the case with the
nonbijective crypto systems.
...
>I agree brute force is possible. You have to realize the number of
>possible keys is huge. For a 128-bit block you expect to randomly see
You agree with what. I never said anything about a blind brute
force search. You keep confusing that fact. That if one shows weakness
it does NOT mean the attacker has to do a blind search. One can show that
fewer keys map to anything. But that in itself does not limit one to
a blind brute force search. All it shows is the information weaknesses
are there. If all weaknesses were done with blind brute force searches
then Engima still would not be broken. But of course you know this
we seem to bring it up over and over and over again. So let me state
it again. I may state many keys lead to situations that an attacker
can imediately tell are bad. But in no way am I limiting an attacker
to use a blind brute force search.
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!
------------------------------
** 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
******************************
