1 /* 2 * Copyright (C) 2022 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.nearby.fastpair.provider.crypto; 18 19 import com.google.common.base.Preconditions; 20 import com.google.common.base.Verify; 21 import com.google.common.primitives.Bytes; 22 import com.google.common.primitives.Ints; 23 import com.google.protobuf.ByteString; 24 25 import java.math.BigInteger; 26 import java.security.spec.ECFieldFp; 27 import java.security.spec.ECParameterSpec; 28 import java.security.spec.ECPoint; 29 import java.security.spec.EllipticCurve; 30 import java.util.Collections; 31 32 /** Provides methods for calculating E2EE EIDs and E2E encryption/decryption based on E2EE EIDs. */ 33 public final class E2eeCalculator { 34 35 private static final byte[] TEMP_KEY_PADDING_1 = 36 Bytes.toArray(Collections.nCopies(11, (byte) 0xFF)); 37 private static final byte[] TEMP_KEY_PADDING_2 = new byte[11]; 38 private static final ECParameterSpec CURVE_SPEC = getCurveSpec(); 39 private static final BigInteger P = ((ECFieldFp) CURVE_SPEC.getCurve().getField()).getP(); 40 private static final BigInteger TWO = new BigInteger("2"); 41 private static final BigInteger THREE = new BigInteger("3"); 42 private static final int E2EE_EID_IDENTITY_KEY_SIZE = 32; 43 private static final int E2EE_EID_SIZE = 20; 44 45 /** 46 * Computes the E2EE EID value for the given device clock based time. Note that Eddystone 47 * beacons start advertising the new EID at a random time within the window, therefore the 48 * currently advertised EID for beacon time <em>t</em> may be either 49 * {@code computeE2eeEid(eik, k, t)} or {@code computeE2eeEid(eik, k, t - (1 << k))}. 50 * 51 * <p>The E2EE EID computation is based on https://goto.google.com/e2ee-eid-computation. 52 * 53 * @param identityKey the beacon's 32-byte Eddystone E2EE identity key 54 * @param exponent rotation period exponent as configured on the beacon, must be in 55 * range the [0,15] 56 * @param deviceClockSeconds the value of the beacon's 32-bit seconds time counter (treated as 57 * an unsigned value) 58 * @return E2EE EID value. 59 */ computeE2eeEid( ByteString identityKey, int exponent, int deviceClockSeconds)60 public static ByteString computeE2eeEid( 61 ByteString identityKey, int exponent, int deviceClockSeconds) { 62 return computePublicKey(computePrivateKey(identityKey, exponent, deviceClockSeconds)); 63 } 64 computePublicKey(BigInteger privateKey)65 private static ByteString computePublicKey(BigInteger privateKey) { 66 return getXCoordinateBytes(toPoint(privateKey)); 67 } 68 computePrivateKey( ByteString identityKey, int exponent, int deviceClockSeconds)69 private static BigInteger computePrivateKey( 70 ByteString identityKey, int exponent, int deviceClockSeconds) { 71 Preconditions.checkArgument( 72 Preconditions.checkNotNull(identityKey).size() == E2EE_EID_IDENTITY_KEY_SIZE); 73 Preconditions.checkArgument(exponent >= 0 && exponent < 16); 74 75 byte[] exponentByte = new byte[]{(byte) exponent}; 76 byte[] paddedCounter = Ints.toByteArray((deviceClockSeconds >>> exponent) << exponent); 77 byte[] data = 78 Bytes.concat( 79 TEMP_KEY_PADDING_1, 80 exponentByte, 81 paddedCounter, 82 TEMP_KEY_PADDING_2, 83 exponentByte, 84 paddedCounter); 85 86 byte[] rTag = 87 Crypto.aesEcbNoPaddingEncrypt(identityKey, ByteString.copyFrom(data)).toByteArray(); 88 return new BigInteger(1, rTag).mod(CURVE_SPEC.getOrder()); 89 } 90 toPoint(BigInteger privateKey)91 private static ECPoint toPoint(BigInteger privateKey) { 92 return multiplyPoint(CURVE_SPEC.getGenerator(), privateKey); 93 } 94 getXCoordinateBytes(ECPoint point)95 private static ByteString getXCoordinateBytes(ECPoint point) { 96 byte[] unalignedBytes = point.getAffineX().toByteArray(); 97 98 // The unalignedBytes may have length < 32 if the leading E2EE EID bytes are zero, or 99 // it may be E2EE_EID_SIZE + 1 if the leading bit is 1, in which case the first byte is 100 // always zero. 101 Verify.verify( 102 unalignedBytes.length <= E2EE_EID_SIZE 103 || (unalignedBytes.length == E2EE_EID_SIZE + 1 && unalignedBytes[0] == 0)); 104 105 byte[] bytes; 106 if (unalignedBytes.length < E2EE_EID_SIZE) { 107 bytes = new byte[E2EE_EID_SIZE]; 108 System.arraycopy( 109 unalignedBytes, 0, bytes, bytes.length - unalignedBytes.length, 110 unalignedBytes.length); 111 } else if (unalignedBytes.length == E2EE_EID_SIZE + 1) { 112 bytes = new byte[E2EE_EID_SIZE]; 113 System.arraycopy(unalignedBytes, 1, bytes, 0, E2EE_EID_SIZE); 114 } else { // unalignedBytes.length == GattE2EE_EID_SIZE 115 bytes = unalignedBytes; 116 } 117 return ByteString.copyFrom(bytes); 118 } 119 120 /** Returns a secp160r1 curve spec. */ getCurveSpec()121 private static ECParameterSpec getCurveSpec() { 122 final BigInteger p = new BigInteger("ffffffffffffffffffffffffffffffff7fffffff", 16); 123 final BigInteger n = new BigInteger("0100000000000000000001f4c8f927aed3ca752257", 16); 124 final BigInteger a = new BigInteger("ffffffffffffffffffffffffffffffff7ffffffc", 16); 125 final BigInteger b = new BigInteger("1c97befc54bd7a8b65acf89f81d4d4adc565fa45", 16); 126 final BigInteger gx = new BigInteger("4a96b5688ef573284664698968c38bb913cbfc82", 16); 127 final BigInteger gy = new BigInteger("23a628553168947d59dcc912042351377ac5fb32", 16); 128 final int h = 1; 129 ECFieldFp fp = new ECFieldFp(p); 130 EllipticCurve spec = new EllipticCurve(fp, a, b); 131 ECPoint g = new ECPoint(gx, gy); 132 return new ECParameterSpec(spec, g, n, h); 133 } 134 135 /** Returns the scalar multiplication result of k*p in Fp. */ multiplyPoint(ECPoint p, BigInteger k)136 private static ECPoint multiplyPoint(ECPoint p, BigInteger k) { 137 ECPoint r = ECPoint.POINT_INFINITY; 138 ECPoint s = p; 139 BigInteger kModP = k.mod(P); 140 int length = kModP.bitLength(); 141 for (int i = 0; i <= length - 1; i++) { 142 if (kModP.mod(TWO).byteValue() == 1) { 143 r = addPoint(r, s); 144 } 145 s = doublePoint(s); 146 kModP = kModP.divide(TWO); 147 } 148 return r; 149 } 150 151 /** Returns the point addition r+s in Fp. */ addPoint(ECPoint r, ECPoint s)152 private static ECPoint addPoint(ECPoint r, ECPoint s) { 153 if (r.equals(s)) { 154 return doublePoint(r); 155 } else if (r.equals(ECPoint.POINT_INFINITY)) { 156 return s; 157 } else if (s.equals(ECPoint.POINT_INFINITY)) { 158 return r; 159 } 160 BigInteger slope = 161 r.getAffineY() 162 .subtract(s.getAffineY()) 163 .multiply(r.getAffineX().subtract(s.getAffineX()).modInverse(P)) 164 .mod(P); 165 BigInteger x = 166 slope.modPow(TWO, P).subtract(r.getAffineX()).subtract(s.getAffineX()).mod(P); 167 BigInteger y = s.getAffineY().negate().mod(P); 168 y = y.add(slope.multiply(s.getAffineX().subtract(x))).mod(P); 169 return new ECPoint(x, y); 170 } 171 172 /** Returns the point doubling 2*r in Fp. */ doublePoint(ECPoint r)173 private static ECPoint doublePoint(ECPoint r) { 174 if (r.equals(ECPoint.POINT_INFINITY)) { 175 return r; 176 } 177 BigInteger slope = r.getAffineX().pow(2).multiply(THREE); 178 slope = slope.add(CURVE_SPEC.getCurve().getA()); 179 slope = slope.multiply(r.getAffineY().multiply(TWO).modInverse(P)); 180 BigInteger x = slope.pow(2).subtract(r.getAffineX().multiply(TWO)).mod(P); 181 BigInteger y = 182 r.getAffineY().negate().add(slope.multiply(r.getAffineX().subtract(x))).mod(P); 183 return new ECPoint(x, y); 184 } 185 E2eeCalculator()186 private E2eeCalculator() { 187 } 188 } 189