Cryptographic security for MAX_BOOT_LEVEL

Use a KDF to generate a key for each boot level, anchored in a key
which can only be used once per boot.

Bug: 176450483
Test: aosp/1577966: ensure key created at level 40 stops working at 41
Test: keystore2_test
Change-Id: I12530cd13cb176251c8a0b5431d53c0a7c1bc02d

9 files changed, 641 insertions, 117 deletions

diff --git a/keystore2/src/boot_level_keys.rs b/keystore2/src/boot_level_keys.rs
new file mode 100644
index 00000000..9af7dbbc
--- /dev/null
+++ b/keystore2/src/boot_level_keys.rs
@@ -0,0 +1,417 @@
+// Copyright 2021, 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.
+
+//! Offer keys based on the "boot level" for superencryption.
+
+use android_hardware_security_keymint::aidl::android::hardware::security::keymint::{
+    Algorithm::Algorithm, BeginResult::BeginResult, Digest::Digest, ErrorCode::ErrorCode,
+    IKeyMintDevice::IKeyMintDevice, IKeyMintOperation::IKeyMintOperation,
+    KeyParameter::KeyParameter, KeyPurpose::KeyPurpose, SecurityLevel::SecurityLevel,
+};
+use android_system_keystore2::aidl::android::system::keystore2::{
+    Domain::Domain, KeyDescriptor::KeyDescriptor, ResponseCode::ResponseCode,
+};
+use anyhow::{Context, Result};
+use binder::Strong;
+use keystore2_crypto::{hkdf_expand, ZVec, AES_256_KEY_LENGTH};
+use std::{collections::VecDeque, convert::TryFrom};
+
+use crate::{
+    database::{
+        BlobMetaData, BlobMetaEntry, CertificateInfo, DateTime, KeyEntry, KeyEntryLoadBits,
+        KeyIdGuard, KeyMetaData, KeyMetaEntry, KeyType, KeystoreDB, SubComponentType, Uuid,
+    },
+    error::{map_km_error, Error},
+    globals::get_keymint_device,
+    key_parameter::KeyParameterValue,
+    super_key::KeyBlob,
+    utils::{key_characteristics_to_internal, Asp, AID_KEYSTORE},
+};
+
+/// Wrapper for operating directly on a KeyMint device.
+/// These methods often mirror methods in [`crate::security_level`]. However
+/// the functions in [`crate::security_level`] make assumptions that hold, and has side effects
+/// that make sense, only if called by an external client through binder.
+/// In addition we are trying to maintain a separation between interface services
+/// so that the architecture is compatible with a future move to multiple thread pools.
+/// So the simplest approach today is to write new implementations of them for internal use.
+/// Because these methods run very early, we don't even try to cooperate with
+/// the operation slot database; we assume there will be plenty of slots.
+struct KeyMintDevice {
+    asp: Asp,
+    km_uuid: Uuid,
+}
+
+impl KeyMintDevice {
+    fn get(security_level: SecurityLevel) -> Result<KeyMintDevice> {
+        let (asp, _hw_info, km_uuid) = get_keymint_device(&security_level)
+            .context("In KeyMintDevice::get: get_keymint_device failed")?;
+        Ok(KeyMintDevice { asp, km_uuid })
+    }
+
+    /// Generate a KM key and store in the database.
+    fn generate_and_store_key(
+        &self,
+        db: &mut KeystoreDB,
+        key_desc: &KeyDescriptor,
+        params: &[KeyParameter],
+    ) -> Result<()> {
+        let km_dev: Strong<dyn IKeyMintDevice> = self
+            .asp
+            .get_interface()
+            .context("In generate_and_store_key: Failed to get KeyMint device")?;
+        let creation_result = map_km_error(km_dev.generateKey(params, None))
+            .context("In generate_and_store_key: generateKey failed")?;
+        let key_parameters = key_characteristics_to_internal(creation_result.keyCharacteristics);
+
+        let creation_date =
+            DateTime::now().context("In generate_and_store_key: DateTime::now() failed")?;
+
+        let mut key_metadata = KeyMetaData::new();
+        key_metadata.add(KeyMetaEntry::CreationDate(creation_date));
+        let mut blob_metadata = BlobMetaData::new();
+        blob_metadata.add(BlobMetaEntry::KmUuid(self.km_uuid));
+
+        db.store_new_key(
+            &key_desc,
+            &key_parameters,
+            &(&creation_result.keyBlob, &blob_metadata),
+            &CertificateInfo::new(None, None),
+            &key_metadata,
+            &self.km_uuid,
+        )
+        .context("In generate_and_store_key: store_new_key failed")?;
+        Ok(())
+    }
+
+    /// This does the lookup and store in separate transactions; caller must
+    /// hold a lock before calling.
+    fn lookup_or_generate_key(
+        &self,
+        db: &mut KeystoreDB,
+        key_desc: &KeyDescriptor,
+        params: &[KeyParameter],
+    ) -> Result<(KeyIdGuard, KeyEntry)> {
+        // We use a separate transaction for the lookup than for the store
+        // - to keep the code simple
+        // - because the caller needs to hold a lock in any case
+        // - because it avoids holding database locks during slow
+        //   KeyMint operations
+        let lookup = db.load_key_entry(
+            &key_desc,
+            KeyType::Client,
+            KeyEntryLoadBits::KM,
+            AID_KEYSTORE,
+            |_, _| Ok(()),
+        );
+        match lookup {
+            Ok(result) => return Ok(result),
+            Err(e) => match e.root_cause().downcast_ref::<Error>() {
+                Some(&Error::Rc(ResponseCode::KEY_NOT_FOUND)) => {}
+                _ => return Err(e),
+            },
+        }
+        self.generate_and_store_key(db, &key_desc, &params)
+            .context("In lookup_or_generate_key: generate_and_store_key failed")?;
+        db.load_key_entry(&key_desc, KeyType::Client, KeyEntryLoadBits::KM, AID_KEYSTORE, |_, _| {
+            Ok(())
+        })
+        .context("In lookup_or_generate_key: load_key_entry failed")
+    }
+
+    /// Call the passed closure; if it returns `KEY_REQUIRES_UPGRADE`, call upgradeKey, and
+    /// write the upgraded key to the database.
+    fn upgrade_keyblob_if_required_with<T, F>(
+        &self,
+        db: &mut KeystoreDB,
+        km_dev: &Strong<dyn IKeyMintDevice>,
+        key_id_guard: KeyIdGuard,
+        key_blob: &KeyBlob,
+        f: F,
+    ) -> Result<T>
+    where
+        F: Fn(&[u8]) -> Result<T, Error>,
+    {
+        match f(key_blob) {
+            Err(Error::Km(ErrorCode::KEY_REQUIRES_UPGRADE)) => {
+                let upgraded_blob = map_km_error(km_dev.upgradeKey(key_blob, &[]))
+                    .context("In upgrade_keyblob_if_required_with: Upgrade failed")?;
+
+                let mut new_blob_metadata = BlobMetaData::new();
+                new_blob_metadata.add(BlobMetaEntry::KmUuid(self.km_uuid));
+
+                db.set_blob(
+                    &key_id_guard,
+                    SubComponentType::KEY_BLOB,
+                    Some(&upgraded_blob),
+                    Some(&new_blob_metadata),
+                )
+                .context(concat!(
+                    "In upgrade_keyblob_if_required_with: ",
+                    "Failed to insert upgraded blob into the database"
+                ))?;
+
+                Ok(f(&upgraded_blob).context(concat!(
+                    "In upgrade_keyblob_if_required_with: ",
+                    "Closure failed after upgrade"
+                ))?)
+            }
+            result => Ok(result.context("In upgrade_keyblob_if_required_with: Closure failed")?),
+        }
+    }
+
+    /// Use the created key in an operation that can be done with
+    /// a call to begin followed by a call to finish.
+    fn use_key_in_one_step(
+        &self,
+        db: &mut KeystoreDB,
+        key_id_guard: KeyIdGuard,
+        key_entry: &KeyEntry,
+        purpose: KeyPurpose,
+        operation_parameters: &[KeyParameter],
+        input: &[u8],
+    ) -> Result<Vec<u8>> {
+        let km_dev: Strong<dyn IKeyMintDevice> = self
+            .asp
+            .get_interface()
+            .context("In use_key_in_one_step: Failed to get KeyMint device")?;
+
+        let (key_blob, _blob_metadata) = key_entry
+            .key_blob_info()
+            .as_ref()
+            .ok_or_else(Error::sys)
+            .context("use_key_in_one_step: Keyblob missing")?;
+        let key_blob = KeyBlob::Ref(&key_blob);
+
+        let begin_result: BeginResult = self
+            .upgrade_keyblob_if_required_with(db, &km_dev, key_id_guard, &key_blob, |blob| {
+                map_km_error(km_dev.begin(purpose, blob, operation_parameters, &Default::default()))
+            })
+            .context("In use_key_in_one_step: Failed to begin operation.")?;
+        let operation: Strong<dyn IKeyMintOperation> = begin_result
+            .operation
+            .ok_or_else(Error::sys)
+            .context("In use_key_in_one_step: Operation missing")?;
+        map_km_error(operation.finish(Some(input), None, None, None, None))
+            .context("In use_key_in_one_step: Failed to finish operation.")
+    }
+}
+
+/// This is not thread safe; caller must hold a lock before calling.
+/// In practice the caller is SuperKeyManager and the lock is the
+/// Mutex on its internal state.
+pub fn get_level_zero_key(db: &mut KeystoreDB) -> Result<ZVec> {
+    let key_desc = KeyDescriptor {
+        domain: Domain::APP,
+        nspace: AID_KEYSTORE as i64,
+        alias: Some("boot_level_key".to_string()),
+        blob: None,
+    };
+    let params = [
+        KeyParameterValue::Algorithm(Algorithm::HMAC).into(),
+        KeyParameterValue::Digest(Digest::SHA_2_256).into(),
+        KeyParameterValue::KeySize(256).into(),
+        KeyParameterValue::MinMacLength(256).into(),
+        KeyParameterValue::KeyPurpose(KeyPurpose::SIGN).into(),
+        KeyParameterValue::MaxUsesPerBoot(1).into(),
+    ];
+    // We use TRUSTED_ENVIRONMENT here because it is the authority on when
+    // the device has rebooted.
+    let km_dev: KeyMintDevice = KeyMintDevice::get(SecurityLevel::TRUSTED_ENVIRONMENT)
+        .context("In get_level_zero_key: KeyMintDevice::get failed")?;
+    let (key_id_guard, key_entry) = km_dev
+        .lookup_or_generate_key(db, &key_desc, &params)
+        .context("In get_level_zero_key: lookup_or_generate_key failed")?;
+
+    let params = [KeyParameterValue::MacLength(256).into()];
+    let level_zero_key = km_dev
+        .use_key_in_one_step(
+            db,
+            key_id_guard,
+            &key_entry,
+            KeyPurpose::SIGN,
+            &params,
+            b"Create boot level key",
+        )
+        .context("In get_level_zero_key: use_key_in_one_step failed")?;
+    // TODO: this is rather unsatisfactory, we need a better way to handle
+    // sensitive binder returns.
+    let level_zero_key = ZVec::try_from(level_zero_key)
+        .context("In get_level_zero_key: conversion to ZVec failed")?;
+    Ok(level_zero_key)
+}
+
+/// Holds the key for the current boot level, and a cache of future keys generated as required.
+/// When the boot level advances, keys prior to the current boot level are securely dropped.
+pub struct BootLevelKeyCache {
+    /// Least boot level currently accessible, if any is.
+    current: usize,
+    /// Invariant: cache entry *i*, if it exists, holds the HKDF key for boot level
+    /// *i* + `current`. If the cache is non-empty it can be grown forwards, but it cannot be
+    /// grown backwards, so keys below `current` are inaccessible.
+    /// `cache.clear()` makes all keys inaccessible.
+    cache: VecDeque<ZVec>,
+}
+
+impl BootLevelKeyCache {
+    const HKDF_ADVANCE: &'static [u8] = b"Advance KDF one step";
+    const HKDF_AES: &'static [u8] = b"Generate AES-256-GCM key";
+    const HKDF_KEY_SIZE: usize = 32;
+
+    /// Initialize the cache with the level zero key.
+    pub fn new(level_zero_key: ZVec) -> Self {
+        let mut cache: VecDeque<ZVec> = VecDeque::new();
+        cache.push_back(level_zero_key);
+        Self { current: 0, cache }
+    }
+
+    /// Report whether the key for the given level can be inferred.
+    pub fn level_accessible(&self, boot_level: usize) -> bool {
+        // If the requested boot level is lower than the current boot level
+        // or if we have reached the end (`cache.empty()`) we can't retrieve
+        // the boot key.
+        boot_level >= self.current && !self.cache.is_empty()
+    }
+
+    /// Get the HKDF key for boot level `boot_level`. The key for level *i*+1
+    /// is calculated from the level *i* key using `hkdf_expand`.
+    fn get_hkdf_key(&mut self, boot_level: usize) -> Result<Option<&ZVec>> {
+        if !self.level_accessible(boot_level) {
+            return Ok(None);
+        }
+        // `self.cache.len()` represents the first entry not in the cache,
+        // so `self.current + self.cache.len()` is the first boot level not in the cache.
+        let first_not_cached = self.current + self.cache.len();
+
+        // Grow the cache forwards until it contains the desired boot level.
+        for _level in first_not_cached..=boot_level {
+            // We check at the start that cache is non-empty and future iterations only push,
+            // so this must unwrap.
+            let highest_key = self.cache.back().unwrap();
+            let next_key = hkdf_expand(Self::HKDF_KEY_SIZE, highest_key, Self::HKDF_ADVANCE)
+                .context("In BootLevelKeyCache::get_hkdf_key: Advancing key one step")?;
+            self.cache.push_back(next_key);
+        }
+
+        // If we reach this point, we should have a key at index boot_level - current.
+        Ok(Some(self.cache.get(boot_level - self.current).unwrap()))
+    }
+
+    /// Drop keys prior to the given boot level, while retaining the ability to generate keys for
+    /// that level and later.
+    pub fn advance_boot_level(&mut self, new_boot_level: usize) -> Result<()> {
+        if !self.level_accessible(new_boot_level) {
+            log::error!(
+                concat!(
+                    "In BootLevelKeyCache::advance_boot_level: ",
+                    "Failed to advance boot level to {}, current is {}, cache size {}"
+                ),
+                new_boot_level,
+                self.current,
+                self.cache.len()
+            );
+            return Ok(());
+        }
+
+        // We `get` the new boot level for the side effect of advancing the cache to a point
+        // where the new boot level is present.
+        self.get_hkdf_key(new_boot_level)
+            .context("In BootLevelKeyCache::advance_boot_level: Advancing cache")?;
+
+        // Then we split the queue at the index of the new boot level and discard the front,
+        // keeping only the keys with the current boot level or higher.
+        self.cache = self.cache.split_off(new_boot_level - self.current);
+
+        // The new cache has the new boot level at index 0, so we set `current` to
+        // `new_boot_level`.
+        self.current = new_boot_level;
+
+        Ok(())
+    }
+
+    /// Drop all keys, effectively raising the current boot level to infinity; no keys can
+    /// be inferred from this point on.
+    pub fn finish(&mut self) {
+        self.cache.clear();
+    }
+
+    fn expand_key(
+        &mut self,
+        boot_level: usize,
+        out_len: usize,
+        info: &[u8],
+    ) -> Result<Option<ZVec>> {
+        let hkdf_key = self
+            .get_hkdf_key(boot_level)
+            .context("In BootLevelKeyCache::expand_key: Looking up HKDF key")?;
+        Ok(hkdf_key
+            .map(|k| hkdf_expand(out_len, k, info))
+            .transpose()
+            .context("In BootLevelKeyCache::expand_key: Calling hkdf_expand")?)
+    }
+
+    /// Return the AES-256-GCM key for the current boot level.
+    pub fn aes_key(&mut self, boot_level: usize) -> Result<Option<ZVec>> {
+        self.expand_key(boot_level, AES_256_KEY_LENGTH, BootLevelKeyCache::HKDF_AES)
+            .context("In BootLevelKeyCache::aes_key: expand_key failed")
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[test]
+    fn test_output_is_consistent() -> Result<()> {
+        let initial_key = b"initial key";
+        let mut blkc = BootLevelKeyCache::new(ZVec::try_from(initial_key as &[u8])?);
+        assert_eq!(true, blkc.level_accessible(0));
+        assert_eq!(true, blkc.level_accessible(9));
+        assert_eq!(true, blkc.level_accessible(10));
+        assert_eq!(true, blkc.level_accessible(100));
+        let v0 = blkc.aes_key(0).unwrap().unwrap();
+        let v10 = blkc.aes_key(10).unwrap().unwrap();
+        assert_eq!(Some(&v0), blkc.aes_key(0)?.as_ref());
+        assert_eq!(Some(&v10), blkc.aes_key(10)?.as_ref());
+        blkc.advance_boot_level(5)?;
+        assert_eq!(false, blkc.level_accessible(0));
+        assert_eq!(true, blkc.level_accessible(9));
+        assert_eq!(true, blkc.level_accessible(10));
+        assert_eq!(true, blkc.level_accessible(100));
+        assert_eq!(None, blkc.aes_key(0)?);
+        assert_eq!(Some(&v10), blkc.aes_key(10)?.as_ref());
+        blkc.advance_boot_level(10)?;
+        assert_eq!(false, blkc.level_accessible(0));
+        assert_eq!(false, blkc.level_accessible(9));
+        assert_eq!(true, blkc.level_accessible(10));
+        assert_eq!(true, blkc.level_accessible(100));
+        assert_eq!(None, blkc.aes_key(0)?);
+        assert_eq!(Some(&v10), blkc.aes_key(10)?.as_ref());
+        blkc.advance_boot_level(0)?;
+        assert_eq!(false, blkc.level_accessible(0));
+        assert_eq!(false, blkc.level_accessible(9));
+        assert_eq!(true, blkc.level_accessible(10));
+        assert_eq!(true, blkc.level_accessible(100));
+        assert_eq!(None, blkc.aes_key(0)?);
+        assert_eq!(Some(v10), blkc.aes_key(10)?);
+        blkc.finish();
+        assert_eq!(false, blkc.level_accessible(0));
+        assert_eq!(false, blkc.level_accessible(9));
+        assert_eq!(false, blkc.level_accessible(10));
+        assert_eq!(false, blkc.level_accessible(100));
+        assert_eq!(None, blkc.aes_key(0)?);
+        assert_eq!(None, blkc.aes_key(10)?);
+        Ok(())
+    }
+}
diff --git a/keystore2/src/database.rs b/keystore2/src/database.rs
index 6a07716a..f673d17c 100644
--- a/keystore2/src/database.rs
+++ b/keystore2/src/database.rs
@@ -186,6 +186,9 @@ impl_metadata!(
         KmUuid(Uuid) with accessor km_uuid,
         /// If the key is ECDH encrypted, this is the ephemeral public key
         PublicKey(Vec<u8>) with accessor public_key,
+        /// If the key is encrypted with a MaxBootLevel key, this is the boot level
+        /// of that key
+        MaxBootLevel(i32) with accessor max_boot_level,
         //  --- ADD NEW META DATA FIELDS HERE ---
         // For backwards compatibility add new entries only to
         // end of this list and above this comment.
diff --git a/keystore2/src/enforcements.rs b/keystore2/src/enforcements.rs
index 3f003be2..8574da08 100644
--- a/keystore2/src/enforcements.rs
+++ b/keystore2/src/enforcements.rs
@@ -14,11 +14,14 @@
 
 //! This is the Keystore 2.0 Enforcements module.
 // TODO: more description to follow.
-use crate::database::{AuthTokenEntry, MonotonicRawTime};
 use crate::error::{map_binder_status, Error, ErrorCode};
 use crate::globals::{get_timestamp_service, ASYNC_TASK, DB, ENFORCEMENTS};
 use crate::key_parameter::{KeyParameter, KeyParameterValue};
 use crate::{authorization::Error as AuthzError, super_key::SuperEncryptionType};
+use crate::{
+    database::{AuthTokenEntry, MonotonicRawTime},
+    globals::SUPER_KEY,
+};
 use android_hardware_security_keymint::aidl::android::hardware::security::keymint::{
     Algorithm::Algorithm, ErrorCode::ErrorCode as Ec, HardwareAuthToken::HardwareAuthToken,
     HardwareAuthenticatorType::HardwareAuthenticatorType,
@@ -34,11 +37,9 @@ use android_system_keystore2::aidl::android::system::keystore2::{
 };
 use android_system_keystore2::binder::Strong;
 use anyhow::{Context, Result};
-use keystore2_system_property::PropertyWatcher;
 use std::{
     collections::{HashMap, HashSet},
     sync::{
-        atomic::{AtomicI32, Ordering},
         mpsc::{channel, Receiver, Sender, TryRecvError},
         Arc, Mutex, Weak,
     },
@@ -369,8 +370,6 @@ pub struct Enforcements {
     /// The enforcement module will try to get a confirmation token from this channel whenever
     /// an operation that requires confirmation finishes.
     confirmation_token_receiver: Arc<Mutex<Option<Receiver<Vec<u8>>>>>,
-    /// Highest boot level seen in keystore.boot_level; used to enforce MAX_BOOT_LEVEL tag.
-    boot_level: AtomicI32,
 }
 
 impl Enforcements {
@@ -596,7 +595,7 @@ impl Enforcements {
         }
 
         if let Some(level) = max_boot_level {
-            if level < self.boot_level.load(Ordering::SeqCst) {
+            if !SUPER_KEY.level_accessible(level) {
                 return Err(Error::Km(Ec::BOOT_LEVEL_EXCEEDED))
                     .context("In authorize_create: boot level is too late.");
             }
@@ -762,27 +761,35 @@ impl Enforcements {
         key_parameters: &[KeyParameter],
         flags: Option<i32>,
     ) -> SuperEncryptionType {
-        if *domain != Domain::APP {
-            return SuperEncryptionType::None;
-        }
         if let Some(flags) = flags {
             if (flags & KEY_FLAG_AUTH_BOUND_WITHOUT_CRYPTOGRAPHIC_LSKF_BINDING) != 0 {
                 return SuperEncryptionType::None;
             }
         }
-        if key_parameters
-            .iter()
-            .any(|kp| matches!(kp.key_parameter_value(), KeyParameterValue::UnlockedDeviceRequired))
-        {
-            return SuperEncryptionType::ScreenLockBound;
-        }
-        if key_parameters
-            .iter()
-            .any(|kp| matches!(kp.key_parameter_value(), KeyParameterValue::UserSecureID(_)))
-        {
-            return SuperEncryptionType::LskfBound;
+        // Each answer has a priority, numerically largest priority wins.
+        struct Candidate {
+            priority: u32,
+            enc_type: SuperEncryptionType,
+        };
+        let mut result = Candidate { priority: 0, enc_type: SuperEncryptionType::None };
+        for kp in key_parameters {
+            let t = match kp.key_parameter_value() {
+                KeyParameterValue::MaxBootLevel(level) => {
+                    Candidate { priority: 3, enc_type: SuperEncryptionType::BootLevel(*level) }
+                }
+                KeyParameterValue::UnlockedDeviceRequired if *domain == Domain::APP => {
+                    Candidate { priority: 2, enc_type: SuperEncryptionType::ScreenLockBound }
+                }
+                KeyParameterValue::UserSecureID(_) if *domain == Domain::APP => {
+                    Candidate { priority: 1, enc_type: SuperEncryptionType::LskfBound }
+                }
+                _ => Candidate { priority: 0, enc_type: SuperEncryptionType::None },
+            };
+            if t.priority > result.priority {
+                result = t;
+            }
         }
-        SuperEncryptionType::None
+        result.enc_type
     }
 
     /// Finds a matching auth token along with a timestamp token.
@@ -844,35 +851,6 @@ impl Enforcements {
             .context("In get_auth_tokens. Error in getting timestamp token.")?;
         Ok((auth_token, tst))
     }
-
-    /// Watch the `keystore.boot_level` system property, and keep self.boot_level up to date.
-    /// Blocks waiting for system property changes, so must be run in its own thread.
-    pub fn watch_boot_level(&self) -> Result<()> {
-        let mut w = PropertyWatcher::new("keystore.boot_level")?;
-        loop {
-            fn parse_value(_name: &str, value: &str) -> Result<Option<i32>> {
-                Ok(if value == "end" { None } else { Some(value.parse::<i32>()?) })
-            }
-            match w.read(parse_value)? {
-                Some(level) => {
-                    let old = self.boot_level.fetch_max(level, Ordering::SeqCst);
-                    log::info!(
-                        "Read keystore.boot_level: {}; boot level {} -> {}",
-                        level,
-                        old,
-                        std::cmp::max(old, level)
-                    );
-                }
-                None => {
-                    log::info!("keystore.boot_level is `end`, finishing.");
-                    self.boot_level.fetch_max(i32::MAX, Ordering::SeqCst);
-                    break;
-                }
-            }
-            w.wait()?;
-        }
-        Ok(())
-    }
 }
 
 // TODO: Add tests to enforcement module (b/175578618).
diff --git a/keystore2/src/keystore2_main.rs b/keystore2/src/keystore2_main.rs
index e745697c..a6bbb2d1 100644
--- a/keystore2/src/keystore2_main.rs
+++ b/keystore2/src/keystore2_main.rs
@@ -68,13 +68,6 @@ fn main() {
 
     ENFORCEMENTS.install_confirmation_token_receiver(confirmation_token_receiver);
 
-    info!("Starting boot level watcher.");
-    std::thread::spawn(|| {
-        keystore2::globals::ENFORCEMENTS
-            .watch_boot_level()
-            .unwrap_or_else(|e| error!("watch_boot_level failed: {}", e));
-    });
-
     entropy::register_feeder();
     shared_secret_negotiation::perform_shared_secret_negotiation();
 
diff --git a/keystore2/src/lib.rs b/keystore2/src/lib.rs
index 62dc16ad..0916af1e 100644
--- a/keystore2/src/lib.rs
+++ b/keystore2/src/lib.rs
@@ -18,6 +18,7 @@
 pub mod apc;
 pub mod async_task;
 pub mod authorization;
+pub mod boot_level_keys;
 pub mod database;
 pub mod ec_crypto;
 pub mod enforcements;
diff --git a/keystore2/src/maintenance.rs b/keystore2/src/maintenance.rs
index e059a0b5..5c1e82dc 100644
--- a/keystore2/src/maintenance.rs
+++ b/keystore2/src/maintenance.rs
@@ -141,6 +141,11 @@ impl Maintenance {
     fn early_boot_ended() -> Result<()> {
         check_keystore_permission(KeystorePerm::early_boot_ended())
             .context("In early_boot_ended. Checking permission")?;
+        log::info!("In early_boot_ended.");
+
+        if let Err(e) = DB.with(|db| SUPER_KEY.set_up_boot_level_cache(&mut db.borrow_mut())) {
+            log::error!("SUPER_KEY.set_up_boot_level_cache failed:\n{:?}\n:(", e);
+        }
 
         let sec_levels = [
             (SecurityLevel::TRUSTED_ENVIRONMENT, "TRUSTED_ENVIRONMENT"),
diff --git a/keystore2/src/security_level.rs b/keystore2/src/security_level.rs
index ec6c4d75..0f9e630c 100644
--- a/keystore2/src/security_level.rs
+++ b/keystore2/src/security_level.rs
@@ -686,7 +686,7 @@ impl KeystoreSecurityLevel {
             SuperKeyManager::reencrypt_if_required(key_blob, &upgraded_blob)
                 .context("In store_upgraded_keyblob: Failed to handle super encryption.")?;
 
-        let mut new_blob_metadata = new_blob_metadata.unwrap_or_else(BlobMetaData::new);
+        let mut new_blob_metadata = new_blob_metadata.unwrap_or_default();
         if let Some(uuid) = km_uuid {
             new_blob_metadata.add(BlobMetaEntry::KmUuid(*uuid));
         }
diff --git a/keystore2/src/super_key.rs b/keystore2/src/super_key.rs
index 3fa4cf02..b78560f7 100644
--- a/keystore2/src/super_key.rs
+++ b/keystore2/src/super_key.rs
@@ -13,6 +13,7 @@
 // limitations under the License.
 
 use crate::{
+    boot_level_keys::{get_level_zero_key, BootLevelKeyCache},
     database::BlobMetaData,
     database::BlobMetaEntry,
     database::EncryptedBy,
@@ -34,6 +35,7 @@ use keystore2_crypto::{
     aes_gcm_decrypt, aes_gcm_encrypt, generate_aes256_key, generate_salt, Password, ZVec,
     AES_256_KEY_LENGTH,
 };
+use keystore2_system_property::PropertyWatcher;
 use std::ops::Deref;
 use std::{
     collections::HashMap,
@@ -41,6 +43,8 @@ use std::{
     sync::{Mutex, Weak},
 };
 
+const MAX_MAX_BOOT_LEVEL: usize = 1_000_000_000;
+
 type UserId = u32;
 
 /// Encryption algorithm used by a particular type of superencryption key
@@ -90,13 +94,47 @@ pub enum SuperEncryptionType {
     LskfBound,
     /// Superencrypt with a key cleared from memory when the device is locked.
     ScreenLockBound,
+    /// Superencrypt with a key based on the desired boot level
+    BootLevel(i32),
+}
+
+#[derive(Debug, Clone, Copy)]
+pub enum SuperKeyIdentifier {
+    /// id of the super key in the database.
+    DatabaseId(i64),
+    /// Boot level of the encrypting boot level key
+    BootLevel(i32),
+}
+
+impl SuperKeyIdentifier {
+    fn from_metadata(metadata: &BlobMetaData) -> Option<Self> {
+        if let Some(EncryptedBy::KeyId(key_id)) = metadata.encrypted_by() {
+            Some(SuperKeyIdentifier::DatabaseId(*key_id))
+        } else if let Some(boot_level) = metadata.max_boot_level() {
+            Some(SuperKeyIdentifier::BootLevel(*boot_level))
+        } else {
+            None
+        }
+    }
+
+    fn add_to_metadata(&self, metadata: &mut BlobMetaData) {
+        match self {
+            SuperKeyIdentifier::DatabaseId(id) => {
+                metadata.add(BlobMetaEntry::EncryptedBy(EncryptedBy::KeyId(*id)));
+            }
+            SuperKeyIdentifier::BootLevel(level) => {
+                metadata.add(BlobMetaEntry::MaxBootLevel(*level));
+            }
+        }
+    }
 }
 
 pub struct SuperKey {
     algorithm: SuperEncryptionAlgorithm,
     key: ZVec,
-    // id of the super key in the database.
-    id: i64,
+    /// Identifier of the encrypting key, used to write an encrypted blob
+    /// back to the database after re-encryption eg on a key update.
+    id: SuperKeyIdentifier,
     /// ECDH is more expensive than AES. So on ECDH private keys we set the
     /// reencrypt_with field to point at the corresponding AES key, and the
     /// keys will be re-encrypted with AES on first use.
@@ -136,11 +174,20 @@ struct UserSuperKeys {
 struct SkmState {
     user_keys: HashMap<UserId, UserSuperKeys>,
     key_index: HashMap<i64, Weak<SuperKey>>,
+    boot_level_key_cache: Option<BootLevelKeyCache>,
 }
 
 impl SkmState {
-    fn add_key_to_key_index(&mut self, super_key: &Arc<SuperKey>) {
-        self.key_index.insert(super_key.id, Arc::downgrade(super_key));
+    fn add_key_to_key_index(&mut self, super_key: &Arc<SuperKey>) -> Result<()> {
+        if let SuperKeyIdentifier::DatabaseId(id) = super_key.id {
+            self.key_index.insert(id, Arc::downgrade(super_key));
+            Ok(())
+        } else {
+            Err(Error::sys()).context(format!(
+                "In add_key_to_key_index: cannot add key with ID {:?}",
+                super_key.id
+            ))
+        }
     }
 }
 
@@ -150,19 +197,101 @@ pub struct SuperKeyManager {
 }
 
 impl SuperKeyManager {
+    pub fn set_up_boot_level_cache(self: &Arc<Self>, db: &mut KeystoreDB) -> Result<()> {
+        let mut data = self.data.lock().unwrap();
+        if data.boot_level_key_cache.is_some() {
+            log::info!("In set_up_boot_level_cache: called for a second time");
+            return Ok(());
+        }
+        let level_zero_key = get_level_zero_key(db)
+            .context("In set_up_boot_level_cache: get_level_zero_key failed")?;
+        data.boot_level_key_cache = Some(BootLevelKeyCache::new(level_zero_key));
+        log::info!("Starting boot level watcher.");
+        let clone = self.clone();
+        std::thread::spawn(move || {
+            clone
+                .watch_boot_level()
+                .unwrap_or_else(|e| log::error!("watch_boot_level failed:\n{:?}", e));
+        });
+        Ok(())
+    }
+
+    /// Watch the `keystore.boot_level` system property, and keep boot level up to date.
+    /// Blocks waiting for system property changes, so must be run in its own thread.
+    fn watch_boot_level(&self) -> Result<()> {
+        let mut w = PropertyWatcher::new("keystore.boot_level")
+            .context("In watch_boot_level: PropertyWatcher::new failed")?;
+        loop {
+            let level = w
+                .read(|_n, v| v.parse::<usize>().map_err(std::convert::Into::into))
+                .context("In watch_boot_level: read of property failed")?;
+            // watch_boot_level should only be called once data.boot_level_key_cache is Some,
+            // so it's safe to unwrap in the branches below.
+            if level < MAX_MAX_BOOT_LEVEL {
+                log::info!("Read keystore.boot_level value {}", level);
+                let mut data = self.data.lock().unwrap();
+                data.boot_level_key_cache
+                    .as_mut()
+                    .unwrap()
+                    .advance_boot_level(level)
+                    .context("In watch_boot_level: advance_boot_level failed")?;
+            } else {
+                log::info!(
+                    "keystore.boot_level {} hits maximum {}, finishing.",
+                    level,
+                    MAX_MAX_BOOT_LEVEL
+                );
+                let mut data = self.data.lock().unwrap();
+                data.boot_level_key_cache.as_mut().unwrap().finish();
+                break;
+            }
+            w.wait().context("In watch_boot_level: property wait failed")?;
+        }
+        Ok(())
+    }
+
+    pub fn level_accessible(&self, boot_level: i32) -> bool {
+        self.data
+            .lock()
+            .unwrap()
+            .boot_level_key_cache
+            .as_ref()
+            .map_or(false, |c| c.level_accessible(boot_level as usize))
+    }
+
     pub fn forget_all_keys_for_user(&self, user: UserId) {
         let mut data = self.data.lock().unwrap();
         data.user_keys.remove(&user);
     }
 
-    fn install_per_boot_key_for_user(&self, user: UserId, super_key: Arc<SuperKey>) {
+    fn install_per_boot_key_for_user(&self, user: UserId, super_key: Arc<SuperKey>) -> Result<()> {
         let mut data = self.data.lock().unwrap();
-        data.add_key_to_key_index(&super_key);
+        data.add_key_to_key_index(&super_key)
+            .context("In install_per_boot_key_for_user: add_key_to_key_index failed")?;
         data.user_keys.entry(user).or_default().per_boot = Some(super_key);
+        Ok(())
     }
 
-    fn lookup_key(&self, key_id: &i64) -> Option<Arc<SuperKey>> {
-        self.data.lock().unwrap().key_index.get(key_id).and_then(|k| k.upgrade())
+    fn lookup_key(&self, key_id: &SuperKeyIdentifier) -> Result<Option<Arc<SuperKey>>> {
+        let mut data = self.data.lock().unwrap();
+        Ok(match key_id {
+            SuperKeyIdentifier::DatabaseId(id) => data.key_index.get(id).and_then(|k| k.upgrade()),
+            SuperKeyIdentifier::BootLevel(level) => data
+                .boot_level_key_cache
+                .as_mut()
+                .map(|b| b.aes_key(*level as usize))
+                .transpose()
+                .context("In lookup_key: aes_key failed")?
+                .flatten()
+                .map(|key| {
+                    Arc::new(SuperKey {
+                        algorithm: SuperEncryptionAlgorithm::Aes256Gcm,
+                        key,
+                        id: *key_id,
+                        reencrypt_with: None,
+                    })
+                }),
+        })
     }
 
     pub fn get_per_boot_key_by_user_id(&self, user_id: UserId) -> Option<Arc<SuperKey>> {
@@ -215,26 +344,27 @@ impl SuperKeyManager {
         Ok(())
     }
 
-    /// Unwraps an encrypted key blob given metadata identifying the encryption key.
-    /// The function queries `metadata.encrypted_by()` to determine the encryption key.
-    /// It then checks if the required key is memory resident, and if so decrypts the
-    /// blob.
-    pub fn unwrap_key<'a>(&self, blob: &'a [u8], metadata: &BlobMetaData) -> Result<KeyBlob<'a>> {
-        let key_id = if let Some(EncryptedBy::KeyId(key_id)) = metadata.encrypted_by() {
-            key_id
+    /// Check if a given key is super-encrypted, from its metadata. If so, unwrap the key using
+    /// the relevant super key.
+    pub fn unwrap_key_if_required<'a>(
+        &self,
+        metadata: &BlobMetaData,
+        blob: &'a [u8],
+    ) -> Result<KeyBlob<'a>> {
+        Ok(if let Some(key_id) = SuperKeyIdentifier::from_metadata(metadata) {
+            let super_key = self
+                .lookup_key(&key_id)
+                .context("In unwrap_key: lookup_key failed")?
+                .ok_or(Error::Rc(ResponseCode::LOCKED))
+                .context("In unwrap_key: Required super decryption key is not in memory.")?;
+            KeyBlob::Sensitive {
+                key: Self::unwrap_key_with_key(blob, metadata, &super_key)
+                    .context("In unwrap_key: unwrap_key_with_key failed")?,
+                reencrypt_with: super_key.reencrypt_with.as_ref().unwrap_or(&super_key).clone(),
+                force_reencrypt: super_key.reencrypt_with.is_some(),
+            }
         } else {
-            return Err(Error::Rc(ResponseCode::VALUE_CORRUPTED))
-                .context("In unwrap_key: Cannot determine wrapping key.");
-        };
-        let super_key = self
-            .lookup_key(&key_id)
-            .ok_or(Error::Rc(ResponseCode::LOCKED))
-            .context("In unwrap_key: Required super decryption key is not in memory.")?;
-        Ok(KeyBlob::Sensitive {
-            key: Self::unwrap_key_with_key(blob, metadata, &super_key)
-                .context("In unwrap_key: unwrap_key_with_key failed")?,
-            reencrypt_with: super_key.reencrypt_with.as_ref().unwrap_or(&super_key).clone(),
-            force_reencrypt: super_key.reencrypt_with.is_some(),
+            KeyBlob::Ref(blob)
         })
     }
 
@@ -389,7 +519,7 @@ impl SuperKeyManager {
             .context(
                 "In populate_cache_from_super_key_blob. Failed to extract super key from key entry",
             )?;
-        self.install_per_boot_key_for_user(user_id, super_key.clone());
+        self.install_per_boot_key_for_user(user_id, super_key.clone())?;
         Ok(super_key)
     }
 
@@ -430,7 +560,12 @@ impl SuperKeyManager {
                     ));
                 }
             };
-            Ok(Arc::new(SuperKey { algorithm, key, id: entry.id(), reencrypt_with }))
+            Ok(Arc::new(SuperKey {
+                algorithm,
+                key,
+                id: SuperKeyIdentifier::DatabaseId(entry.id()),
+                reencrypt_with,
+            }))
         } else {
             Err(Error::Rc(ResponseCode::VALUE_CORRUPTED))
                 .context("In extract_super_key_from_key_entry: No key blob info.")
@@ -498,7 +633,7 @@ impl SuperKeyManager {
             .context("In encrypt_with_aes_super_key: Failed to encrypt new super key.")?;
         metadata.add(BlobMetaEntry::Iv(iv));
         metadata.add(BlobMetaEntry::AeadTag(tag));
-        metadata.add(BlobMetaEntry::EncryptedBy(EncryptedBy::KeyId(super_key.id)));
+        super_key.id.add_to_metadata(&mut metadata);
         Ok((encrypted_key, metadata))
     }
 
@@ -554,27 +689,23 @@ impl SuperKeyManager {
                     metadata.add(BlobMetaEntry::Salt(salt));
                     metadata.add(BlobMetaEntry::Iv(iv));
                     metadata.add(BlobMetaEntry::AeadTag(aead_tag));
-                    metadata.add(BlobMetaEntry::EncryptedBy(EncryptedBy::KeyId(key_id_guard.id())));
+                    SuperKeyIdentifier::DatabaseId(key_id_guard.id())
+                        .add_to_metadata(&mut metadata);
                     Ok((encrypted_key, metadata))
                 }
             }
-        }
-    }
-
-    /// Check if a given key is super-encrypted, from its metadata. If so, unwrap the key using
-    /// the relevant super key.
-    pub fn unwrap_key_if_required<'a>(
-        &self,
-        metadata: &BlobMetaData,
-        key_blob: &'a [u8],
-    ) -> Result<KeyBlob<'a>> {
-        if Self::key_super_encrypted(&metadata) {
-            let unwrapped_key = self
-                .unwrap_key(key_blob, metadata)
-                .context("In unwrap_key_if_required. Error in unwrapping the key.")?;
-            Ok(unwrapped_key)
-        } else {
-            Ok(KeyBlob::Ref(key_blob))
+            SuperEncryptionType::BootLevel(level) => {
+                let key_id = SuperKeyIdentifier::BootLevel(level);
+                let super_key = self
+                    .lookup_key(&key_id)
+                    .context("In handle_super_encryption_on_key_init: lookup_key failed")?
+                    .ok_or(Error::Rc(ResponseCode::LOCKED))
+                    .context("In handle_super_encryption_on_key_init: Boot stage key absent")?;
+                Self::encrypt_with_aes_super_key(key_blob, &super_key).context(concat!(
+                    "In handle_super_encryption_on_key_init: ",
+                    "Failed to encrypt with BootLevel key."
+                ))
+            }
         }
     }
 
@@ -596,14 +727,6 @@ impl SuperKeyManager {
         }
     }
 
-    // Helper function to decide if a key is super encrypted, given metadata.
-    fn key_super_encrypted(metadata: &BlobMetaData) -> bool {
-        if let Some(&EncryptedBy::KeyId(_)) = metadata.encrypted_by() {
-            return true;
-        }
-        false
-    }
-
     /// Fetch a superencryption key from the database, or create it if it doesn't already exist.
     /// When this is called, the caller must hold the lock on the SuperKeyManager.
     /// So it's OK that the check and creation are different DB transactions.
@@ -663,7 +786,7 @@ impl SuperKeyManager {
             Ok(Arc::new(SuperKey {
                 algorithm: key_type.algorithm,
                 key: super_key,
-                id: key_entry.id(),
+                id: SuperKeyIdentifier::DatabaseId(key_entry.id()),
                 reencrypt_with,
             }))
         }
@@ -702,8 +825,8 @@ impl SuperKeyManager {
                 )
             })?
             .clone();
-        data.add_key_to_key_index(&aes);
-        data.add_key_to_key_index(&ecdh);
+        data.add_key_to_key_index(&aes)?;
+        data.add_key_to_key_index(&ecdh)?;
         Ok(())
     }
 
diff --git a/keystore2/src/utils.rs b/keystore2/src/utils.rs
index 7b582053..4a2c6490 100644
--- a/keystore2/src/utils.rs
+++ b/keystore2/src/utils.rs
@@ -217,6 +217,10 @@ pub fn ui_opts_2_compat(opt: i32) -> ApcCompatUiOptions {
 /// AID offset for uid space partitioning.
 pub const AID_USER_OFFSET: u32 = cutils_bindgen::AID_USER_OFFSET;
 
+/// AID of the keystore process itself, used for keys that
+/// keystore generates for its own use.
+pub const AID_KEYSTORE: u32 = cutils_bindgen::AID_KEYSTORE;
+
 /// Extracts the android user from the given uid.
 pub fn uid_to_android_user(uid: u32) -> u32 {
     // Safety: No memory access