ext/solv_ed25519.h

   1 /*
   2  * Copyright (c) 2020, SUSE LLC.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /* simple and slow ed25519 verification code. */
   9
  10 #ifndef LIBSOLV_CHKSUM_H
  11 #include "chksum.h"
  12 #endif
  13
  14 #define MPED25519_LEN (32 / MP_T_BYTES)
  15
  16 #if MP_T_BYTES == 4
  17 # define MPED25519_CONST1(x) (mp_t)x
  18 #elif MP_T_BYTES == 1
  19 # define MPED25519_CONST1(x) (mp_t)(x >> 0), (mp_t)(x >> 8), (mp_t)(x >> 16), (mp_t)(x >> 24)
  20 #endif
  21
  22 #define MPED25519_CONST(a, b, c, d, e, f, g, h) { \
  23   MPED25519_CONST1(h), MPED25519_CONST1(g), MPED25519_CONST1(f), MPED25519_CONST1(e), \
  24   MPED25519_CONST1(d), MPED25519_CONST1(c), MPED25519_CONST1(b), MPED25519_CONST1(a) \
  25 }
  26
  27 static mp_t ed25519_q[] =               /* mod prime */
  28   MPED25519_CONST(0x7FFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFED);
  29 static mp_t ed25519_d[] =               /* -(121665/121666) */
  30   MPED25519_CONST(0x52036CEE, 0x2B6FFE73, 0x8CC74079, 0x7779E898, 0x00700A4D, 0x4141D8AB, 0x75EB4DCA, 0x135978A3);
  31 static mp_t ed25519_sqrtm1[] =          /* sqrt(-1) */
  32   MPED25519_CONST(0x2B832480, 0x4FC1DF0B, 0x2B4D0099, 0x3DFBD7A7, 0x2F431806, 0xAD2FE478, 0xC4EE1B27, 0x4A0EA0B0);
  33 static mp_t ed25519_l[] =               /* order of base point */
  34   MPED25519_CONST(0x10000000, 0x00000000, 0x00000000, 0x00000000, 0x14DEF9DE, 0xA2F79CD6, 0x5812631A, 0x5CF5D3ED);
  35 static mp_t ed25519_gx[] =              /* base point */
  36   MPED25519_CONST(0x216936D3, 0xCD6E53FE, 0xC0A4E231, 0xFDD6DC5C, 0x692CC760, 0x9525A7B2, 0xC9562D60, 0x8F25D51A);
  37 static mp_t ed25519_gy[] =              /* base point */
  38   MPED25519_CONST(0x66666666, 0x66666666, 0x66666666, 0x66666666, 0x66666666, 0x66666666, 0x66666666, 0x66666658);
  39 static mp_t ed25519_one[] =             /* 1 */
  40   MPED25519_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001);
  41
  42 /* small helpers to save some typing */
  43 static inline void
  44 mped25519_add(mp_t *target, mp_t *m1, mp_t *m2)
  45 {
  46   mpadd(MPED25519_LEN, target, m1, m2, ed25519_q);
  47 }
  48
  49 static inline void
  50 mped25519_sub(mp_t *target, mp_t *m1, mp_t *m2)
  51 {
  52   mpsub(MPED25519_LEN, target, m1, m2, ed25519_q);
  53 }
  54
  55 /* target = 512 bit input modulo ed25519_q */
  56 static void
  57 mped25519_reduce512(mp_t *target, mp_t *a)
  58 {
  59   int i;
  60   mp2_t x;
  61
  62   for (x = 0, i = 0; i < MPED25519_LEN; i++)
  63     {
  64       x += (mp2_t)a[i] + (mp2_t)a[i + MPED25519_LEN] * 38;
  65       target[i] = x;
  66       x >>= MP_T_BITS;
  67     }
  68   x *= 38;
  69   if ((target[MPED25519_LEN - 1] & (1 << (MP_T_BITS - 1))) != 0)
  70     {
  71       x += 19;
  72       target[MPED25519_LEN - 1] -= 1 << (MP_T_BITS - 1);
  73     }
  74   for (i = 0; x && i < MPED25519_LEN; i++)
  75     {
  76       x += (mp2_t)target[i];
  77       target[i] = x;
  78       x >>= MP_T_BITS;
  79     }
  80   if (target[MPED25519_LEN - 1] > ed25519_q[MPED25519_LEN - 1] ||
  81       (target[MPED25519_LEN - 1] == ed25519_q[MPED25519_LEN - 1] && !mpisless(MPED25519_LEN - 1, target, ed25519_q)))
  82     mpsubmod(MPED25519_LEN, target, ed25519_q);
  83 }
  84
  85 static void
  86 mped25519_mul(mp_t *target, mp_t *m1, mp_t *m2)
  87 {
  88   mp_t tmp[MPED25519_LEN * 2];
  89   int i, j;
  90   mp2_t x;
  91
  92   mpzero(MPED25519_LEN * 2, tmp);
  93   for (i = 0; i < MPED25519_LEN; i++)
  94     {
  95       for (x = 0, j = 0; j < MPED25519_LEN; j++)
  96         {
  97           x += (mp2_t)tmp[i + j] + (mp2_t)m1[i] * m2[j];
  98           tmp[i + j] = x;
  99           x >>= MP_T_BITS;
 100         }
 101       tmp[i + j] = x;
 102     }
 103   mped25519_reduce512(target, tmp);
 104 }
 105
 106 static inline void
 107 mped25519_sqr(mp_t *target, mp_t *m)
 108 {
 109   mped25519_mul(target, m, m);
 110 }
 111
 112 /* target = a ^ (2^252 - 4), a11 = a ^ 11 */
 113 static void
 114 mped25519_pow_252_4(mp_t *target, mp_t *a, mp_t *a_11)
 115 {
 116   static const int todo[16] = { 0, 5, 1, 10, 2, 20, 3, 10, 2, 50, 5, 100, 6, 50, 5, 2 };
 117   mp_t data[9][MPED25519_LEN];
 118   int i, j;
 119
 120   mpcpy(MPED25519_LEN, target, a);
 121   mped25519_sqr(target, target);
 122   mpcpy(MPED25519_LEN, a_11, target);
 123   mped25519_sqr(target, target);
 124   mped25519_sqr(target, target);
 125   mped25519_mul(data[0], target, a);            /* data[0] = 9 */
 126   mped25519_mul(a_11, data[0], a_11);           /* a_11 = 11 */
 127   mped25519_mul(target, a_11, a_11);            /* target = 22 */
 128   for (i = 0; i < 8; i++)
 129     {
 130       mped25519_mul(target, target, data[todo[i * 2]]);
 131       mpcpy(MPED25519_LEN, data[i + 1], target);
 132       for (j = todo[i * 2 + 1]; j-- > 0;)
 133         mped25519_sqr(target, target);
 134     }
 135 }
 136
 137 /* target = a ^ (2^252 - 3) */
 138 static void
 139 mped25519_pow_252_3(mp_t *target, mp_t *a)
 140 {
 141   mp_t t11[MPED25519_LEN];
 142   mped25519_pow_252_4(target, a, t11);
 143   mped25519_mul(target, target, a);
 144 }
 145
 146 /* target = a ^ -1 = a ^ (2^255 - 21) */
 147 static void
 148 mped25519_inv(mp_t *target, mp_t *a)
 149 {
 150   mp_t t[MPED25519_LEN], t11[MPED25519_LEN];
 151   mped25519_pow_252_4(t, a, t11);
 152   mped25519_sqr(t, t);
 153   mped25519_sqr(t, t);
 154   mped25519_sqr(t, t);          /* 2^255 - 32 */
 155   mped25519_mul(target, t, t11);
 156 }
 157
 158 static void
 159 mped25519_reduce512_l(mp_t *target, mp_t *a)
 160 {
 161   mp_t tmp[MPED25519_LEN];
 162   mpzero(MPED25519_LEN, target);
 163   mpmul_add(MPED25519_LEN, target, ed25519_one, MPED25519_LEN * 2, a, tmp, ed25519_l);
 164 }
 165
 166 /* recover x coordinate from y and sign */
 167 static int
 168 mped25519_recover_x(mp_t *x, mp_t *y, int sign)
 169 {
 170   mp_t num[MPED25519_LEN], den[MPED25519_LEN];
 171   mp_t tmp1[MPED25519_LEN], tmp2[MPED25519_LEN];
 172
 173   if (!mpisless(MPED25519_LEN, y, ed25519_q))
 174     return 0;
 175   /* calculate num=y^2-1 and den=dy^2+1 */
 176   mped25519_sqr(num, y);
 177   mped25519_mul(den, num, ed25519_d);
 178   mped25519_sub(num, num, ed25519_one);
 179   mped25519_add(den, den, ed25519_one);
 180
 181   /* calculate x = num*den^3 * (num*den^7)^((q-5)/8) */
 182   mped25519_sqr(tmp1, den);             /* tmp1 = den^2 */
 183   mped25519_mul(tmp2, tmp1, den);       /* tmp2 = den^3 */
 184   mped25519_sqr(tmp1, tmp2);            /* tmp1 = den^6 */
 185   mped25519_mul(x, tmp1, den);          /* x = den^7 */
 186   mped25519_mul(tmp1, x, num);          /* tmp1 = num * den^7 */
 187   mped25519_pow_252_3(x, tmp1);         /* x = tmp1^((q-5)/8) */
 188   mped25519_mul(tmp1, x, tmp2);         /* tmp1 = x * den^3 */
 189   mped25519_mul(x, tmp1, num);          /* x = tmp1 * num */
 190
 191   /* check if den*x^2 == num */
 192   mped25519_sqr(tmp2, x);
 193   mped25519_mul(tmp1, tmp2, den);
 194   if (!mpisequal(MPED25519_LEN, tmp1, num)) {
 195     mped25519_mul(x, x, ed25519_sqrtm1);        /* x = x * sqrt(-1) */
 196     mped25519_sqr(tmp2, x);
 197     mped25519_mul(tmp1, tmp2, den);
 198     if (!mpisequal(MPED25519_LEN, tmp1, num))
 199       return 0;
 200   }
 201   if (mpiszero(MPED25519_LEN, x))
 202     return 0;                           /* (0,1) is bad */
 203   if ((x[0] & 1) != sign)
 204     mped25519_sub(x, ed25519_q, x);
 205   return 1;
 206 }
 207
 208 /* see https://hyperelliptic.org/EFD/g1p/auto-twisted-projective.html */
 209 /* M=7 add=6 */
 210 static void
 211 mped25519_ptdouble(mp_t *p_x, mp_t *p_y, mp_t *p_z)
 212 {
 213   mp_t B[MPED25519_LEN], C[MPED25519_LEN], D[MPED25519_LEN];
 214   mp_t F[MPED25519_LEN], H[MPED25519_LEN], J[MPED25519_LEN];
 215
 216   mped25519_add(C, p_x, p_y);
 217   mped25519_sqr(B, C);
 218   mped25519_sqr(C, p_x);
 219   mped25519_sqr(D, p_y);
 220   mped25519_sub(F, C, D);
 221   mped25519_sqr(H, p_z);
 222   mped25519_add(H, H, H);
 223   mped25519_add(J, F, H);
 224   mped25519_add(H, C, D);
 225   mped25519_mul(p_y, H, F);
 226   mped25519_mul(p_z, J, F);
 227   mped25519_sub(H, H, B);
 228   mped25519_mul(p_x, J, H);
 229 }
 230
 231 /* M=12 add=7 */
 232 static void
 233 mped25519_ptadd(mp_t *p_x, mp_t *p_y, mp_t *p_z, mp_t *q_x, mp_t *q_y, mp_t *q_z)
 234 {
 235   mp_t A[MPED25519_LEN], B[MPED25519_LEN], C[MPED25519_LEN];
 236   mp_t D[MPED25519_LEN], E[MPED25519_LEN], F[MPED25519_LEN];
 237   mp_t G[MPED25519_LEN], H[MPED25519_LEN], J[MPED25519_LEN];
 238
 239   mped25519_mul(A, p_z, q_z);
 240   mped25519_sqr(B, A);
 241   mped25519_mul(C, p_x, q_x);
 242   mped25519_mul(D, p_y, q_y);
 243   mped25519_mul(F, ed25519_d, C);
 244   mped25519_mul(E, F, D);
 245   mped25519_sub(F, B, E);
 246   mped25519_add(G, B, E);
 247   mped25519_add(H, p_x, p_y);
 248   mped25519_add(J, q_x, q_y);
 249   mped25519_mul(p_x, H, J);
 250   mped25519_sub(p_x, p_x, C);
 251   mped25519_sub(p_x, p_x, D);
 252   mped25519_mul(H, p_x, F);
 253   mped25519_mul(p_x, H, A);
 254   mped25519_add(H, D, C);
 255   mped25519_mul(J, H, G);
 256   mped25519_mul(p_y, J, A);
 257   mped25519_mul(p_z, F, G);
 258 }
 259
 260 static inline void
 261 mped25519_ptcpy(mp_t *p_x, mp_t *p_y, mp_t *p_z, mp_t *q_x, mp_t *q_y, mp_t *q_z)
 262 {
 263   mpcpy(MPED25519_LEN, p_x, q_x);
 264   mpcpy(MPED25519_LEN, p_y, q_y);
 265   mpcpy(MPED25519_LEN, p_z, q_z);
 266 }
 267
 268 #if 0
 269 static void
 270 mped25519_mpdump(mp_t *p, char *s, int c)
 271 {
 272   if (c)
 273     fprintf(stderr, "%c.", c);
 274   mpdump(MPED25519_LEN, p, s);
 275 }
 276
 277 static void
 278 mped25519_ptdump(mp_t *p_x, mp_t *p_y, mp_t *p_z, char *s)
 279 {
 280   mp_t zi[MPED25519_LEN], px[MPED25519_LEN], py[MPED25519_LEN];
 281   mped25519_mpdump(p_x, s, 'X');
 282   mped25519_mpdump(p_y, s, 'Y');
 283   mped25519_mpdump(p_z, s, 'Z');
 284   mped25519_inv(zi, p_z);
 285   mped25519_mul(px, p_x, zi);
 286   mped25519_mul(py, p_y, zi);
 287   mped25519_mpdump(px, s, 'x');
 288   mped25519_mpdump(py, s, 'y');
 289 }
 290 #endif
 291
 292
 293 /* scalar multiplication and add: r = s1*p1 + s2*p2 */
 294 /* needs about 13 + (256 - 32) / 2 = 125 point additions */
 295 static int
 296 mped25519_scmult2(mp_t *r_x, mp_t *r_y, mp_t *s1, mp_t *p1_x, mp_t * p1_y, mp_t *s2, mp_t *p2_x, mp_t * p2_y)
 297 {
 298   mp_t p_x[MPED25519_LEN], p_y[MPED25519_LEN], p_z[MPED25519_LEN];
 299   mp_t pi_z[MPED25519_LEN];
 300   mp_t tabx[16][MPED25519_LEN], taby[16][MPED25519_LEN], tabz[16][MPED25519_LEN];
 301   int i, x, dodouble = 0;
 302
 303   mpzero(MPED25519_LEN, p_x);
 304   mpzero(MPED25519_LEN, p_y);
 305   mpzero(MPED25519_LEN, p_z);
 306   p_y[0] = p_z[0] = 1;
 307
 308   /* setup table: tab[i * 4 + j] = i * p1 + j * p2 */
 309   mped25519_ptcpy(tabx[0], taby[0], tabz[0], p_x, p_y, p_z);
 310   for (i = 4; i < 16; i += 4)
 311     mped25519_ptcpy(tabx[i], taby[i], tabz[i], p1_x, p1_y, ed25519_one);
 312   mped25519_ptdouble(tabx[8], taby[8], tabz[8]);
 313   mped25519_ptadd(tabx[12], taby[12], tabz[12], tabx[8], taby[8], tabz[8]);
 314   mped25519_ptcpy(tabx[1], taby[1], tabz[1], p2_x, p2_y, ed25519_one);
 315   for (i = 2; i < 16; i++)
 316     {
 317       if ((i & 3) == 0)
 318         continue;
 319       mped25519_ptcpy(tabx[i], taby[i], tabz[i], tabx[i - 1], taby[i - 1], tabz[i - 1]);
 320       mped25519_ptadd(tabx[i], taby[i], tabz[i], p2_x, p2_y, ed25519_one);
 321     }
 322   /* now do the scalar multiplication */
 323   for (i = 255; i >= 0; i--)
 324     {
 325       if (dodouble)
 326         mped25519_ptdouble(p_x, p_y, p_z);
 327       x  = s1[i / MP_T_BITS] & (1 << (i % MP_T_BITS)) ? 4 : 0;
 328       x |= s2[i / MP_T_BITS] & (1 << (i % MP_T_BITS)) ? 1 : 0;
 329       if (!x)
 330         continue;
 331       if (i > 0)
 332         {
 333           i--;
 334           if (dodouble)
 335             mped25519_ptdouble(p_x, p_y, p_z);
 336           x <<= 1;
 337           x |= s1[i / MP_T_BITS] & (1 << (i % MP_T_BITS)) ? 4 : 0;
 338           x |= s2[i / MP_T_BITS] & (1 << (i % MP_T_BITS)) ? 1 : 0;
 339         }
 340       mped25519_ptadd(p_x, p_y, p_z, tabx[x], taby[x], tabz[x]);
 341       dodouble = 1;
 342     }
 343 #if 0
 344   mped25519_ptdump(p_x, p_y, p_z, "r   = ");
 345 #endif
 346   mped25519_inv(pi_z, p_z);
 347   mped25519_mul(r_x, p_x, pi_z);
 348   mped25519_mul(r_y, p_y, pi_z);
 349   return mpiszero(MPED25519_LEN, p_z) ? 0 : 1;
 350 }
 351
 352 static void
 353 mped25519_setfromle(int len, mp_t *out, const unsigned char *buf, int bufl, int highmask)
 354 {
 355   unsigned char bebuf[64];      /* bufl must be <= 64 */
 356   int i;
 357   for (i = 0; i < bufl; i++)
 358     bebuf[bufl - 1 - i] = buf[i];
 359   bebuf[0] &= highmask;
 360   mpsetfrombe(len, out, bebuf, bufl);
 361 }
 362
 363 static int
 364 mped25519(const unsigned char *pub, const unsigned char *sig, const unsigned char *data, unsigned int datal)
 365 {
 366   unsigned char hbuf[64], rbuf[32];
 367   int i;
 368   mp_t pub_x[MPED25519_LEN], pub_y[MPED25519_LEN];
 369   mp_t h[MPED25519_LEN], s[MPED25519_LEN], h2[MPED25519_LEN * 2];
 370   mp_t r_x[MPED25519_LEN], r_y[MPED25519_LEN];
 371   Chksum *chk;
 372
 373   mped25519_setfromle(MPED25519_LEN, s, sig + 32, 32, 0xff);
 374   if (!mpisless(MPED25519_LEN, s, ed25519_l))
 375     return 0;           /* bad s */
 376   /* uncompress pubkey, we invert the sign to get -pub */
 377   mped25519_setfromle(MPED25519_LEN, pub_y, pub, 32, 0x7f);
 378   if (!mped25519_recover_x(pub_x, pub_y, pub[31] & 0x80 ? 0 : 1))
 379     return 0;           /* bad pubkey */
 380 #if 0
 381   mped25519_mpdump(pub_x, "-pubx = ", 0);
 382   mped25519_mpdump(pub_y, "puby  = ", 0);
 383 #endif
 384   /* calculate h = H(sig[0..31]|pub|data) mod l */
 385   chk = solv_chksum_create(REPOKEY_TYPE_SHA512);
 386   if (!chk)
 387     return 0;
 388   solv_chksum_add(chk, sig, 32);
 389   solv_chksum_add(chk, pub, 32);
 390   solv_chksum_add(chk, data, datal);
 391   solv_chksum_free(chk, hbuf);
 392   mped25519_setfromle(MPED25519_LEN * 2, h2, hbuf, 64, 0xff);
 393   mped25519_reduce512_l(h, h2);
 394 #if 0
 395   mped25519_mpdump(s, "s     = ", 0);
 396   mped25519_mpdump(h, "h     = ", 0);
 397 #endif
 398   /* calculate r = s * G - h * pub */
 399   if (!mped25519_scmult2(r_x, r_y, s, ed25519_gx, ed25519_gy, h, pub_x, pub_y))
 400     return 0;
 401   /* compress r into rbuf and verify that it matches sig */
 402   for (i = 0; i < 32; i++)
 403     rbuf[i] = r_y[i / MP_T_BYTES] >> (8 * (i % MP_T_BYTES));
 404   if ((r_x[0] & 1) != 0)
 405     rbuf[31] |= 0x80;
 406   return memcmp(sig, rbuf, 32) == 0 ? 1 : 0;
 407 }
 408