DO NOT MERGE verity_verifier: Support verifying images with FEC.

The current VerityVerifier.jar cannot verify verity images with FEC
metadata (since N). Replace it with a new verity verifier that uses
libfec to parse and verify verity metadata.

It accepts the same command line arguments as the old verity_verifier
script.

Usage: verity_verifier <image> -mincrypt <verity_key>
  image       the image file (raw or sparse image) to be verified
  verity_key  the verity key in mincrypt format (/verity_key on device)

Note: this is a backport of commit
bb634ff8dab6327bd38eadee22d5f8ec9d3940d0. It uses the mincrypt headers
and functions instead.

Bug: 32173582
Test: $ verity_verifier $OUT/system.img -mincrypt $OUT/root/verity_key
      VERIFIED
Change-Id: I8624973715dcd0f6d89d408c1c97bf584b50ce06
(cherry picked from commit bb634ff8dab6327bd38eadee22d5f8ec9d3940d0)

5 files changed, 137 insertions, 439 deletions

diff --git a/verity/Android.mk b/verity/Android.mk
index 7b3d13f3..b4a3ed7a 100644
--- a/verity/Android.mk
+++ b/verity/Android.mk
@@ -22,14 +22,6 @@ LOCAL_SHARED_LIBRARIES := libcrypto-host
 include $(BUILD_HOST_EXECUTABLE)
 
 include $(CLEAR_VARS)
-LOCAL_SRC_FILES := VerityVerifier.java Utils.java
-LOCAL_MODULE := VerityVerifier
-LOCAL_JAR_MANIFEST := VerityVerifier.mf
-LOCAL_MODULE_TAGS := optional
-LOCAL_STATIC_JAVA_LIBRARIES := bouncycastle-host
-include $(BUILD_HOST_JAVA_LIBRARY)
-
-include $(CLEAR_VARS)
 LOCAL_SRC_FILES := VeritySigner.java Utils.java
 LOCAL_MODULE := VeritySigner
 LOCAL_JAR_MANIFEST := VeritySigner.mf
@@ -54,13 +46,26 @@ LOCAL_STATIC_JAVA_LIBRARIES := bouncycastle-host
 include $(BUILD_HOST_JAVA_LIBRARY)
 
 include $(CLEAR_VARS)
-LOCAL_SRC_FILES := verity_verifier
+LOCAL_SRC_FILES := verity_verifier.cpp
 LOCAL_MODULE := verity_verifier
 LOCAL_MODULE_CLASS := EXECUTABLES
+LOCAL_MODULE_HOST_OS := linux
 LOCAL_IS_HOST_MODULE := true
 LOCAL_MODULE_TAGS := optional
-LOCAL_REQUIRED_MODULES := VerityVerifier
-include $(BUILD_PREBUILT)
+LOCAL_SANITIZE := integer
+LOCAL_STATIC_LIBRARIES := \
+    libfec_host \
+    libfec_rs_host \
+    libmincrypt \
+    libcrypto_static \
+    libext4_utils_host \
+    libsparse_host \
+    libsquashfs_utils_host \
+    libbase \
+    liblog \
+    libz
+LOCAL_CFLAGS := -Wall -Werror
+include $(BUILD_HOST_EXECUTABLE)
 
 include $(CLEAR_VARS)
 LOCAL_SRC_FILES := verity_signer
diff --git a/verity/VerityVerifier.java b/verity/VerityVerifier.java
deleted file mode 100644
index 6b3f49ed..00000000
--- a/verity/VerityVerifier.java
+++ /dev/null
@@ -1,419 +0,0 @@
-/*
- * Copyright (C) 2014 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.android.verity;
-
-import java.io.File;
-import java.io.RandomAccessFile;
-import java.nio.ByteBuffer;
-import java.nio.ByteOrder;
-import java.lang.Math;
-import java.lang.Process;
-import java.lang.Runtime;
-import java.math.BigInteger;
-import java.security.KeyFactory;
-import java.security.MessageDigest;
-import java.security.PublicKey;
-import java.security.Security;
-import java.security.cert.X509Certificate;
-import java.security.interfaces.RSAPublicKey;
-import java.security.spec.RSAPublicKeySpec;
-import java.util.ArrayList;
-import java.util.Arrays;
-import javax.xml.bind.DatatypeConverter;
-import org.bouncycastle.jce.provider.BouncyCastleProvider;
-
-public class VerityVerifier {
-
-    private ArrayList<Integer> hashBlocksLevel;
-    private byte[] hashTree;
-    private byte[] rootHash;
-    private byte[] salt;
-    private byte[] signature;
-    private byte[] table;
-    private File image;
-    private int blockSize;
-    private int hashBlockSize;
-    private int hashOffsetForData;
-    private int hashSize;
-    private int hashTreeSize;
-    private long hashStart;
-    private long imageSize;
-    private MessageDigest digest;
-
-    private static final int EXT4_SB_MAGIC = 0xEF53;
-    private static final int EXT4_SB_OFFSET = 0x400;
-    private static final int EXT4_SB_OFFSET_MAGIC = EXT4_SB_OFFSET + 0x38;
-    private static final int EXT4_SB_OFFSET_LOG_BLOCK_SIZE = EXT4_SB_OFFSET + 0x18;
-    private static final int EXT4_SB_OFFSET_BLOCKS_COUNT_LO = EXT4_SB_OFFSET + 0x4;
-    private static final int EXT4_SB_OFFSET_BLOCKS_COUNT_HI = EXT4_SB_OFFSET + 0x150;
-    private static final int MINCRYPT_OFFSET_MODULUS = 0x8;
-    private static final int MINCRYPT_OFFSET_EXPONENT = 0x208;
-    private static final int MINCRYPT_MODULUS_SIZE = 0x100;
-    private static final int MINCRYPT_EXPONENT_SIZE = 0x4;
-    private static final int VERITY_FIELDS = 10;
-    private static final int VERITY_MAGIC = 0xB001B001;
-    private static final int VERITY_SIGNATURE_SIZE = 256;
-    private static final int VERITY_VERSION = 0;
-
-    public VerityVerifier(String fname) throws Exception {
-        digest = MessageDigest.getInstance("SHA-256");
-        hashSize = digest.getDigestLength();
-        hashBlocksLevel = new ArrayList<Integer>();
-        hashTreeSize = -1;
-        openImage(fname);
-        readVerityData();
-    }
-
-    /**
-     * Reverses the order of bytes in a byte array
-     * @param value Byte array to reverse
-     */
-    private static byte[] reverse(byte[] value) {
-        for (int i = 0; i < value.length / 2; i++) {
-            byte tmp = value[i];
-            value[i] = value[value.length - i - 1];
-            value[value.length - i - 1] = tmp;
-        }
-
-        return value;
-    }
-
-    /**
-     * Converts a 4-byte little endian value to a Java integer
-     * @param value Little endian integer to convert
-     */
-    private static int fromle(int value) {
-        byte[] bytes = ByteBuffer.allocate(4).putInt(value).array();
-        return ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN).getInt();
-    }
-
-     /**
-     * Converts a 2-byte little endian value to Java a integer
-     * @param value Little endian short to convert
-     */
-    private static int fromle(short value) {
-        return fromle(value << 16);
-    }
-
-    /**
-     * Reads a 2048-bit RSA public key saved in mincrypt format, and returns
-     * a Java PublicKey for it.
-     * @param fname Name of the mincrypt public key file
-     */
-    private static PublicKey getMincryptPublicKey(String fname) throws Exception {
-        try (RandomAccessFile key = new RandomAccessFile(fname, "r")) {
-            byte[] binaryMod = new byte[MINCRYPT_MODULUS_SIZE];
-            byte[] binaryExp = new byte[MINCRYPT_EXPONENT_SIZE];
-
-            key.seek(MINCRYPT_OFFSET_MODULUS);
-            key.readFully(binaryMod);
-
-            key.seek(MINCRYPT_OFFSET_EXPONENT);
-            key.readFully(binaryExp);
-
-            BigInteger modulus  = new BigInteger(1, reverse(binaryMod));
-            BigInteger exponent = new BigInteger(1, reverse(binaryExp));
-
-            RSAPublicKeySpec spec = new RSAPublicKeySpec(modulus, exponent);
-            KeyFactory factory = KeyFactory.getInstance("RSA");
-            return factory.generatePublic(spec);
-        }
-    }
-
-    /**
-     * Unsparses a sparse image into a temporary file and returns a
-     * handle to the file
-     * @param fname Path to a sparse image file
-     */
-     private void openImage(String fname) throws Exception {
-        image = File.createTempFile("system", ".raw");
-        image.deleteOnExit();
-
-        Process p = Runtime.getRuntime().exec("simg2img " + fname +
-                            " " + image.getAbsoluteFile());
-
-        p.waitFor();
-        if (p.exitValue() != 0) {
-            throw new IllegalArgumentException("Invalid image: failed to unsparse");
-        }
-    }
-
-    /**
-     * Reads the ext4 superblock and calculates the size of the system image,
-     * after which we should find the verity metadata
-     * @param img File handle to the image file
-     */
-    public static long getMetadataPosition(RandomAccessFile img)
-            throws Exception {
-        img.seek(EXT4_SB_OFFSET_MAGIC);
-        int magic = fromle(img.readShort());
-
-        if (magic != EXT4_SB_MAGIC) {
-            throw new IllegalArgumentException("Invalid image: not a valid ext4 image");
-        }
-
-        img.seek(EXT4_SB_OFFSET_BLOCKS_COUNT_LO);
-        long blocksCountLo = fromle(img.readInt());
-
-        img.seek(EXT4_SB_OFFSET_LOG_BLOCK_SIZE);
-        long logBlockSize = fromle(img.readInt());
-
-        img.seek(EXT4_SB_OFFSET_BLOCKS_COUNT_HI);
-        long blocksCountHi = fromle(img.readInt());
-
-        long blockSizeBytes = 1L << (10 + logBlockSize);
-        long blockCount = (blocksCountHi << 32) + blocksCountLo;
-        return blockSizeBytes * blockCount;
-    }
-
-    /**
-     * Calculates the size of the verity hash tree based on the image size
-     */
-    private int calculateHashTreeSize() {
-        if (hashTreeSize > 0) {
-            return hashTreeSize;
-        }
-
-        int totalBlocks = 0;
-        int hashes = (int) (imageSize / blockSize);
-
-        hashBlocksLevel.clear();
-
-        do {
-            hashBlocksLevel.add(0, hashes);
-
-            int hashBlocks =
-                (int) Math.ceil((double) hashes * hashSize / hashBlockSize);
-
-            totalBlocks += hashBlocks;
-
-            hashes = hashBlocks;
-        } while (hashes > 1);
-
-        hashTreeSize = totalBlocks * hashBlockSize;
-        return hashTreeSize;
-    }
-
-    /**
-     * Parses the verity mapping table and reads the hash tree from
-     * the image file
-     * @param img Handle to the image file
-     * @param table Verity mapping table
-     */
-    private void readHashTree(RandomAccessFile img, byte[] table)
-            throws Exception {
-        String tableStr = new String(table);
-        String[] fields = tableStr.split(" ");
-
-        if (fields.length != VERITY_FIELDS) {
-            throw new IllegalArgumentException("Invalid image: unexpected number of fields "
-                    + "in verity mapping table (" + fields.length + ")");
-        }
-
-        String hashVersion = fields[0];
-
-        if (!"1".equals(hashVersion)) {
-            throw new IllegalArgumentException("Invalid image: unsupported hash format");
-        }
-
-        String alg = fields[7];
-
-        if (!"sha256".equals(alg)) {
-            throw new IllegalArgumentException("Invalid image: unsupported hash algorithm");
-        }
-
-        blockSize = Integer.parseInt(fields[3]);
-        hashBlockSize = Integer.parseInt(fields[4]);
-
-        int blocks = Integer.parseInt(fields[5]);
-        int start = Integer.parseInt(fields[6]);
-
-        if (imageSize != (long) blocks * blockSize) {
-            throw new IllegalArgumentException("Invalid image: size mismatch in mapping "
-                    + "table");
-        }
-
-        rootHash = DatatypeConverter.parseHexBinary(fields[8]);
-        salt = DatatypeConverter.parseHexBinary(fields[9]);
-
-        hashStart = (long) start * blockSize;
-        img.seek(hashStart);
-
-        int treeSize = calculateHashTreeSize();
-
-        hashTree = new byte[treeSize];
-        img.readFully(hashTree);
-    }
-
-    /**
-     * Reads verity data from the image file
-     */
-    private void readVerityData() throws Exception {
-        try (RandomAccessFile img = new RandomAccessFile(image, "r")) {
-            imageSize = getMetadataPosition(img);
-            img.seek(imageSize);
-
-            int magic = fromle(img.readInt());
-
-            if (magic != VERITY_MAGIC) {
-                throw new IllegalArgumentException("Invalid image: verity metadata not found");
-            }
-
-            int version = fromle(img.readInt());
-
-            if (version != VERITY_VERSION) {
-                throw new IllegalArgumentException("Invalid image: unknown metadata version");
-            }
-
-            signature = new byte[VERITY_SIGNATURE_SIZE];
-            img.readFully(signature);
-
-            int tableSize = fromle(img.readInt());
-
-            table = new byte[tableSize];
-            img.readFully(table);
-
-            readHashTree(img, table);
-        }
-    }
-
-    /**
-     * Reads and validates verity metadata, and checks the signature against the
-     * given public key
-     * @param key Public key to use for signature verification
-     */
-    public boolean verifyMetaData(PublicKey key)
-            throws Exception {
-       return Utils.verify(key, table, signature,
-                   Utils.getSignatureAlgorithmIdentifier(key));
-    }
-
-    /**
-     * Hashes a block of data using a salt and checks of the results are expected
-     * @param hash The expected hash value
-     * @param data The data block to check
-     */
-    private boolean checkBlock(byte[] hash, byte[] data) {
-        digest.reset();
-        digest.update(salt);
-        digest.update(data);
-        return Arrays.equals(hash, digest.digest());
-    }
-
-    /**
-     * Verifies the root hash and the first N-1 levels of the hash tree
-     */
-    private boolean verifyHashTree() throws Exception {
-        int hashOffset = 0;
-        int dataOffset = hashBlockSize;
-
-        if (!checkBlock(rootHash, Arrays.copyOfRange(hashTree, 0, hashBlockSize))) {
-            System.err.println("Root hash mismatch");
-            return false;
-        }
-
-        for (int level = 0; level < hashBlocksLevel.size() - 1; level++) {
-            int blocks = hashBlocksLevel.get(level);
-
-            for (int i = 0; i < blocks; i++) {
-                byte[] hashBlock = Arrays.copyOfRange(hashTree,
-                        hashOffset + i * hashSize,
-                        hashOffset + i * hashSize + hashSize);
-
-                byte[] dataBlock = Arrays.copyOfRange(hashTree,
-                        dataOffset + i * hashBlockSize,
-                        dataOffset + i * hashBlockSize + hashBlockSize);
-
-                if (!checkBlock(hashBlock, dataBlock)) {
-                    System.err.printf("Hash mismatch at tree level %d, block %d\n", level, i);
-                    return false;
-                }
-            }
-
-            hashOffset = dataOffset;
-            hashOffsetForData = dataOffset;
-            dataOffset += blocks * hashBlockSize;
-        }
-
-        return true;
-    }
-
-    /**
-     * Validates the image against the hash tree
-     */
-    public boolean verifyData() throws Exception {
-        if (!verifyHashTree()) {
-            return false;
-        }
-
-        try (RandomAccessFile img = new RandomAccessFile(image, "r")) {
-            byte[] dataBlock = new byte[blockSize];
-            int hashOffset = hashOffsetForData;
-
-            for (int i = 0; (long) i * blockSize < imageSize; i++) {
-                byte[] hashBlock = Arrays.copyOfRange(hashTree,
-                        hashOffset + i * hashSize,
-                        hashOffset + i * hashSize + hashSize);
-
-                img.readFully(dataBlock);
-
-                if (!checkBlock(hashBlock, dataBlock)) {
-                    System.err.printf("Hash mismatch at block %d\n", i);
-                    return false;
-                }
-            }
-        }
-
-        return true;
-    }
-
-    /**
-     * Verifies the integrity of the image and the verity metadata
-     * @param key Public key to use for signature verification
-     */
-    public boolean verify(PublicKey key) throws Exception {
-        return (verifyMetaData(key) && verifyData());
-    }
-
-    public static void main(String[] args) throws Exception {
-        Security.addProvider(new BouncyCastleProvider());
-        PublicKey key = null;
-
-        if (args.length == 3 && "-mincrypt".equals(args[1])) {
-            key = getMincryptPublicKey(args[2]);
-        } else if (args.length == 2) {
-            X509Certificate cert = Utils.loadPEMCertificate(args[1]);
-            key = cert.getPublicKey();
-        } else {
-            System.err.println("Usage: VerityVerifier <sparse.img> <certificate.x509.pem> | -mincrypt <mincrypt_key>");
-            System.exit(1);
-        }
-
-        VerityVerifier verifier = new VerityVerifier(args[0]);
-
-        try {
-            if (verifier.verify(key)) {
-                System.err.println("Signature is VALID");
-                System.exit(0);
-            }
-        } catch (Exception e) {
-            e.printStackTrace(System.err);
-        }
-
-        System.exit(1);
-    }
-}
diff --git a/verity/VerityVerifier.mf b/verity/VerityVerifier.mf
deleted file mode 100644
index 6118b31c..00000000
--- a/verity/VerityVerifier.mf
+++ /dev/null
@@ -1 +0,0 @@
-Main-Class: com.android.verity.VerityVerifier
diff --git a/verity/verity_verifier b/verity/verity_verifier
deleted file mode 100755
index f145228f..00000000
--- a/verity/verity_verifier
+++ /dev/null
@@ -1,8 +0,0 @@
-#!/bin/sh
-
-# Start-up script for VerityVerifier
-
-VERITYVERIFIER_HOME=`dirname "$0"`
-VERITYVERIFIER_HOME=`dirname "$VERITYVERIFIER_HOME"`
-
-java -Xmx512M -jar "$VERITYVERIFIER_HOME"/framework/VerityVerifier.jar "$@"
diff --git a/verity/verity_verifier.cpp b/verity/verity_verifier.cpp
new file mode 100644
index 00000000..75458916
--- /dev/null
+++ b/verity/verity_verifier.cpp
@@ -0,0 +1,121 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <memory>
+#include <string>
+
+#include <android-base/file.h>
+#include <android-base/test_utils.h>
+#include <android-base/unique_fd.h>
+#include <fec/io.h>
+#include <mincrypt/rsa.h>
+#include <mincrypt/sha.h>
+#include <mincrypt/sha256.h>
+#include <sparse/sparse.h>
+
+static RSAPublicKey* load_key(const char* path) {
+  std::string content;
+  if (!android::base::ReadFileToString(path, &content)) {
+    fprintf(stderr, "Failed to load key from %s\n", path);
+    return nullptr;
+  }
+
+  std::unique_ptr<RSAPublicKey> key(new RSAPublicKey);
+  if (!key) {
+    fprintf(stderr, "Failed to malloc key\n");
+    return nullptr;
+  }
+
+  memcpy(key.get(), content.data(), sizeof(RSAPublicKey));
+
+  if (key->len != RSANUMWORDS) {
+    fprintf(stderr, "Invalid key length %d\n", key->len);
+    return nullptr;
+  }
+
+  return key.release();
+}
+
+static int verify_table(const char* key_path, const uint8_t* signature,
+                        const char* table, uint32_t table_length) {
+  // Hash the table
+  uint8_t hash_buf[SHA256_DIGEST_LENGTH];
+  SHA256_hash(reinterpret_cast<const void*>(table), table_length, hash_buf);
+
+  // Now get the public key from the keyfile
+  std::unique_ptr<RSAPublicKey> key(load_key(key_path));
+  if (!key) {
+    fprintf(stderr, "Couldn't load verity keys\n");
+    return -1;
+  }
+
+  // Verify the result
+  if (!RSA_verify(key.get(), signature, RSANUMBYTES, hash_buf, SHA256_DIGEST_SIZE)) {
+    fprintf(stderr, "Couldn't verify table\n");
+    return -1;
+  }
+
+  return 0;
+}
+
+int main(int argc, char* argv[]) {
+  if (argc != 4 || strcmp(argv[2], "-mincrypt") != 0) {
+    printf("Usage: %s <image> -mincrypt <verity_key>\n"
+           "  image       the image file (raw or sparse image) to be verified\n"
+           "  verity_key  the verity key in mincrypt format (/verity_key on device)\n", argv[0]);
+    return 2;
+  }
+
+  // Get the raw image.
+  android::base::unique_fd fd(open(argv[1], O_RDONLY));
+  if (!fd) {
+    fprintf(stderr, "failed to open %s: %s\n", argv[1], strerror(errno));
+    return 1;
+  }
+
+  struct sparse_file* file = sparse_file_import_auto(fd, false, false);
+  if (file == nullptr) {
+    fprintf(stderr, "failed to read file %s\n", argv[1]);
+    return 1;
+  }
+
+  TemporaryFile tf;
+  if (sparse_file_write(file, tf.fd, false, false, false) < 0) {
+    fprintf(stderr, "failed to write output file\n");
+    return 1;
+  }
+  sparse_file_destroy(file);
+
+  // Verify.
+  fec::io input(tf.path);
+  if (!input) {
+    return 1;
+  }
+
+  fec_verity_metadata verity;
+  if (!input.get_verity_metadata(verity)) {
+    fprintf(stderr, "failed to get verity metadata\n");
+    return 1;
+  }
+
+  int ret = verify_table(argv[3], verity.signature, verity.table, verity.table_length);
+  printf("%s\n", ret == 0 ? "VERIFIED" : "FAILED");
+  return ret;
+}