Cryptography-Digest Digest #300, Volume #14 Sun, 6 May 01 09:13:01 EDT
Contents:
Re: Cryptanalysis Question: Determing The Algorithm? (Paul Schlyter)
Re: _Roswell_ episode crypto puzzle -- THANK YOU! (Paul Schlyter)
Re: Tiny s-boxes ("Tom St Denis")
Re: Tiny s-boxes (Tim Tyler)
Re: Tiny s-boxes ("Tom St Denis")
Re: Cryptanalysis Question: Determing The Algorithm? (SCOTT19U.ZIP_GUY)
Re: Cryptanalysis Question: Determing The Algorithm? ("Tom St Denis")
Re: Best encrypting algoritme (SCOTT19U.ZIP_GUY)
Re: LUCIFER (SCOTT19U.ZIP_GUY)
Re: Best encrypting algoritme ("Tom St Denis")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: 6 May 2001 11:10:34 +0200
In article <[EMAIL PROTECTED]>,
wtshaw <[EMAIL PROTECTED]> wrote:
> 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.
If you include the weak and the not well-tested algorithms -- yes!
However, most of those algorithms can be cracked in ways much more
efficient than brute force key search.
--
================================================================
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: [EMAIL PROTECTED] (Paul Schlyter)
Crossposted-To: rec.puzzles
Subject: Re: _Roswell_ episode crypto puzzle -- THANK YOU!
Date: 6 May 2001 11:11:36 +0200
In article <mJ1J6.243$[EMAIL PROTECTED]>,
Ed Murphy <[EMAIL PROTECTED]> wrote:
> "billt" <[EMAIL PROTECTED]> wrote:
>
>> What else could Mr Sixpack give us that would be incontrovertible proof of
>> his visit?
>
> Frequency, direction, and date/time of an alien communication, i.e. the data
> point on which SETI will succeed.
>
> Instructions for creating something unknown to modern human science: a cure
> for disease, a stable transuranic element, anti-gravity, matter duplication
> or teleportation or (non-radioactive-breakdown) transmutation.
Or a detalied map of some solar-system body, or part of it, which we
haven't yet seen in detail. Before 1959 a map of the far side of our
own Moon would have served well. Today, a detailed map of that half
of Mercury not seen by Mariner 10 (the only spacecraft which so far
has visited Mercury), or of Pluto, or of those parts of Saturn's and
Uranus' moons not seen by the Voyagers, would serve fine. Time is
running out for Saturn's moons though, since the Cassini spacecraft
will arrive there in a few years, most likely filling in some major
holes in our maps of Saturn's satellites.
--
================================================================
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: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: Sun, 06 May 2001 11:29:56 GMT
"Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote in message
news:9d32as$q2m$[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
> news:B43J6.24319$[EMAIL PROTECTED]...
> >
> > "Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote in message
> > news:9d25ej$462$[EMAIL PROTECTED]...
> > > It might depend on how you define "generally" and "s-box", but you
don't
> > > suggest that a random state of RC4 would be unsafe for that reason?
More
> > > precisely, I mean that how safe an s-box is depends on the context of
> its
> > > application in the cipher algorithm. But I guess you knew that already
> and
> > > that you are talking about fairly conventional block ciphers.
> >
> > Biham proved (for example) random 6x4's are insecure for the most part
in
> > DES.
> >
> > There is nothing to suggest that random sboxes are ideal unless they are
> > constrained (i.e like in Twofish).
>
>
> Yes, there is: The mere number of them. 2^n < n! < n^n, so n! is of
> exponential order. If the algorithm is such that it would take an attacker
> with access to chosen plain text at least polynomial time to separate the
> impact of each element of each s-box from the impact of any other, then I
> can't see why random s-boxes can't be used.
It depends on the structure of the cipher. You can't just play the big
numbers game and wait for someone to show you why!
In DES for example most sboxes don't have the required differential patterns
and are easily attackable with a known attack.
Tom
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Reply-To: [EMAIL PROTECTED]
Date: Sun, 6 May 2001 11:24:25 GMT
Paul Rubin <[EMAIL PROTECTED]> wrote:
: Tim Tyler <[EMAIL PROTECTED]> writes:
:> Thanks also to David for directing me towards 3WAY. So far I have not yet
:> managed to find out very much about it - besides its use of tiny boxes -
:> and the fact that it uses a block size that is divisible by three.
: 3way is described in Applied Cryptography.
Thanks. I /did/ look there - but I went to the index - and there were
no entries under "3" or the author's name...
I'm there now - the contents page sorted me out ;-)
: I don't remember much about it, except looking over the description and
: noticing it needed very little memory and was therefore a good
: candidate for small embedded processors.
FWIW, http://www.torus.ndirect.co.uk/encryption/algorithms.html lists an
attack on it.
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: Sun, 06 May 2001 11:37:44 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> :> 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. [...]
>
> I thought that it was generally accepted. The idea is that the
> probability of choosing a weak, linear s-box (if choosing at random) is
> high when the box size is small, and becomes vanishingly small when the
> box size becomes large. Other desirable s-box characteristics (except
> small implementation size :->) also improve with the number of box inputs.
>
> You're perfectly correct to say that large s-boxes are unlikely to be
> "perfect" (in terms of maximum non-linearity, etc), but - so the
> thinking goes - if you make them large enough the differences
> from the ideal really don't matter, and testing them is of little
> practical benefit. Indeed, if only you could make them the width of the
> block, all your problems would be solved ;-)
It depends on the cipher. If you're round function is a random 32x32 I
would bet nobody can crack your cipher. On the other hand nobody can *use*
your cipher. I've mentioned DES but also Serpent and ICE are two others
ciphers that wouldn't be ideal with random boxes.
> :> 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. [...]
>
> Software is probably not where tiny s-boxes shine. I tend to try to
> design for hardware - since I think today's software systems suck, and
> some day not so far away, programmable logic will become ubiquitous ;-)
>
> To be honest I haven't yet investigated in any depth how best to
> implement tiny s-boxes in software.
Generally in software you group the bits. I.e two 4x4's into one 8x8 etc...
> [snip speed]
>
> :> 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".
>
> I'm aware of the problems with GOST - but I needed to mention it.
>
> Please pretend that the "strong" referred only to Serpent ;-)
Hmm ok :-)
> : If you want some ideal ciphers with small sboxes look at Square,
> : Rijndael, Twofish, DES, Serpent...
>
> I think your idea of "small" must include 8x8 boxes...
To me 8x8's are small.
> :> The other is *tiny* s-boxes themselves [i.e.] 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 [...]
>
> Yes, I'm well aware of that. Proposing that s-boxes be constructed at a
> size where nonlinear boxes are an impossibility (e.g. 2x2 s-boxes) would
> have been an exceptionally stupid move on my part ;-)
Hehehehe.
> :> 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.
>
> To my mind, that's no great problem. *If* tiny s-boxes are interesting,
> the fact that a few bits in every round in a 2^n bit block cypher won't
> make it through one of them seems like a matter of relatively minor
> concern.
>
> You could make sure its not the same bits in each round - and
> add a couple of rounds at the end to compensate.
>
> Alternatively you could try making a fast "algebraic" 4x4 or 5x5 s-box
> and use one of those instead.
Fast algebraic 4x4? Try inversion in GF(2^4), or raising elements to the
seventh power in GF(2^4) (which is not as good as the former but can be
implemented using four GF mults).
> : You're right that small (i.e 4x4 => 8x8) sboxes should be used more
> : often then larger ones [...]
>
> Well, as far as I understand it, this isn't terribly widely accepted.
How so? Twofish, Serpent, Rijndael, DES, GOST, SAFER, etc... are all
ciphers using 4x4 to 8x8 sized transforms.
Tom
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: 6 May 2001 12:14:15 GMT
[EMAIL PROTECTED] (Tom St Denis) wrote in
<RL4J6.25468$[EMAIL PROTECTED]>:
>
>"Actaully most files would not be a valid output of the two systems..."
>[sic]. How would you know that before decrypting the blocks?
>
Tom I know that from having tested many systems. Something
appearently you don't do. It's not like its that hard to test.
You can even use most systems and try to remove the known haeaders
around the encrypted code. Replacing the blocks containing the
final cyrtpo will usually not reslut in comthing that can be
decrypted. and encrypted back to itself. Take a few systems your
self and see. Then try. BICOM it works either way in both directions
something you appearently are to lazy to look at. Even though
its useing full Rinjdael. Its just Matt decided to do it right.
Something that others refuse to do or are intimidated to do in
the proper way. Try a system of your own creation using deflate
leave off checksums and try to mate it with Rijndeal. Then test
yourself. It might surprise you even when you try to do it right
its hard to get even close to 50%. Thats why when I wrote the
creators of Rijndeal they said Matts program not possible they
are under the false belied that you can't make a fully bijective
crypto system using significant compression with full size
rijndael blocks they are wrong and seem to be very ignorant in that
area or are they trying to hid something.
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: Cryptanalysis Question: Determing The Algorithm?
Date: Sun, 06 May 2001 12:37:38 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Tom St Denis) wrote in
> <RL4J6.25468$[EMAIL PROTECTED]>:
>
> >
> >"Actaully most files would not be a valid output of the two systems..."
> >[sic]. How would you know that before decrypting the blocks?
> >
>
> Tom I know that from having tested many systems. Something
> appearently you don't do. It's not like its that hard to test.
Ok given the ciphertext C=EAFB1234BEEFAB1 from RC5 (W=32, R=12), tell me
how you can tell if any key K could be the real key without trial
decryption? If you can do this I will give you 100 billion dollars (j/k).
Seriously if you can do this you should publish your findings for you just
broke RC5.
I bet you can't and won't and you will go on a wild tangent about how much
BICOM is better. (please prove me wrong here!)
Also another flaw in your arguments. To say X is better than Y, you must
prove that Y is worse than X. Please do that !
Tom
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best encrypting algoritme
Date: 6 May 2001 12:35:49 GMT
[EMAIL PROTECTED] (Tom St Denis) wrote in
<BR4J6.25523$[EMAIL PROTECTED]>:
>
>I still don't get your main points. If the system is a FSM (Finite
>State Machine) such as any computer program (they must be finite) then
>there are only a *finite* amount of states the program can be in. This
>means that no matter what you do, if it's a FSM then I can write a
>program to brute force it. There is no way to escape this logic. You
>can only make brute force impractical (i.e huge key, or something to
>that effect).
Tom what you lack and refuse to learn or even seem to engage your
brain is. I could write a cyrpto system with even a 1 byte block
size. and 2 bits of key space. Lets say I take my messages I don't
have many but I compress them done using bijective compression.
and then encrypt that bijectively compressed message with a 2 bit
key using bijective encryption.If you write a super duper brute force
machine you may get all of the 4 message I may of sent. There may have been
407 messages. You have reduced it to 4. Know which message is it.
The four are all equally likely.
Yes when we go to longer message and longer keys. Many of the
messages may not make sense. Since its hard to write a compressor
for just the messages one might use. However the compressor can be tuned
to the kind of messages we want to send. And if key long enough there
will be many possible message that a key could map the encrypted
message to.
The point is why use an inferior system that allows most
ciphertext message key combinations to be rejected as not
even being possible. Knowing squat about the input. It also
harder for the NSA to hid trap doors in the combination crypto
system if its fully bijective. Something that you think would be
of interest to the crypto community. Though one can still add
trap doors of a type. But thats another topic that I may explain
someday to you once you understand the concepts involved here.
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: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: LUCIFER
Date: 6 May 2001 12:46:47 GMT
[EMAIL PROTECTED] (Paul Rubin) wrote in
<[EMAIL PROTECTED]>:
>I'd say look in the bibliography to Applied Cryptography (my copy is
>not handy). It is very extensive and would probably have what you want,
>if it exists.
>
>Don Coppersmith described Lucifer briefly in his talk on DES at Crypto
>2000. It was a 32-bit block cipher with 128-bit keys(?), but I don't
>remember more. The 32-bit block size is the part that seems amusing now.
Well unless JS is full of crap. The pointer to his page provided by
tim
says "LUCIFER enciphered blocks of 128 bits, and it used a 128-bit key."
I don't see that it was a 32 bit block size. Maybe the NSA has different
veriosn of LUCIFER hanging around so they can pretend DES was designed
to be secure.
However an encryption program can get along on 32 bits.
as a sub unit if they are not directly visable to the out side.
I think scott19u with its use of 19bit blocks is orders of magnitude
more secure than any to the 5 finailists in AES. But then they are
forced to use fast small keyed programs. So the NSA can still stay
on top of things.
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: Best encrypting algoritme
Date: Sun, 06 May 2001 12:58:37 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Tom St Denis) wrote in
> <BR4J6.25523$[EMAIL PROTECTED]>:
>
> >
> >I still don't get your main points. If the system is a FSM (Finite
> >State Machine) such as any computer program (they must be finite) then
> >there are only a *finite* amount of states the program can be in. This
> >means that no matter what you do, if it's a FSM then I can write a
> >program to brute force it. There is no way to escape this logic. You
> >can only make brute force impractical (i.e huge key, or something to
> >that effect).
>
> Tom what you lack and refuse to learn or even seem to engage your
> brain is. I could write a cyrpto system with even a 1 byte block
> size. and 2 bits of key space. Lets say I take my messages I don't
> have many but I compress them done using bijective compression.
> and then encrypt that bijectively compressed message with a 2 bit
> key using bijective encryption.If you write a super duper brute force
> machine you may get all of the 4 message I may of sent. There may have
been
> 407 messages. You have reduced it to 4. Know which message is it.
> The four are all equally likely.
Yeah but you can't break a real cipher even in ECB mode with a single block.
If you gave me say 15, 1-byte blocks with this 2-bit key I could figure out
what the key is. No matter what you do.
Face it if your system is not an OTP it's not universally secure.
> Yes when we go to longer message and longer keys. Many of the
> messages may not make sense. Since its hard to write a compressor
> for just the messages one might use. However the compressor can be tuned
> to the kind of messages we want to send. And if key long enough there
> will be many possible message that a key could map the encrypted
> message to.
Still in the end only one message will make sense. It's not an OTP so this
must be true. Of course the more texts you gather the higher your chances
of success. For example with one AES block (16 bytes) there are probably
around 2^50 plausible english ascii blocks (that look right). However with
the same key and two blocks the chances are even lower that the message
still makes sense. Again with three blocks even lower, etc... Finally you
gather N texts and find that out of all the ciphertexts only one key maps to
a plausible plaintext. That's cryptanalysis.
> The point is why use an inferior system that allows most
> ciphertext message key combinations to be rejected as not
> even being possible. Knowing squat about the input. It also
> harder for the NSA to hid trap doors in the combination crypto
> system if its fully bijective. Something that you think would be
> of interest to the crypto community. Though one can still add
> trap doors of a type. But thats another topic that I may explain
> someday to you once you understand the concepts involved here.
Again you have to show how you can suggest the correct key other than trial
decryptions. Why not answer me that? HOW DO YOU KNOW THE KEY IS WRONG
WITHOUT FIRST DECRYPTING.
Tom
------------------------------
** 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
******************************
