Zen and the Art of Breaking Security - Part I
By Razvan Peteanu for SecurityPortal
I'll admit I had double thoughts about creating yet another variation on the "Zen and the Art of..." theme. I myself shiver when I see such titles, but I hope Zen practitioners and Mr. Pirsig  will forgive me this time. The Zen quotation is appropriate for what we will describe in this two-part series: alternative, perhaps even unusual, means to induce or exploit security vulnerabilities.
The more we work on a topic, the stronger the identification between the concept and its implementation. We often reduce the implementation to the concept, leaving nothing out of the real thing but the concept that originated it. In Zen, we are often reminded that the finger pointing to the moon is not the moon.
Typical example: because algorithm XYZ is not breakable according to the public research, it must mean that an XYZ encryption program or chip cannot be broken. We have just reduced the actual implementation to the mathematical idea. Not only have we limited ourselves in the scope of what we will defend, but we have also made an implicit assumption that the attack path implies breaking the algorithm.
Side-channel attacks are those which employ (apparently) "unusual" methods that seem to have little to do with the security concepts that underlie a system. For instance, when we think about encryption, we tend to follow the thought to key size, symmetric or public, brute-force attacks and so on. Granted, we should think of them. However, there are other ways to attack a cryptographic system, coming from a totally different direction, addressing not the concept but the implementation as well as the other pieces in the big picture.
One example of side-channel attacks is the TEMPEST technology . The topic will be covered in a different article for SecurityPortal, so we won't go into many details here, but the essence is that today's computing systems are sources of electromagnetic radiation, and this radiation can be intercepted with appropriate equipment.
The radiation is not devoid of significance like a light bulb's, but is modulated by the bits going from one subsystem to another. The keyboard I type my password on, particularly helped by the long cable to the PC, sends around signals that could easily allow an attacker to capture my credentials. The monitor, again linked to the PC with a cable, is another strong source. Even if I work in a shielded room, some radiation is induced into and leaks through the power cable and can be intercepted elsewhere near the building's transformer.
For such cases, it no longer matters that I have a long and random PGP passphrase, that the system is virus-free and firewalled and that the crypto algorithms and their implementation in PGP are flawless. The real world also consists of the hardware PGP runs on, the electromagnetic fields, and the building the computer and myself are in, and it is at this level that a perceptive attacker would strike.
A more subtle attempt is the timing attack, which reminds us that, at the end of the day, any software implementation boils down to running some machine language instructions on a CPU and these operations are not instantaneous. Depending on how the program goes through different logical paths, some actions will take longer, some shorter.
We normally completely ignore this level of detail, and only care about if the system is fast or slow, or if the Web page takes more than two seconds to download. But imagine you have a hardware chip that accepts a 30-character passphrase to unlock a safe. In his third Mission: Impossible, Tom Cruise managed to steal the board and gave it to you to find the passphrase (Hollywood can only do so much). The board contained a single chip. Had it been like a regular motherboard, with different subsystems, an attacker, by recording the traffic on the buses, would have access to the machine code and data as they are transferred from the memory, so the attack would have been significantly easier.
The 240-bit key is not something fun to attack by brute-forcing the entire keyspace. For the example's sake, let's consider that the implementation is poorly designed and that although the password check only begins after the entire password is typed in, the passphrase is actually checked character by character. If the first character is correct, the check goes to the next character; if not, the code generates a beep and exits. The second character is checked now, and so on.
A human user would instantly hear the beep. If the board is connected to a logic analyzer, however, we can time with very good precision how long it takes from the moment we input the password until the command signal to the buzzer is sent. We first try with a password consisting of 30 '\0' (characters with the ASCII code 0). Then we move to the next possible value of the first character, 01 in ASCII, leaving the rest unchanged. And so on, until we exhaust all 256 possible values.
For all but one attempt, the beep will come after whatever time is needed to initialize the check and go up to the password verification of the first character which fails, and to jump to the beeper routine. For the correct character, though, the time needed will be slightly longer because the first character was correct and the code proceeded to the next one (so more instructions are executed until the beep comes out).
For each character, we only need to iterate through 256 values, keeping the previous as found and the rest fixed. The number of possible values to check is dramatically reduced, from 2^240 in the most unfavorable case of the sheer brute force, to 256 x 30 = 7680 trials, a piece of cake. A quick reality check: since the logic analyzer is not infinitely precise but samples the signals at its own limited rate, for very fast systems a single password attempt can be repeated multiple times, so the time difference becomes measurable.
Many readers might point out that (a) the attacker would not know that the password check is character by character, and (b) the mechanism is silly and no real security product would use it. Regarding (a), it could be possible for such information to be available Mr. Cruise could have obtained some blueprints as well but even if we don't know, we could try. Timing patterns could reveal useful information about the internal workings of the chip even if they do not lead to the solution in so few steps. Cryptanalysis is a step-by-step process in which any little crumb of information helps the search.
Regarding (b), indeed, the mechanism is silly: the passphrase check is not designed well and there should be a lockout after a number of unsuccessful login attempts. We have chosen this scenario for simplicity. Not that silly implementations do not occur in the real world, but a considerably more secure solution would have used well-researched algorithms only. Indeed, and applying timing attacks to DH, RSA and DSS is exactly the topic of a research paper. See .
Suppose we don't have access to all the pins of the chip (it is sealed in a box that Mr. Cruise will have to surreptitiously return in MI4). There is another type of side-channel attack that is still possible, and for that, we again need to peel a layer from the conceptual processor that is doing all this work. At a lower level, a CPU consists of electrical circuits and, by definition, they can only function if they get power. Depending on what circuits are involved, the power consumption varies.
For instance, a CMOS memory cell practically consumes most of the power when transitioning from a logical state to another, and not while maintaining its state. We don't have such extremely low-level access to the internal structure of the memory chips, but at a CPU level, sequences of instructions that do a lot of memory transfers (thus involving the cache as well) would lead to a different power consumption pattern than a code that does a lot of swapping and arithmetic operations with values in the internal registers.
Or, during an idle loop the CPU would exhibit a different pattern than when executing another code. It may sound far-fetched, but power analysis has been used against real systems. Like timing attacks, it would rarely reveal the solution directly, but in the hands of the knowledgeable attacker, it would provide valuable hints. For instance, in  the authors show how the number of rounds in a DES cryptobox can be visibly determined by power analysis.
Further then, by knowing the building blocks of a DES cryptobox, the analysis can uncover further details. Even if the current values reveal little by themselves, the attacker can compare the measured patterns with known sequences and thus determine the type of operations involved (comparisons, multiplications, exponentiations and so on). Not a task for the weak, indeed, but to a sufficiently interested party with enough technical resources, this is but an interesting challenge.
The electrical current is not the only way to convey information about an otherwise closed system. An infrared camera can reveal heat patterns occurring during functioning that may lead to a better understanding of the internal structure. Heat is better suited for analysis of static conditions, as the various materials existing between the actual circuit and the camera have thermal inertia. Sound and vibration reveal information about mechanical devices. The Enigma machine used by the Germans in WW2 generated noise, and this could have been used in a side-channel attack ( referred to in ).
In the next part we will look at other ways to break a secure system.
References for Part I
 Robert M. Pirsig, Zen and the Art of Motorcycle Maintenance: An Inquiry into Values, Bantam Books, 1984
 David Kahn, The Codebreakers (revised ed.), Scribner, 1996
SecurityPortal is the world's foremost on-line resource and services
provider for companies and individuals concerned about protecting their
information systems and networks.
The Focal Point for Security on the Net (tm)