1 /* 2 * Copyright (C) 2017 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.util.apk; 18 19 import java.io.IOException; 20 import java.io.RandomAccessFile; 21 import java.nio.ByteBuffer; 22 import java.nio.ByteOrder; 23 import java.security.DigestException; 24 import java.security.MessageDigest; 25 import java.security.NoSuchAlgorithmException; 26 import java.util.ArrayList; 27 28 /** 29 * ApkVerityBuilder builds the APK verity tree and the verity header, which will be used by the 30 * kernel to verity the APK content on access. 31 * 32 * <p>Unlike a regular Merkle tree, APK verity tree does not cover the content fully. Due to 33 * the existing APK format, it has to skip APK Signing Block and also has some special treatment for 34 * the "Central Directory offset" field of ZIP End of Central Directory. 35 * 36 * @hide 37 */ 38 abstract class ApkVerityBuilder { 39 private ApkVerityBuilder() {} 40 41 private static final int CHUNK_SIZE_BYTES = 4096; // Typical Linux block size 42 private static final int DIGEST_SIZE_BYTES = 32; // SHA-256 size 43 private static final int FSVERITY_HEADER_SIZE_BYTES = 64; 44 private static final int ZIP_EOCD_CENTRAL_DIR_OFFSET_FIELD_SIZE = 4; 45 private static final int ZIP_EOCD_CENTRAL_DIR_OFFSET_FIELD_OFFSET = 16; 46 private static final String JCA_DIGEST_ALGORITHM = "SHA-256"; 47 private static final byte[] DEFAULT_SALT = new byte[8]; 48 49 static class ApkVerityResult { 50 public final ByteBuffer fsverityData; 51 public final byte[] rootHash; 52 53 ApkVerityResult(ByteBuffer fsverityData, byte[] rootHash) { 54 this.fsverityData = fsverityData; 55 this.rootHash = rootHash; 56 } 57 } 58 59 /** 60 * Generates fsverity metadata and the Merkle tree into the {@link ByteBuffer} created by the 61 * {@link ByteBufferFactory}. The bytes layout in the buffer will be used by the kernel and is 62 * ready to be appended to the target file to set up fsverity. For fsverity to work, this data 63 * must be placed at the next page boundary, and the caller must add additional padding in that 64 * case. 65 * 66 * @return ApkVerityResult containing the fsverity data and the root hash of the Merkle tree. 67 */ 68 static ApkVerityResult generateApkVerity(RandomAccessFile apk, 69 SignatureInfo signatureInfo, ByteBufferFactory bufferFactory) 70 throws IOException, SecurityException, NoSuchAlgorithmException, DigestException { 71 long signingBlockSize = 72 signatureInfo.centralDirOffset - signatureInfo.apkSigningBlockOffset; 73 long dataSize = apk.length() - signingBlockSize; 74 int[] levelOffset = calculateVerityLevelOffset(dataSize); 75 int merkleTreeSize = levelOffset[levelOffset.length - 1]; 76 77 ByteBuffer output = bufferFactory.create( 78 merkleTreeSize 79 + CHUNK_SIZE_BYTES); // maximum size of fsverity metadata 80 output.order(ByteOrder.LITTLE_ENDIAN); 81 82 ByteBuffer tree = slice(output, 0, merkleTreeSize); 83 ByteBuffer header = slice(output, merkleTreeSize, 84 merkleTreeSize + FSVERITY_HEADER_SIZE_BYTES); 85 ByteBuffer extensions = slice(output, merkleTreeSize + FSVERITY_HEADER_SIZE_BYTES, 86 merkleTreeSize + CHUNK_SIZE_BYTES); 87 byte[] apkDigestBytes = new byte[DIGEST_SIZE_BYTES]; 88 ByteBuffer apkDigest = ByteBuffer.wrap(apkDigestBytes); 89 apkDigest.order(ByteOrder.LITTLE_ENDIAN); 90 91 // NB: Buffer limit is set inside once finished. 92 calculateFsveritySignatureInternal(apk, signatureInfo, tree, apkDigest, header, extensions); 93 94 // Put the reverse offset to fs-verity header at the end. 95 output.position(merkleTreeSize + FSVERITY_HEADER_SIZE_BYTES + extensions.limit()); 96 output.putInt(FSVERITY_HEADER_SIZE_BYTES + extensions.limit() 97 + 4); // size of this integer right before EOF 98 output.flip(); 99 100 return new ApkVerityResult(output, apkDigestBytes); 101 } 102 103 /** 104 * Calculates the fsverity root hash for integrity measurement. This needs to be consistent to 105 * what kernel returns. 106 */ 107 static byte[] generateFsverityRootHash(RandomAccessFile apk, ByteBuffer apkDigest, 108 SignatureInfo signatureInfo) 109 throws NoSuchAlgorithmException, DigestException, IOException { 110 ByteBuffer verityBlock = ByteBuffer.allocate(CHUNK_SIZE_BYTES) 111 .order(ByteOrder.LITTLE_ENDIAN); 112 ByteBuffer header = slice(verityBlock, 0, FSVERITY_HEADER_SIZE_BYTES); 113 ByteBuffer extensions = slice(verityBlock, FSVERITY_HEADER_SIZE_BYTES, 114 CHUNK_SIZE_BYTES - FSVERITY_HEADER_SIZE_BYTES); 115 116 calculateFsveritySignatureInternal(apk, signatureInfo, null, null, header, extensions); 117 118 MessageDigest md = MessageDigest.getInstance(JCA_DIGEST_ALGORITHM); 119 md.update(header); 120 md.update(extensions); 121 md.update(apkDigest); 122 return md.digest(); 123 } 124 125 /** 126 * Internal method to generate various parts of FSVerity constructs, including the header, 127 * extensions, Merkle tree, and the tree's root hash. The output buffer is flipped to the 128 * generated data size and is readey for consuming. 129 */ 130 private static void calculateFsveritySignatureInternal( 131 RandomAccessFile apk, SignatureInfo signatureInfo, ByteBuffer treeOutput, 132 ByteBuffer rootHashOutput, ByteBuffer headerOutput, ByteBuffer extensionsOutput) 133 throws IOException, NoSuchAlgorithmException, DigestException { 134 assertSigningBlockAlignedAndHasFullPages(signatureInfo); 135 long signingBlockSize = 136 signatureInfo.centralDirOffset - signatureInfo.apkSigningBlockOffset; 137 long dataSize = apk.length() - signingBlockSize; 138 int[] levelOffset = calculateVerityLevelOffset(dataSize); 139 140 if (treeOutput != null) { 141 byte[] apkRootHash = generateApkVerityTree(apk, signatureInfo, DEFAULT_SALT, 142 levelOffset, treeOutput); 143 if (rootHashOutput != null) { 144 rootHashOutput.put(apkRootHash); 145 rootHashOutput.flip(); 146 } 147 } 148 149 if (headerOutput != null) { 150 headerOutput.order(ByteOrder.LITTLE_ENDIAN); 151 generateFsverityHeader(headerOutput, apk.length(), levelOffset.length - 1, 152 DEFAULT_SALT); 153 } 154 155 if (extensionsOutput != null) { 156 extensionsOutput.order(ByteOrder.LITTLE_ENDIAN); 157 generateFsverityExtensions(extensionsOutput, signatureInfo.apkSigningBlockOffset, 158 signingBlockSize, signatureInfo.eocdOffset); 159 } 160 } 161 162 /** 163 * A helper class to consume and digest data by block continuously, and write into a buffer. 164 */ 165 private static class BufferedDigester implements DataDigester { 166 /** Amount of the data to digest in each cycle before writting out the digest. */ 167 private static final int BUFFER_SIZE = CHUNK_SIZE_BYTES; 168 169 /** 170 * Amount of data the {@link MessageDigest} has consumed since the last reset. This must be 171 * always less than BUFFER_SIZE since {@link MessageDigest} is reset whenever it has 172 * consumed BUFFER_SIZE of data. 173 */ 174 private int mBytesDigestedSinceReset; 175 176 /** The final output {@link ByteBuffer} to write the digest to sequentially. */ 177 private final ByteBuffer mOutput; 178 179 private final MessageDigest mMd; 180 private final byte[] mDigestBuffer = new byte[DIGEST_SIZE_BYTES]; 181 private final byte[] mSalt; 182 183 private BufferedDigester(byte[] salt, ByteBuffer output) throws NoSuchAlgorithmException { 184 mSalt = salt; 185 mOutput = output.slice(); 186 mMd = MessageDigest.getInstance(JCA_DIGEST_ALGORITHM); 187 mMd.update(mSalt); 188 mBytesDigestedSinceReset = 0; 189 } 190 191 /** 192 * Consumes and digests data up to BUFFER_SIZE (may continue from the previous remaining), 193 * then writes the final digest to the output buffer. Repeat until all data are consumed. 194 * If the last consumption is not enough for BUFFER_SIZE, the state will stay and future 195 * consumption will continuous from there. 196 */ 197 @Override 198 public void consume(ByteBuffer buffer) throws DigestException { 199 int offset = buffer.position(); 200 int remaining = buffer.remaining(); 201 while (remaining > 0) { 202 int allowance = (int) Math.min(remaining, BUFFER_SIZE - mBytesDigestedSinceReset); 203 // Optimization: set the buffer limit to avoid allocating a new ByteBuffer object. 204 buffer.limit(buffer.position() + allowance); 205 mMd.update(buffer); 206 offset += allowance; 207 remaining -= allowance; 208 mBytesDigestedSinceReset += allowance; 209 210 if (mBytesDigestedSinceReset == BUFFER_SIZE) { 211 mMd.digest(mDigestBuffer, 0, mDigestBuffer.length); 212 mOutput.put(mDigestBuffer); 213 // After digest, MessageDigest resets automatically, so no need to reset again. 214 mMd.update(mSalt); 215 mBytesDigestedSinceReset = 0; 216 } 217 } 218 } 219 220 public void assertEmptyBuffer() throws DigestException { 221 if (mBytesDigestedSinceReset != 0) { 222 throw new IllegalStateException("Buffer is not empty: " + mBytesDigestedSinceReset); 223 } 224 } 225 226 private void fillUpLastOutputChunk() { 227 int lastBlockSize = (int) (mOutput.position() % BUFFER_SIZE); 228 if (lastBlockSize == 0) { 229 return; 230 } 231 mOutput.put(ByteBuffer.allocate(BUFFER_SIZE - lastBlockSize)); 232 } 233 } 234 235 /** 236 * Digest the source by chunk in the given range. If the last chunk is not a full chunk, 237 * digest the remaining. 238 */ 239 private static void consumeByChunk(DataDigester digester, DataSource source, int chunkSize) 240 throws IOException, DigestException { 241 long inputRemaining = source.size(); 242 long inputOffset = 0; 243 while (inputRemaining > 0) { 244 int size = (int) Math.min(inputRemaining, chunkSize); 245 source.feedIntoDataDigester(digester, inputOffset, size); 246 inputOffset += size; 247 inputRemaining -= size; 248 } 249 } 250 251 // Rationale: 1) 1 MB should fit in memory space on all devices. 2) It is not too granular 252 // thus the syscall overhead is not too big. 253 private static final int MMAP_REGION_SIZE_BYTES = 1024 * 1024; 254 255 private static void generateApkVerityDigestAtLeafLevel(RandomAccessFile apk, 256 SignatureInfo signatureInfo, byte[] salt, ByteBuffer output) 257 throws IOException, NoSuchAlgorithmException, DigestException { 258 BufferedDigester digester = new BufferedDigester(salt, output); 259 260 // 1. Digest from the beginning of the file, until APK Signing Block is reached. 261 consumeByChunk(digester, 262 new MemoryMappedFileDataSource(apk.getFD(), 0, signatureInfo.apkSigningBlockOffset), 263 MMAP_REGION_SIZE_BYTES); 264 265 // 2. Skip APK Signing Block and continue digesting, until the Central Directory offset 266 // field in EoCD is reached. 267 long eocdCdOffsetFieldPosition = 268 signatureInfo.eocdOffset + ZIP_EOCD_CENTRAL_DIR_OFFSET_FIELD_OFFSET; 269 consumeByChunk(digester, 270 new MemoryMappedFileDataSource(apk.getFD(), signatureInfo.centralDirOffset, 271 eocdCdOffsetFieldPosition - signatureInfo.centralDirOffset), 272 MMAP_REGION_SIZE_BYTES); 273 274 // 3. Consume offset of Signing Block as an alternative EoCD. 275 ByteBuffer alternativeCentralDirOffset = ByteBuffer.allocate( 276 ZIP_EOCD_CENTRAL_DIR_OFFSET_FIELD_SIZE).order(ByteOrder.LITTLE_ENDIAN); 277 alternativeCentralDirOffset.putInt(Math.toIntExact(signatureInfo.apkSigningBlockOffset)); 278 alternativeCentralDirOffset.flip(); 279 digester.consume(alternativeCentralDirOffset); 280 281 // 4. Read from end of the Central Directory offset field in EoCD to the end of the file. 282 long offsetAfterEocdCdOffsetField = 283 eocdCdOffsetFieldPosition + ZIP_EOCD_CENTRAL_DIR_OFFSET_FIELD_SIZE; 284 consumeByChunk(digester, 285 new MemoryMappedFileDataSource(apk.getFD(), offsetAfterEocdCdOffsetField, 286 apk.length() - offsetAfterEocdCdOffsetField), 287 MMAP_REGION_SIZE_BYTES); 288 289 // 5. Pad 0s up to the nearest 4096-byte block before hashing. 290 int lastIncompleteChunkSize = (int) (apk.length() % CHUNK_SIZE_BYTES); 291 if (lastIncompleteChunkSize != 0) { 292 digester.consume(ByteBuffer.allocate(CHUNK_SIZE_BYTES - lastIncompleteChunkSize)); 293 } 294 digester.assertEmptyBuffer(); 295 296 // 6. Fill up the rest of buffer with 0s. 297 digester.fillUpLastOutputChunk(); 298 } 299 300 private static byte[] generateApkVerityTree(RandomAccessFile apk, SignatureInfo signatureInfo, 301 byte[] salt, int[] levelOffset, ByteBuffer output) 302 throws IOException, NoSuchAlgorithmException, DigestException { 303 // 1. Digest the apk to generate the leaf level hashes. 304 generateApkVerityDigestAtLeafLevel(apk, signatureInfo, salt, slice(output, 305 levelOffset[levelOffset.length - 2], levelOffset[levelOffset.length - 1])); 306 307 // 2. Digest the lower level hashes bottom up. 308 for (int level = levelOffset.length - 3; level >= 0; level--) { 309 ByteBuffer inputBuffer = slice(output, levelOffset[level + 1], levelOffset[level + 2]); 310 ByteBuffer outputBuffer = slice(output, levelOffset[level], levelOffset[level + 1]); 311 312 DataSource source = new ByteBufferDataSource(inputBuffer); 313 BufferedDigester digester = new BufferedDigester(salt, outputBuffer); 314 consumeByChunk(digester, source, CHUNK_SIZE_BYTES); 315 digester.assertEmptyBuffer(); 316 digester.fillUpLastOutputChunk(); 317 } 318 319 // 3. Digest the first block (i.e. first level) to generate the root hash. 320 byte[] rootHash = new byte[DIGEST_SIZE_BYTES]; 321 BufferedDigester digester = new BufferedDigester(salt, ByteBuffer.wrap(rootHash)); 322 digester.consume(slice(output, 0, CHUNK_SIZE_BYTES)); 323 digester.assertEmptyBuffer(); 324 return rootHash; 325 } 326 327 private static ByteBuffer generateFsverityHeader(ByteBuffer buffer, long fileSize, int depth, 328 byte[] salt) { 329 if (salt.length != 8) { 330 throw new IllegalArgumentException("salt is not 8 bytes long"); 331 } 332 333 // TODO(b/30972906): update the reference when there is a better one in public. 334 buffer.put("TrueBrew".getBytes()); // magic 335 336 buffer.put((byte) 1); // major version 337 buffer.put((byte) 0); // minor version 338 buffer.put((byte) 12); // log2(block-size): log2(4096) 339 buffer.put((byte) 7); // log2(leaves-per-node): log2(4096 / 32) 340 341 buffer.putShort((short) 1); // meta algorithm, SHA256 == 1 342 buffer.putShort((short) 1); // data algorithm, SHA256 == 1 343 344 buffer.putInt(0); // flags 345 buffer.putInt(0); // reserved 346 347 buffer.putLong(fileSize); // original file size 348 349 buffer.put((byte) 2); // authenticated extension count 350 buffer.put((byte) 0); // unauthenticated extension count 351 buffer.put(salt); // salt (8 bytes) 352 skip(buffer, 22); // reserved 353 354 buffer.flip(); 355 return buffer; 356 } 357 358 private static ByteBuffer generateFsverityExtensions(ByteBuffer buffer, long signingBlockOffset, 359 long signingBlockSize, long eocdOffset) { 360 // Snapshot of the FSVerity structs (subject to change once upstreamed). 361 // 362 // struct fsverity_extension_elide { 363 // __le64 offset; 364 // __le64 length; 365 // } 366 // 367 // struct fsverity_extension_patch { 368 // __le64 offset; 369 // u8 databytes[]; 370 // }; 371 372 final int kSizeOfFsverityExtensionHeader = 8; 373 final int kExtensionSizeAlignment = 8; 374 375 { 376 // struct fsverity_extension #1 377 final int kSizeOfFsverityElidedExtension = 16; 378 379 // First field is total size of extension, padded to 64-bit alignment 380 buffer.putInt(kSizeOfFsverityExtensionHeader + kSizeOfFsverityElidedExtension); 381 buffer.putShort((short) 1); // ID of elide extension 382 skip(buffer, 2); // reserved 383 384 // struct fsverity_extension_elide 385 buffer.putLong(signingBlockOffset); 386 buffer.putLong(signingBlockSize); 387 } 388 389 { 390 // struct fsverity_extension #2 391 final int kTotalSize = kSizeOfFsverityExtensionHeader 392 + 8 // offset size 393 + ZIP_EOCD_CENTRAL_DIR_OFFSET_FIELD_SIZE; 394 395 buffer.putInt(kTotalSize); // Total size of extension, padded to 64-bit alignment 396 buffer.putShort((short) 2); // ID of patch extension 397 skip(buffer, 2); // reserved 398 399 // struct fsverity_extension_patch 400 buffer.putLong(eocdOffset + ZIP_EOCD_CENTRAL_DIR_OFFSET_FIELD_OFFSET); // offset 401 buffer.putInt(Math.toIntExact(signingBlockOffset)); // databytes 402 403 // The extension needs to be 0-padded at the end, since the length may not be multiple 404 // of 8. 405 int kPadding = kExtensionSizeAlignment - kTotalSize % kExtensionSizeAlignment; 406 if (kPadding == kExtensionSizeAlignment) { 407 kPadding = 0; 408 } 409 skip(buffer, kPadding); // padding 410 } 411 412 buffer.flip(); 413 return buffer; 414 } 415 416 /** 417 * Returns an array of summed area table of level size in the verity tree. In other words, the 418 * returned array is offset of each level in the verity tree file format, plus an additional 419 * offset of the next non-existing level (i.e. end of the last level + 1). Thus the array size 420 * is level + 1. Thus, the returned array is guarantee to have at least 2 elements. 421 */ 422 private static int[] calculateVerityLevelOffset(long fileSize) { 423 ArrayList<Long> levelSize = new ArrayList<>(); 424 while (true) { 425 long levelDigestSize = divideRoundup(fileSize, CHUNK_SIZE_BYTES) * DIGEST_SIZE_BYTES; 426 long chunksSize = CHUNK_SIZE_BYTES * divideRoundup(levelDigestSize, CHUNK_SIZE_BYTES); 427 levelSize.add(chunksSize); 428 if (levelDigestSize <= CHUNK_SIZE_BYTES) { 429 break; 430 } 431 fileSize = levelDigestSize; 432 } 433 434 // Reverse and convert to summed area table. 435 int[] levelOffset = new int[levelSize.size() + 1]; 436 levelOffset[0] = 0; 437 for (int i = 0; i < levelSize.size(); i++) { 438 // We don't support verity tree if it is larger then Integer.MAX_VALUE. 439 levelOffset[i + 1] = levelOffset[i] 440 + Math.toIntExact(levelSize.get(levelSize.size() - i - 1)); 441 } 442 return levelOffset; 443 } 444 445 private static void assertSigningBlockAlignedAndHasFullPages(SignatureInfo signatureInfo) { 446 if (signatureInfo.apkSigningBlockOffset % CHUNK_SIZE_BYTES != 0) { 447 throw new IllegalArgumentException( 448 "APK Signing Block does not start at the page boundary: " 449 + signatureInfo.apkSigningBlockOffset); 450 } 451 452 if ((signatureInfo.centralDirOffset - signatureInfo.apkSigningBlockOffset) 453 % CHUNK_SIZE_BYTES != 0) { 454 throw new IllegalArgumentException( 455 "Size of APK Signing Block is not a multiple of 4096: " 456 + (signatureInfo.centralDirOffset - signatureInfo.apkSigningBlockOffset)); 457 } 458 } 459 460 /** Returns a slice of the buffer which shares content with the provided buffer. */ 461 private static ByteBuffer slice(ByteBuffer buffer, int begin, int end) { 462 ByteBuffer b = buffer.duplicate(); 463 b.position(0); // to ensure position <= limit invariant. 464 b.limit(end); 465 b.position(begin); 466 return b.slice(); 467 } 468 469 /** Skip the {@code ByteBuffer} position by {@code bytes}. */ 470 private static void skip(ByteBuffer buffer, int bytes) { 471 buffer.position(buffer.position() + bytes); 472 } 473 474 /** Divides a number and round up to the closest integer. */ 475 private static long divideRoundup(long dividend, long divisor) { 476 return (dividend + divisor - 1) / divisor; 477 } 478 } 479
