net: add low-entropy, shared secret authentication protocol.

BUG=none
TEST=crypto_unittests


Review URL: http://codereview.chromium.org/8499032

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@111070 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 518 insertions, 0 deletions

diff --git a/crypto/crypto.gyp b/crypto/crypto.gyp
index 416f64c..2b3ec73 100644
--- a/crypto/crypto.gyp
+++ b/crypto/crypto.gyp
@@ -147,6 +147,8 @@
         'hmac_win.cc',
         'mac_security_services_lock.cc',
         'mac_security_services_lock.h',
+        'p224_spake.cc',
+        'p224_spake.h',
         'nss_util.cc',
         'nss_util.h',
         'nss_util_internal.h',
@@ -206,6 +208,7 @@
         'encryptor_unittest.cc',
         'hmac_unittest.cc',
         'p224_unittest.cc',
+        'p224_spake_unittest.cc',
         'rsa_private_key_unittest.cc',
         'rsa_private_key_nss_unittest.cc',
         'secure_hash_unittest.cc',
diff --git a/crypto/p224.h b/crypto/p224.h
index 0b2aca9..412ca99 100644
--- a/crypto/p224.h
+++ b/crypto/p224.h
@@ -36,6 +36,10 @@ struct CRYPTO_EXPORT Point {
   FieldElement x, y, z;
 };
 
+// kScalarBytes is the number of bytes needed to represent an element of the
+// P224 field.
+static const size_t kScalarBytes = 28;
+
 // ScalarMult computes *out = in*scalar where scalar is a 28-byte, big-endian
 // number.
 void CRYPTO_EXPORT ScalarMult(const Point& in, const uint8* scalar, Point* out);
diff --git a/crypto/p224_spake.cc b/crypto/p224_spake.cc
new file mode 100644
index 0000000..3d83e25
--- /dev/null
+++ b/crypto/p224_spake.cc
@@ -0,0 +1,259 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// This code implements SPAKE2, a varient of EKE:
+//  http://www.di.ens.fr/~pointche/pub.php?reference=AbPo04
+
+#include <crypto/p224_spake.h>
+
+#include <base/logging.h>
+#include <base/rand_util.h>
+#include <crypto/p224.h>
+#include <crypto/secure_util.h>
+
+namespace {
+
+// The following two points (M and N in the protocol) are verifiable random
+// points on the curve and can be generated with the following code:
+
+// #include <stdint.h>
+// #include <stdio.h>
+// #include <string.h>
+//
+// #include <openssl/ec.h>
+// #include <openssl/obj_mac.h>
+// #include <openssl/sha.h>
+//
+// static const char kSeed1[] = "P224 point generation seed (M)";
+// static const char kSeed2[] = "P224 point generation seed (N)";
+//
+// void find_seed(const char* seed) {
+//   SHA256_CTX sha256;
+//   uint8_t digest[SHA256_DIGEST_LENGTH];
+//
+//   SHA256_Init(&sha256);
+//   SHA256_Update(&sha256, seed, strlen(seed));
+//   SHA256_Final(digest, &sha256);
+//
+//   BIGNUM x, y;
+//   EC_GROUP* p224 = EC_GROUP_new_by_curve_name(NID_secp224r1);
+//   EC_POINT* p = EC_POINT_new(p224);
+//
+//   for (unsigned i = 0;; i++) {
+//     BN_init(&x);
+//     BN_bin2bn(digest, 28, &x);
+//
+//     if (EC_POINT_set_compressed_coordinates_GFp(
+//             p224, p, &x, digest[28] & 1, NULL)) {
+//       BN_init(&y);
+//       EC_POINT_get_affine_coordinates_GFp(p224, p, &x, &y, NULL);
+//       char* x_str = BN_bn2hex(&x);
+//       char* y_str = BN_bn2hex(&y);
+//       printf("Found after %u iterations:\n%s\n%s\n", i, x_str, y_str);
+//       OPENSSL_free(x_str);
+//       OPENSSL_free(y_str);
+//       BN_free(&x);
+//       BN_free(&y);
+//       break;
+//     }
+//
+//     SHA256_Init(&sha256);
+//     SHA256_Update(&sha256, digest, sizeof(digest));
+//     SHA256_Final(digest, &sha256);
+//
+//     BN_free(&x);
+//   }
+//
+//   EC_POINT_free(p);
+//   EC_GROUP_free(p224);
+// }
+//
+// int main() {
+//   find_seed(kSeed1);
+//   find_seed(kSeed2);
+//   return 0;
+// }
+
+const crypto::p224::Point kM = {
+  {174237515, 77186811, 235213682, 33849492,
+   33188520, 48266885, 177021753, 81038478},
+  {104523827, 245682244, 266509668, 236196369,
+   28372046, 145351378, 198520366, 113345994},
+  {1, 0, 0, 0, 0, 0, 0},
+};
+
+const crypto::p224::Point kN = {
+  {136176322, 263523628, 251628795, 229292285,
+   5034302, 185981975, 171998428, 11653062},
+  {197567436, 51226044, 60372156, 175772188,
+   42075930, 8083165, 160827401, 65097570},
+  {1, 0, 0, 0, 0, 0, 0},
+};
+
+}  // anonymous namespace
+
+namespace crypto {
+
+P224EncryptedKeyExchange::P224EncryptedKeyExchange(
+    PeerType peer_type,
+    const base::StringPiece& password,
+    const base::StringPiece& session)
+    : state_(kStateInitial),
+      is_server_(peer_type == kPeerTypeServer) {
+  // x_ is a random scalar.
+  base::RandBytes(x_, sizeof(x_));
+
+  // X = g**x_
+  p224::Point X;
+  p224::ScalarBaseMult(x_, &X);
+
+  // The "password" in the SPAKE2 protocol is
+  // SHA256(P(password) + P(session)) where P is function that prepends a
+  // uint32, big-endian length prefix.
+  uint8 password_length[4], session_length[4];
+  password_length[0] = password.size() >> 24;
+  password_length[1] = password.size() >> 16;
+  password_length[2] = password.size() >> 8;
+  password_length[3] = password.size();
+  session_length[0] = session.size() >> 24;
+  session_length[1] = session.size() >> 16;
+  session_length[2] = session.size() >> 8;
+  session_length[3] = session.size();
+  SHA256HashString(std::string(reinterpret_cast<const char *>(password_length),
+                               sizeof(password_length)) +
+                   password.as_string() +
+                   std::string(reinterpret_cast<const char *>(session_length),
+                               sizeof(session_length)) +
+                   session.as_string(),
+                   pw_,
+                   sizeof(pw_));
+
+  // The client masks the Diffie-Hellman value, X, by adding M**pw and the
+  // server uses N**pw.
+  p224::Point MNpw;
+  p224::ScalarMult(is_server_ ? kN : kM, pw_, &MNpw);
+
+  // X* = X + (N|M)**pw
+  p224::Point Xstar;
+  p224::Add(X, MNpw, &Xstar);
+
+  next_message_ = Xstar.ToString();
+}
+
+const std::string& P224EncryptedKeyExchange::GetMessage() {
+  if (state_ == kStateInitial) {
+    state_ = kStateRecvDH;
+    return next_message_;
+  } else if (state_ == kStateSendHash) {
+    state_ = kStateRecvHash;
+    return next_message_;
+  }
+
+  LOG(FATAL) << "P224EncryptedKeyExchange::GetMessage called in"
+                " bad state " << state_;
+  next_message_ = "";
+  return next_message_;
+}
+
+P224EncryptedKeyExchange::Result P224EncryptedKeyExchange::ProcessMessage(
+    const base::StringPiece& message) {
+  if (state_ == kStateRecvHash) {
+    // This is the final state of the protocol: we are reading the peer's
+    // authentication hash and checking that it matches the one that we expect.
+    if (message.size() != sizeof(expected_authenticator_)) {
+      error_ = "peer's hash had an incorrect size";
+      return kResultFailed;
+    }
+    if (!SecureMemEqual(message.data(), expected_authenticator_,
+                        message.size())) {
+      error_ = "peer's hash had incorrect value";
+      return kResultFailed;
+    }
+    state_ = kStateDone;
+    return kResultSuccess;
+  }
+
+  if (state_ != kStateRecvDH) {
+    LOG(FATAL) << "P224EncryptedKeyExchange::ProcessMessage called in"
+                  " bad state " << state_;
+    error_ = "internal error";
+    return kResultFailed;
+  }
+
+  // Y* is the other party's masked, Diffie-Hellman value.
+  p224::Point Ystar;
+  if (!Ystar.SetFromString(message)) {
+    error_ = "failed to parse peer's masked Diffie-Hellman value";
+    return kResultFailed;
+  }
+
+  // We calculate the mask value: (N|M)**pw
+  p224::Point MNpw, minus_MNpw, Y, k;
+  p224::ScalarMult(is_server_ ? kM : kN, pw_, &MNpw);
+  p224::Negate(MNpw, &minus_MNpw);
+
+  // Y = Y* - (N|M)**pw
+  p224::Add(Ystar, minus_MNpw, &Y);
+
+  // K = Y**x_
+  p224::ScalarMult(Y, x_, &k);
+
+  // If everything worked out, then K is the same for both parties.
+  std::string k_str = k.ToString();
+
+  std::string client_masked_dh, server_masked_dh;
+  if (is_server_) {
+    client_masked_dh = message.as_string();
+    server_masked_dh = next_message_;
+  } else {
+    client_masked_dh = next_message_;
+    server_masked_dh = message.as_string();
+  }
+
+  // Now we calculate the hashes that each side will use to prove to the other
+  // that they derived the correct value for K.
+  uint8 client_hash[kSHA256Length], server_hash[kSHA256Length];
+  CalculateHash(kPeerTypeClient, client_masked_dh, server_masked_dh, k_str,
+                client_hash);
+  CalculateHash(kPeerTypeServer, client_masked_dh, server_masked_dh, k_str,
+                server_hash);
+
+  const uint8* my_hash = is_server_ ? server_hash : client_hash;
+  const uint8* their_hash = is_server_ ? client_hash : server_hash;
+
+  next_message_ =
+      std::string(reinterpret_cast<const char*>(my_hash), kSHA256Length);
+  memcpy(expected_authenticator_, their_hash, kSHA256Length);
+  state_ = kStateSendHash;
+  return kResultPending;
+}
+
+void P224EncryptedKeyExchange::CalculateHash(
+    PeerType peer_type,
+    const std::string& client_masked_dh,
+    const std::string& server_masked_dh,
+    const std::string& k,
+    uint8* out_digest) {
+  std::string hash_contents;
+
+  if (peer_type == kPeerTypeServer) {
+    hash_contents = "server";
+  } else {
+    hash_contents = "client";
+  }
+
+  hash_contents += client_masked_dh;
+  hash_contents += server_masked_dh;
+  hash_contents +=
+      std::string(reinterpret_cast<const char *>(pw_), sizeof(pw_));
+  hash_contents += k;
+
+  SHA256HashString(hash_contents, out_digest, kSHA256Length);
+}
+
+const std::string& P224EncryptedKeyExchange::error() const {
+  return error_;
+}
+
+}  // namespace crypto
diff --git a/crypto/p224_spake.h b/crypto/p224_spake.h
new file mode 100644
index 0000000..0441efb
--- /dev/null
+++ b/crypto/p224_spake.h
@@ -0,0 +1,113 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CRYPTO_P224_SPAKE_H_
+#define CRYPTO_P224_SPAKE_H_
+#pragma once
+
+#include <base/string_piece.h>
+#include <crypto/p224.h>
+#include <crypto/sha2.h>
+
+namespace crypto {
+
+// P224EncryptedKeyExchange provides a means to authenticate an
+// encrypted transport using a low-entropy, shared secret.
+//
+// You need a value derived from the master secret of the connection in order
+// to bind the authentication to the encrypted channel. It's the |session|
+// argument to the constructor and can be of any length.
+//
+// The password can be low entropy as authenticating with an attacker only
+// gives the attacker a one-shot password oracle. No other information about
+// the password is leaked. (However, you must be sure to limit the number of
+// permitted authentication attempts otherwise they get many one-shot oracles.)
+//
+// The protocol requires several RTTs (actually two, but you shouldn't assume
+// that.) To use the object, call GetMessage() and pass that message to the
+// peer. Get a message from the peer and feed it into ProcessMessage. Then
+// examine the return value of ProcessMessage:
+//   kResultPending: Another round is required. Call GetMessage and repeat.
+//   kResultFailed: The authentication has failed. You can get a human readable
+//       error message by calling error().
+//   kResultSuccess: The authentication was successful.
+//
+// In each exchange, each peer always sends a message.
+class CRYPTO_EXPORT P224EncryptedKeyExchange {
+ public:
+  enum Result {
+    kResultPending,
+    kResultFailed,
+    kResultSuccess,
+  };
+
+  // PeerType's values are named client and server due to convention. But
+  // they could be called "A" and "B" as far as the protocol is concerned so
+  // long as the two parties don't both get the same label.
+  enum PeerType {
+    kPeerTypeClient,
+    kPeerTypeServer,
+  };
+
+  // peer_type: the type of the local authentication party.
+  // password: a, possibly low-entropy, mutually known password.
+  // session: a value securely derived from the connection's master secret.
+  //     Both parties to the authentication must pass the same value. For the
+  //     case of a TLS connection, see RFC 5705.
+  P224EncryptedKeyExchange(PeerType peer_type,
+                           const base::StringPiece& password,
+                           const base::StringPiece& session);
+
+  // GetMessage returns a byte string which must be passed to the other party
+  // in the authentication.
+  const std::string& GetMessage();
+
+  // ProcessMessage processes a message which must have been generated by a
+  // call to GetMessage() by the other party.
+  Result ProcessMessage(const base::StringPiece& message);
+
+  // In the event that ProcessMessage() returns kResultFailed, error will
+  // return a human readable error message.
+  const std::string& error() const;
+
+ private:
+  // The authentication state machine is very simple and each party proceeds
+  // through each of these states, in order.
+  enum State {
+    kStateInitial,
+    kStateRecvDH,
+    kStateSendHash,
+    kStateRecvHash,
+    kStateDone,
+  };
+
+  State state_;
+  const bool is_server_;
+  // next_message_ contains a value for GetMessage() to return.
+  std::string next_message_;
+  std::string error_;
+
+  // CalculateHash computes the verification hash for the given peer and writes
+  // |kSHA256Length| bytes at |out_digest|.
+  void CalculateHash(
+      PeerType peer_type,
+      const std::string& client_masked_dh,
+      const std::string& server_masked_dh,
+      const std::string& k,
+      uint8* out_digest);
+
+  // x_ is the secret Diffie-Hellman exponent (see paper referenced in .cc
+  // file).
+  uint8 x_[p224::kScalarBytes];
+  // pw_ is SHA256(P(password), P(session))[:28] where P() prepends a uint32,
+  // big-endian length prefix (see paper refereneced in .cc file).
+  uint8 pw_[p224::kScalarBytes];
+  // expected_authenticator_ is used to store the hash value expected from the
+  // other party.
+  uint8 expected_authenticator_[kSHA256Length];
+};
+
+}  // namespace crypto
+
+#endif  // CRYPTO_P224_SPAKE_H_
diff --git a/crypto/p224_spake_unittest.cc b/crypto/p224_spake_unittest.cc
new file mode 100644
index 0000000..e45ec82
--- /dev/null
+++ b/crypto/p224_spake_unittest.cc
@@ -0,0 +1,139 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <crypto/p224_spake.h>
+
+#include "base/logging.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+using namespace crypto;
+
+bool RunExchange(P224EncryptedKeyExchange* client,
+                 P224EncryptedKeyExchange* server) {
+
+  for (;;) {
+    std::string client_message, server_message;
+    client_message = client->GetMessage();
+    server_message = server->GetMessage();
+
+    P224EncryptedKeyExchange::Result client_result, server_result;
+    client_result = client->ProcessMessage(server_message);
+    server_result = server->ProcessMessage(client_message);
+
+    // Check that we never hit the case where only one succeeds.
+    if ((client_result == P224EncryptedKeyExchange::kResultSuccess) ^
+        (server_result == P224EncryptedKeyExchange::kResultSuccess)) {
+      CHECK(false) << "Parties differ on whether authentication was successful";
+    }
+
+    if (client_result == P224EncryptedKeyExchange::kResultFailed ||
+        server_result == P224EncryptedKeyExchange::kResultFailed) {
+      return false;
+    }
+
+    if (client_result == P224EncryptedKeyExchange::kResultSuccess &&
+        server_result == P224EncryptedKeyExchange::kResultSuccess) {
+      return true;
+    }
+
+    CHECK_EQ(P224EncryptedKeyExchange::kResultPending, client_result);
+    CHECK_EQ(P224EncryptedKeyExchange::kResultPending, server_result);
+  }
+}
+
+static const char kPassword[] = "foo";
+static const char kSession[] = "bar";
+
+TEST(MutualAuth, CorrectAuth) {
+  P224EncryptedKeyExchange client(
+      P224EncryptedKeyExchange::kPeerTypeClient,
+      kPassword, kSession);
+  P224EncryptedKeyExchange server(
+      P224EncryptedKeyExchange::kPeerTypeServer,
+      kPassword, kSession);
+
+  EXPECT_TRUE(RunExchange(&client, &server));
+}
+
+TEST(MutualAuth, IncorrectPassword) {
+  P224EncryptedKeyExchange client(
+      P224EncryptedKeyExchange::kPeerTypeClient,
+      kPassword, kSession);
+  P224EncryptedKeyExchange server(
+      P224EncryptedKeyExchange::kPeerTypeServer,
+      "wrongpassword", kSession);
+
+  EXPECT_FALSE(RunExchange(&client, &server));
+}
+
+TEST(MutualAuth, IncorrectSession) {
+  P224EncryptedKeyExchange client(
+      P224EncryptedKeyExchange::kPeerTypeClient,
+      kPassword, kSession);
+  P224EncryptedKeyExchange server(
+      P224EncryptedKeyExchange::kPeerTypeServer,
+      kPassword, "wrongsession");
+
+  EXPECT_FALSE(RunExchange(&client, &server));
+}
+
+TEST(MutualAuth, Fuzz) {
+  static const unsigned kIterations = 40;
+
+  for (unsigned i = 0; i < kIterations; i++) {
+    P224EncryptedKeyExchange client(
+        P224EncryptedKeyExchange::kPeerTypeClient,
+        kPassword, kSession);
+    P224EncryptedKeyExchange server(
+        P224EncryptedKeyExchange::kPeerTypeServer,
+        kPassword, kSession);
+
+    // We'll only be testing small values of i, but we don't want that to bias
+    // the test coverage. So we disperse the value of i by multiplying by the
+    // FNV, 32-bit prime, producing a poor-man's PRNG.
+    const uint32 rand = i * 16777619;
+
+    for (unsigned round = 0;; round++) {
+      std::string client_message, server_message;
+      client_message = client.GetMessage();
+      server_message = server.GetMessage();
+
+      if ((rand & 1) == round) {
+        const bool server_or_client = rand & 2;
+        std::string* m = server_or_client ? &server_message : &client_message;
+        if (rand & 4) {
+          // Truncate
+          *m = m->substr(0, (i >> 3) % m->size());
+        } else {
+          // Corrupt
+          const size_t bits = m->size() * 8;
+          const size_t bit_to_corrupt = (rand >> 3) % bits;
+          const_cast<char*>(m->data())[bit_to_corrupt / 8] ^=
+              1 << (bit_to_corrupt % 8);
+        }
+      }
+
+      P224EncryptedKeyExchange::Result client_result, server_result;
+      client_result = client.ProcessMessage(server_message);
+      server_result = server.ProcessMessage(client_message);
+
+      // If we have corrupted anything, we expect the authentication to fail,
+      // although one side can succeed if we happen to corrupt the second round
+      // message to the other.
+      ASSERT_FALSE(
+          client_result == P224EncryptedKeyExchange::kResultSuccess &&
+          server_result == P224EncryptedKeyExchange::kResultSuccess);
+
+      if (client_result == P224EncryptedKeyExchange::kResultFailed ||
+          server_result == P224EncryptedKeyExchange::kResultFailed) {
+        break;
+      }
+
+      ASSERT_EQ(P224EncryptedKeyExchange::kResultPending,
+                client_result);
+      ASSERT_EQ(P224EncryptedKeyExchange::kResultPending,
+                server_result);
+    }
+  }
+}