diff --git a/keystore2/src/keystore2_main.rs b/keystore2/src/keystore2_main.rs
index 5d99449..1ce3e14 100644
--- a/keystore2/src/keystore2_main.rs
+++ b/keystore2/src/keystore2_main.rs
@@ -14,13 +14,13 @@
 
 //! This crate implements the Keystore 2.0 service entry point.
 
-use keystore2::apc::ApcManager;
 use keystore2::authorization::AuthorizationManager;
 use keystore2::entropy;
 use keystore2::globals::ENFORCEMENTS;
 use keystore2::remote_provisioning::RemoteProvisioningService;
 use keystore2::service::KeystoreService;
 use keystore2::user_manager::Maintenance;
+use keystore2::{apc::ApcManager, shared_secret_negotiation};
 use log::{error, info};
 use std::{panic, path::Path, sync::mpsc::channel};
 use vpnprofilestore::VpnProfileStore;
@@ -76,6 +76,7 @@
     });
 
     entropy::register_feeder();
+    shared_secret_negotiation::perform_shared_secret_negotiation();
 
     info!("Starting thread pool now.");
     binder::ProcessState::start_thread_pool();
diff --git a/keystore2/src/lib.rs b/keystore2/src/lib.rs
index 0e51eff..2a00ae3 100644
--- a/keystore2/src/lib.rs
+++ b/keystore2/src/lib.rs
@@ -32,6 +32,7 @@
 pub mod remote_provisioning;
 pub mod security_level;
 pub mod service;
+pub mod shared_secret_negotiation;
 pub mod user_manager;
 pub mod utils;
 
diff --git a/keystore2/src/shared_secret_negotiation.rs b/keystore2/src/shared_secret_negotiation.rs
new file mode 100644
index 0000000..afce533
--- /dev/null
+++ b/keystore2/src/shared_secret_negotiation.rs
@@ -0,0 +1,263 @@
+// 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.
+
+//! This module implements the shared secret negotiation.
+
+use crate::error::{map_binder_status, map_binder_status_code, Error};
+use android_hardware_security_keymint::aidl::android::hardware::security::keymint::SecurityLevel::SecurityLevel;
+use android_hardware_security_keymint::binder::Strong;
+use android_hardware_security_sharedsecret::aidl::android::hardware::security::sharedsecret::{
+    ISharedSecret::ISharedSecret, SharedSecretParameters::SharedSecretParameters,
+};
+use android_security_compat::aidl::android::security::compat::IKeystoreCompatService::IKeystoreCompatService;
+use anyhow::{Context, Result};
+use keystore2_vintf::{get_aidl_instances, get_hidl_instances};
+use std::fmt::{self, Display, Formatter};
+
+/// This function initiates the shared secret negotiation. It starts a thread and then returns
+/// immediately. The thread consults the vintf manifest to enumerate expected negotiation
+/// participants. It then attempts to connect to all of these participants. If any connection
+/// fails the thread will retry once per second to connect to the failed instance(s) until all of
+/// the instances are connected. It then performs the negotiation.
+///
+/// During the first phase of the negotiation it will again try every second until
+/// all instances have responded successfully to account for instances that register early but
+/// are not fully functioning at this time due to hardware delays or boot order dependency issues.
+/// An error during the second phase or a checksum mismatch leads to a panic.
+pub fn perform_shared_secret_negotiation() {
+    std::thread::spawn(|| {
+        let participants = list_participants()
+            .expect("In perform_shared_secret_negotiation: Trying to list participants.");
+        let connected = connect_participants(participants);
+        negotiate_shared_secret(connected);
+        log::info!("Shared secret negotiation concluded successfully.");
+    });
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
+enum SharedSecretParticipant {
+    /// Represents an instance of android.hardware.security.sharedsecret.ISharedSecret.
+    Aidl(String),
+    /// In the legacy case there can be at most one TEE and one Strongbox hal.
+    Hidl { is_strongbox: bool, version: (usize, usize) },
+}
+
+impl Display for SharedSecretParticipant {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        match self {
+            Self::Aidl(instance) => write!(
+                f,
+                "{}.{}/{}",
+                SHARED_SECRET_PACKAGE_NAME, SHARED_SECRET_INTERFACE_NAME, instance
+            ),
+            Self::Hidl { is_strongbox, version: (ma, mi) } => write!(
+                f,
+                "{}@V{}.{}::{}/{}",
+                KEYMASTER_PACKAGE_NAME,
+                ma,
+                mi,
+                KEYMASTER_INTERFACE_NAME,
+                if *is_strongbox { "strongbox" } else { "default" }
+            ),
+        }
+    }
+}
+
+#[derive(thiserror::Error, Debug)]
+enum SharedSecretError {
+    #[error("Shared parameter retrieval failed on instance {p} with error {e:?}.")]
+    ParameterRetrieval { e: Error, p: SharedSecretParticipant },
+    #[error("Shared secret computation failed on instance {p} with error {e:?}.")]
+    Computation { e: Error, p: SharedSecretParticipant },
+    #[error("Checksum comparison failed on instance {0}.")]
+    Checksum(SharedSecretParticipant),
+}
+
+fn filter_map_legacy_km_instances(
+    name: String,
+    version: (usize, usize),
+) -> Option<SharedSecretParticipant> {
+    match name.as_str() {
+        "default" => Some(SharedSecretParticipant::Hidl { is_strongbox: false, version }),
+        "strongbox" => Some(SharedSecretParticipant::Hidl { is_strongbox: true, version }),
+        _ => {
+            log::warn!("Found unexpected keymaster instance: \"{}\"", name);
+            log::warn!("Device is misconfigured. Allowed instances are:");
+            log::warn!("   * default");
+            log::warn!("   * strongbox");
+            None
+        }
+    }
+}
+
+static KEYMASTER_PACKAGE_NAME: &str = "android.hardware.keymaster";
+static KEYMASTER_INTERFACE_NAME: &str = "IKeymasterDevice";
+static SHARED_SECRET_PACKAGE_NAME: &str = "android.hardware.security.sharedsecret";
+static SHARED_SECRET_INTERFACE_NAME: &str = "ISharedSecret";
+static COMPAT_PACKAGE_NAME: &str = "android.security.compat";
+
+/// Lists participants.
+fn list_participants() -> Result<Vec<SharedSecretParticipant>> {
+    Ok([(4, 0), (4, 1)]
+        .iter()
+        .map(|(ma, mi)| {
+            get_hidl_instances(KEYMASTER_PACKAGE_NAME, *ma, *mi, KEYMASTER_INTERFACE_NAME)
+                .as_vec()
+                .with_context(|| format!("Trying to convert KM{}.{} names to vector.", *ma, *mi))
+                .map(|instances| {
+                    instances
+                        .into_iter()
+                        .filter_map(|name| {
+                            filter_map_legacy_km_instances(name.to_string(), (*ma, *mi))
+                        })
+                        .collect::<Vec<SharedSecretParticipant>>()
+                })
+        })
+        .collect::<Result<Vec<_>>>()
+        .map(|v| v.into_iter().flatten())
+        .and_then(|i| {
+            let participants_aidl: Vec<SharedSecretParticipant> =
+                get_aidl_instances(SHARED_SECRET_PACKAGE_NAME, 1, SHARED_SECRET_INTERFACE_NAME)
+                    .as_vec()
+                    .context("In list_participants: Trying to convert KM1.0 names to vector.")?
+                    .into_iter()
+                    .map(|name| SharedSecretParticipant::Aidl(name.to_string()))
+                    .collect();
+            Ok(i.chain(participants_aidl.into_iter()))
+        })
+        .context("In list_participants.")?
+        .collect())
+}
+
+fn connect_participants(
+    mut participants: Vec<SharedSecretParticipant>,
+) -> Vec<(Strong<dyn ISharedSecret>, SharedSecretParticipant)> {
+    let mut connected_participants: Vec<(Strong<dyn ISharedSecret>, SharedSecretParticipant)> =
+        vec![];
+    loop {
+        let (connected, not_connected) = participants.into_iter().fold(
+            (connected_participants, vec![]),
+            |(mut connected, mut failed), e| {
+                match e {
+                    SharedSecretParticipant::Aidl(instance_name) => {
+                        let service_name =
+                            format!("{}/{}", SHARED_SECRET_PACKAGE_NAME, instance_name);
+                        match map_binder_status_code(binder::get_interface(&service_name)) {
+                            Err(e) => {
+                                log::warn!(
+                                    "Unable to connect \"{}\" with error:\n{:?}\nRetrying later.",
+                                    service_name,
+                                    e
+                                );
+                                failed.push(SharedSecretParticipant::Aidl(instance_name));
+                            }
+                            Ok(service) => connected
+                                .push((service, SharedSecretParticipant::Aidl(instance_name))),
+                        }
+                    }
+                    SharedSecretParticipant::Hidl { is_strongbox, version } => {
+                        // This is a no-op if it was called before.
+                        keystore2_km_compat::add_keymint_device_service();
+
+                        // If we cannot connect to the compatibility service there is no way to
+                        // recover.
+                        // PANIC! - Unless you brought your towel.
+                        let keystore_compat_service: Strong<dyn IKeystoreCompatService> =
+                            map_binder_status_code(binder::get_interface(COMPAT_PACKAGE_NAME))
+                                .expect(
+                                    "In connect_participants: Trying to connect to compat service.",
+                                );
+
+                        match map_binder_status(keystore_compat_service.getSharedSecret(
+                            if is_strongbox {
+                                SecurityLevel::STRONGBOX
+                            } else {
+                                SecurityLevel::TRUSTED_ENVIRONMENT
+                            },
+                        )) {
+                            Err(e) => {
+                                log::warn!(
+                                    concat!(
+                                        "Unable to connect keymaster device \"{}\" ",
+                                        "with error:\n{:?}\nRetrying later."
+                                    ),
+                                    if is_strongbox { "strongbox" } else { "TEE" },
+                                    e
+                                );
+                                failed
+                                    .push(SharedSecretParticipant::Hidl { is_strongbox, version });
+                            }
+                            Ok(service) => connected.push((
+                                service,
+                                SharedSecretParticipant::Hidl { is_strongbox, version },
+                            )),
+                        }
+                    }
+                }
+                (connected, failed)
+            },
+        );
+        participants = not_connected;
+        connected_participants = connected;
+        if participants.is_empty() {
+            break;
+        }
+        std::thread::sleep(std::time::Duration::from_millis(1000));
+    }
+    connected_participants
+}
+
+fn negotiate_shared_secret(
+    participants: Vec<(Strong<dyn ISharedSecret>, SharedSecretParticipant)>,
+) {
+    // Phase 1: Get the sharing parameters from all participants.
+    let mut params = loop {
+        let result: Result<Vec<SharedSecretParameters>, SharedSecretError> = participants
+            .iter()
+            .map(|(s, p)| {
+                map_binder_status(s.getSharedSecretParameters())
+                    .map_err(|e| SharedSecretError::ParameterRetrieval { e, p: (*p).clone() })
+            })
+            .collect();
+
+        match result {
+            Err(e) => {
+                log::warn!("{:?}", e);
+                log::warn!("Retrying in one second.");
+                std::thread::sleep(std::time::Duration::from_millis(1000));
+            }
+            Ok(params) => break params,
+        }
+    };
+
+    params.sort_unstable();
+
+    // Phase 2: Send the sorted sharing parameters to all participants.
+    participants
+        .into_iter()
+        .try_fold(None, |acc, (s, p)| {
+            match (acc, map_binder_status(s.computeSharedSecret(&params))) {
+                (None, Ok(new_sum)) => Ok(Some(new_sum)),
+                (Some(old_sum), Ok(new_sum)) => {
+                    if old_sum == new_sum {
+                        Ok(Some(old_sum))
+                    } else {
+                        Err(SharedSecretError::Checksum(p))
+                    }
+                }
+                (_, Err(e)) => Err(SharedSecretError::Computation { e, p }),
+            }
+        })
+        .expect("Fatal: Shared secret computation failed.");
+}
diff --git a/keystore2/src/vintf/Android.bp b/keystore2/src/vintf/Android.bp
index 77ec57d..feec8ae 100644
--- a/keystore2/src/vintf/Android.bp
+++ b/keystore2/src/vintf/Android.bp
@@ -55,6 +55,7 @@
         "--size_t-is-usize",
         "--whitelist-function", "getHalNames",
         "--whitelist-function", "getHalNamesAndVersions",
+        "--whitelist-function", "getHidlInstances",
         "--whitelist-function", "getAidlInstances",
         "--whitelist-function", "freeNames",
     ],
diff --git a/keystore2/src/vintf/lib.rs b/keystore2/src/vintf/lib.rs
index c3d6d8a..8730a3e 100644
--- a/keystore2/src/vintf/lib.rs
+++ b/keystore2/src/vintf/lib.rs
@@ -14,7 +14,9 @@
 
 //! Bindings for getting the list of HALs.
 
-use keystore2_vintf_bindgen::{freeNames, getAidlInstances, getHalNames, getHalNamesAndVersions};
+use keystore2_vintf_bindgen::{
+    freeNames, getAidlInstances, getHalNames, getHalNamesAndVersions, getHidlInstances,
+};
 use std::ffi::{CStr, CString};
 use std::os::raw::c_char;
 use std::str::Utf8Error;
@@ -65,6 +67,32 @@
 
 /// Gets the instances of the given package, version, and interface tuple.
 /// Note that this is not a zero-cost shim: it will make copies of the strings.
+pub fn get_hidl_instances(
+    package: &str,
+    major_version: usize,
+    minor_version: usize,
+    interface_name: &str,
+) -> HalNames {
+    let mut len: usize = 0;
+    let packages = CString::new(package).expect("Failed to make CString from package.");
+    let interface_name =
+        CString::new(interface_name).expect("Failed to make CString from interface_name.");
+    // Safety: We'll wrap this in HalNames to free the memory it allocates.
+    // It stores the size of the array it returns in len.
+    let raw_strs = unsafe {
+        getHidlInstances(
+            &mut len,
+            packages.as_ptr(),
+            major_version,
+            minor_version,
+            interface_name.as_ptr(),
+        )
+    };
+    HalNames { data: raw_strs, len }
+}
+
+/// Gets the instances of the given package, version, and interface tuple.
+/// Note that this is not a zero-cost shim: it will make copies of the strings.
 pub fn get_aidl_instances(package: &str, version: usize, interface_name: &str) -> HalNames {
     let mut len: usize = 0;
     let packages = CString::new(package).expect("Failed to make CString from package.");
diff --git a/keystore2/src/vintf/vintf.cpp b/keystore2/src/vintf/vintf.cpp
index dbdc046..e407efa 100644
--- a/keystore2/src/vintf/vintf.cpp
+++ b/keystore2/src/vintf/vintf.cpp
@@ -43,6 +43,15 @@
     return convert(names);
 }
 
+char** getHidlInstances(size_t* len, const char* package, size_t major_version,
+                        size_t minor_version, const char* interfaceName) {
+    android::vintf::Version version(major_version, minor_version);
+    auto manifest = android::vintf::VintfObject::GetDeviceHalManifest();
+    const auto names = manifest->getHidlInstances(package, version, interfaceName);
+    *len = names.size();
+    return convert(names);
+}
+
 char** getAidlInstances(size_t* len, const char* package, size_t version,
                         const char* interfaceName) {
     auto manifest = android::vintf::VintfObject::GetDeviceHalManifest();
diff --git a/keystore2/src/vintf/vintf.hpp b/keystore2/src/vintf/vintf.hpp
index 75e80f6..091e8e8 100644
--- a/keystore2/src/vintf/vintf.hpp
+++ b/keystore2/src/vintf/vintf.hpp
@@ -23,6 +23,8 @@
 
 char** getHalNames(size_t* len);
 char** getHalNamesAndVersions(size_t* len);
+char** getHidlInstances(size_t* len, const char* package, size_t major_version,
+                        size_t minor_version, const char* interfaceName);
 char** getAidlInstances(size_t* len, const char* package, size_t version,
                         const char* interfaceName);
 void freeNames(char** names, size_t len);