World's First "Unclonable" RFID Chip

An anonymous reader writes to tell us that a new RFID chip from Verayo claims to be unclonable through the use of the new Physical Unclonable Functions (PUF), sort of an electronic DNA for silicon chips. "Basic passive RFID chips can be easily cloned by copying the data residing on one chip to another. Verayo's PUF-based RFID chips cannot be cloned, and provide a very strong and robust authentication mechanism. No other chip or device can be disguised as the original chip, even if the data is copied from one Verayo RFID chip to another."

Comments

Yeah?

[WillKemp]

Uncloneable today - cloned tomorrow...

Re:Yeah?

[morgan_greywolf]

It's kind of like those 'unhackable' computers, networks and software we keep hearing about. *yawn* Wake me up when someone actually makes such a thing and it actually, you know, works.

Re:Yeah?

[eln]

I have an unhackable computer. I would give you the IP, but it's not hooked up to the Internet. Or any other network. Also, it's powered off and buried 300 feet underground in a 6 foot thick lead-lined vault. On Pluto.

Re:Yeah?

[nog_lorp]

So you think, but I already have root.

Re:Yeah?

[Tubal-Cain]

Congratulations. You rooted a honeypot VM.

Re:Yeah?

[NotBornYesterday]

Okay, so according to TFA (yeah I know, not supposed to read it, yadda yadda yadda), it looks like the RFID device isn't authenticated by its ID, but by a series of challenge-and-response tokens it has that are also stored in some central database, which appear to increment as they are used.

There appears to be a finite number of challenge-response pairs in the authentication database. How limited is that number? Are they also stored on board the RFID tag? Are they generated from the serial# and/or ID#?

What is the length of the challenge, and of the response? Could a captured item (ie, passport) with such an RFID tag be brute-force interrogated (hit with a series of random-number "challenges" to see which might elicit stored "responses"), and counterfeited that way?

Could this scheme be vulnerable to MITM-style attack?

Re:Yeah?

[mollymoo]

According to the manufacturer's site, up to 2^64 challenge-response pairs (each 64 bits). They aren't stored on board the tag, but generated on demand. The uniqueness comes from normal manufacturing variations, so they don't need expensive techniques to make each chip unique. With each tag before using it you capture however many challenge/response pairs you will need. The pairs should in theory should only be used once, but in practice I suppose that's up to the implementation, the tags will happily keep giving out the same[1] response to the same challenge. Given you need to interrogate the IC for each challenge/response before putting it in service, there will be a temptation to re-use keys to reduce the time for training the system for each key.

The large number of challenge/response pairs possible makes cloning implausible (you'd need to capture all 2^64 pairs), until someone can reverse engineer the "algorithm" and find the hidden variables (manufacturing variations) which form the "key" for a particular tag. I'm sure someone will work out how to do that eventually, but given it seems to be an analogue "algorithm" with a potentially large number of hidden variables I don't know how easy it will be. It seems like a sufficiently interesting problem that researchers will be queuing up to try.

[1] Apparently not always the same - there is some finite probability of the same tag giving different responses to the same challenge, but they have techniques to reduce this and its impact. The vagaries of analogue electronics at work.

Re:Yeah?

[ultranova]

The algorithm may be hidden in the hardware, if it is not rock solid (and published) I give this technology a huge chance of failure.

An analogue algorithm using "manufacturing variations" means basically white noise in the circuit. Cloning that accurately might indeed be an extremely difficult and costly operation: you basically have to recreate the chip with tolerance of tiny fraction of the original tolerance (=very expensive), or use a massively powerful (=big, not something you can carry with you unnoticed) computer to simulate it.

Re:Yeah?

[Ian Alexander]

Congratulation!

Only one, you cheap bastard?

Re:Yeah?

[Macman408]

More details can be found for the geekily-minded in their academic paper (PDF warning!).

Basically, it's a series of multiplexers. The challenge selects exactly what pair of paths through the multiplexers are taken, and the output is a 0 or 1 depending on which path is faster. Presumably, this then gets replicated or reused several times to make a multi-bit response. They show an LFSR in their diagram, but don't explicitly say what they use it for - my guess would be they initialize it with the challenge, then use it to generate the programming bits to select a path through the multiplexers.

So yeah, it's pretty difficult to manufacture a circuit that exactly matches it. And it would probably take too long to exhaustively try all challenges to discover what the responses are. However, I still see several possible weaknesses.

First, the challenge/response pairs that are stored (which are outside the RFID chip, used to verify that it is valid) must be selected randomly. If an attacker can reduce the number of possible challenges from 2^64 down to a much smaller number, it's no longer secure: he can interrogate the RFID chip for its responses to those challenges, and then program those into a new chip. It's not completely cloned, but as far as anybody can tell from the stored challenge/response pairs, it is identical.

Second, the paper shows that about 11 bits out of every 128 are different each time you use the *same* challenge with the *same* chip. To catch most false negatives with the fewest false positives (ie highest security possible), the threshold would have to be probably only 104 correct bits out of 128. (The same challenge with different chips is close to the ideal of 64 changed bits out of 128 total). Presumably, these numbers are approximately halved when using 64-bit challenges and responses. This makes the chip weaker than something that really has 2^64 combinations; you don't have to get all 64 bits right, you just have to get maybe 52 of them right. In the paper, they suggest a threshold of 96 correct bits - or presumably 48-bits with the 64-bit implementation. That effectively knocks a good 5 orders of magnitude off the number of possible responses.

Third, what's to stop somebody from figuring out the timing parameters of a particular RFID, and emulating the circuit? They say in the paper that they "scramble its output to thwart such 'model building' attacks." OK, how? Is this why the LFSR is in the design? Obviously, they're trying to prevent their competitors from copying their work, but are they also trying to get security through obscurity? We all know how well *that* works.

Fourth, the challenge/response pairs have to be stored securely. If an attacker can get them, it's game over. Considering most companies still haven't figured out how to secure their customers' credit card numbers, the only thing keeping an attacker at bay is a lack of motivation. Make the payoff good enough, and this is probably the weak point in the system that would be hacked first.

Fifth, if I'm a malicious supplier of RFID chips, I might be able to find two similar chips. I sell one to somebody else, and keep the second for my own malicious purposes. Since it doesn't have to be exactly identical (within a few bits is fine), and I can use the principles of the birthday attack, this shouldn't be a terribly difficult thing to do. Now, if I did my math right, a malicious supplier would have to buy around 83 million RFID chips to have a 50% chance of getting one pair that are considered to be matches, *if* the threshold is set at the most secure level possible. I'd bet a typical threshold would drop that by another order of magnitude or so. That's a lot of RFID tags, but given RFID's target (low-cost, high-volume), it's not so unreasonable.

The paper, like many involving an actual company, lacks a lot o

Honest injun!

[Just Some Guy]

And this time we really mean it!

Re:Honest injun!

[Osurak]

And this time we really mean it!

Anybody want a peanut?

Press release and marketing hype. 1st paragraph:

[BitterOldGUy]

Verayo launched the worldâ(TM)s first unclonable silicon chip â" the Vera X512H RFID chip. This new RFID chip is based on recently announced breakthrough technology called Physical Unclonable Functions (PUF). PUF technology is a type of electronic DNA or fingerprinting technology for silicon chips that makes each chip unclonable. Verayoâ(TM)s PUF-based RFID technology offers

So, is it unclonable?

Let's have a pool to see when it's cloned. I got by the end of the year by a Stanford student.

Isn't that logically impossible?

[danaris]

Forgive me for my ignorance (and I haven't RTFA), but my understanding of RFID is the only way to tell what an RFID device is is by listening to it broadcast. Well, if you listen to a device broadcast enough, particularly if you listen in on a conversation between it and what it's supposed to talk to...doesn't it then become relatively simple to create your own RFID device that broadcasts all the same things as the original chip, and responds in all the same ways to input?

Seems to me it's just another instance of "DRM doesn't work," only in this case all the communication between supposedly secure nodes literally has to take place in the open air...

Dan Aris

Re:Isn't that logically impossible?

[corsec67]

You could have a more powerful RFID tag that has some computation ability. This would allow you to generate a new code for every communication, preventing your replay attack.

If the list of request-responses was a true one time pad, then they might actually have some fairly good security from a radio attack, but the number of queries to the rfid tag would be finite.

If they use any kind of cipher, then it is very much open to attack.

Re:Isn't that logically impossible?

[Tetsujin]

Forgive me for my ignorance (and I haven't RTFA), but my understanding of RFID is the only way to tell what an RFID device is is by listening to it broadcast. Well, if you listen to a device broadcast enough, particularly if you listen in on a conversation between it and what it's supposed to talk to...doesn't it then become relatively simple to create your own RFID device that broadcasts all the same things as the original chip, and responds in all the same ways to input?

Seems to me it's just another instance of "DRM doesn't work," only in this case all the communication between supposedly secure nodes literally has to take place in the open air...

Dan Aris

Well, I don't know if I can answer your question in terms of the technical limitations of RFID - but in general, your argument ignores the possibility that RFID data is being encrypted.

For instance: suppose the subway fare system uses a set of encryption keys - some of these keys will be stored on the fare cards (the RFID devices) and some will be stored in the machines that interact with these cards...

Now suppose the interaction starts with one of these machines broadcasting, looking for a fare card... In some part of the initial handshaking the machine sends out a transaction number - encoded using an encryption key that fare cards can decode. In all further communication that transaction number is part of the encryption key used by the fare card.

You can listen in on this transaction, but you can't do anything with it unless you can decode the messages... You can't replicate the transaction because your response has to include the transaction ID given to you by the gate machine...

So in the context of an "uncloneable" chip - you could create another chip that pretends to have the same "Physical Uncloneable Functions" - but that depends on first knowing exactly what they are... If it's handled in a static way and not encoded, that's pretty easy. If it's handled in a way that one RF exchange only gets you one part of the data you'd need to replicate the thing - or if the data you'd need to replicate the chip is encrypted, then that makes the problem substantially harder...

Fundamentally, though, I believe you're correct - if it can be made once, it can be made again... The trick is to make it difficult to do that.

Re:Isn't that logically impossible?

[maxume]

The chip is characterized at the factory by sending it challenges and recording the responses. Later, the chip is issued one of the recorded challenges and the response is compared to the factory response.

If the challenge-response is done in such a way that it can be recorded, then each challenge is only good the first time it is used.

There is some possibility that the behavior they are exploiting is not as robust as they think and that the response characteristics of the chip could be determined from a limited number of challenges (and then emulated), but on the surface, it looks pretty reasonable, especially for situations with a limited number of challenges (so authenticating an event ticket with it is great, but maybe not so much an ID).

Re:Isn't that logically impossible?

[debatem1]

The very idea of a one time pad is that they don't cycle over time. If they do, it becomes an XOR cipher with a known period- trivially easy to break.

Also, a one time pad cannot securely gain pad length over the untrusted channel, since doing so would violate the 1:1 rule. Each character of new pad would have to be encrypted against- and thus consume- one character from the old pad.

Re:Isn't that logically impossible?

[Thelasko]

This would allow you to generate a new code for every communication, preventing your replay attack.

Already done. In fact, if there is an "unclonable" RFID chip, my money is on it being in cars before your passport.

Wrong Section

[trongey]

Shouldn't this article have been posted in the Humor section? I know I got a chuckle out of it.

Re:Press release and marketing hype. 1st paragraph

[Kingrames]

I'd take your bet, but odds are, it's already been cloned.

Fairly straightforward

[jimicus]

Most obvious mechanism is that the chip has sufficient intelligence to be able to cryptographically identify itself using public key cryptography, and the keypair is embedded on the chip at the manufacturing stage.

Would work beautifully, but it's completely broken the day someone manages to get the private key out of it.

Why is this automatically discredited?

[jeffmeden]

You conduct overheard conversations all the time and have no issue with considering them "secure": namely via SSL/TLS encryption. All that's necessary to create an RFID that can't be completely duplicated is for the chip to hold on to more information than it broadcasts, and then only reveal that information in a clever way (asymmetric encryption). A well coded challenge-response handshake can allow the reader and chip to conduct a conversation that is 'unique' and cannot be easily duplicated later on. Sure, there is the potential for it to be improperly coded, or downright misrepresented. However, don't count it as a failure before it's even seen the light of day.

Re:Why is this automatically discredited?

[debatem1]

What they are claiming is not that the key can't be extracted from transmissions- a relatively humdrum requirement- but rather that unlimited physical access to the device cannot reveal the key, which I find dubious in the extreme. Add to that that there have been numerous devices that have claimed this in the past, only to fail miserably, and it seems pretty reasonable to assume that this will fail as well.

duh!

[MobyDisk]

From the illustration, it looks like a simple challenge response mechanism. All I have to say is: duh!

So they finally added some form of authentication. This is what smart cards were supposed to be when I first heard about them 10 years ago. Simple RFID was never intended to be used for something secure: it was meant to replace bar codes or magnetic strips.

Not for Active

[brunes69]

What you are talking about is a passive RFID device, like most offense keycards from the 80's and early 90s. RFID nowadays is more complex, with the devices having a small computer chip in it that is actually powered up by the RFID. Having this chip allows secure encryption between the device and the terminal such that sniffing in on the conversation should get you no further than sniffing on a properly negotiated SSH session will.

The hole in the scheme of course is, if the crook gets his hands on the keyfob for a short period of time, it is the same as having your SSH private key, and he can clone the chip in the keyfob and return the original without you even knowing.

This company is saying they have a new chip that incorporates physical properties of the chip itself int the encryption somehow such that cloneing it would be recognizable.

Re:So far, 2 for MIT...

[getclear]

Texas A&M may be able to find an organic replacement for the silicon used in the chip, and then implant it in farm animals to further research on the effects of "I can't beleive its NOT silicon" based RFID chips in them.

No, just very, very difficult to do right.

[OmniGeek]

In theory (crypto theory), this can be done if the parties communicating have a shared secret piece of data and a crypto algorithm, resistant to reverse-engineering from outside, that enables them to exchange that secret data without eavesdropping, man-in-the-middle attacks, or a brute-force cracking of the crypto algorithm.

This is quite hard to do properly in general, as the plethora of lousy cryptosystems attests. It *can* be done if one has enough processing power (tough for RFID chips that operate from microwatts of someone else's broadcast RF energy) and a good enough encryption algorithm (see "lousy cryptosystems" above).

Of course, if you can duplicate the data content and algorithms of the RFID chip, say by physically dismantling it layer-by-layer with a destructive analysis, you can clone it even if you don't know the shared secret. The article is claiming (without ANY credible evidence, BTW) to have somehow made this impossible, presumably by creating some random-but-repeatable property in the chip that cannot be extracted by analysis for reproduction in a cloned chip. Unless they've come up with something VERY effective, I'd bet on this system being cracked within months just like all the other RFID schemes. The lack of description or references to how their system works smells like bad crypto and security-by-obscurity to me.

They used Unclonable and DNA in the same sentence

[cutecub]

The use of language is strange.

Unclonable: cannot be cloned
DNA: a molecule that clones itself.

Its not the best choice of marketing metaphor.

Its like saying that an event is possibly inevitable.

-Sean

A short primer on PUFs

[quo_vadis]

This chip utilizes PUFs (so called Physically Unclonable Functions). These are currently a hot topic of research, especially in the secure embedded computing community.

The fundamental idea is that a PUF should produce a unique value for a chip, in a repeatable fashion, with a side effect that modification of the chip will be detectable.

PUFs are of 4 main types -
1. Optical - These are the oldest forms of PUFs. They started with physicists trying to use chips as diffraction gratings. You shine a laser at the silicon vias and record the signature of light. These require depackaging the chip in question and are mostly impractical
2. Silicon - Usually implemented as long delay lines, but are sensitive to environmental conditions (mainly temperature & injected faults) There remains an ongoing research attempt to make these better (less reliant on environmental factors)
3. Coating - These are currently considered one of the best forms of PUFs. The topmost layer of the chip has some embedded metal flakes. The bottom layer of the chip has a capacitance sensor. Since the distribution of the metal flakes is random, the capacitance is random and unique to each chip (the resolution of the capacitance sensor is tuned to ensure this). This method has the added advantage that the minute someone tries to attack the chip, by depackaging it, the capacitance changes and the chips data (usually the secret key for an encryption cipher such as AES/DES) can be wiped. The main problem is that it adds a few extra fab steps , which means it increases the cost. Additionally, the first calibration costs more money to do.

4. Intrinsic - These are the current area of research. In particular for FPGAs. As any hardware designer knows, RAM cells are initalized to random values, but most FPGAs have some small logic which resets them all to zero. If we remove that logic, we have a chip, which has a whole bunch of random numbers, which will usually initialize the same way, based on process variation etc. This technique has been shown for FPAGs and will probably be brought over soon to full scale chips.

In order to keep this short, i have omitted a lot of references, but you can find more info, about intrinsic PUFS here.

Actually Phillips does a lot of research with PUFs and I am surprised that Verayo claims to be the first maker of PUF based chips.

Re:A short primer on PUFs

[quo_vadis]

I realize its bad form to reply to my comment, but I would like to add a bit about how authentication works using PUFs

When the chip is manufactured, the device creator records the original response of the chip to a series of challenges and calls this reponse vector r'. When a chip is powered up, it energizes the PUF circuitry and records the output into the internal PUF value register(k). Next, when the chip (usually a passive RFID) needs to be authenticated, the external party sends a challenge. The challenge (c) is processed through some encryption mechanism (called f() )using the key (the saved PUF register value) to produce a response(r).(For those keeping track at home, r = f(c,k)). This response is sent back to external party. The external party sends n such requests and compares the received response vector to the expected response vector (r') if r and r' are the same, then the chip is authenticated and work continues.

Of course, like any normal physical phenomenon, there is some variation between any two power ups. Thus, the key might change. In order to compensate for this, the key is calculated to be the codeword of some code with a long length. Then, for each subsequent power up, the new key(k') is decoded using nearest neighbor decoding as a codeword of the same code. Finally, the distance of the new key(k') and the expected key(k) is stored into a special vector(l), which is reapplied to key produced at next power up.

So, to clear up a few questions -
1. Its not like OTP (one time pad) encoding, because a unique challenge should produce a given response for a unique chip every time
2. It is not meant to be the only encryption being used. There is usually a second code on the set of challenges to ensure that the challenge vector being created is itself part of a code.
3. Man in the Middle & duplication attacks should be hard as the device manufacturer can release a small subset of real challenges and could always hold back some challenges, which it can use to be completely sure. Additionally, it may release different sets of challenges to different customers.

Sure it does

[gardyloo]

Plan 9 from User Space.