Validate the full image in VerityVerifier
Check the entire image against the verity hash tree, instead of
merely verifying the signature. For signature verification, add
support for mincrypt public key format used by fs_mgr.
Bug: 18502074
Change-Id: I5f81a52e16fc86220d649cc550c6f726d67b16fb
diff --git a/verity/VerityVerifier.java b/verity/VerityVerifier.java
index 5c9d7d2..6b3f49e 100644
--- a/verity/VerityVerifier.java
+++ b/verity/VerityVerifier.java
@@ -20,31 +20,83 @@
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.PrivateKey;
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
*/
- public static int fromle(int value) {
+ private static int fromle(int value) {
byte[] bytes = ByteBuffer.allocate(4).putInt(value).array();
return ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN).getInt();
}
@@ -53,28 +105,51 @@
* Converts a 2-byte little endian value to Java a integer
* @param value Little endian short to convert
*/
- public static int fromle(short value) {
+ 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
*/
- public static RandomAccessFile openImage(String fname) throws Exception {
- File tmp = File.createTempFile("system", ".raw");
- tmp.deleteOnExit();
+ private void openImage(String fname) throws Exception {
+ image = File.createTempFile("system", ".raw");
+ image.deleteOnExit();
Process p = Runtime.getRuntime().exec("simg2img " + fname +
- " " + tmp.getAbsoluteFile());
+ " " + image.getAbsoluteFile());
p.waitFor();
if (p.exitValue() != 0) {
throw new IllegalArgumentException("Invalid image: failed to unsparse");
}
-
- return new RandomAccessFile(tmp, "r");
}
/**
@@ -106,56 +181,234 @@
}
/**
- * Reads and validates verity metadata, and check the signature against the
+ * 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 img File handle to the image file
* @param key Public key to use for signature verification
*/
- public static boolean verifyMetaData(RandomAccessFile img, PublicKey key)
+ public boolean verifyMetaData(PublicKey key)
throws Exception {
- img.seek(getMetadataPosition(img));
- 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");
- }
-
- byte[] signature = new byte[VERITY_SIGNATURE_SIZE];
- img.readFully(signature);
-
- int tableSize = fromle(img.readInt());
-
- byte[] table = new byte[tableSize];
- img.readFully(table);
-
- return Utils.verify(key, table, signature,
+ 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 {
- if (args.length != 2) {
- System.err.println("Usage: VerityVerifier <sparse.img> <certificate.x509.pem>");
+ 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);
}
- Security.addProvider(new BouncyCastleProvider());
-
- X509Certificate cert = Utils.loadPEMCertificate(args[1]);
- PublicKey key = cert.getPublicKey();
- RandomAccessFile img = openImage(args[0]);
+ VerityVerifier verifier = new VerityVerifier(args[0]);
try {
- if (verifyMetaData(img, key)) {
+ if (verifier.verify(key)) {
System.err.println("Signature is VALID");
System.exit(0);
- } else {
- System.err.println("Signature is INVALID");
}
} catch (Exception e) {
e.printStackTrace(System.err);