Re: Why I have a 512 bit PGP key
eric@remailer.net (Eric Hughes) writes:
Read Ken Thompson's Turing Award lecture for why that isn't sufficient. Its quite amusing.
I'm quite familiar with the work. [For those who aren't, it's about compilers that compile in self-perpetuating bugs from their own source code.]
Get the essay that Perry mentioned and start there. Keep in mind that object code can be interpreted in many different ways, only one of them typically expected.
I strongly agree with both Perry that it is amusing and with Eric that everyone should read it. But I see it as more germane than Eric. It is not about arbitrary self perpetuating bugs from source. It is about serious security holes that are self perpetuatated by the binaries of the complier. The compiler ignores its own source and generates security hacked binaries, even when the source looks like it is corrected. One strongly held belief among lots on this list and in the PGP advocacy world is that the availability of source guarentees security. Thompson's lecture throroughly dispells that hope, crushing the "guarentee" completely. Drawing from Thompson, a simple MD5 is not sufficient. Youd have to have multiple compilers, perferably on different cpu architectures, build the tool from source, and compare the results. Then, and only then, could you claim that you were secure. Of course, this is far too much work to be practical. And this approach is impracticale without need to invent a conspiracy between the compiler developers. Pat p.s. HappyNewYear! Pat Farrell Grad Student pfarrell@cs.gmu.edu Department of Computer Science George Mason University, Fairfax, VA Public key availble via finger #include <standard.disclaimer>
Pat Farrell writes:
But I see it as more germane than Eric. It is not about arbitrary self perpetuating bugs from source. It is about serious security holes that are self perpetuatated by the binaries of the complier. The compiler ignores its own source and generates security hacked binaries, even when the source looks like it is corrected.
I hate to remind everyone, but it is possible to actually inspect the compiled binary output by hand with a debugger and even trace its execution step by step through the usually small security sensitive sections of code. While Thompson's famous hack was clever indeed, it basically depended on security by obscurity - if someone had looked at the generated machine code they easily could have spotted the hook that inserted the magic password. Granted of course this is a lot of work, but so is modifying a compiler or perhaps several of them to selectively insert security hooks. On the other hand Eric's point about execs is more telling however, if the evil sysadmin controls the kernal it is quite possible for him to arrange to have the kernal recognize when the security program code is running and fudge the state of the security code variables by interupting its execution at a private to the kernal breakpoint and invoking code that patches the state of the data or stack areas and then returns to the user code. Since the user process is effectively running on a virtual machine it would be very difficult to create code that would reliably detect such selective violations in the consistancy of the virtual machine, especially as code to check for such violations has to run on the same virtual machine and can also be diddled with by the kernel. In fact if the kernal one is running security code under is not 100% trustworthy no amount of cleverness at the user level can prevent it from obtaining any private information or modifying any private data it wants. And if the hacker is clever enough this can be made nearly invisible to any application program and can be used to do almost anything desired. And since the kernal (/vmunix or whatever) files are accessible to anyone with root and are not integrity checked on bootup, such a hack could be planted by some j. random hacker who had root momentarily and activated much later (perhaps via an obscure user level control file somewhere that specified the gory details of what to recognize and patch). Dave Emery die@die.com
From: "Pat Farrell" <pfarrell@netcom.com>
Read Ken Thompson's Turing Award lecture for why that isn't sufficient. Its quite amusing.
But I see it as more germane than Eric. It is not about arbitrary self perpetuating bugs from source. It is about serious security holes that are self perpetuatated by the binaries of the complier. "Bugs" is shorthand for any arbitrary deviation from nominal source code function. Come on, do you expect a one sentence summary to be accurate in all detail? Drawing from Thompson, a simple MD5 is not sufficient. A single, unchanging, global MD5 source would be insufficient. That's not what I mentioned, but rather a constantly changing MD5 source. One could also change the arbitrary constants in the MD5 source for a "personal MD5". Here's a summary of these self-perpetuating false compilers. There is an intermediate source code with the arbitrary deviant function expressed. A true compiler compiles this into the false compiler. The arbitrary function includes a recognizer and a payload. The false compiler recognizes the source code of the true compiler. At this recognition, the corresponding payload is compiled in. The payload includes all the arbitrary deviant function of the intermediate source, including the recognizer. Thus the false compiler will compile itself from the true source. [This is a summary. I believe Thompson's original work has a full intermediate compiler; this makes the attack easier to perform, but is not essential.] Any such attack on the compiler requires a recognizer. This is the point of weakness, since recognizing arbitrary function is mighty difficult. The strongest form of the problem is unsolvable; it's a quick corollary from the solution to the halting problem. Practically speaking, however, the problem is more tractable, because the ability to change the source to some arbitrary form is not unconstrained. You can, however, make recognizing a source _extremely_ difficult. Plus, if you're only interested in finding the first integrity failure, the recognizer has to work on a source which the author of the recognizer hasn't even seen yet! Even with public source code of a source scrambler available to the recognizer author, the scrambler can use combinatorial explosions to eliminate hooks for recognition. Reordering of parallelism, for example, or creative use of aliasing -- the number of techniques available is huge. And that's only for a single algorithm. Lots of functions exist that will detect modification. CRC's are a good example; there are _lots_ of primitive polynomials available for making your very own personal CRC checker. Remember, you only really need to detect the first modification. Eric
participants (3)
-
Dave Emery -
eric＠remailer.net -
Pat Farrell