verity/VerityVerifier.java

/*
 * 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);
    }
}