Cryptography-Digest Digest #298, Volume #14 Sun, 6 May 01 01:13:00 EDT
Contents:
Re: Tiny s-boxes ("Henrick Hellstr�m")
RFC: LFSR's with very large registers (David Bernier)
Re: RFC: LFSR's with very large registers (David Wagner)
Re: SRP attack? (Thomas Wu)
Re: Rijndael Galois Field construction problem. (Walter Hofmann)
Re: _Roswell_ episode crypto puzzle -- THANK YOU! ("Ed Murphy")
Re: Tiny s-boxes ("Tom St Denis")
Re: Cryptanalysis Question: Determing The Algorithm? ("Tom St Denis")
Re: RFC: LFSR's with very large registers (David Bernier)
Re: SRP attack? (Paul Crowley)
Re: Best encrypting algoritme (Paul Crowley)
Re: Cryptanalysis Question: Determing The Algorithm? (SCOTT19U.ZIP_GUY)
Re: Best encrypting algoritme (SCOTT19U.ZIP_GUY)
Re: Cryptanalysis Question: Determing The Algorithm? ("Tom St Denis")
Re: Best encrypting algoritme ("Tom St Denis")
----------------------------------------------------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: Sun, 6 May 2001 02:21:07 +0200
"Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
news:9M%I6.23913$[EMAIL PROTECTED]...
>
> "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
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.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: David Bernier <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: RFC: LFSR's with very large registers
Date: Sat, 05 May 2001 20:51:06 -0400
I've been thinking about LFSR's with very large registers.
Suppose someone adds 128 Mb of RAM to their PC dedicated
to storing an LFSR register. Suppose we index the register bytes as
b_1, ... b_{2^27}. [ 2^27 = 128*2^20 = 128 M, where M = 1,048,576 ].
The tap positions are 1, i_1, i_2, i_3, i_4 with
1< i_1 < i_2 < i_3 < i_4 <= 128 M.
So we are XOR'ing whole bytes at a time, e.g.
11001010 XOR 00100111 = 11101101 .
The secret key is (i_1, i_2, i_3, i_4).
So the keyspace has cardinality:
C(128M -1, 4) ~= 2^103 .
That makes exhaustive key search quite impractical
as a method of attack.
The other attack is brute linear algebra:
solving a ~ 256 M by 256 M linear system
where one row would consist of (say)
the first bit of ~ 256 M consecutive bytes
of keystream. The complexity of this
is something like (256 M)^3 /6 or about
2^81 .
However, one would need to use about
256 M * 256 M bits of memory or
about 8000 terabytes...
So one would have to use
secondary storage unless one had
8000 terabytes of main memory.
The two questions I have are:
(1) Could one do better than an
average ~ 2^81 ops attack and
if so how?
(2) How fast would keystream production be?
I count 5 reads from main memory
and one write just to produce
one byte of new keystream.
(plus a bit of arithmetic)
On a 133 MHz bus, that would imply
a maximum keystream production rate of at most
2.7 megabytes per second...
Note: Extra RAM: 128 Mb SDRAM 133MHz [168Pins] : cost = $CAN 49
----
David Bernier
--
davidp_bernier !!!!!!!!!! at &&&& yahoo [[]] dot ????
com
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: RFC: LFSR's with very large registers
Date: 6 May 2001 00:55:22 GMT
I believe that Berlekamp-Massey requires "only" quadratic time, not cubic,
and I suspect the memory requirements will only be linear. However, I don't
know whether this is the best attack or not. (The sparse feedback taps might
make cryptanalysis easier.)
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: SRP attack?
Date: 05 May 2001 18:05:46 -0700
"Michael Scott" <[EMAIL PROTECTED]> writes:
>
> A clearly desirable property of such protocols is that an active attacker
> masquerading as either the client or the server should be able to eliminate
> only one candidate secret x =H(s,P) with each attempt, where P is the
> password under attack. Clearly it is impossible to do any better than this.
> In fact a masquerading server, Stevie, can eliminate two candidate passwords
> P1 and P2 at once. The SRP paper in fact makes no claims in this regard, so
> perhaps this is not regarded as significant. Let x=H(s,P1) and y=H(s,P2).
It looks like the ability to check two passwords is dependent on the
symmetry of the B calculation. One easy way to fix this would be to
remove the symmetry, e.g. make B=g^b+r*g^x, where r=hash(N,g).
> Mike Scott
Tom
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: [EMAIL PROTECTED] (Walter Hofmann)
Subject: Re: Rijndael Galois Field construction problem.
Date: Sun, 6 May 2001 02:53:05 +0200
Reply-To: [EMAIL PROTECTED]
On Fri, 04 May 2001 16:35:31 GMT, Tom St Denis <[EMAIL PROTECTED]> wrote:
>
>> All elements but 0 of a field are invertible. Thats the definition of a
>> field.
>
>No that isn't. A field must have all the qualtiies of a ring and also
>...
OK. "...that is PART OF the definition..."
Walter
------------------------------
From: "Ed Murphy" <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles
Subject: Re: _Roswell_ episode crypto puzzle -- THANK YOU!
Date: Sat, 5 May 2001 16:24:44 -0700
"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.
--
Ed Murphy <[EMAIL PROTECTED]> http://members.fortunecity.com/emurphy/
"Most of the time, it seemed sublimely unaware of its limbs,
though it was beginning to suspect it had hands."
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: Sun, 06 May 2001 02:57:37 GMT
"Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote in message
news:9d25ej$462$[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
> news:9M%I6.23913$[EMAIL PROTECTED]...
> >
> > "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
>
> 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).
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: Sun, 06 May 2001 03:00:05 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [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.
Hmm I can write an app to brute force any cryptosystem. That's just the
laws of FSMs. I don't see how magic transforms can get around that.
> 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.
Well AES is a 128-bit transform so obviously it's not a "256-bit bijective
encryption" whatever that means. You can use chaining modes, etc to encode
256-bit messages though.
>
> >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.
How can you tell that the 128-bit key
111111110100000000111111110001111001001010101111010000010.... is immediately
bad without trial decryptions?
Tom
------------------------------
From: David Bernier <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: RFC: LFSR's with very large registers
Date: Sat, 05 May 2001 23:34:36 -0400
David Wagner wrote :
> I believe that Berlekamp-Massey requires "only" quadratic time, not cubic,
> and I suspect the memory requirements will only be linear. However, I don't
> know whether this is the best attack or not. (The sparse feedback taps might
> make cryptanalysis easier.)
Right. I looked it up in ``Handbook of Applied Cryptography" by Menezes, van Oorschot
and
Vanstone.
>From Section 6.2 (6.2.3):
``6.32 Fact The running time of the Berlekamp-Massey algorithm (Algorithm 6.30)
for deter-
mining the linear complexity of a binary sequence of bitlength n is
O(n2) bit operations."
Surprising (to me)...
David Bernier
------------------------------
Subject: Re: SRP attack?
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Sun, 06 May 2001 03:41:13 GMT
"Michael Scott" <[EMAIL PROTECTED]> writes:
> I think I have a sort of attack against the SRP log-in protocol, as
> described in
> http://www-cs-students.stanford.edu/~tjw/srp/doc.html.
>
> Its not by any means a devastating attack, but interesting I think
> nonetheless.
This seems right to me. Nice result! I have a similar attack against
another password protocol, you've motivated me to write it up now.
Thanks!
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
Club event for 30th birthday, Sunday 6th May: www.ciphergoth.org/xxx
------------------------------
Subject: Re: Best encrypting algoritme
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Sun, 06 May 2001 03:41:13 GMT
"david" <[EMAIL PROTECTED]> writes:
> Im making a backup program, and I don'treally know what is the most secure
> algoritme, im using Rijndael rigth now and using 256 bit keys, are rc6
> stronger or are there others??
Rijndael, at any key length, will certainly never be the weakest link
of your system, and is the correct choice since it is on the way to
becoming a national and hopefully an international standard. Remember
to use an appropriate chaining mode.
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
Club event for 30th birthday, Sunday 6th May: www.ciphergoth.org/xxx
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: 6 May 2001 03:53:00 GMT
[EMAIL PROTECTED] (Tom St Denis) wrote in
<V63J6.24331$[EMAIL PROTECTED]>:
You missed the point above so I just cut 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.
>
>Well AES is a 128-bit transform so obviously it's not a "256-bit
>bijective encryption" whatever that means. You can use chaining modes,
>etc to encode 256-bit messages though.
I am saying the key is 256 bits. I know the internal block is 128 bits.
Below I am saying if you combine two rijndael encryption using something
written correctly like BICOM you can get a crypto system that works
on any file and has 512 bit keys while the whole file is the actual
single block. And in such a sytem any file can be thought of as an
input file or any output file. And file can be encrypted with any key
and any file can be uniquely decrypted with any key.
>
>>
>> >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.
>
>How can you tell that the 128-bit key
>
>111111110100000000111111110001111001001010101111010000010.... is
>immediately bad without trial decryptions?
>
Well if the system was constructed properly in a bijective
way using BICOM you couldn't becasue it does have the flaws of
most cyrpto systems.
But if you made a 2 part encryption system using delate
with BLOWFISH use what ever mode you want. And then combined
it with another system using RINJNDAEL with deflate again.
and pad to full block sizes using the blessed nonbijective
ways. There would be many files. Actaully most files would not
be a valid output of the two systems. I would not be surprised
if based on cipher intercept attacks only the NSA may be using
sophisticated pattern recognition software. That not only can
tell what the input was put which standard methods you used to
make the encryption. This is becasue the nonbijective methods
that everyone loves adds information to the systems. The NSA
is not totally stupid. At least for the billions we spend on
them I hope they are not totally stupid. They don't need to
test the key. The key you mentioned may in a class that they
could imediately tell could not have produced the output
seen in some long encrypted file they are looking at. Or
if it is in the class that made the possible output they
then just test the few keys left.
I can't write a long system for you. But toy ones with short
key of 2 to 3 bits can be used to illustrate the concepts.
But I see most methods do add info that the NSA could if doing
there job exploit.
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: Best encrypting algoritme
Date: 6 May 2001 04:00:47 GMT
[EMAIL PROTECTED] (Paul Crowley) wrote in
<[EMAIL PROTECTED]>:
>"david" <[EMAIL PROTECTED]> writes:
>> Im making a backup program, and I don'treally know what is the most
>> secure algoritme, im using Rijndael rigth now and using 256 bit keys,
>> are rc6 stronger or are there others??
>
>Rijndael, at any key length, will certainly never be the weakest link
>of your system, and is the correct choice since it is on the way to
>becoming a national and hopefully an international standard. Remember
>to use an appropriate chaining mode.
Pray tell what do you consider an appropriate chaining mode. Since
its obvious your begging someone to ask and are chopping at the bite
so the world will know. I hope only crooks and international terrorists
use the appropriate AES encryption methods in the standard non bijective
packages so the NSA can continue to read there mail and then the hard
part get the info to the coreect place with out a bunch of idoit managers
putting there own poltically correct spin on the data.
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 04:52:01 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Tom St Denis) wrote in
> <V63J6.24331$[EMAIL PROTECTED]>:
> But if you made a 2 part encryption system using delate
> with BLOWFISH use what ever mode you want. And then combined
> it with another system using RINJNDAEL with deflate again.
> and pad to full block sizes using the blessed nonbijective
> ways. There would be many files. Actaully most files would not
> be a valid output of the two systems. I would not be surprised
> if based on cipher intercept attacks only the NSA may be using
> sophisticated pattern recognition software. That not only can
> tell what the input was put which standard methods you used to
> make the encryption. This is becasue the nonbijective methods
> that everyone loves adds information to the systems. The NSA
> is not totally stupid. At least for the billions we spend on
> them I hope they are not totally stupid. They don't need to
> test the key. The key you mentioned may in a class that they
> could imediately tell could not have produced the output
> seen in some long encrypted file they are looking at. Or
> if it is in the class that made the possible output they
> then just test the few keys left.
"Actaully most files would not be a valid output of the two systems..."
[sic]. How would you know that before decrypting the blocks?
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best encrypting algoritme
Date: Sun, 06 May 2001 04:58:09 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Paul Crowley) wrote in
> <[EMAIL PROTECTED]>:
>
> >"david" <[EMAIL PROTECTED]> writes:
> >> Im making a backup program, and I don'treally know what is the most
> >> secure algoritme, im using Rijndael rigth now and using 256 bit keys,
> >> are rc6 stronger or are there others??
> >
> >Rijndael, at any key length, will certainly never be the weakest link
> >of your system, and is the correct choice since it is on the way to
> >becoming a national and hopefully an international standard. Remember
> >to use an appropriate chaining mode.
>
> Pray tell what do you consider an appropriate chaining mode. Since
> its obvious your begging someone to ask and are chopping at the bite
> so the world will know. I hope only crooks and international terrorists
> use the appropriate AES encryption methods in the standard non bijective
> packages so the NSA can continue to read there mail and then the hard
> part get the info to the coreect place with out a bunch of idoit managers
> putting there own poltically correct spin on the data.
Again you have yet to conclusively prove beyond insults and wand waving that
"bijective encodings" are any better or more secure then say a CTR-mode
encrypted file using AES as the transform function. (CTR being the counter
encryption mode where you encrypt a binary counter)
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).
Now your big challenge (if you really are up to it) is find a break on say
CBC or CTR mode encrypted messages (of realistic length) that would not work
against "bijective encoded" messages.
Also your "they will not use blind key-search methods" needs clarification.
Given the ciphertext C and language L, how can you immediately throw out
keys K such that K will not transform C into an element of the set L without
first decrypting the text? Let's use a context. For example you are given
a 128-bit C from AES, how can you tell without decrypting what keys will
lead to non-ascii messages? If you can do this you have broken AES and I
say "congrats".
And please don't bring the NSA into this. This is serious crypto talk here
no "magic conspiracy" crap.
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
******************************
