Cryptography-Digest Digest #296, Volume #14 Sat, 5 May 01 14:13:01 EDT
Contents:
Re: Cryptanalysis Question: Determing The Algorithm? ("Douglas A. Gwyn")
Re: Random and not random (Paul Schlyter)
Re: A Question Regarding Backdoors ("Trevor L. Jackson, III")
Re: A Question Regarding Backdoors ("Tom St Denis")
An Empirical Public Key Algorithm Methodology (Jim Steuert)
Re: Random and not random (Mok-Kong Shen)
Re: linear vs nonlinear (Mok-Kong Shen)
Re: linear vs nonlinear (Leonard R. Budney)
Re: Random and not random (Paul Schlyter)
Tiny s-boxes (Tim Tyler)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: Sat, 05 May 2001 11:12:47 GMT
"Bo D�mstedt" wrote:
> ... What you can do is to sequentially test different assumptions,
If you have a whole team, they can test various possibilities in
parallel, and when one of them succeeds in making a definite break
into the system, the rest of the team can be retasked.
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Random and not random
Date: 5 May 2001 12:28:29 +0200
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Given a perfect OTP source, I DO want perfect secrecy. The question
> is whether I am ENTIRELY free to choose a permutation out of the
> ensemble of all possible ones. IF I am ENTIRELY free, THEN by
> 'definition' I CAN choose it in any way I (personally) LIKE,
> including e.g. asking a friend for advise, and that without ANY
> adverse effects. For otherwise I would have to take care to avoid
> possible negative effects and I wouldn't be ENTIRELY free at all.
> Isn't that very clear?
You're not entirely free to rearrange the order of the output of your
OTP source, because your personal preferences may introduce
non-random components into what you'll later use for encryption.
Suppose, for instance, that you picked the output from your OTP, byte
by byte, and rearranged the bytes in ascending or descending order
before using them for encryption, just because you personally LIKED
it that way. Or, even worse, you could take the output of your
perfect OTP source, bit by bit, and then rearrange the bits so you
got all '0' bits first, followed by all '1' bits.... then the first
half of your message would, after "encryption", remain unchanged
while the second half would be XOR'ed with FFh - not a very safe
way to encrypt a message!
To retain the perfect secrecy of your perfect OTP source, you should
not rearrange its outputs in any non-random way.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Sat, 05 May 2001 14:06:44 GMT
Rick Wash wrote:
> "Tom St Denis" <[EMAIL PROTECTED]> writes:
>
> > "Tim Smith" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > On Mon, 30 Apr 2001 11:11:33 GMT, Tom St Denis <[EMAIL PROTECTED]>
> > > wrote:
> > > > Then he should ask the right question which is "Is it legal to
> > > > use > 256-bit symmetric keys in the US". This has nothing todo
> > > > with AES or possible
> > >
> > > That's not the right question. The right question is whether he
> > > has to put a backdoor into his system, which is what he asked. No
> > > one else seems to be having trouble understanding the question, so
> > > the problem is you, not him.
> >
> > To me that's the last thing a serious cryptographer should be
> > asking. Most have problems enough with inadvertant bugs that
> > cripple systems (PGP, Netscape, etc...) let alone intentional bugs
> > or faults.
>
> 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.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Sat, 05 May 2001 14:14:21 GMT
"Trevor L. Jackson, III" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Rick Wash wrote:
>
> > "Tom St Denis" <[EMAIL PROTECTED]> writes:
> >
> > > "Tim Smith" <[EMAIL PROTECTED]> wrote in message
> > > news:[EMAIL PROTECTED]...
> > > > On Mon, 30 Apr 2001 11:11:33 GMT, Tom St Denis
<[EMAIL PROTECTED]>
> > > > wrote:
> > > > > Then he should ask the right question which is "Is it legal to
> > > > > use > 256-bit symmetric keys in the US". This has nothing todo
> > > > > with AES or possible
> > > >
> > > > That's not the right question. The right question is whether he
> > > > has to put a backdoor into his system, which is what he asked. No
> > > > one else seems to be having trouble understanding the question, so
> > > > the problem is you, not him.
> > >
> > > To me that's the last thing a serious cryptographer should be
> > > asking. Most have problems enough with inadvertant bugs that
> > > cripple systems (PGP, Netscape, etc...) let alone intentional bugs
> > > or faults.
> >
> > 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.
Here, here, well said.
Tom
>
------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: An Empirical Public Key Algorithm Methodology
Date: Sat, 05 May 2001 11:08:12 -0400
Reply-To: Jim, Steuert
An Empirical Public Key Algorithm Methodology
Does anyone know of a public key algorithm
methodology like
this. It almost seems to simple. Or perhaps
there is a flaw
I haven't considered.
1) Form a simple feistel (or other simple
like rc4) cipher (and thus it's inverse)
2) Form the boolean equations of the
forward cipher,
say 160 equations in 160 boolean
variables. This
could be very large (many megabytes,
as in the
simulation of the SHA-1 feistel hash
function
in Dean's thesis)
3) Group those equations my randomly
choosing
the variables (there are 160!
(factorial) choices).
4) Publish the re-grouped forward cipher
as the
public key algorithm.
5) Keep the simple feistel algorithm as
the private algorithm.
This works only if the random choice of
boolean groupings
doesn't explode combinatorially and also
hides the initial
feistel (or other simple) cipher algorithm.
Please let me know if anyone has experience
with this
methodology. Or is there some flaw I've
missed. Of course,
it still remains to be proven with a
practical example.
-Jim Steuert
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Sat, 05 May 2001 17:52:28 +0200
Paul Schlyter wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > Given a perfect OTP source, I DO want perfect secrecy. The question
> > is whether I am ENTIRELY free to choose a permutation out of the
> > ensemble of all possible ones. IF I am ENTIRELY free, THEN by
> > 'definition' I CAN choose it in any way I (personally) LIKE,
> > including e.g. asking a friend for advise, and that without ANY
> > adverse effects. For otherwise I would have to take care to avoid
> > possible negative effects and I wouldn't be ENTIRELY free at all.
> > Isn't that very clear?
>
> You're not entirely free to rearrange the order of the output of your
> OTP source, because your personal preferences may introduce
> non-random components into what you'll later use for encryption.
> Suppose, for instance, that you picked the output from your OTP, byte
> by byte, and rearranged the bytes in ascending or descending order
> before using them for encryption, just because you personally LIKED
> it that way. Or, even worse, you could take the output of your
> perfect OTP source, bit by bit, and then rearrange the bits so you
> got all '0' bits first, followed by all '1' bits.... then the first
> half of your message would, after "encryption", remain unchanged
> while the second half would be XOR'ed with FFh - not a very safe
> way to encrypt a message!
>
> To retain the perfect secrecy of your perfect OTP source, you should
> not rearrange its outputs in any non-random way.
You have apparently not closely followed the on-going
discussion. I was saying that it is of no effect whether
a message (as a whole) is encrypted by one segment
of OTP or by another segment, never saying anything
about re-arranging the bits among one and the same
segment. (In the latter case, of course the result will
e non-random in general, just consider the trivial case
of collecting all 0's at the front and 1's at the end!)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: linear vs nonlinear
Date: Sat, 05 May 2001 18:09:05 +0200
"Leonard R. Budney" wrote:
>
[snip]
> (Note that to some mathematicians, *all* rings are commutative, and to
> some mathematicians, *all* rings are commutative and have a 1. To them,
> a field is exactly a ring in which all elements are units, as Tom said.)
0 is an exception of the 'all' above, I believe, hence I
questined the OP.
M. K. Shen
------------------------------
Subject: Re: linear vs nonlinear
From: [EMAIL PROTECTED] (Leonard R. Budney)
Date: 05 May 2001 13:21:37 -0400
Mok-Kong Shen <[EMAIL PROTECTED]> writes:
> "Leonard R. Budney" wrote:
> >
> [snip]
> > (Note that to some mathematicians, *all* rings are commutative, and to
> > some mathematicians, *all* rings are commutative and have a 1. To them,
> > a field is exactly a ring in which all elements are units, as Tom said.)
>
> 0 is an exception of the 'all' above, I believe, hence I
> questined the OP.
{0, +, *} is indeed a commutative ring with 1; it just happens that 1=0.
What is that supposed to prove? And what does it have to do with OTP?
(And note: the 'all' in my statement was not a theorem about rings; it
was an alternate definition. To some people the triple {S, +, *} is
only a ring if both operations are abelian, and if there exists a
multiplicative unity, in addition to the axioms I listed. Some add even
more conditions, like for example "1 != 0".)
Len.
--
Frugal Tip #24:
Never eat pasta when noodles will do just as well.
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Random and not random
Date: 5 May 2001 18:58:16 +0200
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
>Paul Schlyter wrote:
>>
>> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>>
>> > Given a perfect OTP source, I DO want perfect secrecy. The question
>> > is whether I am ENTIRELY free to choose a permutation out of the
>> > ensemble of all possible ones. IF I am ENTIRELY free, THEN by
>> > 'definition' I CAN choose it in any way I (personally) LIKE,
>> > including e.g. asking a friend for advise, and that without ANY
>> > adverse effects. For otherwise I would have to take care to avoid
>> > possible negative effects and I wouldn't be ENTIRELY free at all.
>> > Isn't that very clear?
>>
>> You're not entirely free to rearrange the order of the output of your
>> OTP source, because your personal preferences may introduce
>> non-random components into what you'll later use for encryption.
>> Suppose, for instance, that you picked the output from your OTP, byte
>> by byte, and rearranged the bytes in ascending or descending order
>> before using them for encryption, just because you personally LIKED
>> it that way. Or, even worse, you could take the output of your
>> perfect OTP source, bit by bit, and then rearrange the bits so you
>> got all '0' bits first, followed by all '1' bits.... then the first
>> half of your message would, after "encryption", remain unchanged
>> while the second half would be XOR'ed with FFh - not a very safe
>> way to encrypt a message!
>>
>> To retain the perfect secrecy of your perfect OTP source, you should
>> not rearrange its outputs in any non-random way.
>
>You have apparently not closely followed the on-going
>discussion. I was saying that it is of no effect whether
>a message (as a whole) is encrypted by one segment
>of OTP or by another segment, never saying anything
>about re-arranging the bits among one and the same
>segment. (In the latter case, of course the result will
>e non-random in general, just consider the trivial case
>of collecting all 0's at the front and 1's at the end!)
I guess the same principle applies even for segment
sizes larger than one bit or one byte.
Or we can pick another example: suppose you ran your perfect
OTP generator until it returned a long enough stream of
all zeroes, and then you used that segment to encrypt
your message because "you preferred it that way". Then
your encryption would obviously be extremely weak. The
reason is that you introduced a non-random element,
essentially removing the randomness of your OTP generator.
So, yes if you deliberately choose which segment of the
OTP generator to use, there are cases when this will
seriously weaken your encryption.
It's best to let that perfect OTP generator decide what
you should use to encrypt your messages.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Tiny s-boxes
Reply-To: [EMAIL PROTECTED]
Date: Sat, 5 May 2001 17:55:27 GMT
I've recently become interested in the use of tiny s-boxes again.
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.
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.
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.
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.
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.
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.
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.
However, I beleive this under-estimates the power of the positive things
about small s-boxes - namely small size, rapid operation, speed of
generation, practicality of testing to avoid things like linearity,
and granularity of design.
To elaborate on the last point, one of the good things about using
this sort of "atomic" s-box is that it's easy to add or subtract
confusion in small doses.
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.
At the very least, tiny boxes seem to be of significant interest
to those studing cypher design be scaling things down. At best,
use of huge numbers of tiny s-boxes may prove to be one of the
best way to build block cyphers, at least in hardware.
I've said enough for the moment.
If anyone thinks there are good reasons for the apparent lack of interest
in tiny s-boxes, I'd be delighted to learn what they are.
Similarly if anyone has any good references to previous work relating to
small, nonlinear s-boxes - or studies relating to methods of combining
them - or examining the properties of scaled-down cyphers built with them
I would love to hear about that as well.
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
** 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
******************************
