am d30f68d1: Merge "system/extra: include more of what you use."
* commit 'd30f68d1d436f2669084315324bc1f64a581b3aa':
system/extra: include more of what you use.
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);