1 2 #include <stddef.h> 3 #include <stdint.h> 4 5 #include "../scalarmult_curve25519.h" 6 #include "export.h" 7 #include "private/ed25519_ref10.h" 8 #include "utils.h" 9 #include "x25519_ref10.h" 10 11 /* 12 * Reject small order points early to mitigate the implications of 13 * unexpected optimizations that would affect the ref10 code. 14 * See https://eprint.iacr.org/2017/806.pdf for reference. 15 */ 16 static int 17 has_small_order(const unsigned char s[32]) 18 { 19 CRYPTO_ALIGN(16) 20 static const unsigned char blacklist[][32] = { 21 { 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 }, 22 { 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 }, 23 { 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 }, 24 { 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 }, 25 { 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 }, 26 { 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 }, 27 { 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 }, 28 { 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 }, 29 { 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 }, 30 { 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 }, 31 { 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 }, 32 { 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 } 33 }; 34 unsigned char c[12] = { 0 }; 35 unsigned int k; 36 size_t i, j; 37 38 COMPILER_ASSERT(12 == sizeof blacklist / sizeof blacklist[0]); 39 for (j = 0; j < 32; j++) { 40 for (i = 0; i < sizeof blacklist / sizeof blacklist[0]; i++) { 41 c[i] |= s[j] ^ blacklist[i][j]; 42 } 43 } 44 k = 0; 45 for (i = 0; i < sizeof blacklist / sizeof blacklist[0]; i++) { 46 k |= (c[i] - 1); 47 } 48 return (int) ((k >> 8) & 1); 49 } 50 51 static int 52 crypto_scalarmult_curve25519_ref10(unsigned char *q, 53 const unsigned char *n, 54 const unsigned char *p) 55 { 56 unsigned char *t = q; 57 unsigned int i; 58 fe25519 x1; 59 fe25519 x2; 60 fe25519 z2; 61 fe25519 x3; 62 fe25519 z3; 63 fe25519 tmp0; 64 fe25519 tmp1; 65 int pos; 66 unsigned int swap; 67 unsigned int b; 68 69 if (has_small_order(p)) { 70 return -1; 71 } 72 for (i = 0; i < 32; i++) { 73 t[i] = n[i]; 74 } 75 t[0] &= 248; 76 t[31] &= 127; 77 t[31] |= 64; 78 fe25519_frombytes(x1, p); 79 fe25519_1(x2); 80 fe25519_0(z2); 81 fe25519_copy(x3, x1); 82 fe25519_1(z3); 83 84 swap = 0; 85 for (pos = 254; pos >= 0; --pos) { 86 b = t[pos / 8] >> (pos & 7); 87 b &= 1; 88 swap ^= b; 89 fe25519_cswap(x2, x3, swap); 90 fe25519_cswap(z2, z3, swap); 91 swap = b; 92 fe25519_sub(tmp0, x3, z3); 93 fe25519_sub(tmp1, x2, z2); 94 fe25519_add(x2, x2, z2); 95 fe25519_add(z2, x3, z3); 96 fe25519_mul(z3, tmp0, x2); 97 fe25519_mul(z2, z2, tmp1); 98 fe25519_sq(tmp0, tmp1); 99 fe25519_sq(tmp1, x2); 100 fe25519_add(x3, z3, z2); 101 fe25519_sub(z2, z3, z2); 102 fe25519_mul(x2, tmp1, tmp0); 103 fe25519_sub(tmp1, tmp1, tmp0); 104 fe25519_sq(z2, z2); 105 fe25519_scalar_product(z3, tmp1, 121666); 106 fe25519_sq(x3, x3); 107 fe25519_add(tmp0, tmp0, z3); 108 fe25519_mul(z3, x1, z2); 109 fe25519_mul(z2, tmp1, tmp0); 110 } 111 fe25519_cswap(x2, x3, swap); 112 fe25519_cswap(z2, z3, swap); 113 114 fe25519_invert(z2, z2); 115 fe25519_mul(x2, x2, z2); 116 fe25519_tobytes(q, x2); 117 118 return 0; 119 } 120 121 static void 122 edwards_to_montgomery(fe25519 montgomeryX, const fe25519 edwardsY, const fe25519 edwardsZ) 123 { 124 fe25519 tempX; 125 fe25519 tempZ; 126 127 fe25519_add(tempX, edwardsZ, edwardsY); 128 fe25519_sub(tempZ, edwardsZ, edwardsY); 129 fe25519_invert(tempZ, tempZ); 130 fe25519_mul(montgomeryX, tempX, tempZ); 131 } 132 133 static int 134 crypto_scalarmult_curve25519_ref10_base(unsigned char *q, 135 const unsigned char *n) 136 { 137 unsigned char *t = q; 138 ge25519_p3 A; 139 fe25519 pk; 140 unsigned int i; 141 142 for (i = 0; i < 32; i++) { 143 t[i] = n[i]; 144 } 145 t[0] &= 248; 146 t[31] &= 127; 147 t[31] |= 64; 148 ge25519_scalarmult_base(&A, t); 149 edwards_to_montgomery(pk, A.Y, A.Z); 150 fe25519_tobytes(q, pk); 151 152 return 0; 153 } 154 155 struct crypto_scalarmult_curve25519_implementation 156 crypto_scalarmult_curve25519_ref10_implementation = { 157 SODIUM_C99(.mult =) crypto_scalarmult_curve25519_ref10, 158 SODIUM_C99(.mult_base =) crypto_scalarmult_curve25519_ref10_base 159 }; 160