Cryptography-Digest Digest #73, Volume #11 Tue, 8 Feb 00 15:13:02 EST
Contents:
Compression cannot prevent plaintext recognition (was Re: is signing a (David
Hopwood)
Re: Anti-crack (Mike Rosing)
Re: permission to do crypto research (Xcott Craver)
Re: Latin Squares (was Re: Reversibly combining two bytes?) ("Tony T. Warnock")
Re: Seeking Information on FRACTAL CRYPTOGRAPHY (John Savard)
Re: Anti-crack ("John E. Kuslich http://www.crak.com")
Re: Anti-crack ("Trevor Jackson, III")
Re: Compression cannot prevent plaintext recognition (was Re: is signing a
signature with RSA risky?) (John Savard)
Re: Anti-crack ("John E. Kuslich http://www.crak.com")
I'm returning the Dr Dobbs CDROM (Victor Zandy)
----------------------------------------------------------------------------
Date: Tue, 08 Feb 2000 05:43:29 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Compression cannot prevent plaintext recognition (was Re: is signing a
=====BEGIN PGP SIGNED MESSAGE=====
Tim Tyler wrote:
>
> Anton Stiglic <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> Anton Stiglic <[EMAIL PROTECTED]> wrote:
> :> : Tim Tyler wrote:
>
> :> :> A compressor with an accurate model of the data will not just make it more
> :> :> difficult to detect a correct message from an incorrect one, it can make
> :> :> it *massively* more difficult.
> :>
> :> : Not true at all. If a compressor is used, the attacker will probably have
> :> : his hands on it, it won't complicate stuff much for him at all!
> :> : This is what people tend to forget...
[...]
> :> Compression *can* make finding halting criteria harder.
>
> : No, it does not make it any harder. The attacker just tries to decrypt
> : to some plaintext p', then decompresses that, call the result p, and
> : checks if p has the headeras he is looking for.
>
> If the compression is correctly and accurately targetted at the datatype
> it is compressing, there will be zero files which lack the "header" in
> question.
Who said that all files are of a single datatype? Many, perhaps most
encryption systems do not just work on a single datatype.
> If all files have the header, the compressor can strip it out, and the
> decompressor can insert it again at the other end.
>
> If not all files have the header, it's not going to work very well
> as a halting criterion.
On the contrary, the compressor and decompressor have to work for all
files that *could* be transmitted, whereas the attacker only has to
implement a halting criterion that works for the particular files
that *are* transmitted. For example, the attack might be targetted at
a particular user who only encrypts files of a certain type.
Take email, for example. Here are some characteristics common to my
outgoing email messages:
- the headers include information about my mail reader, return address,
the location of my ISP, my company name, and so on, most of which is
constant.
- they are written in English, but with a particular word distribution
atypical of most English text (e.g. words relating to cryptography
or computer security occur disproportionately often).
- most sentences would pass a simple grammar check that doesn't attempt
to assign any meaning to words.
- quoting is always done using "> ".
- there is exactly one space separating a full stop from the next
sentence.
- punctuation goes outside rather than inside quotation marks,
"like this".
- the lengths at which lines are wrapped are not consistent (as they
would be with automatic line wrapping).
- there are often lists like this one in which each item is introduced
by "-" indented by exactly one space.
- they have the same plaintext .sig.
- they are PGP signed with my key.
An attacker can choose *any* characteristic that distinguishes a real
message from a random output of decompression, and the compression
algorithm can't possibly remove all of them. You can go to as much
trouble as you like tailoring the compression to particular message types,
but if the attacker knows anything at all about the distribution of
expected messages, he/she can probably find a relatively simple
distinguishing feature that you missed. Partly this is because the
redundancy is only clear when looking "across" messages, while the
compressor can only work on individual messages.
> Much the same is true for any other plaintext characteristic - with good
> enough compression, *all* possible decrypted files will decompress to
> plausible-looking plaintext files.
You're wrong, for three main reasons:
- the compressor/decompressor has to actually implementable, within the
current state of the art, and take a reasonable amount of time and memory.
The problem of creating plausible-looking random messages (which is
strictly easier than the problem of creating an optimal compressor
for messages with the same distribution) is not within the current
state of the art, and has no reasonable prospect of being so short of
the development of human-level artificial intelligence.
- even if it could be implemented, it would not be accurate to characterise
this type of compression as "good", since the compressor and decompressor
would be large, extremely complex, and slow. At the very least, it would
have to be programmed with the vocabulary and grammar of every language,
or the characteristics of every binary format that messages could be
transmitted in.
- the attacker can spend more effort designing and implementing the
recogniser than is spent designing and implementing the compression and
encryption, and often only needs to break a small subset of messages.
> :> With a good enough compressor a halting criteria - short of testing the
> :> integrity of the message in the real world - becomes well nigh impossible.
>
> : It makes no difference if the compresser is good or not!
>
> If the compressor is not good at compressing the data near-maximally,
> it is very unlikely that all decrypted files will decompress to plausible
> looking plaintexts.
>
> Consequently the analyst might have the possibility of using a halting
> criterion available to him.
>
> With good enough compression, halting criteria can be rendered practically
> impossible to find.
No, they can't.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOJ+sejkCAxeYt5gVAQFsDQgAsDmfZCruQrzDahUnIZivPp0tGTLhVRJN
QoB/iAbYVPyhmTQc8ijiQBzJfB7UOx4dvgc36eedStnunBRs+uvrxr5KQFmB8McD
PkIWmreH0LNMyAT6ftF2kZ5UIqxZNSkfPxFfOL/AEU6viZE76/ePm7LUTTURom+b
Elxg0Cc6GcqC4ye4gZsQOPmNl5TBkNdIXpr8ELXK1Z6/sXpaPT4RGI9n4BlzNeq2
r+AL6ZWxPMK2pECVbbak8DEMgbfnvXh4JqgMBxjqnKHG95eVEVdiX1w9mg+Fa6ga
/5FlnAuPmREgRMl52qlSP89o3X077X2wiVDjhfqPLG8YEL5rsM2Dsg==
=Vb9f
=====END PGP SIGNATURE=====
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Anti-crack
Date: Tue, 08 Feb 2000 13:04:42 -0600
CJ wrote:
>
> Has anyone researched means of protecting
> programs from being cracked with encryption?
Check out the Embedded Systems Programming magazine for Feburuary 2000.
The cover article talks about ways of protecting firmware, and most of
the ideas are applicable to software too.
The bottom line is, you can't stop 'em, but you can slow 'em down to
always be one generation behind :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Xcott Craver)
Crossposted-To: talk.politics.crypto,misc.int-property,misc.legal.computing
Subject: Re: permission to do crypto research
Date: 8 Feb 2000 19:15:46 GMT
wtshaw <[EMAIL PROTECTED]> wrote:
>(Xcott Craver) wrote:
>> wtshaw <[EMAIL PROTECTED]> wrote:
>> >No comment, then you have the freedom to study how everything works,
>> >including using any tools to assist you in that pursuit.
>> ^^^^^^^^^^^^^^^
>>
>> Not quite. *Distributing* programs to circumvent a copyright
>> protection measure is flat-out against this law, with no
>> research exemptions. Thus, you might have permission to *use*
>> tools that try to crack copy protection mechanisms, but will you
>> be able to download or buy those tools?
>Your presumption is that it is wrong to study any code.
I certainly make no such presumption!
>I herein bestow
>all right to study anything mechanism I use to make any algorithm work to
>any one who whats to to. Now, don't say that people are forbidden to
>acquire useful tools to do what I said that, at least in my case, is legit
>for them to do.
You can bestow all the rights you want, but you can't switch off
federal law by doing so.
Note: nowhere did I say that you were forbidden to aquire these
tools. What I said was that the people who make the tools will
be forbidden to distribute them. Thus, you might be _unable_
to acquire these tools. Even if research using them is sometimes
alllowed.
This will not change if you officially grant everyone all rights
to reverse-engineer your stuff. It won't even change if MicroSoft
grants everyone all rights to reverse-engineer their stuff.
>> I should check to see if there are any standard tools for
>> jiggling watermarks out of video files; I'm sure that any such
>> tools would be seriously frowned upon by the MPAA.
>>
>The problem with banning software is essentially the same as banning
>pictures for whatever reason, that you pretend that whatever people will
>do is harmful to you in all respects, whether it is to them or not. This
>is miserably backwards thinking.
I don't know if anyone here disagrees with you on this. Rather,
this is a thread about how the law affects crypto research, not
a thread about the right or wrong of such law.
Technically, questions about right or wrong are best not x-posted
to sci.crypt. In this case, however, I think it's relevant
to a discussion of the science of cryptography because the law
may now restrict what scientists are allowed to do.
>For instance, your last case, a person might wish to destroy their own
>watermarks so as to render an image *virgin.* The MPAA might not like
>it, but it is none of their business.
Again, no disagreement, but that pesky law is still there.
Also, destroying a watermark to render an image "virgin" is
a really bad idea. You do damage the image some when you run
a watermark destroying program. If you can't just dig up the
original copy of the image (you fool, you,) it's best to
use your watermarking software to remove the watermark, given
the key you used to add it. One could still argue that a program to
mangle marks is not necessarily a useful tool for content creators.
Of course, the company who made the watermarking software may
not offer a removal utlility....
-Xcott
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Tue, 08 Feb 2000 12:20:15 -0700
Reply-To: [EMAIL PROTECTED]
All combiners will have to be Latin squares. Not all Latin squares are
simply generated. A Latin square is the operation table of a
quasi-group. I'm not sure there's much other structure.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Seeking Information on FRACTAL CRYPTOGRAPHY
Date: Tue, 08 Feb 2000 12:34:57 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote, in part:
>Since - to most people's ears - "fractal cryptography" immediately sounds
>like snake oil, it may be that most people who use fractal-like
>iterated nonlinear functions to generate structures such as chaotic
>avalanches as part of their cryptosystems give the term a wide berth.
The main reason for the bad rep is essentially that a function can be
nonlinear without really scrambling its input thoroughly; that will be
enough to obtain chaotic behavior without being enough to produce a
cryptosecure pseudorandom generator.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "John E. Kuslich http://www.crak.com" <[EMAIL PROTECTED]>
Subject: Re: Anti-crack
Date: Tue, 8 Feb 2000 12:36:39 -0700
Thanks Dr. Mike,
Here is the url to the e-mag with the article http://www.embedded.com/
JK http://www.crak.com
Mike Rosing <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> CJ wrote:
> >
> > Has anyone researched means of protecting
> > programs from being cracked with encryption?
>
> Check out the Embedded Systems Programming magazine for Feburuary 2000.
> The cover article talks about ways of protecting firmware, and most of
> the ideas are applicable to software too.
>
> The bottom line is, you can't stop 'em, but you can slow 'em down to
> always be one generation behind :-)
>
> Patience, persistence, truth,
> Dr. mike
------------------------------
Date: Tue, 08 Feb 2000 14:45:28 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Anti-crack
CJ wrote:
> On Mon, 07 Feb 2000 16:04:41 -0500, Arthur Dardia <[EMAIL PROTECTED]>
> wrote:
>
> >CJ wrote:
> >
> >> Has anyone researched means of protecting
> >> programs from being cracked with encryption?
> >>
> >> I'm not an expert in either area, but what I understand
> >> of cracking is that ultimately you are looking for the
> >> machine instruction in the executable which compares
> >> password/serial number etc. to some given
> >> value.
> >>
> >> So I was thinking one could maybe encrypt this piece
> >> of the executable and decrypt on the fly when the application
> >> starts. You might be able to trace the decryption and try to
> >> spot the key used, but that would be more difficult (esp.
> >> as you wouldn't know what algorithm is used).
> >>
> >> I'm not sure one can prevent direct tracing of the executable
> >> code once it has been decrypted however. (I was thinking
> >> maybe having it in a DLL, but this is maybe traceable too.)
> >> Are there any better ways?
> >
> >Rather than tracing through the encryption/decryption routine, the
> >cracker could just write a jump command. At some point you're going to
> >have to try the key against the the encrypted serial number. By tracing
> >through the dissassembled code, the cracker will be able to see the
> >routine you used, he can then write a keygen using one of the engines by
> >taking your encryption code directly from the dissassembly file.
> >
> Yes, I was assuming you can have some area of RAM which isn't
> traceable. As far as I understand DLL files are not part of the main
> program, they exist in a separate memory space and the main program
> only calls their external functions (this is also how Windows
> programming is done).
Micros~1 would like you to believe this, but it is false. Tracing through
DLL code is not as difficult as tracing through overlay code, which is old
hat. I suspect from your statements that you have not spent much time using
low-level languages. To a person familiar with the architecture of the
machine rather than the "operating environment" like Windoze, all programs,
even the Operating System, look alike. They are SOFTware. Easy to change.
> So I don't think it would be as simple as a jump
> in the main program in this case, but I believe there are tools which
> can trace into them.
You are correct. Tools exist to do more than trace into them.
>
>
> >To sum it up, every program is crackable, it'll just take time, which
> >isn't a factor, because you still won't get the registration money, and
> >he'll then just want to share the wealth of his efforts with more people
> >(bragging for completing a tough crack).
> >
> >--
> When thinking about shareware, one could try to abandon the basic if
> x=y then ok else structure and try something else. For instance the
> serial number might be the key used to decrypt the program instead of
> being compared to something. One serial/key might decrypt it to a
> trial version and another to a full version. I haven't thought this
> through however.
Do so. It will improve your understanding of the issues.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Compression cannot prevent plaintext recognition (was Re: is signing a
signature with RSA risky?)
Date: Tue, 08 Feb 2000 12:41:37 GMT
David Hopwood <[EMAIL PROTECTED]> wrote, in part:
>On the contrary, the compressor and decompressor have to work for all
>files that *could* be transmitted, whereas the attacker only has to
>implement a halting criterion that works for the particular files
>that *are* transmitted. For example, the attack might be targetted at
>a particular user who only encrypts files of a certain type.
>An attacker can choose *any* characteristic that distinguishes a real
>message from a random output of decompression, and the compression
>algorithm can't possibly remove all of them.
Compression can make plaintext recognition more difficult.
That is all that can be legitimately claimed for it, and it is enough
to make compression worth doing for an additional reason, and enough
to motivate carefully tailoring compression to its intended
application - getting rid of headers and the like.
To prevent plaintext recognition, I would suggest, after compression,
a pre-encryption step having these characteristics:
- it involves transposing bytes within (large chunks of) the message,
- it has a larger key than that of the "real" encryption
- it is not computationally intensive
- it produces unbiased output
thus, if one brute-force searches a block cipher with a 128-bit key,
each result is something that is possible to cryptanalyze, perhaps,
but not to recognize immediately, or brute-force search.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "John E. Kuslich http://www.crak.com" <[EMAIL PROTECTED]>
Subject: Re: Anti-crack
Date: Tue, 8 Feb 2000 13:04:37 -0700
I have now read the article and I do NOT recommend it.
I found it superficial and sometimes offered silly suggestions..."write
lousy code" for example. "Seal the EPROMs in plastic" is another (there are
solvents available for almost any potting compound). The author does not
have a deep understanding of the problem.
There are very excellent sources of better advice and information on reverse
engineering and prevention of reverse engineering available on the Net. I
do not offer them here because they are not to be viewed by the faint of
heart. They require some Net searching skill to find. :--)
Anyone with adequate motivation and skill to protect his/her code will
easily find them.
However, I still maintain that against a really skilled
attacker..."Resistance is futile...give up!"
JK http://www.crak.com
John E. Kuslich http://www.crak.com <[EMAIL PROTECTED]> wrote in
message news:pg_n4.138$[EMAIL PROTECTED]...
> Thanks Dr. Mike,
>
> Here is the url to the e-mag with the article http://www.embedded.com/
>
> JK http://www.crak.com
>
> Mike Rosing <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > CJ wrote:
> > >
> > > Has anyone researched means of protecting
> > > programs from being cracked with encryption?
> >
> > Check out the Embedded Systems Programming magazine for Feburuary 2000.
> > The cover article talks about ways of protecting firmware, and most of
> > the ideas are applicable to software too.
> >
> > The bottom line is, you can't stop 'em, but you can slow 'em down to
> > always be one generation behind :-)
> >
> > Patience, persistence, truth,
> > Dr. mike
>
>
------------------------------
From: Victor Zandy <[EMAIL PROTECTED]>
Subject: I'm returning the Dr Dobbs CDROM
Date: 08 Feb 2000 14:06:14 -0600
A couple weeks ago I asked for opinions of the Dr Dobbs CDROM
collection of cryptography books. Overwhelmingly the response was
positive, so I bought it. (Thanks again to those of you who replied.)
I am returning the CDROM because it is not suitable for printing.
For example, to print chapter 1 of the Stinson book (44 pages) Adobe
acroread (x86/Solaris 2.6) creates a 500MB postscript file. I cannot
print this file directly, probably because it is too big. Although I
might be able to find a way to print the file, at 500MB it would take
too much time.
I don't know how the PDF files on the CDROM were prepared, but
they look like they were scanned from physical book pages. For recent
titles, like Stinson, they should have been generated from the
computer originals to make a smaller file, with better image quality.
Several people who responded to me said they appreciate being able
to search and cut-and-paste the text on the CDROM. For those
features, and for anyone who doesn't mind reading books from computer
displays, the CDROM is a great deal. But it is useless for printing
paper copies of its contents, even a tiny amount.
Vic Zandy
------------------------------
** 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
******************************
