ed25519_tor.c 9.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367
  1. /*
  2. Public domain by Andrew M. <liquidsun@gmail.com>
  3. Ed25519 reference implementation using Ed25519-donna
  4. */
  5. /*
  6. Tor specific notes:
  7. This file is used by Tor instead of `ed25519.c` as the number of
  8. changes/additions is non-trivial.
  9. Tor modifications to `ed25519.c`:
  10. * 'Tab` -> ' '.
  11. * Include `ed25519_donna_tor.h` instead of `ed25519.h`.
  12. * The external interface has been reworked to match that provided
  13. by Tor's copy of the SUPERCOP `ref10` code.
  14. * The secret (aka private) key is now stored/used in expanded form.
  15. * The internal math tests from `test-internals.c` have been wrapped
  16. in a function and the entire file is included to allow for
  17. runtime validation.
  18. */
  19. /* define ED25519_SUFFIX to have it appended to the end of each public function */
  20. #if !defined(ED25519_SUFFIX)
  21. #define ED25519_SUFFIX
  22. #endif
  23. #define ED25519_FN3(fn,suffix) fn##suffix
  24. #define ED25519_FN2(fn,suffix) ED25519_FN3(fn,suffix)
  25. #define ED25519_FN(fn) ED25519_FN2(fn,ED25519_SUFFIX)
  26. #include "orconfig.h"
  27. #include "ed25519-donna.h"
  28. #include "ed25519_donna_tor.h"
  29. #include "ed25519-randombytes.h"
  30. #include "ed25519-hash.h"
  31. typedef unsigned char ed25519_signature[64];
  32. typedef unsigned char ed25519_public_key[32];
  33. typedef unsigned char ed25519_secret_key[32];
  34. static void ed25519_donna_gettweak(unsigned char *out,
  35. const unsigned char *param);
  36. static int ED25519_FN(ed25519_sign_open) (const unsigned char *m, size_t mlen,
  37. const ed25519_public_key pk, const ed25519_signature RS);
  38. /*
  39. Generates a (extsk[0..31]) and aExt (extsk[32..63])
  40. */
  41. DONNA_INLINE static void
  42. ed25519_extsk(hash_512bits extsk, const ed25519_secret_key sk) {
  43. ed25519_hash(extsk, sk, 32);
  44. extsk[0] &= 248;
  45. extsk[31] &= 127;
  46. extsk[31] |= 64;
  47. }
  48. static void
  49. ed25519_hram(hash_512bits hram, const ed25519_signature RS, const ed25519_public_key pk, const unsigned char *m, size_t mlen) {
  50. ed25519_hash_context ctx;
  51. ed25519_hash_init(&ctx);
  52. ed25519_hash_update(&ctx, RS, 32);
  53. ed25519_hash_update(&ctx, pk, 32);
  54. ed25519_hash_update(&ctx, m, mlen);
  55. ed25519_hash_final(&ctx, hram);
  56. }
  57. static int
  58. ED25519_FN(ed25519_sign_open) (const unsigned char *m, size_t mlen, const ed25519_public_key pk, const ed25519_signature RS) {
  59. ge25519 ALIGN(16) R, A;
  60. hash_512bits hash;
  61. bignum256modm hram, S;
  62. unsigned char checkR[32];
  63. if ((RS[63] & 224) || !ge25519_unpack_negative_vartime(&A, pk))
  64. return -1;
  65. /* hram = H(R,A,m) */
  66. ed25519_hram(hash, RS, pk, m, mlen);
  67. expand256_modm(hram, hash, 64);
  68. /* S */
  69. expand256_modm(S, RS + 32, 32);
  70. /* SB - H(R,A,m)A */
  71. ge25519_double_scalarmult_vartime(&R, &A, hram, S);
  72. ge25519_pack(checkR, &R);
  73. /* check that R = SB - H(R,A,m)A */
  74. return ed25519_verify(RS, checkR, 32) ? 0 : -1;
  75. }
  76. #include "ed25519-donna-batchverify.h"
  77. /*
  78. Fast Curve25519 basepoint scalar multiplication
  79. */
  80. void
  81. ED25519_FN(curved25519_scalarmult_basepoint) (curved25519_key pk, const curved25519_key e) {
  82. curved25519_key ec;
  83. bignum256modm s;
  84. bignum25519 ALIGN(16) yplusz, zminusy;
  85. ge25519 ALIGN(16) p;
  86. size_t i;
  87. /* clamp */
  88. for (i = 0; i < 32; i++) ec[i] = e[i];
  89. ec[0] &= 248;
  90. ec[31] &= 127;
  91. ec[31] |= 64;
  92. expand_raw256_modm(s, ec);
  93. /* scalar * basepoint */
  94. ge25519_scalarmult_base_niels(&p, ge25519_niels_base_multiples, s);
  95. /* u = (y + z) / (z - y) */
  96. curve25519_add(yplusz, p.y, p.z);
  97. curve25519_sub(zminusy, p.z, p.y);
  98. curve25519_recip(zminusy, zminusy);
  99. curve25519_mul(yplusz, yplusz, zminusy);
  100. curve25519_contract(pk, yplusz);
  101. }
  102. /*
  103. Tor has a specific idea of how an Ed25519 implementation should behave.
  104. Implement such a beast using the ed25519-donna primitives/internals.
  105. * Private key generation using Tor's CSPRNG.
  106. * Routines that deal with the private key now use the expanded form.
  107. * Support for multiplicative key blinding has been added.
  108. * Support for converting a Curve25519 key to an Ed25519 key has been added.
  109. */
  110. int
  111. ed25519_donna_seckey(unsigned char *sk)
  112. {
  113. ed25519_secret_key seed;
  114. crypto_strongest_rand(seed, 32);
  115. ed25519_extsk(sk, seed);
  116. memwipe(seed, 0, sizeof(seed));
  117. return 0;
  118. }
  119. int
  120. ed25519_donna_seckey_expand(unsigned char *sk, const unsigned char *skseed)
  121. {
  122. ed25519_extsk(sk, skseed);
  123. return 0;
  124. }
  125. int
  126. ed25519_donna_pubkey(unsigned char *pk, const unsigned char *sk)
  127. {
  128. bignum256modm a = {0};
  129. ge25519 ALIGN(16) A = {{0}, {0}, {0}, {0}};
  130. /* A = aB */
  131. expand256_modm(a, sk, 32);
  132. ge25519_scalarmult_base_niels(&A, ge25519_niels_base_multiples, a);
  133. ge25519_pack(pk, &A);
  134. return 0;
  135. }
  136. int
  137. ed25519_donna_keygen(unsigned char *pk, unsigned char *sk)
  138. {
  139. int ok;
  140. ok = ed25519_donna_seckey(sk);
  141. ed25519_donna_pubkey(pk, sk);
  142. return ok;
  143. }
  144. int
  145. ed25519_donna_open(const unsigned char *signature, const unsigned char *m,
  146. size_t mlen, const unsigned char *pk)
  147. {
  148. /* Wrap the ed25519-donna routine, since it is also used by the batch
  149. * verification code.
  150. */
  151. return ED25519_FN(ed25519_sign_open)(m, mlen, pk, signature);
  152. }
  153. int
  154. ed25519_donna_sign(unsigned char *sig, const unsigned char *m, size_t mlen,
  155. const unsigned char *sk, const unsigned char *pk)
  156. {
  157. ed25519_hash_context ctx;
  158. bignum256modm r = {0}, S, a;
  159. ge25519 ALIGN(16) R = {{0}, {0}, {0}, {0}};
  160. hash_512bits hashr, hram;
  161. /* This is equivalent to the removed `ED25519_FN(ed25519_sign)` routine,
  162. * except that the key expansion step is omitted as sk already is in expanded
  163. * form.
  164. */
  165. /* r = H(aExt[32..64], m) */
  166. ed25519_hash_init(&ctx);
  167. ed25519_hash_update(&ctx, sk + 32, 32);
  168. ed25519_hash_update(&ctx, m, mlen);
  169. ed25519_hash_final(&ctx, hashr);
  170. expand256_modm(r, hashr, 64);
  171. /* R = rB */
  172. ge25519_scalarmult_base_niels(&R, ge25519_niels_base_multiples, r);
  173. ge25519_pack(sig, &R);
  174. /* S = H(R,A,m).. */
  175. ed25519_hram(hram, sig, pk, m, mlen);
  176. expand256_modm(S, hram, 64);
  177. /* S = H(R,A,m)a */
  178. expand256_modm(a, sk, 32);
  179. mul256_modm(S, S, a);
  180. /* S = (r + H(R,A,m)a) */
  181. add256_modm(S, S, r);
  182. /* S = (r + H(R,A,m)a) mod L */
  183. contract256_modm(sig + 32, S);
  184. return 0;
  185. }
  186. static void
  187. ed25519_donna_gettweak(unsigned char *out, const unsigned char *param)
  188. {
  189. memcpy(out, param, 32);
  190. out[0] &= 248; /* Is this necessary ? */
  191. out[31] &= 63;
  192. out[31] |= 64;
  193. }
  194. int
  195. ed25519_donna_blind_secret_key(unsigned char *out, const unsigned char *inp,
  196. const unsigned char *param)
  197. {
  198. static const char str[] = "Derive temporary signing key hash input";
  199. unsigned char tweak[64];
  200. ed25519_hash_context ctx;
  201. bignum256modm ALIGN(16) sk, t;
  202. ed25519_donna_gettweak(tweak, param);
  203. expand256_modm(t, tweak, 32);
  204. expand256_modm(sk, inp, 32);
  205. mul256_modm(sk, sk, t);
  206. contract256_modm(out, sk);
  207. ed25519_hash_init(&ctx);
  208. ed25519_hash_update(&ctx, (const unsigned char*)str, strlen(str));
  209. ed25519_hash_update(&ctx, inp + 32, 32);
  210. ed25519_hash_final(&ctx, tweak);
  211. memcpy(out + 32, tweak, 32);
  212. memwipe(sk, 0, sizeof(sk));
  213. memwipe(t, 0, sizeof(t));
  214. memwipe(tweak, 0, sizeof(tweak));
  215. return 0;
  216. }
  217. int
  218. ed25519_donna_blind_public_key(unsigned char *out, const unsigned char *inp,
  219. const unsigned char *param)
  220. {
  221. static const bignum256modm zero = { 0 };
  222. unsigned char tweak[64];
  223. unsigned char pkcopy[32];
  224. ge25519 ALIGN(16) A, Aprime;
  225. bignum256modm ALIGN(16) t;
  226. ed25519_donna_gettweak(tweak, param);
  227. expand256_modm(t, tweak, 32);
  228. /* No "ge25519_unpack", negate the public key. */
  229. memcpy(pkcopy, inp, 32);
  230. pkcopy[31] ^= (1<<7);
  231. if (!ge25519_unpack_negative_vartime(&A, pkcopy)) {
  232. return -1;
  233. }
  234. /* A' = [tweak] * A + [0] * basepoint. */
  235. ge25519_double_scalarmult_vartime(&Aprime, &A, t, zero);
  236. ge25519_pack(out, &Aprime);
  237. memwipe(tweak, 0, sizeof(tweak));
  238. memwipe(pkcopy, 0, sizeof(pkcopy));
  239. memwipe(&A, 0, sizeof(A));
  240. memwipe(&Aprime, 0, sizeof(Aprime));
  241. memwipe(t, 0, sizeof(t));
  242. return 0;
  243. }
  244. int
  245. ed25519_donna_pubkey_from_curve25519_pubkey(unsigned char *out,
  246. const unsigned char *inp, int signbit)
  247. {
  248. static const bignum25519 ALIGN(16) one = { 1 };
  249. bignum25519 ALIGN(16) u, uminus1, uplus1, inv_uplus1, y;
  250. /* Prop228: y = (u-1)/(u+1) */
  251. curve25519_expand(u, inp);
  252. curve25519_sub(uminus1, u, one);
  253. curve25519_add(uplus1, u, one);
  254. curve25519_recip(inv_uplus1, uplus1);
  255. curve25519_mul(y, uminus1, inv_uplus1);
  256. curve25519_contract(out, y);
  257. /* Propagate sign. */
  258. out[31] |= (!!signbit) << 7;
  259. return 0;
  260. }
  261. /* Do the scalar multiplication of <b>pubkey</b> with the group order
  262. * <b>modm_m</b>. Place the result in <b>out</b> which must be at least 32
  263. * bytes long. */
  264. int
  265. ed25519_donna_scalarmult_with_group_order(unsigned char *out,
  266. const unsigned char *pubkey)
  267. {
  268. static const bignum256modm ALIGN(16) zero = { 0 };
  269. unsigned char pkcopy[32];
  270. ge25519 ALIGN(16) Point, Result;
  271. /* No "ge25519_unpack", negate the public key and unpack it back.
  272. * See ed25519_donna_blind_public_key() */
  273. memcpy(pkcopy, pubkey, 32);
  274. pkcopy[31] ^= (1<<7);
  275. if (!ge25519_unpack_negative_vartime(&Point, pkcopy)) {
  276. return -1; /* error: bail out */
  277. }
  278. /* There is no regular scalarmult function so we have to do:
  279. * Result = l*P + 0*B */
  280. ge25519_double_scalarmult_vartime(&Result, &Point, modm_m, zero);
  281. ge25519_pack(out, &Result);
  282. return 0;
  283. }
  284. #include "test-internals.c"