1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mobile/android/base/sync/jpake/JPakeCrypto.java Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,264 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +package org.mozilla.gecko.sync.jpake;
1.9 +
1.10 +import java.io.UnsupportedEncodingException;
1.11 +import java.math.BigInteger;
1.12 +import java.security.GeneralSecurityException;
1.13 +import java.security.InvalidKeyException;
1.14 +import java.security.MessageDigest;
1.15 +import java.security.NoSuchAlgorithmException;
1.16 +
1.17 +import javax.crypto.Mac;
1.18 +import javax.crypto.spec.SecretKeySpec;
1.19 +
1.20 +import org.mozilla.gecko.background.common.log.Logger;
1.21 +import org.mozilla.gecko.sync.crypto.HKDF;
1.22 +import org.mozilla.gecko.sync.crypto.KeyBundle;
1.23 +
1.24 +public class JPakeCrypto {
1.25 + private static final String LOG_TAG = "JPakeCrypto";
1.26 +
1.27 + /*
1.28 + * Primes P and Q, and generator G - from original Mozilla J-PAKE
1.29 + * implementation.
1.30 + */
1.31 + public static final BigInteger P = new BigInteger(
1.32 + "90066455B5CFC38F9CAA4A48B4281F292C260FEEF01FD61037E56258A7795A1C" +
1.33 + "7AD46076982CE6BB956936C6AB4DCFE05E6784586940CA544B9B2140E1EB523F" +
1.34 + "009D20A7E7880E4E5BFA690F1B9004A27811CD9904AF70420EEFD6EA11EF7DA1" +
1.35 + "29F58835FF56B89FAA637BC9AC2EFAAB903402229F491D8D3485261CD068699B" +
1.36 + "6BA58A1DDBBEF6DB51E8FE34E8A78E542D7BA351C21EA8D8F1D29F5D5D159394" +
1.37 + "87E27F4416B0CA632C59EFD1B1EB66511A5A0FBF615B766C5862D0BD8A3FE7A0" +
1.38 + "E0DA0FB2FE1FCB19E8F9996A8EA0FCCDE538175238FC8B0EE6F29AF7F642773E" +
1.39 + "BE8CD5402415A01451A840476B2FCEB0E388D30D4B376C37FE401C2A2C2F941D" +
1.40 + "AD179C540C1C8CE030D460C4D983BE9AB0B20F69144C1AE13F9383EA1C08504F" +
1.41 + "B0BF321503EFE43488310DD8DC77EC5B8349B8BFE97C2C560EA878DE87C11E3D" +
1.42 + "597F1FEA742D73EEC7F37BE43949EF1A0D15C3F3E3FC0A8335617055AC91328E" +
1.43 + "C22B50FC15B941D3D1624CD88BC25F3E941FDDC6200689581BFEC416B4B2CB73",
1.44 + 16);
1.45 +
1.46 + public static final BigInteger Q = new BigInteger(
1.47 + "CFA0478A54717B08CE64805B76E5B14249A77A4838469DF7F7DC987EFCCFB11D",
1.48 + 16);
1.49 +
1.50 + public static final BigInteger G = new BigInteger(
1.51 + "5E5CBA992E0A680D885EB903AEA78E4A45A469103D448EDE3B7ACCC54D521E37" +
1.52 + "F84A4BDD5B06B0970CC2D2BBB715F7B82846F9A0C393914C792E6A923E2117AB" +
1.53 + "805276A975AADB5261D91673EA9AAFFEECBFA6183DFCB5D3B7332AA19275AFA1" +
1.54 + "F8EC0B60FB6F66CC23AE4870791D5982AAD1AA9485FD8F4A60126FEB2CF05DB8" +
1.55 + "A7F0F09B3397F3937F2E90B9E5B9C9B6EFEF642BC48351C46FB171B9BFA9EF17" +
1.56 + "A961CE96C7E7A7CC3D3D03DFAD1078BA21DA425198F07D2481622BCE45969D9C" +
1.57 + "4D6063D72AB7A0F08B2F49A7CC6AF335E08C4720E31476B67299E231F8BD90B3" +
1.58 + "9AC3AE3BE0C6B6CACEF8289A2E2873D58E51E029CAFBD55E6841489AB66B5B4B" +
1.59 + "9BA6E2F784660896AFF387D92844CCB8B69475496DE19DA2E58259B090489AC8" +
1.60 + "E62363CDF82CFD8EF2A427ABCD65750B506F56DDE3B988567A88126B914D7828" +
1.61 + "E2B63A6D7ED0747EC59E0E0A23CE7D8A74C1D2C2A7AFB6A29799620F00E11C33" +
1.62 + "787F7DED3B30E1A22D09F1FBDA1ABBBFBF25CAE05A13F812E34563F99410E73B",
1.63 + 16);
1.64 +
1.65 + /**
1.66 + *
1.67 + * Round 1 of J-PAKE protocol.
1.68 + * Generate x1, x2, and ZKP for other party.
1.69 + */
1.70 + public static void round1(JPakeParty jp, JPakeNumGenerator gen) throws NoSuchAlgorithmException, UnsupportedEncodingException {
1.71 + // Randomly select x1 from [0,q), x2 from [1,q).
1.72 + BigInteger x1 = gen.generateFromRange(Q); // [0, q)
1.73 + BigInteger x2 = jp.x2 = BigInteger.ONE.add(gen.generateFromRange(Q
1.74 + .subtract(BigInteger.ONE))); // [1, q)
1.75 +
1.76 + BigInteger gx1 = G.modPow(x1, P);
1.77 + BigInteger gx2 = G.modPow(x2, P);
1.78 +
1.79 + jp.gx1 = gx1;
1.80 + jp.gx2 = gx2;
1.81 +
1.82 + // Generate and store zero knowledge proofs.
1.83 + jp.zkp1 = createZkp(G, x1, gx1, jp.signerId, gen);
1.84 + jp.zkp2 = createZkp(G, x2, gx2, jp.signerId, gen);
1.85 + }
1.86 +
1.87 + /**
1.88 + * Round 2 of J-PAKE protocol.
1.89 + * Generate A and ZKP for A.
1.90 + * Verify ZKP from other party. Does not check for replay ZKP.
1.91 + */
1.92 + public static void round2(BigInteger secretValue, JPakeParty jp, JPakeNumGenerator gen)
1.93 + throws IncorrectZkpException, NoSuchAlgorithmException,
1.94 + Gx3OrGx4IsZeroOrOneException, UnsupportedEncodingException {
1.95 +
1.96 + Logger.debug(LOG_TAG, "round2 started.");
1.97 +
1.98 + // checkZkp does some additional checks, but we can throw a more informative exception here.
1.99 + if (BigInteger.ZERO.compareTo(jp.gx3) == 0 || BigInteger.ONE.compareTo(jp.gx3) == 0 ||
1.100 + BigInteger.ZERO.compareTo(jp.gx4) == 0 || BigInteger.ONE.compareTo(jp.gx4) == 0) {
1.101 + throw new Gx3OrGx4IsZeroOrOneException();
1.102 + }
1.103 +
1.104 + // Check ZKP.
1.105 + checkZkp(G, jp.gx3, jp.zkp3);
1.106 + checkZkp(G, jp.gx4, jp.zkp4);
1.107 +
1.108 + // Compute a = g^[(x1+x3+x4)*(x2*secret)].
1.109 + BigInteger y1 = jp.gx3.multiply(jp.gx4).mod(P).multiply(jp.gx1).mod(P);
1.110 + BigInteger y2 = jp.x2.multiply(secretValue).mod(P);
1.111 +
1.112 + BigInteger a = y1.modPow(y2, P);
1.113 + jp.thisZkpA = createZkp(y1, y2, a, jp.signerId, gen);
1.114 + jp.thisA = a;
1.115 +
1.116 + Logger.debug(LOG_TAG, "round2 finished.");
1.117 + }
1.118 +
1.119 + /**
1.120 + * Final round of J-PAKE protocol.
1.121 + */
1.122 + public static KeyBundle finalRound(BigInteger secretValue, JPakeParty jp)
1.123 + throws IncorrectZkpException, NoSuchAlgorithmException, InvalidKeyException, UnsupportedEncodingException {
1.124 + Logger.debug(LOG_TAG, "Final round started.");
1.125 + BigInteger gb = jp.gx1.multiply(jp.gx2).mod(P).multiply(jp.gx3)
1.126 + .mod(P);
1.127 + checkZkp(gb, jp.otherA, jp.otherZkpA);
1.128 +
1.129 + // Calculate shared key g^(x1+x3)*x2*x4*secret, which is equivalent to
1.130 + // (B/g^(x2*x4*s))^x2 = (B*(g^x4)^x2^s^-1)^2.
1.131 + BigInteger k = jp.gx4.modPow(jp.x2.multiply(secretValue).negate().mod(Q), P).multiply(jp.otherA)
1.132 + .modPow(jp.x2, P);
1.133 +
1.134 + byte[] enc = new byte[32];
1.135 + byte[] hmac = new byte[32];
1.136 + generateKeyAndHmac(k, enc, hmac);
1.137 +
1.138 + Logger.debug(LOG_TAG, "Final round finished; returning key.");
1.139 + return new KeyBundle(enc, hmac);
1.140 + }
1.141 +
1.142 + // TODO Replace this function with the one in the crypto library
1.143 + private static byte[] HMACSHA256(byte[] data, byte[] key) {
1.144 + byte[] result = null;
1.145 + try {
1.146 + Mac hmacSha256;
1.147 + hmacSha256 = Mac.getInstance("HmacSHA256");
1.148 + SecretKeySpec secret_key = new SecretKeySpec(key, "HmacSHA256");
1.149 + hmacSha256.init(secret_key);
1.150 + result = hmacSha256.doFinal(data);
1.151 + } catch (GeneralSecurityException e) {
1.152 + Logger.error(LOG_TAG, "Got exception calculating HMAC.", e);
1.153 + }
1.154 + return result;
1.155 + }
1.156 +
1.157 + /* Helper Methods */
1.158 +
1.159 + /*
1.160 + * Generate the ZKP b = r - x*h, and g^r, where h = hash(g, g^r, g^x, id). (We
1.161 + * pass in gx to save on an exponentiation of g^x)
1.162 + */
1.163 + private static Zkp createZkp(BigInteger g, BigInteger x, BigInteger gx,
1.164 + String id, JPakeNumGenerator gen) throws NoSuchAlgorithmException, UnsupportedEncodingException {
1.165 + // Generate random r for exponent.
1.166 + BigInteger r = gen.generateFromRange(Q);
1.167 +
1.168 + // Calculate g^r for ZKP.
1.169 + BigInteger gr = g.modPow(r, P);
1.170 +
1.171 + // Calculate the ZKP b value = (r-x*h) % q.
1.172 + BigInteger h = computeBHash(g, gr, gx, id);
1.173 + Logger.debug(LOG_TAG, "myhash: " + h.toString(16));
1.174 +
1.175 + // ZKP value = b = r-x*h
1.176 + BigInteger b = r.subtract(x.multiply(h)).mod(Q);
1.177 +
1.178 + return new Zkp(gr, b, id);
1.179 + }
1.180 +
1.181 + /*
1.182 + * Verify ZKP.
1.183 + */
1.184 + private static void checkZkp(BigInteger g, BigInteger gx, Zkp zkp)
1.185 + throws IncorrectZkpException, NoSuchAlgorithmException, UnsupportedEncodingException {
1.186 +
1.187 + BigInteger h = computeBHash(g, zkp.gr, gx, zkp.id);
1.188 +
1.189 + // Check parameters of zkp, and compare to computed hash. These shouldn't
1.190 + // fail.
1.191 + if (gx.compareTo(BigInteger.ONE) < 1) { // g^x > 1.
1.192 + Logger.error(LOG_TAG, "g^x > 1 fails.");
1.193 + throw new IncorrectZkpException();
1.194 + }
1.195 + if (gx.compareTo(P.subtract(BigInteger.ONE)) > -1) { // g^x < p-1
1.196 + Logger.error(LOG_TAG, "g^x < p-1 fails.");
1.197 + throw new IncorrectZkpException();
1.198 + }
1.199 + if (gx.modPow(Q, P).compareTo(BigInteger.ONE) != 0) {
1.200 + Logger.error(LOG_TAG, "g^x^q % p = 1 fails.");
1.201 + throw new IncorrectZkpException();
1.202 + }
1.203 + if (zkp.gr.compareTo(g.modPow(zkp.b, P).multiply(gx.modPow(h, P)).mod(P)) != 0) {
1.204 + // b = r-h*x ==> g^r = g^b*g^x^(h)
1.205 + Logger.debug(LOG_TAG, "gb*g(xh) = " + g.modPow(zkp.b, P).multiply(gx.modPow(h, P)).mod(P).toString(16));
1.206 + Logger.debug(LOG_TAG, "gr = " + zkp.gr.toString(16));
1.207 + Logger.debug(LOG_TAG, "b = " + zkp.b.toString(16));
1.208 + Logger.debug(LOG_TAG, "g^b = " + g.modPow(zkp.b, P).toString(16));
1.209 + Logger.debug(LOG_TAG, "g^(xh) = " + gx.modPow(h, P).toString(16));
1.210 + Logger.debug(LOG_TAG, "gx = " + gx.toString(16));
1.211 + Logger.debug(LOG_TAG, "h = " + h.toString(16));
1.212 + Logger.error(LOG_TAG, "zkp calculation incorrect.");
1.213 + throw new IncorrectZkpException();
1.214 + }
1.215 + Logger.debug(LOG_TAG, "*** ZKP SUCCESS ***");
1.216 + }
1.217 +
1.218 + /*
1.219 + * Use SHA-256 to compute a BigInteger hash of g, gr, gx values with
1.220 + * mySignerId to prevent replay. Does not make a twos-complement BigInteger
1.221 + * form hash.
1.222 + */
1.223 + private static BigInteger computeBHash(BigInteger g, BigInteger gr, BigInteger gx,
1.224 + String id) throws NoSuchAlgorithmException, UnsupportedEncodingException {
1.225 + MessageDigest sha = MessageDigest.getInstance("SHA-256");
1.226 + sha.reset();
1.227 +
1.228 + /*
1.229 + * Note: you should ensure the items in H(...) have clear boundaries. It
1.230 + * is simple if the other party knows sizes of g, gr, gx and signerID and
1.231 + * hence the boundary is unambiguous. If not, you'd better prepend each
1.232 + * item with its byte length, but I've omitted that here.
1.233 + */
1.234 +
1.235 + hashByteArrayWithLength(sha, BigIntegerHelper.BigIntegerToByteArrayWithoutSign(g));
1.236 + hashByteArrayWithLength(sha, BigIntegerHelper.BigIntegerToByteArrayWithoutSign(gr));
1.237 + hashByteArrayWithLength(sha, BigIntegerHelper.BigIntegerToByteArrayWithoutSign(gx));
1.238 + hashByteArrayWithLength(sha, id.getBytes("UTF-8"));
1.239 +
1.240 + byte[] hash = sha.digest();
1.241 +
1.242 + return BigIntegerHelper.ByteArrayToBigIntegerWithoutSign(hash);
1.243 + }
1.244 +
1.245 + /*
1.246 + * Update a hash with a byte array's length and the byte array.
1.247 + */
1.248 + private static void hashByteArrayWithLength(MessageDigest sha, byte[] data) {
1.249 + int length = data.length;
1.250 + byte[] b = new byte[] { (byte) (length >>> 8), (byte) (length & 0xff) };
1.251 + sha.update(b);
1.252 + sha.update(data);
1.253 + }
1.254 +
1.255 + /*
1.256 + * Helper function to generate encryption key and HMAC from a byte array.
1.257 + */
1.258 + public static void generateKeyAndHmac(BigInteger k, byte[] encOut, byte[] hmacOut) throws NoSuchAlgorithmException, InvalidKeyException {
1.259 + // Generate HMAC and Encryption keys from synckey.
1.260 + byte[] zerokey = new byte[32];
1.261 + byte[] prk = HMACSHA256(BigIntegerHelper.BigIntegerToByteArrayWithoutSign(k), zerokey);
1.262 +
1.263 + byte[] okm = HKDF.hkdfExpand(prk, HKDF.HMAC_INPUT, 32 * 2);
1.264 + System.arraycopy(okm, 0, encOut, 0, 32);
1.265 + System.arraycopy(okm, 32, hmacOut, 0, 32);
1.266 + }
1.267 +}
