41

A number of crypto-dongles make the claim that it is impossible to extract the stored private key once written.

Yubico:

The YubiKey AES Key information can never be extracted from a YubiKey device – only programmed to it.

Nitrokey:

Other than ordinary software solutions, the secret keys are always stored securely inside the Nitrokey. Their extraction is impossible which makes Nitrokey immune to computer viruses and Trojan horses.

The claim as literally stated seems like marketing nonsense. The dongle itself has access to the private key so somehow it can be read.

Still, it's an interesting claim. The choice of words -- "never", "always", "impossible" -- suggest that there is something that can be proven here. Or maybe I'm giving them too much credit. Is there anything to this? What is it?

My guess is that they mean it's impossible to extract the private key without physically tampering with the crypto-dongle. It seems plausible that one could show that there simply is no physical channel for relaying the private key outside of the device. That complicates writing the key and I can't see how that could be solved. One way I could see is to not write the key verbatim but somehow allow it to be randomized, but I believe these devices actually allow writing the key.

Or maybe there's more substance to it than that. For all I know theses devices uses some exotic mechanism for storing bits that really can't be read directly without destroying the device.

I did find an answer here suggesting there is some real meat to this but it doesn't go into detail.

https://security.stackexchange.com/a/92796/45880

Extracting private keys directly from the card is nearly impossible. With some acid package destruction and electron microscope work, a skilled team, and enough time, money, and luck you can in theory extract keys but it involves not only physical access but a scenario where the card will be physically destroyed.

Community
  • 1
Praxeolitic
  • 603
  • 6
  • 11
  • The marketing text only means that there is no intended functionality that would allow to read the key from the stick, because it should never leave the stick. Physical storage of the key as well as physical channels for information input and output have to be available for the stick to be useful. As per the specs (implementation details, bugs and physical tampering aside) the stick should only output encrypted data, never the key. See also: [Write-Only Memory](https://en.wikipedia.org/wiki/Write-only_memory_(joke)) – Alexander Jul 08 '15 at 10:36
  • 3
    Are you sure *Write*-Only Memory was the wiki article you meant to link to? – Praxeolitic Jul 08 '15 at 10:56
  • 4
    @Alexander I really do think/hope they mean more than just "we do not provide software to extract the key". That would be egregiously misleading even for marketing material. – Praxeolitic Jul 08 '15 at 11:00
  • Looking at the [devel docs](https://developers.yubico.com/OTP/OTPs_Explained.html) it looks like the Yubi OTP is a plaintext message consisting of "some counters" which is encrypted with AES in an unspecified mode, with a fixed prefix the size of an AES block (the ID) and no initialization vector. OTPs are rejected if the decrypted plaintext counters are not greater than the ones seen before. To me, this sounds like it should be hard but quite possible to extract the key from the message (seeing how you only need to run a dictionary attack on the first block until a collision is found). – Damon Jul 09 '15 at 11:26

2 Answers2

48

Well "impossible" is impossible to prove which is why in the linked answer I said "almost impossible", maybe even that is overstating it. By using a secure hardware device the attack vector goes from "malware installed remotely on host steals secret," to "attacker needs to physically gain access to the hardware device and destructively remove the private key." The latter is certainly not impossible, but it is a lot more difficult.

Those usb dongles work very similar to smartcards. I have more experience with smartcards so I will use that in the answer but most of the same principles apply. In fact many of those usb dongles use a smart card SoC internally. They are cheap, programmable, and offer robust security so in many applications it makes sense to just use a smartcard internally rather than try to build something new.

A programmable smartcard is a complete computer in a single chip, or system on a chip (SoC). Now it is a very limited computer but still a computer. The connection to the "outside world" for the smartcard is a low privilege simple serial interface. The card gets a command (more like a request) from the host and the card responds with a response. The commands are limited to what the card has been programmed to do.

So if we have a smart card programmed to digitally sign an instruction (like a payment request in credit card EMV), the host will send a request over the serial interface to the card consisting of a command and some inputs. The card parsed the command and assuming it is valid it sends back a digital signature to the host over the same interface. In many ways it resembles a client-server relationship with the smartcard being the server and the host system being the client. The private key never leaves the card during the process. It is just request in, response out. The host has no mechanism to force the smartcard to return the private key or do anything it wasn't programmed to do. Of course this assumes there is no "please give me all the private keys" command which would obviously be pointless and provide no security. The smartcard may have a user assigned PIN and the PIN is part of the command format. The smartcard verifies the PIN and if it is invalid will reject the command. It has its own internal memory so it may record internally the number of invalid attempts and be programmed to shutdown (or in extreme cases erase the card).

The programming (flashing) of a smartcard is done prior to shipping. Of course if an attacker could just reprogram the smartcard to run a "give me all your keys" program it wouldn't be secure so most cards employ some sort of security bit in write once memory. So the card is programmed and the write bit set. The card will then reject any future attempts to reprogram.

Try not to get hung up on a smartcard doing exactly this. They are programmable devices so they will vary in implementation but the general concept is you have this self contained computer with its own internal secure storage which has been programmed to respond to requests from a host over a simple low permission interface. I do agree the word "impossible" is marketing but it isn't that far from the truth. You could say practically impossible. The very basic design and locked functionality means you end up with a hardened device that is difficult to attack.

However the old axiom "there is no information security without physical security" still applies. The private key is still physically in the smartcard. With physical access and enough motivation you can do pretty much "unsecret" any secret. As in the linked example the smartcard can be bypassed and the key read out directly off the physical memory. A common method is to take the card, remove the SoC and use acid deconstruction to burn away package. Using an electron microscope and enough skill you could locate the spot on the silicon which stores the keys, connect leads and read them out. It has been done so it definitely is not impossible but in most cases that isn't the type of attack or attacker we are trying to defend against. Honestly if your attacker would go to that level I would be more worried about a $5 wrench.

Angew is no longer proud of SO
  • 374
  • 1
  • 4
  • 10
Gerald Davis
  • 2,250
  • 16
  • 17
  • 4
    Some devices go so far as to protect the contents physically. For example, even the TPM installed in some motherboards will physically self-destruct the very moment the innards are exposed (possibly by oxidation, but I'm not an expert). There are devices where it is effectively impossible to ever retrieve the key without extreme cost, such as requiring microscopic tweezers operated in a vacuum or some such. – phyrfox Jul 08 '15 at 15:39
  • I think a quote should be in "keys command" rather than at the end of that sentence. ​ I also think "up on a" should be replaced with "up on how a". ​ ​ ​ ​ –  Jul 08 '15 at 16:34
  • 1
    What's to stop an attacker from keylogging your PIN and generating a request for himself using the breached host PC? Are there additional methods in place that prevent this? It's still impossible to retrieve the private key for the attacker, but it's possible for the attacker to use it, right? – mucaho Jul 08 '15 at 17:06
  • 1
    @mucaho The Yubikey needs to be physically touched (at least for the OTP authentication method) which the smart card can independently verify. – Praxeolitic Jul 08 '15 at 17:26
  • I think this answer is well-reasoned and balanced without the usual bias against marketing from CS/infosec people. I also think the distinction between (theoretically, and "pretty" easily even in practice) requiring *physical access* warrants "impossible" as a valid adjective here. Additionally, I also think the iPhone encrypted firmware/onboard private key analogous system should go on the record under this question as well! – lol Jul 10 '15 at 06:35
  • 1
    @mucaho the PIN cannot be programmatically sent to the card (API does not allow) – Michael Chourdakis Sep 25 '18 at 13:51
24

Hardware crypto modules like this are regulated by a set of standards called FIPS 140-2 which specify the ridiculous lengths that the devices must go to in order to protect the private keys inside them.

There are four levels of FIPS 140-2, briefly summarized as:

Level 1: It does basic crypto-y things.

Level 2: "Tamper-evident"; it's impossible to extract or modify the private keys without damaging the device in an evident way (ex.: breaking a seal, re-soldering the pins, etc).

Level 3: These devices should have a "high probability of detecting physical access" and they usually zero-out the keys if tampering is detected - think server racks with sensors on the access panels. Or in the case of cool new DARPA research, circuits that dissolve when exposed to air and humidity.

Level 4: Strengthens the requirements for tamper detection and key zeroization. Must also be highly resistant to attacks which use extreme temperature and extreme voltage.

So when you say

Still, it's an interesting claim. The choice of words -- "never", "always", "impossible" -- suggest that there is something that can be proven here.

I'm guessing that they mean "proven" relative to the FIPS 140-2 standards. And in fact, clicking through the links you provided, both those devices are certified to FIPS 140-2 Level 2.

Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
  • Fips 140-2 level 2 is a rather low bar to clear even if certification actually meant somone checked the hardware. As is, being certified to any Fips level is mostly annoying paperwork which guarantees little. I've had the dubious honor of working with Fips 140-2 level 4 certified hardware for which the certified firmware had multiple crippling bugs which made it unfit for any purpose. One of them was that cryptographic keys inside the device could not be wrapped for export with split knowledge keys and thus backups were impossible (not so good for a CA hsm). – DRF Jul 09 '15 at 07:29
  • 1
    @DRF Agreed; FIPS 140-2 (and worse: Common Criteria) is **not** a Quality Assurance test, you still have to trust that the company does it's QA properly. It's like a car: just because it passed Safety does not guarantee that you want to drive it. – Mike Ounsworth Jul 09 '15 at 11:27
  • 1
    @DRF: Huh? If it were possible to back up the private key, wouldn't that defeat the entire purpose of a hardware crypto module? – David Cary Jul 09 '15 at 16:50
  • 1
    @davidcary Nope. In general it's not particularly useful to have a public CA, where if a piece of hardware dies you're scr**ed. The usual approach is to first generate a symmetric key in the HSM then encrypt the privae key by the symmetric key in he HSM, then export the encrypted private key, then split the symmetric key using Shamir's secret sharing into n shares any k of which allow reconstruction. Preferably this is also done in the HSM but might be done outside if HSM hasn't got the scheme implemented. You export those parts onto smart cards(continued) – DRF Jul 09 '15 at 19:23
  • 1
    @DavidCary each smart card has a different keeper and all of which are usually deposited in different bank vaults (vaults of different banks). That way when invariably the HSM fails you have a DRP in place. – DRF Jul 09 '15 at 19:27