verity/VerityVerifier.java

   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 }