src/util/tweetnacl-gnunet.c

   1 /*
   2       This file has been placed in the public domain.
   3
   4       Based on TweetNaCl version 20140427
   5
   6       Originally obtained from:
   7       https://tweetnacl.cr.yp.to/20140427/tweetnacl.h
   8
   9       SPDX-License-Identifier: 0BSD
  10 */
  11
  12 #include "platform.h"
  13 #include "gnunet_crypto_lib.h"
  14 #include "tweetnacl-gnunet.h"
  15 #define FOR(i,n) for (i = 0; i < n; ++i)
  16
  17 typedef uint8_t u8;
  18 typedef uint32_t u32;
  19 typedef uint64_t u64;
  20 typedef int64_t i64;
  21 typedef i64 gf[16];
  22
  23 static const u8 _9[32] = {9};
  24 static const gf
  25   gf0,
  26   gf1 = {1},
  27   _121665 = {0xDB41,1},
  28   D = {0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070, 0xe898,
  29        0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203},
  30   D2 = {0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0, 0xd130,
  31         0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406},
  32   X = {0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c, 0xdc5c,
  33        0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169},
  34   Y = {0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666,
  35        0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666},
  36   I = {0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43, 0xd7a7,
  37        0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83};
  38
  39 static int
  40 vn (const u8 *x,const u8 *y,int n)
  41 {
  42   u32 i,d = 0;
  43   FOR (i,n) d |= x[i] ^ y[i];
  44   return (1 & ((d - 1) >> 8)) - 1;
  45 }
  46
  47 static int
  48 crypto_verify_32 (const u8 *x,const u8 *y)
  49 {
  50   return vn (x,y,32);
  51 }
  52
  53 static void
  54 set25519 (gf r, const gf a)
  55 {
  56   int i;
  57   FOR (i,16) r[i] = a[i];
  58 }
  59
  60 static void
  61 car25519 (gf o)
  62 {
  63   int i;
  64   i64 c;
  65   FOR (i,16) {
  66     o[i] += (1LL << 16);
  67     c = o[i] >> 16;
  68     o[(i + 1) * (i<15)] += c - 1 + 37 * (c - 1) * (i==15);
  69     o[i] -= c << 16;
  70   }
  71 }
  72
  73 static void
  74 sel25519 (gf p,gf q,int b)
  75 {
  76   i64 t,i,c = ~(b - 1);
  77   FOR (i,16) {
  78     t = c & (p[i] ^ q[i]);
  79     p[i] ^= t;
  80     q[i] ^= t;
  81   }
  82 }
  83
  84 static void
  85 pack25519 (u8 *o,const gf n)
  86 {
  87   int i,j,b;
  88   gf m,t;
  89   FOR (i,16) t[i] = n[i];
  90   car25519 (t);
  91   car25519 (t);
  92   car25519 (t);
  93   FOR (j,2) {
  94     m[0] = t[0] - 0xffed;
  95     for (i = 1; i<15; i++) {
  96       m[i] = t[i] - 0xffff - ((m[i - 1] >> 16) & 1);
  97       m[i - 1] &= 0xffff;
  98     }
  99     m[15] = t[15] - 0x7fff - ((m[14] >> 16) & 1);
 100     b = (m[15] >> 16) & 1;
 101     m[14] &= 0xffff;
 102     sel25519 (t,m,1 - b);
 103   }
 104   FOR (i,16) {
 105     o[2 * i] = t[i] & 0xff;
 106     o[2 * i + 1] = t[i] >> 8;
 107   }
 108 }
 109
 110 static int
 111 neq25519 (const gf a, const gf b)
 112 {
 113   u8 c[32],d[32];
 114   pack25519 (c,a);
 115   pack25519 (d,b);
 116   return crypto_verify_32 (c,d);
 117 }
 118
 119 static uint8_t
 120 par25519 (const gf a)
 121 {
 122   u8 d[32];
 123   pack25519 (d,a);
 124   return d[0] & 1;
 125 }
 126
 127 static void
 128 unpack25519 (gf o, const u8 *n)
 129 {
 130   int i;
 131   FOR (i,16) o[i] = n[2 * i] + ((i64) n[2 * i + 1] << 8);
 132   o[15] &= 0x7fff;
 133 }
 134
 135 static void
 136 A (gf o,const gf a,const gf b)
 137 {
 138   int i;
 139   FOR (i,16) o[i] = a[i] + b[i];
 140 }
 141
 142 static void
 143 Z (gf o,const gf a,const gf b)
 144 {
 145   int i;
 146   FOR (i,16) o[i] = a[i] - b[i];
 147 }
 148
 149 static void
 150 M (gf o,const gf a,const gf b)
 151 {
 152   i64 i,j,t[31];
 153   FOR (i,31) t[i] = 0;
 154   FOR (i,16) FOR (j,16) t[i + j] += a[i] * b[j];
 155   FOR (i,15) t[i] += 38 * t[i + 16];
 156   FOR (i,16) o[i] = t[i];
 157   car25519 (o);
 158   car25519 (o);
 159 }
 160
 161 static void
 162 S (gf o,const gf a)
 163 {
 164   M (o,a,a);
 165 }
 166
 167 static void
 168 inv25519 (gf o,const gf i)
 169 {
 170   gf c;
 171   int a;
 172   FOR (a,16) c[a] = i[a];
 173   for (a = 253; a>=0; a--) {
 174     S (c,c);
 175     if ((a!=2)&&(a!=4))
 176       M (c,c,i);
 177   }
 178   FOR (a,16) o[a] = c[a];
 179 }
 180
 181 static void pow2523 (gf o,const gf i)
 182 {
 183   gf c;
 184   int a;
 185   FOR (a,16) c[a] = i[a];
 186   for (a = 250; a>=0; a--) {
 187     S (c,c);
 188     if (a!=1)
 189       M (c,c,i);
 190   }
 191   FOR (a,16) o[a] = c[a];
 192 }
 193
 194 int
 195 GNUNET_TWEETNACL_scalarmult_curve25519 (u8 *q,const u8 *n,const u8 *p)
 196 {
 197   u8 z[32];
 198   i64 x[80],r,i;
 199   gf a,b,c,d,e,f;
 200   FOR (i,31) z[i] = n[i];
 201   z[31] = (n[31] & 127) | 64;
 202   z[0] &= 248;
 203   unpack25519 (x,p);
 204   FOR (i,16) {
 205     b[i] = x[i];
 206     d[i] = a[i] = c[i] = 0;
 207   }
 208   a[0] = d[0] = 1;
 209   for (i = 254; i>=0; --i) {
 210     r = (z[i >> 3] >> (i & 7)) & 1;
 211     sel25519 (a,b,r);
 212     sel25519 (c,d,r);
 213     A (e,a,c);
 214     Z (a,a,c);
 215     A (c,b,d);
 216     Z (b,b,d);
 217     S (d,e);
 218     S (f,a);
 219     M (a,c,a);
 220     M (c,b,e);
 221     A (e,a,c);
 222     Z (a,a,c);
 223     S (b,a);
 224     Z (c,d,f);
 225     M (a,c,_121665);
 226     A (a,a,d);
 227     M (c,c,a);
 228     M (a,d,f);
 229     M (d,b,x);
 230     S (b,e);
 231     sel25519 (a,b,r);
 232     sel25519 (c,d,r);
 233   }
 234   FOR (i,16) {
 235     x[i + 16] = a[i];
 236     x[i + 32] = c[i];
 237     x[i + 48] = b[i];
 238     x[i + 64] = d[i];
 239   }
 240   inv25519 (x + 32,x + 32);
 241   M (x + 16,x + 16,x + 32);
 242   pack25519 (q,x + 16);
 243   return 0;
 244 }
 245
 246 int
 247 GNUNET_TWEETNACL_scalarmult_curve25519_base (u8 *q,const u8 *n)
 248 {
 249   return GNUNET_TWEETNACL_scalarmult_curve25519 (q,n,_9);
 250 }
 251
 252 static int
 253 crypto_hash (u8 *out,const u8 *m,u64 n)
 254 {
 255   struct GNUNET_HashCode *hc = (void *) out;
 256   GNUNET_CRYPTO_hash (m, n, hc);
 257   return 0;
 258 }
 259
 260 static void
 261 add (gf p[4],gf q[4])
 262 {
 263   gf a,b,c,d,t,e,f,g,h;
 264
 265   Z (a, p[1], p[0]);
 266   Z (t, q[1], q[0]);
 267   M (a, a, t);
 268   A (b, p[0], p[1]);
 269   A (t, q[0], q[1]);
 270   M (b, b, t);
 271   M (c, p[3], q[3]);
 272   M (c, c, D2);
 273   M (d, p[2], q[2]);
 274   A (d, d, d);
 275   Z (e, b, a);
 276   Z (f, d, c);
 277   A (g, d, c);
 278   A (h, b, a);
 279
 280   M (p[0], e, f);
 281   M (p[1], h, g);
 282   M (p[2], g, f);
 283   M (p[3], e, h);
 284 }
 285
 286 static void
 287 cswap (gf p[4],gf q[4],u8 b)
 288 {
 289   int i;
 290   FOR (i,4)
 291   sel25519 (p[i],q[i],b);
 292 }
 293
 294 static void
 295 pack (u8 *r,gf p[4])
 296 {
 297   gf tx, ty, zi;
 298   inv25519 (zi, p[2]);
 299   M (tx, p[0], zi);
 300   M (ty, p[1], zi);
 301   pack25519 (r, ty);
 302   r[31] ^= par25519 (tx) << 7;
 303 }
 304
 305 static void
 306 scalarmult (gf p[4],gf q[4],const u8 *s)
 307 {
 308   int i;
 309   set25519 (p[0],gf0);
 310   set25519 (p[1],gf1);
 311   set25519 (p[2],gf1);
 312   set25519 (p[3],gf0);
 313   for (i = 255; i >= 0; --i) {
 314     u8 b = (s[i / 8] >> (i & 7)) & 1;
 315     cswap (p,q,b);
 316     add (q,p);
 317     add (p,p);
 318     cswap (p,q,b);
 319   }
 320 }
 321
 322 static void
 323 scalarbase (gf p[4],const u8 *s)
 324 {
 325   gf q[4];
 326   set25519 (q[0],X);
 327   set25519 (q[1],Y);
 328   set25519 (q[2],gf1);
 329   M (q[3],X,Y);
 330   scalarmult (p,q,s);
 331 }
 332
 333 static const u64 L[32] = {0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6,
 334                           0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0, 0, 0, 0,
 335                           0, 0, 0, 0, 0, 0, 0, 0,
 336                           0, 0, 0, 0x10};
 337
 338 static void
 339 modL (u8 *r,i64 x[64])
 340 {
 341   i64 carry,i,j;
 342   for (i = 63; i >= 32; --i) {
 343     carry = 0;
 344     for (j = i - 32; j < i - 12; ++j) {
 345       x[j] += carry - 16 * x[i] * L[j - (i - 32)];
 346       carry = (x[j] + 128) >> 8;
 347       x[j] -= carry << 8;
 348     }
 349     x[j] += carry;
 350     x[i] = 0;
 351   }
 352   carry = 0;
 353   FOR (j,32) {
 354     x[j] += carry - (x[31] >> 4) * L[j];
 355     carry = x[j] >> 8;
 356     x[j] &= 255;
 357   }
 358   FOR (j,32) x[j] -= carry * L[j];
 359   FOR (i,32) {
 360     x[i + 1] += x[i] >> 8;
 361     r[i] = x[i] & 255;
 362   }
 363 }
 364
 365 static void
 366 reduce (u8 *r)
 367 {
 368   i64 x[64],i;
 369   FOR (i,64) x[i] = (u64) r[i];
 370   FOR (i,64) r[i] = 0;
 371   modL (r,x);
 372 }
 373
 374 static int
 375 unpackneg (gf r[4],const u8 p[32])
 376 {
 377   gf t, chk, num, den, den2, den4, den6;
 378   set25519 (r[2],gf1);
 379   unpack25519 (r[1],p);
 380   S (num,r[1]);
 381   M (den,num,D);
 382   Z (num,num,r[2]);
 383   A (den,r[2],den);
 384
 385   S (den2,den);
 386   S (den4,den2);
 387   M (den6,den4,den2);
 388   M (t,den6,num);
 389   M (t,t,den);
 390
 391   pow2523 (t,t);
 392   M (t,t,num);
 393   M (t,t,den);
 394   M (t,t,den);
 395   M (r[0],t,den);
 396
 397   S (chk,r[0]);
 398   M (chk,chk,den);
 399   if (neq25519 (chk, num))
 400     M (r[0],r[0],I);
 401
 402   S (chk,r[0]);
 403   M (chk,chk,den);
 404   if (neq25519 (chk, num))
 405     return -1;
 406
 407   if (par25519 (r[0]) == (p[31] >> 7))
 408     Z (r[0],gf0,r[0]);
 409
 410   M (r[3],r[0],r[1]);
 411   return 0;
 412 }
 413
 414 /* The following functions have been added for GNUnet */
 415
 416 void
 417 GNUNET_TWEETNACL_sign_pk_from_seed (u8 *pk, const u8 *seed)
 418 {
 419   u8 d[64];
 420   gf p[4];
 421
 422   crypto_hash (d, seed, 32);
 423   d[0] &= 248;
 424   d[31] &= 127;
 425   d[31] |= 64;
 426
 427   scalarbase (p, d);
 428   pack (pk, p);
 429 }
 430
 431 void
 432 GNUNET_TWEETNACL_scalarmult_gnunet_ecdsa (u8 *pk, const u8 *s)
 433 {
 434   u8 d[64];
 435   gf p[4];
 436
 437   // Treat s as little endian.
 438   for (u32 i = 0; i < 32; i++)
 439     d[i] = s[31 - i];
 440
 441   // For GNUnet, we don't normalize d
 442
 443   scalarbase (p, d);
 444   pack (pk, p);
 445 }
 446
 447 void
 448 GNUNET_TWEETNACL_sign_sk_from_seed (u8 *sk, const u8 *seed)
 449 {
 450   u8 d[64];
 451   gf p[4];
 452   u8 pk[32];
 453   int i;
 454
 455   crypto_hash (d, seed, 32);
 456   d[0] &= 248;
 457   d[31] &= 127;
 458   d[31] |= 64;
 459
 460   scalarbase (p,d);
 461   pack (pk,p);
 462
 463   FOR (i,32) sk[i] = seed[i];
 464   FOR (i,32) sk[32 + i] = pk[i];
 465 }
 466
 467 int
 468 GNUNET_TWEETNACL_sign_ed25519_pk_to_curve25519 (u8 *x25519_pk,
 469                                                 const u8 *ed25519_pk)
 470 {
 471   gf ge_a[4];
 472   gf x;
 473   gf one_minus_y;
 474
 475   if (0 != unpackneg (ge_a, ed25519_pk))
 476     return -1;
 477
 478   set25519 (one_minus_y, gf1);
 479   Z (one_minus_y, one_minus_y, ge_a[1]);
 480
 481   set25519 (x, gf1);
 482   A (x, x, ge_a[1]);
 483
 484   inv25519 (one_minus_y, one_minus_y);
 485   M (x, x, one_minus_y);
 486   pack25519 (x25519_pk, x);
 487
 488   return 0;
 489 }
 490
 491 int GNUNET_TWEETNACL_sign_detached_verify (const u8 *sig,
 492                                            const u8 *m,
 493                                            u64 n,
 494                                            const u8 *pk)
 495 {
 496   struct GNUNET_HashContext *hc;
 497   u8 t[32],h[64];
 498   gf p[4],q[4];
 499
 500   if (unpackneg (q,pk))
 501     return -1;
 502
 503   hc = GNUNET_CRYPTO_hash_context_start ();
 504   GNUNET_CRYPTO_hash_context_read (hc, sig, 32);
 505   GNUNET_CRYPTO_hash_context_read (hc, pk, 32);
 506   GNUNET_CRYPTO_hash_context_read (hc, m, n);
 507   GNUNET_CRYPTO_hash_context_finish (hc, (void *) h);
 508
 509   reduce (h);
 510   scalarmult (p,q,h);
 511
 512   scalarbase (q,sig+32);
 513   add (p,q);
 514   pack (t,p);
 515
 516   if (crypto_verify_32 (sig, t))
 517     return -1;
 518   return 0;
 519 }
 520
 521 int
 522 GNUNET_TWEETNACL_sign_detached (u8 *sig,
 523                                 const u8 *m,
 524                                 u64 n,
 525                                 const u8 *sk)
 526 {
 527   struct GNUNET_HashContext *hc;
 528   u8 d[64],h[64],r[64];
 529   i64 i,j,x[64];
 530   gf p[4];
 531
 532   crypto_hash (d, sk, 32);
 533   d[0] &= 248;
 534   d[31] &= 127;
 535   d[31] |= 64;
 536
 537   hc = GNUNET_CRYPTO_hash_context_start ();
 538   GNUNET_CRYPTO_hash_context_read (hc, d + 32, 32);
 539   GNUNET_CRYPTO_hash_context_read (hc, m, n);
 540   GNUNET_CRYPTO_hash_context_finish (hc, (void *) r);
 541
 542   reduce (r);
 543   scalarbase (p,r);
 544   pack (sig,p);
 545
 546   hc = GNUNET_CRYPTO_hash_context_start ();
 547   GNUNET_CRYPTO_hash_context_read (hc, sig, 32);
 548   GNUNET_CRYPTO_hash_context_read (hc, sk + 32, 32);
 549   GNUNET_CRYPTO_hash_context_read (hc, m, n);
 550   GNUNET_CRYPTO_hash_context_finish (hc, (void *) h);
 551
 552   reduce (h);
 553
 554   FOR (i,64) x[i] = 0;
 555   FOR (i,32) x[i] = (u64) r[i];
 556   FOR (i,32) FOR (j,32) x[i + j] += h[i] * (u64) d[j];
 557   modL (sig + 32,x);
 558
 559   return 0;
 560 }