1 /* 2 * Copyright (C) 2014 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.verity; 18 19 import java.io.File; 20 import java.io.RandomAccessFile; 21 import java.nio.ByteBuffer; 22 import java.nio.ByteOrder; 23 import java.lang.Math; 24 import java.lang.Process; 25 import java.lang.Runtime; 26 import java.math.BigInteger; 27 import java.security.KeyFactory; 28 import java.security.MessageDigest; 29 import java.security.PublicKey; 30 import java.security.Security; 31 import java.security.cert.X509Certificate; 32 import java.security.interfaces.RSAPublicKey; 33 import java.security.spec.RSAPublicKeySpec; 34 import java.util.ArrayList; 35 import java.util.Arrays; 36 import javax.xml.bind.DatatypeConverter; 37 import org.bouncycastle.jce.provider.BouncyCastleProvider; 38 39 public class VerityVerifier { 40 41 private ArrayList<Integer> hashBlocksLevel; 42 private byte[] hashTree; 43 private byte[] rootHash; 44 private byte[] salt; 45 private byte[] signature; 46 private byte[] table; 47 private File image; 48 private int blockSize; 49 private int hashBlockSize; 50 private int hashOffsetForData; 51 private int hashSize; 52 private int hashTreeSize; 53 private long hashStart; 54 private long imageSize; 55 private MessageDigest digest; 56 57 private static final int EXT4_SB_MAGIC = 0xEF53; 58 private static final int EXT4_SB_OFFSET = 0x400; 59 private static final int EXT4_SB_OFFSET_MAGIC = EXT4_SB_OFFSET + 0x38; 60 private static final int EXT4_SB_OFFSET_LOG_BLOCK_SIZE = EXT4_SB_OFFSET + 0x18; 61 private static final int EXT4_SB_OFFSET_BLOCKS_COUNT_LO = EXT4_SB_OFFSET + 0x4; 62 private static final int EXT4_SB_OFFSET_BLOCKS_COUNT_HI = EXT4_SB_OFFSET + 0x150; 63 private static final int MINCRYPT_OFFSET_MODULUS = 0x8; 64 private static final int MINCRYPT_OFFSET_EXPONENT = 0x208; 65 private static final int MINCRYPT_MODULUS_SIZE = 0x100; 66 private static final int MINCRYPT_EXPONENT_SIZE = 0x4; 67 private static final int VERITY_FIELDS = 10; 68 private static final int VERITY_MAGIC = 0xB001B001; 69 private static final int VERITY_SIGNATURE_SIZE = 256; 70 private static final int VERITY_VERSION = 0; 71 72 public VerityVerifier(String fname) throws Exception { 73 digest = MessageDigest.getInstance("SHA-256"); 74 hashSize = digest.getDigestLength(); 75 hashBlocksLevel = new ArrayList<Integer>(); 76 hashTreeSize = -1; 77 openImage(fname); 78 readVerityData(); 79 } 80 81 /** 82 * Reverses the order of bytes in a byte array 83 * @param value Byte array to reverse 84 */ 85 private static byte[] reverse(byte[] value) { 86 for (int i = 0; i < value.length / 2; i++) { 87 byte tmp = value[i]; 88 value[i] = value[value.length - i - 1]; 89 value[value.length - i - 1] = tmp; 90 } 91 92 return value; 93 } 94 95 /** 96 * Converts a 4-byte little endian value to a Java integer 97 * @param value Little endian integer to convert 98 */ 99 private static int fromle(int value) { 100 byte[] bytes = ByteBuffer.allocate(4).putInt(value).array(); 101 return ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN).getInt(); 102 } 103 104 /** 105 * Converts a 2-byte little endian value to Java a integer 106 * @param value Little endian short to convert 107 */ 108 private static int fromle(short value) { 109 return fromle(value << 16); 110 } 111 112 /** 113 * Reads a 2048-bit RSA public key saved in mincrypt format, and returns 114 * a Java PublicKey for it. 115 * @param fname Name of the mincrypt public key file 116 */ 117 private static PublicKey getMincryptPublicKey(String fname) throws Exception { 118 try (RandomAccessFile key = new RandomAccessFile(fname, "r")) { 119 byte[] binaryMod = new byte[MINCRYPT_MODULUS_SIZE]; 120 byte[] binaryExp = new byte[MINCRYPT_EXPONENT_SIZE]; 121 122 key.seek(MINCRYPT_OFFSET_MODULUS); 123 key.readFully(binaryMod); 124 125 key.seek(MINCRYPT_OFFSET_EXPONENT); 126 key.readFully(binaryExp); 127 128 BigInteger modulus = new BigInteger(1, reverse(binaryMod)); 129 BigInteger exponent = new BigInteger(1, reverse(binaryExp)); 130 131 RSAPublicKeySpec spec = new RSAPublicKeySpec(modulus, exponent); 132 KeyFactory factory = KeyFactory.getInstance("RSA"); 133 return factory.generatePublic(spec); 134 } 135 } 136 137 /** 138 * Unsparses a sparse image into a temporary file and returns a 139 * handle to the file 140 * @param fname Path to a sparse image file 141 */ 142 private void openImage(String fname) throws Exception { 143 image = File.createTempFile("system", ".raw"); 144 image.deleteOnExit(); 145 146 Process p = Runtime.getRuntime().exec("simg2img " + fname + 147 " " + image.getAbsoluteFile()); 148 149 p.waitFor(); 150 if (p.exitValue() != 0) { 151 throw new IllegalArgumentException("Invalid image: failed to unsparse"); 152 } 153 } 154 155 /** 156 * Reads the ext4 superblock and calculates the size of the system image, 157 * after which we should find the verity metadata 158 * @param img File handle to the image file 159 */ 160 public static long getMetadataPosition(RandomAccessFile img) 161 throws Exception { 162 img.seek(EXT4_SB_OFFSET_MAGIC); 163 int magic = fromle(img.readShort()); 164 165 if (magic != EXT4_SB_MAGIC) { 166 throw new IllegalArgumentException("Invalid image: not a valid ext4 image"); 167 } 168 169 img.seek(EXT4_SB_OFFSET_BLOCKS_COUNT_LO); 170 long blocksCountLo = fromle(img.readInt()); 171 172 img.seek(EXT4_SB_OFFSET_LOG_BLOCK_SIZE); 173 long logBlockSize = fromle(img.readInt()); 174 175 img.seek(EXT4_SB_OFFSET_BLOCKS_COUNT_HI); 176 long blocksCountHi = fromle(img.readInt()); 177 178 long blockSizeBytes = 1L << (10 + logBlockSize); 179 long blockCount = (blocksCountHi << 32) + blocksCountLo; 180 return blockSizeBytes * blockCount; 181 } 182 183 /** 184 * Calculates the size of the verity hash tree based on the image size 185 */ 186 private int calculateHashTreeSize() { 187 if (hashTreeSize > 0) { 188 return hashTreeSize; 189 } 190 191 int totalBlocks = 0; 192 int hashes = (int) (imageSize / blockSize); 193 194 hashBlocksLevel.clear(); 195 196 do { 197 hashBlocksLevel.add(0, hashes); 198 199 int hashBlocks = 200 (int) Math.ceil((double) hashes * hashSize / hashBlockSize); 201 202 totalBlocks += hashBlocks; 203 204 hashes = hashBlocks; 205 } while (hashes > 1); 206 207 hashTreeSize = totalBlocks * hashBlockSize; 208 return hashTreeSize; 209 } 210 211 /** 212 * Parses the verity mapping table and reads the hash tree from 213 * the image file 214 * @param img Handle to the image file 215 * @param table Verity mapping table 216 */ 217 private void readHashTree(RandomAccessFile img, byte[] table) 218 throws Exception { 219 String tableStr = new String(table); 220 String[] fields = tableStr.split(" "); 221 222 if (fields.length != VERITY_FIELDS) { 223 throw new IllegalArgumentException("Invalid image: unexpected number of fields " 224 + "in verity mapping table (" + fields.length + ")"); 225 } 226 227 String hashVersion = fields[0]; 228 229 if (!"1".equals(hashVersion)) { 230 throw new IllegalArgumentException("Invalid image: unsupported hash format"); 231 } 232 233 String alg = fields[7]; 234 235 if (!"sha256".equals(alg)) { 236 throw new IllegalArgumentException("Invalid image: unsupported hash algorithm"); 237 } 238 239 blockSize = Integer.parseInt(fields[3]); 240 hashBlockSize = Integer.parseInt(fields[4]); 241 242 int blocks = Integer.parseInt(fields[5]); 243 int start = Integer.parseInt(fields[6]); 244 245 if (imageSize != (long) blocks * blockSize) { 246 throw new IllegalArgumentException("Invalid image: size mismatch in mapping " 247 + "table"); 248 } 249 250 rootHash = DatatypeConverter.parseHexBinary(fields[8]); 251 salt = DatatypeConverter.parseHexBinary(fields[9]); 252 253 hashStart = (long) start * blockSize; 254 img.seek(hashStart); 255 256 int treeSize = calculateHashTreeSize(); 257 258 hashTree = new byte[treeSize]; 259 img.readFully(hashTree); 260 } 261 262 /** 263 * Reads verity data from the image file 264 */ 265 private void readVerityData() throws Exception { 266 try (RandomAccessFile img = new RandomAccessFile(image, "r")) { 267 imageSize = getMetadataPosition(img); 268 img.seek(imageSize); 269 270 int magic = fromle(img.readInt()); 271 272 if (magic != VERITY_MAGIC) { 273 throw new IllegalArgumentException("Invalid image: verity metadata not found"); 274 } 275 276 int version = fromle(img.readInt()); 277 278 if (version != VERITY_VERSION) { 279 throw new IllegalArgumentException("Invalid image: unknown metadata version"); 280 } 281 282 signature = new byte[VERITY_SIGNATURE_SIZE]; 283 img.readFully(signature); 284 285 int tableSize = fromle(img.readInt()); 286 287 table = new byte[tableSize]; 288 img.readFully(table); 289 290 readHashTree(img, table); 291 } 292 } 293 294 /** 295 * Reads and validates verity metadata, and checks the signature against the 296 * given public key 297 * @param key Public key to use for signature verification 298 */ 299 public boolean verifyMetaData(PublicKey key) 300 throws Exception { 301 return Utils.verify(key, table, signature, 302 Utils.getSignatureAlgorithmIdentifier(key)); 303 } 304 305 /** 306 * Hashes a block of data using a salt and checks of the results are expected 307 * @param hash The expected hash value 308 * @param data The data block to check 309 */ 310 private boolean checkBlock(byte[] hash, byte[] data) { 311 digest.reset(); 312 digest.update(salt); 313 digest.update(data); 314 return Arrays.equals(hash, digest.digest()); 315 } 316 317 /** 318 * Verifies the root hash and the first N-1 levels of the hash tree 319 */ 320 private boolean verifyHashTree() throws Exception { 321 int hashOffset = 0; 322 int dataOffset = hashBlockSize; 323 324 if (!checkBlock(rootHash, Arrays.copyOfRange(hashTree, 0, hashBlockSize))) { 325 System.err.println("Root hash mismatch"); 326 return false; 327 } 328 329 for (int level = 0; level < hashBlocksLevel.size() - 1; level++) { 330 int blocks = hashBlocksLevel.get(level); 331 332 for (int i = 0; i < blocks; i++) { 333 byte[] hashBlock = Arrays.copyOfRange(hashTree, 334 hashOffset + i * hashSize, 335 hashOffset + i * hashSize + hashSize); 336 337 byte[] dataBlock = Arrays.copyOfRange(hashTree, 338 dataOffset + i * hashBlockSize, 339 dataOffset + i * hashBlockSize + hashBlockSize); 340 341 if (!checkBlock(hashBlock, dataBlock)) { 342 System.err.printf("Hash mismatch at tree level %d, block %d\n", level, i); 343 return false; 344 } 345 } 346 347 hashOffset = dataOffset; 348 hashOffsetForData = dataOffset; 349 dataOffset += blocks * hashBlockSize; 350 } 351 352 return true; 353 } 354 355 /** 356 * Validates the image against the hash tree 357 */ 358 public boolean verifyData() throws Exception { 359 if (!verifyHashTree()) { 360 return false; 361 } 362 363 try (RandomAccessFile img = new RandomAccessFile(image, "r")) { 364 byte[] dataBlock = new byte[blockSize]; 365 int hashOffset = hashOffsetForData; 366 367 for (int i = 0; (long) i * blockSize < imageSize; i++) { 368 byte[] hashBlock = Arrays.copyOfRange(hashTree, 369 hashOffset + i * hashSize, 370 hashOffset + i * hashSize + hashSize); 371 372 img.readFully(dataBlock); 373 374 if (!checkBlock(hashBlock, dataBlock)) { 375 System.err.printf("Hash mismatch at block %d\n", i); 376 return false; 377 } 378 } 379 } 380 381 return true; 382 } 383 384 /** 385 * Verifies the integrity of the image and the verity metadata 386 * @param key Public key to use for signature verification 387 */ 388 public boolean verify(PublicKey key) throws Exception { 389 return (verifyMetaData(key) && verifyData()); 390 } 391 392 public static void main(String[] args) throws Exception { 393 Security.addProvider(new BouncyCastleProvider()); 394 PublicKey key = null; 395 396 if (args.length == 3 && "-mincrypt".equals(args[1])) { 397 key = getMincryptPublicKey(args[2]); 398 } else if (args.length == 2) { 399 X509Certificate cert = Utils.loadPEMCertificate(args[1]); 400 key = cert.getPublicKey(); 401 } else { 402 System.err.println("Usage: VerityVerifier <sparse.img> <certificate.x509.pem> | -mincrypt <mincrypt_key>"); 403 System.exit(1); 404 } 405 406 VerityVerifier verifier = new VerityVerifier(args[0]); 407 408 try { 409 if (verifier.verify(key)) { 410 System.err.println("Signature is VALID"); 411 System.exit(0); 412 } 413 } catch (Exception e) { 414 e.printStackTrace(System.err); 415 } 416 417 System.exit(1); 418 } 419 } 420
