diff --git a/security/keymint/support/remote_prov_utils.cpp b/security/keymint/support/remote_prov_utils.cpp
index ffcaa95..3cb783c 100644
--- a/security/keymint/support/remote_prov_utils.cpp
+++ b/security/keymint/support/remote_prov_utils.cpp
@@ -855,8 +855,8 @@
         return "Challenge must be a Bstr.";
     }
 
-    if (challenge.size() < 16 || challenge.size() > 64) {
-        return "Challenge size must be between 16 and 64 bytes inclusive. "
+    if (challenge.size() > 64) {
+        return "Challenge size must be between 0 and 64 bytes inclusive. "
                "However, challenge is " +
                std::to_string(challenge.size()) + " bytes long.";
     }
diff --git a/security/rkp/aidl/android/hardware/security/keymint/IRemotelyProvisionedComponent.aidl b/security/rkp/aidl/android/hardware/security/keymint/IRemotelyProvisionedComponent.aidl
index f714f1a..461357d 100644
--- a/security/rkp/aidl/android/hardware/security/keymint/IRemotelyProvisionedComponent.aidl
+++ b/security/rkp/aidl/android/hardware/security/keymint/IRemotelyProvisionedComponent.aidl
@@ -315,7 +315,7 @@
      *
      * @param in challenge contains a byte string from the provisioning server which will be
      *        included in the signed data of the CSR structure. Different provisioned backends may
-     *        use different semantic data for this field, but the supported sizes must be between 16
+     *        use different semantic data for this field, but the supported sizes must be between 0
      *        and 64 bytes, inclusive.
      *
      * @return the following CBOR Certificate Signing Request (Csr) serialized into a byte array:
@@ -344,7 +344,7 @@
      *     UdsCerts,
      *     DiceCertChain,
      *     SignedData<[
-     *         challenge: bstr .size (16..64), ; Provided by the method parameters
+     *         challenge: bstr .size (0..64), ; Provided by the method parameters
      *         bstr .cbor T,
      *     ]>,
      * ]
diff --git a/security/rkp/aidl/vts/functional/VtsRemotelyProvisionedComponentTests.cpp b/security/rkp/aidl/vts/functional/VtsRemotelyProvisionedComponentTests.cpp
index 9f68bfa..94bfbb4 100644
--- a/security/rkp/aidl/vts/functional/VtsRemotelyProvisionedComponentTests.cpp
+++ b/security/rkp/aidl/vts/functional/VtsRemotelyProvisionedComponentTests.cpp
@@ -49,6 +49,9 @@
 constexpr int32_t VERSION_WITH_UNIQUE_ID_SUPPORT = 2;
 constexpr int32_t VERSION_WITHOUT_TEST_MODE = 3;
 
+constexpr uint8_t MIN_CHALLENGE_SIZE = 0;
+constexpr uint8_t MAX_CHALLENGE_SIZE = 64;
+
 #define INSTANTIATE_REM_PROV_AIDL_TEST(name)                                         \
     GTEST_ALLOW_UNINSTANTIATED_PARAMETERIZED_TEST(name);                             \
     INSTANTIATE_TEST_SUITE_P(                                                        \
@@ -693,32 +696,54 @@
 };
 
 /**
- * Generate an empty certificate request, and decrypt and verify the structure and content.
+ * Generate an empty certificate request with all possible length of challenge, and decrypt and
+ * verify the structure and content.
  */
 TEST_P(CertificateRequestV2Test, EmptyRequest) {
     bytevec csr;
 
-    auto status =
-            provisionable_->generateCertificateRequestV2({} /* keysToSign */, challenge_, &csr);
-    ASSERT_TRUE(status.isOk()) << status.getMessage();
+    for (auto size = MIN_CHALLENGE_SIZE; size <= MAX_CHALLENGE_SIZE; size++) {
+        SCOPED_TRACE(testing::Message() << "challenge[" << size << "]");
+        auto challenge = randomBytes(size);
+        auto status =
+                provisionable_->generateCertificateRequestV2({} /* keysToSign */, challenge, &csr);
+        ASSERT_TRUE(status.isOk()) << status.getMessage();
 
-    auto result = verifyProductionCsr(cppbor::Array(), csr, provisionable_.get(), challenge_);
-    ASSERT_TRUE(result) << result.message();
+        auto result = verifyProductionCsr(cppbor::Array(), csr, provisionable_.get(), challenge);
+        ASSERT_TRUE(result) << result.message();
+    }
 }
 
 /**
- * Generate a non-empty certificate request.  Decrypt, parse and validate the contents.
+ * Generate a non-empty certificate request with all possible length of challenge.  Decrypt, parse
+ * and validate the contents.
  */
 TEST_P(CertificateRequestV2Test, NonEmptyRequest) {
     generateKeys(false /* testMode */, 1 /* numKeys */);
 
     bytevec csr;
 
-    auto status = provisionable_->generateCertificateRequestV2(keysToSign_, challenge_, &csr);
-    ASSERT_TRUE(status.isOk()) << status.getMessage();
+    for (auto size = MIN_CHALLENGE_SIZE; size <= MAX_CHALLENGE_SIZE; size++) {
+        SCOPED_TRACE(testing::Message() << "challenge[" << size << "]");
+        auto challenge = randomBytes(size);
+        auto status = provisionable_->generateCertificateRequestV2(keysToSign_, challenge, &csr);
+        ASSERT_TRUE(status.isOk()) << status.getMessage();
 
-    auto result = verifyProductionCsr(cborKeysToSign_, csr, provisionable_.get(), challenge_);
-    ASSERT_TRUE(result) << result.message();
+        auto result = verifyProductionCsr(cborKeysToSign_, csr, provisionable_.get(), challenge);
+        ASSERT_TRUE(result) << result.message();
+    }
+}
+
+/**
+ * Generate an empty certificate request with invalid size of challenge
+ */
+TEST_P(CertificateRequestV2Test, EmptyRequestWithInvalidChallengeFail) {
+    bytevec csr;
+
+    auto status = provisionable_->generateCertificateRequestV2(
+            /* keysToSign */ {}, randomBytes(MAX_CHALLENGE_SIZE + 1), &csr);
+    EXPECT_FALSE(status.isOk()) << status.getMessage();
+    EXPECT_EQ(status.getServiceSpecificError(), BnRemotelyProvisionedComponent::STATUS_FAILED);
 }
 
 /**