[botan-devel] Exception when doing multithreaded signing

Jack Lloyd lloyd at randombit.net
Tue Jun 7 10:02:33 EDT 2011


On Tue, Jun 07, 2011 at 03:07:03PM +0200, Rickard Bellgrim wrote:
> Hi
> 
> I am randomly (1 of 1000 signatures) hitting an exception in Botan 1.9.18 when pushing the computer to its limits. Using 8 threads and signing data with a 1024-bit RSA key (copied to each thread). The data is first digested with SHA1 outside Botan then signed using a PK_Signer and "EMSA3(Raw)". Calling the sign_message function with an RNG that is unique for each thread. The problem does not appear in 1.8.11.
> 
> Internal error: Assertion self_test_signature(encoded, plain_sig) failed (PK_Signer consistency check failed) in Botan::SecureVector<unsigned char> Botan::PK_Signer::signature(Botan::RandomNumberGenerator&) @src/pubkey/pubkey.cpp:218
> 
> Any thoughts on what the problem could be?

Based on your bisecting it to 1.9.11, my first guess is the change to
Montgomery reduction to avoid branching in that release. Likely I've
messed up a corner case. I've attached a patch for 1.9.18 that reverts the
algorithm back to the one used in 1.9.10 - does it make a difference?

I'm wondering as well if the threading is the underlying issue....
perhaps there is a new race I introduced at some point. Does this show
up if you do the same test with only 1 or 2 threads running?

I'm a bit suspcious it's a thread issue, tbh, because I turned on
fault protection checking on the benchmarks and ran them. ~400K
signatures later, no failures.

Can you send me a copy of the source? Offlist is fine.

-Jack
-------------- next part --------------
#
# old_revision [d71da9305f933a6bded46983de89deef25950983]
#
# patch "src/math/mp/mp_monty.cpp"
#  from [abde647444457cbec4f0e61790172c02c2b2e134]
#    to [9d827c9187a9943ef4feb0341e539662f95d4d72]
#
============================================================
--- src/math/mp/mp_monty.cpp	abde647444457cbec4f0e61790172c02c2b2e134
+++ src/math/mp/mp_monty.cpp	9d827c9187a9943ef4feb0341e539662f95d4d72
@@ -19,51 +19,71 @@ void bigint_monty_redc(word z[], size_t 
 * Montgomery Reduction Algorithm
 */
 void bigint_monty_redc(word z[], size_t z_size,
-                       const word p[], size_t p_size,
-                       word p_dash, word ws[])
+                       const word x[], size_t x_size,
+                       word u, word [])
    {
-   const size_t blocks_of_8 = p_size - (p_size % 8);
+   const size_t blocks_of_8 = x_size - (x_size % 8);
 
-   for(size_t i = 0; i != p_size; ++i)
+   for(u32bit i = 0; i != x_size; ++i)
       {
       word* z_i = z + i;
 
-      const word y = z_i[0] * p_dash;
+      const word y = z_i[0] * u;
 
-      /*
-      bigint_linmul3(ws, p, p_size, y);
-      bigint_add2(z_i, z_size - i, ws, p_size+1);
-      */
-
       word carry = 0;
 
       for(size_t j = 0; j != blocks_of_8; j += 8)
-         carry = word8_madd3(z_i + j, p + j, y, carry);
+         carry = word8_madd3(z_i + j, x + j, y, carry);
 
-      for(size_t j = blocks_of_8; j != p_size; ++j)
-         z_i[j] = word_madd3(p[j], y, z_i[j], &carry);
+      for(u32bit j = blocks_of_8; j != x_size; ++j)
+         z_i[j] = word_madd3(x[j], y, z_i[j], &carry);
 
-      word z_sum = z_i[p_size] + carry;
-      carry = (z_sum < z_i[p_size]);
-      z_i[p_size] = z_sum;
+      word z_sum = z_i[x_size] + carry;
+      carry = (z_sum < z_i[x_size]);
+      z_i[x_size] = z_sum;
 
-      for(size_t j = p_size + 1; carry && j != z_size - i; ++j)
+      for(u32bit j = x_size + 1; carry && j != z_size - i; ++j)
          {
          ++z_i[j];
          carry = !z_i[j];
          }
       }
 
-   word borrow = 0;
-   for(size_t i = 0; i != p_size; ++i)
-      ws[i] = word_sub(z[p_size + i], p[i], &borrow);
+   // Check if z[x_size...x_size+1] >= x[0...x_size] using bigint_cmp (inlined)
+   if(!z[x_size + x_size])
+      {
+      for(u32bit i = x_size; i > 0; --i)
+         {
+         if(z[x_size + i - 1] > x[i-1])
+            break;
 
-   ws[p_size] = word_sub(z[p_size+p_size], 0, &borrow);
+         if(z[x_size + i - 1] < x[i-1])
+            {
+            for(size_t i = 0; i != x_size + 1; ++i)
+               z[i] = z[x_size+i];
+            for(size_t i = x_size+1; i != x_size + x_size; ++i)
+               z[i] = 0;
+            return;
+            }
+         }
+      }
 
-   copy_mem(ws + p_size + 1, z + p_size, p_size + 1);
+   // If the compare above is true, subtract using bigint_sub2 (inlined)
+   word carry = 0;
 
-   copy_mem(z, ws + borrow*(p_size+1), p_size + 1);
-   clear_mem(z + p_size + 1, z_size - p_size - 1);
+   for(u32bit i = 0; i != blocks_of_8; i += 8)
+      carry = word8_sub2(z + x_size + i, x + i, carry);
+
+   for(u32bit i = blocks_of_8; i != x_size; ++i)
+      z[x_size + i] = word_sub(z[x_size + i], x[i], &carry);
+
+   if(carry)
+      --z[x_size+x_size];
+
+   for(size_t i = 0; i != x_size + 1; ++i)
+     z[i] = z[x_size+i];
+   for(size_t i = x_size+1; i != x_size + x_size; ++i)
+     z[i] = 0;
    }
 
 void bigint_monty_mul(word z[], size_t z_size,


More information about the botan-devel mailing list