1page.title=dm-verity on boot 2@jd:body 3 4<!-- 5 Copyright 2013 The Android Open Source Project 6 7 Licensed under the Apache License, Version 2.0 (the "License"); 8 you may not use this file except in compliance with the License. 9 You may obtain a copy of the License at 10 11 http://www.apache.org/licenses/LICENSE-2.0 12 13 Unless required by applicable law or agreed to in writing, software 14 distributed under the License is distributed on an "AS IS" BASIS, 15 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16 See the License for the specific language governing permissions and 17 limitations under the License. 18--> 19<div id="qv-wrapper"> 20 <div id="qv"> 21 <h2>In this document</h2> 22 <ol id="auto-toc"> 23 </ol> 24 </div> 25</div> 26 27<h2 id="introduction">Introduction</h2> 28 29<p>Android 4.4 supports verified boot through the optional device-mapper-verity 30(dm-verity) kernel feature, which provides transparent integrity checking of 31block devices. dm-verity helps prevent persistent rootkits that can hold onto 32root privileges and compromise devices. This experimental feature helps Android 33users be sure when booting a device it is in the same state as when it was last 34used.</p> 35 36<p>Clever malware with root privileges can hide from detection programs and 37otherwise mask themselves. The rooting software can do this because it is often 38more privileged than the detectors, enabling the software to "lie" to to the 39detection programs.</p> 40 41<p>The dm-verity feature lets you look at a block device, the underlying storage 42layer of the file system, and determine if it matches its expected 43configuration. It does this using a cryptographic hash tree. For every block 44(typically 4k), there is a SHA256 hash.</p> 45 46<p>And since the hash values are stored in a tree of pages, only the top-level 47"root" hash must be trusted to verify the rest of the tree. The ability to 48modify any of the blocks would be equivalent to breaking the cryptographic hash. 49See the following diagram for a depiction of this structure.</p> 50 51<p><img src="images/dm-verity-hash-table.png" alt="dm-verity-hash-table"/><br/> 52A public key is included on the boot partition, which must be verified 53externally by the OEM. That key is used to verify the signature for that hash 54and confirm the device's system partition is protected and unchanged.</p> 55 56<h2 id="operation">Operation</h2> 57 58<p>dm-verity protection lives in the kernel. So if rooting software compromises the 59system before the kernel comes up, it will retain that access. To mitigate this 60risk, most manufacturers verify the kernel using a key burned into the device. 61That key is not changeable once the device leaves the factory.</p> 62 63<p>Manufacturers use that key to verify the signature on the first-level 64bootloader, which in turn verifies the signature on subsequent levels, the 65application bootloader and eventually the kernel. Each manufacturer wishing to 66take advantage of verified boot should have a method for verifying the integrity 67of the kernel. Assuming the kernel has been verified, the kernel can look at a 68block device and verify it as it is mounted.</p> 69 70<p>One way of verifying a block device is to directly hash its contents and compare 71them to a stored value. However, attempting to verify an entire block device can 72take an extended period and consume much of a device's power. Devices would take 73long periods to boot and then be significantly drained prior to use.</p> 74 75<p>Instead, dm-verity verifies blocks individually and only when each one is 76accessed. When read into memory, the block is hashed in parallel. The hash is 77then verified up the tree. And since reading the block is such an expensive 78operation, the latency introduced by this block-level verification is 79comparatively nominal.</p> 80 81<p>If verification fails, the device generates an I/O error indicating the block 82cannot be read. It will appear as if the filesystem has been corrupted, as is 83expected.</p> 84 85<p>Applications may choose to proceed without the resulting data, such as when 86those results are not required to the application's primary function. However, 87if the application cannot continue without the data, it will fail.</p> 88 89<h2 id="prerequisites">Prerequisites</h2> 90 91<h3 id="block-otas">Switching to block-oriented OTAs</h3> 92 93<p>To enable dm-verity on your devices, you <strong>must</strong> move from file-based "over the 94air" (OTA) updates to block-oriented OTAs. This is needed because during OTA, 95Android attempts to change the contents of the system partition at the 96filesystem layer.<br/> 97And since OTA works on a file-by-file basis, it is not guaranteed to write files 98in a consistent order, have a consistent last modified time or superblock, or 99even place the blocks in the same location on the block device. For this reason, 100<em>file-based OTAs will fail on a dm-verity-enabled device.</em><strong>The device will 101not boot after OTA.</strong></p> 102 103<p>So you must use block-oriented OTAs. With block-oriented OTAs, you serve the 104device the difference between the two block images rather than the two sets of 105files. Many manufacturers have already moved to block-oriented OTAs to make them 106more reproducible and predictable.</p> 107 108<p>A block-oriented OTA checks a device build against the corresponding build 109server at the block device level, below the filesystem. This can be done in a 110couple of different ways, each with their own benefits and drawbacks:</p> 111 112<ul> 113<li><em>Copy the full system image to the device</em> - This is simple and makes patch 114generation easy. But it also makes the application of those patches quite 115expensive as the resulting images are large.</li> 116<li><em>Employ a binary differ</em> - These tools, such as <code>bsdiff</code>, simplify patch 117application as images are much smaller. But these tools tend to be memory 118intensive and therefore expensive in generating the patches themselves.</li> 119</ul> 120 121<h3 id="config-dm-verity">Configuring dm-verity</h3> 122 123<p>After switching to block-oriented OTAs, incorporate the latest Android kernel or 124use a stock upstream kernel and enable dm-verity support by including the 125relevant configuration option:<br/> 126<code>CONFIG_DM_VERITY 127</code></p> 128<p>When using the Android kernel, dm-verity is turned on when the kernel is built.</p> 129 130<h2 id="implementation">Implementation</h2> 131 132<h3 id="summary">Summary</h3> 133 134<ol> 135<li>Generate an ext4 system image.</li> 136<li><a href="#heading=h.wiiuowe37q8h">Generate a hash tree</a> for that image.</li> 137<li><a href="#heading=h.cw7mesnrerea">Build a dm-verity table</a> for that hash tree.</li> 138<li><a href="#heading=h.maq6jfk4vx92">Sign that dm-verity table</a> to produce a table 139signature.</li> 140<li><a href="#heading=h.tkceh5wnx7z2">Bundle the table signature</a> and dm-verity table 141into verity metadata.</li> 142<li>Concatenate the system image, the verity metadata, and the hash tree.</li> 143</ol> 144 145<p>See the <a href="http://www.chromium.org/chromium-os/chromiumos-design-docs/verified-boot">The Chromium Projects - Verified 146Boot</a> 147for a detailed description of the hash tree and dm-verity table.</p> 148 149<h3 id="hash-tree">Generating the hash tree</h3> 150 151<p>As described in the <a href="#heading=h.q4z3ftrhbehy">Introduction</a>, the hash tree is 152integral to dm-verity. The 153<a href="https://code.google.com/p/cryptsetup/wiki/DMVerity">cryptsetup</a> tool will 154generate a hash tree for you. Alternatively, a compatible one is defined here:</p> 155 156<pre> 157<your block device name> <your block device name> <block size> <block size> <image size in blocks> <image size in blocks + 8> <root hash> <salt> 158</pre> 159 160<p>To form the hash, the system image is split at layer 0 into 4k blocks, each 161assigned a SHA256 hash. Layer 1 is formed by joining only those SHA256 hashes 162into 4k blocks, resulting in a much smaller image. Layer 2 is formed 163identically, with the SHA256 hashes of Layer 1.</p> 164 165<p>This is done until the SHA256 hashes of the previous layer can fit in a single 166block. When get the SHA256 of that block, you have the root hash of the tree. </p> 167 168<p>The size of the hash tree (and corresponding disk space usage) varies with the 169size of the verified partition. In practice, the size of hash trees tends to be 170small, often less than 30 MB.</p> 171 172<p>If you have a block in a layer that isn't completely filled naturally by the 173hashes of the previous layer, you should pad it with zeroes to achieve the 174expected 4k. This allows you to know the hash tree hasn't been removed and is 175instead completed with blank data.</p> 176 177<p>To generate the hash tree, concatenate the layer 2 hashes onto those for layer 1781, the layer 3 the hashes onto those of layer 2, and so on. Write all of this 179out to disk. Note that this doesn't reference layer 0 of the root hash.</p> 180 181<p>To recap, the general algorithm to construct the hash tree is as follows:</p> 182 183<ol> 184<li>Choose a random salt (hexadecimal encoding).</li> 185<li>Unsparse your system image into 4k blocks.</li> 186<li>For each block, get its (salted) SHA256 hash.</li> 187<li>Concatenate these hashes to form a level</li> 188<li>Pad the level with 0s to a 4k block boundary.</li> 189<li>Concatenate the level to your hash tree.</li> 190<li>Repeat steps 2-6 using the previous level as the source for the next until 191you have only a single hash.</li> 192</ol> 193 194<p>The result of this is a single hash, which is your root hash. This and your salt 195are used during the construction of your dm-verity mapping hash table.</p> 196 197<h3 id="mapping-table">Building the dm-verity mapping table</h3> 198 199<p>Build the dm-verity mapping table, which identifies the block device (or target) 200for the kernel and the location of the hash tree (which is the same value.) This 201mapping is used for <code>fstab</code> generation and booting. The table also identifies 202the size of the blocks and the hash_start, or the offset in hash size blocks 203(length of layer 0).</p> 204 205<p>See <a href="https://code.google.com/p/cryptsetup/wiki/DMVerity">cryptsetup</a> for a 206detailed description of the verity target mapping table fields.</p> 207 208<h3 id="signing">Signing the dm-verity table</h3> 209 210<p>Sign the dm-verity table to produce a table signature. When verifying a 211partition, the table signature is validated first. This is done against a key on 212your boot image in a fixed location. Keys are typically included in the 213manufacturers' build systems for automatic inclusion on devices in a fixed 214location.</p> 215 216<p>To verify the partition with this signature and key combination:</p> 217 218<ol> 219<li>Add an RSA-2048 key in libmincrypt-compatible format to the /boot partition 220at /verity_key. Identify the location of the key used to verify the hash 221tree.</li> 222<li>In the fstab for the relevant entry, add 'verify' to the fs_mgr flags.</li> 223</ol> 224 225<h3 id="metadata">Bundling the table signature into metadata</h3> 226 227<p>Bundle the table signature and dm-verity table into verity metadata. The entire 228block of metadata is versioned so it may be extended, such as to add a second 229kind of signature or change some ordering.</p> 230 231<p>As a sanity check, a magic number is associated with each set of table metadata 232that helps identify the table. Since the length is included in the ext4 system 233image header, this provides a way to search for the metadata without knowing the 234contents of the data itself.</p> 235 236<p>This makes sure you haven't elected to verify an unverified partition. If so, 237the absence of this magic number will halt the verification process. This number 238resembles:<br/> 2390xb001b001</p> 240 241<p>The byte values in hex are:</p> 242 243<ul> 244<li>first byte = b0</li> 245<li>second byte = 01</li> 246<li>third byte = b0</li> 247<li>fourth byte = 01</li> 248</ul> 249 250<p>The following diagram depicts the breakdown of the verity metadata:</p> 251 252<pre><magic number>|<version>|<signature>|<table length>|<table>|<padding> 253\-------------------------------------------------------------------/ 254\----------------------------------------------------------/ | 255 | | 256 | 32K 257 block content 258</pre> 259 260<p>And this table describes those metadata fields.</p> 261 262<table> 263<tr> 264<th>Field</th> 265<th>Purpose</th> 266<th>Size</th> 267<th>Value</th> 268</tr> 269<tr> 270<td>magic number</td> 271<td>used by fs_mgr as a sanity check</td> 272<td>4 bytes</td> 273<td>0xb001b001</td> 274</tr> 275<tr> 276<td>version</td> 277<td>used to version the metadata block</td> 278<td>4 bytes</td> 279<td>currently 0</td> 280</tr> 281<tr> 282<td>signature</td> 283<td>the signature of the table in PKCS1.5 padded form</td> 284<td>256 bytes</td> 285<td></td> 286</tr> 287<tr> 288<td>table length</td> 289<td>the length of the dm-verity table in bytes</td> 290<td>4 bytes</td> 291<td></td> 292</tr> 293<tr> 294<td>table</td> 295<td>the dm-verity table described earlier</td> 296<td>`table length` bytes</td> 297<td></td> 298</tr> 299<tr> 300<td>padding</td> 301<td>this structure is 0-padded to 32k in length</td> 302<td></td> 303<td>0</td> 304</tr> 305</table> 306 307<p>For additional assistance, contact security@android.com.</p> 308 309<h2 id="supporting-docs">Supporting documentation</h2> 310 311<p><a href="https://code.google.com/p/cryptsetup/wiki/DMVerity">cryptsetup - dm-verity: device-mapper block integrity checking 312target</a><br/> 313<a href="http://www.chromium.org/chromium-os/chromiumos-design-docs/verified-boot">The Chromium Projects - Verified 314Boot</a><br/> 315<a 316href="http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=Documentation/device-mapper/verity.txt">Linux Kernel Documentation: 317verity.txt</a></p> 318
