Repository: randombit/botan
Pull request #3236 (2023-01-31 12:10:54)

Fix a bug in SRP6
The crticial issue is that when computing the client-side key, the exponent a+u*x was reduced modulo p, which is completely incorrect. At best, we could reduce it modulo the group order, but this is hard to do given how SRP groups are structured.

This only caused problems when the hash function used is >= half of the bitlength of the group, since otherwise the reduction was a no-op. This is why it caused very occasional failures for the Python tests; it uses the 1024 bit group with SHA-512.

Outside of using something like SHAKE with SRP6, the most likely case where this would cause problems is exactly the situation for the Python tests.

GH #3232


Patch:
diff --git a/src/lib/misc/srp6/srp6.cpp b/src/lib/misc/srp6/srp6.cpp
index 903371bb8..c0ea6cf52 100644
--- a/src/lib/misc/srp6/srp6.cpp
+++ b/src/lib/misc/srp6/srp6.cpp
@@ -94,6 +94,8 @@ srp6_client_agree(const std::string& identifier,
                   const size_t a_bits,
                   RandomNumberGenerator& rng)
    {
+   BOTAN_ARG_CHECK(a_bits <= group.p_bits(), "Invalid a_bits");
+
    const BigInt& g = group.get_g();
    const BigInt& p = group.get_p();
 
@@ -103,6 +105,9 @@ srp6_client_agree(const std::string& identifier,
       throw Decoding_Error("Invalid SRP parameter from server");
 
    std::unique_ptr<HashFunction> hash_fn(HashFunction::create_or_throw(hash_id));
+   if(8*hash_fn->output_length() >= group.p_bits())
+      throw Invalid_Argument("Hash function " + hash_id +
+                             " too large for SRP6 with this group");
 
    const BigInt k = hash_seq(*hash_fn, p_bytes, p, g);
 
@@ -116,10 +121,16 @@ srp6_client_agree(const std::string& identifier,
 
    const BigInt g_x_p = group.power_g_p(x, hash_fn->output_length()*8);
 
-   const BigInt B_k_g_x_p = group.mod_p(B - (k * g_x_p));
-   const BigInt a_ux = group.mod_p(a + (u * x));
+   const BigInt B_k_g_x_p = group.mod_p(B - group.multiply_mod_p(k, g_x_p));
+
+   const BigInt a_ux = a + u*x;
 
-   const BigInt S = group.power_b_p(B_k_g_x_p, a_ux, group.p_bits());
+   const size_t max_aux_bits =
+      std::max<size_t>(a_bits + 1,
+                       2*8*hash_fn->output_length());
+   BOTAN_ASSERT_NOMSG(max_aux_bits >= a_ux.bits());
+
+   const BigInt S = group.power_b_p(B_k_g_x_p, a_ux, max_aux_bits);
 
    const SymmetricKey Sk(BigInt::encode_1363(S, p_bytes));
 
@@ -143,6 +154,10 @@ BigInt generate_srp6_verifier(const std::string& identifier,
                               const std::string& hash_id)
    {
    std::unique_ptr<HashFunction> hash_fn(HashFunction::create_or_throw(hash_id));
+   if(8*hash_fn->output_length() >= group.p_bits())
+      throw Invalid_Argument("Hash function " + hash_id +
+                             " too large for SRP6 with this group");
+
    const BigInt x = compute_x(*hash_fn, identifier, password, salt);
    return group.power_g_p(x, hash_fn->output_length() * 8);
    }
@@ -163,19 +178,23 @@ BigInt SRP6_Server_Session::step1(const BigInt& v,
                                   size_t b_bits,
                                   RandomNumberGenerator& rng)
    {
+   BOTAN_ARG_CHECK(b_bits <= group.p_bits(), "Invalid b_bits");
+
+   m_group = group;
+
    const BigInt& g = group.get_g();
    const BigInt& p = group.get_p();
 
-   m_p_bytes = p.bytes();
    m_v = v;
    m_b = BigInt(rng, b_bits);
-   m_p = p;
    m_hash_id = hash_id;
 
    std::unique_ptr<HashFunction> hash_fn(HashFunction::create_or_throw(hash_id));
+   if(8*hash_fn->output_length() >= m_group.p_bits())
+      throw Invalid_Argument("Hash function " + hash_id +
+                             " too large for SRP6 with this group");
 
-   const BigInt k = hash_seq(*hash_fn, m_p_bytes, p, g);
-
+   const BigInt k = hash_seq(*hash_fn, m_group.p_bytes(), p, g);
    m_B = group.mod_p(v*k + group.power_g_p(m_b, b_bits));
 
    return m_B;
@@ -183,15 +202,20 @@ BigInt SRP6_Server_Session::step1(const BigInt& v,
 
 SymmetricKey SRP6_Server_Session::step2(const BigInt& A)
    {
-   if(A <= 0 || A >= m_p)
+   if(A <= 0 || A >= m_group.get_p())
       throw Decoding_Error("Invalid SRP parameter from client");
 
    std::unique_ptr<HashFunction> hash_fn(HashFunction::create_or_throw(m_hash_id));
-   const BigInt u = hash_seq(*hash_fn, m_p_bytes, A, m_B);
+   if(8*hash_fn->output_length() >= m_group.p_bits())
+      throw Invalid_Argument("Hash function " + m_hash_id +
+                             " too large for SRP6 with this group");
+
+   const BigInt u = hash_seq(*hash_fn, m_group.p_bytes(), A, m_B);
 
-   const BigInt S = power_mod(A * power_mod(m_v, u, m_p), m_b, m_p);
+   const BigInt vup = m_group.power_b_p(m_v, u, m_group.p_bits());
+   const BigInt S = m_group.power_b_p(m_group.multiply_mod_p(A, vup), m_b, m_group.p_bits());
 
-   return BigInt::encode_1363(S, m_p_bytes);
+   return BigInt::encode_1363(S, m_group.p_bytes());
    }
 
 }
diff --git a/src/lib/misc/srp6/srp6.h b/src/lib/misc/srp6/srp6.h
index 6bb4b7e7c..42b724b23 100644
--- a/src/lib/misc/srp6/srp6.h
+++ b/src/lib/misc/srp6/srp6.h
@@ -10,11 +10,11 @@
 
 #include <botan/bigint.h>
 #include <botan/symkey.h>
+#include <botan/dl_group.h>
 #include <string>
 
 namespace Botan {
 
-class DL_Group;
 class RandomNumberGenerator;
 
 /**
@@ -145,9 +145,9 @@ class BOTAN_PUBLIC_API(2,0) SRP6_Server_Session final
       SymmetricKey step2(const BigInt& A);
 
    private:
+      DL_Group m_group;
       std::string m_hash_id;
-      BigInt m_B, m_b, m_v, m_S, m_p;
-      size_t m_p_bytes = 0;
+      BigInt m_B, m_b, m_v, m_S;
    };
 
 }


Test patch:
diff --git a/src/scripts/test_python.py b/src/scripts/test_python.py
index 309dbcd8f..ee287872b 100644
--- a/src/scripts/test_python.py
+++ b/src/scripts/test_python.py
@@ -706,42 +706,18 @@ ofvkP1EDmpx50fHLawIDAQAB
         identity = 'alice'
         password = 'password123'
         rng = botan2.RandomNumberGenerator()
+        group = 'modp/srp/1024'
+        hash_fn = 'SHA-512'
 
         # Test successful authentication
         server = botan2.Srp6ServerSession()
         salt = rng.get(24)
-        verifier = botan2.generate_srp6_verifier(identity, password, salt, 'modp/srp/1024', 'SHA-512')
-        b = server.step1(verifier, 'modp/srp/1024', 'SHA-512', rng)
-        (a, key_c) = botan2.srp6_client_agree(identity, password, 'modp/srp/1024', 'SHA-512', salt, b, rng)
+        verifier = botan2.generate_srp6_verifier(identity, password, salt, group, hash_fn)
+        b = server.step1(verifier, group, hash_fn, rng)
+        (a, key_c) = botan2.srp6_client_agree(identity, password, group, hash_fn, salt, b, rng)
         key_s = server.step2(a)
         self.assertEqual(key_c, key_s)
 
-        # Test wrong server ephemeral
-        try:
-            salt = rng.get(24)
-            b = b'BD0C6151 2C692C0C B6D041FA 01BB152D 4916A1E7 7AF46AE1 05393011 \
-            BAF38964 DC46A067 0DD125B9 5A981652 236F99D9 B681CBF8 7837EC99 \
-            6C6DA044 53728610 D0C6DDB5 8B318885 D7D82C7F 8DEB75CE 7BD4FBAA \
-            37089E6F 9C6059F3 88838E7A 00030B33 1EB76840 910440B1 B27AAEAE \
-            EB4012B7 D7665238 A8E3FB00 4B117B58'
-            botan2.srp6_client_agree(identity, password, 'modp/srp/1024', 'SHA-512', salt, b, rng)
-        except botan2.BotanException as e:
-            self.assertEqual(str(e), "botan_srp6_client_agree failed: -1 (Invalid input): Invalid SRP parameter from server")
-
-        # Test wrong client ephemeral
-        try:
-            salt = rng.get(24)
-            verifier = botan2.generate_srp6_verifier(identity, password, salt, 'modp/srp/1024', 'SHA-512')
-            server.step1(verifier, 'modp/srp/1024', 'SHA-512', rng)
-            a = b'61D5E490 F6F1B795 47B0704C 436F523D D0E560F0 C64115BB 72557EC4 \
-            4352E890 3211C046 92272D8B 2D1A5358 A2CF1B6E 0BFCF99F 921530EC \
-            8E393561 79EAE45E 42BA92AE ACED8251 71E1E8B9 AF6D9C03 E1327F44 \
-            BE087EF0 6530E69F 66615261 EEF54073 CA11CF58 58F0EDFD FE15EFEA \
-            B349EF5D 76988A36 72FAC47B 0769447B'
-            server.step2(a)
-        except botan2.BotanException as e:
-            self.assertEqual(str(e), "botan_srp6_server_session_step2 failed: -32 (Bad parameter)")
-
 def main():
     parser = argparse.ArgumentParser()
     parser.add_argument('--test-data-dir', default='.')
diff --git a/src/tests/data/srp6a.vec b/src/tests/data/srp6a.vec
index aa1435d7b..c018f1e42 100644
--- a/src/tests/data/srp6a.vec
+++ b/src/tests/data/srp6a.vec
@@ -1,21 +1,36 @@
 
-# From RFC 5054
-
-N = 0xeeaf0ab9adb38dd69c33f80afa8fc5e86072618775ff3c0b9ea2314c9c256576d674df7496ea81d3383b4813d692c6e0e0d5d8e250b98be48e495c1d6089dad15dc7d7b46154d6b6ce8ef4ad69b15d4982559b297bcf1885c529f566660e57ec68edbc3c05726cc02fd4cbf4976eaa9afd5138fe8376435b9fc61d2fc0eb06e3
-g = 2
-
+# Parameters shared by all of the tests in this file:
 I = alice
 P = password123
 s = beb25379d1a8581eb5a727673a2441ee
 a = 60975527035cf2ad1989806f0407210bc81edc04e2762a56afd529ddda2d4393
 b = e487cb59d31ac550471e81f00f6928e01dda08e974a004f49e61f5d105284d20
 
+# From RFC 5054
+
+N = 0xeeaf0ab9adb38dd69c33f80afa8fc5e86072618775ff3c0b9ea2314c9c256576d674df7496ea81d3383b4813d692c6e0e0d5d8e250b98be48e495c1d6089dad15dc7d7b46154d6b6ce8ef4ad69b15d4982559b297bcf1885c529f566660e57ec68edbc3c05726cc02fd4cbf4976eaa9afd5138fe8376435b9fc61d2fc0eb06e3
+g = 2
+
 Hash = SHA-1
 v = 0x7e273de8696ffc4f4e337d05b4b375beb0dde1569e8fa00a9886d8129bada1f1822223ca1a605b530e379ba4729fdc59f105b4787e5186f5c671085a1447b52a48cf1970b4fb6f8400bbf4cebfbb168152e08ab5ea53d15c1aff87b2b9da6e04e058ad51cc72bfc9033b564e26480d78e955a5e29e7ab245db2be315e2099afb
 A = 0x61d5e490f6f1b79547b0704c436f523dd0e560f0c64115bb72557ec44352e8903211c04692272d8b2d1a5358a2cf1b6e0bfcf99f921530ec8e39356179eae45e42ba92aeaced825171e1e8b9af6d9c03e1327f44be087ef06530e69f66615261eef54073ca11cf5858f0edfdfe15efeab349ef5d76988a3672fac47b0769447b
 B = 0xbd0c61512c692c0cb6d041fa01bb152d4916a1e77af46ae105393011baf38964dc46a0670dd125b95a981652236f99d9b681cbf87837ec996c6da04453728610d0c6ddb58b318885d7d82c7f8deb75ce7bd4fbaa37089e6f9c6059f388838e7a00030b331eb76840910440b1b27aaeaeeb4012b7d7665238a8e3fb004b117b58
 S = b0dc82babcf30674ae450c0287745e7990a3381f63b387aaf271a10d233861e359b48220f7c4693c9ae12b0a6f67809f0876e2d013800d6c41bb59b6d5979b5c00a172b4a2a5903a0bdcaf8a709585eb2afafa8f3499b200210dcc1f10eb33943cd67fc88a2f39a4be5bec4ec0a3212dc346d7e474b29ede8a469ffeca686e5a
 
+# Generated by the script in https://github.com/secure-remote-password/test-vectors
+
+Hash = BLAKE2b(512)
+v = 0x8cb3f772b67d3d7b44d07840b9bf0c5f492f7e85aa337f96aface5b12f8036ada1bb76583753fca89858dea5f33c646208e31b72bd6fe9c27e4ff5e68f211b52a1726cacd9bbb885b0f0c327b387a658a84c45b27a108488b1bac6618744af5675266795f62941dfecc7a61f4ce59b4f9c1f92dca5e4d4affe6c2d4cbcb76627
+A = 0x61d5e490f6f1b79547b0704c436f523dd0e560f0c64115bb72557ec44352e8903211c04692272d8b2d1a5358a2cf1b6e0bfcf99f921530ec8e39356179eae45e42ba92aeaced825171e1e8b9af6d9c03e1327f44be087ef06530e69f66615261eef54073ca11cf5858f0edfdfe15efeab349ef5d76988a3672fac47b0769447b
+B = 0x4f0571ed14e68b76b4999c238093048187501c58b9fdf653c06837924a8f996a543d72c734ec6793f9fffba7fb65c1ebc5d8e28ad0aeb21cdb86d71ed36673d71878f0d3d8517781ae676f16164e8e7111c162fbed32fa6bcc3e88287222a434ded9f5e5352059cd91ffc839d6d3c6bce0eba4027cc04b4244e27d723be2e197
+S = d9d6c9abf277b0052e40df3a031358c03166e7f815425cca1abaaa637303184731dcdfdcc8c786ea164766eeab9fcd135c9cf8f6f7eb0da8f306543881a22f06a0b6ebd7498c72bcc520614e5af221dafb2fba19f45da6943f9552bb65fcb3819c66771dc180dd083da822862c4cd7d09d9e260c5f7657d06d40fcbd14bced40
+
+Hash = SHAKE-256(896)
+v = 0xc5c7b9a3668fbc4cb486230f80511f5b1b2e0b98663f4a1474f4428c73a970935a12d98a9138dc5457a77784515aaf829296a1359ea57338edca4a964b097a010faa72a7e1c77bbffaf0c4fd40db5c7bb339fe137f636e390058822016819345b38bd4e1bb0b139d02cfd262e4bf1132c1189a5a213c6d77cc2c60ccb7e8baf3
+A = 0x61d5e490f6f1b79547b0704c436f523dd0e560f0c64115bb72557ec44352e8903211c04692272d8b2d1a5358a2cf1b6e0bfcf99f921530ec8e39356179eae45e42ba92aeaced825171e1e8b9af6d9c03e1327f44be087ef06530e69f66615261eef54073ca11cf5858f0edfdfe15efeab349ef5d76988a3672fac47b0769447b
+B = 0xdadb013417426bca28d98fb6f9ebc3f76dd2522231f9a97beb442c41872356601c3ae4730fc50fd8006b353b9ca516827ba1dfeb70d3467877cd8aedfda96da9454dac2e360341c808650654ccf82cb3bfe25abd15222a2a15cf7b01d20a3206cc7c875ffaf9acbd184ca84cf176f8a9b337220aba69a98b5554db707f3e7b6a
+S = 81fed49434ebe0df24d4e631970811dee6099cd1033b96fc4111baa32e7bab0d6c32e326d8243925bd2b091a46888a8322282b226ce78f8b03875fc51b5b7c407932dda370b14c36e27baa906ffe7a465b0b88f8d735abf6a5fd0406ed18d8f64003b93acfe451757eb1978ef6429be79062f7327ef36cf3a5349a2d50340fda
+
 # All remaining tests from https://github.com/secure-remote-password/test-vectors
 
 Hash = SHA-256
diff --git a/src/tests/test_srp6.cpp b/src/tests/test_srp6.cpp
index cb1b64385..846616566 100644
--- a/src/tests/test_srp6.cpp
+++ b/src/tests/test_srp6.cpp
@@ -28,8 +28,6 @@ class SRP6_KAT_Tests final : public Text_Based_Test
 
       Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override
          {
-         Test::Result result("SRP6a");
-
          const std::string hash = vars.get_req_str("Hash");
          const std::string username = vars.get_req_str("I");
          const std::string password = vars.get_req_str("P");
@@ -43,22 +41,24 @@ class SRP6_KAT_Tests final : public Text_Based_Test
          const BigInt exp_B = vars.get_req_bn("B");
          const std::vector<uint8_t> exp_S = vars.get_req_bin("S");
 
+         const std::string group_id = Botan::srp6_group_identifier(N, g);
+         if(group_id == "")
+            throw Test_Error("Unknown SRP group used in test data");
+
+         Test::Result result("SRP6a " + group_id);
+
          if(Botan::HashFunction::create(hash) == nullptr)
             {
             result.test_note("Skipping test as hash function not available");
             return result;
             }
 
-         if(Test::run_long_tests() == false && N.bits() >= 4096)
+         if(N.bits() >= 4096 && !Test::run_long_tests())
             {
             result.test_note("Skipping test with long SRP modulus");
             return result;
             }
 
-         const std::string group_id = Botan::srp6_group_identifier(N, g);
-
-         result.test_ne("Known SRP group", group_id, "");
-
          Botan::DL_Group group(group_id);
 
          const Botan::BigInt v = Botan::generate_srp6_verifier(username, password, salt, group_id, hash);
@@ -78,9 +78,8 @@ class SRP6_KAT_Tests final : public Text_Based_Test
 
          const auto S = server.step2(srp_resp.first);
 
-         result.test_eq("SRP client and server agree", srp_resp.second, S);
-
-         result.test_eq("SRP S", srp_resp.second.bits_of(), exp_S);
+         result.test_eq("SRP client S", srp_resp.second.bits_of(), exp_S);
+         result.test_eq("SRP server S", S, exp_S);
 
          return result;
          }
@@ -96,34 +95,52 @@ class SRP6_RT_Tests final : public Test
       std::vector<Test::Result> run() override
          {
          std::vector<Test::Result> results;
-         Test::Result result("SRP6");
 
          const std::string username = "user";
          const std::string password = "Awellchosen1_to_be_sure_";
-         const std::string group_id = "modp/srp/1024";
          const std::string hash_id = "SHA-256";
 
-         std::vector<uint8_t> salt;
-         Test::rng().random_vec(salt, 16);
+         for(size_t b : { 1024, 1536, 2048, 3072, 4096, 6144, 8192 })
+            {
+            if(b >= 4096 && !Test::run_long_tests())
+               {
+               continue;
+               }
 
-         const Botan::BigInt verifier = Botan::generate_srp6_verifier(username, password, salt, group_id, hash_id);
+            const std::string group_id = "modp/srp/" + std::to_string(b);
+            Test::Result result("SRP6 " + group_id);
 
-         Botan::SRP6_Server_Session server;
+            result.start_timer();
+
+            const size_t trials = 8192 / b;
+
+            for(size_t t = 0; t != trials; ++t)
+               {
+               std::vector<uint8_t> salt;
+               Test::rng().random_vec(salt, 16);
 
-         const Botan::BigInt B = server.step1(verifier, group_id, hash_id, Test::rng());
+               const Botan::BigInt verifier =
+                  Botan::generate_srp6_verifier(username, password, salt, group_id, hash_id);
 
-         auto client = srp6_client_agree(username, password, group_id, hash_id, salt, B, Test::rng());
+               Botan::SRP6_Server_Session server;
 
-         const Botan::SymmetricKey server_K = server.step2(client.first);
+               const Botan::BigInt B = server.step1(verifier, group_id, hash_id, Test::rng());
 
-         result.test_eq("computed same keys", client.second.bits_of(), server_K.bits_of());
-         results.push_back(result);
+               auto client = srp6_client_agree(username, password, group_id, hash_id, salt, B, Test::rng());
+
+               const Botan::SymmetricKey server_K = server.step2(client.first);
+
+               result.test_eq("computed same keys", client.second.bits_of(), server_K.bits_of());
+               }
+            result.end_timer();
+            results.push_back(result);
+            }
 
          return results;
          }
    };
 
-BOTAN_REGISTER_TEST("pake", "srp6", SRP6_RT_Tests);
+BOTAN_REGISTER_TEST("pake", "srp6_rt", SRP6_RT_Tests);
 
 #endif