Cryptography-Digest Digest #207, Volume #10 Thu, 9 Sep 99 04:13:03 EDT
Contents:
Re: "NSA have no objections to AES finalists" (SCOTT19U.ZIP_GUY)
Re: Unix Crypt on MS Windows platform (Bill Unruh)
Re: General encryption question (SCOTT19U.ZIP_GUY)
Re: _NSAKey (Bill Unruh)
Re: Neal Stephenson's Cryptonomicon: Crypto Cop-Out (David A Molnar)
Re: Neal Stephenson's Cryptonomicon: Crypto Cop-Out (Stefan E. Jones)
Re: some information theory (Anti-Spam)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: "NSA have no objections to AES finalists"
Date: Thu, 09 Sep 1999 05:13:14 GMT
In article <[EMAIL PROTECTED]>, David Crick <[EMAIL PROTECTED]> wrote:
>For what it's worth....
>
>"On Friday, a source close to the NSA told Wired News that --
> at the Commerce Department's request -- the agency reviewed
> the five and decided it had no objections to any of them.
>
> [Carl] Ellison said there's one very good reason for the
> NSA to be telling the truth about the ciphers' security:
> The government will be using it, too."
>
> http://www.wired.com/news/news/business/story/21484.html
>
Oh really I thought AES was for unclassifed data. Is the US going to use AES
for "top secrect" data. HELL NO THAT is BULL SHIT. And only a fool would think
the NSA would give an honest anwser to anything about encryption.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Unix Crypt on MS Windows platform
Date: 9 Sep 1999 04:28:05 GMT
In <[EMAIL PROTECTED]> John Brugioni <[EMAIL PROTECTED]> writes:
>Anybody have a utility to do unix crypt on Windows NT, 95 or 98?
Which one? If you mean the password hash, then any of the versions (eg
in cryptlib or in Crack) are simple enough that there should be no
problem in compiling them on Win. If you mean crypt(1) the encryption
algorithm, then you would not want to, since it is extremely weak.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: General encryption question
Date: Thu, 09 Sep 1999 05:24:45 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>Is it possible to decrypt and
>execute a file/application
>without at any time leaving it
>in a decrypted state on the
>hard drive?
>
>Andrew
one way would be to boot your system off a floppy and never use the hard
drive. then all your data is either in memory or on the floppy.
But not sure if the over bloated windows 95 and above can ran that way
very well you may need DOS 3 or something like that.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: talk.politics.crypto
Subject: Re: _NSAKey
Date: 9 Sep 1999 04:14:09 GMT
In <eOxdlKH##GA.273@cpmsnbbsa03> "Microsoft Mail Server" <[EMAIL PROTECTED]>
writes:
>good point, the assumtion that the government is vile, devious, sinless, and
>above the law has been created from single examples of deviant individual
>misbehavior on the part of selected events.
?? Of course the examples are "selected". To show that the agents of the
government can misuse their power, you select examples where that power
has been misused. To call them "deviant individuals" begs the question,
because it is the legitimate power which is invested in the government
which allows them to misuse that power. Thus, if for example, the
government is given a list of passphrases, it is the existence of those
passphrases which would allow a "deviant" to misuse them.
One sets in place checks and limits on the power of government precisely
because one KNOWS that such deviant individuals will exist on each and
every government. If we thought all government officials were saints, we
would not need government checks. We know that are not all saints, we
know that venal, corrupt, powerhungry individuals sometimes find them
selves with the power to misuse the instruments of government power that
we put restrictions on those powers.
It is certainly not true that everyone in governement is corrupt or
evil. Many, most, are trying to do a good job and trying to help the
country. However one needs protection against those that do not.
One also needs protection against "conflicts of interest". Many people,
persuing one particular goal, which they feel is a legitimate moral
goal, forget that one can be evil, can carry out attrocious behaviour,
persuing those laudable goals-- whether this is the defence of the
people against terrorists, or drugs or against those incompetent
politicians of the other side.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Crossposted-To: rec.arts.sf.written,alt.cyberpunk
Subject: Re: Neal Stephenson's Cryptonomicon: Crypto Cop-Out
Date: 9 Sep 1999 06:52:58 GMT
In sci.crypt Stefan E. Jones <[EMAIL PROTECTED]> wrote:
> Interesting analysis!
> Watch for the flames on this one.
Indeed. Hopefully not in sci.crypt.
-David
------------------------------
From: [EMAIL PROTECTED] (Stefan E. Jones)
Crossposted-To: rec.arts.sf.written,alt.cyberpunk
Subject: Re: Neal Stephenson's Cryptonomicon: Crypto Cop-Out
Date: 9 Sep 1999 06:41:55 GMT
Interesting analysis!
Watch for the flames on this one.
On Thu, 09 Sep 1999 00:02:48 GMT, [EMAIL PROTECTED]
wrote:
> Crypto Cop-Out
>
> If ever a cyberpunk novel packed political
>punch, this is it. Neal Stephenson's
>Cryptonomicon hums with manic caffeinated glee,
>proclaiming, Freedom through technology! Crypto-
>Anarchy now! Crypto-Anarchy being a networked
>global economy where bootleg information and
>untraceable digital cash flow free, out of reach
>of government regulatory agencies like the FBI
>and the IRS.
>[MASSIVE SNIP]
> But along comes Cryptonomicon, showing how
>untraceable e-cash gets put into place in a world
>recognizably ours, by idealistic technophiles
>like myself, working alongside drug lords and
>dictators. They had to do it, because... well,
>something or other.
>
> Though libertarian agit-prop, Cryptonomicon
>isn't Birth of a Nation or The Turner Diaries.
>There is good mixed with the bad -- like,
>Stephenson obviously detests racists. But the
>book makes an emotional appeal for Crypto-Anarchy
>without adequately exploring core issues,
>fostering the smug illusion of understanding
>where a more thoughtful job might have stimulated
>intelligent discourse. Stephenson needs to look
>at Crypto-Anarchy more critically if he really
>wants to shed light on the future of Internet
>cash.
--
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
SeJ@ay-oh-el-dot-com ~ stefanj@eye-oh-dot-com
http://www.io.com/~stefanj/
CHARGES APPLIED FOR UNSOLICITED COMMERCIAL EMAIL!
------------------------------
From: Anti-Spam <[EMAIL PROTECTED]>
Subject: Re: some information theory
Date: Thu, 09 Sep 1999 00:46:46 -0700
Tom St Denis wrote:
>
> If I am not wrong, the following statement is true:
>
> 1) There is no method of INCREASING or DECREASING the entropy of a message M
> (outside of adding/removing information).
>
> If that is true, then no matter what function you employ (be it ROT13,
> compression, etc...) the actual secret message (before being encrypted) will
> always have H(M) bits of 'information'.
>
> I am trying to figure this out to shut DS up for once. I still don't believe
> compression before encryption increases security in REAL cryptosystems. I
> still believe that it can slightly make things more complicated, but it's
> SOLE job is to make M shorter (by removing redundancy).
>
> 2) Is it not true that no matter what compression algorithm (C for this
> example) H(M) will always equal H(C(M))? If so then the message is no more
> complicated after compressing with 'one-to-one huffman' or deflate, or lz78,
> or lzss, or ...
>
> (btw I make the assumption that the encryption and compression are both fully
> invertable.) Tom -- damn windows... new PGP key!!!
> http://people.goplay.com/tomstdenis/key.pgp (this time I have a backup of the
> secret key)
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
I've followed these thread debates on encryption vs. compression for
months without saying anything. Now it's time to speak.
This is a long post, so here's the summary and then read all below it to
see how I back up this statement:
Compression with huffman-encoding type schemes is identical to a
substition encipherment.
The relative order of SYMBOLS as ENCODED in the uncompressed data/file
with ASCII, UNICODE or any other binary representation is PRESERVED by
the compression and appears intact in the compressed data/file. Each
SYMBOL is ENCODED with a shorter bit string in the compressed file/data,
but the SYMBOLS still appear in the same frequency and order as they did
in the original uncompressed data/file. Compression is just the encoding
of the SYMBOLS with the least number of bits (ie. as close as possible
to a Maximal Entropy Code.)
Compression PRESERVES the TOPOLOGY of the SYMBOLS as ordered elements in
a finite set. SYMBOLS in positions 1, 2, 3...i, j, k... n in an n
symbol long message that are neighbors, encoded in the uncompressed
data/file, are still neighbors, encoded in the compressed data/file.
Compressing data/files prior to encryption with a cipher system does not
alter the frequency of the SYMBOLS encoded in the compressed data/file
relative to their original frequencies in the uncompressed file/data.
Compressing prior to encrypting does not permutate the order of the
SYMBOLS encoded in the compressed data/file relative to their original
order as encoded in the uncompressed file/data. Compression only alters
the encoding of the SYMBOLS to achieve the maximal entropy possible as a
function of the probabilites of the SYMBOLS themselves.
So yes, Tom, you are on the right track. This arguement can be extended
to other compression schemes (in fact , its a good idea for a paper.)
Now down to the nitty gritty:
First, Compressed data is NOT necessarily random data. Many of us assume
the compressed form of a file is "equivalent" in some form to true
random data. It is not. Compressed files will not pass statistical
tests for random bit streams. A compressed file is non-random. Say the
compressed file is n bits long. Apply the five basic tests for
randomness to that binary sequence ( see Handbook of Applied
Cryptography, Section 5.4.4).
1. The Frequency Test ( or mono-bit test) - do 1s and 0s occur in the
same total number (with some margin of difference based on the
Chi-Square test.) A compressed file SHOULD pass this test.
2. The Serial Test ( two-bit test) - do the patterns 00, 01, 10 and 11
occur with the same frequency? Here we see a good chance that the
compressed file should not pass this test, espcially if we use Huffman
Encoding or Variable Huffman encoding.
3. The Poker Test ( a generalization of the Frequency test )- looks for
the number of occurances of k bit sequences ( such as 010, or 0110, or
001, or 1000101, etc..) in the m bit sequence. (See ref. Handbook for
exact details ) Again, compressed data should not pass this test.
4. The Runs Test - looks at the number of runs of 0s (gaps)of various
lengths (example 00, 000, 0000, etc.) and 1s (blocks)(example 11, 111,
1111, 11111, etc.) that appear in the candidate random data verses the
expected number of gaps and blocks of various sizes that should appear
in random data ( with some margin of difference based on the Chi-Square
test.)
A compressed file should not pass this test.
5. The Autocorrelation test - look for correlations between sequences of
bits in the candidate random data with itself in non-cyclic shifts. A
compressed file should exhibit correlations far larger than those
expected for random bits.
Why should a compressed file fail four out of five of these tests?
Compression schemes like Huffman Coding,Shannon-Fano Coding do the
following:
Look the set of symbols in the file or data before compression ( or the
"alphabet" of symbols in the data.) These symbols are strings of bits
(0s and 1s) that appear many times in the data. Many times we use ASCII
or UNICODE characters of fixed bit lengths. Determine the total number
of all symbols in the file or data. Call it k. Determine each unique
symbol's probability of occurance in the data by its frequency (unique
symbol count/total number of symbols).
Now, using the probability of occurance for each defined symbol from
above, define a new encoding for that symbol. These new encodings are
binary strings but they are not necessarily the same length as the
binary strings representing the symbols in the original data or file.
No two new encodings will be the same binary string. Each new encoding
string shall be constructed such that no additional information is
necessary to identify where that encoding starts or ends when it is
written before or after another encoding string for a different symbol.
Keep a dictionary that maps the correspondance between the original
symbol and its binary representation in the original file or data and
its new encoding bit string in the compressed file or data.
The net result is that if you order the symbols by their probabilites,
p1 >= p2 >= p3 >= p4... >= pk , the lengths of the binary strings of 1s
and 0s for the new encodings for the symbols are in a similar order but
decreasing in magnitude, L1 <= L2 <= L3 <= L4 ... <= Lk. Now these new
encoding bit strings for the symbols should be less than (or equal) to
the bit lengths of the encoding for the original symbols. If some are
less than the original symbols' encoding bit lengths we WILL get
compression. Huffman and Shannon-Fano algorithms use a binary tree
algorithm to establish the 1/0 bit string representations for the
symbols as a function of frequency. Usually these encodings use equal
numbers of 1s and 0s. (they occur with equal frequency)
We now take the original data or file and REPLACE the encoding of the
symbols as appeared in the original data or file with these new encoding
strings (which are different than the original bit strings for those
symbols.) If the new encodings are shorter in bit length than the
original encodings for the symbols we get smaller (less bits) data or
files.
There is a one-to-one correspondance between the occurances of the
symbols (as encoded in ASCII or UNICODE for example) in the original
data or file and the occurances of these same symbols in their new
encoding for compression. THIS IS AN IMPORTANT POINT. We have
substituted different encodings for those symbols in the compressed data
or file. That is all we have done. We do not alter the relative
positions of the symbols. There is no shuffling, no rearrangement of
symbols occurances spatially in the data/file.
At best what we have done can be called a "substitution encipherment"
from a cryptological point of view but nothing more than that. If we had
36 e's in the original uncompressed file, and e was encoded in ASCII, in
the compressed file we now have 36 occurances of a new encoding string
for e (say its 001) that is less than the ASCII bit encoding bit
length. The relative order of symbols as they occurred in the
uncompressed data/file IS PRESERVED BY COMPRESSION in the compressed
data/file. The new encodings appear many times in the compressed
data/file, and in the same frequency as the SYMBOLS for which they stand
as those SYMBOLS appeared in the uncompressed data/file.
This is necessary for the decompression to work! If the ordering of
symbols is not preserved then decompression back to the original
encoding in the uncompressed file/data will not return the original
data/file. Decompression is just the recognition of the smaller
encoding strings in the compressed data/file for replacement with the
corresponding longer, original binary represenation for that symbol.
That original represenation is in the dictionary for the compressed file
generated during the compression (and must accompany the compressed
file/data in an uncompressed form to ensure the decompression can occur
- or be available at the time of decompression if sent by other means.)
Tnis is why compressed data/files will/should fail the Serial test,
Poker Test, Runs test and Autocorrelation tests for true randomness. The
only cryptoanalytic challenge posed by compression is the cryptanalysis
of a substitution cipher. The SYMBOLS that appeared in the uncompressed
file/data are encoded with different codes in the compressed file/data.
That's at most a substitution cipher. If we have only the compressed
data/file, we can "attack" it as a substitution cipher.
What makes this more of a challenge is the definition of those SYMBOLS.
If the symbols are ASCII or UNICODE then I could apply language models
in the "cryptanalysis" of the compressed data to identify probable
compressed encodings for e, i, th, etc. If I just select every k bits
as the occurance of a symbol, then the set of unique k bit values that I
find (if much smaller than 2^k in number ) serves as my "alphabet" and I
encode them with new codes that are less than k bits long to get
compression. Here there are no language models to help me analyize the
compressed data/file to try to determine the compression encoding. But,
if I know what k is and I know something about the nature of what was
compressed then I can use other examples of that compressed data/file to
try to put together reasonable estimates of a dictionary to use in
substitution cryptanalysis, and I can try autocorrelation tests on the
compressed data to spot the compression encoding strings (which will
repeat in the compressed data/file and thus will autocorrelate.)
For those more mathematically inclined ( I think of rosi as I write
this), Compression preserves the TOPOLOGY of SYMBOLS as they appear in
relative order (neighbor to neighbor) and frequency in the uncompressed
data/file. That preserved topology is a doorway to analytical attack.
For example, let's say this is the message in SYMBOLS:
T H E M E S S.......
when encoded before compression, in binary,
001001 101011 001001 110111 001001 101010 101010
But, when compressed, T now is encoded as 0111, H as 0011, E as 01, S as
10101, M as 1001...
(just examples, didn't do the math for the encoding.....)
0111 0011 01 1001 01 10101 10101
We see the bit length of the message is shrinking with the new encoding,
but note the occurances of the new codes follows the relative ordering
of the occurances of the uncompressed code. An e no matter how encoded
still follows the H no matter how encoded. A T starts the message, no
matter how encoded. We can define a point-set topology on the SYMBOLS
as they occur in the original message, and we can show that this
point-set topology is preserved by the compression.
Just my two cents,
[EMAIL PROTECTED]
------------------------------
** 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
******************************
