Cryptography-Digest Digest #470, Volume #10 Sat, 30 Oct 99 02:13:03 EDT
Contents:
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Re: Preventing a User from Extracting information from an Executable
Re: Bruce Schneier's Crypto Comments on Slashdot
Re: Proposal: Inexpensive Method of "True Random Data" Generation (Boaz Lopez)
Re: the ACM full of Dolts? (SCOTT19U.ZIP_GUY)
Re: Build your own one-on-one compressor (SCOTT19U.ZIP_GUY)
Re: Compression: A ? for David Scott (SCOTT19U.ZIP_GUY)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (David
Wagner)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: 30 Oct 99 03:00:08 GMT
Terry Ritter ([EMAIL PROTECTED]) wrote:
: On Tue, 26 Oct 1999 21:54:03 GMT, in
: <[EMAIL PROTECTED]>, in sci.crypt
: [EMAIL PROTECTED] (John Savard) wrote:
: >(perhaps it is cumbersome
: >and impractical,
: I suppose TCP/IP might be called "cumbersome and impractical" -- until
: one starts to feel the advantages. Once a dynamically changing cipher
: scheme is programmed, there should be little need for intrusion into
: applications or users.
: The dynamically changing cipher scheme may be complicated for some
: people to think about, but that is mainly an issue for implementors.
It will require the availability of hardware resources which are, in some
contexts, nontrivial.
: >perhaps the effort involved is not worth it for the
: >security improvement it can bring - because the improvement in
: >security is not that badly needed,
: If you could tell us what level of security you get from your favorite
: cipher, then we could decide whether dynamically changing ciphers
: improved things for you or not.
: Alas, we cannot know how much security your cipher provides. Neither
: can you, neither can anyone else.
Well, the consensus in the academic community, wrong-headed or not, is
that ciphers like the current AES finalists provide an *awful lot* of
security.
You're right: they can't prove that this is correct.
Unfortunately, I can't prove them wrong either, not having an effective
cryptanalytic attack against MARS or Twofish up my sleeve. So I can't
reasonably argue that something like your multi-ciphering proposal *is*
necessary - even if I have to admit, on the other hand, that, as far as I
know, if *might* be.
: >By making the use of a "strong" cipher mandatory,
: >as I've advocated, if worst comes to worst the weak ciphers are still
: >adding to strength, by supplying whitening, at the least, for the
: >strong ciphers.
: As there is no practical cipher which is known to be strong, this
: hardly makes any sense at all.
Translated for the uninitiated:
this is based on considering the one-time-pad to be impractical, and even
ciphers like Blum-Blum-Shub to not be *proven* strong.
But actually, my proposal *does* make a lot of sense; however, I will
reword it slightly to make it more valid from your viewpoint.
Make mandatory the use of a cipher known _not to be trivially weak_; one
cipher from a set that has recieved intensive analysis. Those ciphers are
going to be in short supply for quite some time, as much as we might wish
otherwise.
: >At worst - whitening. At best, an enormous increase in the difficulty
: >of analyzing the cipher stream. (Note that since our negotiation
: >occurs under a single cipher, not a variable one, quintuple encryption
: >under the five ciphers believed strongest would not be inappropriate.)
: >The idea _is_ a very promising one, even if it is not suitable for all
: >applications, and even though it does require that some caution be
: >taken when working out the basic design.
: Yes, of course.
I know that I can hardly claim to be on your side here - when it comes to
the old guard and the mavericks, I have a foot in both camps. But I do
hope to deal with those criticisms of your concept which I can easily,
directly, and convincingly show to be unjustified.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: 30 Oct 99 03:03:33 GMT
David Wagner ([EMAIL PROTECTED]) wrote:
: Hmm. I didn't realize that was what you meant by a non-cryptographic
: negotiation. If it's encrypted, it sounds cryptographic to me.
Although it was noted early on as being encrypted, I think the intent was
to state that the protocol need not be an elaborate one with special
properties; except for being enciphered, other special measures do not
seem to be obviously required.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Preventing a User from Extracting information from an Executable
Date: 30 Oct 99 03:13:01 GMT
Chad Hurwitz ([EMAIL PROTECTED]) wrote:
: Is there a proven way that makes it difficult for a user to see what is stored
: with in an executable they are running?
As you note, this "can't be done as effectively as encryption", because
all the information is there for the microprocessor to execute the code.
One way which probably is reasonably effective on code that isn't
speed-critical, however, would be to use two layers of encrypted P-code
interpreters. That is, one has an encrypted P-code interpreter in machine
language...and one has another encrypted P-code interpreter written in the
first encrypted P-code.
This should be somewhat frustrating and difficult for at least
inexperienced hackers. But, unfortunately, I can't say more for this or
any other approach.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Bruce Schneier's Crypto Comments on Slashdot
Date: 30 Oct 99 03:20:27 GMT
Omar Y. Inkle ([EMAIL PROTECTED]) wrote:
: [EMAIL PROTECTED] (jerome) wrote:
: >from bruce schneier
: >> The best and brightest of the cryptographers are staying in the open
: >> academic community, and are not being swallowed up by the NSA (or
: >> by its counterparts in other countries).
: >How can he affirm that ? It is unlikle that anybody on the world has
: >the knowledge to affirm that, just because it require to know each
: >military cryptographic service and it is a secret field by definition.
: Since he can account for all of the really brilliant cryptographers, the
: only way there could be some working for the NSA would be if they were
: secretly cooking them up in a lab somewhere or recruiting beings from
: another planet.
Is a smiley missing from that paragraph?
The NSA has hundreds of mathematicians working for it; it is not trivial
to judge their calibre (as they naturally have published little in the
open literature) and it does not seem impossible that they, working as
they are in a circumscribed field, constitute a cross-fertilizing
community larger than the open mathematical community in this area.
There are, perhaps, subtle evidences that seem to hint that the NSA has
not yet made another discovery as epochal as public-key cryptography that
the open community has not matched. On the other hand, they do seem to
have expertise in judging the strength of cipher systems, at least against
currently known attacks, much more precisely than is done in public.
John Savard
------------------------------
From: Boaz Lopez <[EMAIL PROTECTED]>
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Date: Fri, 29 Oct 1999 20:59:14 -1000
DSM wrote:
>
> If this is off-topic, please forgive me;
> I am thinking that the groups this message is directed to
> are frequented by those who may be interested in the method.
You are on topic.
>
> ***
>
> Currently, any experiment (or other procedure) for which "true"
> random data is required must be conducted on a computer equipped
> with a special-purpose peripheral device (usually quite expensive.)
> Applications for "true random data" include statistical research
> and strong encryption.
>
> PROPOSAL: Make use of minute electronic inaccuracies in existing
> computer
> systems. Every computer, no matter how skillfully designed,
> contains some component(s) which can be "tortured" to extract
> entropic data.
>
> Examples of Implementation
>
> Basic premise: ALL MODERN DIGITAL COMPUTERS CONTAIN BUILT-IN TRUE-RND
> GENERATORS,
> WHETHER PART OF THE DESIGN OR NOT.
>
> (1)
> The machine you are most likely now using contains a number of quartz
> crystals used for timing various processes, including the operation of
> the CPU. The crystals are accurate to ~0.02%, as I recall. No two of
> even the
> best-made and most accurate quartz crystal timing devices will err in
> exactly
> the same way at any given point of time. Use various system timers to
> extract
> data from relative inaccuracies. Put it through some entropizing
> algorithm,
> mix well.
This has been done before by several people. Yes, it works,
with a degree of quality which is not perfect.
> (2)
> Study in detail a design for a certain computer, no matter which. Some
> element
> of its digital circuts will no doubt produce errors when "flexed". Track
> down
> a weak point in the motherboard, for example. Have the system send data
> through
> said point, test for "quality" (entropy), test for consistency across
> systems
> (test it on 100 machines of same make.) Distribute software library, or
> incorporate
> into operating system.
>
> If anything in this post is new, it is now in the public domain.
If you propose to bend the motherboard and find errors, you will
make a mess that only you would love.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: the ACM full of Dolts?
Date: Sat, 30 Oct 1999 04:59:44 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>On Sat, 30 Oct 1999 00:01:26 GMT, SCOTT19U.ZIP_GUY wrote:
>>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>>>Obviously if you has written your letter with your 'carefree writing style',
>>>it is unlikely to get an answer.
>>>Dolts or not, most people don't like to be called 'pompous assholes'.
>>
>> No while waiting to see if it was to be published I pretended to be a
>>nice guy. But it is hard for me to fake it like most of you can.
>
>I read your article and my opinion of non specialist follows. It is
>on the style, not on the technical part. The style is a part of the game,
>you have to comply with the rules. You may find them stupid, it is
>irrelevant, you don't have the power to change them.
>
>- Your style isn't the 'scientific paper' one. You write as if you talk
> to somebody e.g. "I will now show you how to do that". It isn't a oral
> presentation in a tradeshow but a written work destined to be read
> by specialists.
>- It is usually 'in good taste' to adopt a humble attitude especially
> for beginner. e.g. "i will show you", "the solution" aren't suitable.
>- It is full of typo, it prooves the article hasnt been carefully
> reviewed, not even a spelling corrector, a example of 'carefree'
> attitude.
>- No bibliography, except some internet links. Even dijkstra in 'a
> discipline of programming' has commented about the absence of
> bibliography in his book. A bibliography shows that you have
> read the past work so you won't, less likely, repeat it.
>
>You don't comply with the rules, the referee/reviewer prevents you from
>playing the game. Like in sport, except than here the rules are tacits.
>If you read scientific papers and extracts the common pattern, you
>probably will easily find out them.
>
>My advice: write your next paper so close to the common pattern that
>the referee will judge only on the real contents and not on the style.
>
>All that are my opinions and i am not an authority. Follows my advice or
>not, i wrote that because i think it can help you.
>
>
Actually I was following there style since I edited an existing article so
that it would be in the style they used. It is well know that I can't spell
I did my best and was under the impreesion I would get feed back for that
part. But thanks anyway
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)
Crossposted-To: comp.compression
Subject: Re: Build your own one-on-one compressor
Date: Sat, 30 Oct 1999 05:04:02 GMT
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <[EMAIL PROTECTED]>
wrote:
>SCOTT19U.ZIP_GUY schrieb:
>>
>> In article <[EMAIL PROTECTED]>, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>> >SCOTT19U.ZIP_GUY wrote:
>> >>
>> >> >> >> TIm I did a quick look at it and yes I feel it would work. I
> have
>> > been
>> >> >> >> thinking of a more complicated version but yours is more straight
>> > forward.
>> >> >> >> I hope to is clear to users that as you search the long strings
> are
>> >> >> >> replaced by the short one and that if a short string is found it is
>> >> > replaced
>> >> >> >> by the long one.
>> >> >> >>
>> >> >> >> The weird way I was thinking of doing it was things like "th"
>> > replace
>> >> > with
>> >> >> >> "q" if "th" not followed by "u" this way since q is usually
> followed
>> > by
>> >> > u
>> >> >> >> then it would not be replaced and since th seldom has a u after it
> it
>> >> > would
>> >> >> >> generally be replaced by a q
>> >> >> >> So you can see mine would be messier.
>> >> >> >>
>> >> >> >> An alternate approoach is to allow for more than 256 symbols. You
> can
>> >> > expand
>> >> >> >> from 8 bits to 9 bits with leading bit a zero for common stuff that
>> > way
>> >> >> >> ( note the 9 bit or even 16 bit is a temporary file to allow for
> more
>> > than
>> >> >> >> 256 leaves at start mabye only 267 leaves in huffman tree)
>> >> >> >> "th" could be replaced by a new symbol when at the compression
> stage
>> >> > since I
>> >> >> >> can easily allow 512 symbols with a slight mod to the current
>> > compressor.
>> >> >> > Know
>> >> >> >> on decompression if a "th" not there as a special symbol. It would
> be
>> >> > count
>> >> >> > as
>> >> >> >> a repeat of "th" where combinations of "th" and specail new symbol
>> > would
>> >> >> >> represent the repeat count. This is what I am playing with lately.
>> >> >> >>
>> >> >> >> Keep up the good work
>> >> >> >
>> >> >> >If I understand correctly, you are now on compression not operating
>> >> >> >on groups of 8 bits but on group of bytes. That certainly removes
>> >> >> >the remaining bits problem at the last byte of file on decompression
>> >> >> >of an arbitrary file which is a factor giving rise to the original
>> >> >> >one-to-one problem. However: (1) the frequency counts of such group
>> >> >> >of bytes takes much larger work and the Huffman tree is much much
>> >> >> >larger, (2) due to the larger granularity the compression ratio is
>> >> >> >likely to be poor, I believe.
>> >> >> >
>> >> >> >M. K. Shen
>> >> >> You lost me Mok. I was using groups of 8 bits to mean bytes. Some
>> >> >> people don't use the common defination of byte to mean 8 bits. There
>> >> >> was no change. To clarify
>> >> >> "8bits==byte"
>> >> >
>> >> >Did I ever deviate from the common naming convention of bytes??
>> >> >Note also the arguments of mine in an addendum given in a follow-up
>> >> >posted some hours later. No comments to any argument are yet seen.
>> >> >
>> >> Then reask your question so I know what your asking. You have be
>> >> confused since "on groups of 8 bits but on group of bytes" seems to
>> >> me to mean you don't think 8bits is a typical byte.
>> >
>> >'Groups of 8 bits' means a number of groups, each of which has 8 bits.
>> >'Group of bytes' means a group, which contains a number of bytes. Well,
>> >natural language has the disadvantage of sometimes incurring
>> >ambiguities, particularly on quick reading. Let me say it hence more
>> >clearly: In one case one compresses a string ABCDE... where each A, B,
>> >etc. is a seperate unit having 8 bits (each unit is a group of
>> >8 bits -- commonly also called a byte); one counts the frequencies
>> >of these and designs an optimal coding. In the other case one
>> >has RSTUV...... where RST is one entry in the dictionary, UV is
>> >another, and each R, S, etc is a byte (8 bits), but the units,
>> >on which the compression algorithm operates, are 'RST', 'UV', etc.,
>> >which are each a group of bytes (i.e. each unit may consists of
>> >more than one byte and hence be larger than 8 bits). Is this
>> >clarification o.k. for you? If yes, please kindly proceed to
>> >comment on my posts.
>> >
>>
>> I think your refering to TIm Tylers suggustion.
>> Which describes a one to one mapping which could be used
>> as a compression or even a first pass to my compression
>> program. He was trying to explain how others could start to
>> build there own compressor.
>
>If his mapping is used that way, doesn't that ALSO has to fulfill
>the one-to-one property?
>
>M. K. Shen
Yes and it does.
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: A ? for David Scott
Date: Sat, 30 Oct 1999 04:56:38 GMT
In article <7vcq37$5ld$[EMAIL PROTECTED]>, Clinton Begin <[EMAIL PROTECTED]> wrote:
>I think I found an interesting property of your compression scheme (and
>most likely all compression schemes) that may involve the structure of
>the information.
>
>When your decompressor encounters invalid 'compressed' information, the
>size of the information remains almost the same (within 1% or 2%) when
>the information is 'decompressed'.
What do you mean invalid information?
If you decompress a random file with my method the file gets much longer
try it. This may sound strange but if you compress a random file with my
method it gets longer by only a very small amount. Please try this
since it does not appear to be obvious until you try it.
>
>Obviously, when valid information is decompressed, the size doubles or
>triples (otherwise the 'compressed' information is invalid or the
>information was compressed more than once).
The expansion ratio would vary greatly depending on the file type
that is compressed. Are you using straight ascii or a word document
or what?
>
>Could this be considered a structural weakness? I don't know, but it
>seems that an attack similar to the one you are trying to avoid can be
>employed by a hacker because of this property of one-to-one compressed
>information.
Look this is not encryption. What I have done is to suggest that
if one uses compression at all. One should use compression that
does not add hooks to help break it. There is nothing added to make
the break easier for the hacker?
>
>For example, (if you remember from alt.security.pgp) here is the attack
>(simplified) that is avoided by using your one-to-one compression:
>
>1) Attempt decryption with random key [M=D(C)]
>2) Decompress M to M1
>3) Recompress M1 to M2
>4) If M2 <> M then key is probably invalid. Eliminate key. Go to 1.
>5) Else, perform further analysis on key.
>
>Next, here is the attack that I believe is made possible for the reasons
>I described prior to the last example. This is possible with your
>one-to-one compression example (and most likely other forms of
>compression):
>
>1) Attempt decryption with random key [M=D(C)]
>2) Decompress M to M1 *
>3) Calculate x = AbsoluteValue(SizeOf(M) - SizeOf(M1))
>4) If x < (GetThreshold(SizeOf(M))) then key is may be invalid. **
>Eliminate key. Go to 1.
I am not convenced the attacker could have a rasonable
handle on the threshold values. Since the true value would vary
greatly.
>5) Else, perform further analysis on key.
>
>* If decompression fails, the key is invalid. This note applies to
>other forms of encryption. Yours never seems to 'fail'.
>
>** This may also mean that the information was compressed by some other
>means, before the one-to-one compression. In this case, the hacker
>could easily add another step in the process to attempt a second
>decompression etc. (i.e. the user encrypted a *.ZIP file, which would
>also open up the original attack from the first example).
>
>I believe this attack may be just as dangerous as the one you describe
>(first example). In order to avoid it, the decompressor would have to
>successfully decompress and change the size of the information to make
>it appear as though it could be valid.
LIke I said before I think you are speculating because this is not
what happens when you test it.
>
>I don't know if it would be possible to avoid this attack. In order to
>decompress a file, there always has to be some sort of structure. If
>the structure isn't there, the decompression fails in one way or
>another. Hence, structure is a risk that we cannot avoid. Information
>without structure is not information at all. The best we can do (to
>date) is reduce the amount of redundancy in our structure.
>
>Given this, my feeling is that sticking with the best possible
>compression ratio is probably still the best bet.
>
>Thoughts?
>
>Cheers,
>
> Clinton.
>
>PS: This was a hard concept to describe. If I was unclear, I apologize.
I think you made up this concept with out testing it. Please let me
know where you get the figures 1 ro 2 % change if decompressing
a random file becasue this is not even close to what I get.
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] (David Wagner)
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: 29 Oct 1999 21:09:30 -0700
In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> David Wagner ([EMAIL PROTECTED]) wrote:
> : Hmm. I didn't realize that was what you meant by a non-cryptographic
> : negotiation. If it's encrypted, it sounds cryptographic to me.
>
> Although it was noted early on as being encrypted, I think the intent was
> to state that the protocol need not be an elaborate one with special
> properties; except for being enciphered, other special measures do not
> seem to be obviously required.
I'm not convinced (yet).
First, there are the obvious protocol attacks.
If it's encrypted, it'd better be MAC'ed as well -- otherwise there might
well be ciphertext tampering attacks (e.g., truncate the ciphertext
to delete some of the sender's proposed ciphers). Also, you have
to worry about replay attacks -- so does that mean we need to add a
challenge-response prelude to the negotiation protocol? And as someone
else pointed out, we better make sure the cipher we use to encrypt the
negotiation protocol is different from the cipher we use to encrypt
the rest of our traffic, because otherwise we have a huge single point
of failure.
Once you start getting into this level of complexity, I have to wonder
whether the claim that "it need not be elaborate" is truly realistic.
Second, there are the obvious implementation issues.
Usually if we need a cipher negotiation protocol, it's because we don't
know a priori of any ciphers that are strong enough to satisfy everyone
and yet are implemented everywhere. (After all, if we had one, we'd just
use it for encrypting all our traffic.) But now we've got a bootstrapping
problem: how do we pick which cipher to encrypt our negotiation under?
We could precede it with another negotiation protocol, but that'd be silly.
So I'm not convinced that cipher negotiation is as trivial as it is
made out to be. In fact, experience (SSL, SSH, etc.) seems to suggest
exactly the opposite.
------------------------------
** 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
******************************
