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