Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!ames!ptsfa!ihnp4!homxb!houxm!mhuxt!mhuxm!mhuxo!ulysses!faline!karn
From: karn@faline.UUCP
Newsgroups: comp.sys.ibm.pc,sci.crypt
Subject: Stopping Trojans
Message-ID: <537@faline.bellcore.com>
Date: Sun, 12-Apr-87 20:29:29 EST
Article-I.D.: faline.537
Posted: Sun Apr 12 20:29:29 1987
Date-Received: Wed, 15-Apr-87 04:40:56 EST
Organization: Bell Communications Research, Inc
Lines: 91
Xref: utgpu comp.sys.ibm.pc:2923 sci.crypt:307

I've read one too many Trojan Horse reports. I'm tired of hearing about
people having their hard disks wiped out by jerks with a strange sense of
humor. They must come from the same crowd that puts cyanide into Tylenol.

I think I have a possible technical solution to the problem. What's needed
is a way for any user to verify that the program he just downloaded from a
BBS is uncorrupted.  One way is to publish in, say, Byte Magazine a list of
"checksums" for all popular shareware programs.  A nervous user could then
recompute the checksum and compare it to the published value.  The problem
is then reduced to making sure that there are no malicious hackers on the
magazine staff who could change the checksum values before they are
published.

You can't just use your everyday "count the bytes" checksum algorithm,
though. While this is usually adequate to detect random acts of nature, a
clever person could corrupt a program in such a way that the same checksum
is computed even after the Trojan is added. A more sophisticated algorithm
is needed that is secure against deliberate, intelligent attacks by humans
as well as random attacks by nature.

Here is one possible "human-proof" checksum algorithm. The 'x' characters
represent exclusive-OR operations:

			Block #0 of file
				|
				v
			"Noninvertible function"
				|
				x <- Block #1 of file
				|
				v
			"Noninvertible function"
				|
				x <- Block #2 of file
				|
				v
			       etc.
				|
				v
			"Checksum" output


The "noninvertible function" block (also called a "one-way function") is the
heart of the algorithm. This function, while easy to compute in the forward
direction, is computationally infeasible (i.e., impossible in practice) to
invert.  In other words, given x, I can easily compute y = f(x). But given
y, it is extremely difficult to find the value of x that produced it,
even though the function f() is completely known.

Such a function does exist, and it is already the basis of UNIX password
security: the Data Encryption Standard (DES). DES has the property that
while encrypting and decrypting is easy as long as you know the key, if you
are given a matched ciphertext/plaintext pair and told to find the key that
produced the transformation, you will have to try all 2^56 keys by
brute-force trial-and-error. (On the average you will probably only have to
try half this number, or 2^55. Not much difference, though).

So we can just make our one-way function be DES, with the "function input"
fed to the key input of DES, and a known, constant value (e.g., all 0's)
sent to the plaintext input of the DES algorithm.  Or the algorithm could
be changed to the following:

			fixed constant
				|
				v
			DES Encrypt  <-- Block #0 of file
				|
				v
			DES Encrypt  <-- Block #1 of file
				|
			      (etc)
				v
			DES Encrypt  <-- Block #n of file
				|
				v
			"Checksum" output

This is equivalent to super-encrypting the fixed constant N times, each
time using a different block of the file as the key.  Again, DES's resistance
to known-plaintext attack would make it extremely difficult to change any
data block while keeping the same checksum output.

One problem, of course, is that DES uses only 56 of the 64 key input bits;
the low order bit of each byte is ignored. This is not good, since it would
not detect changes in the low order bit of any byte in the program. Either
the DES algorithm could be changed to make all 64 key bits significant, or
perhaps only 7 file bytes would be fed to it at a time.

Comments?

Phil