src/devices/tech/security/verifiedboot/verified-boot.jd

page.title=Verifying Boot
@jd:body

<!--
    Copyright 2015 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=objective>Objective</h2>
<p>Verified boot guarantees the integrity of the device software starting from a
hardware root of trust up to the system partition. During boot, each stage
verifies the integrity and authenticity of the next stage before executing it.</p>

<p>This capability can be used to warn users of unexpected changes to the
software when they acquire a used device, for example. It will also provide an
additional signal of device integrity for remote attestation, and together with
encryption and Trusted Execution Environment (TEE) root of trust binding, adds
another layer of protection for user data against malicious system software.</p>

<p>Note that if verification fails at any stage, the user must be visibly
notified and always be given an option to continue using the device at
their own discretion.</p>

<h2 id=glossary>Glossary</h2>

<table>
 <tr>
    <td>
<p><strong>Term</strong></p>
</td>
    <td>
<p><strong>Definition</strong></p>
</td>
 </tr>
 <tr>
    <td>
<p>Boot state</p>
</td>
    <td>
<p>The boot state of the device describes the level of protection provided to the
end user if the device boots. Boot states are GREEN, YELLOW, ORANGE, and RED.</p>
</td>
 </tr>
 <tr>
    <td>
<p>Device state</p>
</td>
    <td>
<p>The device state indicates how freely software can be flashed to the device.
Device states are LOCKED, UNLOCKED, or VERIFIED.</p>
</td>
 </tr>
 <tr>
    <td>
<p>dm-verity</p>
</td>
    <td>
<p>Linux kernel driver for verifying the integrity of a partition at runtime using
a hash tree and signed metadata.</p>
</td>
 </tr>
 <tr>
    <td>
<p>Keystore</p>
</td>
    <td>
<p>A keystore is a signed collection of public keys.</p>
</td>
 </tr>
 <tr>
    <td>
<p>OEM key</p>
</td>
    <td>
<p>The OEM key is a fixed, tamper-protected key available to the bootloader that
must be used to verify the boot image.</p>
</td>
 </tr>
 <tr>
    <td>
<p>User provided keystore</p>
</td>
    <td>
<p>The user keystore is a keystore flashed to the device via <code>fastboot 
flash keystore &lt;path&gt;</code>.</p>
</td>
 </tr>
</table>

<h2 id=overview>Overview</h2>

<p>In addition to device state - which already exists in devices and controls
whether the bootloader allows new software to be flashed - we introduce the
concept of boot state that indicates the state of device integrity. We also
add a third device state, which allows developers for example, to flash the
software more frequently without a data wipe while still benefiting from
verification.</p>

<h3 id=verification_keys>Verification keys</h3>

<p>Bootloader integrity must be verified using a hardware root of trust. For
verifying boot and recovery images, the bootloader must have a fixed OEM key
available to it. It must always attempt to verify the boot image using the OEM
key and only try other possible keys if this verification fails.</p>

<p>It must be possible for the user to flash alternative image verification keys
to the device, and the bootloader must try verification using these keys if
verification using the OEM key fails. However, using an image signed with the
user-provided keystore must result in a notification to be shown, as described
below.</p>

<h3 id=boot_state>Boot state</h3>

<p>A verified device will ultimately boot into one of four states during each boot
attempt:</p>

<ul>
  <li> GREEN, indicating a full chain of trust extending from the bootloader to the
system partition, including the bootloader, boot partition, and system
partition.
</ul>

<ul>
  <li> YELLOW, indicating a chain of trust starting from a user-provided keystore
and extending up. To enable users to acquire trust in their keystore,
bootloaders are required to display a partial hash of the verifying keystore
during boot.
</ul>

<ul>
  <li> ORANGE, indicating a device may be freely modified. Device integrity is
left to the user to verify out-of-band.
</ul>

<ul>
  <li> RED, indicating the device has failed verification. This must display a
warning to the user before allowing the boot process to continue.
</ul>

<p>The recovery partition must also be verified and should be verified in the
exact same way.</p>

<img src="../images/verified_boot.png" alt="Verified boot flow" id="figure1" />
<p class="img-caption"><strong>Figure 1.</strong> Verified boot flow</p>

<h3 id=device_state>Device state</h3>

<p>The device is required to be in one of three states at all times:</p>

<ol>
  <li>LOCKED, indicating the device cannot currently be flashed. In the image
above, a LOCKED device must boot into the GREEN state, YELLOW state, or RED
state during any attempted boot. It must not be possible to alter the user
keystore in the LOCKED state.

  <li>VERIFIED, indicating someone in physical control of the device may perform
limited actions intended to change the state of the device but may not break
its current chain of trust. In the image above, a VERIFIED device must boot
into the GREEN state, YELLOW state, or RED state during each attempted boot. It
must not be possible to alter the user keystore in the VERIFIED state. It must
be possible to:
   <ol>
    <li> Flash the following partitions:
    <ol>
      <li> bootloader
      <li> boot partition
      <li> system partition
      <li> vendor partition
      <li> recovery partition
    </ol>
    <li> Erase the following partitions:
    <ol>
      <li> userdata
      <li> cache
    </ol>
   </ol>

<p>Boot and recovery image signatures may be verified during the flashing process,
and the bootloader may reject images that do not validate against the OEM key
or the user-provided keystore at this point. However, signatures must also be
verified again at every boot.

  <li>UNLOCKED, indicating the device may be flashed freely and is not intended
to be verified.
</ol>

<h2 id=detailed_design>Detailed design</h2>

<p>Achieving full chain of trust requires support from both the bootloader and the
software on the boot partition, specifically <code>init</code>, which is responsible for
mounting additional partitions. Verification metadata must also be appended to the
system partition and any additional partitions whose integrity should be
verified.</p>

<h3 id=bootloader_requirements>Bootloader requirements</h3>

<p>The bootloader is the guardian of the device state, manages the user-provided
keystore, and is responsible for initializing the TEE and binding its root of
trust.</p>

<p>Most importantly, the bootloader must verify the integrity of the boot and/or
recovery partition before moving execution to the kernel and display the
warnings or notifications in the section <a href="#boot_state">Boot state</a>.</p>

<h4 id=changing_device_state><strong>Changing device state</strong></h4>

<p>State changes are performed using the <code>fastboot flashing [unlock |
verified | lock]</code> command. And to protect user data, <strong>all</strong>
state transitions require a data wipe. Note the user must be asked for
confirmation before data is deleted.</p>

<img src="../images/device_states.png" alt="Changing device states" id="figure2" />
<p class="img-caption"><strong>Figure 2.</strong> Changing device states</p>

<ol>
  <li>The UNLOCKED to LOCKED transition is anticipated when a user buys a used
development device. As a result of locking the device, the user should have
confidence that it is in a state produced by the OEM.

  <li>The LOCKED to UNLOCKED transition is expected in the case where a developer
wishes to disable verification on the device.

  <li>The LOCKED to VERIFIED transition is expected in the case where a developer
wishes to do development on the device and doesn’t want to wipe data frequently.

  <li>The VERIFIED to LOCKED transition is idempotent with the above.

  <li>The UNLOCKED to VERIFIED transition is anticipated when a user wishes to put a
development device in a more secure state but may not want to prevent
themselves from flashing new system images.

  <li> The VERIFIED to UNLOCKED transition is idempotent with the above.
</ol>

<p>Requirements for <code>fastboot</code> commands that alter device state are listed in the table below:</p>
<table>
 <tr>
    <td>
<p><strong><code>fastboot</code> command</strong></p>
</td>
    <td>
<p><strong>Requirements</strong></p>
</td>
 </tr>
 <tr>
    <td>
<code>
flashing lock</code></td>
    <td>
<ul>
  <li>Wipe data after asking the user for confirmation     
  <li>Clear a write-protected bit indicating the device is unlocked
  <li>Clear a write-protected bit indicating the device is verified
</ul>
</td>
 </tr>
 <tr>
    <td>
<code>
flashing unlock</code></td>
    <td>
<ul>
  <li>Wipe data after asking the user for confirmation     
  <li>Set a write-protected bit indicating the device is unlocked
  <li>Clear a write-protected bit indicating the device is verified
</ul>
</td>
 </tr>
 <tr>
    <td>
<code>
flashing verified</code></td>
    <td>
<ul>
  <li>Wipe data after asking the user for confirmation     
  <li>Clear a write-protected bit indicating the device is unlocked
  <li>Set a write-protected bit indicating the device is verified
</ul>
</td>
 </tr>
</table>

<p>When altering partition contents, the bootloader must check the bits set by
the above commands as described in the following table:</p>
<table>
 <tr>
    <td>
<p><strong><code>fastboot</code> command</strong></p>
</td>
    <td>
<p><strong>Requirements</strong></p>
</td>
 </tr>
 <tr>
    <td>
<code>
flash &lt;partition&gt;</code></td>
    <td>
<ul>
  <li>If the bit set by <code>flashing unlock</code> is set, flash the partition as normal    
  <li>If this bit is not set, check the bit set by <code>flashing verified</code>
    <ul>
      <li>If this bit is not set, exit with an error
      <li>If this bit is set and &lt;partition&gt; is on the list provided in
          the section <a href="#device_state">Device state</a>, flash the partition as normal.
   </ul>
</ul>
    </td>
 </tr>
</table>

<p>The same checks should be performed for any <code>fastboot</code> command that can be used to change the contents of partitions.</p>

<h4 id=managing_user_provided_keystore><strong>Managing user-provided keystore</strong></h4>

<p>Users can flash their own verification keys to the device, which must be
used to verify the integrity of boot and recovery images if verification
against the OEM key fails. This allows a developer to change the system
software frequently, for example,  while still keeping verified boot enabled.</p>

<p>The bootloader is responsible for maintaining the integrity of the user
keystore. It must not be possible to change the contents of the keystore unless
the device is UNLOCKED. When the user flashes a new keystore to the device, the
bootloader must sign it using the TEE and store the signed keystore. Before
using keys from the keystore, the bootloader must use the TEE to verify the
signature.</p>

<p>Requirements for <code>fastboot</code> commands used to manage the user-provided keystore are listed in the table
below:</p>
<table>
 <tr>
    <td>
<p><strong><code>fastboot</code> command</strong></p>
</td>
    <td>
<p>Requirements</p>
</td>
 </tr>
 <tr>
    <td>
<code>
flash keystore &lt;filename&gt;</code></td>
    <td>
<ul>
  <li>Check the bit set by <code>flashing unlock</code>; if not set, exit with an error 
  <li>Validate the given keystore against the format provided in section <a href="#keystore_format">Keystore format</a>
  <li>Pass the keystore to the TEE for signing
  <li>Write the signed keystore to the write-protected user keystore storage
      area (location to be determined by the OEM)
</ul>
</td>
 </tr>
 <tr>
    <td>
<code>
erase keystore</code></td>
    <td>
<ul>
  <li>Check the bit set by <code>flashing unlock</code>; if not set, exit with an error
  <li>Erase the keystore stored in the write-protected user keystore storage area
</ul>
    </td>
 </tr>
</table>

<h4 id=binding_tee_root_of_trust><strong>Binding TEE root of trust</strong></h4>

<p>After the bootloader has initialized the TEE and performed boot image
verification steps, it must pass the following information to the TEE Keymaster
as the root of trust:</p>

<ol>
  <li>The public key that was used to sign the boot image
  <li>The current device state (LOCKED, VERIFIED, or UNLOCKED)
</ol>

<p>This changes the keys derived by the TEE. For disk encryption, for example,
this prevents user data from being decrypted when the device is booted using a
potentially untrusted image signed with a different key.</p>

<p class="note"><strong>Note:</strong> This means if the system software or the
device state changes, encrypted user data will no longer be accessible as the
TEE will attempt to use a different key to decrypt the data.</p>

<h4 id=booting_into_recovery><strong>Booting into recovery</strong></h4>

<p>The recovery image should be verified in exactly the same manner as the boot
image.</p>

<h3 id=boot_partition>Boot partition</h3>

<p>Once execution has moved to the boot and/or recovery image, <code>init</code> is responsible
for setting up verification for further partitions. Due to its large size, the
system partition cannot be verified similarly to previous parts but must be
verified in real time as it’s being accessed by using the dm-verity kernel
driver.</p>

<p>When <code>fs_mgr</code> flags in the device’s <code>fstab</code> indicate a partition should be
verified, <code>init</code> will verify the signed verity metadata appended to the partition
before mounting it and set up the dm-verity device for the partition.</p>

<h4 id=managing_dm-verity><strong>Managing dm-verity</strong></h4>

<p>By default, dm-verity operates in verifying mode and verifies each block read
from the device against a hash tree passed to it by <code>init</code> during set up. If it
comes across a block that fails to verify, it returns an I/O error and makes
the block with unexpected contents inaccessible to user space. Depending on
which block is corrupted, this may cause some of the programs that reside on
the partition to malfunction.</p>

<p>Using a persistent flag, dm-verity can also be configured to function in
logging mode. This flag is read by <code>init</code> when setting up dm-verity. And if the
mode flag is set to logging or verity metadata cannot be verified, a warning
must be displayed to the user, similar to the warning the bootloader shows
before booting into RED state.</p>

<img src="../images/dm-verity_mgmt.png" alt="dm-verity management" id="figure3" />
<p class="img-caption"><strong>Figure 3.</strong> dm-verity management</p>

<h4 id=recovering_from_dm-verity_errors><strong>Recovering from dm-verity errors</strong></h4>

<p>Since the system partition is by far larger than the boot partition, the
probability of verification errors is also higher. Specifically, there is a
larger probability of unintentional disk corruption, which will cause a
verification failure and can potentially make an otherwise functional device
unusable if a critical block in the partition can no longer be accessed.</p>

<p>It’s generally not possible to distinguish disk corruption from malicious
changes, so any change to the system partition must result in the user being
notified, and no unverified data must leak to user space until a warning has
been shown. However, we must also assume most verification failures are
not the result of malicious behavior; so the user must also have an option to
continue using the device without verification.</p>

<p>If dm-verity is in verifying mode and a block of a partition fails to verify,
it will send a <code>uevent</code> to notify user space of the error. This event must be
handled by software in the boot partition as potentially any program residing
on the verified partition may not function anymore. When the event is received,
the persistent dm-verity state must be updated to set the mode flag to logging
mode, and the device must be rebooted. When the device restarts,
<code>init</code> will warn the user of changes to the partition before mounting it.</p>

<h3 id=verified_partition>Verified partition</h3>

<p>In a verified device, the system partition must always be verified. But any
other read-only partition can also be set to be verified, as well. Specifically,
any read-only partition that contains executable code must be verified on a
verified device. This include the vendor partition, if one exists, for example.</p>

<p>In order for a partition to be verified, signed verity metadata must be
appended to it. The metadata consists of a hash tree of the partition contents
and a verity table containing signed parameters and the root of the hash tree.
If this information is missing or invalid when <code>init</code> attempts to
mount the device, the user must be warned.</p>

<h2 id=implementation_details>Implementation details</h2>

<h3 id=key_types_and_sizes>Key types and sizes</h3>

<p>The OEM key is recommended to be an RSA key with a modulus of 2048 bits or
higher and a public exponent of 65537 (F4). The OEM key is required to be of
equivalent or greater strength than such a key.</p>

<h3 id=signature_format>Signature format</h3>


<p>The signature on an Android verifiable boot image is an ASN.1 DER-encoded
message, which can be parsed with a decoder similar to the one found at: <a
href="https://android.googlesource.com/platform/bootable/recovery/+/f4a6ab27b335b69fbc419a9c1ef263004b561265/asn1_decoder.cpp">platform/bootable/recovery/asn1_decoder.cpp</a><br/>
The message format itself is as follows:</p>

<pre>
AndroidVerifiedBootSignature DEFINITIONS ::=
     BEGIN
          FormatVersion ::= INTEGER
          Certificate ::= Certificate OPTIONAL
          AlgorithmIdentifier  ::=  SEQUENCE {
               algorithm OBJECT IDENTIFIER,
               parameters ANY DEFINED BY algorithm OPTIONAL
          }
          AuthenticatedAttributes ::= SEQUENCE {
                 target CHARACTER STRING,
                 length INTEGER
          }

          Signature ::= OCTET STRING
     END
</pre>

<p>The <code>Certificate</code> field is the full X.509 certificate containing
the public key used for signing, as defined by <a
href="http://tools.ietf.org/html/rfc5280#section-4.1.1.2">RFC5280</a> section
4.1. The bootloader must ignore this field and must NOT use the key
specified in the certificate to verify the signature. Signatures must always be
verified against the OEM key or the user-provided keystore only.</p>

<p>The remaining structure is similar to that defined by <a
href="http://tools.ietf.org/html/rfc5280#section-4.1.1.2">RFC5280</a> sections
4.1.1.2 and 4.1.1.3 with the exception of the
<code>AuthenticatedAttributes</code> field. This field contains the length of
the image to be verified as an integer and the partition where the image can
be found (boot, recovery, etc.).</p>

<h3 id=signing_and_verifying_an_image>Signing and verifying an image</h3>

<p>To produce a signed image:</p>
<ol>
  <li>Generate the unsigned image.
  <li>0-pad the image to the next page size boundary (omit this step if already
aligned).
  <li>Populate the fields of the <code>AuthenticatedAttributes</code> section above based on the padded image and desired target partition.
  <li>Append the <code>AuthenticatedAttributes</code> structure above to the image.
  <li>Sign the image.
</ol>

<p>To verify the image:</p>
<ol>
  <li>Determine the size of the image to be loaded including padding (eg, by reading
a header).
  <li>Read the signature located at the offset above.
  <li>Validate the contents of the <code>AuthenticatedAttributes</code> field.
If these values do not validate, treat it as a signature validation error.
  <li>Verify the image and <code>AuthenticatedAttributes</code> sections.
</ol>

<h3 id=keystore_format>Keystore format</h3>

<p>The Android verified boot keystore format is an ASN.1 DER-encoded document. Its
 specification follows:</p>

<pre>
AndroidVerifiedBootKeystore DEFINITIONS ::=
     BEGIN
          FormatVersion ::= INTEGER
          KeyBag ::= SEQUENCE {
               Key  ::= SEQUENCE {
                    AlgorithmIdentifier  ::=  SEQUENCE {
                         algorithm OBJECT IDENTIFIER,
                         parameters ANY DEFINED BY algorithm
                    OPTIONAL
                    }
                    KeyMaterial ::= RSAPublicKey
               }
          }
          Signature ::= AndroidVerifiedBootSignature OPTIONAL
     END
</pre>

<p>Where <code>RSAPublicKey</code>, <code>AlgorithmIdentifier</code>, and
parameters are as specified in <a
href="http://tools.ietf.org/html/rfc3279#section-2.3.1">RFC3279</a>. Other key
types specified in RFC3279 section 2.3 may optionally be supported,
in which case the appropriate type for <code>Key</code> must be used.</p>

<h3 id=keystore_location>Keystore location</h3>

<p>The location of the keystore is not specified here, but that location must be
known to the bootloader and both readable and writable by it. Reading should
happen as per the above; writing a new keystore should be accomplished through
<code>fastboot flash keystore &lt;path&gt;</code>. Sufficient storage must be
provided for at least one key, with storage for additional keys recommended.</p>

<h3 id=user_experience>User experience</h3>

<p>A user in the GREEN boot state should see no additional user interaction besides that
required by normal device boot. In other boot states, the user should see a
warning for at least five seconds. Should the user interact with the device during
this time, the warning should remain visible until the user agrees to continue.</p>

<p>Sample user interaction screens for other states are shown in the following table:</p>
<table>
 <tr>
    <td>
<p><strong>Device state</strong></p>
</td>
    <td>
<p><strong>Sample UX</strong></p>
</td>
 </tr>
 <tr>
    <td>
<p>YELLOW (before and after user interaction)</p>
</td>
    <td>
<img src="../images/boot_yellow1.png" alt="Yellow device state 1" id="figure4" />
<p class="img-caption"><strong>Figure 4.</strong> Yellow state example 1 UI</p>
</td>
    <td>
<img src="../images/boot_yellow2.png" alt="Yellow device state 2" id="figure5" />
<p class="img-caption"><strong>Figure 5.</strong> Yellow state example 2 UI</p>
</td>

 </tr>
 <tr>
    <td>
<p>ORANGE</p>
</td>
    <td>
<img src="../images/boot_orange.png" alt="Orange device state" id="figure6" />
<p class="img-caption"><strong>Figure 6.</strong> Orange state example UI</p>
</td>
 </tr>
 <tr>
    <td>
<p>RED</p>
</td>
    <td>
<img src="../images/boot_red.png" alt="Red device state" id="figure7" />
<p class="img-caption"><strong>Figure 7.</strong> Red state example UI</p>
</td>
 </tr>
</table>