From 1670af4bdf6b5139fa218377fa8761e2c4ea0e4a Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Sun, 2 Dec 2018 18:16:40 -0500 Subject: Add a constant time divide variant for dividing by uint8_t Originally wrote it for div-by-word but that ends up requiring a dword type which we don't always have. And uint8_t covers the most important cases of n = 10 and n = 58 (whenever I get around to writing base58). We could portably support up to div-by-uint32, but I don't think we need it. Nicely for n = 10, this is actually faster than the variable time division. --- src/fuzzer/divide.cpp | 27 ++++++++++++++++++++++----- 1 file changed, 22 insertions(+), 5 deletions(-) (limited to 'src/fuzzer') diff --git a/src/fuzzer/divide.cpp b/src/fuzzer/divide.cpp index c0c86f051..b6342ff7d 100644 --- a/src/fuzzer/divide.cpp +++ b/src/fuzzer/divide.cpp @@ -11,25 +11,42 @@ void fuzz(const uint8_t in[], size_t len) if(len % 2 == 1 || len > 2*4096/8) return; - const Botan::BigInt x = Botan::BigInt::decode(in, len / 2); - const Botan::BigInt y = Botan::BigInt::decode(in + len / 2, len / 2); + // Save on allocations by making these static + static Botan::BigInt x, y, q, r, ct_q, ct_r, z; + + x = Botan::BigInt::decode(in, len / 2); + y = Botan::BigInt::decode(in + len / 2, len / 2); if(y == 0) return; - Botan::BigInt q, r; Botan::divide(x, y, q, r); FUZZER_ASSERT_TRUE(r < y); - Botan::BigInt z = q*y + r; + z = q*y + r; FUZZER_ASSERT_EQUAL(z, x); - Botan::BigInt ct_q, ct_r; Botan::ct_divide(x, y, ct_q, ct_r); FUZZER_ASSERT_EQUAL(q, ct_q); FUZZER_ASSERT_EQUAL(r, ct_r); + + // Now divide by just low byte of y + + y = y.byte_at(0); + if(y == 0) + y = 251; + Botan::divide(x, y, q, r); + + z = q*y + r; + FUZZER_ASSERT_EQUAL(z, x); + + uint8_t r8; + Botan::ct_divide_u8(x, y.byte_at(0), ct_q, r8); + FUZZER_ASSERT_EQUAL(ct_q, q); + FUZZER_ASSERT_EQUAL(r8, r.byte_at(0)); + } -- cgit v1.2.3