Docs: Adding dm-verity to Security section.
Bug: 10706838
Staging location:
http://claym.mtv.corp.google.com:8091/devices/tech/security/dm-verity.html
Change-Id: Id876632f1f62db0dc705c1e2a3a10d9fc7d7348a
diff --git a/src/devices/devices_toc.cs b/src/devices/devices_toc.cs
index 13e0174..af6ab77 100644
--- a/src/devices/devices_toc.cs
+++ b/src/devices/devices_toc.cs
@@ -105,6 +105,11 @@
</a>
</li>
<li>
+ <a href="<?cs var:toroot ?>devices/tech/security/dm-verity.html">
+ <span class="en">dm-verity on boot</span>
+ </a>
+ </li>
+ <li>
<a href="<?cs var:toroot ?>devices/tech/security/se-linux.html">
<span class="en">Security-Enhanced Linux</span>
</a>
diff --git a/src/devices/tech/security/dm-verity.jd b/src/devices/tech/security/dm-verity.jd
new file mode 100644
index 0000000..79e375f
--- /dev/null
+++ b/src/devices/tech/security/dm-verity.jd
@@ -0,0 +1,318 @@
+page.title=dm-verity on boot
+@jd:body
+
+<!--
+ Copyright 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.
+-->
+<div id="qv-wrapper">
+ <div id="qv">
+ <h2>In this document</h2>
+ <ol id="auto-toc">
+ </ol>
+ </div>
+</div>
+
+<h2 id="introduction">Introduction</h2>
+
+<p>Android 4.4 supports verified boot through the optional device-mapper-verity
+(dm-verity) kernel feature, which provides transparent integrity checking of
+block devices. dm-verity helps prevent persistent rootkits that can hold onto
+root privileges and compromise devices. This experimental feature helps Android
+users be sure when booting a device it is in the same state as when it was last
+used.</p>
+
+<p>Clever malware with root privileges can hide from detection programs and
+otherwise mask themselves. The rooting software can do this because it is often
+more privileged than the detectors, enabling the software to "lie" to to the
+detection programs.</p>
+
+<p>The dm-verity feature lets you look at a block device, the underlying storage
+layer of the file system, and determine if it matches its expected
+configuration. It does this using a cryptographic hash tree. For every block
+(typically 4k), there is a SHA256 hash.</p>
+
+<p>And since the hash values are stored in a tree of pages, only the top-level
+"root" hash must be trusted to verify the rest of the tree. The ability to
+modify any of the blocks would be equivalent to breaking the cryptographic hash.
+See the following diagram for a depiction of this structure.</p>
+
+<p><img src="images/dm-verity-hash-table.png" alt="dm-verity-hash-table"/><br/>
+A public key is included on the boot partition, which must be verified
+externally by the OEM. That key is used to verify the signature for that hash
+and confirm the device's system partition is protected and unchanged.</p>
+
+<h2 id="operation">Operation</h2>
+
+<p>dm-verity protection lives in the kernel. So if rooting software compromises the
+system before the kernel comes up, it will retain that access. To mitigate this
+risk, most manufacturers verify the kernel using a key burned into the device.
+That key is not changeable once the device leaves the factory.</p>
+
+<p>Manufacturers use that key to verify the signature on the first-level
+bootloader, which in turn verifies the signature on subsequent levels, the
+application bootloader and eventually the kernel. Each manufacturer wishing to
+take advantage of verified boot should have a method for verifying the integrity
+of the kernel. Assuming the kernel has been verified, the kernel can look at a
+block device and verify it as it is mounted.</p>
+
+<p>One way of verifying a block device is to directly hash its contents and compare
+them to a stored value. However, attempting to verify an entire block device can
+take an extended period and consume much of a device's power. Devices would take
+long periods to boot and then be significantly drained prior to use.</p>
+
+<p>Instead, dm-verity verifies blocks individually and only when each one is
+accessed. When read into memory, the block is hashed in parallel. The hash is
+then verified up the tree. And since reading the block is such an expensive
+operation, the latency introduced by this block-level verification is
+comparatively nominal.</p>
+
+<p>If verification fails, the device generates an I/O error indicating the block
+cannot be read. It will appear as if the filesystem has been corrupted, as is
+expected.</p>
+
+<p>Applications may choose to proceed without the resulting data, such as when
+those results are not required to the application's primary function. However,
+if the application cannot continue without the data, it will fail.</p>
+
+<h2 id="prerequisites">Prerequisites</h2>
+
+<h3 id="block-otas">Switching to block-oriented OTAs</h3>
+
+<p>To enable dm-verity on your devices, you <strong>must</strong> move from file-based "over the
+air" (OTA) updates to block-oriented OTAs. This is needed because during OTA,
+Android attempts to change the contents of the system partition at the
+filesystem layer.<br/>
+And since OTA works on a file-by-file basis, it is not guaranteed to write files
+in a consistent order, have a consistent last modified time or superblock, or
+even place the blocks in the same location on the block device. For this reason,
+<em>file-based OTAs will fail on a dm-verity-enabled device.</em><strong>The device will
+not boot after OTA.</strong></p>
+
+<p>So you must use block-oriented OTAs. With block-oriented OTAs, you serve the
+device the difference between the two block images rather than the two sets of
+files. Many manufacturers have already moved to block-oriented OTAs to make them
+more reproducible and predictable.</p>
+
+<p>A block-oriented OTA checks a device build against the corresponding build
+server at the block device level, below the filesystem. This can be done in a
+couple of different ways, each with their own benefits and drawbacks:</p>
+
+<ul>
+<li><em>Copy the full system image to the device</em> - This is simple and makes patch
+generation easy. But it also makes the application of those patches quite
+expensive as the resulting images are large.</li>
+<li><em>Employ a binary differ</em> - These tools, such as <code>bsdiff</code>, simplify patch
+application as images are much smaller. But these tools tend to be memory
+intensive and therefore expensive in generating the patches themselves.</li>
+</ul>
+
+<h3 id="config-dm-verity">Configuring dm-verity</h3>
+
+<p>After switching to block-oriented OTAs, incorporate the latest Android kernel or
+use a stock upstream kernel and enable dm-verity support by including the
+relevant configuration option:<br/>
+<code>CONFIG_DM_VERITY
+</code></p>
+<p>When using the Android kernel, dm-verity is turned on when the kernel is built.</p>
+
+<h2 id="implementation">Implementation</h2>
+
+<h3 id="summary">Summary</h3>
+
+<ol>
+<li>Generate an ext4 system image.</li>
+<li><a href="#heading=h.wiiuowe37q8h">Generate a hash tree</a> for that image.</li>
+<li><a href="#heading=h.cw7mesnrerea">Build a dm-verity table</a> for that hash tree.</li>
+<li><a href="#heading=h.maq6jfk4vx92">Sign that dm-verity table</a> to produce a table
+signature.</li>
+<li><a href="#heading=h.tkceh5wnx7z2">Bundle the table signature</a> and dm-verity table
+into verity metadata.</li>
+<li>Concatenate the system image, the verity metadata, and the hash tree.</li>
+</ol>
+
+<p>See the <a href="http://www.chromium.org/chromium-os/chromiumos-design-docs/verified-boot">The Chromium Projects - Verified
+Boot</a>
+for a detailed description of the hash tree and dm-verity table.</p>
+
+<h3 id="hash-tree">Generating the hash tree</h3>
+
+<p>As described in the <a href="#heading=h.q4z3ftrhbehy">Introduction</a>, the hash tree is
+integral to dm-verity. The
+<a href="https://code.google.com/p/cryptsetup/wiki/DMVerity">cryptsetup</a> tool will
+generate a hash tree for you. Alternatively, a compatible one is defined here:</p>
+
+<pre>
+<your block device name> <your block device name> <block size> <block size> <image size in blocks> <image size in blocks + 8> <root hash> <salt>
+</pre>
+
+<p>To form the hash, the system image is split at layer 0 into 4k blocks, each
+assigned a SHA256 hash. Layer 1 is formed by joining only those SHA256 hashes
+into 4k blocks, resulting in a much smaller image. Layer 2 is formed
+identically, with the SHA256 hashes of Layer 1.</p>
+
+<p>This is done until the SHA256 hashes of the previous layer can fit in a single
+block. When get the SHA256 of that block, you have the root hash of the tree. </p>
+
+<p>The size of the hash tree (and corresponding disk space usage) varies with the
+size of the verified partition. In practice, the size of hash trees tends to be
+small, often less than 30 MB.</p>
+
+<p>If you have a block in a layer that isn't completely filled naturally by the
+hashes of the previous layer, you should pad it with zeroes to achieve the
+expected 4k. This allows you to know the hash tree hasn't been removed and is
+instead completed with blank data.</p>
+
+<p>To generate the hash tree, concatenate the layer 2 hashes onto those for layer
+1, the layer 3 the hashes onto those of layer 2, and so on. Write all of this
+out to disk. Note that this doesn't reference layer 0 of the root hash.</p>
+
+<p>To recap, the general algorithm to construct the hash tree is as follows:</p>
+
+<ol>
+<li>Choose a random salt (hexadecimal encoding).</li>
+<li>Unsparse your system image into 4k blocks.</li>
+<li>For each block, get its (salted) SHA256 hash.</li>
+<li>Concatenate these hashes to form a level</li>
+<li>Pad the level with 0s to a 4k block boundary.</li>
+<li>Concatenate the level to your hash tree.</li>
+<li>Repeat steps 2-6 using the previous level as the source for the next until
+you have only a single hash.</li>
+</ol>
+
+<p>The result of this is a single hash, which is your root hash. This and your salt
+are used during the construction of your dm-verity mapping hash table.</p>
+
+<h3 id="mapping-table">Building the dm-verity mapping table</h3>
+
+<p>Build the dm-verity mapping table, which identifies the block device (or target)
+for the kernel and the location of the hash tree (which is the same value.) This
+mapping is used for <code>fstab</code> generation and booting. The table also identifies
+the size of the blocks and the hash_start, or the offset in hash size blocks
+(length of layer 0).</p>
+
+<p>See <a href="https://code.google.com/p/cryptsetup/wiki/DMVerity">cryptsetup</a> for a
+detailed description of the verity target mapping table fields.</p>
+
+<h3 id="signing">Signing the dm-verity table</h3>
+
+<p>Sign the dm-verity table to produce a table signature. When verifying a
+partition, the table signature is validated first. This is done against a key on
+your boot image in a fixed location. Keys are typically included in the
+manufacturers' build systems for automatic inclusion on devices in a fixed
+location.</p>
+
+<p>To verify the partition with this signature and key combination:</p>
+
+<ol>
+<li>Add an RSA-2048 key in libmincrypt-compatible format to the /boot partition
+at /verity_key. Identify the location of the key used to verify the hash
+tree.</li>
+<li>In the fstab for the relevant entry, add 'verify' to the fs_mgr flags.</li>
+</ol>
+
+<h3 id="metadata">Bundling the table signature into metadata</h3>
+
+<p>Bundle the table signature and dm-verity table into verity metadata. The entire
+block of metadata is versioned so it may be extended, such as to add a second
+kind of signature or change some ordering.</p>
+
+<p>As a sanity check, a magic number is associated with each set of table metadata
+that helps identify the table. Since the length is included in the ext4 system
+image header, this provides a way to search for the metadata without knowing the
+contents of the data itself.</p>
+
+<p>This makes sure you haven't elected to verify an unverified partition. If so,
+the absence of this magic number will halt the verification process. This number
+resembles:<br/>
+0xb001b001</p>
+
+<p>The byte values in hex are:</p>
+
+<ul>
+<li>first byte = b0</li>
+<li>second byte = 01</li>
+<li>third byte = b0</li>
+<li>fourth byte = 01</li>
+</ul>
+
+<p>The following diagram depicts the breakdown of the verity metadata:</p>
+
+<pre><magic number>|<version>|<signature>|<table length>|<table>|<padding>
+\-------------------------------------------------------------------/
+\----------------------------------------------------------/ |
+ | |
+ | 32K
+ block content
+</pre>
+
+<p>And this table describes those metadata fields.</p>
+
+<table>
+<tr>
+<th>Field</th>
+<th>Purpose</th>
+<th>Size</th>
+<th>Value</th>
+</tr>
+<tr>
+<td>magic number</td>
+<td>used by fs_mgr as a sanity check</td>
+<td>4 bytes</td>
+<td>0xb001b001</td>
+</tr>
+<tr>
+<td>version</td>
+<td>used to version the metadata block</td>
+<td>4 bytes</td>
+<td>currently 0</td>
+</tr>
+<tr>
+<td>signature</td>
+<td>the signature of the table in PKCS1.5 padded form</td>
+<td>256 bytes</td>
+<td></td>
+</tr>
+<tr>
+<td>table length</td>
+<td>the length of the dm-verity table in bytes</td>
+<td>4 bytes</td>
+<td></td>
+</tr>
+<tr>
+<td>table</td>
+<td>the dm-verity table described earlier</td>
+<td>`table length` bytes</td>
+<td></td>
+</tr>
+<tr>
+<td>padding</td>
+<td>this structure is 0-padded to 32k in length</td>
+<td></td>
+<td>0</td>
+</tr>
+</table>
+
+<p>For additional assistance, contact
+<a href="mailto:gcondra@google.com">gcondra@google.com</a>.</p>
+
+<h2 id="supporting-docs">Supporting documentation</h2>
+
+<p><a href="https://code.google.com/p/cryptsetup/wiki/DMVerity">cryptsetup - dm-verity: device-mapper block integrity checking
+target</a><br/>
+<a href="http://www.chromium.org/chromium-os/chromiumos-design-docs/verified-boot">The Chromium Projects - Verified
+Boot</a><br/>
+<a
+href="http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=Documentation/device-mapper/verity.txt">Linux Kernel Documentation:
+verity.txt</a></p>
diff --git a/src/devices/tech/security/images/dm-verity-hash-table.png b/src/devices/tech/security/images/dm-verity-hash-table.png
new file mode 100644
index 0000000..3761dc6
--- /dev/null
+++ b/src/devices/tech/security/images/dm-verity-hash-table.png
Binary files differ
