Cryptography-Digest Digest #766, Volume #10 Sun, 19 Dec 99 08:13:01 EST
Contents:
random numbers straight out of MS BASIC (Raddatz Peter)
CryptoPunk - 128 bit encryption? (MEGstir)
Re: The 20 years periods did apply to 2 of the 3 patents. Why not for RSA ? (Rich
Wales)
Re: compression & encryption (David A Molnar)
Re: random numbers straight out of MS BASIC (Mok-Kong Shen)
Re: RSA, how to calculate big numbers (MEGstir)
Re: compression & encryption ("Kasper Pedersen")
Re: Enigma - theoretical question (Johnny Bravo)
Re: random numbers straight out of MS BASIC (Johnny Bravo)
Re: 'Simple' password storage (Amos)
Re: Sorry, I was unclear... (Amos)
Re: Sorry, I was unclear... (Amos)
Re: First Bijective Arithmetic Compression (SCOTT19U.ZIP_GUY)
Re: compression & encryption (SCOTT19U.ZIP_GUY)
Casio's Multi Dimensional Space Rotation encryption ("Barry")
----------------------------------------------------------------------------
From: Raddatz Peter <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: random numbers straight out of MS BASIC
Date: Sat, 18 Dec 1999 23:20:07 -0800
I keep reading about how weak and predictable the built in RNG from MS
is, so I did some testing. The MS RNG has a repeat series of approx.
256^3 or 16777215.
If I create 10 sboxes with 1000 rnd numbers betw. 0 and 256 based on 2,
rather large, seeds (> 111111111111111 & < 999999999999999) and a keybox
of 1000 rnd numbers betw. 0 and 256 with a seed of ~100000 then I do
not believe the following is unreasonable.
Combos ~ 1/4*1/4*1/4 or 4,000,000*4,000,000*25,000. That translates into
4 e17 different attack combos before hitting paydirt. Even at 50,000,000
combos per second it'd take ~253 years for success. I don't think I'm
too worried! Have we all forgotten that 20 years after WWII any $5.-
Encyclopedia had an 'how to' article on the nuclear bomb.
Perhaps an ill conceived use of the MS RNG is weak, but with a little
ingenuity in implementation I am at a loss to see the weakness.
Peter Rabbit
------------------------------
From: [EMAIL PROTECTED] (MEGstir)
Subject: CryptoPunk - 128 bit encryption?
Date: 19 Dec 1999 07:56:35 GMT
http://download.cnet.com/downloads/0-10105-100-917695.html?tag=st.dl.10105
_103_1.lst.titledetail
or
http://www.winsite.com/info/pc/win95/misc/CryptoPunk11.zip/
So what do you think? Any comments?
------------------------------
From: [EMAIL PROTECTED] (Rich Wales)
Crossposted-To: alt.security.pgp
Subject: Re: The 20 years periods did apply to 2 of the 3 patents. Why not for RSA ?
Date: 19 Dec 1999 00:00:22 -0800
"wtshaw" wrote:
> There is more at work in changing some of the laws on
> patents and copyrights beyond just picking round numbers.
Fair enough. Here, then, is some more specific info, to the best of
my understanding (based on some discussions of this question which I
read in early 1997).
Originally, US patent law stated that a patent would expire 17 years
after the date the patent was issued. However, this rule had to be
changed when the US ratified the GATT patent treaty in 1995. The new
rule (mandated by the treaty) is that a patent expires 20 years after
the date the application for the patent was filed.
When the GATT patent treaty was ratified, all US patents which hadn't
already expired by that time were extended so that they would expire
either 20 years after filing, or 17 years after issue, whichever was
later. (The treaty didn't shorten the duration of any existing patent.)
This change affected the patents on Diffie-Hellman (4,200,770) and
Hellman-Merkle (4,218,582). Originally (under the "17 years after
issue" rule), D-H was supposed to expire on 1997-04-29. Under the
new "20 years after filing" rule, however, D-H's expiration date
was extended to 1997-09-06. Similarly, H-M's expiration date was
postponed from the original 1997-08-19 to the new 1997-10-06.
The RSA patent (4,405,829), on the other hand, was originally applied
for on 1977-12-14, but the patent wasn't issued until almost six years
later (1983-09-20). Thus, the adoption of the GATT patent treaty did
not extend the RSA patent; it will still expire 17 years after the
issue date, on 2000-09-20.
Rich Wales [EMAIL PROTECTED] http://www.webcom.com/richw/
See http://www.webcom.com/richw/pgp/ for my PGP key and fingerprint info
*** NOTE: any key generated by me before 1997-09-18 has been REVOKED ***
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: compression & encryption
Date: 19 Dec 1999 08:53:53 GMT
Jerry Coffin <[EMAIL PROTECTED]> wrote:
> Just for example, many compressors leave a signature at the beginning
> of their output. This is typically around 3 bytes or so,
> substantially smaller than a single block with nearly any reasonably
> recent block cipher of which I'm aware.
on a tangent (almost nothing to do with block ciphers :)
I used to secretly scoff at the idea that a 3 byte known header could make
a difference. Except I just realized that if you look at Bleichenbacher's
attack on RSA PKCS #1 1.5, it exploits the fact that the standard
specified a stereotyped header.
The attack consists of taking your target ciphertext c, and then creating
a new ciphertext c' by multiplying c by another number. Then you have
access to some oracle which tells you if the ciphertext is correctly
formed or not after it decrypts. Such an oracle can be something as
simple as a server which outputs "decryption failed" if the message
isn't 'correctly formed', and "message not understood" if the message
is 'correctly formed, but looks like garbage.'
Because of the stereotyped header, this means you now know some of the
high-order bits of the decrypted message. The paper then goes on to show
how to extract more and more bits, using more new ciphertexts and oracle
queries. Eventually (about 2^20 trials) you can recover the message
itself.
So I'll stop scoffing now and start worrying about where else such
stereotyped headers pop up instead...
Thanks,
-David Molnar
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: random numbers straight out of MS BASIC
Date: Sun, 19 Dec 1999 10:55:29 +0100
Raddatz Peter wrote:
>
> I keep reading about how weak and predictable the built in RNG from MS
> is, so I did some testing. The MS RNG has a repeat series of approx.
> 256^3 or 16777215.
> If I create 10 sboxes with 1000 rnd numbers betw. 0 and 256 based on 2,
> rather large, seeds (> 111111111111111 & < 999999999999999) and a keybox
> of 1000 rnd numbers betw. 0 and 256 with a seed of ~100000 then I do
> not believe the following is unreasonable.
> Combos ~ 1/4*1/4*1/4 or 4,000,000*4,000,000*25,000. That translates into
> 4 e17 different attack combos before hitting paydirt. Even at 50,000,000
> combos per second it'd take ~253 years for success. I don't think I'm
> too worried! Have we all forgotten that 20 years after WWII any $5.-
> Encyclopedia had an 'how to' article on the nuclear bomb.
> Perhaps an ill conceived use of the MS RNG is weak, but with a little
> ingenuity in implementation I am at a loss to see the weakness.
The security of employing a PRNG depends on the nature of the PRNG and
on how the output is used. Given a number of successive values output
from a linear congruential generator, the coefficents of the generator
can be very simply calculated and all the following output determined.
Even if only some bits of the numbers out are employed, inference is
still possible. See the literature cited in one follow-up in a recent
thread 'Q: BBS'. On the other hand, post-processing can render
the inference difficult. I used some such techniques. See my web page.
Finally, note that even BBS, which is commonly praised in the
literature to be 'provably secure', is questionable, see the
discussions in the thread 'Q: BBS'.
M. K. Shen
===========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (MEGstir)
Subject: Re: RSA, how to calculate big numbers
Date: 19 Dec 1999 09:52:48 GMT
(79525592A ^ 59A2F) % 95035AA7D
= B1634
Calculation time: Less than 1/2 second
Note: Numbers are in hexadecimal
------------------------------
From: "Kasper Pedersen" <[EMAIL PROTECTED]>
Subject: Re: compression & encryption
Date: Sun, 19 Dec 1999 00:05:51 +0100
"Raddatz Peter" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Forgive me for being stupid about this...
> I keep on reading about weak compression for encryption etc.
> Here is what baffles me. Let's say I use Zlib for compression and then
> encrypt the result with RC4 - why is that weak? If Zlib leaves a header,
> which I have not seen, that header gets encrypted through RC4.
> Trying to crack the cypherfile you must first reverse the RC4 code and
> then unzip. So WHY is the use of Zlib weak????
> Peter Rabbit
It's not. Especially weak, that is. When you run the 'deflate' method with
header on, you get the first two bytes to be 78 9C.
This means that the attacker knows plaintext, helping him/her doing a
known-plaintext keysearch. He can also determine when(ever) he/she succeeds,
as there are adler32 sums in there.
It is similar to telling the attacker that the file begins with the text
'WORD DOCUMENT', and ends with a checksum. Or that a .wav file probably
starts with 'RIFF????WAVEfmt'. If your cipher is good, the entire system is
still secure.
/Kasper
"Hmm. That power supply lying there, isn't that for the satellite they're
going to launch tomorrow? Nah, I'm probably just being stupid..."
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: Enigma - theoretical question
Date: Sun, 19 Dec 1999 05:26:06 GMT
On Sat, 18 Dec 1999 19:21:23 GMT, amadeus @DELETE_THIS.netcomuk.co.uk
(Jim) wrote:
>>Much more secure than the actual Enigma as the Germans used it, since they
>>broke all the above rules on a regular basis.
>
>Agreed. But the Germans were using it very much more heavily than
>we are proposing here.
Lack of traffic would definitely be a plus, but for something like
this why not just use something that wasn't broken more than 40 years
ago just to avoid the risk. RC4 would be a good choice, very simple
to implement (it would easily fit into a 10 line signature if you
compacted some of the white space). It can be done in as little as
three lines of Perl or 36 lines of QBasic.
Best Wishes,
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: random numbers straight out of MS BASIC
Date: Sun, 19 Dec 1999 06:04:27 GMT
On Sat, 18 Dec 1999 23:20:07 -0800, Raddatz Peter <[EMAIL PROTECTED]>
wrote:
>4 e17 different attack combos before hitting paydirt. Even at 50,000,000
>combos per second it'd take ~253 years for success.
You seriously underestimate the potential of dedicated hardware.
The EFF cracked a 56 bit message in three days with a $250k box.
At those speeds 4e17 combos can be checked to a 50/50 chance of
breaking in 6.5 days for about $1 million dollars by using four
machines. Your attack divisor is off by a factor of around 1700 or so.
>I don't think I'm too worried!
You should be if you are relying on this system for your security.
>Perhaps an ill conceived use of the MS RNG is weak, but with a little
>ingenuity in implementation I am at a loss to see the weakness.
Why rely on the MS PRNG when there are much better alternatives
available?
Johnny Bravo
------------------------------
From: Amos <[EMAIL PROTECTED]>
Subject: Re: 'Simple' password storage
Date: Sun, 19 Dec 1999 11:24:06 +0000
Reply-To: [EMAIL PROTECTED]
Hi again Jerry,
I am in Bedford, Bedfordshire, England.
-Amos
------------------------------
From: Amos <[EMAIL PROTECTED]>
Subject: Re: Sorry, I was unclear...
Date: Sun, 19 Dec 1999 11:26:42 +0000
Reply-To: [EMAIL PROTECTED]
Hi Omar,
Thanks for your feedback.
I am a little worried about cryptographic systems whose workings are unknown.
The only way I can really rest easy about things like this (no matter if what
type of software it is), is if the s/code has been subject to extensive public
debate, or if I wrote it :)
Thanks again,
-Amos
------------------------------
From: Amos <[EMAIL PROTECTED]>
Subject: Re: Sorry, I was unclear...
Date: Sun, 19 Dec 1999 11:30:12 +0000
Reply-To: [EMAIL PROTECTED]
Hi Eric,
My knowledge of cryptographic related terminology and understanding is increasing
at a dramatic rate. I already had "dictionary attacks" figured, and fortunately
have always been in the habit of creating passwords like "k!D9f_Ao" and ensuring
that I change them every 30 days.
Whilst it can be tedious sometimes, I know that one day - vigilance will pay off.
Thanks for your reply. I am investigating your other suggestions too.
-Amos
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: First Bijective Arithmetic Compression
Date: Sun, 19 Dec 1999 12:55:01 GMT
In article <83h22h$fpm$[EMAIL PROTECTED]>, "Gary" <[EMAIL PROTECTED]>
wrote:
>You introduce rules,
>
>>You wrote in your rejected ACM paper:
>>What follows is a set of rules that guarantee ''one to one'' compression in
>a Huffman file >where one uses a table of all 256 leaves:
>
>why are these rules here?
>There here to make your decompression work!
There there to that the compressin decompression follows
the facst for any X then decompress(compress(X))=X and
compress(decompress(X))=X
>I'm babbling about the fact that you should trip these rules randomly in a
>legit compression that doesn't require them. Otherwise their non-tripping
>would tip off an analyst to a legit decompression.
I have no idea what you are talking about. Obvisouly you don't unstand
how the compression works.
>
>Anyway it's academic as your compression is little more than a two way
>process an analyst has to go thru before getting to the actual information.
I am not arguing the merits of useing stronger encryption. By all means
use extra rounds or whitning or what ever you want. What I am saying is
if you use compression. At least use one that does not add information
to the file making it easyer to break. I see you could care less if only
one value of a key can lead to a possible soultion. I prefer that any bad
key leads to a possibel solution that the attacker has to think about before
rejecting a key
>People are better off adding more rounds to their cipher or doing loads of
>time consuming all or nothing transforms, key strenghening etc.
>
>I've taken the time to read and think about your proposal, the least you can
>do is....
>
>
>....the same!
>
I have thought about it a great deal.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: compression & encryption
Date: Sun, 19 Dec 1999 12:46:30 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>Jerry Coffin wrote:
>>
>> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>> > Forgive me for being stupid about this...
>> > I keep on reading about weak compression for encryption etc.
>> > Here is what baffles me. Let's say I use Zlib for compression and then
>> > encrypt the result with RC4 - why is that weak? If Zlib leaves a header,
>> > which I have not seen, that header gets encrypted through RC4.
>> > Trying to crack the cypherfile you must first reverse the RC4 code and
>> > then unzip. So WHY is the use of Zlib weak????
>>
>> The general idea is that if the compression includes a predictable
>> content, you give the attacker some known-plaintext to work with.
>> Quite a few ciphers are easier to attack with known plaintext than
>> without.
>>
>> The alternative view is that the amount of known plaintext revealed by
>> this is typically so small that it makes no real difference -- the
>> attacker has to have broken the encryption quite thoroughly before a
>> tiny amount of known plaintext is even marginally useful. A known-
>> plaintext attack against a block cipher normally has to have ALL the
>> plaintext for a complete block (e.g. 256 bits) known before it's of
>> any use at all.
>>
>> Just for example, many compressors leave a signature at the beginning
>> of their output. This is typically around 3 bytes or so,
>> substantially smaller than a single block with nearly any reasonably
>> recent block cipher of which I'm aware.
>>
>> --
>> Later,
>> Jerry.
>>
>> The universe is a figment of its own imagination.
>
>I've inspected a couple of Zlib compressions without encryption and it
>seems that, indeed, there's a 2 byte header &h78 and a second byte
>dependent on the compression level. If I hardwire the level in my
>source-code to, let's say, 6 then the first 2 bytes in any compressed
>files will always be &H78 9C. Knowing this it is easy to strip the first
>2 bytes off the beginning of the compressed file before encrypting it
>and add them to the beginning of the file after decrypting and before
>un- zipping. What's the problem here?
>Peter
The problem is that the information added is far greater than most
people realize. It is bad to allow an attacker to perform cipher text
only analysis and get structures or data for free from the underlying
compression.
Example if the 2 bytes used are the only bad stuff in the compression
routine you could do this for any binary file.
Add the two bytes that you normally strip off to the front of a binary file
then decompress that file. WHen done recompress that file. Does
it match you original file with the extra 2 bytes of header. Well if it
does thats great. But the odds are if you used compression not deisnged
wirth the thought that encryption is being used after it then it will not
match. It is these strutual weaknesses that allow an attacker more
information to play with. The actual compression can be so bad that
it is possible only one key could exist that that could actually lead
to a file that was compressed with the poor method.
Maybe not today but when quatom or quark or what ever methods get
fast enough why use a compression that is so bad that the only possible
soultion an attacker can settle on is the one you encrypted. This even
applies if you encrypt a random file. So it is not wise to use normal
compression methods which add information to a file when they
compress.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: "Barry" <[EMAIL PROTECTED]>
Subject: Casio's Multi Dimensional Space Rotation encryption
Date: Sun, 19 Dec 1999 20:12:45 +0800
Any information as to the security of this algorithm? Casio say that they
have developed it themselves, but why when there are more reliable,
road-tested ones out in the public domain!
Feedback welcome
Barry.
------------------------------
** 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
******************************
