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-

        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

            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

| 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]

Reply via email to