diff --git a/delta_performer.cc b/delta_performer.cc
index 2d4517f..0071834 100644
--- a/delta_performer.cc
+++ b/delta_performer.cc
@@ -1226,29 +1226,22 @@
   }
   TEST_AND_RETURN_VAL(ErrorCode::kSignedDeltaPayloadExpectedError,
                       !signatures_message_data_.empty());
-  chromeos::Blob signed_hash_data;
-  TEST_AND_RETURN_VAL(ErrorCode::kDownloadPayloadPubKeyVerificationError,
-                      PayloadVerifier::VerifySignature(
-                          signatures_message_data_,
-                          path_to_public_key.value(),
-                          &signed_hash_data));
   OmahaHashCalculator signed_hasher;
   TEST_AND_RETURN_VAL(ErrorCode::kDownloadPayloadPubKeyVerificationError,
                       signed_hasher.SetContext(signed_hash_context_));
   TEST_AND_RETURN_VAL(ErrorCode::kDownloadPayloadPubKeyVerificationError,
                       signed_hasher.Finalize());
   chromeos::Blob hash_data = signed_hasher.raw_hash();
-  PayloadVerifier::PadRSA2048SHA256Hash(&hash_data);
+  TEST_AND_RETURN_VAL(ErrorCode::kDownloadPayloadPubKeyVerificationError,
+                      PayloadVerifier::PadRSA2048SHA256Hash(&hash_data));
   TEST_AND_RETURN_VAL(ErrorCode::kDownloadPayloadPubKeyVerificationError,
                       !hash_data.empty());
-  if (hash_data != signed_hash_data) {
+
+  if (!PayloadVerifier::VerifySignature(
+      signatures_message_data_, path_to_public_key.value(), hash_data)) {
     // The autoupdate_CatchBadSignatures test checks for this string
     // in log-files. Keep in sync.
-    LOG(ERROR) << "Public key verification failed, thus update failed. "
-        "Attached Signature:";
-    utils::HexDumpVector(signed_hash_data);
-    LOG(ERROR) << "Computed Signature:";
-    utils::HexDumpVector(hash_data);
+    LOG(ERROR) << "Public key verification failed, thus update failed.";
     return ErrorCode::kDownloadPayloadPubKeyVerificationError;
   }
 
diff --git a/delta_performer_integration_test.cc b/delta_performer_integration_test.cc
index 1e3dea8..eddce9c 100644
--- a/delta_performer_integration_test.cc
+++ b/delta_performer_integration_test.cc
@@ -193,8 +193,7 @@
       out_metadata_size));
   EXPECT_TRUE(PayloadVerifier::VerifySignedPayload(
       payload_path,
-      kUnittestPublicKeyPath,
-      kSignatureMessageOriginalVersion));
+      kUnittestPublicKeyPath));
 }
 
 static void SignGeneratedShellPayload(SignatureTest signature_test,
diff --git a/payload_generator/generate_delta_main.cc b/payload_generator/generate_delta_main.cc
index d38c5c5..a600c9c 100644
--- a/payload_generator/generate_delta_main.cc
+++ b/payload_generator/generate_delta_main.cc
@@ -171,15 +171,13 @@
 }
 
 void VerifySignedPayload(const string& in_file,
-                         const string& public_key,
-                         int public_key_version) {
+                         const string& public_key) {
   LOG(INFO) << "Verifying signed payload.";
   LOG_IF(FATAL, in_file.empty())
       << "Must pass --in_file to verify signed payload.";
   LOG_IF(FATAL, public_key.empty())
       << "Must pass --public_key to verify signed payload.";
-  CHECK(PayloadVerifier::VerifySignedPayload(in_file, public_key,
-                                             public_key_version));
+  CHECK(PayloadVerifier::VerifySignedPayload(in_file, public_key));
   LOG(INFO) << "Done verifying signed payload.";
 }
 
@@ -241,9 +239,8 @@
                 "Path to output metadata hash file");
   DEFINE_string(private_key, "", "Path to private key in .pem format");
   DEFINE_string(public_key, "", "Path to public key in .pem format");
-  DEFINE_int32(public_key_version,
-               chromeos_update_engine::kSignatureMessageCurrentVersion,
-               "Key-check version # of client");
+  DEFINE_int32(public_key_version, -1,
+               "DEPRECATED. Key-check version # of client");
   DEFINE_string(prefs_dir, "/tmp/update_engine_prefs",
                 "Preferences directory, used with apply_delta");
   DEFINE_string(signature_size, "",
@@ -344,8 +341,9 @@
     return 0;
   }
   if (!FLAGS_public_key.empty()) {
-    VerifySignedPayload(FLAGS_in_file, FLAGS_public_key,
-                        FLAGS_public_key_version);
+    LOG_IF(WARNING, FLAGS_public_key_version != -1)
+        << "--public_key_version is deprecated and ignored.";
+    VerifySignedPayload(FLAGS_in_file, FLAGS_public_key);
     return 0;
   }
   if (!FLAGS_in_file.empty()) {
diff --git a/payload_generator/payload_signer.cc b/payload_generator/payload_signer.cc
index 218b432..4a2bb95 100644
--- a/payload_generator/payload_signer.cc
+++ b/payload_generator/payload_signer.cc
@@ -38,22 +38,21 @@
 
 namespace {
 
+// The payload verifier will check all the signatures included in the payload
+// regardless of the version field. Old version of the verifier require the
+// version field to be included and be 1.
+const uint32_t kSignatureMessageLegacyVersion = 1;
+
 // Given raw |signatures|, packs them into a protobuf and serializes it into a
 // binary blob. Returns true on success, false otherwise.
 bool ConvertSignatureToProtobufBlob(const vector<chromeos::Blob>& signatures,
                                     chromeos::Blob* out_signature_blob) {
   // Pack it into a protobuf
   Signatures out_message;
-  uint32_t version = kSignatureMessageOriginalVersion;
-  LOG_IF(WARNING, kSignatureMessageCurrentVersion -
-         kSignatureMessageOriginalVersion + 1 < signatures.size())
-      << "You may want to support clients in the range ["
-      << kSignatureMessageOriginalVersion << ", "
-      << kSignatureMessageCurrentVersion << "] inclusive, but you only "
-      << "provided " << signatures.size() << " signatures.";
   for (const chromeos::Blob& signature : signatures) {
     Signatures_Signature* sig_message = out_message.add_signatures();
-    sig_message->set_version(version++);
+    // Set all the signatures with the same version number.
+    sig_message->set_version(kSignatureMessageLegacyVersion);
     sig_message->set_data(signature.data(), signature.size());
   }
 
@@ -156,16 +155,10 @@
                                          padded_hash.data(),
                                          padded_hash.size()));
 
-  // This runs on the server, so it's okay to cop out and call openssl
-  // executable rather than properly use the library
-  vector<string> cmd;
-  base::SplitString("openssl rsautl -raw -sign -inkey x -in x -out x",
-                    ' ',
-                    &cmd);
-  cmd[cmd.size() - 5] = private_key_path;
-  cmd[cmd.size() - 3] = hash_path;
-  cmd[cmd.size() - 1] = sig_path;
-
+  // This runs on the server, so it's okay to copy out and call openssl
+  // executable rather than properly use the library.
+  vector<string> cmd = {"openssl", "rsautl", "-raw", "-sign", "-inkey",
+                        private_key_path, "-in", hash_path, "-out", sig_path};
   int return_code = 0;
   TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &return_code,
                                                     nullptr));
diff --git a/payload_generator/payload_signer_unittest.cc b/payload_generator/payload_signer_unittest.cc
index 1cd45ce..cedb432 100644
--- a/payload_generator/payload_signer_unittest.cc
+++ b/payload_generator/payload_signer_unittest.cc
@@ -94,30 +94,37 @@
 };
 
 namespace {
-void SignSampleData(chromeos::Blob* out_signature_blob) {
+void SignSampleData(chromeos::Blob* out_signature_blob,
+                    const vector<string>& private_keys) {
   string data_path;
-  ASSERT_TRUE(
-      utils::MakeTempFile("data.XXXXXX", &data_path, nullptr));
+  ASSERT_TRUE(utils::MakeTempFile("data.XXXXXX", &data_path, nullptr));
   ScopedPathUnlinker data_path_unlinker(data_path);
   ASSERT_TRUE(utils::WriteFile(data_path.c_str(),
                                kDataToSign,
                                strlen(kDataToSign)));
   uint64_t length = 0;
-  EXPECT_TRUE(PayloadSigner::SignatureBlobLength(
-      vector<string> (1, kUnittestPrivateKeyPath),
-      &length));
+  EXPECT_TRUE(PayloadSigner::SignatureBlobLength(private_keys, &length));
   EXPECT_GT(length, 0);
   EXPECT_TRUE(PayloadSigner::SignPayload(
       data_path,
-      vector<string>(1, kUnittestPrivateKeyPath),
+      private_keys,
       out_signature_blob));
   EXPECT_EQ(length, out_signature_blob->size());
 }
 }  // namespace
 
-TEST(PayloadSignerTest, SimpleTest) {
+class PayloadSignerTest : public ::testing::Test {
+ protected:
+  void SetUp() override {
+    PayloadVerifier::PadRSA2048SHA256Hash(&padded_hash_data_);
+  }
+
+  chromeos::Blob padded_hash_data_{std::begin(kDataHash), std::end(kDataHash)};
+};
+
+TEST_F(PayloadSignerTest, SignSimpleTextTest) {
   chromeos::Blob signature_blob;
-  SignSampleData(&signature_blob);
+  SignSampleData(&signature_blob, {kUnittestPrivateKeyPath});
 
   // Check the signature itself
   Signatures signatures;
@@ -125,7 +132,7 @@
                                         signature_blob.size()));
   EXPECT_EQ(1, signatures.signatures_size());
   const Signatures_Signature& signature = signatures.signatures(0);
-  EXPECT_EQ(kSignatureMessageOriginalVersion, signature.version());
+  EXPECT_EQ(1, signature.version());
   const string sig_data = signature.data();
   ASSERT_EQ(arraysize(kDataSignature), sig_data.size());
   for (size_t i = 0; i < arraysize(kDataSignature); i++) {
@@ -133,20 +140,31 @@
   }
 }
 
-TEST(PayloadSignerTest, VerifySignatureTest) {
+TEST_F(PayloadSignerTest, VerifyAllSignatureTest) {
   chromeos::Blob signature_blob;
-  SignSampleData(&signature_blob);
+  SignSampleData(&signature_blob,
+                 {kUnittestPrivateKeyPath, kUnittestPrivateKey2Path});
 
-  chromeos::Blob hash_data;
+  // Either public key should pass the verification.
   EXPECT_TRUE(PayloadVerifier::VerifySignature(signature_blob,
-                                             kUnittestPublicKeyPath,
-                                             &hash_data));
-  chromeos::Blob padded_hash_data(std::begin(kDataHash), std::end(kDataHash));
-  PayloadVerifier::PadRSA2048SHA256Hash(&padded_hash_data);
-  ASSERT_EQ(padded_hash_data.size(), hash_data.size());
-  for (size_t i = 0; i < padded_hash_data.size(); i++) {
-    EXPECT_EQ(padded_hash_data[i], hash_data[i]);
-  }
+                                               kUnittestPublicKeyPath,
+                                               padded_hash_data_));
+  EXPECT_TRUE(PayloadVerifier::VerifySignature(signature_blob,
+                                               kUnittestPublicKey2Path,
+                                               padded_hash_data_));
+}
+
+TEST_F(PayloadSignerTest, VerifySignatureTest) {
+  chromeos::Blob signature_blob;
+  SignSampleData(&signature_blob, {kUnittestPrivateKeyPath});
+
+  EXPECT_TRUE(PayloadVerifier::VerifySignature(signature_blob,
+                                               kUnittestPublicKeyPath,
+                                               padded_hash_data_));
+  // Passing the invalid key should fail the verification.
+  EXPECT_FALSE(PayloadVerifier::VerifySignature(signature_blob,
+                                                kUnittestPublicKey2Path,
+                                                padded_hash_data_));
 }
 
 }  // namespace chromeos_update_engine
diff --git a/payload_verifier.cc b/payload_verifier.cc
index c3dc134..f713fb1 100644
--- a/payload_verifier.cc
+++ b/payload_verifier.cc
@@ -28,9 +28,6 @@
 
 namespace chromeos_update_engine {
 
-const uint32_t kSignatureMessageOriginalVersion = 1;
-const uint32_t kSignatureMessageCurrentVersion = 1;
-
 namespace {
 
 // The following is a standard PKCS1-v1_5 padding for SHA256 signatures, as
@@ -111,38 +108,43 @@
 
 bool PayloadVerifier::VerifySignature(const chromeos::Blob& signature_blob,
                                       const string& public_key_path,
-                                      chromeos::Blob* out_hash_data) {
-  return VerifySignatureBlob(signature_blob, public_key_path,
-                             kSignatureMessageCurrentVersion, out_hash_data);
-}
-
-bool PayloadVerifier::VerifySignatureBlob(
-    const chromeos::Blob& signature_blob,
-    const string& public_key_path,
-    uint32_t client_version,
-    chromeos::Blob* out_hash_data) {
+                                      const chromeos::Blob& hash_data) {
   TEST_AND_RETURN_FALSE(!public_key_path.empty());
 
   Signatures signatures;
-  LOG(INFO) << "signature size = " <<  signature_blob.size();
+  LOG(INFO) << "signature blob size = " <<  signature_blob.size();
   TEST_AND_RETURN_FALSE(signatures.ParseFromArray(signature_blob.data(),
                                                   signature_blob.size()));
 
-  // Finds a signature that matches the current version.
-  int sig_index = 0;
-  for (; sig_index < signatures.signatures_size(); sig_index++) {
-    const Signatures_Signature& signature = signatures.signatures(sig_index);
-    if (signature.has_version() &&
-        signature.version() == client_version) {
-      break;
-    }
+  if (!signatures.signatures_size()) {
+    LOG(ERROR) << "No signatures stored in the blob.";
+    return false;
   }
-  TEST_AND_RETURN_FALSE(sig_index < signatures.signatures_size());
 
-  const Signatures_Signature& signature = signatures.signatures(sig_index);
-  chromeos::Blob sig_data(signature.data().begin(), signature.data().end());
+  std::vector<chromeos::Blob> tested_hashes;
+  // Tries every signature in the signature blob.
+  for (int i = 0; i < signatures.signatures_size(); i++) {
+    const Signatures_Signature& signature = signatures.signatures(i);
+    chromeos::Blob sig_data(signature.data().begin(), signature.data().end());
+    chromeos::Blob sig_hash_data;
+    if (!GetRawHashFromSignature(sig_data, public_key_path, &sig_hash_data))
+      continue;
 
-  return GetRawHashFromSignature(sig_data, public_key_path, out_hash_data);
+    if (hash_data == sig_hash_data) {
+      LOG(INFO) << "Verified correct signature " << i + 1 << " out of "
+                << signatures.signatures_size() << " signatures.";
+      return true;
+    }
+    tested_hashes.push_back(sig_hash_data);
+  }
+  LOG(ERROR) << "None of the " << signatures.signatures_size()
+             << " signatures is correct. Expected:";
+  utils::HexDumpVector(hash_data);
+  LOG(ERROR) << "But found decrypted hashes:";
+  for (const auto& sig_hash_data : tested_hashes) {
+    utils::HexDumpVector(sig_hash_data);
+  }
+  return false;
 }
 
 
@@ -191,8 +193,7 @@
 }
 
 bool PayloadVerifier::VerifySignedPayload(const string& payload_path,
-                                          const string& public_key_path,
-                                          uint32_t client_key_check_version) {
+                                          const string& public_key_path) {
   chromeos::Blob payload;
   DeltaArchiveManifest manifest;
   uint64_t metadata_size;
@@ -206,15 +207,12 @@
   chromeos::Blob signature_blob(
       payload.begin() + metadata_size + manifest.signatures_offset(),
       payload.end());
-  chromeos::Blob signed_hash;
-  TEST_AND_RETURN_FALSE(VerifySignatureBlob(
-      signature_blob, public_key_path, client_key_check_version, &signed_hash));
-  TEST_AND_RETURN_FALSE(!signed_hash.empty());
   chromeos::Blob hash;
   TEST_AND_RETURN_FALSE(OmahaHashCalculator::RawHashOfBytes(
       payload.data(), metadata_size + manifest.signatures_offset(), &hash));
-  PadRSA2048SHA256Hash(&hash);
-  TEST_AND_RETURN_FALSE(hash == signed_hash);
+  TEST_AND_RETURN_FALSE(PadRSA2048SHA256Hash(&hash));
+  TEST_AND_RETURN_FALSE(VerifySignature(
+      signature_blob, public_key_path, hash));
   return true;
 }
 
diff --git a/payload_verifier.h b/payload_verifier.h
index edaa754..faea31d 100644
--- a/payload_verifier.h
+++ b/payload_verifier.h
@@ -30,26 +30,16 @@
 
 namespace chromeos_update_engine {
 
-extern const uint32_t kSignatureMessageOriginalVersion;
-extern const uint32_t kSignatureMessageCurrentVersion;
-
 class PayloadVerifier {
  public:
-  // Returns false if the payload signature can't be verified. Returns true
-  // otherwise and sets |out_hash| to the signed payload hash.
+  // Interprets |signature_blob| as a protocol buffer containing the Signatures
+  // message and decrypts each signature data using the |public_key_path|.
+  // Returns whether *any* of the decrypted hashes matches the |hash_data|.
+  // In case of any error parsing the signatures or the public key, returns
+  // false.
   static bool VerifySignature(const chromeos::Blob& signature_blob,
                               const std::string& public_key_path,
-                              chromeos::Blob* out_hash_data);
-
-  // Interprets signature_blob as a protocol buffer containing the Signatures
-  // message and decrypts the signature data using the public_key_path and
-  // stores the resultant raw hash data in out_hash_data. Returns true if
-  // everything is successful. False otherwise. It also takes the client_version
-  // and interprets the signature blob according to that version.
-  static bool VerifySignatureBlob(const chromeos::Blob& signature_blob,
-                                  const std::string& public_key_path,
-                                  uint32_t client_version,
-                                  chromeos::Blob* out_hash_data);
+                              const chromeos::Blob& hash_data);
 
   // Decrypts sig_data with the given public_key_path and populates
   // out_hash_data with the decoded raw hash. Returns true if successful,
@@ -62,8 +52,7 @@
   // verified using the public key in |public_key_path| with the signature
   // of a given version in the signature blob. Returns false otherwise.
   static bool VerifySignedPayload(const std::string& payload_path,
-                                  const std::string& public_key_path,
-                                  uint32_t client_key_check_version);
+                                  const std::string& public_key_path);
 
   // Pads a SHA256 hash so that it may be encrypted/signed with RSA2048
   // using the PKCS#1 v1.5 scheme.