diff --git a/Keystore.cpp b/Keystore.cpp
index 0995d05..a017d68 100644
--- a/Keystore.cpp
+++ b/Keystore.cpp
@@ -230,5 +230,18 @@
     logKeystore2ExceptionIfPresent(rc, "earlyBootEnded");
 }
 
+void Keystore::deleteAllKeys() {
+    ::ndk::SpAIBinder binder(AServiceManager_getService(maintenance_service_name));
+    auto maint_service = ks2_maint::IKeystoreMaintenance::fromBinder(binder);
+
+    if (!maint_service) {
+        LOG(ERROR) << "Unable to connect to keystore2 maintenance service for deleteAllKeys";
+        return;
+    }
+
+    auto rc = maint_service->deleteAllKeys();
+    logKeystore2ExceptionIfPresent(rc, "deleteAllKeys");
+}
+
 }  // namespace vold
 }  // namespace android
diff --git a/Keystore.h b/Keystore.h
index 05a8370..d8c488e 100644
--- a/Keystore.h
+++ b/Keystore.h
@@ -126,6 +126,9 @@
     // be created or used.
     static void earlyBootEnded();
 
+    // Tell all Keymint devices to delete all rollback-protected keys.
+    static void deleteAllKeys();
+
   private:
     std::shared_ptr<ks2::IKeystoreSecurityLevel> securityLevel;
     DISALLOW_COPY_AND_ASSIGN(Keystore);
diff --git a/MetadataCrypt.cpp b/MetadataCrypt.cpp
index 5fe7918..277a908 100644
--- a/MetadataCrypt.cpp
+++ b/MetadataCrypt.cpp
@@ -113,6 +113,17 @@
     auto dir = metadata_key_dir + "/key";
     LOG(DEBUG) << "metadata_key_dir/key: " << dir;
     if (!MkdirsSync(dir, 0700)) return false;
+    if (!pathExists(dir)) {
+        auto delete_all = android::base::GetBoolProperty(
+                "ro.crypto.metadata_init_delete_all_keys.enabled", false);
+        if (delete_all) {
+            LOG(INFO) << "Metadata key does not exist, calling deleteAllKeys";
+            Keystore::deleteAllKeys();
+        } else {
+            LOG(DEBUG) << "Metadata key does not exist but "
+                          "ro.crypto.metadata_init_delete_all_keys.enabled is false";
+        }
+    }
     auto temp = metadata_key_dir + "/tmp";
     return retrieveOrGenerateKey(dir, temp, kEmptyAuthentication, gen, key);
 }