On Thu, 24 Apr 2008, Jacob Appelbaum wrote:
| Perry E. Metzger wrote:
| > A pretty scary paper from the Usenix LEET conference:
| >
| > http://www.usenix.org/event/leet08/tech/full_papers/king/king_html/
| >
| > The paper describes how, by adding a very small number of gates to a
| > microprocessor design (small enough that it would be hard to notice
| > them), you can create a machine that is almost impossible to defend
| > against an attacker who possesses a bit of secret knowledge. I
| > suggest reading it -- I won't do it justice with a small summary.
| >
| > It is about the most frightening thing I've seen in years -- I have
| > no idea how one might defend against it.
|
| "Silicon has no secrets."
|
| I spent last weekend in Seattle and Bunnie (of XBox hacking
| fame/Chumby) gave a workshop with Karsten Nohl (who recently cracked
| MiFare).
|
| In a matter of an hour, all of the students were able to take a
| selection of a chip (from an OK photograph) and walk through the
| transistor layout to describe the gate configuration. I was surprised
| (not being an EE person by training) at how easy it can be to
| understand production hardware. Debug pads, automated masking,
| etc. Karsten has written a set of MatLab extensions that he used to
| automatically describe the circuits of the mifare devices. Automation
| is key though, I think doing it by hand is the path of madness.
While analysis of the actual silicon will clearly have to be part of
any solution, it's going to be much harder than that:
1. Critical circuitry will likely be "tamper-resistant".
Tamper-resistance techniques make it hard to see what's
there, too. So, paradoxically, the very mechanisms used
to protect circuitry against one attack make it more
vulnerable to another. What this highlights, perhaps,
is the need for "transparent" tamper-resistance techniques,
which prevent tampering but don't interfere with inspec-
tion.
2. An experienced designer can readily understand circuitry
that was designed "normally". This is analogous to the
ability of an experience C programmer to understand what a
"normal", decently-designed C program is doing. Under-
standing what a poorly designed C program is doing is a
whole other story - just look at the history of the
Obfuscated C contests. At least in that case, an
experienced analyst can raise the alarm that something
wierd is going on . But what *deliberately deceptive*
C code? Look up "Underhanded C Contest" on Wikipedia.
The 2007 contest was to write a program that implements
a standard, reliable encryption algorithm, which some
percentage of the time makes the data easy to decrypt
(if you know how) - and which will look innocent to
an analyst. There have been two earlier contests.
I remember seeing another, similar contest in which
the goal was to produce a vote-counting program that
looked completely correct, but biased the results.
The winner was amazingly good - I consider myself
pretty good at analyzing code, but even knowing that
this code had a "hook" in it, I missed it completely.
Worse, none of the code even set of my "why is it
doing *that*" detector.
3. This is another step in a long line of attacks that
attack something by moving to a lower-level of abstraction
and using that to invalidate the assumptions that
implementations at higher levels of abstraction use.
There's a level below logic gates, the actual circuitry.
A paper dating back to 1999 - "Analysis of Unconventional
Evolved Electronics", CACM V42#4 (it doesn't seem to be
available on-line) reported on experiments using genetic
algorithms to evolve an FPGA design to solve a simple
program (something like "generate a -.5V output if you
see a 200Hz input, and a +1V output if you see a 2KHz
input). The genetic algorithm ran at the design level,
but fitness testing was done on actual, synthesized
circuits.
A human engineer given this problem would have used a
counter chain of some sort. The evolved circuit had
nothing that looked remotely like a counter chain. But
it worked ... and the experimenters couldn't figure out
exactly how. Probing the FPGA generally caused it to
stop working. The design included unconnected gates -
which, if removed, caused the circuit to stop working.
Presumably, the circuit was relying on the analogue
characteristics of the FPGA rather than its nominal
digital characteristics.
The paper at hand shows some very simple attacks, which
today would be very difficult and expensive to counter.
Attacks only get better over time - and even if we come
up with counters to all the digital-domain attacks, the
analogue layer underlying all this stuff is still out
there.
| If we could convince (this is the hard part) companies to publish what
| they think their chips should look like, we'd have a starting point.
Why would you believe that what they publish doesn't already contain the
attack circuitry? How far would you have them go? Publish the VHDL
specs as well? That's exactly the level at which the writers of this
paper added their code - around a hundred lines added to a total of
11,000 or so that describe a very simple chip. Going further, suppose
someone has managed to "spike" the VHDL toolchain - recall Ken
Thompson's classic "On Trusting Trust". Given the funding potentially
available to the kinds of adversaries who might want to mount such
attacks, the possible entry points are many.
This is a very tough problem.
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
