diff --git a/Keymaster.cpp b/Keymaster.cpp
index 8038681..2314550 100644
--- a/Keymaster.cpp
+++ b/Keymaster.cpp
@@ -230,5 +230,18 @@
     logKeystore2ExceptionIfPresent(rc, "earlyBootEnded");
 }
 
+void Keymaster::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/Keymaster.h b/Keymaster.h
index 1100840..47bf4a2 100644
--- a/Keymaster.h
+++ b/Keymaster.h
@@ -127,6 +127,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(Keymaster);
diff --git a/MetadataCrypt.cpp b/MetadataCrypt.cpp
index dc50679..9038e8d 100644
--- a/MetadataCrypt.cpp
+++ b/MetadataCrypt.cpp
@@ -112,6 +112,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";
+            Keymaster::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);
 }