Merge GH #1502 Fix (EC)DSA when using hashes longer than group order

9 files changed, 165 insertions, 6 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 694c7afab..fd967e66e 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -93,6 +93,18 @@ BigInt::BigInt(const uint8_t input[], size_t length, Base base)
    *this = decode(input, length, base);
    }
 
+BigInt::BigInt(const uint8_t buf[], size_t length, size_t max_bits)
+   {
+   const size_t max_bytes = std::min(length, (max_bits + 7) / 8);
+   *this = decode(buf, max_bytes);
+
+   const size_t b = this->bits();
+   if(b > max_bits)
+      {
+      *this >>= (b - max_bits);
+      }
+   }
+
 /*
 * Construct a BigInt from an encoded BigInt
 */
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 56b907d80..3d6626e4d 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -86,6 +86,15 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      BigInt(const uint8_t buf[], size_t length, Base base);
 
      /**
+     * Create a BigInt from an integer in a byte array
+     * @param buf the byte array holding the value
+     * @param length size of buf
+     * @param max_bits if the resulting integer is more than max_bits,
+     *        it will be shifted so it is at most max_bits in length.
+     */
+     BigInt(const uint8_t buf[], size_t length, size_t max_bits);
+
+     /**
      * Create a BigInt from an array of words
      * @param words the words
      * @param length number of words
diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index 9249cd0d5..982e1b931 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -105,7 +105,7 @@ DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
    {
    const BigInt& q = m_group.get_q();
 
-   BigInt i(msg, msg_len);
+   BigInt i(msg, msg_len, q.bits());
 
    while(i >= q)
       i -= q;
@@ -167,7 +167,7 @@ bool DSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
 
    BigInt r(sig, q_bytes);
    BigInt s(sig + q_bytes, q_bytes);
-   BigInt i(msg, msg_len);
+   BigInt i(msg, msg_len, q.bits());
 
    if(r <= 0 || r >= q || s <= 0 || s >= q)
       return false;
diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index 6ff02e8c9..f35693189 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -81,7 +81,7 @@ secure_vector<uint8_t>
 ECDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
                                     RandomNumberGenerator& rng)
    {
-   const BigInt m(msg, msg_len);
+   BigInt m(msg, msg_len, m_group.get_order_bits());
 
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
    const BigInt k = generate_rfc6979_nonce(m_x, m_group.get_order(), m, m_rfc6979_hash);
@@ -134,7 +134,7 @@ bool ECDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
    if(sig_len != m_group.get_order_bytes() * 2)
       return false;
 
-   const BigInt e(msg, msg_len);
+   const BigInt e(msg, msg_len, m_group.get_order_bits());
 
    const BigInt r(sig, sig_len / 2);
    const BigInt s(sig + sig_len / 2, sig_len / 2);
diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.cpp b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
index db790b0d1..12962d18c 100644
--- a/src/lib/pubkey/ecgdsa/ecgdsa.cpp
+++ b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
@@ -57,7 +57,7 @@ secure_vector<uint8_t>
 ECGDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
                                      RandomNumberGenerator& rng)
    {
-   const BigInt m(msg, msg_len);
+   const BigInt m(msg, msg_len, m_group.get_order_bits());
 
    BigInt k = BigInt::random_integer(rng, 1, m_group.get_order());
 
@@ -107,7 +107,7 @@ bool ECGDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
    if(sig_len != m_group.get_order_bytes() * 2)
       return false;
 
-   const BigInt e(msg, msg_len);
+   const BigInt e(msg, msg_len, m_group.get_order_bits());
 
    const BigInt r(sig, sig_len / 2);
    const BigInt s(sig + sig_len / 2, sig_len / 2);
diff --git a/src/tests/data/pubkey/dsa_verify.vec b/src/tests/data/pubkey/dsa_verify.vec
new file mode 100644
index 000000000..6bf24f20d
--- /dev/null
+++ b/src/tests/data/pubkey/dsa_verify.vec
@@ -0,0 +1,16 @@
+
+# Generated by OpenSSL
+
+P = 0xE6793D8A212FE151FE077D76183388C201521FFFF76B966AEBA9F7FC94ADEEF752933897ED8E599C94C705AFD111BA33B36329FDC5090E918F28C59BA06943492A1381DE0A4D90603DFE705B6A89D6099CDD2E9581E82BF34957EB048C178E2468DF8B443E58081FE04B78DD2AB98E2BD939F3EC348D612D9622F6B8D9CD0C5F
+Q = 0xF8AF4EF46D9A0881BD01C70F969870B05580F499
+G = 0x9427DC62CBF9461FBF58D415D9A33974A15AA30114D93A54D5E06BEE6C34AF19D2E70FA763CA0A361B6F4F47A0E8773FF2624AC6D973A316ECC10DE18218AD7BBFFECBAF01A4840D40D42B59F6BDB5E722127597B24B495E93BC7E500497FDBC17319A8C8DBBFA711FA0898BCCAB3F83C3BCFCBDE5E18C23B9573D3DD24BFDB5
+Y = 0xCEA7C9120EB8D8BC17CBE015CAD32FC349140C7018AF2445C6686BBBB2E57205FE7412A40E196D57CF5AC924855AD25B79C6140CFE2DECE79B907C37CF9A74EAEF9597B73D55655B30843B9025C2EDD1531C11480971DD55B7462A23DE611CE0BE7A3FE82FD4B0C65FAA4445B894212406AC608ED05AD2B3C2986EFA1B8CD580
+Msg = FFFDFBF9F7F5F3F1EFEDEBE9E7E5E3E1DFDDDBD9
+Signature = 3DB343DC58ACDEBF815F85D0E55FBDEDA326BEA6107F10F3A2CB1FBFAFB3324B3FC6076FE298AC9E
+
+P = 0xB7F3ECDFCF8C3DB00C4F007CB59F7CA7B0083671D09D1CCAD7ACAACF0A5D6881AABA9686EEB879C5E8480441EBBFBCBAB4E0F4829C43938E06E954F988284187
+Q = 0xE10EC91ADBF217B6D7B3677ABB266A1E6D85CA17
+G = 0x24CC4D8AD70AE84ACD19181943C9EAB408CC9153E426F55CCCF6037A93E1B2B2A3BDE0516A1AF3186404D43C029374430AA4FE46520509904115A293E5A5193E
+Y = 0x259476F6FDC576ECDA5BDE2D4441030E52BC77F0121F74BDDD91EB4749D0E77DB34C249742DFCF80D097360BA19BB5801B1B6C83636E8B4B9AA8BF93FAAA53EF
+Msg = FFFDFBF9F7F5F3F1EFEDEBE9E7E5E3E1DFDDDBD9
+Signature = BA031AB679E9A96EA5D929C609C861702E658D0DD8247C0EF439DF3DF8126F0122F0D5AD6796E014
diff --git a/src/tests/data/pubkey/ecdsa_verify.vec b/src/tests/data/pubkey/ecdsa_verify.vec
new file mode 100644
index 000000000..2bdf3299b
--- /dev/null
+++ b/src/tests/data/pubkey/ecdsa_verify.vec
@@ -0,0 +1,56 @@
+
+# These were generated with OpenSSL
+
+Group = secp256k1
+Px = 0xF3F8BB913AA68589A2C8C607A877AB05252ADBD963E1BE846DDEB8456942AEDC
+Py = 0xA2ED51F08CA3EF3DAC0A7504613D54CD539FC1B3CBC92453CD704B6A2D012B2C
+Msg = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+Signature = E30F2E6A0F705F4FB5F8501BA79C7C0D3FAC847F1AD70B873E9797B17B89B39081F1A4457589F30D76AB9F89E748A68C8A94C30FE0BAC8FB5C0B54EA70BF6D2F
+
+Group = secp256r1
+Px = 0x89F5662F5D9DE780184E3A2E1D170D6D30FF28F03E030C9CA99F3DB670E5DBB8
+Py = 0xEDDB57C7ACA9711D3CF67A2699792F76EE15A8129449D8A450D371CEFF2E00C7
+Msg = 3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E
+Signature = 2AC979EB6C7502A49CACC0995A2B9C50192F334B742573767ADD6DCB01343D50F444D29AFCA529A0A96467DAA5E881B1C60C73273E099DF7C910BD4EED0502D6
+
+Group = secp256r1
+Px = 0x927EC4F595E5F7CE4F7F5DBB981C5FB23F40513B20FBC6B64896EBE8987AEF99
+Py = 0xD0D24752AB3E2204AB45A29D3FC9A57C5C880206EC5B62E6BD452F783D58882D
+Msg = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+Signature = 04EB3913B651D9862E06B606B3525E4813AAA4AF9E8D0BBE187CE8F460F53A60082442D68B83398B45FFBBB4B633EB241C1BF03D1D81768222C2FB9C3617CA0C
+
+Group = secp256r1
+Px = 0xE3E8AA2F7E352ABADC60710055BB5F21FB3CF0BE4C7492F6A31FE9BBCD4C416F
+Py = 0x7FBF10AFF223B58A967A02D88BDAB88E8605811A382966917F97D58B13987E08
+Msg = FFFEFDFCFBFAF9F8F7F6F5F4F3F2F1F0EFEEEDECEBEAE9E8E7E6E5E4E3E2E1E0DFDEDDDCDBDAD9D8
+Signature = B3E288B55C8FD2450CB5F610349C2B00B67BE086483DED5AF18CB78961EA68A78876C2E4BAAD502DDEE54557F32C3DCFB4EE7A808190B407ACA8506551D71713
+
+Group = secp256r1
+Px = 0x317AD241D0B8A1E3E60D72AE1C939E9BEFABA6863C6E654A4228ACEACB282BE7
+Py = 0x67F9E2B18D669E8C7E7FAD633E23328F542FE27BF18A2B060AF133ECE0658A00
+Msg = 80FEFDFCFBFAF9F8F7F6F5F4F3F2F1F0EFEEEDECEBEAE9E8E7E6E5E4E3E2E1E0DFDEDDDCDBDAD9D8
+Signature = FAD3B78EBBCB9BA3A2C0B7A7BBDA87A808E06F274741C00E0CF912FF7D82803190C858FCD9E1F018D51B8C6BAA37F490B2368C89BBD72CE06E9EAA24F428DD43
+
+Group = secp256r1
+Px = 0x2F1FAAAC824241DD8B3EDEBB9A2E9CA3021A982D1420A2AE72BA77600BF112FF
+Py = 0xC1A501E6D6292F0623619F535A3B9AD3EA3755B5FC7403C296E8773EB712A907
+Msg = 40FEFDFCFBFAF9F8F7F6F5F4F3F2F1F0EFEEEDECEBEAE9E8E7E6E5E4E3E2E1E0DFDEDDDCDBDAD9D8
+Signature = C9912615CC72B56FBC7BABB148F19B1EA7B250825D0CF7C0CAD1236097640F4FA7C010DA8E3650DD122F7C3A06C71615E457C9F43634269C2A2F4844B3B420AC
+
+Group = secp256r1
+Px = 0x91F04AEE0048A1C4D4EEF4F37AE0154CC96A902BDBADE7268BC6D038F1D4B7B8
+Py = 0xE62928361EE169531D90390355DF7DFAFA63428C28F7CBB22FA9A59FD9A4793C
+Msg = 01FEFDFCFBFAF9F8F7F6F5F4F3F2F1F0EFEEEDECEBEAE9E8E7E6E5E4E3E2E1E0DFDEDDDCDBDAD9D8
+Signature = A8816FA8E2F0C8289F58A6CE2E88CDE0E215E53D98A3B04278E696A5696A568AAB06D266C25347810EC5116AB6D5122A1723B1F3612432316C381E15AB69BC1B
+
+Group = secp256r1
+Px = 0x3C21E4A41B2ED5652E438A84D321B744FF916EE23DC0B0044D11688D84D23C5A
+Py = 0xEE3EBD4F6D35DDA2967B481B94548DB7A5EFF82B8CC0B41F4DA3CD0346F11D0
+Msg = 02FEFDFCFBFAF9F8F7F6F5F4F3F2F1F0EFEEEDECEBEAE9E8E7E6E5E4E3E2E1E0DFDEDDDCDBDAD9D8
+Signature = 459F4445D7649A60586E7D49EACA681D1473FD41FBAF7C44583EEE9408E267E19C5E01B7729175F378DF3F9753B4EC6B9277FEC08A2D039B0CF369C61D9FD9C3
+
+Group = secp256r1
+Px = 0x6564C83962A17949120C5E0E65290527A02CC7B635A829B33C083A09AAF67A12
+Py = 0xBFECD7CD5956512DF2A051356B2DF592D93C739128828405E1F37F84B7E27CF9
+Msg = 04FEFDFCFBFAF9F8F7F6F5F4F3F2F1F0EFEEEDECEBEAE9E8E7E6E5E4E3E2E1E0DFDEDDDCDBDAD9D8
+Signature = 264A27F175848F0A110B2E7B03886B94777FB5ECBE2E8CD674AE196A6C80D8FFC8B5C6C00EACB1C76A3BAD03F8FFD4B58784BF35E104E721FF8F3F81AC9E6E91
diff --git a/src/tests/test_dsa.cpp b/src/tests/test_dsa.cpp
index b76c78a58..c0b2508c0 100644
--- a/src/tests/test_dsa.cpp
+++ b/src/tests/test_dsa.cpp
@@ -55,6 +55,38 @@ class DSA_KAT_Tests final : public PK_Signature_Generation_Test
          }
    };
 
+class DSA_Verification_Tests final : public PK_Signature_Verification_Test
+   {
+   public:
+      DSA_Verification_Tests() : PK_Signature_Verification_Test(
+            "DSA",
+            "pubkey/dsa_verify.vec",
+            "P,Q,G,Y,Msg,Signature") {}
+
+      bool clear_between_callbacks() const override
+         {
+         return false;
+         }
+
+      std::unique_ptr<Botan::Public_Key> load_public_key(const VarMap& vars) override
+         {
+         const Botan::BigInt p = get_req_bn(vars, "P");
+         const Botan::BigInt q = get_req_bn(vars, "Q");
+         const Botan::BigInt g = get_req_bn(vars, "G");
+         const Botan::BigInt y = get_req_bn(vars, "Y");
+
+         const Botan::DL_Group grp(p, q, g);
+
+         std::unique_ptr<Botan::Public_Key> key(new Botan::DSA_PublicKey(grp, y));
+         return key;
+         }
+
+      std::string default_padding(const VarMap&) const override
+         {
+         return "Raw";
+         }
+   };
+
 class DSA_Keygen_Tests final : public PK_Key_Generation_Test
    {
    public:
@@ -69,6 +101,7 @@ class DSA_Keygen_Tests final : public PK_Key_Generation_Test
    };
 
 BOTAN_REGISTER_TEST("dsa_sign", DSA_KAT_Tests);
+BOTAN_REGISTER_TEST("dsa_verify", DSA_Verification_Tests);
 BOTAN_REGISTER_TEST("dsa_keygen", DSA_Keygen_Tests);
 
 #endif
diff --git a/src/tests/test_ecdsa.cpp b/src/tests/test_ecdsa.cpp
index 2105250cb..331a1dcaf 100644
--- a/src/tests/test_ecdsa.cpp
+++ b/src/tests/test_ecdsa.cpp
@@ -21,6 +21,38 @@ namespace {
 
 #if defined(BOTAN_HAS_ECDSA)
 
+class ECDSA_Verification_Tests final : public PK_Signature_Verification_Test
+   {
+   public:
+      ECDSA_Verification_Tests() : PK_Signature_Verification_Test(
+            "ECDSA",
+            "pubkey/ecdsa_verify.vec",
+            "Group,Px,Py,Hash,Msg,Signature") {}
+
+      bool clear_between_callbacks() const override
+         {
+         return false;
+         }
+
+      std::unique_ptr<Botan::Public_Key> load_public_key(const VarMap& vars) override
+         {
+         const std::string group_id = get_req_str(vars, "Group");
+         const BigInt px = get_req_bn(vars, "Px");
+         const BigInt py = get_req_bn(vars, "Py");
+         Botan::EC_Group group(Botan::OIDS::lookup(group_id));
+
+         const Botan::PointGFp public_point = group.point(px, py);
+
+         std::unique_ptr<Botan::Public_Key> key(new Botan::ECDSA_PublicKey(group, public_point));
+         return key;
+         }
+
+      std::string default_padding(const VarMap&) const override
+         {
+         return "Raw";
+         }
+   };
+
 class ECDSA_Signature_KAT_Tests final : public PK_Signature_Generation_Test
    {
    public:
@@ -121,6 +153,7 @@ class ECDSA_Invalid_Key_Tests final : public Text_Based_Test
          }
    };
 
+BOTAN_REGISTER_TEST("ecdsa_verify", ECDSA_Verification_Tests);
 BOTAN_REGISTER_TEST("ecdsa_sign", ECDSA_Signature_KAT_Tests);
 BOTAN_REGISTER_TEST("ecdsa_keygen", ECDSA_Keygen_Tests);
 BOTAN_REGISTER_TEST("ecdsa_invalid", ECDSA_Invalid_Key_Tests);