Cryptography-Digest Digest #478, Volume #9 Wed, 28 Apr 99 11:13:05 EDT
Contents:
Re: FSE-6 Report: Mod n Cryptanalysis (Mok-Kong Shen)
Re: Papers on RC4 key size (Eric Young)
Re: True Randomness & The Law Of Large Numbers (Jim Gillogly)
Re: SHA vs. SHA-1 (Nathan Kennedy)
Re: OAEP, CBC, patents, and improving PGP ("Anonymous")
Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO (Mok-Kong Shen)
Re: Prime Numbers Generator (David Kuestler)
Re: Prime Numbers Generator (David Kuestler)
Re: Papers on RC4 key size ("Anonymous")
Re: break this code (Patrick Juola)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Leonard R. Budney)
Re: Extreme lossy text compression (Mok-Kong Shen)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: FSE-6 Report: Mod n Cryptanalysis
Date: Wed, 28 Apr 1999 12:48:21 +0200
Piso Mojado wrote:
> But even if the rotation amount is not known, some information about the
> mod 3 output is available. If an Even n bit rotation is used, the residue
> is X, if n is Odd, the residue is 2X mod 3. Probability vecors can be
A question: What if the rotation amount is not known and varies
from round to round and from block to block? Does the equation
depicted still helps?
M. K. Shen
http://www.stud.uni-muenchen.de/~mok-kong.shen/ (Updated: 12 Apr 99)
------------------------------
From: Eric Young <[EMAIL PROTECTED]>
Subject: Re: Papers on RC4 key size
Date: Tue, 27 Apr 1999 21:50:56 +1000
[EMAIL PROTECTED] wrote:
> Does anyone know of any papers that discuss the RC4 key-size? Any scientific
> account of relative strengths would be extremely usefull. Primary interest is
> the relative strengths of 40-bit and 128-bit keys, for SSL of course.
A minor point, SSLv2, SSLv3 and TLSv1 all drive RC4 in 128 bit mode.
For export ciphers
SSLv2 passes a full length key but only encrypts 40 bits when
transferring
the key over the wire.
SSLv3 and TLSv1 input 40 bits (along with the random values)
into a function that expands these bits to 128 bits.
So while we talk about 40 bit RC4/RC2/DES ciphers in SSL, it
is the SSL cipher suite that is this size, not the actual
stream/block cipher operating in this mode.
As another point of interest, the MAC keys generated for SSLv3/TLSv1
are full size, even for export ciphers. So message tampering is not
weakened, but privacy is.
eric
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Tue, 27 Apr 1999 05:38:23 -0700
R. Knauer wrote:
> What if I know you are monitoring my traffic and I decide to fake you
> out. I send this ciphertext:
>
> ATTACK AT DUSK
>
> Unbeknownst to you the key is the XOR of that ciphertext with the real
> message:
>
> ATTACK AT DAWN
>
> [NB: Yeah, I know - that requires sending that special key by a secure
> channel, in which case I could just as well sent the message itself,
> but it is my intent to trick you.]
Then you're being very silly: you could send your plaintext by that
secure channel (as you point out), but instead of sending this "special"
message that will decrypt to something you already knew you'd be sending
when you sent the special key, you could simply send as many fake messages
of whatever length you wanted by the monitored channel to "trick" me. No
need to have this "tricky" message decrypt to anything in particular.
So I don't buy it. If I see extended plaintext (for some definition of
extended), I'll expect that it's either real plaintext or fake cover
traffic. That's operationally safer than assuming the alternative, which
would be that you're an idiot. Although sometimes in adversary
situations your opponents are indeed idiots, you're an idiot yourself if
base your strategy on that assumption.
Robert H. Morris said the first rule of cryptanalysis is "Look for
plaintext." I'll believe him rather than you on this one.
--
Jim Gillogly
Sterday, 6 Thrimidge S.R. 1999, 12:24
12.19.6.2.11, 7 Chuen 19 Pop, Sixth Lord of Night
------------------------------
From: Nathan Kennedy <[EMAIL PROTECTED]>
Subject: Re: SHA vs. SHA-1
Date: Wed, 28 Apr 1999 19:21:36 +0800
Bjoern Sewing wrote:
>
> Hi everbody
>
> I have just one question about the SHA / SHA-1:
>
> What is the difference between these 2 algorithm ?
>
> Bjoern
SHA-1 is a correction, I believe typographical, not sure, which corrects a
weakness of the SHA standard.
Basically, only use SHA-1. Nobody uses SHA, SHA almost always means SHA-1.
Nate
------------------------------
From: "Anonymous" <[EMAIL PROTECTED]>
Subject: Re: OAEP, CBC, patents, and improving PGP
Date: Wed, 28 Apr 1999 08:30:46 -0400
John Savard wrote in part:
>A while back - on September 11, 1996 for the first time, which is after
>Mihir Bellare invented the similar techniques that are the topic of this
>post in 1995 - I proposed the following scheme for improving PGP:
>
>Instead of enciphering a session key plus random padding with RSA, why not
>replace the random padding with the first part of the message?
>
>I went further, and suggested the following scheme:
>
>divide the message into two pieces, the first 160 bits and the remainder.
>
>Take the SHA-1 hash of the remainder of the plaintext message.
>
>XOR that to the first piece of the message.
>
>Use as much of the 160 bit result of the previous step as required as the
>session key, and encipher the rest of the message with it.
>
>Using RSA, encipher the start of the message XOR the hash, and as much of
>the enciphered message as possible.
>
>
>A recent post in talk.politics.crypto pointed me to an IBM patent
>(5,673,319). This patent used DES in CBC mode to illustrate the principle,
>
>All but the first block of a message is used to produce a hash code using
>CBC-MAC. The hash code is XORed to the first block, then that block is used
>as an IV for the encryption of the rest of the message, using the same
>block cipher in CBC mode. (Keys are prearranged for both the CBC-MAC step
>and the CBC step.)
>
Mr Savard,
The first patent you speak of would NOT affect you.
If you read it carefully, you will find that the sole purpose of the
technique is to provide a way to ensure that the entire ciphertext changes
as only a portion of plaintext changes. WITHOUT THE USE OF IV. (For
applications where output length must equal input length) It is the LAST
block that is encrypted only once. Read the section where they speak of
"concatenation." Even so, it appears far to obvious to be patentable.
Consider: if you double encrypt a file in CBC and do not clear the FBR, are
you infringing on this patent? If so, this is rather funny.
Anon
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO
Date: Wed, 28 Apr 1999 13:31:07 +0200
SCOTT19U.ZIP_GUY wrote:
> Adding a random number of bits is a function of encryption not
> compression. ANd your are right an analyst looking at only the
> ending of a file can not tell what the EOF is. If he is looking at
> the ending of the file you compressed. But if he had the whole
> file. He could tell if it was a "REAL COMPRESSED" file. Also
> if a random number of bits added that information has to be in
> the file itself for the receiving person to use. Remeber the game
> is enemy has same code. IF this random number is passed secrectly
> then again it is like part of a key and is in the realm of encryption
> not compression.
I am not sure that I understand what you mean by
But if he had the whole file. He could tell if it was a "REAL
COMPRESSED" file.
Do you mean that he could discern a distinction because these
random bits are simply random and not the Huffman transformed
symbols which are in the proper ciphertext and which have some
patterns he could determine? But you can certainly generate a random
sequence of 'normal' symbols and have them Huffman transformed as if
that were part of the proper plaintext.
I also don't understand your last sentences. The random bits are
discarded by the receiver. They involve some transmission expense,
but that's all.
M. K. Shen
------------------------------
From: David Kuestler <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Generator
Date: Wed, 28 Apr 1999 12:55:17 +0000
Reply-To: [EMAIL PROTECTED]
This is a multi-part message in MIME format.
==============703CCF9197824E830D9AD423
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Peter Gunn wrote:
> David Kuestler wrote:
>
> > Jim Gillogly wrote
>
> > [snip]
>
> > Excellent ! This ran just shy of an hour on a 233Mhz K6 and gave the
> > same file size, though the byte order is different ( as expected ).
> > You're certainly a better C programmer than I as you only use integers
> > and pointers where as I used array references with the occasional
> > floating point operation.
> >
> > If you are interested you should submit it to The Prime Pages . Your
> > code is faster, smaller, more understandable and therefore would be
> > easier to impliment than others.
>
> Have a look at http://www.smdp.freeserve.co.uk/erato.cpp
> for a somewhat faster version... should run in ~10mins or
11.5 minutes ! ( with the file output back in ).
>
> less on a 233Mhz PC. Basically it uses bitmaps instead
> of character arrays and an 8Mb buffer to speed thing up.
>
> Im sure this could be reduced to less than 2mins runtime
> & 1Mb memory usage if it was hacked a bit further.
>
> I suppose you could even use a 2D graphics accelerator
> to make things *much* faster? That would be interesting...
> might even be worth watching :-)
>
> tata
>
> PG.
>
> PS I took out the code that output the primes to a file :-)
I put them back in to to give me a 'better' timing comparison to other
routines I've run.
I've got a lot to learn about C coding/tuning :-{
I will try Jim's blocking technique and your bitmaps on my 64 bit prime
number field routines.
Thanks to both you and Jim :-)
==============703CCF9197824E830D9AD423
Content-Type: text/plain; charset=us-ascii;
name="erato.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="erato.cpp"
/*
* erato: sieve of eratosthenes for up to 2**32.
* Two steps: first find all primes less than 2**16, then use them to sift
* the remaining numbers in blocks.
*
* Jim Gillogly, 24 Apr 1999
*
* Hacked by Peter Gunn 26 Apr 1999
*
* NOTE: Switch off Gloabal Optimsation & Full Optimisation when using
* MS VC++ 5, coz its broken!!!
*/
#include <stdio.h>
#include <memory.h>
#include <time.h>
#define MAXSMALL 6542 /* 6542 for primes up to 1<<16. */
#define TOP (1 << 16) /* Top of each block to be sifted. */
#define PRFILE "primes0" /* Save 'em in a file. */
#define BLOCKS (1 << 16) /* How many blocks to do total? */
unsigned long sieve[TOP/32]; /* Turned off if composite. */
#define bit(x) (sieve[(x)>>5]&(1<<(x&31)))
#define cbit(x) sieve[(x)>>5]&=~(1<<(x&31))
/* bitmasks for all primes < 32 in all rotations */
unsigned long sieve2[32][32][TOP/32];
#define csbit(y,r,x) sieve2[y][r][(x)>>5]&=~(1<<(x&31))
//char * stop = &sieve[TOP];
unsigned long smalls[MAXSMALL]; /* All primes under 2**16. */
unsigned long smallnum = 0;
main()
{
unsigned long b,b1, i, j, k, nprimes, start, step, *s;
char *p, *q, xxx[40];
FILE *out;
unsigned long start_time,stop_time;
start_time=time((time_t *)NULL);
memset(sieve,0xff,sizeof(sieve));
cbit(0); cbit(1);
b=0;
do
{
b++;
while (b<TOP && !bit(b)) b++; /* Scan to next prime. */
b1=b;
while ((b1+=b)<TOP)
cbit(b1);
} while (b<TOP);
if ((out = fopen(PRFILE, "w")) == NULL)
{
fprintf(stderr, "Phui.\n");
return 1;
}
for (i=0, s=smalls; i<TOP; i++)
{
if (bit(i))
{
*s=i;
fwrite(&i, 4, 1, out);
if (i<32)
{
unsigned long rot;
for (rot=0;rot<32;rot++)
{
memset(&sieve2[s-smalls][rot],0xff,sizeof(sieve2[0][0]));
b1=rot%i;
csbit(s-smalls,rot,b1);
while ((b1+=i)<TOP)
csbit(s-smalls,rot,b1);
}
}
s++;
}
}
smallnum = nprimes = (s - smalls);
printf("%d small primes.\n", smallnum);
/* Now sift each 2**16-number block with these small primes. */
start=0;
for (k=1; k<BLOCKS; k++)
{
start=k*TOP;
memset(sieve,0xff,sizeof(sieve));
cbit(0);
for (i=0, s=smalls; i<smallnum; i++) /* small primes */
{
if ((step=*s++)<32)
{
unsigned long rot=step-(start%step);
unsigned long *s1=&sieve[TOP/32-1],
*s2=&sieve2[s-smalls-1][rot][TOP/32-1];
while (s1>=sieve)
*s1--&=*s2--;
}
else
{
for (b=step-(start%step);b<TOP;b+=step)
cbit(b);
}
}
for (i=0; i<TOP; i++)
{
if (bit(i))
{
j=i+start;
// printf("%d\n",j);
nprimes++;
// if (!(nprimes&0xfffff))
// printf("%ld primes in %ld secs
(k=%ld)\n",nprimes,
// time((time_t *)NULL)-start_time,k);
fwrite(&j, 4, 1, out);
}
}
}
stop_time=time((time_t *)NULL);
printf("%d primes in %ld secs \n", nprimes,stop_time-start_time);
printf("hit enter\n");
fclose(out);
return 0;
}
==============703CCF9197824E830D9AD423==
------------------------------
From: David Kuestler <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Generator
Date: Wed, 28 Apr 1999 13:00:23 +0000
Reply-To: [EMAIL PROTECTED]
snip ...
> however I would also like to refer
> you to Jim Gillogly's code which he posted in this thread which runs about 80
> times faster than mine ( on my machine ).
And Peter Gunn's hacks to Jim's code which runs another 5 times faster still !
snip ...
------------------------------
From: "Anonymous" <[EMAIL PROTECTED]>
Subject: Re: Papers on RC4 key size
Date: Wed, 28 Apr 1999 08:43:34 -0400
[EMAIL PROTECTED] wrote in part:
>There is a mini-weakness in the key schedule which
is the fact that if you
>repeat a byte (thru the entire key) is has an effective length of one byte.
>This is the same as in Blowfish too.
>
>Tom
Yes, and the same is true for any length string that
is repeated:
1234 = 12341234
Anon
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: break this code
Date: 28 Apr 1999 08:35:40 -0400
In article <XaqV2.13452$[EMAIL PROTECTED]>,
Dan <[EMAIL PROTECTED]> wrote:
>Why do you need the entire system, isn't that kind of like cheating?
>
>Please don't take this the wrong way, I just wanted to know.
It's more realistic. It's very very difficult to keep a cryptographic
*system* secret; code can be reverse-engineered, equipment can be
stolen, and so forth.
For example, the British had a copy of the German Enigma machine well
before the outbreak of WWII; it had been reverse-engineered by the
Poles. Similarly, anyone who likes can pick up a copy of PGP 5.0 and
figure out how it works.
So unless you have some reason to assume that no one will ever be able
to get a copy of your system, then you have to do a more realistic
analysis of the strength of your system when the encryption method
is known.
-kitten
------------------------------
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
From: [EMAIL PROTECTED] (Leonard R. Budney)
Date: 28 Apr 1999 08:49:18 -0400
Sundial Services <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
>
> > Once you have an "OTP quality stream key" just XOR and go. You
> > get perfect secrecy quality privacy and you can do no better.
> > If you need provable authenticaiton, use a universal keyed hash.
> > Your extra operations are pointless.
>
> I question that, Bryan. It seems to me fairly obvious that you
> -can- gain security by doing something more clever than XOR using
> the stream key that you've produced.
But you can't. As Bryan observed, if the stream cipher is "OTP
quality", then it provides absolutely perfect security. Why do better
than 100% perfect?
In this context, "perfect" means "perfect". That is, a message of
length N can be decrypted as any other message of length N, by some
key. Thus, exhaustive search turns up ALL POSSIBLE MESSAGES of length
N, which is useless.
Such perfection generally requires the the key also have length N,
which is the case with a OTP.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Len Budney | Designing a cipher takes only a
Maya Design Group | few minutes. The only problem is
[EMAIL PROTECTED] | that almost all designs are junk.
| -- Prof. Dan Bernstein
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Extreme lossy text compression
Date: Wed, 28 Apr 1999 14:25:42 +0200
Terry Ritter wrote:
>
> For production use, CRC's are table-driven. Typically, we generate a
> 256-entry table, then process data byte-by-byte. Each step typically
> requires a byte exclusive-OR, an 8-bit "shift" of the CRC (which might
> involve simply changing a pointer to the head), and an exclusive-OR
> from table into the CRC register.
Could you say what speed you can achieve with that on a typical
processor (in assembler and in C or other languages)? Thanks
in advance.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Wed, 28 Apr 1999 13:43:26 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 28 Apr 1999 04:11:49 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>Since FIPS-140 does not specify details of the implementation
>(algorithm, hardware architecture, etc.), it cannot tie tests
>to specific failure modes.
Wrong. The fourth test, the Long Run Test can be tied to a failure
mode - an intermittently floating or shorted output. Long runs would
be characteristic of such a mode of failure.
>Instead, it specifies generic tests
>that *any* sufficiently random generator should pass 999,999
>times out of 1,000,000 (or thereabouts).
In the first place, your statement is merely a pontification of the
very issue we have been discussing for these several months, and is
not made credible just because you arrert it.
Furthermore, where did you get that 999,999 out of 1,000,000 from? And
what does "thereabouts" mean? Please don't say that you got it from
"standard statistics", because that too is just more pontification .
There is no rational justification to expect the time average of one
sequence to be characteristic of the ensemble average, and therefore
of the generation process itself. To do so is to misapply the notions
of statistics, as Feller and others have pointed out.
Go back an read the recent comments of Herman Rubin in this regard. As
a professional statistician he is qualified to comment on these
matters, whereas the best I can hope to do is quote the experts. What
experts are you quoting to back up your assertion?
Even your beloved Triola said in unequivocal English that there are no
parametric statistical tests for deciding whether a process is random
or not. Yet the FIPS-140 Monobit Test is a parametric statisitcal
test. The only thing he even offered was a non-parametric test, namely
the long run test, which I consider on a far different footing than
the Monobit Test.
Yet in the face of this broad expert commentary you persist in
clinging to your false dogma as some kind of article of faith. Have
you even bothered to give the opposite position any time in your mind,
or is your mind so closed that you can't open it enough to consider
what we are saying?
Bob Knauer
Guns don't cause violence - violence causes violence. Gratuitous violence
in the media/entertainment industry causes violence. Government sponsored
violence like at the Waco Massacre causes violence. Quit blaming law abiding
citizens for the violence in America, and blame the real sources of violence:
the federal government and the media/entertainment industry.
------------------------------
** 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
******************************
