2 * Copyright (C) 2014 The Android Open Source Project
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 package com.android.verity;
20 import java.io.RandomAccessFile;
21 import java.nio.ByteBuffer;
22 import java.nio.ByteOrder;
23 import java.lang.Math;
24 import java.lang.Process;
25 import java.lang.Runtime;
26 import java.math.BigInteger;
27 import java.security.KeyFactory;
28 import java.security.MessageDigest;
29 import java.security.PublicKey;
30 import java.security.Security;
31 import java.security.cert.X509Certificate;
32 import java.security.interfaces.RSAPublicKey;
33 import java.security.spec.RSAPublicKeySpec;
34 import java.util.ArrayList;
35 import java.util.Arrays;
36 import javax.xml.bind.DatatypeConverter;
37 import org.bouncycastle.jce.provider.BouncyCastleProvider;
39 public class VerityVerifier {
41 private ArrayList<Integer> hashBlocksLevel;
42 private byte[] hashTree;
43 private byte[] rootHash;
45 private byte[] signature;
48 private int blockSize;
49 private int hashBlockSize;
50 private int hashOffsetForData;
52 private int hashTreeSize;
53 private long hashStart;
54 private long imageSize;
55 private MessageDigest digest;
57 private static final int EXT4_SB_MAGIC = 0xEF53;
58 private static final int EXT4_SB_OFFSET = 0x400;
59 private static final int EXT4_SB_OFFSET_MAGIC = EXT4_SB_OFFSET + 0x38;
60 private static final int EXT4_SB_OFFSET_LOG_BLOCK_SIZE = EXT4_SB_OFFSET + 0x18;
61 private static final int EXT4_SB_OFFSET_BLOCKS_COUNT_LO = EXT4_SB_OFFSET + 0x4;
62 private static final int EXT4_SB_OFFSET_BLOCKS_COUNT_HI = EXT4_SB_OFFSET + 0x150;
63 private static final int MINCRYPT_OFFSET_MODULUS = 0x8;
64 private static final int MINCRYPT_OFFSET_EXPONENT = 0x208;
65 private static final int MINCRYPT_MODULUS_SIZE = 0x100;
66 private static final int MINCRYPT_EXPONENT_SIZE = 0x4;
67 private static final int VERITY_FIELDS = 10;
68 private static final int VERITY_MAGIC = 0xB001B001;
69 private static final int VERITY_SIGNATURE_SIZE = 256;
70 private static final int VERITY_VERSION = 0;
72 public VerityVerifier(String fname) throws Exception {
73 digest = MessageDigest.getInstance("SHA-256");
74 hashSize = digest.getDigestLength();
75 hashBlocksLevel = new ArrayList<Integer>();
82 * Reverses the order of bytes in a byte array
83 * @param value Byte array to reverse
85 private static byte[] reverse(byte[] value) {
86 for (int i = 0; i < value.length / 2; i++) {
88 value[i] = value[value.length - i - 1];
89 value[value.length - i - 1] = tmp;
96 * Converts a 4-byte little endian value to a Java integer
97 * @param value Little endian integer to convert
99 private static int fromle(int value) {
100 byte[] bytes = ByteBuffer.allocate(4).putInt(value).array();
101 return ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN).getInt();
105 * Converts a 2-byte little endian value to Java a integer
106 * @param value Little endian short to convert
108 private static int fromle(short value) {
109 return fromle(value << 16);
113 * Reads a 2048-bit RSA public key saved in mincrypt format, and returns
114 * a Java PublicKey for it.
115 * @param fname Name of the mincrypt public key file
117 private static PublicKey getMincryptPublicKey(String fname) throws Exception {
118 try (RandomAccessFile key = new RandomAccessFile(fname, "r")) {
119 byte[] binaryMod = new byte[MINCRYPT_MODULUS_SIZE];
120 byte[] binaryExp = new byte[MINCRYPT_EXPONENT_SIZE];
122 key.seek(MINCRYPT_OFFSET_MODULUS);
123 key.readFully(binaryMod);
125 key.seek(MINCRYPT_OFFSET_EXPONENT);
126 key.readFully(binaryExp);
128 BigInteger modulus = new BigInteger(1, reverse(binaryMod));
129 BigInteger exponent = new BigInteger(1, reverse(binaryExp));
131 RSAPublicKeySpec spec = new RSAPublicKeySpec(modulus, exponent);
132 KeyFactory factory = KeyFactory.getInstance("RSA");
133 return factory.generatePublic(spec);
138 * Unsparses a sparse image into a temporary file and returns a
140 * @param fname Path to a sparse image file
142 private void openImage(String fname) throws Exception {
143 image = File.createTempFile("system", ".raw");
144 image.deleteOnExit();
146 Process p = Runtime.getRuntime().exec("simg2img " + fname +
147 " " + image.getAbsoluteFile());
150 if (p.exitValue() != 0) {
151 throw new IllegalArgumentException("Invalid image: failed to unsparse");
156 * Reads the ext4 superblock and calculates the size of the system image,
157 * after which we should find the verity metadata
158 * @param img File handle to the image file
160 public static long getMetadataPosition(RandomAccessFile img)
162 img.seek(EXT4_SB_OFFSET_MAGIC);
163 int magic = fromle(img.readShort());
165 if (magic != EXT4_SB_MAGIC) {
166 throw new IllegalArgumentException("Invalid image: not a valid ext4 image");
169 img.seek(EXT4_SB_OFFSET_BLOCKS_COUNT_LO);
170 long blocksCountLo = fromle(img.readInt());
172 img.seek(EXT4_SB_OFFSET_LOG_BLOCK_SIZE);
173 long logBlockSize = fromle(img.readInt());
175 img.seek(EXT4_SB_OFFSET_BLOCKS_COUNT_HI);
176 long blocksCountHi = fromle(img.readInt());
178 long blockSizeBytes = 1L << (10 + logBlockSize);
179 long blockCount = (blocksCountHi << 32) + blocksCountLo;
180 return blockSizeBytes * blockCount;
184 * Calculates the size of the verity hash tree based on the image size
186 private int calculateHashTreeSize() {
187 if (hashTreeSize > 0) {
192 int hashes = (int) (imageSize / blockSize);
194 hashBlocksLevel.clear();
197 hashBlocksLevel.add(0, hashes);
200 (int) Math.ceil((double) hashes * hashSize / hashBlockSize);
202 totalBlocks += hashBlocks;
205 } while (hashes > 1);
207 hashTreeSize = totalBlocks * hashBlockSize;
212 * Parses the verity mapping table and reads the hash tree from
214 * @param img Handle to the image file
215 * @param table Verity mapping table
217 private void readHashTree(RandomAccessFile img, byte[] table)
219 String tableStr = new String(table);
220 String[] fields = tableStr.split(" ");
222 if (fields.length != VERITY_FIELDS) {
223 throw new IllegalArgumentException("Invalid image: unexpected number of fields "
224 + "in verity mapping table (" + fields.length + ")");
227 String hashVersion = fields[0];
229 if (!"1".equals(hashVersion)) {
230 throw new IllegalArgumentException("Invalid image: unsupported hash format");
233 String alg = fields[7];
235 if (!"sha256".equals(alg)) {
236 throw new IllegalArgumentException("Invalid image: unsupported hash algorithm");
239 blockSize = Integer.parseInt(fields[3]);
240 hashBlockSize = Integer.parseInt(fields[4]);
242 int blocks = Integer.parseInt(fields[5]);
243 int start = Integer.parseInt(fields[6]);
245 if (imageSize != (long) blocks * blockSize) {
246 throw new IllegalArgumentException("Invalid image: size mismatch in mapping "
250 rootHash = DatatypeConverter.parseHexBinary(fields[8]);
251 salt = DatatypeConverter.parseHexBinary(fields[9]);
253 hashStart = (long) start * blockSize;
256 int treeSize = calculateHashTreeSize();
258 hashTree = new byte[treeSize];
259 img.readFully(hashTree);
263 * Reads verity data from the image file
265 private void readVerityData() throws Exception {
266 try (RandomAccessFile img = new RandomAccessFile(image, "r")) {
267 imageSize = getMetadataPosition(img);
270 int magic = fromle(img.readInt());
272 if (magic != VERITY_MAGIC) {
273 throw new IllegalArgumentException("Invalid image: verity metadata not found");
276 int version = fromle(img.readInt());
278 if (version != VERITY_VERSION) {
279 throw new IllegalArgumentException("Invalid image: unknown metadata version");
282 signature = new byte[VERITY_SIGNATURE_SIZE];
283 img.readFully(signature);
285 int tableSize = fromle(img.readInt());
287 table = new byte[tableSize];
288 img.readFully(table);
290 readHashTree(img, table);
295 * Reads and validates verity metadata, and checks the signature against the
297 * @param key Public key to use for signature verification
299 public boolean verifyMetaData(PublicKey key)
301 return Utils.verify(key, table, signature,
302 Utils.getSignatureAlgorithmIdentifier(key));
306 * Hashes a block of data using a salt and checks of the results are expected
307 * @param hash The expected hash value
308 * @param data The data block to check
310 private boolean checkBlock(byte[] hash, byte[] data) {
314 return Arrays.equals(hash, digest.digest());
318 * Verifies the root hash and the first N-1 levels of the hash tree
320 private boolean verifyHashTree() throws Exception {
322 int dataOffset = hashBlockSize;
324 if (!checkBlock(rootHash, Arrays.copyOfRange(hashTree, 0, hashBlockSize))) {
325 System.err.println("Root hash mismatch");
329 for (int level = 0; level < hashBlocksLevel.size() - 1; level++) {
330 int blocks = hashBlocksLevel.get(level);
332 for (int i = 0; i < blocks; i++) {
333 byte[] hashBlock = Arrays.copyOfRange(hashTree,
334 hashOffset + i * hashSize,
335 hashOffset + i * hashSize + hashSize);
337 byte[] dataBlock = Arrays.copyOfRange(hashTree,
338 dataOffset + i * hashBlockSize,
339 dataOffset + i * hashBlockSize + hashBlockSize);
341 if (!checkBlock(hashBlock, dataBlock)) {
342 System.err.printf("Hash mismatch at tree level %d, block %d\n", level, i);
347 hashOffset = dataOffset;
348 hashOffsetForData = dataOffset;
349 dataOffset += blocks * hashBlockSize;
356 * Validates the image against the hash tree
358 public boolean verifyData() throws Exception {
359 if (!verifyHashTree()) {
363 try (RandomAccessFile img = new RandomAccessFile(image, "r")) {
364 byte[] dataBlock = new byte[blockSize];
365 int hashOffset = hashOffsetForData;
367 for (int i = 0; (long) i * blockSize < imageSize; i++) {
368 byte[] hashBlock = Arrays.copyOfRange(hashTree,
369 hashOffset + i * hashSize,
370 hashOffset + i * hashSize + hashSize);
372 img.readFully(dataBlock);
374 if (!checkBlock(hashBlock, dataBlock)) {
375 System.err.printf("Hash mismatch at block %d\n", i);
385 * Verifies the integrity of the image and the verity metadata
386 * @param key Public key to use for signature verification
388 public boolean verify(PublicKey key) throws Exception {
389 return (verifyMetaData(key) && verifyData());
392 public static void main(String[] args) throws Exception {
393 Security.addProvider(new BouncyCastleProvider());
394 PublicKey key = null;
396 if (args.length == 3 && "-mincrypt".equals(args[1])) {
397 key = getMincryptPublicKey(args[2]);
398 } else if (args.length == 2) {
399 X509Certificate cert = Utils.loadPEMCertificate(args[1]);
400 key = cert.getPublicKey();
402 System.err.println("Usage: VerityVerifier <sparse.img> <certificate.x509.pem> | -mincrypt <mincrypt_key>");
406 VerityVerifier verifier = new VerityVerifier(args[0]);
409 if (verifier.verify(key)) {
410 System.err.println("Signature is VALID");
413 } catch (Exception e) {
414 e.printStackTrace(System.err);