Cut-in x25519 weak points and validation

1 files changed, 57 insertions, 3 deletions

diff --git a/xed25519.cpp b/xed25519.cpp
index fcab71d0..b97182e4 100644
--- a/xed25519.cpp
+++ b/xed25519.cpp
@@ -12,6 +12,59 @@
 #include "xed25519.h"

 #include "donna.h"

 

+ANONYMOUS_NAMESPACE_BEGIN

+

+using CryptoPP::byte;

+

+// See the comments for the code in tweetnacl.cpp

+int is_small_order(const byte s[32])

+{

+  CRYPTOPP_ALIGN_DATA(16)

+  const byte blacklist[][32] = {

+    { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },

+    { 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },

+    { 0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae, 0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a,

+      0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd, 0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00 },

+    { 0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24, 0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b,

+      0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86, 0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57 },

+    { 0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

+      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f },

+    { 0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

+      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f },

+    { 0xee, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

+      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f },

+    { 0xcd, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae, 0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a,

+      0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd, 0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x80 },

+    { 0x4c, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24, 0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b,

+      0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86, 0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0xd7 },

+    { 0xd9, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

+      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff },

+    { 0xda, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

+      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff },

+    { 0xdb, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

+      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff }

+  };

+

+  // The magic 12 is the count of blaklisted points

+  byte c[12] = { 0 };

+  for (size_t j = 0; j < 32; j++) {

+    for (size_t i = 0; i < COUNTOF(blacklist); i++) {

+      c[i] |= s[j] ^ blacklist[i][j];

+    }

+  }

+

+  unsigned int k = 0;

+  for (size_t i = 0; i < COUNTOF(blacklist); i++) {

+    k |= (c[i] - 1);

+  }

+

+  return (int) ((k >> 8) & 1);

+}

+

+ANONYMOUS_NAMESPACE_END

+

 NAMESPACE_BEGIN(CryptoPP)

 

 x25519::x25519(const byte y[32], const byte x[32])

@@ -87,9 +140,10 @@ void x25519::DEREncode(BufferedTransformation &params) const
 bool x25519::Validate(RandomNumberGenerator &rng, unsigned int level) const

 {

     CRYPTOPP_UNUSED(rng);

-    CRYPTOPP_UNUSED(level);

 

-    // TODO: add weak keys test

+    if (level >= 2 && is_small_order(m_pk) != 0)

+        return false;

+

     return true;

 }

 

@@ -147,7 +201,7 @@ bool x25519::Agree(byte *agreedValue, const byte *privateKey, const byte *otherP
     CRYPTOPP_ASSERT(agreedValue != NULLPTR);

     CRYPTOPP_ASSERT(otherPublicKey != NULLPTR);

 

-    if (validateOtherPublicKey && Validate(NullRNG(), 3) == false)

+    if (validateOtherPublicKey && is_small_order(otherPublicKey) != 0)

         return false;

 

     return Donna::curve25519(agreedValue, privateKey, otherPublicKey) == 0;