1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 19 package com.example.android.brokenkeyderivation; 20 21 /** 22 * Stripped-down version of the SHA1PRNG provided by the Crypto provider. 23 * 24 * The Crypto provider that offers this functionality was deprecated on Android. 25 * 26 * Use this class only to retrieve encrypted data that couldn't be retrieved otherwise. 27 */ 28 class InsecureSHA1PRNGKeyDerivator { 29 30 /** 31 * Only public method. Derive a key from the given seed. 32 * 33 * Use this method only to retrieve encrypted data that couldn't be retrieved otherwise. 34 * 35 * @param seed seed used for the random generator, usually coming from a password 36 * @param keySizeInBytes length of the array returned 37 */ deriveInsecureKey(byte[] seed, int keySizeInBytes)38 public static byte[] deriveInsecureKey(byte[] seed, int keySizeInBytes) { 39 InsecureSHA1PRNGKeyDerivator derivator = new InsecureSHA1PRNGKeyDerivator(); 40 derivator.setSeed(seed); 41 byte[] key = new byte[keySizeInBytes]; 42 derivator.nextBytes(key); 43 return key; 44 } 45 46 // constants to use in expressions operating on bytes in int and long variables: 47 // END_FLAGS - final bytes in words to append to message; 48 // see "ch.5.1 Padding the Message, FIPS 180-2" 49 // RIGHT1 - shifts to right for left half of long 50 // RIGHT2 - shifts to right for right half of long 51 // LEFT - shifts to left for bytes 52 // MASK - mask to select counter's bytes after shift to right 53 54 private static final int[] END_FLAGS = { 0x80000000, 0x800000, 0x8000, 0x80 }; 55 56 private static final int[] RIGHT1 = { 0, 40, 48, 56 }; 57 58 private static final int[] RIGHT2 = { 0, 8, 16, 24 }; 59 60 private static final int[] LEFT = { 0, 24, 16, 8 }; 61 62 private static final int[] MASK = { 0xFFFFFFFF, 0x00FFFFFF, 0x0000FFFF, 63 0x000000FF }; 64 65 // HASHBYTES_TO_USE defines # of bytes returned by "computeHash(byte[])" 66 // to use to form byte array returning by the "nextBytes(byte[])" method 67 // Note, that this implementation uses more bytes than it is defined 68 // in the above specification. 69 private static final int HASHBYTES_TO_USE = 20; 70 71 // value of 16 defined in the "SECURE HASH STANDARD", FIPS PUB 180-2 72 private static final int FRAME_LENGTH = 16; 73 74 // miscellaneous constants defined in this implementation: 75 // COUNTER_BASE - initial value to set to "counter" before computing "nextBytes(..)"; 76 // note, that the exact value is not defined in STANDARD 77 // HASHCOPY_OFFSET - offset for copy of current hash in "copies" array 78 // EXTRAFRAME_OFFSET - offset for extra frame in "copies" array; 79 // as the extra frame follows the current hash frame, 80 // EXTRAFRAME_OFFSET is equal to length of current hash frame 81 // FRAME_OFFSET - offset for frame in "copies" array 82 // MAX_BYTES - maximum # of seed bytes processing which doesn't require extra frame 83 // see (1) comments on usage of "seed" array below and 84 // (2) comments in "engineNextBytes(byte[])" method 85 // 86 // UNDEFINED - three states of engine; initially its state is "UNDEFINED" 87 // SET_SEED call to "engineSetSeed" sets up "SET_SEED" state, 88 // NEXT_BYTES call to "engineNextByte" sets up "NEXT_BYTES" state 89 90 private static final int COUNTER_BASE = 0; 91 92 private static final int HASHCOPY_OFFSET = 0; 93 94 private static final int EXTRAFRAME_OFFSET = 5; 95 96 private static final int FRAME_OFFSET = 21; 97 98 private static final int MAX_BYTES = 48; 99 100 private static final int UNDEFINED = 0; 101 102 private static final int SET_SEED = 1; 103 104 private static final int NEXT_BYTES = 2; 105 106 // Structure of "seed" array: 107 // - 0-79 - words for computing hash 108 // - 80 - unused 109 // - 81 - # of seed bytes in current seed frame 110 // - 82-86 - 5 words, current seed hash 111 private transient int[] seed; 112 113 // total length of seed bytes, including all processed 114 private transient long seedLength; 115 116 // Structure of "copies" array 117 // - 0-4 - 5 words, copy of current seed hash 118 // - 5-20 - extra 16 words frame; 119 // is used if final padding exceeds 512-bit length 120 // - 21-36 - 16 word frame to store a copy of remaining bytes 121 private transient int[] copies; 122 123 // ready "next" bytes; needed because words are returned 124 private transient byte[] nextBytes; 125 126 // index of used bytes in "nextBytes" array 127 private transient int nextBIndex; 128 129 // variable required according to "SECURE HASH STANDARD" 130 private transient long counter; 131 132 // contains int value corresponding to engine's current state 133 private transient int state; 134 135 /** 136 * constant defined in "SECURE HASH STANDARD" 137 */ 138 private static final int H0 = 0x67452301; 139 140 141 /** 142 * constant defined in "SECURE HASH STANDARD" 143 */ 144 private static final int H1 = 0xEFCDAB89; 145 146 147 /** 148 * constant defined in "SECURE HASH STANDARD" 149 */ 150 private static final int H2 = 0x98BADCFE; 151 152 153 /** 154 * constant defined in "SECURE HASH STANDARD" 155 */ 156 private static final int H3 = 0x10325476; 157 158 159 /** 160 * constant defined in "SECURE HASH STANDARD" 161 */ 162 private static final int H4 = 0xC3D2E1F0; 163 164 165 /** 166 * offset in buffer to store number of bytes in 0-15 word frame 167 */ 168 private static final int BYTES_OFFSET = 81; 169 170 171 /** 172 * offset in buffer to store current hash value 173 */ 174 private static final int HASH_OFFSET = 82; 175 176 177 /** 178 * # of bytes in H0-H4 words; <BR> 179 * in this implementation # is set to 20 (in general # varies from 1 to 20) 180 */ 181 private static final int DIGEST_LENGTH = 20; 182 183 // The "seed" array is used to compute both "current seed hash" and "next bytes". 184 // 185 // As the "SHA1" algorithm computes a hash of entire seed by splitting it into 186 // a number of the 512-bit length frames (512 bits = 64 bytes = 16 words), 187 // "current seed hash" is a hash (5 words, 20 bytes) for all previous full frames; 188 // remaining bytes are stored in the 0-15 word frame of the "seed" array. 189 // 190 // As for calculating "next bytes", 191 // both remaining bytes and "current seed hash" are used, 192 // to preserve the latter for following "setSeed(..)" commands, 193 // the following technique is used: 194 // - upon getting "nextBytes(byte[])" invoked, single or first in row, 195 // which requires computing new hash, that is, 196 // there is no more bytes remaining from previous "next bytes" computation, 197 // remaining bytes are copied into the 21-36 word frame of the "copies" array; 198 // - upon getting "setSeed(byte[])" invoked, single or first in row, 199 // remaining bytes are copied back. 200 InsecureSHA1PRNGKeyDerivator()201 private InsecureSHA1PRNGKeyDerivator() { 202 seed = new int[HASH_OFFSET + EXTRAFRAME_OFFSET]; 203 seed[HASH_OFFSET] = H0; 204 seed[HASH_OFFSET + 1] = H1; 205 seed[HASH_OFFSET + 2] = H2; 206 seed[HASH_OFFSET + 3] = H3; 207 seed[HASH_OFFSET + 4] = H4; 208 209 seedLength = 0; 210 copies = new int[2 * FRAME_LENGTH + EXTRAFRAME_OFFSET]; 211 nextBytes = new byte[DIGEST_LENGTH]; 212 nextBIndex = HASHBYTES_TO_USE; 213 counter = COUNTER_BASE; 214 state = UNDEFINED; 215 } 216 217 /* 218 * The method invokes the SHA1Impl's "updateHash(..)" method 219 * to update current seed frame and 220 * to compute new intermediate hash value if the frame is full. 221 * 222 * After that it computes a length of whole seed. 223 */ updateSeed(byte[] bytes)224 private void updateSeed(byte[] bytes) { 225 226 // on call: "seed" contains current bytes and current hash; 227 // on return: "seed" contains new current bytes and possibly new current hash 228 // if after adding, seed bytes overfill its buffer 229 updateHash(seed, bytes, 0, bytes.length - 1); 230 231 seedLength += bytes.length; 232 } 233 234 /** 235 * Changes current seed by supplementing a seed argument to the current seed, 236 * if this already set; 237 * the argument is used as first seed otherwise. <BR> 238 * 239 * The method overrides "engineSetSeed(byte[])" in class SecureRandomSpi. 240 * 241 * @param 242 * seed - byte array 243 * @throws 244 * NullPointerException - if null is passed to the "seed" argument 245 */ setSeed(byte[] seed)246 private void setSeed(byte[] seed) { 247 if (seed == null) { 248 throw new NullPointerException("seed == null"); 249 } 250 251 if (state == NEXT_BYTES) { // first setSeed after NextBytes; restoring hash 252 System.arraycopy(copies, HASHCOPY_OFFSET, this.seed, HASH_OFFSET, 253 EXTRAFRAME_OFFSET); 254 } 255 state = SET_SEED; 256 257 if (seed.length != 0) { 258 updateSeed(seed); 259 } 260 } 261 262 /** 263 * Writes random bytes into an array supplied. 264 * Bits in a byte are from left to right. <BR> 265 * 266 * To generate random bytes, the "expansion of source bits" method is used, 267 * that is, 268 * the current seed with a 64-bit counter appended is used to compute new bits. 269 * The counter is incremented by 1 for each 20-byte output. <BR> 270 * 271 * The method overrides engineNextBytes in class SecureRandomSpi. 272 * 273 * @param 274 * bytes - byte array to be filled in with bytes 275 * @throws 276 * NullPointerException - if null is passed to the "bytes" argument 277 */ nextBytes(byte[] bytes)278 protected synchronized void nextBytes(byte[] bytes) { 279 280 int i, n; 281 282 long bits; // number of bits required by Secure Hash Standard 283 int nextByteToReturn; // index of ready bytes in "bytes" array 284 int lastWord; // index of last word in frame containing bytes 285 286 // This is a bug since words are 4 bytes. Android used to keep it this way for backward 287 // compatibility. 288 final int extrabytes = 7;// # of bytes to add in order to computer # of 8 byte words 289 290 if (bytes == null) { 291 throw new NullPointerException("bytes == null"); 292 } 293 294 // This is a bug since extraBytes == 7 instead of 3. Android used to keep it this way for 295 // backward compatibility. 296 lastWord = seed[BYTES_OFFSET] == 0 ? 0 297 : (seed[BYTES_OFFSET] + extrabytes) >> 3 - 1; 298 299 if (state == UNDEFINED) { 300 301 throw new IllegalStateException("No seed supplied!"); 302 303 } else if (state == SET_SEED) { 304 305 System.arraycopy(seed, HASH_OFFSET, copies, HASHCOPY_OFFSET, 306 EXTRAFRAME_OFFSET); 307 308 // possible cases for 64-byte frame: 309 // 310 // seed bytes < 48 - remaining bytes are enough for all, 8 counter bytes, 311 // 0x80, and 8 seedLength bytes; no extra frame required 312 // 48 < seed bytes < 56 - remaining 9 bytes are for 0x80 and 8 counter bytes 313 // extra frame contains only seedLength value at the end 314 // seed bytes > 55 - extra frame contains both counter's bytes 315 // at the beginning and seedLength value at the end; 316 // note, that beginning extra bytes are not more than 8, 317 // that is, only 2 extra words may be used 318 319 // no need to set to "0" 3 words after "lastWord" and 320 // more than two words behind frame 321 for (i = lastWord + 3; i < FRAME_LENGTH + 2; i++) { 322 seed[i] = 0; 323 } 324 325 bits = (seedLength << 3) + 64; // transforming # of bytes into # of bits 326 327 // putting # of bits into two last words (14,15) of 16 word frame in 328 // seed or copies array depending on total length after padding 329 if (seed[BYTES_OFFSET] < MAX_BYTES) { 330 seed[14] = (int) (bits >>> 32); 331 seed[15] = (int) (bits & 0xFFFFFFFF); 332 } else { 333 copies[EXTRAFRAME_OFFSET + 14] = (int) (bits >>> 32); 334 copies[EXTRAFRAME_OFFSET + 15] = (int) (bits & 0xFFFFFFFF); 335 } 336 337 nextBIndex = HASHBYTES_TO_USE; // skipping remaining random bits 338 } 339 state = NEXT_BYTES; 340 341 if (bytes.length == 0) { 342 return; 343 } 344 345 nextByteToReturn = 0; 346 347 // possibly not all of HASHBYTES_TO_USE bytes were used previous time 348 n = (HASHBYTES_TO_USE - nextBIndex) < (bytes.length - nextByteToReturn) ? HASHBYTES_TO_USE 349 - nextBIndex 350 : bytes.length - nextByteToReturn; 351 if (n > 0) { 352 System.arraycopy(nextBytes, nextBIndex, bytes, nextByteToReturn, n); 353 nextBIndex += n; 354 nextByteToReturn += n; 355 } 356 357 if (nextByteToReturn >= bytes.length) { 358 return; // return because "bytes[]" are filled in 359 } 360 361 n = seed[BYTES_OFFSET] & 0x03; 362 for (;;) { 363 if (n == 0) { 364 365 seed[lastWord] = (int) (counter >>> 32); 366 seed[lastWord + 1] = (int) (counter & 0xFFFFFFFF); 367 seed[lastWord + 2] = END_FLAGS[0]; 368 369 } else { 370 371 seed[lastWord] |= (int) ((counter >>> RIGHT1[n]) & MASK[n]); 372 seed[lastWord + 1] = (int) ((counter >>> RIGHT2[n]) & 0xFFFFFFFF); 373 seed[lastWord + 2] = (int) ((counter << LEFT[n]) | END_FLAGS[n]); 374 } 375 if (seed[BYTES_OFFSET] > MAX_BYTES) { 376 copies[EXTRAFRAME_OFFSET] = seed[FRAME_LENGTH]; 377 copies[EXTRAFRAME_OFFSET + 1] = seed[FRAME_LENGTH + 1]; 378 } 379 380 computeHash(seed); 381 382 if (seed[BYTES_OFFSET] > MAX_BYTES) { 383 384 System.arraycopy(seed, 0, copies, FRAME_OFFSET, FRAME_LENGTH); 385 System.arraycopy(copies, EXTRAFRAME_OFFSET, seed, 0, 386 FRAME_LENGTH); 387 388 computeHash(seed); 389 System.arraycopy(copies, FRAME_OFFSET, seed, 0, FRAME_LENGTH); 390 } 391 counter++; 392 393 int j = 0; 394 for (i = 0; i < EXTRAFRAME_OFFSET; i++) { 395 int k = seed[HASH_OFFSET + i]; 396 nextBytes[j] = (byte) (k >>> 24); // getting first byte from left 397 nextBytes[j + 1] = (byte) (k >>> 16); // getting second byte from left 398 nextBytes[j + 2] = (byte) (k >>> 8); // getting third byte from left 399 nextBytes[j + 3] = (byte) (k); // getting fourth byte from left 400 j += 4; 401 } 402 403 nextBIndex = 0; 404 j = HASHBYTES_TO_USE < (bytes.length - nextByteToReturn) ? HASHBYTES_TO_USE 405 : bytes.length - nextByteToReturn; 406 407 if (j > 0) { 408 System.arraycopy(nextBytes, 0, bytes, nextByteToReturn, j); 409 nextByteToReturn += j; 410 nextBIndex += j; 411 } 412 413 if (nextByteToReturn >= bytes.length) { 414 break; 415 } 416 } 417 } 418 419 /** 420 * The method generates a 160 bit hash value using 421 * a 512 bit message stored in first 16 words of int[] array argument and 422 * current hash value stored in five words, beginning OFFSET+1, of the array argument. 423 * Computation is done according to SHA-1 algorithm. 424 * 425 * The resulting hash value replaces the previous hash value in the array; 426 * original bits of the message are not preserved. 427 * 428 * No checks on argument supplied, that is, 429 * a calling method is responsible for such checks. 430 * In case of incorrect array passed to the method 431 * either NPE or IndexOutOfBoundException gets thrown by JVM. 432 * 433 * @params 434 * arrW - integer array; arrW.length >= (BYTES_OFFSET+6); <BR> 435 * only first (BYTES_OFFSET+6) words are used 436 */ 437 private static void computeHash(int[] arrW) { 438 439 int a = arrW[HASH_OFFSET ]; 440 int b = arrW[HASH_OFFSET +1]; 441 int c = arrW[HASH_OFFSET +2]; 442 int d = arrW[HASH_OFFSET +3]; 443 int e = arrW[HASH_OFFSET +4]; 444 445 int temp; 446 447 // In this implementation the "d. For t = 0 to 79 do" loop 448 // is split into four loops. The following constants: 449 // K = 5A827999 0 <= t <= 19 450 // K = 6ED9EBA1 20 <= t <= 39 451 // K = 8F1BBCDC 40 <= t <= 59 452 // K = CA62C1D6 60 <= t <= 79 453 // are hex literals in the loops. 454 455 for ( int t = 16; t < 80 ; t++ ) { 456 457 temp = arrW[t-3] ^ arrW[t-8] ^ arrW[t-14] ^ arrW[t-16]; 458 arrW[t] = ( temp<<1 ) | ( temp>>>31 ); 459 } 460 461 for ( int t = 0 ; t < 20 ; t++ ) { 462 463 temp = ( ( a<<5 ) | ( a>>>27 ) ) + 464 ( ( b & c) | ((~b) & d) ) + 465 ( e + arrW[t] + 0x5A827999 ) ; 466 e = d; 467 d = c; 468 c = ( b<<30 ) | ( b>>>2 ) ; 469 b = a; 470 a = temp; 471 } 472 for ( int t = 20 ; t < 40 ; t++ ) { 473 474 temp = ((( a<<5 ) | ( a>>>27 ))) + (b ^ c ^ d) + (e + arrW[t] + 0x6ED9EBA1) ; 475 e = d; 476 d = c; 477 c = ( b<<30 ) | ( b>>>2 ) ; 478 b = a; 479 a = temp; 480 } 481 for ( int t = 40 ; t < 60 ; t++ ) { 482 483 temp = (( a<<5 ) | ( a>>>27 )) + ((b & c) | (b & d) | (c & d)) + 484 (e + arrW[t] + 0x8F1BBCDC) ; 485 e = d; 486 d = c; 487 c = ( b<<30 ) | ( b>>>2 ) ; 488 b = a; 489 a = temp; 490 } 491 for ( int t = 60 ; t < 80 ; t++ ) { 492 493 temp = ((( a<<5 ) | ( a>>>27 ))) + (b ^ c ^ d) + (e + arrW[t] + 0xCA62C1D6) ; 494 e = d; 495 d = c; 496 c = ( b<<30 ) | ( b>>>2 ) ; 497 b = a; 498 a = temp; 499 } 500 501 arrW[HASH_OFFSET ] += a; 502 arrW[HASH_OFFSET +1] += b; 503 arrW[HASH_OFFSET +2] += c; 504 arrW[HASH_OFFSET +3] += d; 505 arrW[HASH_OFFSET +4] += e; 506 } 507 508 /** 509 * The method appends new bytes to existing ones 510 * within limit of a frame of 64 bytes (16 words). 511 * 512 * Once a length of accumulated bytes reaches the limit 513 * the "computeHash(int[])" method is invoked on the array to compute updated hash, 514 * and the number of bytes in the frame is set to 0. 515 * Thus, after appending all bytes, the array contain only those bytes 516 * that were not used in computing final hash value yet. 517 * 518 * No checks on arguments passed to the method, that is, 519 * a calling method is responsible for such checks. 520 * 521 * @params 522 * intArray - int array containing bytes to which to append; 523 * intArray.length >= (BYTES_OFFSET+6) 524 * @params 525 * byteInput - array of bytes to use for the update 526 * @params 527 * from - the offset to start in the "byteInput" array 528 * @params 529 * to - a number of the last byte in the input array to use, 530 * that is, for first byte "to"==0, for last byte "to"==input.length-1 531 */ 532 private static void updateHash(int[] intArray, byte[] byteInput, int fromByte, int toByte) { 533 534 // As intArray contains a packed bytes 535 // the buffer's index is in the intArray[BYTES_OFFSET] element 536 537 int index = intArray[BYTES_OFFSET]; 538 int i = fromByte; 539 int maxWord; 540 int nBytes; 541 542 int wordIndex = index >>2; 543 int byteIndex = index & 0x03; 544 545 intArray[BYTES_OFFSET] = ( index + toByte - fromByte + 1 ) & 077 ; 546 547 // In general case there are 3 stages : 548 // - appending bytes to non-full word, 549 // - writing 4 bytes into empty words, 550 // - writing less than 4 bytes in last word 551 552 if ( byteIndex != 0 ) { // appending bytes in non-full word (as if) 553 554 for ( ; ( i <= toByte ) && ( byteIndex < 4 ) ; i++ ) { 555 intArray[wordIndex] |= ( byteInput[i] & 0xFF ) << ((3 - byteIndex)<<3) ; 556 byteIndex++; 557 } 558 if ( byteIndex == 4 ) { 559 wordIndex++; 560 if ( wordIndex == 16 ) { // intArray is full, computing hash 561 562 computeHash(intArray); 563 wordIndex = 0; 564 } 565 } 566 if ( i > toByte ) { // all input bytes appended 567 return ; 568 } 569 } 570 571 // writing full words 572 573 maxWord = (toByte - i + 1) >> 2; // # of remaining full words, may be "0" 574 for ( int k = 0; k < maxWord ; k++ ) { 575 576 intArray[wordIndex] = ( ((int) byteInput[i ] & 0xFF) <<24 ) | 577 ( ((int) byteInput[i +1] & 0xFF) <<16 ) | 578 ( ((int) byteInput[i +2] & 0xFF) <<8 ) | 579 ( ((int) byteInput[i +3] & 0xFF) ) ; 580 i += 4; 581 wordIndex++; 582 583 if ( wordIndex < 16 ) { // buffer is not full yet 584 continue; 585 } 586 computeHash(intArray); // buffer is full, computing hash 587 wordIndex = 0; 588 } 589 590 // writing last incomplete word 591 // after writing free byte positions are set to "0"s 592 593 nBytes = toByte - i +1; 594 if ( nBytes != 0 ) { 595 596 int w = ((int) byteInput[i] & 0xFF) <<24 ; 597 598 if ( nBytes != 1 ) { 599 w |= ((int) byteInput[i +1] & 0xFF) <<16 ; 600 if ( nBytes != 2) { 601 w |= ((int) byteInput[i +2] & 0xFF) <<8 ; 602 } 603 } 604 intArray[wordIndex] = w; 605 } 606 607 return ; 608 } 609 } 610