Cryptography-Digest Digest #49, Volume #14 Sat, 31 Mar 01 01:13:01 EST
Contents:
Re: new sboxgen :-) ("Tom St Denis")
Re: conferences? ("Tom St Denis")
Re: conferences? ("Tom St Denis")
Re: conferences? ("Tom St Denis")
Re: Idea - (LONG) (Benjamin Goldberg)
Re: What do we mean when we say a cipher is broken? (Paul Crowley)
Re: Idea - (LONG) (Rob Warnock)
Re: new sboxgen :-) (Benjamin Goldberg)
Re: new sboxgen :-) ("Tom St Denis")
Re: Idea - (LONG) (Rob Warnock)
Eric Lee Green & Co + Anti Evidence Eliminator Fake Spammers FBI Task Force
Authority (Anonymous)
Re: What do we mean when we say a cipher is broken? (Paul Rubin)
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: new sboxgen :-)
Date: Sat, 31 Mar 2001 05:15:50 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9a3nj1$2th$[EMAIL PROTECTED]...
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:1Fax6.167489$[EMAIL PROTECTED]...
> >
> > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > news:9a3bu6$h35$[EMAIL PROTECTED]...
> > >
> > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > news:rH9x6.166677$[EMAIL PROTECTED]...
> > > > I updated my sboxgen program... it can now make bijective sboxes
(that
> > are
> > > > their own inverse) using a 2-function 3-round feistel. It outputs
the
> > > > feistel round functions too. Obviously the smallest sbox you can
make
> > > with
> > > > this is 6x6 since 2x2 functions can't be non-linear (and the size of
> the
> > > > sbox must be even!)
> > > Off the top of my head, I'd be rather cautious about self-inverting
> > sboxes.
> > > One obvious differential they may be prone to is when on input, the
> inputs
> > > on the two sides of the differential are X and Y, and it just happens
> that
> > > SBox[X]==Y. Then, on output, the two sides of the differential are Y
> and
> > X,
> > > and this happens considerably more often than on a random SBox.
> > >
> > > I'm not sure how this would be of use attacking a real cipher, but it
> > looks
> > > like something to be wary about.
> > >
> >
> > Even if that does occur it happens with a bounded probability.
>
> Well, yes, but that bound is considerably higher than the corresponding
> bound on an arbitrary sbox. And, the bound can be reduced only be making
> the sbox bigger, not by choosing a better sbox.
Ahh, well making an 8x8 with this method I have reduced the DPmax to 10/256
using five-rounds in the feistel. That means even your condition is bounded
by 10/256.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: conferences?
Date: Sat, 31 Mar 2001 05:17:18 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9a3n95$v6m$[EMAIL PROTECTED]...
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:D5dx6.169576$[EMAIL PROTECTED]...
> > I just finished a design for a simple cipher based on MDS matrices and a
> FFT
> > like network (like CS-Cipher) the idea is to make the encryption really
> > simple and use it in CTR mode. The cipher takes a 192-bit key and a
> 64-bit
> > block (i.e you encrypt the 64-bit counter and xor it against the msg as
> > required).
> >
> > I was wondering what conferences this type of cipher would be relevant
> too.
> Selected Areas in Cryptography would be one idea. It's in Toronto this
> year, so it might be not that far for you in any case.
Would you (or anyone else) be interested in helping me write the paper
(possibly co-author?). My cipher is conceptually easy to cryptanalyze which
is nice :-). And it's fast. My unrolled C code can encrypt 1000 blocks in
about 2.5 seconds on an 8051. Obviously not super fast but not bad... the
cipher is very simple so making it faster is a matter of writting it in
assembly...
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: conferences?
Date: Sat, 31 Mar 2001 05:19:48 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9a3o97$2s9$[EMAIL PROTECTED]...
>
> Paul Rubin <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Tom St Denis" <[EMAIL PROTECTED]> writes:
> > > I just finished a design for a simple cipher based on MDS matrices and
a
> FFT
> > > like network (like CS-Cipher) the idea is to make the encryption
really
> > > simple and use it in CTR mode. The cipher takes a 192-bit key and a
> 64-bit
> > > block (i.e you encrypt the 64-bit counter and xor it against the msg
as
> > > required).
> BTW: why counter mode, in particular? Counter mode isn't bad, but one of
> the things nice about block ciphers is there are so many useful things you
> can do with a keyed permutation, and turning it into a keystream generator
> via counter mode is only one of them. Or, is there something about your
> cipher that makes it especially appropriate for counter mode?
>
> Oh, and unless your block cipher isn't invertable, you do realize there is
a
> distinguishing attack after 2**32 blocks == 2**35 bytes, simply because
> after that much keystream, an attacker would expect to see duplicated
blocks
> in a random stream, and never see such a duplicated block from your
output?
My cipher is bijective, it's just more efficient in the forward direction.
So I mainly concentrated on making the encryption routine fast and small.
You can still use the cipher as a primitive, just don't use the backwards
direction.
> >
> > > I was wondering what conferences this type of cipher would be relevant
> too.
> >
> > Stop designing ciphers and start breaking ciphers other people have
> designed.
> > But you knew that already.
>
> But, if we all just sat around and broke ciphers, who'd be designing the
> ciphers for us to break? :-)
>
> But, seriously, it *is* much easier to get a cryptanalytic result
published
> than it is to get a new cipher published.
True, but two problems. a) I lack the math to make a "new break" and b)
nobody cares about a break that's been done before. I can't really attack
Twofish for example since it's been designed against all the attacks I know
off and well... my level of math makes designing new attacks hard (not to
mention my isolation from other cryptographers...)
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: conferences?
Date: Sat, 31 Mar 2001 05:24:28 GMT
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> writes:
> > I just finished a design for a simple cipher based on MDS matrices and a
FFT
> > like network (like CS-Cipher) the idea is to make the encryption really
> > simple and use it in CTR mode. The cipher takes a 192-bit key and a
64-bit
> > block (i.e you encrypt the 64-bit counter and xor it against the msg as
> > required).
> >
> > I was wondering what conferences this type of cipher would be relevant
too.
>
> More seriously than in previous post, the Fast Software Encryption
> workshop comes to mind, and the IACR conference referees actually look
> at submissions like that. But really, can you explain what an MDS
> matrix is? Can you explain what an FFT is? Why would you those
> things to be relevant to your cipher's security?
MDS is a maximal distance separable linear transform (in any cyclic field
such as GF) that has the property that the two n-element tuples differ by a
maximal n+1 elements. In my case I use
[2 1]
[1 1]
in GF(2^8) where the modulus is the polynomial given by 0x169 (....
expanding that to binary requires thought... it's 12am...)
An FFT is a discrete transform from the spatial domain to the spectral. The
FFT has a data flow network such that the number of operations required
before every output is a linear function of the input is minimal, namely
O(log2(N) + N/2).
The cipher is better in the encryption direction since the matrix [2 1] ..
[1 1] is simple to implement... a multiplication of 2 is basically computed
via
if (x & 0x80)
return (x << 1) ^ 0x69;
else
return x <<1;
(C notation). I can even precompute this easily...
Does this help?
Tom
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Idea - (LONG)
Date: Sat, 31 Mar 2001 05:32:37 GMT
David Wagner wrote:
>
> John A. Malley wrote:
> >Can we construct a block cipher with perfect secrecy by cascading
> >substitution and transposition "units" in some sequence?
>
> Not unless you use really large S-boxes or enormous numbers of rounds.
> Think: to have perfect secrecy, you need (2^n)! bits of key. Each
> transposition layer can use at most n! bits of key. A m-bit S-box can
> take advantage of only (2^m)! bits of key. Thus, you'd something like
> (2^n)! / (2^m)! copies of such a S-box, and this number is basically
> enormous unless n=m.
>
> However, maybe you'd be happy with something less than perfect
> secrecy.
> Say you want a block cipher that's information-theoretically secure as
> long as it is used to encrypt no more than o(2^{n/4}) blocks. You can
> achieve this using a 4-round Feistel cipher where each round uses a
> random function with n/2-bit inputs and n/2-bit outputs. By a theorem
> of Luby and Rackoff, this is secure for up to o(2^{n/4}) encryptions.
> Note that such a cipher requires only 4 * (2^{n/2})! << (2^n)! bits of
> key.
If one assumes that all of it's component sboxen (which are part of the
key) are randomly selected (not psuedorandomly selected), is the turtle
block cipher information- theoretically secure for any number of blocks?
Yes, I realize that in the paper describing turtle, the sboxes which are
part of the key are psuedorandomly created by shuffling with the byte
array key.
For those who aren't familiar with the turtle cipher, here's some sample
code:
void turtle_encrypt(unsigned char *block, TK *key) {
int nn = key->n >> 1; // key->n is the blocksize, a power of 2
int r = 0;
turtle_r( block+nn, block, nn, key, &r );
turtle_r( block, block+nn, nn, key, &r );
turtle_r( block+nn, block, nn, key, &r );
turtle_r( block, block+nn, nn, key, &r );
}
void turtle_decrypt(unsigned char *block, TK *key) {
int nn = key->n >> 1;
int rr = nn*nn, r;
r = rr*3; turtle_r( block+nn, block, nn, key, &r );
r = rr*2; turtle_r( block, block+nn, nn, key, &r );
r = rr; turtle_r( block+nn, block, nn, key, &r );
r = 0; turtle_r( block, block+nn, nn, key, &r );
}
static void turtle_r(
unsigned char *target, const unsigned char *source,
int n, TK* key, int* r)
{
if( n == 2 ) {
int x0 = source[0], x1 = source[1];
x1 ^= key->sbox[*r++][x0];
x0 ^= key->sbox[*r++][x1];
x1 ^= key->sbox[*r++][x0];
x0 ^= key->sbox[*r++][x1];
target[0] ^= x0; target[1] ^= x1;
} else {
int nn = n >> 1, i;
unsigned char block[16];
for( i = 0; i < n; ++i )
block[i] = source[i];
turtle_r( block+nn, block, nn, key, r );
turtle_r( block, block+nn, nn, key, r );
turtle_r( block+nn, block, nn, key, r );
turtle_r( block, block+nn, nn, key, r );
for( i = 0; i < n; ++i )
target[i] ^= block[i];
}
}
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
Subject: Re: What do we mean when we say a cipher is broken?
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Sat, 31 Mar 2001 05:32:17 GMT
"Trevor L. Jackson, III" <[EMAIL PROTECTED]> writes:
> From this perspective a broken/not broken predicate is not very useful.
> Consider breaking some old rotted branch with breaking living wood. Anyone
> who has wrestled with a live branch has had an experience similar to
> applying a certificational weakness as the basis for an attack -- typically
> fruitless. While solving a simple substitution is like an old, rotted
> branch. Eminently breakable.
If after years of research it seemed that the task of building a
cipher without certificational weaknesses were hopeless, then we
certainly would need the distinctions you're discussing to build
secure systems. However, the current state of the art seems to
indicate that we do have some cryptographic primitives - Blowfish,
say - which don't even have the slightest certificational weakness.
Not only can we do it, it's not even terribly expensive.
Now, when you're discussing the impact of a break on fielded systems,
these distinctions are important - for example, it would be a mistake
to worry about web traffic encrypted with RC4 despite the efficiency
of the known distinguisher. But when designing new systems, caution
says that when certificational-weakness-free cryptographic primitives
are available, efficient, and free, it would be crazy to use anything
else, and so this distinction is the only one that those designing new
ciphers need.
Incidentally, I have to admit that as a fan of mixed metaphors it
crossed my mind that wrestling with a live branch might quite
literally be more fruitful than you might have liked :-)
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Subject: Re: Idea - (LONG)
Date: 31 Mar 2001 05:37:49 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
+---------------
| [Shannon] demonstrated that ... *one way* to attain (perfect) secrecy
| was to obscure the PT with a sufficient amount entropy from a secret key.
| But that is usually impractical, so methods were developed that take into
| account how much *work* must be done to extract the hidden information in
| the presence of the key entropy. ...in the real world practical secrecy
| is all that we actually need. How to attain that is the big question.
+---------------
Hmmm... O.k., so here's another way of stating what I heard John Malley
getting at, using Mok-Kong Shen's "reducio ad absurdum" as a starting point
and moving forwards:
1. The identity transformation adds nothing to the attacker's "work".
2. Running some "k" chosed bits of plaintext through a chosen substitution
adds some amount (obviously depending on the redundancy in the plaintext
and can perhaps might be *very* small if "k" is small) to the attacker's
"work".
3. Ditto permuting "m" chosen bits with a chosen permutation.
4. And so on for each primitive operation we wish to admit.
Is there some way to quantify the added "work" for each primitive
operation (as a function of, e.g., "k", "m", how the bits are chosen,
existing redundancy of the text at each step, etc.), as well as assign
an "increase in work" to the composition of such primitives, so that
starting from the identity transformation and stepwise proceeding all
the way up to (say) Rijndael (or the like) one could quantify the total
"work" that has been introduced? If so, this might be a basis for a
formal discipline of cipher design.
-Rob
=====
Rob Warnock, 31-2-510 [EMAIL PROTECTED]
SGI Network Engineering <URL:http://reality.sgi.com/rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: new sboxgen :-)
Date: Sat, 31 Mar 2001 05:40:17 GMT
Tom St Denis wrote:
>
> I updated my sboxgen program... it can now make bijective sboxes (that
> are their own inverse) using a 2-function 3-round feistel. It outputs
> the feistel round functions too. Obviously the smallest sbox you can
> make with this is 6x6 since 2x2 functions can't be non-linear (and the
> size of the sbox must be even!)
>
> http://tomstdenis.home.dhs.orc/src/sboxgen.c
>
> (or a pretty html copy )
> http://tomstdenis.home.dhs.orc/src/sboxgen.c.html
>
> --
> Tom St Denis
> ---
> http://tomstdenis.home.dhs.org
For what particular purpose would we prefer sboxen which are
involutions?
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: new sboxgen :-)
Date: Sat, 31 Mar 2001 05:44:30 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > I updated my sboxgen program... it can now make bijective sboxes (that
> > are their own inverse) using a 2-function 3-round feistel. It outputs
> > the feistel round functions too. Obviously the smallest sbox you can
> > make with this is 6x6 since 2x2 functions can't be non-linear (and the
> > size of the sbox must be even!)
> >
> > http://tomstdenis.home.dhs.orc/src/sboxgen.c
> >
> > (or a pretty html copy )
> > http://tomstdenis.home.dhs.orc/src/sboxgen.c.html
> >
> > --
> > Tom St Denis
> > ---
> > http://tomstdenis.home.dhs.org
>
> For what particular purpose would we prefer sboxen which are
> involutions?
They were used in CS-Cipher to reduce the size of the cipher in moderate
speed implementations.
The idea is you can make a non-linear transform such that F(F(X)) = X then
you need not encode another transform :-). If you use F(F(X + K1) + K2) = Y
then your function is "secret" even if it's an involution you need the key
to compute it...
>
> --
> Sometimes the journey *is* its own reward--but not when you're trying to
> get to the bathroom in time.
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Subject: Re: Idea - (LONG)
Date: 31 Mar 2001 05:44:56 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
+---------------
| [Shannon] demonstrated that ... *one way* to attain (perfect) secrecy
| was to obscure the PT with a sufficient amount entropy from a secret key.
| But that is usually impractical, so methods were developed that take into
| account how much *work* must be done to extract the hidden information in
| the presence of the key entropy. ...in the real world practical secrecy
| is all that we actually need. How to attain that is the big question.
+---------------
Hmmm... O.k., so here's another way of stating what I heard John Malley
getting at, using Mok-Kong Shen's "reducio ad absurdum" as a starting point
and moving forwards from there:
1. The identity transformation adds nothing to the attacker's "work".
2. Running some "k" chosen bits of plaintext through a chosen substitution
adds some amount [obviously depending on the redundancy in the plaintext
and can perhaps might be *very* small if "k" is small, and also depending
on the method(s) of "choosing"] to the attacker's "work".
3. Ditto permuting "m" chosen bits with a chosen permutation.
4. And so on for each primitive operation we wish to admit.
Is there some way to quantify the added "work" for each primitive
operation (as a function of, "k", "m", how the bits & substitutions &
permutations are chosen, existing redundancy of the text at each step,
etc.), as well as assign an "increase in work" to the *composition* of
such primitives[*], so that (in theory) one could start from the identity
transformation and proceed stepwise all the way up to (say) Rijndael
(or the like), thereby quantifying the total "work" that has been
introduced? If so, this might be a basis for a formal discipline of
cipher design.
-Rob
[*] Where the work function of a composition might *not* be either
Abelian or associative, and might be different for each pair of
operators being composed, and perhaps the work function of a
composition might even depend on some of the parameters of the
functions being composed.
=====
Rob Warnock, 31-2-510 [EMAIL PROTECTED]
SGI Network Engineering <URL:http://reality.sgi.com/rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
------------------------------
Date: Sat, 31 Mar 2001 07:49:03 +0200
From: Anonymous <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,alt.security.pgp
Subject: Eric Lee Green & Co + Anti Evidence Eliminator Fake Spammers FBI Task Force
Authority
Listen to the real PIG who wrote this
<[EMAIL PROTECTED]> is really
the idiot amateur programmer and
full time professional spammer who used
to call himself
---EE Support---
HEAR him SQUEEAL!
>Eric Lee Green (pig stooge) wrote:
>
>"AVOID EVIDENCE ELIMINATOR -- for details, see
>http://badtux.org/eric/editorial/scumbags.html "
>
>Eric & his spammers are the cops sending all the fake spam about evidence
>eliminator (great util BTW)
>
>EE caught the pigs lying on 49 points.
EE Support is the PIG spammer with a thousand names
he is the only PIG I have seen around here lately
I will make him SQUEEEAL just for you!
DONT PAY FOR FREE SOFTWARE!
http://www.evidence-eliminator.com/order.shtml#order
Evidence Eliminator 5.0
name: USER-1-1567-21D
s/n: EE50-708040060003
Evidence Eliminator 5.0.52
name: HERiTAGE CREW
s/n: YXU2K51ZY-tE!176823357
I will stop posting new cracks when EE Support
stops SPAMMING newsgroups to sell SHIT to unsuspecting MARKS
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: What do we mean when we say a cipher is broken?
Date: 30 Mar 2001 21:54:51 -0800
Paul Crowley <[EMAIL PROTECTED]> writes:
> If after years of research it seemed that the task of building a
> cipher without certificational weaknesses were hopeless, then we
> certainly would need the distinctions you're discussing to build
> secure systems. However, the current state of the art seems to
> indicate that we do have some cryptographic primitives - Blowfish,
> say - which don't even have the slightest certificational weakness.
> Not only can we do it, it's not even terribly expensive.
But I thought Blowfish had a class of distinguishable keys (1/4096th
of the keyspace or something like that).
------------------------------
** 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
******************************
