karn@faline.UUCP (04/13/87)
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
ark@alice.UUCP (04/13/87)
In article <537@faline.bellcore.com>, karn@faline.UUCP writes: > 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. Several years ago, I wrote a program that does this. It is part of the software package described in the proceedings of the summer 1984 USENIX conference (Salt Lake City) under the title ``Automatic Software Distribution.'' The program itself is available from the ``UNIX System Toolchest.'' Interested parties can contact me directly for more information. Andrew Koenig Room 4N-R12 AT&T Bell Laboratories 184 Liberty Corner Road Warren NJ 07060 {kaiser,ulysses,alice,research}!ark
gwyn@brl-smoke.ARPA (Doug Gwyn ) (04/14/87)
In article <537@faline.bellcore.com> karn@faline.bellcore.com (Phil R. Karn) writes: >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. Or people who think "practical jokes" are funny. >I think I have a possible technical solution to the problem. It looks okay, if everybody would agree to use the same algorithm. Just make sure that the width of the checksum data flow is great enough through the entire algorithm that the postulated malicious person could not simply adjust a small number (e.g. 16-bit datum) in one block of the file until the computed checksum came out right. 64 bits (assuming DES one-way functions) is probably enough to foil virtually all would-be troublemakers for the near future.
andrews@ubc-cs.UUCP (Jamie Andrews) (04/14/87)
karn@faline's idea was to publish checksums of popular shareware
programs. Unfortunately, this means that anyone who wants to post
"popular shareware program X, with my nifty modifications" is under
suspicion. It would mean that an inferior program could become the
standard due simply to having been listed in journal Y -- which may
well be what some very cautious users want, but may not ultimately
be good for the user community.
Surely the best way for users to detect trojan horses is via
a program which would convert code to a format with the crucial
system calls replaced by non-destructive ones, for testing
purposes. This may not be easy to do with current machine and
OS architectures; I would suggest that the computer and OS
developers should make it easy. Unfortunately, this sounds like
a job for the Free Software Foundation, as developers have no
interest in producing products that will make it safer for users
to use PD software.
--Jamie.
...!seismo!ubc-vision!ubc-cs!andrews
"We have to touch people" --J.Bronowskitomc@oakhill.UUCP (04/15/87)
In article <5760@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn ) writes: > In article <537@faline.bellcore.com> karn@faline.bellcore.com (Phil R. Karn) writes: > >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. > > It looks okay, if everybody would agree to use the same algorithm. This is indeed the most general approach. However, for IBM PCs Andy Hopkins has written a couple of clever programs that check other programs for potentially malicious behavior. I have included below some of the introductory material from the doc file of one of the programs. They are generally available on local bulletin board systems. To quote: "Bomb Squad" (BOMBSQAD.COM) is NOT a game! It is a further attempt to prevent pranksters from destroying your data. The proliferation of the "Trojan Horse" type programs which proport to be games but actually plant bombs in your system which format your hard disk or erase the disk directory, has prompted the writing of this program, as well as CHK4BOMB.EXE ("Check for Bomb"). CHK4BOMB.EXE reads the program file from disk and attempts to spot dangerous code and suspicious messages, but since code is often a function of run time memory situations, it could miss spotting the "bombs". BOMBSQAD.COM is a program that intercepts calls to the BIOS code in ROM as a suspicious program is run, displays what is going to happen during the call, and asks if you want to continue. You can abort or continue as you see fit. -- Tom Cunningham "Good, fast, cheap -- select two." USPS: Motorola Inc. 6501 William Cannon Dr. W. Austin, TX 78735-8598 UUCP: {ihnp4,seismo,ctvax,gatech}!ut-sally!oakhill!tomc Phone: 512-440-2953
ddb@viper.UUCP (04/15/87)
Your suggestion of using DES in a checksum algorithm sounds like overkill to
me. The normal crc-16 algorithm is sufficiently hard to patch around for this
purpose. And ARC and company already report it in their verbose directories.
This reduces the problem to distribution of the correct CRC's.
I have a modest proposal for that -- using the public-key cryptosystem
shareware, the author of each shareware package would include a "signed"
message giving the correct checksums for the product he was distributing.
Now we've reduced the problem to distributing the public keys from the
shareware authors. This is easier than distributing the current checksums,
because it would be invariant across versions. It would be possible to set
up some sort of a public key server on Fidonet with reasonable security --
the problem can be reduced to the step of distributing the public key of
the public key server. That's just ONE key (of perhaps 150 digits) that
has to be widely and accurately distributed.
(Even if the crc-16 algorithm isn't sufficient, I think this public
encryption approach is a better way to distribute the correct checksums
than publication in byte or whatever. Besides, they'd put it on Bix and
compuserve and stuff I don't want to spend money on.)
--
David Dyer-Bennet
UUCP: ...{amdahl,ihnp4,rutgers}!{meccts,dayton}!viper!ddb
UUCP: ...ihnp4!umn-cs!starfire!ddb
Fido: sysop of fido 14/341, (612) 721-8967caf@omen.UUCP (04/16/87)
In article <537@faline.bellcore.com> karn@faline.bellcore.com (Phil R. Karn) writes:
: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.
Unless everybody used Kermit, YMODEM, or ZMODEM to transfer the file,
different copies of the same file would have random bytes of garbage
appended to them by the XMODEM transfers most programs use. This would
upset any reasonable checksumming program, including the proposed DES
mutant.
Even if everbody used ZMODEM and got the file transferred without
alteration, the time required to collect, verify, and publish official
checmsums means the information will be somewhat out of date by the time
it is published. In addition, magazines might not wish to expose
themselves to lawsuits resulting from dissemination of incorrect checksum
information.
Chuck Forsberg WA7KGX Author of Pro-YAM communications Tools for PCDOS and Unix
...!tektronix!reed!omen!caf Omen Technology Inc "The High Reliability Software"
17505-V Northwest Sauvie Island Road Portland OR 97231 Voice: 503-621-3406
TeleGodzilla BBS: 621-3746 2400/1200 CIS:70007,2304 Genie:CAF Source:TCE022
omen Any ACU 1200 1-503-621-3746 se:--se: link ord: Giznoid in:--in: uucp
omen!/usr/spool/uucppublic/FILES lists all uucp-able files, updated hourlyblarson@castor.usc.edu (Bob Larson) (04/20/87)
I don't understand the problem. I don't run any software that I don't have either the sources to or someone I can sue. (The latter is software I have payed for.) -- Bob Larson Arpa: Blarson@Usc-Eclb.Arpa Uucp: (several backbone sites)!sdcrdcf!usc-oberon!castor.usc.edu!blarson seismo!cit-vax!usc-oberon!castor.usc.edu!blarson
dick@zaphod.UUCP (Dick Flanagan) (04/21/87)
Summary: Expires: Sender: Followup-To: In article <1007@ubc-cs.UUCP> andrews@ubc-cs.UUCP (Jamie Andrews) writes: >[...] as developers have no interest in producing products that will make >it safer for users to use PD software. What a total, absolute, unmitigated, crock of sh%#&! -- Dick Flanagan, W6OLD UUCP: ...!ucbvax!sun!plx!dick GEnie: FLANAG
john@hpcvlo.HP.COM (John Eaton) (04/21/87)
<<<< < < What's needed is a way for any user to verify that the program he just < downloaded from a BBS is uncorrupted. < What's needed is a real multitasking operating system that protects tasks and the operating system from each other. John Eaton !hplabs!hp-pcd!john
ken@rochester.UUCP (04/23/87)
|What's needed is a real multitasking operating system that protects tasks |and the operating system from each other. That doesn't help if the trojan horse does the equivalent of rm -fr $HOME. Ken
johnc@haddock.UUCP (04/23/87)
In article <606@zaphod.UUCP> dick@plx.UUCP (Dick Flanagan) writes: >In article <1007@ubc-cs.UUCP> andrews@ubc-cs.UUCP (Jamie Andrews) writes: >>[...] as developers have no interest in producing products that will make >>it safer for users to use PD software. > >What a total, > absolute, > unmitigated, > crock of sh%#&! Hey, instead of just hurling insults, how about giving some examples. I have one: There are many companies about (including this one) that are moving to include the Usenet software in their libraries. Why? Well, it gives a noticeable added value to the product. No more reason is needed. In some cases, Usenet is replacing a proprietary package. As for flames about profiteering from a PD product, well, it's the package that is sold, not the individual programs. What the customer buys is the convenience of not having to unpackage the mod.sources files, do all the configuring, debug a few SEGMENTATION FAULTs, and so on. It could be well worth a little extra money (if you have the sense not to accept most of the newsgroups. :-) Have you seen the growing list of vendors that are announcing support for Posix? 'Nuf said. -- John Chambers (617)247-1155 <...!ima!johnc> [The above opinions are my own; for a small fee, they can be yours, too.]
andersa@kuling.UUCP (Anders Andersson) (04/24/87)
In article <1669@castor.usc.edu> blarson@castor.usc.edu.UUCP (Bob Larson) writes: >I don't understand the problem. I don't run any software that I don't >have either the sources to or someone I can sue. (The latter is >software I have payed for.) Having the sources will certainly ease the task of manually verifying that a program does what you expect it to do, but does that eliminate the problem? It is possible to include unpleasant routines in source code as well, hiding them where least expected. Also, manually checking 1 MB or so of sources is quite a job. Having a standard and safe way of identifying the true originator of a particular software document is a way to find out who to sue - if such action is at all possible; serious software vendors usually don't bug their own code. If you obtain your software through a reliable channel (like snail mail perhaps) directly from the vendor, you will probably do fine without any of this fancy checking. I find the method of using public-key encryption (as someone suggested) a quite reasonable approach. This will not only prevent you from executing malicious code inserted by human gremlins under the cover of a well-reputed software author, but also provide you with an easy way of finding out whether the copy you have still is *the* one provided by the original author, regardless of any undocumented (not necessarily malicious) minor changes introduced by others. Maybe this isn't too much of a problem to warrant the development of a standard verification algorithm? -- Anders Andersson, Dept. of Computer Systems, Uppsala University, Sweden Phone: +46 18 183170 UUCP: andersa@kuling.UUCP (...!{seismo,mcvax}!enea!kuling!andersa)