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 hourlyroman@sigma.UUCP (04/17/87)
In article <1007@ubc-cs.UUCP> andrews@ubc-cs.UUCP (Jamie Andrews) writes: > 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. If the program has "nifty modifications" doesn't this imply that the person posting has source? Post the sources. > 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 will cause software guerillas to avoid system calls and find non-obvious ways to implement their attacks. The best way for users to detect trojan horses is to carefully peruse and understand the source code prior to compiling it themselves. Post the sources. Free Software Forever!
dillon@CORY.BERKELEY.EDU (Matt Dillon) (04/18/87)
Here are some ideas on avoiding Trojan horses: (A) download source only, or (B) download programs from well known authors (C) download from better controlled BBS's Unfortunetly, if one follows the above three points strictly, one usually misses out on a lot of good software. There really is no way to 'verify' unknown author's programs, and those of us who do post programs on BBS's are doing so because we want to share them with everyone... not out of duty. We are not about to spend an extra three hours 'preparing' our contributions to 'prove' they are not trojan horses. So if anybody has any ideas about having the *authors* do something 'extra' when posting code, they might as well forget it... nobody will ever do it. -Matt
blarson@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
mark@elsie.UUCP (Mark J. Miller) (04/20/87)
Obviously, if one wants to post a Trojan program, anonymity is essential. The solution would seem to be for Sysops to ensure that they have the correct name and address (both email and smail) of any person who posts a program. The Sysop would need to obtain this verification befor allowing the program to be entered in the FILES section of the BBS. Obviously, there are many ways to break into a BBS and pretend you're someone else, so it would probably be wise to send a letter through the (I know there are some hackers who will throw up at the thought) post office to the contributing programer asking for verification (through smail) of name, address, and program. If the individual was local, the Sysop could simply telephone. Then, if it's a Trojan you'll know where to start looking (with cattle prods and spay hooks). Of course, it would be a PIA for everyone concerned. But it would be simple, relativly quick, probably less dangerous than trying out the program on a spare machine, and hard to fool. True, the programmer could be about to leave town -- but that's unlikely. True, a Trojaner could intercept the letter (I suppose) but that would be mail fraud and we could call in the FBI (:-<>) -- Dr. Mark J. Miller NIH/NCI/DCE/LEC UUCP: ..!seismo!elsie!mark Phone: (301) 496-5688
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
jvc@mirror.UUCP (04/21/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 This would indicate that you don't use any Shareware (typical $25-$50 contribution to the author) or you pay the extra ~ $300 for the sources (if they're offered at all). This means you miss out on a lot or you're rich. Be aware that even though you have the sources, there is no guarantee that the executables were generated from those sources or that the executables weren't modified (unless you compiled them yourself). Also note that you can't sue (I mean have a chance at winning a suit since anyone can sue anyone) a Shareware author if you've received that Shareware through normal distribution channels (ie, not mailed directly to you from the author but obtained through BBSs or passed on to you from someone not associated with the author, etc) even if you made a contribution, since anyone could have modified the executables and/or sources. If you decide to sue anyway, you'll be out a lot of money when you lose since the plantiff pays the defendant's court costs if the plantiff loses. Although I wouldn't expect commercial companies to create trojans, if the software does cause damage, be aware that if you buy software through commercial channels, one of the provisions in your license agreement frees the author/company from any damages resulting from the use of the software. You would have to prove they intentionally wrote code to cause malicious damage inorder to have a chance of winning a suit. ----- Just curious: Do you actually not use *any* software that is not sold commercially or that you don't have the sources for?
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)