Cryptography-Digest Digest #479, Volume #10 Sun, 31 Oct 99 23:13:03 EST
Contents:
Re: the ACM full of Dolts? (Mok-Kong Shen)
Re: Build your own one-on-one compressor (Mok-Kong Shen)
Re: Scientific Progress and the NSA (was: Bruce Schneier's Crypto
Re: Build your own one-on-one compressor (Mok-Kong Shen)
Re: Compression: A ? for David Scott (CoyoteRed)
Re: Bruce Schneier's Crypto Comments on Slashdot (Tim Tyler)
Re: Doesn't Bruce Schneier practice what he preaches? (John Kennedy)
Re: Doesn't Bruce Schneier practice what he preaches? (Steve K)
Re: Newly Encountered Crypto System (John Kennedy)
Re: Compression: A ? for David Scott (CoyoteRed)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: the ACM full of Dolts?
Date: Sun, 31 Oct 1999 22:17:23 +0100
SCOTT19U.ZIP_GUY wrote:
>
> In article <[EMAIL PROTECTED]>, Mok-Kong Shen
><[EMAIL PROTECTED]> wrote:
> >SCOTT19U.ZIP_GUY wrote:
> >>
> >
> >> Why add anything extra to the plaintext when it clearly is not needed?
> >
> >Well, I think that practical considerations may justify that.
> >Consider the two cases:
> >
> >(1) Add no length information. Use your modification of Huffman.
> >
> >(2) Add length information. Use adaptive Huffman.
> >
> >The first case employs something that is not yet in wide-spread
> >use (and hence the user must study its correctness), while the
> >second is well-known technique. The second, as discussed previously,
> >adds some 'effective key' bits for encryption and that could be
> >advantageous.
> >
> >M. K. Shen
> I am lost. My modifcation was to an "adaptive huffman compression"
> and yes i agree you could add a training string to make the compression
> part of the encryption but I think it is easer to analyse this with no
> training string first. If the compression does what it is supose to do
> then one could add the training string to the overall system since this
> would increae the effective length of the encryption key for the encryption
> process that follows the compression.
Let me repeat: If one has an initial frequency distribution that
the analyst can't figure out, then he can't do any compression or
decompression properly. In that case the failure to meet the
one-to-one property can namely have two different causes:
(1) The key he tried to decrypt is right but his guess of the
initial frequency distribution is wrong.
(2) The key he tried to decrypt is wrong.
Now since his chance of correctly guessing the distribution in
case (1) is very low, this means that encountering the non-one-
to-one property tells him practically nothing whether the key
he tried is right or wrong, i.e. in the present scheme he also can't
get the kind of information that your scheme is designed to prevent
him from obtaining with your one-to-one property. I hope this
is understandable to you now.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Build your own one-on-one compressor
Date: Sun, 31 Oct 1999 22:20:08 +0100
Tim Tyler wrote:
>
> In sci.crypt Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : I meant this:
>
> : Side1 Side 2
> : ABCD HG
> : ABCDHN UK
> : XYZ PQ
>
> : Now XYZABCDABCD goes to PQHGHG. But the modified PQHGHN comes back
> : as XYZABCDHN and this goes to XYZUK. Or do I miss something?
>
> Well, XYZABCDHN would seem to go to PQUK...
>
> However your problem is that your dictionary is fundamentally screwed ;-)
>
> If fails to obey the first constraint on dictionary entries I mentioned in
> my original monograph.
>
> To quote the section from http://www.alife.co.uk/securecompress/ that I
> quoted in the post at the head of this thread:
>
> ``* No string in the tables should contain another such string as a
> substring;
>
> * No leading symbols in any string should exactly match the trailing
> symbols in a different string.''
>
> "ABCD" is a substring of "ABCDHN". Your dictionary thus violates my first
> condition, and should not have been used in the first place.
First, let me remark that your first condition is very unreasonable
for a dictionary. For if your symbols are the normal alphabet,
I don't see that you can construct such a dictionary at all for
transcribing English texts. (Compare a normal dictionary.) The second
condition is similar to that of Huffman encoding (now at byte level),
but it is unreasonable and not applicable for the same reason.
Second, there is no problem for me to construct a case satisfying
your conditions but nonetheless doesn't work:
Side1 Side 2
ABCD HG
HTHN UK
XYZ PQ
XYZABCDABCD goes to PQHGHG. I modify this to PQHTHN. It
comes bach to XYZHTHN. Now this goes to PQUK. Or do I again miss
something?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Scientific Progress and the NSA (was: Bruce Schneier's Crypto
Date: 31 Oct 99 22:35:49 GMT
Nicol So ([EMAIL PROTECTED]) wrote:
: Bruce Schneier seems to suggest that the NSA is not much ahead of the
: open research community. I'm skeptical of that suggestion--I just don't
: think we can reliably tell.
After I read the full interview, I was less concerned with what he had
said. He may well be right that the _lower_ bound on how far NSA is ahead
is either eroding or getting fuzzier. But as long as he avoids any
categorical claims about the _upper_ bound, I am happy he is choosing his
words with care.
John Savard
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Build your own one-on-one compressor
Date: Mon, 01 Nov 1999 00:39:26 +0100
Tim Tyler wrote:
>
> In sci.crypt Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> :> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> :> :> : If I understand correctly, you are now on compression not operating
> :> :> : on groups of 8 bits but on group of bytes.
> :> :>
> :> :> This is a strange way of putting it. There is no possibility of a
> :> :> non-byte aligned end-of-file, if you work with byte-aligned symbol
> :> :> strings.
> :> :>
> :> :> Of course my method is not *confined* to the use of byte-confined
> :> :> symbol strings - but your strings *must* differ from their replacements
> :> :> by a multiple of 8 bits or you will introduce the type of file-ending
> :> :> problems that only David Scott knows how to solve ;-)
> :>
> :> : Let me explain what I meant. You have certain symbols; let's
> :> : for convenience identify these with A, B, C, etc. (they could in fact
> :> : be anything you define through grouping any number of bits). Now your
> :> : dictionary does translations. An example could be that 'ABCD' is
> :> : translated to 'HG'. This is the compression direction. On decompression
> :> : it goes backward to translate 'HG' to 'ABCD'. Am I o.k. till here?
> :>
> :> Y
> :>
> :> : Now I denote the side with 'ABCD' above side1 and the side with 'HG'
> :> : side2. So on compression one matches the source string with entries
> :> : of side1 and replaces the found entries with the corresponding
> :> : entries of side2. On decompression one reverses that.
> :>
> :> Such a scheme would fail to be one-on-one unless all the entries in side1
> :> were also in side2. If not, imagine if the original text was:
> :>
> :> "xxxxABCDxxxxHGxxx". It would "compress" to:
> :> "xxxxHGxxxxHGxxx", which would then decompress to:
> :>
> :> "xxxxABCDxxxxABCDxxx" :-(
>
> : Your argument that both sides should contain the same entires can
> : be trivially shown to be invalid.
>
> ?
>
> : Suppose ABCD and EF are all occurences that are possible in source.
> : I can map ABCD to HG and EF to K. Isn't this a reversible mapping?
>
> <cough> What happens if there's an "HG" in the file initially?
This branch of the thread is no longer up-to-date. I have answered
your post of Sun, 31 Oct 1999 10:51:01 GMT. (Mine is Sun, 31 Oct 1999
22:20:08 +0100). Please respond to that.
Note for my example there that the dictionary is assumed to be
complete for the source, i.e. no source text ever needs any
entry outside of that dictionary.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (CoyoteRed)
Subject: Re: Compression: A ? for David Scott
Date: Sun, 31 Oct 1999 23:54:18 GMT
Reply-To: CoyoteRed (at) Bigfoot (dot) com
On Sat, 30 Oct 1999 22:06:16 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote:
>>Second, if you are using compression to hide patterns, wouldn't XORing
>>a random file be just as effective AND without the "built-in"
>>cryptanalytic tool of compression; one-to-one or other wise?
>
> That is correct if you can XOR with a random file and you can share
>that random file with you buddies you can kiss compression and pgp
>good bye. Since you can use a proveable secure ONE TIME PAD
>the trick is the so called random file.
I gather that this is the case with PGP from the manual. The random
file key (or session key) is part of ciphertext that is sent in the
message. This random file is encrypted with the recipients's public
key. It seems to me that the compression in PGP is really for making
a message smaller, if possible, and the security aspect is, in all
practical purposes, redundant.
And if I understand correctly, conventional cipher are stronger than
public key cipher of a given size. This would mean that to try and
attack the ciphertext portion of PGP file would be harder than to
attack the public key encrypted portion. The problem arises from the
fact you wouldn't recognize the properly decrypted session key when
you saw it, you have to actually try it.
Plus, this is true for only one message, the session key changes for
every message.
While I understand the brute force attack using the angle of
Comp(DeComp(x))=x. (An aside to this is, not every message can be
attacked this way because PGP will not compress uncompressible data.)
Wouldn't it be easier to brute force attack the public key?
Hopefully, you had the public key, of course!
Sequentially generate key pairs of the size and type that you can
glean from the public key. Compare the public key that you generate
with the target's public key, if you have a match then you have the
target's private key and therefore you can decrypt /any/ message that
was encrypted with that key.
I understand that generating public key pairs is a lengthy operation,
but wouldn't this be the angle that an organization would go in
constructing a network of observation? Though it would be harder to
break a public key (presumably because the public key is alot longer
than the session key) , you would only have to do this once versus
every time if you try to break only the session key. One would need
to only build a library of keys and then just apply that key to that
recipient's messages. Much, much faster in the long run. (Assuming
infrequent key changes)
While, granted, one-to-one compression should be included in a more
perfect security scheme just to remove this angle of attack, is it
necessary? Is non-one-to-one compression really that much of a
concern? Is tight compression that important to security if a
sufficiently random key file is used, thus also removing artifacts?
Note: these are the rantings of a crypto-neophyt and I may be
overlooking something important. And I understand that this whole
issue is really academic I'm sure this has been brought up before,
but in case it hasn't...
--
CoyoteRed
CoyoteRed <at> bigfoot <dot> com
http://go.to/CoyoteRed
PGP key ID: 0xA60C12D1 at ldap://certserver.pgp.com
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Bruce Schneier's Crypto Comments on Slashdot
Reply-To: [EMAIL PROTECTED]
Date: Mon, 1 Nov 1999 00:18:03 GMT
[EMAIL PROTECTED] wrote:
: Tim Tyler ([EMAIL PROTECTED]) wrote:
: : "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? ;-)
: Since a quantum computer and a non-quantum computer are two different
: computers, there is no problem here.
: If solving a problem for one possible value takes the ordinary computer X
: seconds, and the quantum computer Y seconds (which will probably be
: larger), then the claim is that solving it for N values
: will take the ordinary computer NX seconds,
: and the quantum computer sqrt(N)Y seconds.
: Since N is dimensionless, and X and Y are not subjected to a square root,
: there is no problem. [...]
So what is "N" for the "arbitrary calculations" under discussion?
...and since when does an ordinary computer facing a problem with N
elements take Nk seconds for some constant "k" - has nobody heard of
parallel processing? ;-)
*However* I look at it - even if I do my best to ignore the fact that
the original assertion is false - it's still the plainest nonsense ;-/
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
This message luxuriously crafted from the finest ASCII.
------------------------------
From: John Kennedy <[EMAIL PROTECTED]>
Crossposted-To: alt.security.scramdisk
Subject: Re: Doesn't Bruce Schneier practice what he preaches?
Date: Sun, 31 Oct 1999 20:39:49 -0500
On Sun, 31 Oct 1999 19:58:22 GMT, [EMAIL PROTECTED] (Roman E.
Liky) wrote:
>(Posted to alt.security.scramdisk and sci.crypt)
>
>In the thread titled "What about Best Crypt" on alt.security.scramdisk,
>John Kennedy <[EMAIL PROTECTED]> wrote:
>
>>Yep, trust math not strangers. Trust open source that anybody,
>>including experts, can find the holes in. If strong cryptography is
>>real then there is no advantage to keeping your source secret and
>>tremendous disadvantages.
>
>>Here's an example, Counterpane Systems has a nice little freeware
>>utility called Pasword Safe. http://www.counterpane.com/passsafe.html
>>It reportedly uses the blowfish algorithm to encrypt your passwords. I
>>think Countepane Systems has a fine reputation. Schneier has a fine
>>reputation. I trust blowfish. I'd like to use the utility, but I won't
>>because I don't see any open source for it. I believe these guys are
>>honest and competent but I won't rely on that belief without open
>>source. Why these folks would release a security system without open
>>source is beyond me. I can't think of any reasons that are favorable
>>to me.
>
>>(If the source to this utility is in fact open and I've just missed
>>it, then of course I apologize.)
>
>If it's available, I sure couldn't find it! This is quite a shock. I
>explored http://www.counterpane.com/passsafe.html and couldn't find any
>source code. I downloaded and unzipped PS171.ZIP and couldn't find any
>source code. And to think that only a month and a half ago in the September
>fifteenth issue of Crypto-Gram, Bruce Schneier wrote this:
>
>>Open Source Cryptography
>
>>Cryptography has been espousing open source ideals for decades, although we
>>call it "using public algorithms and protocols." The idea is simple:
>>cryptography is hard to do right, and the only way to know if something was
>>done right is to be able to examine it.
>
>>This is vital in cryptography, because security has nothing to do with
>>functionality. You can have two algorithms, one secure and the other
>>insecure, and they both can work perfectly. They can encrypt and decrypt,
>>they can be efficient and have a pretty user interface, they can never
>>crash. The only way to tell good cryptography from bad cryptography is to
>>have it examined.
>
>(See the September 15, 1999 issue of Crypto-Gram for the rest.)
>
>So what the Hell is going on here?
I found it vexing myself. I have not asked Counterpane, but I find it
hard to believe nobody has.
------------------------------
From: [EMAIL PROTECTED] (Steve K)
Crossposted-To: alt.security.scramdisk
Subject: Re: Doesn't Bruce Schneier practice what he preaches?
Date: Mon, 01 Nov 1999 01:59:11 GMT
On Sun, 31 Oct 1999 19:58:22 GMT, [EMAIL PROTECTED] (Roman E.
Liky) wrote:
<snip>
>If it's available, I sure couldn't find it! This is quite a shock. I
>explored http://www.counterpane.com/passsafe.html and couldn't find any
>source code. I downloaded and unzipped PS171.ZIP and couldn't find any
>source code.
<chop>
>So what the Hell is going on here?
It has always struck me as odd that someone who has gone to the
trouble to do their homework before deciding how far to trust PGP (or
any crypto software), would use a stand-alone password keeper utility.
To me, it just doesn't fit any kind of rational security model.
If someone has a trusted means of encryption at their disposal, they
can just use it: My reminder notes collection lives in a PGP
encrypted file with its very own key & pass phrase, never uploaded and
reserved for "interrnal use only".
If I was going to use a seperate program for password storage, I would
have to go through the work involved in doing a background check on
it. Even if I decided it was wonderful, I would still hesitate to use
it, because it simply adds one more thing that *might* go wrong. If I
trust PGP for anything, by definition I should trust it to keep my
reminder notes safe & sound.
If R' = the risk of failure with PGP, and
R" = the risk of failure with a password keeper, then using PGP itself
to encrypt a reminder notes file makes R' + R" = R'. PGP is the only
thing under attack, so the risk of failure is the same as if I had no
reminder notes at all.
If I use a seperate application to encrypt my reminder notes, then
there are two possible failure points, and R' + R" > R'.
QED. Right?
------------------------------
From: John Kennedy <[EMAIL PROTECTED]>
Subject: Re: Newly Encountered Crypto System
Date: Sun, 31 Oct 1999 21:10:14 -0500
On Sun, 31 Oct 1999 12:48:03 -0700, [EMAIL PROTECTED] (Jerry Coffin)
wrote:
>In article <7vi41h$5r9$[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] says...
>> Message: To Contact/74-000085
>> Prodigy of Encryption
>> ANECs' algorithm and programming language program is designed specifically
>> for ANEC encode. There is no computer program in existence that can decipher
>> ANEC encryption.
>
>That surely renders the method useless -- if you can't decrypt what it
>has encrypted, then it's essentially equivalent to a simple random
>number generator.
>
>> It is confirmed that the "cyrpto-eccentric has designed his
>> very own program specifically for enciphering and deciphering ANEC
>> encryption
>
>Something's wrong here: just above, you said no program in existence
>can decrypt this encryption. Now you're saying the inventor has
>written a program to decrypt it. Which is it?
It's a pure snake-oil pitch, obviously.
>
>LOTS of people have written their own encryption and decryption
>programs. Many of them use unique algorithms that nobody's bothered
>to break, so there's probably no program other than the original that
>CAN decrypt them, at least without some manual intervention.
>
>That does NOT, however, mean that these programs are particularly
>secure. Having a unique, home-brewed algorithm RARELY contributes to
>security.
-
John Kennedy
The Wild Shall Wild Remain!
http://members.xoom.com/rational1/wild/
------------------------------
From: [EMAIL PROTECTED] (CoyoteRed)
Subject: Re: Compression: A ? for David Scott
Date: Mon, 01 Nov 1999 02:01:20 GMT
Reply-To: CoyoteRed (at) Bigfoot (dot) com
On Sun, 31 Oct 1999 23:21:45 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>That depends on where you get your "random" file the same length as the
>message from - and how it happens that your partner (who you are sending
>the message to) comes to have the same "random" file available to him at
>his end.
See my response to David Scott and while I know this is fairly
specific to PGP it does apply to any scheme that uses a similar scheme
to PGP's
Yes, I can see the problem of a truly random file that is the length
of the message. Because trying to send the symmetric key the length
of the message with the message would about double the plain text
length. I believe PGP uses a 128 bit key and 65 bit block cipher. So,
we don't have a message length key.
I'm not up on how block ciphers work but I'm sure that you don't just
continually XOR with the key over and over. Hell, even I could have
thought of that!
I'm no math wizard, but isn't there a way to generate a sufficiently
large file "random" file from a particular seed key? I remember from
my military days that one scheme is to use a key to generate a
pseudo-random number that was so long that you wouldn't have a repeat
before it was time to change it. And the repeat is a problem when
having to deal with artifacts in the compressed file or patterns in
the message. The more repeats you have the easier to find the
patterns. If we can seed a random file from a key then both problems
of message size and left over artifacts could be eliminated.
As to the question about getting the random file to my buddy (if I
were to XOR the plaintext first) wouldn't it be easy to send the file
encrypted because how would the analyst ever know he has a properly
decrypted file?
I know that this may be elementary to most here, but hey, I'm trying
to learn.
--
CoyoteRed
CoyoteRed <at> bigfoot <dot> com
http://go.to/CoyoteRed
PGP key ID: 0xA60C12D1 at ldap://certserver.pgp.com
------------------------------
** 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
******************************
