Elliptic Curve Cryptography in Practice

This week, in our study group, Dan P. looked at the paper "Elliptic Curve Cryptography in Practice". This paper tries to do for elliptic curve based cryptography what the following papers did for factoring based cryptography:

• Ron was wrong, Whit is right
• Mining your Ps and Qs
• Coppersmith in the wild    

All three of these papers managed to extract RSA private keys from a large corpus of published RSA public keys. The essential trick being that poor random number generation leads to RSA public keys which have a high probability of sharing a prime factor with another RSA public key. This is particularly a problem for low end devices which generate their own keys on start-up, when there is little available entropy to seed the random number generator.

The current paper aims to study how ECC is really used in the wild, and examine similar issues. As the first task the authors captured real world data. This was from four different applications.

• Bitcoin: Here the signing algorithm used to transfer bitcoins from one wallet to another is the ECDSA algorithm. Obtaining the full set of public keys for bitcoin, and the full set of issued digital signatures, is easy. All one needs to do is download the blockchain!
• TLS: ECC can be used in one of two places. Either via ECDH to derive the pre-master secret and/or using ECDSA to sign the Diffie-Hellman handshake. To obtain the data on TLS the authors scanned the internet to examine all IPv4 web addresses and see whether they answered a TLS handshake request, and with what.
• SSH: SSH is much like TLS, except the handshake algorithm is a lot simpler. Again one can use ECC in one of two ways; either to derive keys and/or to provide authentication.
• Austrian Citizen Card: The Austrian e-ID card can use ECDSA for signing; and all public keys are available via an LDAP database.

In terms of what the authors found, the deployment of ECC seemed quite sparse. For TLS, the most important protocol, only 1 in 10 servers supported ECC. Of these 98% supported curves of 256 bits, whereas 80 (resp. 70) percent supported curves of 384 (resp. 521) bits. Why servers would not support all bit sizes sparked some discussion in our group. But we could come up with no really rational reason.

An interesting aside would be to reconduct the experiment. Since the Snowden revelations last year many companies have moved to "forward secure" variants of TLS. Almost all forward secure variants of TLS require the use of ECC enabled Diffie-Hellman key agreement. Thus one would expect (hope maybe?) that the number of servers supporting ECC would now be larger than 10%.

Then the authors went on to examine possible weak failure points of implementations of ECDSA; similar to the weak entropy for RSA key generation mentioned at the start. There were a tiny number of  anomalies in Bitcoin transactions: 

• For 158 wallets (out of 47 million) one could recover the private key from the public signing data. Again this was due to poor random number generation.
•  A number of wallet addresses cannot (within reason) correspond to valid private keys (unless the Bitcoin hash function can be easily inverted). The authors reckon 75 BTC have been lost in this way.

The conclusions re the investigation for the other three cases studies revealed virtually no surprising results. So the study group closed for the week.

 

Life's not fair? Bitcoin can help.

Last week, Marcel presented a study group on secure computation using bitcoin. In a secure multi-party computation (MPC) protocol, several players interact to compute a function of their inputs, without revealing the inputs to each other. These days MPC is a huge area of research in cryptography and there always tends to be several interesting papers at the big conferences.

One fundamental issue that is often overlooked in MPC is fairness. A protocol is said to be fair if it is impossible for a malicious player to abort the protocol early and learn the result of the computation, before the other players have managed to do so. In general this is impossible to achieve, as the first player to learn the result can usually just abort instead of passing this on to the other players [1]. However, using the power of the bitcoin network, fairness can be enforced for any function.

Bitcoin transactions

 

A transaction in the blockchain typically contains: [2]
- value
- previous transaction ID
- in-script: outputs signature on current transaction
- out-script: verifies signature from next transaction's in-script
- (timelock)

The value and previous transaction ID are self-explanatory; the two scripts provide the key functionality. For a normal bitcoin transaction, the in-script outputs a signature on the current transaction, and the out-script is used to verify the signature from the in-script of the next transaction using the appropriate public key.

The key point is that the in-script and out-script are not just a signature and a public key. They are pieces of code written in a (very simple) scripting language [3], so can actually be used to do something entirely different!

The final, optional item in a transaction is a timelock: this can be used to indicate a time, before which the transaction may not be added to the ledger.

Timed Commitment

 

A fundamental building block for fair secure computation using bitcoin  transactions is timed commitment, which functions as a normal cryptographic commitment, except the committer must pay a penalty if they do not open it within a set time period. The Committer, C, sends a standard commitment to the receiver, R, and posts an initial commitment transaction to the blockchain:

Commit
in-script: (output signature as normal)
out-script: check sigC AND (opening OR sigR)

Here the out-script verifies that the next transaction was signed by C (the  committer), and also that the next transaction either contains the required  decommitment information, opening, or was signed by R (the receiver). This  means that either of the following two transactions may be added to Commit in the blockchain:

Open
in: sigC, opening
out: C

Fuse
in: sigC, sigR
out: R
timelock

The Fuse transaction must be created (and signed by both parties) at the start and given to the Receiver. Once Commit has been posted, the Commiter must post the Open transaction, with the relevant decommitment information, before the timelock expires, at which point the receiver can post Fuse to gain their reward if Open hasn't been added.

Fair MPC using Mutual Commitment

 

Similarly to the timed commitment protocol above, a *mutual commitment*  between any number of parties can be created. Here every party must commit to something, and is penalised if they do not decommit within the time period. Adapting this to MPC is quite straightforward. At the end of a typical MPC protocol, every party will hold a *share* of the result, which must be revealed so that everyone can reconstruct the result. Mutual commitment guarantees that everyone will reveal their share, or pay the penalty.

Clearly using bitcoin doesn't quite guarantee fairness in the traditional sense; it is still possible for a player to abort, just at a high monetary cost. But in a model with rational adversaries, if the penalty is set appropriately then this seems a reasonable solution.

Further reading:

The first paper we discussed, on timed commitment and secure lotteries without a trusted third party.

The second paper, on fairness in two-party computation.

Another recent paper on fairness and MPC.

[1] See Enrique's blog post for details of a nice, recent work that characterizes situations where fairness is possible.

[2] This is probably not entirely accurate, I recommend the bitcoin wiki for a more thorough description.

[3] The Script language is a simple stack machine, deliberately not Turing-Complete so that non-terminating scripts can be detected easily.

Who are you to access this?

Today's study group was given by Bin on the paper "Enforcing Confinement in Distributed Storage and a Cryptographic Model for Access Control" by Halevi et al. It deals with the T10 OSD protocol, which provides access control in a network storage setting. The contributions of the paper are two-fold: First, the authors propose binding access credentials to clients, which prevents clients from passing on credentials to other clients of the system. Second, they formalize access control in the model of universal composability and proof the security of the amended protocol therein.

The protocol involves four parties: a client, a security manager, a policy manager, and a storage server. It is required that the storage server and the security manager share a secret key. If the client wants to access an object on the storage server, it sends a request to the security manager, which in turn request a capability from the policy manager. If the request is accepted, the latter returns a capability, which is then included in the credential sent from the security manager the client. The client then uses the credential to access the desired object on the storage server. Finally, the security manager can also revoke credentials by communication directly with the storage server.

There are four security modes requiring increasing level of checks from the storage server: NoSec, CAPKEY, CMDRSD, ALLDATA. The talk was only concerned with CAPKEY. In this mode, the storage server checks the expiry time included in the capability as well as the so-called VTag. This is a MAC on a security token (a random number for every client-server pair) using a key that is derived by a PRF on the capability using the secret key shared by the security and the storage server. This authenticates the credential. However, this does not bind the credential a particular client. The authors therefore suggest to include a tag derived by PRF on the client ID using the same secret key.

To prove the security of the resulting protocol, the authors propose an ideal functionality keeping tracks of all credential issued and revoked, and they provide a simulator in the hybrid model assuming secure channels and a common reference string.