Cryptography-Digest Digest #474, Volume #10 Sat, 30 Oct 99 22:13:03 EDT
Contents:
Re: This compression argument must end now (Tim Tyler)
Re: VXD Memory Allocator for Win9x ("Nobody")
Re: Bruce Schneier's Crypto Comments on Slashdot (Tim Tyler)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
([EMAIL PROTECTED])
Re: Unbiased One to One Compression ([EMAIL PROTECTED])
Re: Unbiased One to One Compression ([EMAIL PROTECTED])
Re: Unbiased One to One Compression ([EMAIL PROTECTED])
Re: compression and encryption ([EMAIL PROTECTED])
Re: Portable crypt() function ([EMAIL PROTECTED])
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
([EMAIL PROTECTED])
Re: is <your favorite algo here> a group? ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: This compression argument must end now
Reply-To: [EMAIL PROTECTED]
Date: Sat, 30 Oct 1999 22:50:10 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: Tom St Denis wrote:
:> Ok, explain to me what good knowing the file extension would be?
: That wasn't what he meant -- it was knowing the *type* of file.
: .EXE and .DLL files aren't just arbitrary data that happen to have
: been assigned names ending in those "extensions"; they have a
: specific purpose (executable image or dynamically-linkable object-
: module library) and as such have exploitable internal structure.
: Even a simple .TXT file (meaning: contents are ASCII text) has
: its own characteristic internal structure that is easy to exploit.
: Even if the names (extensions) were changed, the characteristic
: structure of the contents would remain, and that is what can be
: exploited.
IIRC, that was Tom's point.
FWIW, the way I read the original post would treat:
``In fact, I was able to modify the "known plaintext attack" against that
stream cipher to achieve breaks in some cases without knowing
-anything- about the plaintext except that it was, say, a compressed
TXT file, or an EXE or DLL.''
...as equivalent to...
``In fact, I was able to modify the "known plaintext attack" against that
stream cipher to achieve breaks in some cases without knowing
-anything- about the plaintext except that it was a compressed file.''
i.e. the extensions were just examples, and knowing the file-extensions
was scarsely relevant. Knowing that the file had been compressed
might have been the only additional information available.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Life would be easier if I had the source code.
------------------------------
From: "Nobody" <[EMAIL PROTECTED]>
Subject: Re: VXD Memory Allocator for Win9x
Date: Sat, 30 Oct 1999 14:09:46 +0100
Memory allocator:
http://www.cs.utexas.edu/users/emery/hoard/
AK
> > Note to Paul Koning: I followed the link you suggested, but I didn't
find anything which would help much trying to determine the
> > "bookkeeping" strategy. I have a copy of one malloc (for *nix machines)
and the source for Win9X's malloc... neither seems to me
> > quite suitable. I looked at NT's allocation, and tried to find a way
close to it.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Bruce Schneier's Crypto Comments on Slashdot
Reply-To: [EMAIL PROTECTED]
Date: Sat, 30 Oct 1999 23:15:30 GMT
David Crick <[EMAIL PROTECTED]> wrote:
: Dylan Thurston wrote:
:>
:> Indeed, very interesting and well-written. But there is one point
:> where I think he's mistaken:
:>
:> > And when it becomes a reality, it does not destroy all
:> > cryptography. Quantum computing reduces the complexity of arbitrary
:> > calculations by a factor of a square root. This means that key
:> > lengths are effectively halved. 128-bit keys are more than secure
:> > enough today; 256-bit keys are more than secure enough against quantum
:> > computers.
:>
:> I don't think it's true that "quantum computing reduces the complexity
:> of arbitrary calculations by a factor of a square root."
Correct. This has been proven. See "Quantum Computer Can Not Speed Up
Iterated Applications of a Black Box" - by Y. Ozhigov - abstract at:
http://link.springer.de/link/service/series/0558/bibs/1509/15090152.htm
"A factor of a square root"? A square root of *what*?!??
Not *time* certainly - as this is unit-dependant:
sqrt(100) = 10, but sqrt(1) = 1 ...!
I hesitate to suggest it, but could the author have had no idea what they
were talking about? ;-)
: This is indeed true. See Grover's Quantum Database Search algorithm.
I presume this is another example.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
This isn't right. This isn't even wrong.
------------------------------
Date: Mon, 25 Oct 1999 18:20:51 +0200
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
From: [EMAIL PROTECTED] ([EMAIL PROTECTED])
wtshaw wrote:
>> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Terry Ritter)
>wrote:
>> >
>> > Cipher negotiation can be far cleaner -- provided a single selection
>> > mechanism is standardized. If not, then we may see the same sort of
>> > ad hoc stuff we saw with modems.
>> ...
>> >
>> > Because the need is to change ciphers frequently, the desired
>> > negotiation process is not one-time at the start, but rather, a
>> > frequent or continuous process in different messages or sessions.
>> >
>> ....
>> >
>> > There is no other possibility, unless you wish to depend upon the
>> > strength of a cipher which explicitly HAS *no* known or guaranteed
>> > strength. Not having strength is not a trivial detail, this is the
>> > essence of the reason for using a cipher.
>> >
>> > The ability to change ciphers offers each of us the power to choose
>> > what cipher we want to use. This means no government organization is
>> > edicting our use, or forcing it through market pressure. We get to
>> > choose what to use, and what not to use, and to change our minds on a
>> > daily basis. That is not a trivial advantage.
>> >
>> Well, how clean can it be: Figure that you have a list of ciphers which
>> you will accept. It is up to the sender to speak in one or them, at
>> least.
>>
>> Figure that you develop a means of generating a key for any of them, but
>> from something which may be acceptable in form to anyone of them, text
>of
>> some sufficient length.
>>
>> The recepient generates all the keys as needed, tries one at a time with
>> an appropriate algorithm on the ciphertext. The system should lock to
>the
>> one with the most appropriate recovered plaintext, likely only one that
>> makes sense.
This becomes trivial if the initial message contains a standard plaintext.
>>
>>
>> To change cryptosystems, just do it; at the other end, detection falls
>out
>> of lock as the current system fails to recover reasonable output, and go
>> back to checking the various algorithms, getting the new system, locking
>> until unlocked.
>>
>> Sounds simple enough to me, but who am I to judge?
>> --
>> Sometime ago, Gates bought lots of shares of Apple.
>> My preference is to keep the Worm out of the Apple.
{}{}{} Posted via Uncensored-News.Com, http://www.uncensored-news.com {}{}{}
{}{}{}{} Only $8.95 A Month, - The Worlds Uncensored News Source {}{}{}{}
{}{}{}{}{} Five News Servers with a BINARIES ONLY Server {}{}{}{}{}
------------------------------
Date: Sun, 24 Oct 1999 22:49:32 +0200
Subject: Re: Unbiased One to One Compression
From: [EMAIL PROTECTED] ([EMAIL PROTECTED])
Tim Tyler ([EMAIL PROTECTED]) wrote:
>: However, if you *systematically* choose to compress to one type of file
>: rather than another one, your compressor may well be adding information
>to
>: the compressed file, which was not present in the original message.
>: It /may/ be possible for an attacker to utilise information added in
>: the process of compression to aid his attack on the subsequent cypher.
>: Making the cypher "one-on-one" avoids the possibility of any information
>: or regularity *added* by the compressor being used in the attack on the
>: cypher - since no information has been added.
And, by the way, there is a section on my web page about "Red Thread
Resistance", which talks about ways to minimize an encryption program's
opportunity to exploit a subliminal channel by means of random IVs and the
like.
However, I felt that the small number of bits added - at the very
beginning of encipherment - to make the number of bits come out to an even
multiple of 8 was not a significant hazard, even if other things, like
64-bit IVs, can be usefully eliminated.
John Savard
{}{}{} Posted via Uncensored-News.Com, http://www.uncensored-news.com {}{}{}
{}{}{}{} Only $8.95 A Month, - The Worlds Uncensored News Source {}{}{}{}
{}{}{}{}{} Five News Servers with a BINARIES ONLY Server {}{}{}{}{}
------------------------------
Date: Sun, 24 Oct 1999 22:52:09 +0200
Subject: Re: Unbiased One to One Compression
From: [EMAIL PROTECTED] ([EMAIL PROTECTED])
SCOTT19U.ZIP_GUY ([EMAIL PROTECTED]) wrote:
>: But could you anwser one question directly. Can your
>compress/decompression
>: method take a random binary file of bytes then uncompress it a file.
>Which
>: when compressed will give back this same file? I don't think this
>question
>: is to hard to anwser or to test for. But I either think you don't
>understand
>: this or don't want to understand this particular point.
No, it can't, and thus it isn't really "one-to-one". It only satisfies the
weaker condition that decompression is "onto". When compressed, a file
gives one of the files it could be decompressed from. In a response to Tim
Tyler's post, I explained the reason that I have avoided the one-to-one
method that I can think of.
John Savard
{}{}{} Posted via Uncensored-News.Com, http://www.uncensored-news.com {}{}{}
{}{}{}{} Only $8.95 A Month, - The Worlds Uncensored News Source {}{}{}{}
{}{}{}{}{} Five News Servers with a BINARIES ONLY Server {}{}{}{}{}
------------------------------
Date: Sun, 24 Oct 1999 22:46:29 +0200
Subject: Re: Unbiased One to One Compression
From: [EMAIL PROTECTED] ([EMAIL PROTECTED])
Tim Tyler ([EMAIL PROTECTED]) wrote:
>: I have a high opinion of John Savard, based on his usenet contributions.
Why, thank you.
>: However, I'm not sure I've done as well as I could have done in
>explaining
>: why having one - and only one - decompressed file for every compressed
>one
>: is potentially important to security.
>: If you *don't* have this, then the compressor, when compressing, can
>: choose more than one compressed file to compress to.
>: If the compressor chooses between these files at random, then there's no
>: security problem - you just wind up with fatter compressed files than
>you
>: need to.
Yes, you need to choose between those files at random.
>: Making the cypher "one-on-one" avoids the possibility of any information
>: or regularity *added* by the compressor being used in the attack on the
>: cypher - since no information has been added.
>: Attacks can still be based on any regularities left by sub-optimal
>: compression, though.
There is a problem with one-to-one compression.
As I recently noted, I had found a way to perform Huffman compression so
as to approximate the one-to-one condition between the files to be
compressed, and strings of bits of arbitrary length.
But the next step, converting to a message that is a whole number of bytes
in length, is the problem.
Here is an example of a mapping between messages an arbitrary number of
bits in length, and messages that are an even number of bytes long.
Leave all of the message alone, except for the last 0 through 7 bits.
These may have 255 possible values, so these can be coded in the last byte
as follows:
Code Represents
00000000 not used
00000001 <nothing>
00000010 0
00000011 1
00000100 00
00000101 01
00000110 10
00000111 11
00001000 000
...
00001111 111
00010000 0000
...
00011111 1111
00100000 00000
...
00111111 11111
01000000 000000
...
01111111 111111
10000000 0000000
...
11111111 1111111
Each byte represents the bits that follow the first 1 in the byte.
This is the most efficient way to represent arbitrary-length bit strings.
What is wrong with it?
When we compress a message, it is reasonable to expect that, for good
compression:
- the probability of each bit in the compressed message being a 0 or a 1
is 50% each way, and
- the probability of the number of bits in the message being of the form
8n+k, for k from 0 to 7, is 12.5% for each value of k.
Given that, we find that the last byte of the message, using the
representation above, has the probabilities:
00000001 12.5%
00000010 6.25%
00000011 6.25%
00000100 3.125%
...
00000111 3.125%
00001000 1.5625%
and so on.
This problem is _fundamental_, and not due to my particular choice of
representations. The probability distribution of "random strings of bits
of arbitrary length" and of "random strings of bits an even number of
bytes in length" are different in shape.
Of course, simple techniques can distribute this bias throughout the
message. For example, XOR the last byte with a checksum of the rest of the
message.
But in that case, the whole idea of one-to-one compression is not
necessary, since whether or not the message ends in the middle of a
Huffman symbol can only be found out by reading the message from beginning
to end.
Adding random padding, on the other hand, lets the two probability
distributions match in shape. The case that is twice as likely as another
case has one more bit of random padding added to it.
John Savard
{}{}{} Posted via Uncensored-News.Com, http://www.uncensored-news.com {}{}{}
{}{}{}{} Only $8.95 A Month, - The Worlds Uncensored News Source {}{}{}{}
{}{}{}{}{} Five News Servers with a BINARIES ONLY Server {}{}{}{}{}
------------------------------
Date: Sun, 24 Oct 1999 23:06:15 +0200
Subject: Re: compression and encryption
From: [EMAIL PROTECTED] ([EMAIL PROTECTED])
In article <r7JQ3.5246$[EMAIL PROTECTED]>,
gtf[@]cirp.org (Geoffrey T. Falk) wrote:
>> Precisely. I was not talking about LZ, which are far from headerless
>> algorithms. All flavours of Lempel-Ziv rely on pointers throughout the
>> message, which essentially provide header-type information that can
>> be used by an attacker.
>>
>> An example of a headerless algorithm would be adaptive arithmetic
>> or Huffman coder/decoder. The output can be considered as a bit stream
>> with no special structure.
If I am not mistaken LZ methods have no implicit header information.
They build their 'dictionaries' as they process the input. Just like
adaptive single symbol entropy coders (i.e huffman, arith, range,
etc...)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
{}{}{} Posted via Uncensored-News.Com, http://www.uncensored-news.com {}{}{}
{}{}{}{} Only $8.95 A Month, - The Worlds Uncensored News Source {}{}{}{}
{}{}{}{}{} Five News Servers with a BINARIES ONLY Server {}{}{}{}{}
------------------------------
Date: Mon, 25 Oct 1999 00:08:04 +0200
Subject: Re: Portable crypt() function
From: [EMAIL PROTECTED] ([EMAIL PROTECTED])
In article <7uvfcj$[EMAIL PROTECTED]>,
Chad Hurwitz <[EMAIL PROTECTED]> wrote:
>>
>>Is there a standard function that will be in a library on both a
>microsoft
>>platform AND a unix platform? I can't find any crypt library functions
>>in micro$ofts Visual C++ compiler help.
>>
>>If not, is there source publically available for a portable
>>crypt(key,message) and decrypt(key,crypt_message) or are these kind of
>>things government regulated?
>>
>>--
>>/-------------------------------------------------------------------\
>>| spam if you can, spam if you dare, spam if you must, i won't care |
>>| spam is futile, spam is free, spam is filtered, so i won't see |
>>\-------------------------------------------------------------------/
to answer my own question i found a nice link
http://www.eskimo.com/~weidai/cryptlib.html
--
/-------------------------------------------------------------------\
| spam if you can, spam if you dare, spam if you must, i won't care |
| spam is futile, spam is free, spam is filtered, so i won't see |
\-------------------------------------------------------------------/
{}{}{} Posted via Uncensored-News.Com, http://www.uncensored-news.com {}{}{}
{}{}{}{} Only $8.95 A Month, - The Worlds Uncensored News Source {}{}{}{}
{}{}{}{}{} Five News Servers with a BINARIES ONLY Server {}{}{}{}{}
------------------------------
Date: Sun, 24 Oct 1999 23:26:59 +0200
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
From: [EMAIL PROTECTED] ([EMAIL PROTECTED])
In article <7uueot$[EMAIL PROTECTED]>,
"Roger Schlafly" <[EMAIL PROTECTED]> wrote:
>> Even if your analysis is correct, it is stronger by only a trivial
>> amount. It would be more secure to just increase the key size
>> by a few bits.
If my analysis is correct then it shows that it does make sense to use
a pool of independent ciphers because it increases security (against
any attack) without decreasing the speed of the system.
Now, I agree that if the pool is not very large then the practical
advantage is negligible. If somebody discovered a k=0.5 attack against
the AES class ciphers then the "fourAES" cipher I described would
increase the cost of attack only in 25% (not even one additional bit of
security).
Using multiple ciphers becomes interesting only with M>>1. Let us for a
moment assume we had 2^128 independent ciphers (M=128). If we use only
one of them with a key of 256 bits and somebody discovers an k=0.2
attack then we get a cipher with 256*0.2=51 bits of effective security,
i.e. we have a catastrophic failure in our hands. If, on the other
hand, we use all of them with a key of 128 bits and use the other 128
bits of the key to index the pool of ciphers, then the average cost of
the attack 2^(k*N-1)*(2^M+1)=2^153, i.e. it would afford us a very
significant 153 bits of security.
How do we get 2^128 ciphers? First of all observe that each individual
cipher can be very weak indeed. For large M, the cost of breaking the
"pooled" cipher would be 2^(k*N+M-1), i.e. that cipher's strength would
be k*N+M-1 bits. Even if k=0.01, i.e. even if each individual cipher
offers only 1.28 bits of security, the "pooled" cipher would still
offer 128.28 bits of security. So the question here is how to produce a
great many independent ciphers without much thought about the strength
of each individual one.
The best way I can imagine to achieve this is to create a cipher
generator: take a large number of bits out of the key and use them to
produce a cipher (code+tables). Use the rest of the key plus the
plaintext blocks to drive that cipher and produce the ciphertext.
This is almost exactly what my Frog algorithm does. Only about 5.6% of
the key material is really used as key data. The rest is used for
building tables and for "expressing" code. The AES specifications
didn't allow assembly code - therefore the only code variability I
included in my AES candidate was key dependent addresses. Frog is not
unique in that respect. Twofish can also be considered a "pool" of 2^64
ciphers because it uses that many key dependent tables. The big
question for any such cipher is whether the cipher instances are
independent.
I have written a more generalized version of Frog that works like a
compiler and literally produces code. That version generates key
dependent instructions as well as key and data dependent addresses.
Therefore, arguably, the generalized version of Frog covers a much more
"variable" subset of the cipher space, which brings it nearer to the
ideal of a generator that produces independent ciphers.
Sent via Deja.com http://www.deja.com/
Before you buy.
{}{}{} Posted via Uncensored-News.Com, http://www.uncensored-news.com {}{}{}
{}{}{}{} Only $8.95 A Month, - The Worlds Uncensored News Source {}{}{}{}
{}{}{}{}{} Five News Servers with a BINARIES ONLY Server {}{}{}{}{}
------------------------------
Date: Mon, 25 Oct 1999 01:18:07 +0200
Subject: Re: is <your favorite algo here> a group?
From: [EMAIL PROTECTED] ([EMAIL PROTECTED])
In <[EMAIL PROTECTED]> Fiji
<[EMAIL PROTECTED]> writes:
>>I have seen people discuss whether DES is a group. I believe I understnad
>>the issues if it were a group. The question is how come nobody seems to
>>worry about other algos? What about hashing algorithms? What about other
>>Feistel ciphers? Is it just because nobody has done this yet?
DES being a group became of interest when people were wanting to use
triple DES as a crypto algorithm. If it were a group then doing triple (
or 10^4) DES would have been useless since any number of DES would be
equivqalent to singel DES.
Hashing cannot be a group since hashes map many to one.
{}{}{} Posted via Uncensored-News.Com, http://www.uncensored-news.com {}{}{}
{}{}{}{} Only $8.95 A Month, - The Worlds Uncensored News Source {}{}{}{}
{}{}{}{}{} Five News Servers with a BINARIES ONLY Server {}{}{}{}{}
------------------------------
** 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
******************************
