Ed is an EE, PE, and author in Poughkeepsie, New York. You can contact him at [email protected].
The Allied cryptanalysts had proved by this point that the tiniest of flaws was enough to split the most perfect cryptographic edifices wide open. Even one-time pads were not immune, even one-time pads that were really (unlike the Russian ones) used only once.
—Stephen Budiansky, Battle of Wits
Encrypting and decrypting messages in the years leading up to the Second World War required massive amounts of thoroughly tedious handwork: table lookups, simple arithmetic, position transpositions, and the ability to transcribe gibberish without a single mistake. In many cases, a scheme's effectiveness lay in security through obscurity, as only its designers and users knew the exact algorithms. As long as opposing analysts also used hand methods, there was no practical way to break the code.
A one-time pad offered a theoretically uncrackable coding system combined with a straightforward implementation. You simply added a random number to each plaintext character, producing a single cyphertext character. At the receiver, subtracting the same random number produced the original plaintext character. Obviously, both parties must use the same random numbers in the same sequence.
Those numbers were originally printed on sheets of paper bound in pads, with the sender and recipient each using an identical pad. In their purest form, the numbers came from dice, electronic noise, or other random processes. That sufficed until wartime brought on the need for industrial quantities of random numbers, far beyond the capability of human production.
Coming up with truly random numbers is difficult, so the German cryptographers used a complex printing mechanism to generate one-time pads based on a mechanical pseudorandom number generator. The British cryptanalysts, given a captured set of one-time pad pages and voluminous message intercepts, figured out the machinery and, thus, the sequence of pseudorandom numbers. They could then run new messages against various possible pads and extract the original plaintext more or less automatically.
That analysis wasn't done by hand. IBM punch-card tabulators and sorters, augmented by custom crypto mechanisms, chewed through literally millions of cards holding the intercepted messages and tables of not-quite-random numbers. The combination of dogged mathematical pencil work and machine-powered analysis cracked the code.
After that, the German transmissions were an open book and, yes, the rest is history.
The Bletchley Park cryptanalysts made many breakthroughs, but perhaps the most significant was translating algorithms into machinery. Those mechanisms represented innovative, completely "outside the box" thinking that invalidated the design assumptions underlying the Axis codes.
What's the relevance to embedded systems? Well, we all know that Java applets running in a virtual machine's sandbox can't cause any system damage, because Java programs have strong static type checking and the VM enforces security policies at run time. Right?
Nice assumption, but wrong.
Security by Isolation
Java began as a way to control set-top boxes and subsequently morphed into a multitiered monster. The original notion of "write once, run anywhere" has largely foundered on the practical need to tailor applications to a specific platform or purpose; the largest enterprise-class programs require facilities that simply don't exist in the smallest embedded-class hardware.
All that notwithstanding, the underlying principles remain fairly constant. Human-readable Java source code compiles into machine-readable bytecodes that are subsequently interpreted in a Virtual Machine that isolates the program from the actual hardware. A Class Verifier sanity-checks the bytecodes to ensure that they are well-formed, make sense, and don't violate any basic ground rules. As the VM executes the bytecodes, a Security Manager restricts access to memory, disks, networks, and so forth according to specifications that are nominally under user control.
The Security Manager is actually optional, as each Java program must define its own security methods. Java applets, however, are subject to the Security Manager rules set up by the browser or viewer that loads them.
In short, Java code can be constrained in ways that C++ code (or other machine-instruction languages) cannot. There are several problems, however, not the least of which is that it all comes down to trust.
A program that doesn't interact with hardware can't do any damage, but it can't do many useful things, either. As soon as you allow a program to touch your hardware because you need, say, persistent storage, anything else is possible. So if you must trust programmers to do useful things correctly, you must also trust them to not do harmful things. No matter how fine-grained the mechanism becomes, it still comes down to trust.
Let's suppose, however, that you prohibit all hardware access by restricting a Java app to the well-protected functions of memory allocation, keyboard input, and display output. What harm can come from that?
Physical Security
Because Java's security model isolates programs, not only from the underlying hardware, but also from each other, Java has been a shoo-in for security-conscious applications such as smartcards and mobile phones. The former hold highly valuable personal information, the latter grant access to the phone network and, in both cases, physical possession must not allow access to information and functions held within the system's memory without additional user identification.
Various schemes ensure that data cannot be extracted from the chips themselves. Ordinary phones may use simple password protection, but smartcards for high-security applications incorporate self-destruct mechanisms behind intricate mechanical encapsulation. As you might expect, cost and physical security are inversely related by a nonlinear exponent.
Some smartcard applications and nearly all phones allow (or even encourage) extended functions provided by user-loaded Java apps. How smartcards will actually work in practice isn't quite as obvious, but from what I've seen, you'll be able to enhance their functions with Java apps that control various financial and ID transactions. In any event, because the card allows additional functions from any source, you're depending on the Java VM to protect your data.
More to the point, your wireless phone undoubtedly came with a few Java games and, if you spend enough on access, you can download more from a variety of online sources. The Java security model ensures that these apps can't fiddle with the machinery or each other, so you can be quite certain a rogue app won't interfere with your phone without your permission, even though the data and apps may live within the same Subscriber Information Module card.
All of that security depends on the single assumption that the JVM controls the applications. That turns out to be just as false as the German cryptographers' faith in their pseudorandom number machinery.
Cracking the Code
A good technical paper's title should summarize its contents and, in this case, the title says it all: "Using Memory Errors to Attack a Virtual Machine," by Govindavajhala and Appel. They assert that if you can both load a Java program and manipulate the physical environment, you can gain access to the entire memory space and subsequently control the entire system regardless of the security settings. A brief overview will be chilling enough, although you should read the whole paper to understand the nuances.
A malicious Java program fills the heap with objects that contain pointers to another object on the heap, a weird but perfectly legal practice. It then repeatedly scans the pointers until one changes. The attack creates the objects so that a broken pointer will probably point to a different object, which means the program now has a pointer to something other than the object that the JVM expects. From there, things go downhill quite rapidly.
Given two pointers of different types with the address of a single object, an impossible situation under the JVM's type-checking and memory-management rules, the program can create pointers to arbitrary physical-memory addresses and write arbitrary data. The program can even overwrite the Security Manager's settings, granting itself unlimited system access in a nicely portable manner.
But we all know that no matter how often a program reads a variable, it will always get the same result. That's the whole basis of programming: A stored value remains unchanged. Right?
Yes, as long as the hardware works properly. If the malicious app runs on a sufficient number of systems, eventually one will malfunction. If that system is connected to the network (which is what everyone wants), the app phones home, perhaps literally, and delivers the goods.
Attackers can always improve the odds by manipulating the environment. Govindavajhala and Appel's paper describes how the authors induced memory errors by aiming a 50-W reflector bulb at the DRAM inside a standard PC from a range of 2 cm. After one minute of heating, which raised the DRAM's temperature to about 100° C, their program escaped the JVM's control.
Reduction to Practice
Popping covers and baking DRAM isn't a particularly subtle attack; it's the sort of thing you'd notice right away if you happened to walk by. The authors chose heat simply because it was convenient, although they catalog the many ways of causing memory errors.
A cosmic ray or other penetrating particle will flip a single memory bit, while bulk heating can cause multiple, simultaneous failures. Their algorithms work with any type of data error caused by any external influence, so being finicky about a particular error source simply isn't productive.
Not all failures will affect the pointers stored on the heap, as some errors will crash the system or go completely undetected. The results depend on the fraction of RAM devoted to the heap, whether the JVM code runs from RAM or ROM, and similar considerations. The numbers work out to about three successes for each system crash across the PC-class systems they studied, which is not bad at all.
A successful attack of this nature requires both loading a program and having physical access to the target system. Loading a program on a PC isn't particularly difficult these days, putting a Java app on a mobile phone isn't much harder, but getting that system in hand is more difficult.
If you routinely leave your mobile phone unlocked, an attacker can simply siphon off the information without using a Java app. A locked phone poses more difficulty, assuming that the SIM encryption works as advertised, because attackers without the password cannot load a program. A smartcard shouldn't be any more vulnerable.
However, a program distributed to thousands (or millions) of units really can rely on sporadic failures. Govindavajhala and Appel cite an IBM finding that a typical 1996-era PC would suffer one intermittent DRAM failure per month and extrapolate to a few months per failure in contemporary chips, perhaps four failures per year. If three of those failures allow the attacking program to gain control, you can see where this leads.
The program need not be actively running at the time the error occurs if its memory remains allocated and located in DRAM so that it can examine the results later. Phones and other hand-held gizmos don't have hard drives, so any allocated memory remains active and vulnerable at all times. An app that wakes up occasionally won't steal too much CPU time and might even be forgotten; a single setup program might install a desired app and a malicious one.
The authors note that the program must allocate a significant chunk of RAM to be successful, but that users have grown accustomed to multimegabyte requirements for even the most trivial programs. A subtle attacker might even vary the memory requirements periodically just to reduce suspicions. It's a matter of time and targets, with the attacker having plenty of both.
Countermeasures
The first line of defense is to not run untrusted programs. Unfortunately, experience has shown that essentially no programs can be trusted; even shrink-wrapped software has shipped with viral payloads and I've gotten the odd press release carrying a Word macro virus. Mobile devices depend on downloaded programs from many sources that simply cannot be trusted, so you must assume that any program can have undesired side effects.
A program that does nothing other than allocate and scan great deal of memory won't appear in any of the virus alerts, simply because nobody will ever notice it's running. How often have you looked at the dozens of processes running in your system (can you trust that list?) and determined what each one was up to?
The authors note that error checking and correction for memories will help by eliminating single- or multiple-bit errors, but any practical ECC system will miss some error conditions. Ordinary ECC DRAM circuitry corrects all single-bit errors, detects all double-bit errors, and may catch more severe errors. The typical ECC design point does not include a heat-lamp attack!
Analyzing error logs might indicate an attack in progress, but by the time one's detected, it may have succeeded: A single error in the right place will suffice. Worse, the best response seems to be a complete and unconditional system shutdown.
Although the original paper describes an attack on PC-based Java Virtual Machines, the same technique can be used on any hardware and any software. The likelihood that it will appear on a system near you may be fairly small, but its stealthy nature makes it hard to assess the risks.
Be very afraid!
Contact Release
Battle of Wits by Stephen Budiansky (The Free Press, 2000; ISBN 0-684-85932-7) uses the massive declassification of WW II cryptographic documents in the late 1990s to detail the often mistold and misunderstood stories of code making and code breaking.
If you've read Neal Stephenson's Cryptonomicon (Avon, 1999; ISBN 0-380-97346-0), Budiansky provides some facts behind the fiction: Compare the treatments of the 20th Division's abandoned code books in Sio, New Guinea, and their subsequent processing in Brisbane, Australia.
Many crackpot crypto schemes are one-time pads in disguise. The problem with pads is that they require distributing massive amounts of random data rather than a short encryption key. This is not, in general, a big win, as Bruce Schneier discusses in his Crypto-Gram newsletter (http://www.counterpane.com/crypto-gram.html).
Cryptographers make codes, cryptanalysts break them, and Schneier's Applied Cryptography remains a fundamental work on the subject; see http://www.counterpane.com/applied.html.
The JVM memory-error attack was mentioned in the June 15, 2003 Crypto-Gram, which pointed to the original paper at http://www.cs.princeton.edu/~sudhakar/papers/.
An old but good survey of Java security starts at http://www.javaworld.com/ javaworld/jw-08-1997/jw-08-hood.html. The intersection of wireless phones and smartcards is described at http://www.schlumbergersema.com/telecom/ind_insight /simcard7.htm.
DDJ
