Using ECDH on Android

Elliptic curve cryptography (ECC) offers equivalent or higher levels of security than the currently widely deployed RSA and Diffie–Hellman (DH) algorithms using much shorter keys. For example, the computational effort  for cryptanalysis of a 160-bit ECC key is roughly equivalent to that of a 1024-bit key (NIST). The shift to ECC has however been fairly slow, mostly due to the added complexity, the need for standardization, and of course, patents. Standards are now available (more than a few, of course) and efficient implementations in both software and dedicated hardware have been developed. This,  along with the constant need for higher security, is pushing the wider adoption of ECC. Let's see if, and how we can use ECC on Android, specifically to perform key exchange using the ECDH (Elliptic Curve Diffie-Hellman) algorithm.

Android uses the Bouncy Castle Java libraries to implement some of its cryptographic functionality. It acts as the default JCE crypto provider, accessible through the java.security and related JCA API's. Bouncy Castle has supported EC for quite some time, and the most recent Android release, 4.0 (Ice Cream Sandwich, ICS), is based on the latest Bouncy Castle version (1.46), so this should be easy, right? Android, however, does not include the full Bouncy Castle library (some algorithms are omitted, presumably to save space), and the bundled version has some Android-specific modifications. Let's see what EC-related algorithms are supported on Android (output is from ICS, version 4.0.1):

BC/BouncyCastle Security Provider v1.46/1.460000
  KeyAgreement/ECDH
  KeyFactory/EC
  KeyPairGenerator/EC
  Signature/ECDSA
  Signature/NONEwithECDSA
  Signature/SHA256WITHECDSA
  Signature/SHA384WITHECDSA
  Signature/SHA512WITHECDSA

As seen above, it does support EC key generation, ECDH key exchange and ECDSA signatures. That is sufficient to generate EC keys and preform the exchange on the newest Android version, but as it turns out, currently more than 85% of devices are using 2.2 or 2.3. Android 4.0 doesn't even show up in the platform distribution graph. Let's check what is supported on a more mainstream version, such as 2.3 (Gingerbread). The output below is from stock 2.3.6:

BC/BouncyCastle Security Provider v1.45/1.450000

Which is exactly nothing: the JCE provider in Gingerbread is missing all EC-related mechanisms. The solution is, of course, to bundle the full Bouncy Castle library with our app, so that we have all algorithms available. It turns out that it is not that simple, though. Android preloads the framework libraries, including Bouncy Castle, and as a result, if you include the stock library in your project, it won't be properly loaded (you will most likely get a ClassCastException). This appears to have been fixed in 3.0 (Honeycomb) and later versions (they have changed the provider's package name), but not in our target platform (2.3). There are two main solutions to this:

• use jarjar to rename the Bouncy Castle library package name we bundle
• use the Spongy Castle library that already does this for us

We'll take the second option, because it's less work and the name sounds funny :) Using the library is pretty straightforward, but do check the Eclipse-specific instructions if you get stuck. Now that we have it set up, let's initialize the provider and see what algorithms it gives us. 

// add the provider
{
    Security.addProvider(new org.spongycastle.jce.provider.BouncyCastleProvider());
}

SC/BouncyCastle Security Provider v1.46/1.460000
   AlgorithmParameters/SHA1WITHECDSA
   ...
   Cipher/BrokenECIES
   Cipher/ECIES
   KeyAgreement/ECDH
   KeyAgreement/ECDHC
   KeyAgreement/ECMQV
   KeyFactory/EC
   KeyFactory/ECDH
   KeyFactory/ECDHC
   KeyFactory/ECDSA
   KeyFactory/ECGOST3410
   KeyFactory/ECMQV
   KeyPairGenerator/EC
   KeyPairGenerator/ECDH
   KeyPairGenerator/ECDHC
   KeyPairGenerator/ECDSA
   KeyPairGenerator/ECGOST3410
   KeyPairGenerator/ECIES
   KeyPairGenerator/ECMQV
   Mac/DESEDECMAC
   Signature/ECDSA
   Signature/ECGOST3410
   Signature/NONEwithECDSA
   Signature/RIPEMD160WITHECDSA
   Signature/SHA1WITHCVC-ECDSA
   ...

This is much, much better. As you have probably noticed, the provider name has also been changed from 'BC' to 'SC' in order not to clash with the platform default. We will use 'SC' in our code, to ensure we are calling the correct crypto provider.

Now that we have a working configuration, let's move on to the actual implementation. JCE makes DH key exchange pretty straightforward: you just need to initialize the KeyAgreement class with the current party's (Alice!) private key, pass the other party's public key (who else but Bob), and call generateSecret() to get the shared secret bytes. To make things a little bit more interesting, we'll try to stimulate a (fairly) realistic example where we use pre-generated keys serialized in the PKCS#8 (for the private key) and X.509 (for the public) formats. We'll also show two ways of initializing the EC crypto system: by using a standard named EC curve, and by initializing the curve using discrete EC domain parameters.

To generate EC keys we need to first specify the required EC domain parameters:

• an elliptic curve, defined by an elliptic field and the coefficients a and b, 
• the generator (base point) G and its order n, 
• and the cofactor h.

Assuming we have the parameters (we use the recommended values from SEC 2) in an instance of a class ECParams called ecp (see sample code) the required code looks like this:

ECFieldFp fp = new ECFieldFp(ecp.getP());
EllipticCurve ec = EllipticCurve(fp, ecp.getA(), ecp.getB());
ECParameterSpec esSpec = new ECParameterSpec(curve, ecp.getG(),
                ecp.getN(), ecp.h);
KeyPairGenerator kpg = KeyPairGenerator.getInstance("ECDH", "SC");
kpg.initialize(esSpec);

Of course, since we are using standard curves, we can make this much shorter:

ECGenParameterSpec ecParamSpec = new ECGenParameterSpec("secp224k1");
KeyPairGenerator kpg = KeyPairGenerator.getInstance("ECDH", "SC");
kpg.initialize(ecParamSpec);

Next, we generate Alice's and Bob's key pairs, and save them as Base64 encoded strings in the app's shared preferences (we show only Alice's part, Bob's is identical):

KeyPair kpA = kpg.generateKeyPair();

String pubStr = Crypto.base64Encode(kpA.getPublic().getEncoded());
String privStr = Crypto.base64Encode(kpA.getPrivate().getEncoded());

SharedPreferences.Editor prefsEditor = PreferenceManager
                .getDefaultSharedPreferences(this).edit();

prefsEditor.putString("kpA_public", pubStr);
prefsEditor.putString("kpA_private", privStr);
prefsEditor.commit();

If we save the keys as files on external storage as well, it's easy to check the key format using OpenSSL:

$ openssl asn1parse -inform DER -in kpA_public.der
cons: SEQUENCE          
cons: SEQUENCE          
prim: OBJECT            :id-ecPublicKey
cons: SEQUENCE          
prim: INTEGER           :01
cons: SEQUENCE          
prim: OBJECT            :prime-field
prim: INTEGER           :FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC73
cons: SEQUENCE          
prim: OCTET STRING      [HEX DUMP]:0000000000000000000000000000000000000000
prim: OCTET STRING      [HEX DUMP]:0000000000000000000000000000000000000007
prim: OCTET STRING      [HEX DUMP]:043B4C382CE37AA192A4019E763036F4F5DD4...
prim: INTEGER           :0100000000000000000001B8FA16DFAB9ACA16B6B3
prim: INTEGER           :01
prim: BIT STRING         

We see that it contains the EC domain parameters (G is in uncompressed form) and the public key itself as a bit string. The private key file contains the public key plus the private key as an octet string (not shown).

Now that we have the two sets of keys, let's perform the actual key exchange. First we read the keys from storage, and use a KeyFactory to decode them (only Alice's part is shown):

SharedPreferences prefs = PreferenceManager
                .getDefaultSharedPreferences(this);
String pubKeyStr = prefs.getString("kpA_public", null);
String privKeyStr = prefs.getString("kpB_private", null);

KeyFactory kf = KeyFactory.getInstance("ECDH", "SC");

X509EncodedKeySpec x509ks = new X509EncodedKeySpec(
                Base64.decode(pubKeyStr));
PublicKey pubKeyA = kf.generatePublic(x509ks);

PKCS8EncodedKeySpec p8ks = new PKCS8EncodedKeySpec(
                Base64.decode(privKeyStr));
PrivateKey privKeyA = kf.generatePrivate(p8ks);

After all that work, the actual key exchange is pretty easy (again, only Alice's part):

KeyAgreement aKA = KeyAgreement.getInstance("ECDH", "SC");
aKeyAgreement.init(privKeyA);
aKeyAgreement.doPhase(pubKeyB, true);

byte[] sharedKeyA = aKA.generateSecret();

Finally, the all important screenshot:

As you can see, Alice's and Bob's shared keys are the same, so we can conclude the key agreement is successful. Of course, for a practically useful cryptographic protocol that is only part of the story: they would need to generate a session key based on the shared secret and use it to encrypt communications. It's not too hard to come up with one, but inventing a secure protocol is not a trivial task, so the usual advice applies: use TLS or another standard protocol that already supports ECC.

To sum things up: you can easily implement ECDH using the standard JCE interfaces available in Android. However, older version (2.x) don't include the necessary ECC implementation classes in the default JCE provider (based on Bouncy Castle). To add support for ECC, you need to bundle a JCE provider that does and is usable on Android (i.e., doesn't depend on JDK classes not available in Android and doesn't clash with the default provider), such as Spongy Castle. Of course, another way is to use a lightweight API not based on JCE. For this particular scenario, Bouncy/Spongy Castle provides ECDHBasicAgreement.

That concludes our discussion of ECDH on Android. As usual, the full source code of the example app is available on Github for your hacking pleasure.