crypto: remove slight bias in key generation due to modulo

5 files changed, 77 insertions, 10 deletions

diff --git a/src/crypto/crypto.cpp b/src/crypto/crypto.cpp
index f4ef751d3..9eafa0e28 100644
--- a/src/crypto/crypto.cpp
+++ b/src/crypto/crypto.cpp
@@ -93,6 +93,29 @@ namespace crypto {
     generate_random_bytes_not_thread_safe(N, bytes);
   }
 
+  static inline bool less32(const unsigned char *k0, const unsigned char *k1)
+  {
+    for (int n = 31; n >= 0; --n)
+    {
+      if (k0[n] < k1[n])
+        return true;
+      if (k0[n] > k1[n])
+        return false;
+    }
+    return false;
+  }
+
+  void random32_unbiased(unsigned char *bytes)
+  {
+    // l = 2^252 + 27742317777372353535851937790883648493.
+    // it fits 15 in 32 bytes
+    static const unsigned char limit[32] = { 0xe3, 0x6a, 0x67, 0x72, 0x8b, 0xce, 0x13, 0x29, 0x8f, 0x30, 0x82, 0x8c, 0x0b, 0xa4, 0x10, 0x39, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xf0 };
+    do
+    {
+      generate_random_bytes_thread_safe(32, bytes);
+    } while (!less32(bytes, limit)); // should be good about 15/16 of the time
+    sc_reduce32(bytes);
+  }
   /* generate a random 32-byte (256-bit) integer and copy it to res */
   static inline void random_scalar_not_thread_safe(ec_scalar &res) {
     unsigned char tmp[64];
@@ -101,10 +124,7 @@ namespace crypto {
     memcpy(&res, tmp, 32);
   }
   static inline void random_scalar(ec_scalar &res) {
-    unsigned char tmp[64];
-    generate_random_bytes_thread_safe(64, tmp);
-    sc_reduce(tmp);
-    memcpy(&res, tmp, 32);
+    random32_unbiased((unsigned char*)res.data);
   }
 
   void hash_to_scalar(const void *data, size_t length, ec_scalar &res) {
diff --git a/src/crypto/crypto.h b/src/crypto/crypto.h
index 9ea0f2ec0..449af8f6d 100644
--- a/src/crypto/crypto.h
+++ b/src/crypto/crypto.h
@@ -99,6 +99,7 @@ namespace crypto {
 #pragma pack(pop)
 
   void hash_to_scalar(const void *data, size_t length, ec_scalar &res);
+  void random32_unbiased(unsigned char *bytes);
 
   static_assert(sizeof(ec_point) == 32 && sizeof(ec_scalar) == 32 &&
     sizeof(public_key) == 32 && sizeof(secret_key) == 32 &&
diff --git a/src/ringct/rctOps.cpp b/src/ringct/rctOps.cpp
index 68cc43128..50693bad7 100644
--- a/src/ringct/rctOps.cpp
+++ b/src/ringct/rctOps.cpp
@@ -62,14 +62,13 @@ namespace rct {
 
     //generates a random scalar which can be used as a secret key or mask
     void skGen(key &sk) {
-        sk = crypto::rand<key>();
-        sc_reduce32(sk.bytes);
+        random32_unbiased(sk.bytes);
     }
 
     //generates a random scalar which can be used as a secret key or mask
     key skGen() {
-        key sk = crypto::rand<key>();
-        sc_reduce32(sk.bytes);
+        key sk;
+        skGen(sk);
         return sk;
     }
 
@@ -79,9 +78,8 @@ namespace rct {
         CHECK_AND_ASSERT_THROW_MES(rows > 0, "0 keys requested");
         keyV rv(rows);
         size_t i = 0;
-        crypto::rand(rows * sizeof(key), (uint8_t*)&rv[0]);
         for (i = 0 ; i < rows ; i++) {
-            sc_reduce32(rv[i].bytes);
+            skGen(rv[i]);
         }
         return rv;
     }
diff --git a/tests/unit_tests/CMakeLists.txt b/tests/unit_tests/CMakeLists.txt
index 6d79ba74b..06112d3ee 100644
--- a/tests/unit_tests/CMakeLists.txt
+++ b/tests/unit_tests/CMakeLists.txt
@@ -55,6 +55,7 @@ set(unit_tests_sources
   mul_div.cpp
   multisig.cpp
   parse_amount.cpp
+  random.cpp
   serialization.cpp
   sha256.cpp
   slow_memmem.cpp
diff --git a/tests/unit_tests/random.cpp b/tests/unit_tests/random.cpp
new file mode 100644
index 000000000..7653453cd
--- /dev/null
+++ b/tests/unit_tests/random.cpp
@@ -0,0 +1,47 @@
+// Copyright (c) 2018, The Monero Project
+// 
+// All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without modification, are
+// permitted provided that the following conditions are met:
+// 
+// 1. Redistributions of source code must retain the above copyright notice, this list of
+//    conditions and the following disclaimer.
+// 
+// 2. Redistributions in binary form must reproduce the above copyright notice, this list
+//    of conditions and the following disclaimer in the documentation and/or other
+//    materials provided with the distribution.
+// 
+// 3. Neither the name of the copyright holder nor the names of its contributors may be
+//    used to endorse or promote products derived from this software without specific
+//    prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
+// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#include "gtest/gtest.h"
+
+#include "crypto/crypto.h"
+
+extern "C" {
+#include "crypto/crypto-ops.h"
+}
+
+TEST(random32_unbiased, less_than_order)
+{
+  unsigned char tmp[32], tmp2[32];
+  for (int i = 0; i < 1000; ++i)
+  {
+    crypto::random32_unbiased(tmp);
+    memcpy(tmp2, tmp, 32);
+    sc_reduce32(tmp2);
+    ASSERT_EQ(memcmp(tmp, tmp2, 32), 0);
+  }
+}