Repository: randombit/botan
Pull request #2301 (2020-03-08 12:04:57)

Fix underflow bug in modular inverse
OSS-Fuzz 21115


Patch:
diff --git a/src/fuzzer/invert.cpp b/src/fuzzer/invert.cpp
index b4ef5e616..5d34512f3 100644
--- a/src/fuzzer/invert.cpp
+++ b/src/fuzzer/invert.cpp
@@ -65,16 +65,16 @@ void fuzz(const uint8_t in[], size_t len)
    if(mod < 2)
       return;
 
-   const Botan::BigInt ref = ref_inverse_mod(x, mod);
    const Botan::BigInt lib = Botan::inverse_mod(x, mod);
+   const Botan::BigInt ref = ref_inverse_mod(x, mod);
 
    if(ref != lib)
       {
       FUZZER_WRITE_AND_CRASH("X = " << x << "\n"
-                             << "P = " << mod << "\n"
-                             << "GCD = " << gcd(x, mod) << "\n"
-                             << "Ref = " << ref << "\n"
-                             << "Lib  = " << lib << "\n"
+                             << "Mod = " << mod << "\n"
+                             << "GCD(X,Mod) = " << gcd(x, mod) << "\n"
+                             << "RefInv(X,Mod) = " << ref << "\n"
+                             << "LibInv(X,Mod)  = " << lib << "\n"
                              << "RefCheck = " << (x*ref)%mod << "\n"
                              << "LibCheck  = " << (x*lib)%mod << "\n");
       }
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index fac82defa..96ca92b35 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -455,6 +455,8 @@ void BigInt::binary_decode(const uint8_t buf[], size_t length)
 
 void BigInt::ct_cond_add(bool predicate, const BigInt& value)
    {
+   if(this->is_negative() || value.is_negative())
+      throw Invalid_Argument("BigInt::ct_cond_add requires both values to be positive");
    this->grow_to(1 + value.sig_words());
 
    bigint_cnd_add(static_cast<word>(predicate),
diff --git a/src/lib/math/numbertheory/mod_inv.cpp b/src/lib/math/numbertheory/mod_inv.cpp
index 8bc073d9c..013b5bdc5 100644
--- a/src/lib/math/numbertheory/mod_inv.cpp
+++ b/src/lib/math/numbertheory/mod_inv.cpp
@@ -12,17 +12,6 @@
 
 namespace Botan {
 
-// Deprecated forwarding functions:
-BigInt inverse_euclid(const BigInt& x, const BigInt& modulus)
-   {
-   return inverse_mod(x, modulus);
-   }
-
-BigInt ct_inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod)
-   {
-   return inverse_mod(n, mod);
-   }
-
 /*
 Sets result to a^-1 * 2^k mod a
 with n <= k <= 2n
@@ -199,6 +188,11 @@ BigInt inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod)
    // in which case zero out the result to indicate this
    (~b_is_1).if_set_zero_out(v_w, mod_words);
 
+   /*
+   * We've placed the result in the lowest words of the temp buffer.
+   * So just clear out the other values and then give that buffer to a
+   * BigInt.
+   */
    clear_mem(&tmp_mem[mod_words], 4*mod_words);
 
    CT::unpoison(tmp_mem.data(), tmp_mem.size());
@@ -223,8 +217,12 @@ BigInt inverse_mod_pow2(const BigInt& a1, size_t k)
 
    BigInt b = 1;
    BigInt X = 0;
+   BigInt newb;
 
-   const size_t a_words = 1 + a.sig_words();
+   const size_t a_words = a.sig_words();
+
+   X.grow_to(round_up(k, BOTAN_MP_WORD_BITS) / BOTAN_MP_WORD_BITS);
+   b.grow_to(a_words);
 
    /*
    Hide the exact value of k. k is anyway known to word length
@@ -237,8 +235,8 @@ BigInt inverse_mod_pow2(const BigInt& a1, size_t k)
       {
       const bool b0 = b.get_bit(0);
       X.conditionally_set_bit(i, b0);
-      b.grow_to(a_words);
-      bigint_cnd_sub(b0, b.mutable_data(), b.size(), a.data(), a.sig_words());
+      newb = b - a;
+      b.ct_cond_assign(b0, newb);
       b >>= 1;
       }
 
@@ -288,13 +286,15 @@ BigInt inverse_mod(const BigInt& n, const BigInt& mod)
    */
 
    const BigInt o = mod >> mod_lz;
-   const BigInt inv_o = inverse_mod_odd_modulus(ct_modulo(n, o), o);
+   const BigInt n_redc = ct_modulo(n, o);
+   const BigInt inv_o = inverse_mod_odd_modulus(n_redc, o);
    const BigInt inv_2k = inverse_mod_pow2(n, mod_lz);
 
    // No modular inverse in this case:
    if(inv_o == 0 || inv_2k == 0)
       return 0;
 
+   const BigInt m2k = BigInt::power_of_2(mod_lz);
    // Compute the CRT parameter
    const BigInt c = inverse_mod_pow2(o, mod_lz);
 
@@ -304,7 +304,7 @@ BigInt inverse_mod(const BigInt& n, const BigInt& mod)
    h.set_sign(BigInt::Positive);
    h.mask_bits(mod_lz);
    const bool h_nonzero = h.is_nonzero();
-   h.ct_cond_assign(h_nonzero && h_neg, BigInt::power_of_2(mod_lz) - h);
+   h.ct_cond_assign(h_nonzero && h_neg, m2k - h);
 
    // Return result inv_o + h * o
    h *= o;
@@ -312,6 +312,17 @@ BigInt inverse_mod(const BigInt& n, const BigInt& mod)
    return h;
    }
 
+// Deprecated forwarding functions:
+BigInt inverse_euclid(const BigInt& x, const BigInt& modulus)
+   {
+   return inverse_mod(x, modulus);
+   }
+
+BigInt ct_inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod)
+   {
+   return inverse_mod_odd_modulus(n, mod);
+   }
+
 word monty_inverse(word a)
    {
    if(a % 2 == 0)


Test patch:
diff --git a/src/tests/data/bn/invmod.vec b/src/tests/data/bn/invmod.vec
index 9bcca8ee3..b7f03419a 100644
--- a/src/tests/data/bn/invmod.vec
+++ b/src/tests/data/bn/invmod.vec
@@ -528,3 +528,14 @@ Input = 43000466091
 Modulus = 0x10000000000
 Output  = 140404367363
 
+# OSS-Fuzz 21115
+
+# The originally reported test case
+Input = 3329223706171052463206866408355190852145308853551222855374206553291583641200362811169867167522066732427259441069045458590915570173077273266668323626418910290729833115917608762612451607036836604560196526748133295229482315432160861956985661720415008502817376589122369169168503051700575534361360734357915507005267791266056164843197115173542457409178397682412186017844044878477733706673665949312479502081417286848135607066940796741261651879705761216547813649105594986990007847567220787224253724912309650653332895570458720843322485065681189768697291752149748575893233520856711838140401691494532333502278879425087656782163494363567584633848194784070822245649557468578497368723157561724530746784741768646102936863260630088882545875047173194357829837349405264332156553159
+Modulus = 5159669275902268897019683770634129859849131442089512209466255369748647885295043458100453095139637532489732379349334183998359005271540851438475735390060160055101459757369025094548935216928274885474920588457238932199212826132848112983030207228729230350143070245214615032330098373606816857555487378911597356175295963296209024100980888874174104384926439773409352855895683162800486061893625461339248419592365333197671396390223849652458316548872173632032072142493359961192701645150390051578875246900773560274606831152842526302321197703270752422496079310760804228859682734104661333367088085354635701827808417686374790164642660390557925243983808216928421220094838103017958334974205040660858707963225716195222460679137994123278276584663712976241848458904056941218720227786752
+Output = 1616976508685598612715404615539711729591496303838727278361745768459912744766103110805335531789260471902032668556823877781797119177369744675655036227693862387901335929380526158525335617191171199406261059141492729550964383378755592271377330924178695575317855482198418687207284119472436638891655267287870468947394828003595194476459620373954194618413638984959865778647102302286558592688810633664007264011579909176526804508142200273299822852592676936629738013383103344642638188458260268481981965239756241374381655466503673701310357329513881591759718900992472283603129650577355418728929787837071330285526447596817142247043818915739644061292726006592557005008244120258692943705325131549610392209481948231318177450181776222904306153521050324221361215524333142914455291939319
+
+# The sub-computation which failed
+Input = 65279
+Modulus = 0x100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+Output = 21361914537342414713552871917029943574709104078599594478169627833328205584507146367057038170698710253677755075362127788711957331760388539866898398399344480664991941861081743615