From f02c07ea99509531d815eb7ab18076365924f13f Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Sat, 24 Oct 2015 09:35:34 -0400 Subject: Make Montgomery reduction constant time. It was already close, but the carry loop would break early and selecting which value to copy out was indexed on the borrow bit. Have the carry loop run through, and add a const-time conditional copy operation and use that to copy the output. Convert ct_utils to CT namespace. Templatize the utils, which I was hesitant to do initially but is pretty useful when dealing with arbitrary word sizes. Remove the poison macros, replace with inline funcs which reads cleaner at the call site. --- src/lib/math/mp/mp_monty.cpp | 23 +++++++++++++++++------ 1 file changed, 17 insertions(+), 6 deletions(-) (limited to 'src/lib/math/mp/mp_monty.cpp') diff --git a/src/lib/math/mp/mp_monty.cpp b/src/lib/math/mp/mp_monty.cpp index 820f41e6c..7e427b540 100644 --- a/src/lib/math/mp/mp_monty.cpp +++ b/src/lib/math/mp/mp_monty.cpp @@ -9,6 +9,7 @@ #include #include #include +#include #include namespace Botan { @@ -22,6 +23,10 @@ void bigint_monty_redc(word z[], { const size_t z_size = 2*(p_size+1); + CT::poison(z, z_size); + CT::poison(p, p_size); + CT::poison(ws, 2*(p_size+1)); + const size_t blocks_of_8 = p_size - (p_size % 8); for(size_t i = 0; i != p_size; ++i) @@ -47,10 +52,10 @@ void bigint_monty_redc(word z[], carry = (z_sum < z_i[p_size]); z_i[p_size] = z_sum; - for(size_t j = p_size + 1; carry && j != z_size - i; ++j) + for(size_t j = p_size + 1; j < z_size - i; ++j) { - ++z_i[j]; - carry = !z_i[j]; + z_i[j] += carry; + carry = carry & !z_i[j]; } } @@ -73,12 +78,18 @@ void bigint_monty_redc(word z[], ws[p_size] = word_sub(z[p_size+p_size], 0, &borrow); - BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow"); - copy_mem(ws + p_size + 1, z + p_size, p_size + 1); - copy_mem(z, ws + borrow*(p_size+1), p_size + 1); + CT::conditional_copy_mem(borrow, z, ws + (p_size + 1), ws, (p_size + 1)); clear_mem(z + p_size + 1, z_size - p_size - 1); + + CT::unpoison(z, z_size); + CT::unpoison(p, p_size); + CT::unpoison(ws, 2*(p_size+1)); + + // This check comes after we've used it but that's ok here + CT::unpoison(&borrow, 1); + BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow"); } void bigint_monty_mul(word z[], size_t z_size, -- cgit v1.2.3