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