diff --git a/ext4_utils/Android.mk b/ext4_utils/Android.mk
index 27b00bf..0808886 100644
--- a/ext4_utils/Android.mk
+++ b/ext4_utils/Android.mk
@@ -10,7 +10,6 @@
     contents.c \
     extent.c \
     indirect.c \
-    uuid.c \
     sha1.c \
     wipe.c \
     crc16.c \
@@ -66,9 +65,11 @@
 LOCAL_C_INCLUDES += system/core/logwrapper/include
 LOCAL_SHARED_LIBRARIES := \
     libcutils \
+    libext2_uuid \
     libselinux \
     libsparse \
     libz
+LOCAL_CFLAGS := -DREAL_UUID
 include $(BUILD_SHARED_LIBRARY)
 
 
@@ -86,9 +87,11 @@
 LOCAL_MODULE := make_ext4fs
 LOCAL_SHARED_LIBRARIES := \
     libcutils \
+    libext2_uuid \
     libext4_utils \
     libselinux \
     libz
+LOCAL_CFLAGS := -DREAL_UUID
 include $(BUILD_EXECUTABLE)
 
 
diff --git a/ext4_utils/ext4_utils.c b/ext4_utils/ext4_utils.c
index ad0491f..3b22b81 100644
--- a/ext4_utils/ext4_utils.c
+++ b/ext4_utils/ext4_utils.c
@@ -15,12 +15,15 @@
  */
 
 #include "ext4_utils.h"
-#include "uuid.h"
 #include "allocate.h"
 #include "indirect.h"
 #include "extent.h"
+#include "sha1.h"
 
 #include <sparse/sparse.h>
+#ifdef REAL_UUID
+#include <uuid.h>
+#endif
 
 #include <fcntl.h>
 #include <inttypes.h>
@@ -49,6 +52,44 @@
 
 jmp_buf setjmp_env;
 
+/* Definition from RFC-4122 */
+struct uuid {
+    u32 time_low;
+    u16 time_mid;
+    u16 time_hi_and_version;
+    u8 clk_seq_hi_res;
+    u8 clk_seq_low;
+    u16 node0_1;
+    u32 node2_5;
+};
+
+static void sha1_hash(const char *namespace, const char *name,
+    unsigned char sha1[SHA1_DIGEST_LENGTH])
+{
+    SHA1_CTX ctx;
+    SHA1Init(&ctx);
+    SHA1Update(&ctx, (const u8*)namespace, strlen(namespace));
+    SHA1Update(&ctx, (const u8*)name, strlen(name));
+    SHA1Final(sha1, &ctx);
+}
+
+static void generate_sha1_uuid(const char *namespace, const char *name, u8 result[16])
+{
+    unsigned char sha1[SHA1_DIGEST_LENGTH];
+    struct uuid *uuid = (struct uuid *)result;
+
+    sha1_hash(namespace, name, (unsigned char*)sha1);
+    memcpy(uuid, sha1, sizeof(struct uuid));
+
+    uuid->time_low = ntohl(uuid->time_low);
+    uuid->time_mid = ntohs(uuid->time_mid);
+    uuid->time_hi_and_version = ntohs(uuid->time_hi_and_version);
+    uuid->time_hi_and_version &= 0x0FFF;
+    uuid->time_hi_and_version |= (5 << 12);
+    uuid->clk_seq_hi_res &= ~(1 << 6);
+    uuid->clk_seq_hi_res |= 1 << 7;
+}
+
 /* returns 1 if a is a power of b */
 static int is_power_of(int a, int b)
 {
@@ -188,7 +229,7 @@
 }
 
 /* Fill in the superblock memory buffer based on the filesystem parameters */
-void ext4_fill_in_sb()
+void ext4_fill_in_sb(int real_uuid)
 {
 	unsigned int i;
 	struct ext4_super_block *sb = aux_info.sb;
@@ -225,7 +266,16 @@
 	sb->s_feature_compat = info.feat_compat;
 	sb->s_feature_incompat = info.feat_incompat;
 	sb->s_feature_ro_compat = info.feat_ro_compat;
-	generate_uuid("extandroid/make_ext4fs", info.label, sb->s_uuid);
+	if (real_uuid == 1) {
+#ifdef REAL_UUID
+	    uuid_generate(sb->s_uuid);
+#else
+	    fprintf(stderr, "Not compiled with real UUID support\n");
+	    abort();
+#endif
+	} else {
+	    generate_sha1_uuid("extandroid/make_ext4fs", info.label, sb->s_uuid);
+	}
 	memset(sb->s_volume_name, 0, sizeof(sb->s_volume_name));
 	strncpy(sb->s_volume_name, info.label, sizeof(sb->s_volume_name));
 	memset(sb->s_last_mounted, 0, sizeof(sb->s_last_mounted));
diff --git a/ext4_utils/ext4_utils.h b/ext4_utils/ext4_utils.h
index 499753f..ea95446 100644
--- a/ext4_utils/ext4_utils.h
+++ b/ext4_utils/ext4_utils.h
@@ -138,7 +138,7 @@
 void write_ext4_image(int fd, int gz, int sparse, int crc);
 void ext4_create_fs_aux_info(void);
 void ext4_free_fs_aux_info(void);
-void ext4_fill_in_sb(void);
+void ext4_fill_in_sb(int real_uuid);
 void ext4_create_resize_inode(void);
 void ext4_create_journal_inode(void);
 void ext4_update_free(void);
@@ -157,7 +157,7 @@
 
 int make_ext4fs_internal(int fd, const char *directory,
 						 const char *mountpoint, fs_config_func_t fs_config_func, int gzip,
-						 int sparse, int crc, int wipe,
+						 int sparse, int crc, int wipe, int real_uuid,
 						 struct selabel_handle *sehnd, int verbose, time_t fixed_time,
 						 FILE* block_list_file);
 
diff --git a/ext4_utils/make_ext4fs.c b/ext4_utils/make_ext4fs.c
index 62a3f1a..5c9e208 100644
--- a/ext4_utils/make_ext4fs.c
+++ b/ext4_utils/make_ext4fs.c
@@ -18,7 +18,6 @@
 #include "ext4_utils.h"
 #include "allocate.h"
 #include "contents.h"
-#include "uuid.h"
 #include "wipe.h"
 
 #include <sparse/sparse.h>
@@ -406,7 +405,7 @@
 	reset_ext4fs_info();
 	info.len = len;
 
-	return make_ext4fs_internal(fd, NULL, mountpoint, NULL, 0, 1, 0, 0, sehnd, 0, -1, NULL);
+	return make_ext4fs_internal(fd, NULL, mountpoint, NULL, 0, 1, 0, 0, 0, sehnd, 0, -1, NULL);
 }
 
 int make_ext4fs(const char *filename, long long len,
@@ -424,7 +423,7 @@
 		return EXIT_FAILURE;
 	}
 
-	status = make_ext4fs_internal(fd, NULL, mountpoint, NULL, 0, 0, 0, 1, sehnd, 0, -1, NULL);
+	status = make_ext4fs_internal(fd, NULL, mountpoint, NULL, 0, 0, 0, 1, 0, sehnd, 0, -1, NULL);
 	close(fd);
 
 	return status;
@@ -492,7 +491,7 @@
 
 int make_ext4fs_internal(int fd, const char *_directory,
 						 const char *_mountpoint, fs_config_func_t fs_config_func, int gzip,
-						 int sparse, int crc, int wipe,
+						 int sparse, int crc, int wipe, int real_uuid,
 						 struct selabel_handle *sehnd, int verbose, time_t fixed_time,
 						 FILE* block_list_file)
 {
@@ -585,7 +584,7 @@
 
 	block_allocator_init();
 
-	ext4_fill_in_sb();
+	ext4_fill_in_sb(real_uuid);
 
 	if (reserve_inodes(0, 10) == EXT4_ALLOCATE_FAILED)
 		error("failed to reserve first 10 inodes");
diff --git a/ext4_utils/make_ext4fs_main.c b/ext4_utils/make_ext4fs_main.c
index a6c5f61..0e2ef5e 100644
--- a/ext4_utils/make_ext4fs_main.c
+++ b/ext4_utils/make_ext4fs_main.c
@@ -52,7 +52,7 @@
 {
 	fprintf(stderr, "%s [ -l <len> ] [ -j <journal size> ] [ -b <block_size> ]\n", basename(path));
 	fprintf(stderr, "    [ -g <blocks per group> ] [ -i <inodes> ] [ -I <inode size> ]\n");
-	fprintf(stderr, "    [ -L <label> ] [ -f ] [ -a <android mountpoint> ]\n");
+	fprintf(stderr, "    [ -L <label> ] [ -f ] [ -a <android mountpoint> ] [ -u ]\n");
 	fprintf(stderr, "    [ -S file_contexts ] [ -C fs_config ] [ -T timestamp ]\n");
 	fprintf(stderr, "    [ -z | -s ] [ -w ] [ -c ] [ -J ] [ -v ] [ -B <block_list_file> ]\n");
 	fprintf(stderr, "    <filename> [<directory>]\n");
@@ -70,6 +70,7 @@
 	int sparse = 0;
 	int crc = 0;
 	int wipe = 0;
+	int real_uuid = 0;
 	int fd;
 	int exitcode;
 	int verbose = 0;
@@ -80,7 +81,7 @@
 	struct selinux_opt seopts[] = { { SELABEL_OPT_PATH, "" } };
 #endif
 
-	while ((opt = getopt(argc, argv, "l:j:b:g:i:I:L:a:S:T:C:B:fwzJsctv")) != -1) {
+	while ((opt = getopt(argc, argv, "l:j:b:g:i:I:L:a:S:T:C:B:fwzJsctvu")) != -1) {
 		switch (opt) {
 		case 'l':
 			info.len = parse_num(optarg);
@@ -118,6 +119,9 @@
 		case 'w':
 			wipe = 1;
 			break;
+		case 'u':
+			real_uuid = 1;
+			break;
 		case 'z':
 			gzip = 1;
 			break;
@@ -227,7 +231,7 @@
 	}
 
 	exitcode = make_ext4fs_internal(fd, directory, mountpoint, fs_config_func, gzip,
-		sparse, crc, wipe, sehnd, verbose, fixed_time, block_list_file);
+		sparse, crc, wipe, real_uuid, sehnd, verbose, fixed_time, block_list_file);
 	close(fd);
 	if (block_list_file)
 		fclose(block_list_file);
diff --git a/ext4_utils/uuid.c b/ext4_utils/uuid.c
deleted file mode 100644
index 33d2494..0000000
--- a/ext4_utils/uuid.c
+++ /dev/null
@@ -1,65 +0,0 @@
-/*
- * Copyright (C) 2010 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 <string.h>
-
-#ifdef USE_MINGW
-#include <winsock2.h>
-#else
-#include <arpa/inet.h>
-#endif
-
-#include "ext4_utils.h"
-#include "sha1.h"
-#include "uuid.h"
-
-/* Definition from RFC-4122 */
-struct uuid {
-	u32 time_low;
-	u16 time_mid;
-	u16 time_hi_and_version;
-	u8 clk_seq_hi_res;
-	u8 clk_seq_low;
-	u16 node0_1;
-	u32 node2_5;
-};
-
-static void sha1_hash(const char *namespace, const char *name,
-	unsigned char sha1[SHA1_DIGEST_LENGTH])
-{
-	SHA1_CTX ctx;
-	SHA1Init(&ctx);
-	SHA1Update(&ctx, (const u8*)namespace, strlen(namespace));
-	SHA1Update(&ctx, (const u8*)name, strlen(name));
-	SHA1Final(sha1, &ctx);
-}
-
-void generate_uuid(const char *namespace, const char *name, u8 result[16])
-{
-	unsigned char sha1[SHA1_DIGEST_LENGTH];
-	struct uuid *uuid = (struct uuid *)result;
-
-	sha1_hash(namespace, name, (unsigned char*)sha1);
-	memcpy(uuid, sha1, sizeof(struct uuid));
-
-	uuid->time_low = ntohl(uuid->time_low);
-	uuid->time_mid = ntohs(uuid->time_mid);
-	uuid->time_hi_and_version = ntohs(uuid->time_hi_and_version);
-	uuid->time_hi_and_version &= 0x0FFF;
-	uuid->time_hi_and_version |= (5 << 12);
-	uuid->clk_seq_hi_res &= ~(1 << 6);
-	uuid->clk_seq_hi_res |= 1 << 7;
-}
diff --git a/ext4_utils/uuid.h b/ext4_utils/uuid.h
deleted file mode 100644
index ff1b438..0000000
--- a/ext4_utils/uuid.h
+++ /dev/null
@@ -1,24 +0,0 @@
-/*
- * Copyright (C) 2010 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.
- */
-
-#ifndef _UUID_H_
-#define _UUID_H_
-
-#include "ext4_utils.h"
-
-void generate_uuid(const char *namespace, const char *name, u8 result[16]);
-
-#endif
diff --git a/f2fs_utils/f2fs_sparseblock.c b/f2fs_utils/f2fs_sparseblock.c
index 950628c..e39a61f 100644
--- a/f2fs_utils/f2fs_sparseblock.c
+++ b/f2fs_utils/f2fs_sparseblock.c
@@ -262,13 +262,13 @@
 
     struct f2fs_checkpoint *cp1, *cp2, *cur_cp;
     int cur_cp_no;
-    unsigned long blk_size;// = 1<<le32_to_cpu(info->sb->log_blocksize);
+    unsigned long blk_size;
     unsigned long long cp1_version = 0, cp2_version = 0;
     unsigned long long cp1_start_blk_no;
     unsigned long long cp2_start_blk_no;
     u32 bmp_size;
 
-    blk_size = 1U<<le32_to_cpu(sb->log_blocksize);
+    blk_size = 1U << le32_to_cpu(sb->log_blocksize);
 
     /*
      * Find valid cp by reading both packs and finding most recent one.
@@ -489,7 +489,8 @@
     u64 block;
     unsigned int used, found, started = 0, i;
 
-    for (block=startblock; block<info->total_blocks; block++) {
+    block = startblock;
+    while (block < info->total_blocks) {
         /* TODO: Save only relevant portions of metadata */
         if (block < info->main_blkaddr) {
             if (func(block, data)) {
@@ -512,17 +513,24 @@
 
             /* get SIT entry from SIT section */
             if (!found) {
-                sit_block_num_cur = segnum/SIT_ENTRY_PER_BLOCK;
+                sit_block_num_cur = segnum / SIT_ENTRY_PER_BLOCK;
                 sit_entry = &info->sit_blocks[sit_block_num_cur].entries[segnum % SIT_ENTRY_PER_BLOCK];
             }
 
             block_offset = (block - info->main_blkaddr) % info->blocks_per_segment;
 
+            if (block_offset == 0 && GET_SIT_VBLOCKS(sit_entry) == 0) {
+                block += info->blocks_per_segment;
+                continue;
+            }
+
             used = f2fs_test_bit(block_offset, (char *)sit_entry->valid_map);
             if(used)
                 if (func(block, data))
                     return -1;
         }
+
+        block++;
     }
     return 0;
 }
@@ -548,7 +556,7 @@
 {
     struct privdata *d = data;
     char *buf;
-    int pdone = (pos*100)/d->info->total_blocks;
+    int pdone = (pos * 100) / d->info->total_blocks;
     if (pdone > d->done) {
         d->done = pdone;
         printf("Done with %d percent\n", d->done);
@@ -562,7 +570,7 @@
     }
 
     off64_t ret;
-    ret = lseek64(d->outfd, pos*F2FS_BLKSIZE, SEEK_SET);
+    ret = lseek64(d->outfd, pos * F2FS_BLKSIZE, SEEK_SET);
     if (ret < 0) {
         SLOGE("failed to seek\n");
         return ret;
diff --git a/verity/Utils.java b/verity/Utils.java
index 3576e3b..937c206 100644
--- a/verity/Utils.java
+++ b/verity/Utils.java
@@ -35,6 +35,8 @@
 import java.security.cert.Certificate;
 import java.security.cert.CertificateFactory;
 import java.security.cert.X509Certificate;
+import java.security.spec.ECPublicKeySpec;
+import java.security.spec.ECPrivateKeySpec;
 import java.security.spec.X509EncodedKeySpec;
 import java.security.spec.PKCS8EncodedKeySpec;
 import java.security.spec.InvalidKeySpecException;
@@ -52,6 +54,7 @@
 import org.bouncycastle.asn1.pkcs.PrivateKeyInfo;
 import org.bouncycastle.asn1.pkcs.PKCSObjectIdentifiers;
 import org.bouncycastle.asn1.x509.AlgorithmIdentifier;
+import org.bouncycastle.asn1.x9.X9ObjectIdentifiers;
 import org.bouncycastle.util.encoders.Base64;
 
 public class Utils {
@@ -63,10 +66,16 @@
         ID_TO_ALG = new HashMap<String, String>();
         ALG_TO_ID = new HashMap<String, String>();
 
+        ID_TO_ALG.put(X9ObjectIdentifiers.ecdsa_with_SHA256.getId(), "SHA256withECDSA");
+        ID_TO_ALG.put(X9ObjectIdentifiers.ecdsa_with_SHA384.getId(), "SHA384withECDSA");
+        ID_TO_ALG.put(X9ObjectIdentifiers.ecdsa_with_SHA512.getId(), "SHA512withECDSA");
         ID_TO_ALG.put(PKCSObjectIdentifiers.sha1WithRSAEncryption.getId(), "SHA1withRSA");
         ID_TO_ALG.put(PKCSObjectIdentifiers.sha256WithRSAEncryption.getId(), "SHA256withRSA");
         ID_TO_ALG.put(PKCSObjectIdentifiers.sha512WithRSAEncryption.getId(), "SHA512withRSA");
 
+        ALG_TO_ID.put("SHA256withECDSA", X9ObjectIdentifiers.ecdsa_with_SHA256.getId());
+        ALG_TO_ID.put("SHA384withECDSA", X9ObjectIdentifiers.ecdsa_with_SHA384.getId());
+        ALG_TO_ID.put("SHA512withECDSA", X9ObjectIdentifiers.ecdsa_with_SHA512.getId());
         ALG_TO_ID.put("SHA1withRSA", PKCSObjectIdentifiers.sha1WithRSAEncryption.getId());
         ALG_TO_ID.put("SHA256withRSA", PKCSObjectIdentifiers.sha256WithRSAEncryption.getId());
         ALG_TO_ID.put("SHA512withRSA", PKCSObjectIdentifiers.sha512WithRSAEncryption.getId());
@@ -208,15 +217,36 @@
         }
     }
 
-    private static String getSignatureAlgorithm(Key key) {
-        if ("RSA".equals(key.getAlgorithm())) {
+    private static String getSignatureAlgorithm(Key key) throws Exception {
+        if ("EC".equals(key.getAlgorithm())) {
+            int curveSize;
+            KeyFactory factory = KeyFactory.getInstance("EC");
+
+            if (key instanceof PublicKey) {
+                ECPublicKeySpec spec = factory.getKeySpec(key, ECPublicKeySpec.class);
+                curveSize = spec.getParams().getCurve().getField().getFieldSize();
+            } else if (key instanceof PrivateKey) {
+                ECPrivateKeySpec spec = factory.getKeySpec(key, ECPrivateKeySpec.class);
+                curveSize = spec.getParams().getCurve().getField().getFieldSize();
+            } else {
+                throw new InvalidKeySpecException();
+            }
+
+            if (curveSize <= 256) {
+                return "SHA256withECDSA";
+            } else if (curveSize <= 384) {
+                return "SHA384withECDSA";
+            } else {
+                return "SHA512withECDSA";
+            }
+        } else if ("RSA".equals(key.getAlgorithm())) {
             return "SHA256withRSA";
         } else {
             throw new IllegalArgumentException("Unsupported key type " + key.getAlgorithm());
         }
     }
 
-    static AlgorithmIdentifier getSignatureAlgorithmIdentifier(Key key) {
+    static AlgorithmIdentifier getSignatureAlgorithmIdentifier(Key key) throws Exception {
         String id = ALG_TO_ID.get(getSignatureAlgorithm(key));
 
         if (id == null) {
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);