Secret Key Generation with Physically Unclonable Functions

Yesterday, I wrote about automotive security from a big-picture level. Today let's drop down and look at some implementation approaches from the chip level. This comes from Thomas Kallstenious, who is imec's program director for security. At the imec Technology Forum, which is always the afternoon before SEMICON West, he presented some of what they are up to with some teasing hints that there would be more next year.

Physically Unclonable Functions

One problem with chip-level security is that all chips are the same. Foundries invest billions of dollars to make it so. That makes it hard to stop a successful penetration of one chip making other chips vulnerable to whatever it was you found out: you read the secret master key, for example.

One approach to attacking security is what is called a man-in-the-middle attack (it could be a woman, but that's what they are always called). The example Thomas used was a Bluetooth door lock where by recording or altering what was transmitted between the smartphone and the doorlock, there is potential to open other locks.

The standard way to deal with this is that you don't simply send a complicated number from the phone, and the door unlocks. Instead, the door lock sends a challenge, which is a number that is only used once (and shortened to nonce). The phone then sends a reply to the doorlock that depends on transforming the nonce in some way. The man-in-the-middle attack doesn't really work since the nonce will never be used again, the reply will never be used again, and replaying the entire transaction will get the phone to respond, but since the lock never sent the nonce it won't open.

The problem with this approach is that random numbers generated by computers are not actually random, they are pseudo-random. Knuth's famous multi-volume work on The Art of Computer Science has an entire volume dedicated to this (volume 2). For some purposes, this is just fine. But for security, it is not. If you ever see a number a second time you know what is coming next, a more complicated version of what would happen if we generated each nonce by adding 1 to the last one. Because every chip is identical.

Making Chips Different: PUFs

A physically unclonable function, or PUF, is a block on a chip that is different on every chip. The imec approach is to use the technique that some non-volatile memories use: oxide breakdown. A higher voltage than normal is applied to a transistor. For an NVM, breakdown is usually used for one binary value, and no breakdown (so no applying the voltage) for the other. Whether the oxide broke down or not can be detected. Or for more reliability, two transistors can be used, one for 1 and one for 0.

The imec PUF used two transistors at a time, with the same gate. At the atomic level, all chips are not the same, and which of the two bits breaks down turns out to be entirely random. The moment the gate oxide on one transistor is ruptured, the voltage is sunk to the substrate and the other transistor will not break down. But which one goes first cannot be predicted

This has a small area on the chip, so it is cheap. It is also low power. It doesn't require a trusted third party, the service provider can do key generation after manufacture.

Of course, there are some assumptions here, namely that it is truly random which bit breaks down. You want an equal number of 0s and 1s in any given chip, and you want there to be no correlation as to which bits break down in different instances of the same chip. So imec measures randomness and the bias turned out to be 0.498 (0.5 would be exactly half 0 and half 1) so that is statistically equivalent.

Between chips, they looked at the Hamming distance (which is 0 if the values are the same, and 1 if all the bits are inverted, so again 0.5 means no correlation). The data patterns are not related in any way and the PUF data is completely unpredictable between chips.

True Random Number Generator

A lot of cryptography involves random number generators and I already explained that typically these are pseudorandom number generators (PRNG) not true random number generator (TRNG). Thomas wasn't ready to tell us how the new imec TRNG works yet, but he did tell us some characteristics:

• CMOS based
• Open hardware architecture
• Formally security validated and standards compliant
• Resistant against physical attacks
• Small area
• Low power

There nothing not to like, but without the details it is hard to tell.

Encryption

One thing that I hadn't known was that the AES encryption standard was originated by researchers at imec (actually an imec group at KU Leuven nearby). Since its original name was Rijndael, which is obviously Dutch or Flemish, that might have been a hint. It is the global de facto encryption standard succeeding DES. It was developed by Vincent Rijmen and Joan Daemen (Joan is a guy's name in Flemish).

There are thousands of certified products and billions of deployments. It uses 7.6 cycles/byte on Intel (or less than 1 on Intel with the AES instruction, but that's kinda cheating). It is tiny, only 49 bytes of RAM on an 8051. It can run at 53Gb/s in 125mW, or 56Kb/s in 3.7uW (just 65pJ/bit).

imec has developed even more lightweight crypto called Trivium which gets down to about 2pJ/bit and a tiny area.

Sign up for the weekly Breakfast Bytes email: