The Art of Breaking Security

Designing a secure solution, be it protocol, algorithm or enterprise architecture, is far from trivial. Apart from the technical or scientific difficulties to overcome, there is a mental trap easy to fall into; looking at the picture through the eyes of the designer. The designer often works with concepts, not with the real thing. We look at an algorithm’s specifications and we mistake it for its implementation in a particular program. We read several RFCs (request for comments) and we say, this is TCP/IP.

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 pubic research, it must mean that an XYZ encrypted 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 that 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. But 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.

The Tempest Rises

One example of side-channel attacks is the tempest technology. Today’s computing systems are sources of electromagnetic radiation, and this radiation can be intercepted with appropriate equipment. The radiation 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.

Timing Attacks

A more subtle attempt is the timing attack, which reminds us that, at the end of the day, any software 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. The board contained a single chip. Had it been like a regular motherboard, with different subsystems, and attacker, by recording 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 key space. 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 generated 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 356 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 final beep can be heard).

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*30=7,680 trials, a piece of cake. A 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 pint out that (A) the attacker would note 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’s be possible for such information to be available, but even if we don’t know, we could try. Timing patterns could reveal useful information about 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/refused 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.

Power Analysis

Suppose we don’t have access to all the pins of the chip. 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 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 note while maintaining its state. We don’t have such extremely low-level access to the internal structure of the memory chops, 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.

Further then, by knowing the building blocks of a DES crypto box, 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 son 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 note the only way to convey information about an otherwise closed system. And infrared camera can reveal heat patterns occurring during functioning that may lead to a better understanding of the internal structure. 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.

Less Explored Ways

There are cases in which “gentle” techniques like timing or power analyses are not enough to fulfill the attacker’s goal. Or, for that matter, the goal itself is not to break the protection scheme but to break through it. Enter failure-inducing attacks, in which the technique is to induce a failure in the very protection mechanism itself.

Since computing equipment uses electrical power to function, manipulating the voltage becomes an obvious target. A handy but coarse attack would be to blow the circuit up into smoke by applying the 110/220V current (or even more) to it. Not elegant at all and a bit dangerous, but perfectly valid in the real world if this is what it takes to access, say, a bank safe.

This is the very reason security systems should have fail-safe operation; the failure of the protection mechanism should leave the rest of the system in a secure state. A power lock should keep the door locked in the event of an electrical power outage, and a firewall shield be designed so that if tits software crashes, all traffic is blocked between its various interfaces. There are finer approaches to voltage attacks though.

An electrical system, particularly a complex and delicate one like today’s digital systems, only works correctly within a specified range of the supply voltage. What happens if we lower this voltage but just enough to cause malfunctions in the system’s behavior? If the VCC, ideally at +5V, what happens if we make it 4.6V? Does the circuit detect it and shut down? Not necessarily.

In situations where direct access to the circuit is not possible, there are other ways to induce failure; irradiation (which affects the state of registry and memory cells) or temperature (freezing the circuits with a chemical spray or heating them with a portable device). Military-grade integrated circuits have better temperature tolerances, but the wider rage was intended to accommodate harsh weather conditions and not security attacks.

Molecular Computing

We have so far only explored several possibilities which, however off the beaten path they might seem, still revolve around computing and electric current. For a totally fresh approach to solving a security problem, specifically breaking DES, let us take a look at molecular biology.

The idea is to map all nodes to DNA sequences, allow a chemo-biological reaction to happen so that more complex structures are formed, then extract the “winning” combination, of known length/weight, via magnetic separation, and analyze it so that the actual sequence is obtained. The key here is the massive parallelisation of the combinatorial work that takes place when all DNA sequences are missed up and shaken.

Molecular cryptanalysis is still an emerging field. The techniques are still prone to errors, but here is yet another example in which security can be broken by taking a different approach from those considered by the designers of a mechanism.

Traffic Analysis

Lets us go back to the digital world now. In many of the examples above, we wrote about breaking an encrypted message or a system. Knowing that “something is going on’ is already a significant step for an attacked and, in fact, perhaps one of the most devastating. The best spy is one that the counter-intelligence service does not know of. If someone is suspected, already his covert activity is endangered and, as the real world shows us, breaking PGP is not necessarily the only way to get o the cleartext message.

Except for relying on sheer good luck, people have turned to steganographic techniques to hide the presence of a message, without necessarily protecting it further. In the past, steganography relied on cleverness or technology (invisible link, microdot photography). In the Internet age, software allows us to hide messages in images, sounds or text. It is even used for copyright watermarking of multimedia artworks, so easily stolen and reproduced. It is a wonderfully covert channel to send information-who would even suspect the JPEG I sent to my friend had hidden data?

Steganography has its disadvantages. It relies on a well-chosen container that does not reveal the hidden information. For instance, synthesizes images with large areas with the same color information show the “nose”. The data-hiding algorithm itself, if naïve, can lead to the compromise of the message and all subsequent ones. Public packages use known algorithms, and it might be possible that interested agencies already have developed detection techniques.

It matters a lot whom you are up against. However, we will not dwell into the pros and cons of steganography itself. After all, as the attacker does not yet know, there is a hidden message.

Yet, there is something in the big picture that can lead to suspicions; the traffic itself. Out of nowhere, there is a flurry of multimedia attachments between two people. Especially for large quantities of hidden data, you might need many containers. For a party that has access to the larger data pipes, it is possible to compile statistical information, on the E-mail patterns and signal any significant change. If I suddenly start to exchange images or, for this matter, even PGP mails, this may be flagged as “interesting, requires further investigation”.

We do not have to limit ourselves to E-mail. Traffic analysis has been used in military intelligence for a long time. By observing the paths of supply trucks of triangulating radio transmitters, the relocation of the military bases can be inferred. Cellular companies use it to detect fraud by flagging unusual call patterns. Banks analyze electronic payments to detect buying patterns. Intrusion detection systems do it to signal unusual packets. Of course, there will be a lot of false positives. By itself, traffic analysis cannot tell us more, but that’s not its job. Traffic analysis is a statistical tool and this requires large amounts of data. It also requires the computing and logistical means to gather it, including access to points where traffic is concentrated.

But once a single entity in a big set is singled out, it is no longer an undifferentiated contributor to the overall traffic. It acquires an identity in the eye of the attacker, and from here other techniques can be used. Traffic analysis can still be part of them; by analyzing where my cell phone is or what phone calls I place, information about the places I go and the people I know is obtained. The balance of power has also changed; it is no longer the monitoring system against the indiscriminate traffic flow, but the system vs. an entity. The more information is available, the more expanded in scope traffic analysis becomes, and at some point the term ‘surveillance’ would be better suited.

Razvan Peteanu, security analyst based in the US.