Guides Zen and the Art of Breaking Security - Part I

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 [1] 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.


Designing a secure solution, be it a 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 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 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.


TEMPEST

One example of side-channel attacks is the TEMPEST technology [2].
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.


Timing Attacks

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 ‘’ (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 [3].


Power Analysis

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 [4]
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 ([5] referred to in [6]).


In the next part we will look at other ways to break a secure system.


References for Part I

[1] Robert M. Pirsig, Zen and the Art of Motorcycle
Maintenance: An Inquiry into Values
, Bantam Books, 1984


[2] http://cryptome.org/#NSA-TS


[3] Paul C. Kocher, Timing Attacks on Implementations
of Diffie-Hellman, RSA, DSS, and Other Systems

http://www.cryptography.com/timingattack/


[4] Paul Kocher, Joshua Jaffe, and Benjamin Jun,
Differential Power Analysis
http://www.cryptography.com/dpa/Dpa.pdf


[5] David Kahn, The Codebreakers (revised
ed.), Scribner, 1996


[6] John Kelsey, Bruce Schneier, David Wagner,
Chris Hall, Side Channel Cryptanalysis of Product Ciphers
http://www.counterpane.com/side-channel2.pdf


SecurityPortal is the world’s foremost on-line resource and services
provider for companies and individuals concerned about protecting their
information systems and networks.
http://www.SecurityPortal.com
The Focal Point for Security on the Net ™

Latest Posts

Related Stories