1 /* 2 * Copyright (C) 2021 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 com.android.libraries.entitlement.eapaka; 18 19 import static java.nio.charset.StandardCharsets.UTF_8; 20 21 import android.text.TextUtils; 22 import android.util.Log; 23 24 import androidx.annotation.Nullable; 25 26 import com.android.libraries.entitlement.ServiceEntitlementException; 27 import com.android.libraries.entitlement.utils.BytesConverter; 28 29 import java.math.BigInteger; 30 import java.security.MessageDigest; 31 import java.security.NoSuchAlgorithmException; 32 33 /** 34 * The class for Master Key. 35 * 36 * <p>Reference : RFC 4187, Section 7. Key Generation MK = SHA1(Identity|IK|CK) 37 */ 38 class MasterKey { 39 private static final String TAG = "ServiceEntitlement"; 40 /* K_encr (128 bits) */ 41 private static final int LENGTH_K_ENCR = 16; 42 /* K_aut (128 bits) */ 43 private static final int LENGTH_K_AUT = 16; 44 /* Master Session Key (64 bytes) */ 45 private static final int LENGTH_MSK = 64; 46 /* Extended Master Session Key (64 bytes) */ 47 private static final int LENGTH_EMSK = 64; 48 /* Transient EAP Keys : K_enrc + K_aut + MSK + EMSK */ 49 private static final int LENGTH_TEKS = 160; 50 51 /* Master Key */ 52 private byte[] mMasterKey; 53 54 /* Transient EAP Keys */ 55 private byte[] mEncr; 56 private byte[] mAut; 57 private byte[] mMsk; 58 private byte[] mEmsk; 59 MasterKey()60 private MasterKey() { 61 } 62 63 /** Create the {@code masterKey}. */ create(String identity, @Nullable byte[] ik, @Nullable byte[] ck)64 public static MasterKey create(String identity, @Nullable byte[] ik, @Nullable byte[] ck) 65 throws ServiceEntitlementException { 66 if (TextUtils.isEmpty(identity) 67 || ik == null 68 || ik.length == 0 69 || ck == null 70 || ck.length == 0) { 71 Log.d(TAG, "Can't create master key due to invalid input!"); 72 return null; 73 } 74 MasterKey mk = new MasterKey(); 75 mk.from(identity, ik, ck); 76 return mk; 77 } 78 from(String identity, byte[] ik, byte[] ck)79 void from(String identity, byte[] ik, byte[] ck) { 80 // concatenate Identity/IK/CK 81 byte[] identityBytes = identity.getBytes(UTF_8); 82 byte[] data = new byte[identityBytes.length + ik.length + ck.length]; 83 int index = 0; 84 System.arraycopy(identityBytes, 0, data, index, identityBytes.length); 85 index += identityBytes.length; 86 System.arraycopy(ik, 0, data, index, ik.length); 87 index += ik.length; 88 System.arraycopy(ck, 0, data, index, ck.length); 89 90 // process SHA1 91 try { 92 MessageDigest messageDigest = MessageDigest.getInstance("SHA-1"); 93 messageDigest.update(data); 94 mMasterKey = messageDigest.digest(); 95 } catch (NoSuchAlgorithmException e) { 96 Log.d(TAG, "process SHA-1 failed", e); 97 } 98 99 // Generate TEKs 100 generateTransientEapKeys(); 101 } 102 103 /** 104 * Generates TEKs base on RFC 4187, Section 7. Key Generation, snippet as below 105 * 106 * <p>The Master Key is fed into a Pseudo-Random number Function (PRF), which generates 107 * separate 108 * Transient EAP Keys (TEKs) for protecting EAP-AKA packets, as well as a Master Session Key 109 * (MSK) 110 * for link layer security and an Extended Master Session Key (EMSK) for other purposes. 111 */ generateTransientEapKeys()112 void generateTransientEapKeys() { 113 byte[] teks = generatePsudoRandomNumber(); 114 115 if (teks == null || teks.length != 160) { 116 Log.e(TAG, "Invalid TEKs data!"); 117 return; 118 } 119 120 int index = 0; 121 mEncr = new byte[LENGTH_K_ENCR]; 122 System.arraycopy(teks, index, mEncr, 0, LENGTH_K_ENCR); 123 index += LENGTH_K_ENCR; 124 mAut = new byte[LENGTH_K_AUT]; 125 System.arraycopy(teks, index, mAut, 0, LENGTH_K_AUT); 126 index += LENGTH_K_AUT; 127 mMsk = new byte[LENGTH_MSK]; 128 System.arraycopy(teks, index, mMsk, 0, LENGTH_MSK); 129 index += LENGTH_MSK; 130 mEmsk = new byte[LENGTH_EMSK]; 131 System.arraycopy(teks, index, mEmsk, 0, LENGTH_EMSK); 132 } 133 134 /** Returns {@code aut}. */ getAut()135 public byte[] getAut() { 136 return mAut; 137 } 138 139 // RFC 4187 Appendix A. Pseudo-Random Number Generator 140 @Nullable generatePsudoRandomNumber()141 private byte[] generatePsudoRandomNumber() { 142 // Step 1: Choose a new, secret value for the seed-key, XKEY 143 byte[] key = mMasterKey; 144 145 // 160-bit XKEY and XVAL values are used, so b = 160. On each full 146 // authentication, the Master Key is used as the initial secret seed-key 147 // XKEY. 148 if (key == null || key.length != 20) { 149 Log.e(TAG, "Not a valid XKey!length=" + (key == null ? "null" : key.length)); 150 return null; 151 } 152 153 // Step 2: In hexadecimal notation let 154 // t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 155 // This is the initial value for H0|H1|H2|H3|H4 156 // in the FIPS SHS [SHA-1] 157 int[] t = {0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0}; 158 159 // Step 3: For j = 0 to m - 1 do 160 // 3.1. XSEED_j = 0 /* no optional user input */ 161 // 3.2. For i = 0 to 1 do 162 // a. XVAL = (XKEY + XSEED_j) mod 2^b 163 // b. w_i = G(t, XVAL) 164 // c. XKEY = (1 + XKEY + w_i) mod 2^b 165 // 3.3. x_j = w_0|w_1 166 // Step 3: For j = 0 to m - 1 do 167 // 168 // Base on below snippet from RFC 4187, b is 160, x_j is 40 bytes, w_i is 20 bytes, TEKs 169 // length is 160 bytes and m is 160/40=4 170 // 171 // 160-bit XKEY and XVAL values are used, so b = 160. On each full 172 // authentication, the Master Key is used as the initial secret seed-key 173 // XKEY. The optional user input values (XSEED_j) in step 3.1 are set 174 // to zero. 175 // On full authentication, the resulting 320-bit random numbers x_0, 176 // x_1, ..., x_m-1 are concatenated and partitioned into suitable-sized 177 // chunks and used as keys in the following order: K_encr (128 bits), 178 // K_aut (128 bits), Master Session Key (64 bytes), Extended Master 179 // Session Key (64 bytes). 180 byte[] teks = new byte[LENGTH_TEKS]; 181 int index = 0; 182 for (int j = 0; j < 4; j++) { 183 // 3.1. XSEED_j = 0, do nothing 184 // 3.2. For i = 0 to 1 do 185 for (int i = 0; i < 2; i++) { 186 // a. XVAL = (XKEY + XSEED_j) mod 2^b 187 byte[] val = key; 188 189 // b. w_i = G(t, XVAL) 190 byte[] w = doFunctionG(t, val); 191 if (w == null || w.length != 20) { 192 Log.e(TAG, "Get invalid w value from G function!"); 193 return null; 194 } 195 // fill w to teks 196 System.arraycopy(w, 0, teks, index, 20); 197 index += 20; 198 199 // c. XKEY = (1 + XKEY + w_i) mod 2^b 200 // XKEY is 20 bytes, 160 bits, mod 2^160 is for make sure XKEY just 160 bits 201 int carry = 1; 202 for (int k = 19; k >= 0; k--) { 203 carry += (key[k] & 0xff) + (w[k] & 0xff); 204 key[k] = (byte) (carry & 0xff); 205 // shift one byte and keep carry for next byte calculate 206 carry >>= 8; 207 } 208 } 209 // 3.3. x_j = w_0|w_1, already copy w_0/w_1 to output 210 } 211 212 return teks; 213 } 214 215 // See FIPS 186-2 APPENDIX 3.3. CONSTRUCTING THE FUNCTION G FROM THE SHA-1, snippet as below 216 // 217 // G(t,c) may be constructed using steps (a) - (e) in section 7 of the Specifications for the 218 // Secure Hash Standard. Before executing these steps, {Hj} and M1 must be initialized as 219 // follows: 220 // 221 // i. Initialize the {Hj} by dividing the 160 bit value t into five 32-bit segments as follows: 222 // t = t0 || t1 || t2 || t3 || t4 223 // Then Hj = tj for j = 0 through 4. 224 // 225 // ii. There will be only one message block, M1, which is initialized as follows: 226 // M1 = c || 0^(512-b) 227 // (The first b bits of M1 contain c, and the remaining (512-b) bits are set to zero). 228 // 229 // Then steps (a) through (e) of section 7 are executed, and G(t,c) is the 160 bit string 230 // represented by the five words: 231 // H0 || H1 || H2 || H3 || H4 232 // at the end of step (e). doFunctionG(int[] t, byte[] c)233 private byte[] doFunctionG(int[] t, byte[] c) { 234 // i. Initialize the {Hj} by dividing the 160 bit value t into five 32-bit segments 235 // 5 segments and every segments is 32 bits/4 bytes 236 byte[][] bytesH = new byte[5][4]; 237 for (int i = 0; i < 5; i++) { 238 System.arraycopy(BytesConverter.convertIntegerTo4Bytes(t[i]), 0, bytesH[i], 0, 4); 239 } 240 241 // ii. init message block, M1 242 // The first b bits of M1 contain c, and the remaining (512-b) bits are set to zero 243 byte[] bytesM1 = new byte[64]; 244 System.arraycopy(c, 0, bytesM1, 0, 20); 245 for (int i = 20; i < 64; i++) { 246 bytesM1[i] = 0x00; 247 } 248 249 // See FIPS PUB 180-1, Secure Hash Standard 250 // Section 7. COMPUTING THE MESSAGE DIGEST which defined steps (a) - (e) 251 252 // The words of the 80-word sequence are labeled W0, W1,..., W79. 253 byte[][] bytesW = new byte[80][4]; 254 255 // a. Divide Mi into 16 words W0, W1, ... , W15, where W0 is the left-most word. 256 for (int i = 0; i < 16; i++) { 257 System.arraycopy(bytesM1, i * 4, bytesW[i], 0, 4); 258 } 259 260 // b. For t = 16 to 79 let Wt = S^1(Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16). 261 for (int i = 16; i < 80; i++) { 262 bytesW[i] = 263 doFunctionS(1, 264 doXor(bytesW[i - 3], bytesW[i - 8], bytesW[i - 14], bytesW[i - 16])); 265 } 266 267 // c. Let A = H0, B = H1, C = H2, D = H3, E = H4. 268 byte[] bytesA = new byte[4]; 269 byte[] bytesB = new byte[4]; 270 byte[] bytesC = new byte[4]; 271 byte[] bytesD = new byte[4]; 272 byte[] bytesE = new byte[4]; 273 System.arraycopy(bytesH[0], 0, bytesA, 0, 4); 274 System.arraycopy(bytesH[1], 0, bytesB, 0, 4); 275 System.arraycopy(bytesH[2], 0, bytesC, 0, 4); 276 System.arraycopy(bytesH[3], 0, bytesD, 0, 4); 277 System.arraycopy(bytesH[4], 0, bytesE, 0, 4); 278 279 // d. For t = 0 to 79 do 280 // TEMP = S^5(A) + ft(B,C,D) + E + Wt + Kt; 281 // E = D; D = C; C = S^30(B); B = A; A = TEMP; 282 for (int i = 0; i < 80; i++) { 283 int tmpA = new BigInteger(doFunctionS(5, bytesA)).intValue(); 284 int tmpF = doFunctionF(i, bytesB, bytesC, bytesD); 285 int tmpE = new BigInteger(bytesE).intValue(); 286 int tmpW = new BigInteger(bytesW[i]).intValue(); 287 int tmpK = doFunctionK(i); 288 int temp = tmpA + tmpF + tmpE + tmpW + tmpK; 289 bytesE = bytesD; 290 bytesD = bytesC; 291 bytesC = doFunctionS(30, bytesB); 292 bytesB = bytesA; 293 bytesA = BytesConverter.convertIntegerTo4Bytes(temp); 294 } 295 296 // e. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E. 297 bytesH[0] = addTwoBytes(bytesH[0], bytesA); 298 bytesH[1] = addTwoBytes(bytesH[1], bytesB); 299 bytesH[2] = addTwoBytes(bytesH[2], bytesC); 300 bytesH[3] = addTwoBytes(bytesH[3], bytesD); 301 bytesH[4] = addTwoBytes(bytesH[4], bytesE); 302 303 // After processing Mn, the message digest is the 160-bit string represented by the 5 words 304 // H0 H1 H2 H3 H4. 305 byte[] output = new byte[20]; 306 System.arraycopy(bytesH[0], 0, output, 0, 4); 307 System.arraycopy(bytesH[1], 0, output, 4, 4); 308 System.arraycopy(bytesH[2], 0, output, 8, 4); 309 System.arraycopy(bytesH[3], 0, output, 12, 4); 310 System.arraycopy(bytesH[4], 0, output, 16, 4); 311 312 return output; 313 } 314 addTwoBytes(byte[] a, byte[] b)315 private static byte[] addTwoBytes(byte[] a, byte[] b) { 316 BigInteger iA = new BigInteger(a); 317 BigInteger iB = new BigInteger(b); 318 return BytesConverter.convertIntegerTo4Bytes(iA.add(iB).intValue()); 319 } 320 321 // See FIPS PUB 180-1, Section 3. OPERATIONS ON WORDS 322 // Sn(X) = (X << n) OR (X >> 32-n). doFunctionS(int n, byte[] dataX)323 private static byte[] doFunctionS(int n, byte[] dataX) { 324 BigInteger leftShiftValue = new BigInteger(dataX).shiftLeft(n); 325 326 // BigInteger.shiftRight would fill 1 if the left-most bit is 1, so use '>>>' 327 int value = new BigInteger(dataX).intValue(); 328 value = value >>> (32 - n); // X should be 32 bits 329 BigInteger rightShiftValue = BigInteger.valueOf(value); 330 BigInteger result = leftShiftValue.or(rightShiftValue); 331 return BytesConverter.convertIntegerTo4Bytes(result.intValue()); 332 } 333 doXor(byte[] a, byte[] b, byte[] c, byte[] d)334 private static byte[] doXor(byte[] a, byte[] b, byte[] c, byte[] d) { 335 BigInteger iA = new BigInteger(a); 336 BigInteger iB = new BigInteger(b); 337 BigInteger iC = new BigInteger(c); 338 BigInteger iD = new BigInteger(d); 339 BigInteger result = iA.xor(iB).xor(iC).xor(iD); 340 return BytesConverter.convertIntegerTo4Bytes(result.intValue()); 341 } 342 343 // See FIPS PUB 180-1, Section 5. FUNCTIONS USED 344 // A sequence of logical functions f0, f1,..., f79 is used in the SHA-1. Each ft, 0 <= t <= 79, 345 // operates on three 32-bit words B, C, D and produces a 32-bit word as output. ft(B,C,D) is 346 // defined as follows: for words B, C, D, 347 // 348 // ft(B,C,D) = (B AND C) OR ((NOT B) AND D) (0 <= t <= 19) 349 // ft(B,C,D) = B XOR C XOR D (20 <= t <= 39) 350 // ft(B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <= t <= 59) 351 // ft(B,C,D) = B XOR C XOR D (60 <= t <= 79). doFunctionF(int t, byte[] b, byte[] c, byte[] d)352 private static int doFunctionF(int t, byte[] b, byte[] c, byte[] d) { 353 BigInteger iB = new BigInteger(b); 354 BigInteger iC = new BigInteger(c); 355 BigInteger iD = new BigInteger(d); 356 BigInteger result = BigInteger.valueOf(-1); 357 if (0 <= t && t <= 19) { 358 result = iB.and(iC).or(iB.not().and(iD)); 359 } else if (20 <= t && t <= 39) { 360 result = iB.xor(iC).xor(iD); 361 } else if (40 <= t && t <= 59) { 362 result = iB.and(iC).or(iB.and(iD)).or(iC.and(iD)); 363 } else if (60 <= t && t <= 79) { 364 result = iB.xor(iC).xor(iD); 365 } 366 367 return result.intValue(); 368 } 369 370 // See FIPS PUB 180-1, Section 6. CONSTANTS USED 371 // 372 // A sequence of constant words K(0), K(1), ... , K(79) is used in the SHA-1. In hex these are 373 // given by 374 // K = 5A827999 ( 0 <= t <= 19) 375 // Kt = 6ED9EBA1 (20 <= t <= 39) 376 // Kt = 8F1BBCDC (40 <= t <= 59) 377 // Kt = CA62C1D6 (60 <= t <= 79). doFunctionK(int t)378 private static int doFunctionK(int t) { 379 if (0 <= t && t <= 19) { 380 return 0x5A827999; 381 } else if (20 <= t && t <= 39) { 382 return 0x6ED9EBA1; 383 } else if (40 <= t && t <= 59) { 384 return 0x8F1BBCDC; 385 } else if (60 <= t && t <= 79) { 386 return 0xCA62C1D6; 387 } 388 389 return -1; 390 } 391 } 392