Cryptography-Digest Digest #856, Volume #11 Thu, 25 May 00 02:13:01 EDT
Contents:
Re: safer style sboxes (tomstd)
Re: Patent busting for AES usage (zapzing)
yet another broken cipher (please read) (tomstd)
Re: Yet another block cipher: Storin ([EMAIL PROTECTED])
Re: Crypto patentability (Jerry Coffin)
Re: safer style sboxes (Jerry Coffin)
Re: Chosen Plaintext Attack ([EMAIL PROTECTED])
Re: Modulu arithmetic additive stripping? ("Douglas A. Gwyn")
Re: pentium timings (Greg)
Re: bamburismus ("Douglas A. Gwyn")
----------------------------------------------------------------------------
Subject: Re: safer style sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 19:19:47 -0700
In article <8ghujs$921$[EMAIL PROTECTED]>, zapzing <zapzing@my-
deja.com> wrote:
>In article <[EMAIL PROTECTED]>,
> tomstd <[EMAIL PROTECTED]> wrote:
>> In article <8gfjlh$ib5$[EMAIL PROTECTED]>, zapzing <zapzing@my-
>> deja.com> wrote:
>> >In article <8gfc0q$d86$[EMAIL PROTECTED]>,
>> > Tom St Denis <[EMAIL PROTECTED]> wrote:
>> >> I have tested all possible sboxes in GF(257) of the form
>> >>
>> >> S(x) = x^b mod 257
>> >> and
>> >> S(x) = b^x mod 257
>> >>
>> >> (fixed 'b' value)
>> >>
>> >> And haven't found one that is ideally non-linear. Which
>> makes me ask,
>> >> how come ciphers like SAFER or E2 (uses x^255 right?) can
get
>> away
>> >with
>> >> that?
>> >>
>> >> I use the WT to measure non-linearness and typically see -
>> 44/44 as the
>> >> WT output... I would expect at least -32/32, and at best -
>> 16/14
>> >> (matsui's sboxes do that well).
>> >>
>> >> Tom
>> >>
>> >> Sent via Deja.com http://www.deja.com/
>> >> Before you buy.
>> >>
>> >
>> >I just wonder why cipher desighners don't start
>> >using larger s-boxes. From what I understand, if
>> >an s-box is large enough, say 16 bits, then just
>> >about any randomly generated s-box will perform
>> >adequately. With hardware improving by leaps
>> >and bounds, this seems like it might be the
>> >way to go.
>>
>> Not true, a 16x16 sbox would still have to be designed
according
>> to CAST (or similar) to be secure. While it is possible to
>> make 'more' secure 16x16 sboxes then say two parallel 8x8
sboxes
>> you have to be careful.
>>
>I was going by what I read in "applied cryptography"
>section 14.10 seems to say that a 16X16 randomly
>generated s-box would probably be very secure.
"would probably" is very suggestive. For example you have about
2^-24 chance of randomly comming across 'good' 8x8 sboxes. I
bet it's about higher for 16x16, but probably still lower then
2^-16 of getting ideally secure sboxes.
I wouldn't use 16x16 anyways, unless it was algebraic. The
memory required is enormous and they would be slow to construct
at runtime.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Patent busting for AES usage
Date: Thu, 25 May 2000 02:53:05 GMT
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> In article <8gf74o$a0f$[EMAIL PROTECTED]>, zapzing <zapzing@my-
> deja.com> wrote:
> >In article <FKzW4.195$[EMAIL PROTECTED]>,
> > <[EMAIL PROTECTED]> wrote:
> >> I would like to start one or more threads with the
> >> goal of creating prior art to spoil patents based on
> >> using the algorithm or algorithms selected as the AES.
> >> [Please, no discussion of the benefits of selecting
> >> one, or more than one, candidate on this thread.] The
> >> submitters have agreed to terms that allow free use of
> >> the selected AES, so I am not worried about that.
> >> [Please no discussion of the Hitachi patents on this
> >> thread.]
> >>
> >> What I would like to prevent are things like the MDC-2
> >> and MDC-4 patents that IBM got on a DES mode of
> >> operation that creates a cryptographic digest from DES
> >> or similar block ciphers (see US Patent #4,908,861).
> >> These threads could declare certain ideas as obvious
> >> to a workman versed in the trade, or they could publish
> >> novel ideas, which could no longer be the basis for a
> >> patent.
> >>
> >
> >Here are some ideas (and if you know about
> >a source of inexpensive DES chips please
> >let me know).
> >
> >A PRNG could be created as follows:
> >
> >B_i=E(k2,i+B_(i-1))
> >
> >Instead of encryption hashing could be used.
> >Instead of adding i to B_(i-1) one could
> >add a hash or encryption of i.
>
> The problem with using the above, is if B[0] is fixed, and I
> find the key, I can find all others B[i] outputs.
>
> Similarly with using a hash in counter mode. That's why it must
> be non-invertible, or very difficult (i.e large symmetric key).
> Using a good hash (md5, sha-1, tiger, etc...) in counter mode
> like
>
> B[i] = H(B[i - 1] || i || key)
>
> Is much simpler, and it's secure iff the hash is secure and the
> key is random (and sufficiently large, say >100 bits).
>
Yes, that would work better if the hash had an
output of the correct size.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: yet another broken cipher (please read)
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 20:45:37 -0700
I designed yet another cipher, but broke it with a 16R
differntial and *at least* 2^49 plaintexts. The postscript
paper is at
www.tomstdenis.com/tc1_draft.ps
If anyone wants pdf copies I will make one...
I would really like comments and confirmations of my results. I
have some questions about doing the selective-sbox attack (i.e
where only some of the sboxes are active). If anyone wants to
help please email me or reply here.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Yet another block cipher: Storin
Date: Thu, 25 May 2000 04:35:00 GMT
In article <8ghu1f$c4g$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> In article <8ggv2a$h5c$[EMAIL PROTECTED]>, <matthew_fisher@my-
deja.com> wrote:
> > Blowfish avoids this problem by setting the max key length to be 14
> > words instead of 18.
>
> Well, ok, but I believe even in Blowfish you can find a 448-bit key
> that will force the first 14 round subkeys to be zero; the last four
> remain uncontrolled. In any case, the probability of hitting a weak
> key is so small that I think it is probably negligible in most
scenarios.
>
Mr. Wagner,
Under what circumstances can a 448 bit yield 14 zero subkeys in
Blowfish? As I am sure you know, that would involve finding 7 P and S
arrays that encrypt the zero input block to the zero output block. If
the chance for each one is random, (2^64)^7 = 2^448, so probably no
such key exists. Is that right?
Also, Storin does not have the secret sboxes. The weak key is easy to
identify in Storin.
In Blowfish with secret sboxes, it appears difficult to determine if a
large subset, but not all, of the round keys are zero. Perhaps, a
slide attack combined with a transform attack could be used.
--Matthew
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Crypto patentability
Date: Wed, 24 May 2000 23:10:36 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> Well I don't like patents, too. They are only a way for the
> rich people to keep their richness. They are a way for the
> big companies to stay big by destroying small companies
> without much effort.
_Precisely_ the opposite is actually true: patents are one of the few
ways for a small company, or even one smart person, to level the
playing field and be competitive against a big company. Consider
what would happen if there were no patents. I, as simply a smart
guy, invent some great new invention. I can't protect it, so the
minute I start to sell it, IBM or GM, or whatever company makes the
same general sort of thing I've invented, starts to make it as well.
Since they're already big and have lots of money, they can build it
for less than I can and can afford to sell it at a loss for a while
to put me out of business. Aftwards, they have an open market to
take advantage of the way they want to.
Patents change that: even though I'm only one person, my patent is
just as good as anybody else's. If they try to steal my invention, I
can stop them or make them pay me for it.
Yes, patents can involve lawsuits, and lawsuits can be expensive.
Fortunately, there are law firms around (quite a few of them really)
that'll happily take a case on a contingency basis as long as the
case has merits to justify their time and effort. True, this way
when you win a few hundred million from the company that stole your
invention, you'll end up paying a few tens of those millions to the
law firm. But so what? If there was no patent system to help
protect you, you'd have ended up with _nothing_!
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: safer style sboxes
Date: Wed, 24 May 2000 23:10:39 -0600
In article <8gfjlh$ib5$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> I just wonder why cipher desighners don't start
> using larger s-boxes. From what I understand, if
> an s-box is large enough, say 16 bits, then just
> about any randomly generated s-box will perform
> adequately. With hardware improving by leaps
> and bounds, this seems like it might be the
> way to go.
Larger S-boxes take more memory. Variable (key-dependent) S-boxes
have to live in RAM instead of ROM (and ROM is typically a LOT
cheaper).
You're right that hardware is constantly improving, but at the same
time, people want to deploy things into situations where lower costs,
smaller size, reduced power consumption, etc., are important. At one
time, encipherment was available only to a VERY select few, and even
they couldn't get anything that was worth much -- consider that the
Caesar cipher was originally used by a man who ruled the majority of
the western world at the time! Now, it would be _awfully_ nice to be
able to replace (for example) most credit/ATM cards that use magnetic
strips with something like smart-cards that provide a lot higher
security. To do that, though, you need to use a cipher that can
implemented in a small, cheap, low-power chip.
In fairness, I think there's more than practicality at work here
though: as Bruce Schneier has pointed out, it doesn't take much
talent to design a cipher that's probably secure as long as you don't
mind designing something that's slow, takes lots of memory, and so
on. For most cryptologists, the challenge is in creating a cipher
that uses the bare minimum of resources, but still makes optimal use
of the key and provides as much security as possible for that key
size.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Chosen Plaintext Attack
Date: Thu, 25 May 2000 05:09:44 GMT
In article <[EMAIL PROTECTED]>,
Raphael Phan Chung Wei <[EMAIL PROTECTED]> wrote:
> Hi,
>
> Referring to the post as a follow-up to Mark Wooding's post on
> Interesting differentials of Breakme...
>
> If we have a 10-round differential of prob. 2^-15.... how do we make
use
> of
> this to break the cipher? I still do not have a clear idea how to
> implement this
> attack.. We need 2^16 chosen plaintext pairs... and then?
>
> How do we implement the generation of for instance 2^16 chosen
> plaintexts pairs? For
> example, for the breakme cipher, we would like plaintext pairs with
the
> input XOR of
> 0x65000000... how do you translate that into C code?
>
> --
>
> Raphael
Here you go. This code is a bit sloppy but should give you a good
start. Have fun.
The code tries to find the high byte of the first round key. It should
always work but sometimes fails so a bug must be present. I hacked it
out in about an hour or so.
--Matthew
// The rest of breakme is needed to link
int array[256]; // hold the collision indices
int suggest[256]; // hold the number of times a key values is suggested
void main()
{
word x,y;
word p,p1,q,q1;
int m,r,ll;
key k;
int count = 0;
word keyMaterial[4] = { 0 };
int diffA[3] = {0x52,0x65,0xf2}; // the good differentials
srand(time(0));
x = rand();
keyMaterial[0] = (x<<15)|rand();
keyMaterial[1] = (x<<15)|rand();
keyMaterial[2] = (x<<15)|rand();
keyMaterial[3] = (x<<15)|rand();
keySetup(&k, keyMaterial);
for(ll=0;ll<3;ll++)
{
word diff = diffA[ll%3];
memset(array,0,sizeof(array));
count =0;
for(x=0;x<256;x++) // calculate the collisions
{
if((sbox[x]^sbox[x^diff]) == 0)
array[count++] = x;
}
for(x=0;x<256;x++)
for(y=0;y<256;y++)
{
q = (x<< 24)|ll;
q1 = ((x^diff) << 24)|ll;
p = y << 24;
p1 = p;
encryptBlock (&k, &p, &q);
encryptBlock (&k, &p1, &q1);
/* Just try a bunch of blocks. If the differential holds,
one side will be equal and the other will be the differential value
We are looking at the high bytes so shift left 24 bits.
*/
if(((p^p1)== (diff<<24L)) && (q==q1))
{
int s = x;
int s1 = x^diff;
for(m=0;m<256;m++)
{
int found = 0;
int found1 = 0;
for(r=0;r<count;r++)
{
// one of the differential in the array must have held to
// get here.
// By guessing the byte to be m, each value in the array
// can be checked.
if((array[r] == (m^s)) &&
((array[r]^diff) == (m^s1)))
{
found = 1;
}
}
if(found)
suggest[m]++;
}
}
}
}
{
int max = 0;
int hit;
int i;
for(i=0;i<256;i++)
{
if(suggest[i] > max)
{
max = suggest[i];
hit = i;
}
}
// the hit should be equal to the high byte of k.s[0]. QED
printf("%02X %d %08lX\n",hit,max,k.s[0]);
}
}
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Modulu arithmetic additive stripping?
Date: Thu, 25 May 2000 05:55:18 GMT
Mok-Kong Shen wrote:
> (Unfortunately I don't have the literature you mentioned.)
That's like a computer programmer not having Knuth's TAOCP.
Plaintext message: ATTACK AT DAWN
Code book:
AT -> 7892
ATTACK -> 0123
DAWN -> 0199
... (and others)
Coded message: 0123 7892 0199
One-time-pad:
p.025
59276
32957
10116
98723
05549
Indicator: 025 (OTP page number)
Coded message: 012378920199
Additive: 592763295710
Superenciphered message: 504031115809 (used non-carrying addition)
Transmitted message: 02550 40311 15809 (first 3 digits are indicator)
The receiver uses the first 3 digits to find the right OTP page:
Indicator: 025 (OTP page number)
One-time-pad:
p.025
59276
32957
10116
98723
05549
Superenciphered message: 504031115809
Additive: 592763295710
Coded message: 012378920199 (used non-borrowing subtraction)
At this point the additive has been stripped off.
Coded message: 0123 7892 0199
Decode book:
0123 -> ATTACK
0199 -> DAWN
7892 -> AT
... (and others)
Recovered plaintext: ATTACK AT DAWN
Many variations are possible, but that's the stereotypical example.
Historically, systems just like this one were frequently used for
some military and spy communications. The operations can be performed
quickly using pencil and paper with low error rate under adverse
conditions, and if an error occurs (other than using the wrong OTP
page), typically the garble is highly localized and the rest of the
message remains intelligible; these are important properties for any
system used for such purposes.
In base 2 (binary codes), non-carrying addition is in fact bitwise
exclusive-or, and non-borrowing subtraction is the same operation,
which leads to nice simplifications in the algebra.
A cryptanalyst also uses the term "stripping off additive" when by
some means he is able to undo the effect of the additive. There
are several circumstances under which he can accomplish this.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Thu, 25 May 2000 05:47:48 GMT
> >A question of curiosity: How do you get the time
> >to sufficient accuracy?
> >On a computer, e.g. PC, there are other tasks
> >running concurrently.
>
> I think my DOS task just hogs the cpu, because the idle time
> goes to zero when I do time testing.
>
> Either rate I can test in pure dos, but I get the EXACT same
> results.
I assume you are running Windows 98 from other posts you have made
along this subject. You should get a book on how 98 idle processing
works and what it means. Also read about context switching, which
occurs many times every second.
A co worker improved performance of some compression code by
detecting and taking advantage (in assembler) the Pent II dual
pipeline design.
How did he know his code improved performance? He calculated it
on paper using the Intel docs. Then he verified it in practice.
He could not possibly tell you how much improvement precisely,
due to the Pent cache/bus/timing complexities, but he could tell
you why there would be roughly 40-50% less processing time as
a result. And he was CLOSE (more like 30%). But that is all we
expected given our limited resources.
I would venture to guess that people would expect less precision
from you as well, given your limited resources.
--
There is only one gun law on the books- the second amendment.
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: bamburismus
Date: Thu, 25 May 2000 06:03:52 GMT
"David A. Wagner" wrote:
> Nonetheless, if we interpret "proper use of modern algorithms"
> as "use 3DES" and we interpret "cryptanalysis" as "analysis of
> block (or stream) ciphers", John Savard's comment seems to stand
> up pretty well -- it seems that potential weaknesses in the
> higher-level aspects of the system will dominate the assurance
> level of the low-level primitives, no?
The fraction that is crackable depends on the mix of systems as
well as on the security of protocols, key management, etc. The
last I heard, 3DES was one of the systems that *no*body was
reading with any method substantially better than a brute-force
key search, but (a) it's not the only system being used and (b)
it's among the family of systems I suspect *can* be cracked
along the lines of my now-defunct research project of a couple
of years ago. Anyone who trusts that the core 3DES algorithm
is forever immune to (e.g.) known-plaintext cryptanalysis is
assuming more than is warranted.
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
