Breaking the Xilinx Virtex-II FPGA Bitstream Encryption

It's a power-analysis attack, which makes it much harder to defend against. And since the attack model is an engineer trying to reverse-engineer the chip, it's a valid attack.

Abstract: Over the last two decades FPGAs have become central components for many advanced digital systems, e.g., video signal processing, network routers, data acquisition and military systems. In order to protect the intellectual property and to prevent fraud, e.g., by cloning an FPGA or manipulating its content, many current FPGAs employ a bitstream encryption feature. We develop a successful attack on the bitstream encryption engine integrated in the widespread Virtex-II Pro FPGAs from Xilinx, using side-channel analysis. After measuring the power consumption of a single power-up of the device and a modest amount of o-line computation, we are able to recover all three different keys used by its triple DES module. Our method allows extracting secret keys from any real-world device where the bitstream encryption feature of Virtex-II Pro is enabled. As a consequence, the target product can be cloned and manipulated at will of the attacker. Also, more advanced attacks such as reverse engineering or the introduction of hardware Trojans become potential threats. As part of the side-channel attack, we were able to deduce certain internals of the hardware encryption engine. To our knowledge, this is the first attack against the bitstream encryption of a commercial FPGA reported in the open literature.

Posted on August 1, 2011 at 12:29 PM • 21 Comments

Comments

bcsAugust 1, 2011 1:37 PM

Building IC's to be resistant to this would make for an interesting filed of research.

James SutherlandAugust 1, 2011 1:57 PM

@bcs: As I understand it, this is already done in more security-focussed chips such as smart cards - Xilinx just didn't put that level of effort into hiding the FPGA encryption keys, probably assuming it wasn't worth the effort at that point. Presumably future Xilinx devices will use a constant-power implementation of 3DES just in case - but how many actual uses really bother with the encryption, or just use it 'because it's there', rather than actually hiding really sensitive data in that bitstream?

Yes, Cisco have their proprietary code for routers - but is that really that different from Microsoft's running on regular CPUs, which doesn't have this encryption available in the first place? I can crank out bootleg copies of Windows 7 a lot more easily than I could clone a Cisco switch or router, with or without the FPGA code.

DGAugust 1, 2011 5:09 PM

This is the indirect response I got from Xilinx through a distributor after forwarding references to both papers to Xilinx (IACR 2011 papers 390 and 391):

- DPA attacks on semiconductor devices have been known and understood for at least 13 years.
- DPA attacks can be targeted at virtually all processors, microcontrollers, payment cards ('smart cards') as well as FPGA's.
- To date, no field DPA attacks on Xilinx FPGA's have been reported.

It is perhaps interesting to note that we are aware that a company that tries to sell security patents to semiconductor vendors has been distributing these research papers to editors...

While technically feasible, these techniques are not trivial to execute and require significant undetected access to the physical systems under attack, as well as specialized knowledge and equipment.

Xilinx takes all reports of security breaches extremely seriously; they continually add new features to protect the security of our devices.

Customers with concerns about the security of their design should implement a comprehensive security strategy to protect their architecture and design files, access to physical equipment, as well as any other measures they may deem appropriate.

I sent a few papers back on techniques to defeat DPA in particular

Reversible Logic to Cryptographic Hardware: A New Paradigm
Himanshu Thapliyal and Mark Zwolinski

A Novel and Highly Efficient AES Implementation Robust
against Differential Power Analysis
Massoud Masoumi
K. N. Toosi University of Tech., Tehran, Iran

There's plenty of other work in the field.

The response was the equivalent of stating security is the responsibility of the Xilinx customer, and security is what you see or make yourself.

Unfortunately for the likes of Cisco, unlike military applications, unscreened customers are in regular possession of hardware containing FPGAs getting 'securely' configured.

This may not be the biggest threat to 'IP' capture when you consider most 'piracy' occurs in the supply chain. In a Cisco's case the new attack focuses on the economics involved, cost versus return volume of 'pirated' 'IP' sold. Simply steps like controlled access during secure configuration loading into EEPROM linked to device serial numbers would no longer be a guarantee.

Think of it as a war of escalation between driving production costs down and the ease of 'piracy'. What's out of balance here is the production cost of the 'IP' duplication when counting on the encryption (that doesn't really work) against the risk of duplication.

Xilinx will likely improve their story adding better protection or quit selling the feature. This is so reminiscent of DRM schemes which are vulnerable to 'broken once duplicated many' times attacks.

In the past we've seen networking products for instance where every spare FPGA pin is bused to neighboring devices allowing products to be re-manufactured by design changes represented by different programming configuration. I'd imagine a close examination would also show product differentiation done the same way, leaving cheaper products vulnerable to configuration upgrades.

High volume or high profit means high risk. Now will this drive vendor back toward ASICs or simply dilute markets with counterfeit goods for lower volume products with little physical differentiation?

ArclightAugust 1, 2011 6:21 PM

I'm willing to give Xilinx a bit more slack on their position that "security is the customer's responsibility."

Unlike Microsoft, Apple, Google, etc, Xilinx sells chips that are intended to be integrated into products by their customers. Those vendors of complete systems are at leisure to decide if the economics of better security (for their IP) vs. higher cost make sense.

I think Xilinx is correct in stating that DPA attacks have been well-known for years, and they do not represent their product as being "uncrackable."

Now those same customers who buy Xilinx FPGAs may also decide to rely on the bitstream encryption feature to protect the content of other third parties who may be harmed, and determine that it is not economically sensible for them to include additional security features, as the costs are an externality.

So we're back to economics again.

Arclight

NarrAugust 1, 2011 6:51 PM

>these techniques are not trivial to execute and require significant undetected access to the physical systems under attack
>as well as specialized knowledge and equipment.

'Undetected' by whom? The engineer whose company bought a part to reverse engineer it? I bet he'd tell the owner if he saw someone hanging around it lol!

RobertTAugust 1, 2011 10:28 PM

@ DG, "High volume or high profit means high risk"

you're absolutely right about this.

The difficulty is that Xilinx sells a generic device to Cisco where the configuration sequence can be easily extracted by the attacker. It is a joke to talk about DPA extraction because the configuration information is worth Hundreds of thousands of dollars, if not more.

Under such circumstances the attacker will definitely decap the device, after decap they will find the "plain text" output point and FIB a probe points, typically they'll bond this probe point to an unused I/O and than have access to the decrypted stream. All this work will cost them under $5K USD at any good Failure Analysis company, with no questions asked!


Natanael LAugust 2, 2011 1:49 AM

Practically, how does power analysis and similiar types of analysis work? How much knowledge do you need about the hardware? What could stop it from working?

DavidAugust 2, 2011 4:03 AM

@RobertT
"the configuration information is worth Hundreds of thousands of dollars, if not more."

Could you explain how's that?
How would the configuration of a router/firewall/anyCiscoProduct be wroth that much.

What's the scenario?
If I bought a device (router/firewall) from Cisco, then I'm probably a big organization - and I keep my device physically "out-of-reach" from the baddies.
What are the cirumstances in which the configurations of a virgin/clean device bought directly from a vendor (Cisco or a comm' company) be worth that much?

qwertzAugust 2, 2011 4:15 AM

Maybe it is good news for people developing "C like" firmware compilers, i.e. use a "C like language" to write firmware instead of Verilog/VHDL.
Previously they were not able to download the result of the "compilation" into some FPGA because of encryption...

Clive RobinsonAugust 2, 2011 5:17 AM

@ David,

"Could you explain how's that?"

It's the equivalent of knowing what the content of a custom chip is, not the routing rules in a router.

The attack being talked about is stealing the design of the internal electronics and using it to make your own "knock off" of a product without having to invest in very very expensive R&D which could represent 25-50% of the cost of the first production run.

The attack you are thinking of is how to get through a poorly configured router to steal information from other computing devices on the other side.

What moost electronics manufactures know is it's a race to stay ahead of the competition and the competition is in many cases compleatly dishonest. The question is to what level they steal, your ideas, your algorithms, your design, or your good name...

I know of a company in the UK that makes low cost equipment for the broadcast industry, they have lots of inovative ideas. However within weeks of producing a new product an Israeli company has stolen the design and is undercuting the price in countries like Africa.

And others even "rebadge" the knock offs and sell them on on Ebay and the like, and as is inevitable when the re-badged knock off fails the end customer tries to get a warranty repair from the company whose name has been put on the equipment...

This has been going on as an industrial process since the 1960's with "Taiwanise Knock Offs". It carries on in China and Israel and other countries.

Clive RobinsonAugust 2, 2011 5:39 AM

As Bruce notes,

"It's a power-analysis attack, which makes it much harder to defend against"

We know that nonlinear behaviour as often used in cryptography has some very definate power spectrum consiquences when translated into hardware.

We also know from past evidence the resulting power signiture is difficult if not impossible to hide. The best we can appear to hope for is "security by obscurity" in various forms backed by "planed obsolescence" to close any new avenues of attack down as quickly as possible.

It is worth going back to look what happened with Sky Satellite TV set top boxes and the subscription cards to see what sort of arms race you can get into.

At the end of the day if you have a stand alone system, (which these FPGA systems are,) that an attacker can obtain then they will break even the most secure of systems, it is just a matter of time.

You stand a better chance of remaining secure for longer with non-stand alone systems because the attacks can (pottentialy) be detected and thus stopped.

As was suspected with the US plane that crash landed and the Chinese got hold of, some if not all of the secrets can and will be recovered from even the best of designs to prevent the loss.

One of the fundemental tenets of physics is that whilst information can be created it cannot be destroyed, that is cause and effect holds for all time (see the problems Steven Hawking came up with due to black hole evaporation and information loss, which gave rise to the notion that all information about an object that goes into a black hole gets trapped at the event horizon).

RobertTAugust 2, 2011 6:37 AM

@David,
"Could you explain how's that?
How would the configuration of a router/firewall/anyCiscoProduct be wroth that much."

Stored in the FPGA (or the load / configuration file) is Cisco's router R&D if this can be duplicated than producing a copy of their product is trivial, because the PCB and the case can easily be copied. All the existing Cisco software will work perfectly IF I can copy the FPGA's.

A certain unnamed Chinese firm is well known for doing Cisco router rip-offs, the copies are so good that Cisco can only tell the copies by their invalid ID codes.

So if you have ever bought a Cisco router on Ebay, chances are high that it's a fake.

As a matter of fact fake chips are also becoming a big problem, because not only can you get fake Firmware, as in copying the Load for a Cisco product, but you can also get fake FPGA's and even fake Analog semiconductors like opamps. With practically all the worlds production shifted to China, there are big rewards for enterprising individuals that copy a Xilinx product and insert it into the existing supply chain.

Even Cisco thinks they are buying genuine parts but finds out they are fakes. Sometimes you only find the fake because it fails under some corner condition and when you try to work with the manufacturer to identify the problem, they tell you it's not their part.

All chips look like little black things with silver legs. you can stamp whatever you want on the top and sell it through dubious Hong Kong channels.

This is part of the reason that I say true information security is only possible with Supply chain security. Otherwise you really don't know what's happening behind your back.

DavidAugust 2, 2011 7:47 AM

@Clive Robinson - thanks, I did not fully realized what those "configs" were. Now I get it.

The funny thing is when I was a CS student at the Hebrew U (I'm Israeli), I also studied an MBA with specific courses for people coming from CS (don't ask).

A former CEO of a big Israeli comm. company, told us the following:
Every year, he would always go to this big comm. exhibition in Spain.
And with the years he would always see there copycats of his own products made by a Chinese company (Xuaue).
With the years, the Xuaue booth would always erect itself right adjacently to their booth. The CEO of Xuaue that have also attended this exhibition would always come to him and tell him: "I admire you. I admire your company. I admire your products. How innovative, how marvellous".
With the years, the situation became so ridiculous, that Xuaue would number there copycat products in the exact same model numbering as theirs.

The aftermath is that this guy's company actually pulled out many of its models from south-east Asia, where Xuaua has basically taken over sales with the copycats.
He did say that these copycats had virtually no market in Europe and the US.
So yeah, it's a big-big problem.

[Only reason I'm not mentioning the company's name - is because this talks were given to a small group of people in a relaxed & open "meet the CEO" kind of meets. I'm not sure they would benefit by a former CEO of them quoted as saying bad things about any-one]

Dirk PraetAugust 2, 2011 8:52 AM

"The response was the equivalent of stating security is the responsibility of the Xilinx customer, and security is what you see or make yourself."

Pretty much in sync with the worldwide trend that user security is an opt-in. A clever move by corporate lawyers to limit vendor/service provider accountability and liability.

Bruce SchneierAugust 2, 2011 10:23 AM

"Practically, how does power analysis and similiar types of analysis work? How much knowledge do you need about the hardware? What could stop it from working?"

Basically, you need physical access to the encryption device so you can attach test equipment: power analyzers, timing analyzers, radiation detectors, whatever. You need to be able to make it work.

There are some timing attacks that work over a network, but those are exceptions. Basically, it's an attack suited for when the secrets inside a device are not controlled by the person who has physical possession of a device. Think smart card, TV set-top boxes, and so on.

DGAugust 2, 2011 1:50 PM

"Practically, how does power analysis and similiar types of analysis work? How much knowledge do you need about the hardware? What could stop it from working?"

Massoud Masoumi's paper A Novel and Highly Efficient AES Implementation Robust against Differential Power Analysis gives an outline of power analysis with emphasis on Differential Power Analysis (DPA) in Section 3. It's based on the use of a hypothetical model of the algorithm and defensive techniques are aimed at disconnecting the power signatures from the theoretical model.

This paper describes one way to do it, the paper Reversible Logic to Cryptographic Hardware: A New Paradigm describes another using reversible logic.

The paper Lightweight Cryptography and DPA Countermeasures: A Survey (PDF) provides an overview of some techniques to defeat DPA. In a military environment one might expect EMI container encapsulation, power filters and split key access to cryptographic functions to prevent unauthorized access to devices in operation. You'd also imagine other countermeasures might be adopted, as well as need to postulate theoretical models for undisclosed Type I cryptographic algorithms.

Split secrets are also applicable in a commercial environment. Most counterfeiting is done by elements participating in a products supply chain. You could separate the FPGA configuration code loading from the rest of the supply chain requiring collusion between the two operators. The net result would be the need for actual cryptanalysis techniques such as DPA, where the value of such services would increase.

I'd suggest googling for "AES DPA", where the emphasis is as in the present case on recovering keys from Advanced Encryption Standard implementations. Note the side bar Ad for DPA Resistant AES Core.

Nick PAugust 2, 2011 3:28 PM

@ DG

I appreciate the papers!

"You'd also imagine other countermeasures might be adopted, as well as need to postulate theoretical models for undisclosed Type I cryptographic algorithms."

I doubt it. I think we can be pretty sure that most of these guys designing Type 1 cryptosystems at major defense contractors are cleared for the Type 1 algorithms. At the least, the guy who does the DPA & TEMPEST issues at the board level. I could imagine, though, that they might not and NSA could give them a somewhat abstract model that's good enough for DPA analysis.

"The net result would be the need for actual cryptanalysis techniques such as DPA, where the value of such services would increase."

Or just an attack on two points in the supply chain. It depends on the value of the information and level of protection. Groups like Anonymous & LulzSec recently showed that simple attack strategies work even against defense contractors and some systems containing classified information. Hack this PC, bribe this guy, coerce this other guy, etc. Very usable approach for organized criminals or spies going for high value assets protected by two entities following commercial security practices. Just saying...

RobertTAugust 2, 2011 8:25 PM

"Practically, how does power analysis and similiar types of analysis work? How much knowledge do you need about the hardware? What could stop it from working?"

Power analysis is a branch off from a from a Failure Analysis technique calls IDDQ. Typically the setup is
1) remove as many PCB level power supply de-coupling caps as possible.
2) Connect the VDD / GND supply to a constant Current source, adjust current and clock rate until supply voltage stays with upper / lower process limits (say 1V min 1.6V max) (also advisable to set clamp levels (say 0.9V and 1.7V just in case)
3) run the algorithm and record the VDD supply variation using an accurate high speed oscilloscope or similar accurate ADC method.
4) repeat with different known keys and observe any differences in the power signature
5) understand how the power signature variations correlate to Key bits (a lot of statistics and a lot of repeat runs)

BTW you are unlikely to manage to extract the key completely, so what you are trying to do is reduce the possible key space. (brute force on a 64 bit key space is much easier than a brute force on a 256 bit key space)

IMHO the best anti DPA techniques are to add an internal voltage shunt regulator and power the whole crypto ALU section from a constant current source internally off say teh 3V supply. This prevents the typical DPA configuration of an external constant current source from having any effect. Additionally you should design the voltage shunt regulator so that the circuit is disabled if the reg voltage falls below the minimum for the shunt reg to be operational.

Defeating this shunt regulator circuit is very difficult because disabling the shunt regulator will result in an over voltage stress that kill the chip very quickly, I usually add a lock-out Poly fuse triggered if the voltage exceeds the process Vmax. Under voltage will reset the circuit.

There are other digital techniques that attempt to make the circuit take constant power, some suggest fully differential logic, or simply adding a pseudo random current draw to the crypto ALU supply. Personally I don't really like these techniques because they usually open the system up to timing attacks by increasing the clock rate until ALU fails occur.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..