Tomorrow at Cryptographic Hardware and Embedded Systems 2009 I’m going to be presenting a frequency injection attack on random number generators formed from ring oscillators.
Random numbers are a vital part of cryptography — if predictable numbers are being used an attacker may be able to read secret messages, impersonate either party, or replay transactions. In addition, many countermeasures to attacks such as Differential Power Analysis involve adding randomness to operations — without the randomness algorithms such as RSA become susceptible.
To create unpredictable random numbers in a predictable computer involves measuring some kind of physical process. Examples include circuit noise, radioactive decay and timing variations. One method commonly used in low-cost circuits such as smartcards is measuring the jitter from free-running ring oscillators. The ring oscillators’ frequencies depend on environmental factors such as voltage and temperature, and by having many independent ring oscillators we can harvest small timing differences between them (jitter).
But what happens if they aren’t independent? In particular, what happens if the circuit is faced with an attacker who can manipulate the outside of the system?
The attack turns out to be fairly straightforward. An effect called injection locking, known since 1665, considers what happens if you have two oscillators very lightly connected. For example, two pendulum clocks mounted on a wall tend to synchronise the swing of their pendula through small vibrations transmitted through the wall.
In an electronic circuit, the attacker can inject a signal to force the ring oscillators to injection-lock. The simplest way involves forcing a frequency onto the power supply from which the ring oscillators are powered. If there are any imbalances in the circuit we suggest that this causes the circuit to ring to be more susceptible at that point to injection locking. So we examined the effects of power supply injection, and can envisage a similar attack by irradiation with electromagnetic fields.
And it works surprisingly well. We tried an old version of a secure microcontroller that has been used in banking ATMs (and is still recommended for new ones). For the 32 random bits that are used in an ATM transaction, we managed to reduce the number of possibilities from 4 billion to about 225.
So if an attacker can have access to your card and PIN, in a modified shop terminal for example, he can record some ATM transactions. Then he needs to take a fake card to the ATM containing this microcontroller. On average he’ll need to record 15 transactions (the square root of 225) on the card and try 15 transactions at the ATM before he can steal the money. This number may be small enough not to set off alarms at the bank. The customer’s card and PIN were used for the transaction, but at a time when he was nowhere near an ATM.
While we looked at power supply injection, the ATM could also be attacked electromagnetically. Park a car next to the ATM emitting a 10 GHz signal amplitude modulated by the ATM’s vulnerable frequency (1.8 MHz in our example). The 10 GHz will penetrate the ventilation slots but then be filtered away, leaving 1.8 MHz in the power supply. When the car drives away there’s no evidence that the random numbers were bad – and bad random numbers are very difficult to detect anyway.
We also tried the same attack on an EMV (‘Chip and PIN’) bank card. Before injection, the card failed only one of the 188 tests in the standard NIST suite for random number testing. With injection it failed 160 of 188. While we can’t completely predict the random number generator, there are some sequences that can be seen.
So, as ever, designing good random number generators turns out to be a hard problem not least because the attacker can tamper with your system in more ways than you might expect.
Theo,
Did you speak to Ross Anderson about this?
It is very very old news I was doing it with electronic wallets back in the days of Mondex.
I had corespondence with Ross when he was looking at using self clocking logic to try and prevent DPA attacks.
I pointed out that all that was needed was to pick an appropriate generator frequency and either use it directly or modulate it ontop of another carrier.
Infact if you want to improve the attack have a look at what makes a paremetric amplifier tick, you might be highly surprised by what you can do by mounting a sim or other such single chip micro in a length of 3cm waveguide…
Oh and if you search this blog and Bruce Schneier’s blog you will see I have mentioned this a number of times in the past.
Hum, I think you mean 1965, not 1665? Unless they were applied to pre-enlightenment electronic circuits 🙂
Ian:
Robert Hooke, who discovered the phenomenon, died in 1703.
@Clive Robinson:
Indeed, there have been rumours of this effect from the industry. In particular designers have been well aware of the need to avoid parasitic injection locking. But there has been little published about this as an active attack, and in particular how easy it is. And it’s still surprising that recent smartcards are vulnerable. Given that some of the defences I describe are similar to those for DPA, it’s puzzling why a card which presumably has DPA protection is still affected.
@Ian:
Injection locking was described by Christiaan Huygens (who invented the pendulum clock) in a letter of 26th February 1665.
Theo,
As you note “injection locking” is well known to (some) electronic design engineers and is the principle behind NTSC and PAL colour osc syncing, 19KHz stereo pilot tone re-generation and thus is in most peoples homes.
Also quite a few early designs of data coms and spread spectrum receivers work this way.
Oh and early frequency synths used banks of crystals that where “pulled” by similar techniques.
I had an Email chat with Ross about it getting on for ten years ago when IR “fault injection” for reading the contents of chip ROM was the latest thing. It was shortly before an EMP via “pico probe” fault injection paper was to be published. Ross suggested I chat to the author in Belgium to check with him.
The work I had done was on electronic wallets such as Mondex that had no RF shielding built in and must have been around 1990, and was based on work I had done several years prior to that on Remote Telematry Units (RTU’s) for the offshore industry to understand the effects of PMR equipment on the CMOS CPU (1802) card.
It turns out that all oscilators (Xtal, CR, LC, etc) can be “pulled” via injection locking. Ian Hicks of Wireless World published a couple of articals on it and the assumption was it was the change in base/gate bias point causing phase modulation to pull the oscillator. However I’m not convinced it is the only effect as there are parasitic effects visable with very low levels of locking signal. In practice a signal level of one tenth the tuned circuit level is sufficient to get a reliable lock.
There was a design going around for a Random Number generator using a lage number of 14Pin DIL pack Xtal Osc’s to get “many jitter sources” around the same time. It exhibited the problem if insufficient decouping on the power lines was used.
When Intel brought out their on chip “roulet wheel” design using an Xtal osc and free running OSC modulated by the noise from a resistor, a few tests showed (from current consumption) that it was quite suceptable.
I guess the only reason it was not obvious at the time was the way they hashed the output.
I’ve designed a few True Random Number Generators (TRNG) in my time and they realy are “sensitive little beasts” that need lots of loving care in feeding and caging.
Most comercial designs I have seen in the past for some reason did not use balanced circuitry in the noise generator or true instrumentation amps. Worse was the slap dash use of RC coupling and analogue to digital conversion (often ordinary TTL Schmitt triggers).
In essence the most sensitive part of the design on whic every thing rested had little or no thought in it and appeared to use either a standard “designers notes” semiconductor noise source or worse. It was often clear that the designer had no idea of what effect filters would have on the output of the noise source… Oh and invariably there would be a “magic entropy normaliser” in the wrong part of the design suggesting that the output without it would not exactly be unbiased…
So if you are ever building or buying a noise based system, make sure you get at the raw output before any “magic entropy normalisers” and run tests on it all the time to look for changes in the output.
Another little trick you might want to look at is square wave modulation onto your carrier signal. This has a habit of traveling quite a way into the logic of a chip and thus might be a way to cause a change in program state without crashing the program.
The question is would it be possible to find a way to sync it to the running program to make it a reliable attack vector, I have a sneaky fealing that the answer is yes.
Then there is the less relevant attack these days (expcept on leads) of “resonating” a conductor to target one specific part of the circuit. A side effect of this is that you can sometimes use it to lift data out.
There was a gambling console I looked at where you could get state information out of it simply by illuminating it from an RF source and looking at the super imposed info on the other side. I did have a look at mounting smart cards in a bit of X-band wave guide and a wide band IQ demodulator. When you get the level right you would be surprised at just how much cross modulation there is…
I was somewhat aware of this, but interesting to see it carried out in practice.
The bast way to solve this type of problem is to avoid it altogether. Luckily most of the practical ways of doing this are already used (perhaps dating back to when protocol designers could not count on having a high quality RNG on the device).
The basic idea is to limit the times you have to use the RNG to points where active attacks are difficult to perform. If the key is created by the device, than have it create the key in a safer place (e.g. factory floor). Yes I know we want to eliminate key depots and the like as much as we can, but typically there has to be some amount of trust in the manufacturing process.
If you need to create random keys as part of a protocol, than bias it so that the host, not the exposed client, generates the key. As mentioned above, this was already a pretty common practice – an expensive HSM contained in a secure facility has a higher level of trust than a $5 smartcard (or an ATM) where attackers have physical access. That won’t solve smartcard-to-terminal issues, but that type of communication does not need true RNG anyway (derived keys, perhaps with a forward-security system could work instead).
I don’t recall financial protocols making much use of a device’s RNG after initialization. Has anyone identified a real attack against a specific protocol?
@ trsm.mckay,
“The bast way to solve this type of problem is to avoid it altogether.”
Definatly, however,
“If the key is created by the device, than have it create the key in a safer place (e.g. factory floor).”
Like most of the older solutions do not work simply due to the “rate of use”. Effectivly you end up with exactly the same problem as key managment for OTP’s.
The real question should be,
“When do we realy need truely random and when will pesudo random do?”
For instance the BBS generator is 100% deterministic but as far as we currently know (on the same assumption as RSA) provably secure.
It uses a couple of very long primes, and they should be “Truely Random”. The downside of the BBS is it’s oh so slow for the number of usable bits.
But does this matter?
Well yes and no.
For instance what if you used the BBS to “perturbe” another much higher speed PRBS such as for arguments sake the RC4 stream generator. There are two easy ways to do this one is add the BBS output (P) into the output byte selection (ie x=Sary[I+J+P]) the other is to use it modify either the I or J pointers used to swap the bytes in the State array (Sary).
However either way is still 100% determanistic so in theory could be worked backwards etc.
However what if you used the principle of “indetrministic sampling”?
That is the RC4 generator and BBS run continuously just as fast as they can in a microprocessor, when an output byte is needed the micro services it via an interupt. As long as the demand for random bytes remains un corelated with the micro then the result will (within limits) be effectivly non determanistic which is kind of the definition of a truely random number sequence.
In essence it is an engineering problem that needs to be guided by sound design principles that correctly account for the (security) issues involved.
And the problem with this is “side channels” in reality all our current crypto algorithms are unbreakable the implementations however are breakable due to “side channels”.
Side channels are in most cases EmSec/TEMPEST attacks. In the case of Theo’s attack it is a “suceptability attack” not an “emmission attack”.
One of the problems is that the engineers who know about “suceptance and emmission” are analog/RF communications engineer’s (more recently EMC engineers as well) and they just do not get asked for their input at an early stage of the design of crypto projects (if at all).
Clive rightly asks “when will pesudo random do?”. I should bring up an occasional requirement that makes it more difficult to use pseudo random. Sometime we need to ensure that past random numbers cannot be determined if a device is broken into and all the secrets compromised. Kind of a perfect-forward-security for random number generation.
It takes more work to meet this objective with pseudo random numbers, and I think the implementation would have to be pretty careful (thinking about how we could use some of the last BBS Generator output for creating new random primes that could not be traced back to the original values…). If it can be done securely, it would slows things down even more.
Thanks both of you for the interesting comments and ideas.
The re-radiation idea is something I’ve worked on, and there’s also a fairly recent paper “The Re-emission Side Channel” by Burnside, Erdogan and Arslan:
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4595813
(sadly I can’t find a non-subscription version online)
For using a PRNG, I suppose you need enough entropy to initialise it. Otherwise you can just bruteforce by trying all possible seeds and noting the sequences, assuming you know roughly how far down the sequence you are likely to be.
I agree, though, that there’s relatively little need for MB/s of random bits unless there are further attacks revealed on the PRNGs. And for many protocols even a little entropy is enough once the whitening function is run on top (if you only get 3 tries, you need to know pretty much all the state).
Clive, do you remember any more details of that ‘EMP via “pico probe” fault injection paper’? That would be interesting to read. There’s some mention of the technique in the dependable systems literature but I can’t find anything specific on a quick look.
Theo,
Ross might remember it was around the time he was looking at non sync logic to trye to get around DPA issues.
Also there was a paper about a month or so before about using a highly focused light source for fault injection (I don’t think it was a laser however).
Unfortunatly I’m back in hospital yet again (problems involving both lack of the red stuff and the red stuff going solid in the wrong places the cure for one is contra indicated by the other), I’ll have a google around, and see if I can find it.
Out of interest, which Chip&PIN cardstock did you try it on, and get that promising RNG fail result? And what was the issue date of the card? You should be able to see it written on the back, either Oberthur or Gemalto are the most common bureaus here in UK.
Mike.
@ Mike, Theo,
You two should have a chat I can easily see a rather good joint paper out of this 8)
And as I said get a suitably wideband IQ Software Defined Receiver and I think the pair of you could have quite some fun for the next few months.
I have more than good reason to think that “susceptability” and “cross/re-modulation” are going to be the next biggest source of effective side channel attacks.
And it has all sorts of implications for Banks with regards to “security tokens” for EPOS, ATM and iBanking.
Oh and passports you will find that some of the chips in passports can be “enumerated” to the point you can remotly identify the country and date of issue. This makes “ID Shopping” more feasable than it currently is.
Theo,
Whilst I remember, a simple experiment for you and anyone else to carry out just to show how easy it is to mistake random and non random behaviour.
Get a D-Type latch and clock it from a XTAL or sig generator.
Get a variable frequency oscilator and put it into the D pin and have a look at the output on an osciliscope.
At first it looks fairly random but then you notice that the envolope of the waveform has nulls at points that are related to the difference frequency between the two oscilators…
If you integrate the output wave form either digitaly with an up/down counter or lowpass filter you get what looks very close to being a sine wave.
My advise to any one making a “roulet wheel” type TRNG is to always always monitor the raw output of the “slicer” / sample and hold / mixer with the likes of a frequency/sequency analyser.
@ theo
Many keep saying that these attacks are theoretical and weren’t demonstrated until the papers were published. I think it’s more appropriate to say they weren’t publicly demonstrated. One public web site (google it) has a TSCM specialist discussing issues like keeping STU-III secure telephones safe and doing so partly by banning cell phone use nearby. At one point, he mentions that having a specific model of cellphone/service within a certain distance of the device will compromise its key[s] due to the EMF waves it emits. He describes what’s essentially an inadvertant, active EMSEC attack on the STU-III by the cell phone and electromagnetic leakage of the key.
I’d also note two things. First, even the BLACKER A1-class VPN had TEMPEST shielding for the BLACKER Front End devices. They knew, even then, that the hardware and software couldn’t be trusted unless EMSEC attacks were prevented. That was two decades ago. Second, nuclear command and control systems continue to use older methods of building computer boards and networks even when “better” stuff is up for grabs. They cite reliability, but I bet EMSEC has to do with it too. It’s probably easier to prevent passive/active issues on those primitive designs than on a modern SOC. I keep thinking about building a cross-domain guard or something out of *old* technology instead of new. I bet a Chinaman’s salary that it’s easier to secure a good old design than a good new one. And 20Mhz is plenty fast to people who know how to code. 😉
Nick P
Of schneier’s blog infamy