diff --git a/keystore2/Android.bp b/keystore2/Android.bp
index 812d5e6..aaa5659 100644
--- a/keystore2/Android.bp
+++ b/keystore2/Android.bp
@@ -42,6 +42,7 @@
         "libkeystore2_crypto_rust",
         "libkeystore2_km_compat",
         "libkeystore2_selinux",
+        "libkeystore2_vintf_rust",
         "liblazy_static",
         "liblibc",
         "liblibsqlite3_sys",
@@ -87,6 +88,7 @@
         "libkeystore2_km_compat",
         "libkeystore2_selinux",
         "libkeystore2_test_utils",
+        "libkeystore2_vintf_rust",
         "liblazy_static",
         "liblibc",
         "liblibsqlite3_sys",
diff --git a/keystore2/keystore2.rc b/keystore2/keystore2.rc
index c5fc72a..2d1f05a 100644
--- a/keystore2/keystore2.rc
+++ b/keystore2/keystore2.rc
@@ -8,13 +8,12 @@
 
 # Start Keystore 2 conditionally
 # TODO b/171563717 Remove when Keystore 2 migration is complete.
-on nonencrypted && property:persist.android.security.keystore2.enable=true
+on property:persist.android.security.keystore2.enable=true
     enable keystore2
 
 service keystore2 /system/bin/keystore2 /data/misc/keystore
-    class main
+    class early_hal
     user keystore
     group keystore readproc log
     writepid /dev/cpuset/foreground/tasks
-    # TODO b/171563717 Remove when Keystore 2 migration is complete.
     disabled
diff --git a/keystore2/src/globals.rs b/keystore2/src/globals.rs
index 9668ee3..e1b41b5 100644
--- a/keystore2/src/globals.rs
+++ b/keystore2/src/globals.rs
@@ -35,6 +35,7 @@
 use android_hardware_security_keymint::binder::{StatusCode, Strong};
 use android_security_compat::aidl::android::security::compat::IKeystoreCompatService::IKeystoreCompatService;
 use anyhow::{Context, Result};
+use keystore2_vintf::get_aidl_instances;
 use lazy_static::lazy_static;
 use std::sync::{Arc, Mutex};
 use std::{cell::RefCell, sync::Once};
@@ -175,38 +176,49 @@
 /// If no native KeyMint device can be found this function also brings
 /// up the compatibility service and attempts to connect to the legacy wrapper.
 fn connect_keymint(security_level: &SecurityLevel) -> Result<(Asp, KeyMintHardwareInfo)> {
+    let keymint_instances =
+        get_aidl_instances("android.hardware.security.keymint", 1, "IKeyMintDevice");
+
     let service_name = match *security_level {
-        SecurityLevel::TRUSTED_ENVIRONMENT => format!("{}/default", KEYMINT_SERVICE_NAME),
-        SecurityLevel::STRONGBOX => format!("{}/strongbox", KEYMINT_SERVICE_NAME),
+        SecurityLevel::TRUSTED_ENVIRONMENT => {
+            if keymint_instances.as_vec()?.iter().any(|instance| *instance == "default") {
+                Some(format!("{}/default", KEYMINT_SERVICE_NAME))
+            } else {
+                None
+            }
+        }
+        SecurityLevel::STRONGBOX => {
+            if keymint_instances.as_vec()?.iter().any(|instance| *instance == "strongbox") {
+                Some(format!("{}/strongbox", KEYMINT_SERVICE_NAME))
+            } else {
+                None
+            }
+        }
         _ => {
             return Err(Error::Km(ErrorCode::HARDWARE_TYPE_UNAVAILABLE))
                 .context("In connect_keymint.")
         }
     };
 
-    let keymint = map_binder_status_code(binder::get_interface(&service_name))
-        .context("In connect_keymint: Trying to connect to genuine KeyMint service.")
-        .or_else(|e| {
-            match e.root_cause().downcast_ref::<Error>() {
-                Some(Error::BinderTransaction(StatusCode::NAME_NOT_FOUND)) => {
-                    // This is a no-op if it was called before.
-                    keystore2_km_compat::add_keymint_device_service();
+    let keymint = if let Some(service_name) = service_name {
+        map_binder_status_code(binder::get_interface(&service_name))
+            .context("In connect_keymint: Trying to connect to genuine KeyMint service.")
+    } else {
+        // This is a no-op if it was called before.
+        keystore2_km_compat::add_keymint_device_service();
 
-                    let keystore_compat_service: Strong<dyn IKeystoreCompatService> =
-                        map_binder_status_code(binder::get_interface("android.security.compat"))
-                            .context("In connect_keymint: Trying to connect to compat service.")?;
-                    map_binder_status(keystore_compat_service.getKeyMintDevice(*security_level))
-                        .map_err(|e| match e {
-                            Error::BinderTransaction(StatusCode::NAME_NOT_FOUND) => {
-                                Error::Km(ErrorCode::HARDWARE_TYPE_UNAVAILABLE)
-                            }
-                            e => e,
-                        })
-                        .context("In connect_keymint: Trying to get Legacy wrapper.")
+        let keystore_compat_service: Strong<dyn IKeystoreCompatService> =
+            map_binder_status_code(binder::get_interface("android.security.compat"))
+                .context("In connect_keymint: Trying to connect to compat service.")?;
+        map_binder_status(keystore_compat_service.getKeyMintDevice(*security_level))
+            .map_err(|e| match e {
+                Error::BinderTransaction(StatusCode::NAME_NOT_FOUND) => {
+                    Error::Km(ErrorCode::HARDWARE_TYPE_UNAVAILABLE)
                 }
-                _ => Err(e),
-            }
-        })?;
+                e => e,
+            })
+            .context("In connect_keymint: Trying to get Legacy wrapper.")
+    }?;
 
     let hw_info = map_km_error(keymint.getHardwareInfo())
         .context("In connect_keymint: Failed to get hardware info.")?;
@@ -250,33 +262,33 @@
 /// If no native SecureClock device can be found brings up the compatibility service and attempts
 /// to connect to the legacy wrapper.
 fn connect_secureclock() -> Result<Asp> {
-    let secureclock = map_binder_status_code(binder::get_interface(TIME_STAMP_SERVICE_NAME))
-        .context("In connect_secureclock: Trying to connect to genuine secure clock service.")
-        .or_else(|e| {
-            match e.root_cause().downcast_ref::<Error>() {
-                Some(Error::BinderTransaction(StatusCode::NAME_NOT_FOUND)) => {
-                    // This is a no-op if it was called before.
-                    keystore2_km_compat::add_keymint_device_service();
+    let secureclock_instances =
+        get_aidl_instances("android.hardware.security.secureclock", 1, "ISecureClock");
 
-                    let keystore_compat_service: Strong<dyn IKeystoreCompatService> =
-                        map_binder_status_code(binder::get_interface("android.security.compat"))
-                            .context(
-                                "In connect_secureclock: Trying to connect to compat service.",
-                            )?;
+    let secure_clock_available =
+        secureclock_instances.as_vec()?.iter().any(|instance| *instance == "default");
 
-                    // Legacy secure clock services were only implemented by TEE.
-                    map_binder_status(keystore_compat_service.getSecureClock())
-                        .map_err(|e| match e {
-                            Error::BinderTransaction(StatusCode::NAME_NOT_FOUND) => {
-                                Error::Km(ErrorCode::HARDWARE_TYPE_UNAVAILABLE)
-                            }
-                            e => e,
-                        })
-                        .context("In connect_secureclock: Trying to get Legacy wrapper.")
+    let secureclock = if secure_clock_available {
+        map_binder_status_code(binder::get_interface(TIME_STAMP_SERVICE_NAME))
+            .context("In connect_secureclock: Trying to connect to genuine secure clock service.")
+    } else {
+        // This is a no-op if it was called before.
+        keystore2_km_compat::add_keymint_device_service();
+
+        let keystore_compat_service: Strong<dyn IKeystoreCompatService> =
+            map_binder_status_code(binder::get_interface("android.security.compat"))
+                .context("In connect_secureclock: Trying to connect to compat service.")?;
+
+        // Legacy secure clock services were only implemented by TEE.
+        map_binder_status(keystore_compat_service.getSecureClock())
+            .map_err(|e| match e {
+                Error::BinderTransaction(StatusCode::NAME_NOT_FOUND) => {
+                    Error::Km(ErrorCode::HARDWARE_TYPE_UNAVAILABLE)
                 }
-                _ => Err(e),
-            }
-        })?;
+                e => e,
+            })
+            .context("In connect_secureclock: Trying to get Legacy wrapper.")
+    }?;
 
     Ok(Asp::new(secureclock.as_binder()))
 }
@@ -298,18 +310,28 @@
     "android.hardware.security.keymint.IRemotelyProvisionedComponent";
 
 fn connect_remotely_provisioned_component(security_level: &SecurityLevel) -> Result<Asp> {
+    let remotely_prov_instances =
+        get_aidl_instances("android.hardware.security.keymint", 1, "IRemotelyProvisionedComponent");
+
     let service_name = match *security_level {
         SecurityLevel::TRUSTED_ENVIRONMENT => {
-            format!("{}/default", REMOTE_PROVISIONING_HAL_SERVICE_NAME)
+            if remotely_prov_instances.as_vec()?.iter().any(|instance| *instance == "default") {
+                Some(format!("{}/default", REMOTE_PROVISIONING_HAL_SERVICE_NAME))
+            } else {
+                None
+            }
         }
-        SecurityLevel::STRONGBOX => format!("{}/strongbox", REMOTE_PROVISIONING_HAL_SERVICE_NAME),
-        _ => {
-            // Given the integration of IRemotelyProvisionedComponent with KeyMint, it is reasonable
-            // to return HARDWARE_TYPE_UNAVAILABLE as a Km error if it cannot be found.
-            return Err(Error::Km(ErrorCode::HARDWARE_TYPE_UNAVAILABLE))
-                .context("In connect_remotely_provisioned_component.");
+        SecurityLevel::STRONGBOX => {
+            if remotely_prov_instances.as_vec()?.iter().any(|instance| *instance == "strongbox") {
+                Some(format!("{}/strongbox", REMOTE_PROVISIONING_HAL_SERVICE_NAME))
+            } else {
+                None
+            }
         }
-    };
+        _ => None,
+    }
+    .ok_or(Error::Km(ErrorCode::HARDWARE_TYPE_UNAVAILABLE))
+    .context("In connect_remotely_provisioned_component.")?;
 
     let rem_prov_hal: Strong<dyn IRemotelyProvisionedComponent> =
         map_binder_status_code(binder::get_interface(&service_name))
diff --git a/keystore2/src/vintf/Android.bp b/keystore2/src/vintf/Android.bp
new file mode 100644
index 0000000..da7935a
--- /dev/null
+++ b/keystore2/src/vintf/Android.bp
@@ -0,0 +1,70 @@
+// 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.
+
+rust_library {
+    name: "libkeystore2_vintf_rust",
+    crate_name: "keystore2_vintf",
+    srcs: ["lib.rs"],
+    rustlibs: [
+        "libkeystore2_vintf_bindgen",
+    ],
+    shared_libs: [
+        "libkeystore2_vintf_cpp",
+        "libvintf",
+    ],
+}
+
+cc_library {
+    name: "libkeystore2_vintf_cpp",
+    srcs: [
+        "vintf.cpp",
+    ],
+    shared_libs: [
+        "libvintf",
+    ],
+}
+
+rust_bindgen {
+    name: "libkeystore2_vintf_bindgen",
+    wrapper_src: "vintf.hpp",
+    crate_name: "keystore2_vintf_bindgen",
+    source_stem: "bindings",
+    host_supported: true,
+    shared_libs: ["libvintf"],
+    bindgen_flags: [
+        "--size_t-is-usize",
+        "--whitelist-function", "getHalNames",
+        "--whitelist-function", "getHalNamesAndVersions",
+        "--whitelist-function", "getAidlInstances",
+        "--whitelist-function", "freeNames",
+    ],
+}
+
+rust_test {
+    name: "keystore2_vintf_test",
+    crate_name: "keystore2_vintf_test",
+    srcs: ["lib.rs"],
+    test_suites: ["general-tests"],
+    auto_gen_config: true,
+    rustlibs: [
+        "libkeystore2_vintf_bindgen",
+    ],
+    static_libs: [
+        "libkeystore2_vintf_cpp",
+    ],
+    shared_libs: [
+        "libc++",
+        "libvintf",
+    ],
+}
diff --git a/keystore2/src/vintf/lib.rs b/keystore2/src/vintf/lib.rs
new file mode 100644
index 0000000..c3d6d8a
--- /dev/null
+++ b/keystore2/src/vintf/lib.rs
@@ -0,0 +1,99 @@
+// 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.
+
+//! Bindings for getting the list of HALs.
+
+use keystore2_vintf_bindgen::{freeNames, getAidlInstances, getHalNames, getHalNamesAndVersions};
+use std::ffi::{CStr, CString};
+use std::os::raw::c_char;
+use std::str::Utf8Error;
+
+/// A struct that contains a list of HALs (optionally with version numbers).
+/// To use it, call as_vec to get a Vec view of the data it contains.
+pub struct HalNames {
+    data: *mut *mut c_char,
+    len: usize,
+}
+
+impl Drop for HalNames {
+    fn drop(&mut self) {
+        // Safety: The memory is allocated by our C shim so it must free it as well.
+        unsafe { freeNames(self.data, self.len) }
+    }
+}
+
+impl<'a> HalNames {
+    /// Get a Vec view of the list of HALs.
+    pub fn as_vec(&'a self) -> Result<Vec<&'a str>, Utf8Error> {
+        // Safety: self.data contains self.len C strings.
+        // The lifetimes ensure that the HalNames (and hence the strings) live
+        // at least as long as the returned vector.
+        unsafe { (0..self.len).map(|i| CStr::from_ptr(*self.data.add(i)).to_str()) }.collect()
+    }
+}
+
+/// Gets all HAL names.
+/// Note that this is not a zero-cost shim: it will make copies of the strings.
+pub fn get_hal_names() -> HalNames {
+    let mut len: usize = 0;
+    // 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 { getHalNames(&mut len) };
+    HalNames { data: raw_strs, len }
+}
+
+/// Gets all HAL names and versions.
+/// Note that this is not a zero-cost shim: it will make copies of the strings.
+pub fn get_hal_names_and_versions() -> HalNames {
+    let mut len: usize = 0;
+    // 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 { getHalNamesAndVersions(&mut len) };
+    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.");
+    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 { getAidlInstances(&mut len, packages.as_ptr(), version, interface_name.as_ptr()) };
+    HalNames { data: raw_strs, len }
+}
+
+#[cfg(test)]
+mod tests {
+
+    use super::*;
+
+    #[test]
+    fn test() -> Result<(), Utf8Error> {
+        let result = get_hal_names();
+        let names = result.as_vec()?;
+        assert_ne!(names.len(), 0);
+
+        let result = get_hal_names_and_versions();
+        let names_and_versions = result.as_vec()?;
+        assert_ne!(names_and_versions.len(), 0);
+
+        assert!(names_and_versions.len() >= names.len());
+
+        Ok(())
+    }
+}
diff --git a/keystore2/src/vintf/vintf.cpp b/keystore2/src/vintf/vintf.cpp
new file mode 100644
index 0000000..dbdc046
--- /dev/null
+++ b/keystore2/src/vintf/vintf.cpp
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 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.
+ */
+
+#include "vintf.hpp"
+
+#include <vintf/HalManifest.h>
+#include <vintf/VintfObject.h>
+
+// Converts a set<string> into a C-style array of C strings.
+static char** convert(const std::set<std::string>& names) {
+    char** ret = new char*[names.size()];
+    char** ptr = ret;
+    for (const auto& name : names) {
+        *(ptr++) = strdup(name.c_str());
+    }
+    return ret;
+}
+
+char** getHalNames(size_t* len) {
+    auto manifest = android::vintf::VintfObject::GetDeviceHalManifest();
+    const auto names = manifest->getHalNames();
+    *len = names.size();
+    return convert(names);
+}
+
+char** getHalNamesAndVersions(size_t* len) {
+    auto manifest = android::vintf::VintfObject::GetDeviceHalManifest();
+    const auto names = manifest->getHalNamesAndVersions();
+    *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();
+    const auto names = manifest->getAidlInstances(package, version, interfaceName);
+    *len = names.size();
+    return convert(names);
+}
+
+void freeNames(char** names, size_t len) {
+    for (int i = 0; i < len; i++) {
+        free(names[i]);
+    }
+    delete[] names;
+}
diff --git a/keystore2/src/vintf/vintf.hpp b/keystore2/src/vintf/vintf.hpp
new file mode 100644
index 0000000..75e80f6
--- /dev/null
+++ b/keystore2/src/vintf/vintf.hpp
@@ -0,0 +1,31 @@
+/*
+ * Copyright (C) 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.
+ */
+
+#ifndef __VINTF_H__
+#define __VINTF_H__
+
+#include <stddef.h>
+
+extern "C" {
+
+char** getHalNames(size_t* len);
+char** getHalNamesAndVersions(size_t* len);
+char** getAidlInstances(size_t* len, const char* package, size_t version,
+                        const char* interfaceName);
+void freeNames(char** names, size_t len);
+}
+
+#endif  //  __VINTF_H__