1 page.title=Implementing dm-verity 2 @jd:body 3 4 <!-- 5 Copyright 2015 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="operation">Operation</h2> 28 29 <p>dm-verity protection lives in the kernel. So if rooting software compromises the 30 system before the kernel comes up, it will retain that access. To mitigate this 31 risk, most manufacturers verify the kernel using a key burned into the device. 32 That key is not changeable once the device leaves the factory.</p> 33 34 <p>Manufacturers use that key to verify the signature on the first-level 35 bootloader, which in turn verifies the signature on subsequent levels, the 36 application bootloader and eventually the kernel. Each manufacturer wishing to 37 take advantage of <a href="verified-boot.html">verified boot</a> should have a 38 method for verifying the integrity of the kernel. Assuming the kernel has been 39 verified, the kernel can look at a block device and verify it as it is mounted.</p> 40 41 <p>One way of verifying a block device is to directly hash its contents and compare 42 them to a stored value. However, attempting to verify an entire block device can 43 take an extended period and consume much of a device's power. Devices would take 44 long periods to boot and then be significantly drained prior to use.</p> 45 46 <p>Instead, dm-verity verifies blocks individually and only when each one is 47 accessed. When read into memory, the block is hashed in parallel. The hash is 48 then verified up the tree. And since reading the block is such an expensive 49 operation, the latency introduced by this block-level verification is 50 comparatively nominal.</p> 51 52 <p>If verification fails, the device generates an I/O error indicating the block 53 cannot be read. It will appear as if the filesystem has been corrupted, as is 54 expected.</p> 55 56 <p>Applications may choose to proceed without the resulting data, such as when 57 those results are not required to the application's primary function. However, 58 if the application cannot continue without the data, it will fail.</p> 59 60 <h2 id="implementation">Implementation</h2> 61 62 <h3 id="summary">Summary</h3> 63 64 <ol> 65 <li>Generate an ext4 system image.</li> 66 <li><a href="#hash-tree">Generate a hash tree</a> for that image.</li> 67 <li><a href="#mapping-table">Build a dm-verity table</a> for that hash tree.</li> 68 <li><a href="#signing">Sign that dm-verity table</a> to produce a table 69 signature.</li> 70 <li><a href="#metadata">Bundle the table signature</a> and dm-verity table 71 into verity metadata.</li> 72 <li>Concatenate the system image, the verity metadata, and the hash tree.</li> 73 </ol> 74 75 <p>See the <a href="http://www.chromium.org/chromium-os/chromiumos-design-docs/verified-boot">The Chromium Projects - Verified 76 Boot</a> 77 for a detailed description of the hash tree and dm-verity table.</p> 78 79 <h3 id="hash-tree">Generating the hash tree</h3> 80 81 <p>As described in the <a href="#introduction">Introduction</a>, the hash tree is 82 integral to dm-verity. The 83 <a href="https://code.google.com/p/cryptsetup/wiki/DMVerity">cryptsetup</a> tool will 84 generate a hash tree for you. Alternatively, a compatible one is defined here:</p> 85 86 <pre> 87 <your block device name> <your block device name> <block size> <block size> <image size in blocks> <image size in blocks + 8> <root hash> <salt> 88 </pre> 89 90 <p>To form the hash, the system image is split at layer 0 into 4k blocks, each 91 assigned a SHA256 hash. Layer 1 is formed by joining only those SHA256 hashes 92 into 4k blocks, resulting in a much smaller image. Layer 2 is formed 93 identically, with the SHA256 hashes of Layer 1.</p> 94 95 <p>This is done until the SHA256 hashes of the previous layer can fit in a single 96 block. When get the SHA256 of that block, you have the root hash of the tree. </p> 97 98 <p>The size of the hash tree (and corresponding disk space usage) varies with the 99 size of the verified partition. In practice, the size of hash trees tends to be 100 small, often less than 30 MB.</p> 101 102 <p>If you have a block in a layer that isn't completely filled naturally by the 103 hashes of the previous layer, you should pad it with zeroes to achieve the 104 expected 4k. This allows you to know the hash tree hasn't been removed and is 105 instead completed with blank data.</p> 106 107 <p>To generate the hash tree, concatenate the layer 2 hashes onto those for layer 108 1, the layer 3 the hashes onto those of layer 2, and so on. Write all of this 109 out to disk. Note that this doesn't reference layer 0 of the root hash.</p> 110 111 <p>To recap, the general algorithm to construct the hash tree is as follows:</p> 112 113 <ol> 114 <li>Choose a random salt (hexadecimal encoding).</li> 115 <li>Unsparse your system image into 4k blocks.</li> 116 <li>For each block, get its (salted) SHA256 hash.</li> 117 <li>Concatenate these hashes to form a level</li> 118 <li>Pad the level with 0s to a 4k block boundary.</li> 119 <li>Concatenate the level to your hash tree.</li> 120 <li>Repeat steps 2-6 using the previous level as the source for the next until 121 you have only a single hash.</li> 122 </ol> 123 124 <p>The result of this is a single hash, which is your root hash. This and your salt 125 are used during the construction of your dm-verity mapping hash table.</p> 126 127 <h3 id="mapping-table">Building the dm-verity mapping table</h3> 128 129 <p>Build the dm-verity mapping table, which identifies the block device (or target) 130 for the kernel and the location of the hash tree (which is the same value.) This 131 mapping is used for <code>fstab</code> generation and booting. The table also identifies 132 the size of the blocks and the hash_start, or the offset in hash size blocks 133 (length of layer 0).</p> 134 135 <p>See <a href="https://code.google.com/p/cryptsetup/wiki/DMVerity">cryptsetup</a> for a 136 detailed description of the verity target mapping table fields.</p> 137 138 <h3 id="signing">Signing the dm-verity table</h3> 139 140 <p>Sign the dm-verity table to produce a table signature. When verifying a 141 partition, the table signature is validated first. This is done against a key on 142 your boot image in a fixed location. Keys are typically included in the 143 manufacturers' build systems for automatic inclusion on devices in a fixed 144 location.</p> 145 146 <p>To verify the partition with this signature and key combination:</p> 147 148 <ol> 149 <li>Add an RSA-2048 key in libmincrypt-compatible format to the /boot partition 150 at /verity_key. Identify the location of the key used to verify the hash 151 tree.</li> 152 <li>In the fstab for the relevant entry, add 'verify' to the fs_mgr flags.</li> 153 </ol> 154 155 <h3 id="metadata">Bundling the table signature into metadata</h3> 156 157 <p>Bundle the table signature and dm-verity table into verity metadata. The entire 158 block of metadata is versioned so it may be extended, such as to add a second 159 kind of signature or change some ordering.</p> 160 161 <p>As a sanity check, a magic number is associated with each set of table metadata 162 that helps identify the table. Since the length is included in the ext4 system 163 image header, this provides a way to search for the metadata without knowing the 164 contents of the data itself.</p> 165 166 <p>This makes sure you haven't elected to verify an unverified partition. If so, 167 the absence of this magic number will halt the verification process. This number 168 resembles:<br/> 169 0xb001b001</p> 170 171 <p>The byte values in hex are:</p> 172 173 <ul> 174 <li>first byte = b0</li> 175 <li>second byte = 01</li> 176 <li>third byte = b0</li> 177 <li>fourth byte = 01</li> 178 </ul> 179 180 <p>The following diagram depicts the breakdown of the verity metadata:</p> 181 182 <pre><magic number>|<version>|<signature>|<table length>|<table>|<padding> 183 \-------------------------------------------------------------------/ 184 \----------------------------------------------------------/ | 185 | | 186 | 32K 187 block content 188 </pre> 189 190 <p>And this table describes those metadata fields.</p> 191 192 <table> 193 <tr> 194 <th>Field</th> 195 <th>Purpose</th> 196 <th>Size</th> 197 <th>Value</th> 198 </tr> 199 <tr> 200 <td>magic number</td> 201 <td>used by fs_mgr as a sanity check</td> 202 <td>4 bytes</td> 203 <td>0xb001b001</td> 204 </tr> 205 <tr> 206 <td>version</td> 207 <td>used to version the metadata block</td> 208 <td>4 bytes</td> 209 <td>currently 0</td> 210 </tr> 211 <tr> 212 <td>signature</td> 213 <td>the signature of the table in PKCS1.5 padded form</td> 214 <td>256 bytes</td> 215 <td></td> 216 </tr> 217 <tr> 218 <td>table length</td> 219 <td>the length of the dm-verity table in bytes</td> 220 <td>4 bytes</td> 221 <td></td> 222 </tr> 223 <tr> 224 <td>table</td> 225 <td>the dm-verity table described earlier</td> 226 <td>`table length` bytes</td> 227 <td></td> 228 </tr> 229 <tr> 230 <td>padding</td> 231 <td>this structure is 0-padded to 32k in length</td> 232 <td></td> 233 <td>0</td> 234 </tr> 235 </table> 236
