Second-guessing Satoshi: ECDSA and Bitcoin (part I)

“Cold-wallets can be attacked.” Behind that excited headline turns out to be a case of superficial journalism and missing the real story. Referring back to the original paper covered in the article, the attack is premised on a cold-wallet implementation that has been already subverted by an attacker. Now that may sound tautological: “if your wallet has been compromised, then it can be compromised.” But there is a subtlety the authors are careful to point out: offline Bitcoin storage is supposed to be truly incommunicado. Even if an attacker has managed to get full control and execute arbitrary code- perhaps by corrupting the system ahead of time, before it was placed into service- there is still no way for that malicious software to communicate with the outside world and disclose sensitive information. Here we give designers the benefit of the doubt, assuming they have taken steps to physically disable/remove networking hardware and place the device in a Faraday cage at the bottom of a missile silo. Such counter-measures foreclose the obvious communication channels to the outside world. The attacker may have full control of the wallet system, including knowledge of the cryptographic keys associated with Bitcoin funds, but how does she exfiltrate those keys?

There is always the possibility of covert channels, ways of communicating information in a stealth way. For example the time taken for a system to respond could be a hidden signal: operate quickly to signal 0, introduce artificial delays to communicate 1. But such side-channels are not readily available here either; the workings of offline Bitcoin storage are not directly observable to attackers in the typical threat model. Only the legitimate owners have direct physical access to the system. Our attacker sits some place on the other side of the world, while those authorized users walk in to generate signed transactions.

But there is one piece of information that must be communicated out of that offline wallet and inevitably become visible to everyone— the digital signature on Bitcoin transactions signed by that wallet. Because transactions are broadcast to the network, those signatures are public knowledge. Within those signatures is an easy covert channel. Credit goes to ECDSA, the digital-signature algorithm chosen by Satoshi for the Bitcoin protocol. ECDSA is a probabilistic  algorithm. For any given message, there is a large number of signatures that would be considered “valid” according to the verification algorithm; in fact for the specific elliptic-curve used by Bitcoin, an extraordinarily large number in the same ballpark as estimated number of particles in the observable universe. An “honest” implementation of ECDSA is expected to choose a nonce at random and construct the signature based on that random choice. But that same freedom offers a malicious ECDSA implementation to covertly send messages by carefully “cooking” the nonce to produce a specific pattern in the final signature output. For example successive key-bits can be leaked by choosing the signature to have same parity as the bit being exfiltrated.

But the channel present within ECDSA is far more sophisticated. Building on the work of Moti Yung and Adam Young, it is an example of a kleptographic system. It is efficient: two back-to-back signatures are sufficient to output the entire key. It is also deniable: without the additional secret value injected by the attacker, it is not possible for other observers with access to same outputs—recall that everyone gets to see transactions posted on the blockchain— to pull-off that key-recovery feat. That includes the legitimate owner of the wallet. To everyone else these signatures looks indistinguishable from those output by an “honest” cold-storage implementation.

There is a notion of deterministic ECDSA where nonces are generated as a function of the message, instead of chosen randomly. This variant was designed to solve a slightly different problem, namely that each ECDSA signature requires a fresh unpredictable nonce. Reusing one from a different message or even generating a partially predictable nonce leads to private-key recovery. While this looks like a promising way to close the covert channel, the problem is there is no way for an outside observer to verify that the signature was generated deterministically. (Recall that we posit attacker has introduced malware subverting the operation of the cold-storage system, including its cryptographic implementation.) Checking that a signature was generated deterministically requires knowing the private key- which defeats the point of only entrusting private keys to the cold-storage itself.

This same problem also applies to other black-box implementations of ECDSA where the underlying system is not even open to inspection, namely special-purpose cryptographic hardware such as smart-cards and hardware security modules (HSM.) An HSM manufacturer could use a similar kleptographic technique to disclose keys in a way that only that manufacturer can recover. In all other aspects, including statistical randomness tests run against those nonces, the system is indistinguishable from a properly functioning device.

[continued- countermeasures]


Smart-card logon for OS X (part IV)

[continued from part III]

Smart-card elevation

In addition to the login screen and screen-saver, elevation prompts for sensitive operations will also work with smart-cards:

Elevation prompt asking for PINAs before, the dialog can adjust for credential type in real-time. On detecting presence of a smart-card (more precisely, a card for which an appropriate tokend module exists and contains valid credentials) the dialog will change in two subtle ways:

  • Username field is hard-coded to the account mapped from the certificate on the card, and this entry is grayed out to prevent edits
  • Password field is replaced by PIN

If the card is removed before PIN entry is completed, UI reverts back to the original username/password collection model.

One might expect that elevation in command line with “sudo” would similarly pick up the presence of smart-card but that is not the case. su and sudo still require a password. One heavy-weight solution involves installing the PKCS#11 PAM (pluggable authentication module) since OS X does support the PAM extensibility mechanism. A simpler work-around is to substitute an osascript wrapper for sudo. This wrapper can invoke the GUI credential collection which is already smart-card aware:

sudo replacement with PIN collection(Downside is that the elevation request is attributed to osascript, instead of the specific binary to be executed with root privileges. But presumably the user who typed out the command knows the intended target.)


Before discussing the trust-model and comparing it to Windows implementation, here is a quick overview of steps to enable smart-card logon with OS X:

  • Install tokend modules for the specific type of card you plan to use. For the US government PIV standard, OpenSC project installer contains one out of the box.
  • Enable smart-card login using the security command to modify authorization database.
    $ sudo security authorizationdb smartcard enable
    YES (0)
    $ sudo security authorizationdb smartcard status
    Current smartcard login state: enabled (system.login.console enabled, authentication rule enabled)
    YES (0)

    (Side-note: prior to Mavericks the authorization “database” was a plain text-file at /etc/authorization and it could be edited manually with a text editor— this is why some early OSX smart-card tutorials suggest tinkering with the file directly. In Mavericks it is a true SQLite database and best manipulated with the security utility.)

  • Associate one or more certificate mappings to the local account, using sc_auth command.

Primitive trust-model

Because certificate hashes are tied to a public-key, this mapping does not survive the reissuance of the certificate under a different key. That defeats the point of using PKI in the first place. OSX is effectively using X509 as a glorified public-key container, no different from SSH in the trusting specific keys rather than the generalized concept of an identity (“subject”) whose key at any given time is vouched for by a third-party. Contrast that with how Active Directory does certificate mapping, adding a level of indirection by using fields in the certificate. If the certificate expires or the user loses their token, they can be issued a new certificate from the same CA. Because the replacement has the same subject and/or same UPN, it provides continuity of identity: different certificate, same user. There is no need to let every endpoint know that a new certificate has been issued for that user.

A series of future posts will look at how the same problem is solved on Linux using a PAM tailored for digital certificates. Concrete implementations such as PAM PKCS#11 have same two-stage design: verify ownership of private key corresponding to a certificate, followed by mapping the certificate to local account. Its main differentiating factor is the choice of sophisticated mapping schemes.  These can accommodate everything from the primitive single-certificate approach in OSX to the Windows design that relies on UPN/email, and other alternatives that build on existing Linux trust structures such as ssh authorized keys.


Smart-card logon for OS X (part III)

[continued from part II]

Managing the mapping for smart-card logon

OS X supports two options for mapping a certificate to a local user account:

  • Perform look-up in enterprise directory
  • Decide based on hash of the public-key in the certificate

For local login on stand-alone computers without Active Directory or equivalent, only the second, very basic option is available. As described by several sources [Feitian, PIV focused guides, blog posts], sc_auth command in OS X— which is just a Bash script— is used to manage that mapping via various sub-commands. sc_auth hash purports to display keys on currently present smart-cards, but in fact outputs a kitchen sink of certificates including those coming from the local keychain. It can be scoped to  specific key by passing an identifier. For example to get PIV authentication key out of a PIV card when using OpenSC tokend modules:

$ sc_auth hash -k "PIV"
67081F01CB1AAA07EF2B19648D0FD5A89F5FAFB8 PIV AUTH key

The displayed value is a SHA1 hash derived from the public-key. (Keep in mind that key names such “PIV AUTH key” above are manufactured by the tokend middleware; your mileage may vary when using different one.)

To convince OS X into accepting that certificate for local logon, sc_auth accept must be invoked with root privileges.

$ sudo sc_auth accept -u Alice -k "PIV"

This instructs the system to accept the PIV certificate on presently connected smart-card for authenticating local user Alice.  There is another option to specify the key using its hash:

$ sudo sc_auth accept -u Alice -h 67081F01CB1AAA07EF2B19648D0FD5A89F5FAFB8

More than one certificate can be mapped to a single account by repeating that process. sc_auth list will display all currently trusted public-key hashes for a specified user:

$ sc_auth list -u Alice

Finally sc_auth remove deletes all certificates currently mapped to a local user account:

$ sudo sc_auth remove -u Alice

Smart-card user experience on OS X

So what does the user experience look like once the mapping is configured?

Initial login

First the bad news: don’t throw away your password just yet. The boot/reboot process remains unchanged. FileVault II full-disk encryption still requires typing in the password to unlock the disk.** Interestingly, its predecessor the original FileVault did support smart-cards because it was decrypting a container in the file-system after enough of the OS had been loaded to support tokend. New variant operates at a much lower level. Because OS X does not ask for the password a second time after the FileVault prompt, there is no opportunity to use smart-card in this scenario.

Good news is that subsequent authentication and screen unlocking can be done using a smart-card. The system recognizes the presence of a card and modifies its UI to switch authentication mode on the fly. For example, here is what the Yosemite login screen usually looks like after signing out:**

Standard login screen

Standard login screen

After a card is connected to the system, the UI updates automatically:

OS X login UI after detecting card presence

OS X login UI after detecting card presence

Local account mapped to the certificate from the card is chosen, and any other  avatars that may have been present disappear from the UI. More subtly the password prompt changes into a PIN prompt. After entering the correct PIN, the system will communicate with the card to verify its possession of the private-key and continue with login as before.

Caveat emptor

  • On failed PIN entry, the system does not display the number of remaining tries left before the card is locked. It is common for card standards to return this information as part of the error; PIV specification specifically mandates that. Windows will display the count after incorrect attempts as a gentle nudge to be careful with next try; a locked card typically requires costly intervention by enterprise IT.
  • After logging in, it is not uncommon to see another prompt coming from the keychain, lest the user is lulled to a false sense of freedom from passwords:
    Screen Shot 2015-02-08 at 20.17.11 Keychain entries previously protected by the password still need to be unlocked using the same credential. If authentication took place using a smart-card, that password is not available after login. So the first application trying to retrieve something out of the key-chain will trigger on-demand collection. (As the dialog from Messages Agent demonstrates, that does not take very long.)

Screen unlock

Unlocking the screen works in a similar fashion, reacting to the presence of a card. Here is example UI when coming out of screen-saver that requires password:

Screen-saver prompting for password

Screen-saver prompting for password

After detecting card presence:

Screen-saver prompting for card PIN

Screen-saver prompting for card PIN

This is arguably the main usability improvement to using smart-cards. Instead of typing a complex passphrase to bring the system out of sleep or unlock after  walking away (responsible individuals lock their screen before leaving their computer unattended, one would hope) one need only type in a short numeric PIN.



* In other words OS X places the burden of security on users to choose a random pass-phrase, instead of offloading that problem to specialized hardware. Similarly Apple has never managed to leverage TPMs for disk encryption, despite a half-hearted attempt circa 2006, keeping with the company tradition of failing to grok enterprise technologies.
** MacWorld has a helpful guide for capturing these screenshots, which involve SSH from another machine.