ext/solv_pgpvrfy.c

   1 /*
   2  * Copyright (c) 2013-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 pgp signature verification code. */
   9
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12 #include <string.h>
  13
  14 #include "util.h"
  15 #include "solv_pgpvrfy.h"
  16
  17 #ifndef ENABLE_PGPVRFY_ED25519
  18 #define ENABLE_PGPVRFY_ED25519 1
  19 #endif
  20
  21 typedef unsigned int mp_t;
  22 typedef unsigned long long mp2_t;
  23 #define MP_T_BYTES 4
  24
  25 #define MP_T_BITS (MP_T_BYTES * 8)
  26
  27 static inline mp_t *
  28 mpnew(int len)
  29 {
  30   return solv_calloc(len, MP_T_BYTES);
  31 }
  32
  33 static inline void
  34 mpzero(int len, mp_t *target)
  35 {
  36   memset(target, 0, MP_T_BYTES * len);
  37 }
  38
  39 static inline void
  40 mpcpy(int len, mp_t *target, mp_t *source)
  41 {
  42   memcpy(target, source, len * MP_T_BYTES);
  43 }
  44
  45 static void
  46 mpsetfrombe(int len, mp_t *target, const unsigned char *buf, int bufl)
  47 {
  48   int i, mpl = len * MP_T_BYTES;
  49   buf += bufl;
  50   if (bufl >= mpl)
  51     bufl = mpl;
  52   if (mpl)
  53     memset(target, 0, mpl);
  54   for (i = 0; bufl > 0; bufl--, i++)
  55     target[i / MP_T_BYTES] |= (int)(*--buf) << (8 * (i % MP_T_BYTES));
  56 }
  57
  58 static int
  59 mpisless(int len, mp_t *a, mp_t *b)
  60 {
  61   int i;
  62   for (i = len - 1; i >= 0; i--)
  63     if (a[i] < b[i])
  64       return 1;
  65     else if (a[i] > b[i])
  66       return 0;
  67   return 0;
  68 }
  69
  70 static int
  71 mpisequal(int len, mp_t *a, mp_t *b)
  72 {
  73   return memcmp(a, b, len * MP_T_BYTES) == 0;
  74 }
  75
  76 static int
  77 mpiszero(int len, mp_t *a)
  78 {
  79   int i;
  80   for (i = 0; i < len; i++)
  81     if (a[i])
  82       return 0;
  83   return 1;
  84 }
  85
  86 #if 0
  87 static void mpdump(int l, mp_t *a, char *s)
  88 {
  89   int i;
  90   if (s)
  91     fprintf(stderr, "%s", s);
  92   for (i = l - 1; i >= 0; i--)
  93     fprintf(stderr, "%0*x", MP_T_BYTES * 2, a[i]);
  94   fprintf(stderr, "\n");
  95 }
  96 #endif
  97
  98 /* subtract mod from target. target >= mod */
  99 static inline void mpsubmod(int len, mp_t *target, mp_t *mod)
 100 {
 101   int i;
 102   mp2_t n;
 103   for (n = 0, i = 0; i < len; i++)
 104     {
 105       mp2_t n2 = (mp2_t)mod[i] + n;
 106       n = n2 > target[i] ? 1 : 0;
 107       target[i] -= (mp_t)n2;
 108     }
 109 }
 110
 111 /* target[len] = x, target = target % mod
 112  * assumes that target < (mod << MP_T_BITS)! */
 113 static void
 114 mpdomod(int len, mp_t *target, mp2_t x, mp_t *mod)
 115 {
 116   int i, j;
 117   for (i = len - 1; i >= 0; i--)
 118     {
 119       x = (x << MP_T_BITS) | target[i];
 120       target[i] = 0;
 121       if (mod[i])
 122         break;
 123     }
 124   if (i < 0)
 125     return;
 126   while (x >= 2 * (mp2_t)mod[i])
 127     {
 128       /* reduce */
 129       mp2_t z = x / ((mp2_t)mod[i] + 1);
 130       mp2_t n = 0;
 131       if ((z >> MP_T_BITS) != 0)
 132         z = (mp2_t)1 << MP_T_BITS;      /* just in case... */
 133       for (j = 0; j < i; j++)
 134         {
 135           mp_t n2;
 136           n += mod[j] * z;
 137           n2 = (mp_t)n;
 138           n >>= MP_T_BITS;
 139           if (n2 > target[j])
 140             n++;
 141           target[j] -= n2;
 142         }
 143       n += mod[j] * z;
 144       x -= n;
 145     }
 146   target[i] = x;
 147   if (x > mod[i] || (x == mod[i] && !mpisless(i, target, mod)))
 148     mpsubmod(i + 1, target, mod);
 149 }
 150
 151 /* target += src * m */
 152 static void
 153 mpmul_add_int(int len, mp_t *target, mp_t *src, mp2_t m, mp_t *mod)
 154 {
 155   int i;
 156   mp2_t x = 0;
 157   for (i = 0; i < len; i++)
 158     {
 159       x += src[i] * m + target[i];
 160       target[i] = x;
 161       x >>= MP_T_BITS;
 162     }
 163   mpdomod(len, target, x, mod);
 164 }
 165
 166 /* target = target << MP_T_BITS */
 167 static void
 168 mpshift(int len, mp_t *target, mp_t *mod)
 169 {
 170   mp_t x;
 171   if (len <= 0)
 172     return;
 173   x = target[len - 1];
 174   if (len > 1)
 175     memmove(target + 1, target, (len - 1) * MP_T_BYTES);
 176   target[0] = 0;
 177   mpdomod(len, target, x, mod);
 178 }
 179
 180 /* target += m1 * m2 */
 181 static void
 182 mpmul_add(int len, mp_t *target, mp_t *m1, int m2len, mp_t *m2, mp_t *tmp, mp_t *mod)
 183 {
 184   int i, j;
 185   for (j = m2len - 1; j >= 0; j--)
 186     if (m2[j])
 187       break;
 188   if (j < 0)
 189     return;
 190   mpcpy(len, tmp, m1);
 191   for (i = 0; i < j; i++)
 192     {
 193       if (m2[i])
 194         mpmul_add_int(len, target, tmp, m2[i], mod);
 195       mpshift(len, tmp, mod);
 196     }
 197   if (m2[i])
 198     mpmul_add_int(len, target, tmp, m2[i], mod);
 199 }
 200
 201 /* target = target * m */
 202 static void
 203 mpmul_inplace(int len, mp_t *target, mp_t *m, mp_t *tmp1, mp_t *tmp2, mp_t *mod)
 204 {
 205   mpzero(len, tmp1);
 206   mpmul_add(len, tmp1, target, len, m, tmp2, mod);
 207   mpcpy(len, target, tmp1);
 208 }
 209
 210 /* target = target ^ 16 * b ^ e */
 211 static void
 212 mppow_int(int len, mp_t *target, mp_t *t, mp_t *mod, int e)
 213 {
 214   mp_t *t2 = t + len * 16;
 215   mpmul_inplace(len, target, target, t, t2, mod);
 216   mpmul_inplace(len, target, target, t, t2, mod);
 217   mpmul_inplace(len, target, target, t, t2, mod);
 218   mpmul_inplace(len, target, target, t, t2, mod);
 219   if (e)
 220     mpmul_inplace(len, target, t + len * e, t, t2, mod);
 221 }
 222
 223 /* target = b ^ e (b < mod) */
 224 static void
 225 mppow(int len, mp_t *target, mp_t *b, int elen, mp_t *e, mp_t *mod)
 226 {
 227   int i, j;
 228   mp_t *t;
 229   mpzero(len, target);
 230   target[0] = 1;
 231   for (i = elen - 1; i >= 0; i--)
 232     if (e[i])
 233       break;
 234   if (i < 0)
 235     return;
 236   t = mpnew(len * 17);
 237   mpcpy(len, t + len, b);
 238   for (j = 2; j < 16; j++)
 239     mpmul_add(len, t + len * j, b, len, t + len * j - len, t + len * 16, mod);
 240   for (; i >= 0; i--)
 241     {
 242 #if MP_T_BYTES == 4
 243       mppow_int(len, target, t, mod, (e[i] >> 28) & 0x0f);
 244       mppow_int(len, target, t, mod, (e[i] >> 24) & 0x0f);
 245       mppow_int(len, target, t, mod, (e[i] >> 20) & 0x0f);
 246       mppow_int(len, target, t, mod, (e[i] >> 16) & 0x0f);
 247       mppow_int(len, target, t, mod, (e[i] >> 12) & 0x0f);
 248       mppow_int(len, target, t, mod, (e[i] >>  8) & 0x0f);
 249       mppow_int(len, target, t, mod, (e[i] >>  4) & 0x0f);
 250       mppow_int(len, target, t, mod,  e[i]        & 0x0f);
 251 #elif MP_T_BYTES == 1
 252       mppow_int(len, target, t, mod, (e[i] >>  4) & 0x0f);
 253       mppow_int(len, target, t, mod,  e[i]        & 0x0f);
 254 #endif
 255     }
 256   free(t);
 257 }
 258
 259 /* target = m1 * m2 (m1 < mod) */
 260 static void
 261 mpmul(int len, mp_t *target, mp_t *m1, int m2len, mp_t *m2, mp_t *mod)
 262 {
 263   mp_t *tmp = mpnew(len);
 264   mpzero(len, target);
 265   mpmul_add(len, target, m1, m2len, m2, tmp, mod);
 266   free(tmp);
 267 }
 268
 269 static void
 270 mpdec(int len, mp_t *a)
 271 {
 272   int i;
 273   for (i = 0; i < len; i++)
 274     if (a[i]--)
 275       return;
 276 }
 277
 278 #if ENABLE_PGPVRFY_ED25519
 279 /* target = m1 + m2 (m1, m2 < mod). target may be m1 or m2 */
 280 static void
 281 mpadd(int len, mp_t *target, mp_t *m1, mp_t *m2, mp_t *mod)
 282 {
 283   int i;
 284   mp2_t x = 0;
 285   for (i = 0; i < len; i++)
 286     {
 287       x += (mp2_t)m1[i] + m2[i];
 288       target[i] = x;
 289       x >>= MP_T_BITS;
 290     }
 291   if (x || target[len - 1] > mod[len - 1] ||
 292       (target[len -1 ] == mod[len - 1] && !mpisless(len - 1, target, mod)))
 293     mpsubmod(len, target, mod);
 294 }
 295
 296 /* target = m1 - m2 (m1, m2 < mod). target may be m1 or m2 */
 297 static void
 298 mpsub(int len, mp_t *target, mp_t *m1, mp_t *m2, mp_t *mod)
 299 {
 300   int i;
 301   mp2_t x = 0;
 302   for (i = 0; i < len; i++)
 303     {
 304       x = (mp2_t)m1[i] - m2[i] - x;
 305       target[i] = x;
 306       x = x & ((mp2_t)1 << MP_T_BITS) ? 1 : 0;
 307     }
 308   if (x)
 309     {
 310       for (x = 0, i = 0; i < len; i++)
 311         {
 312           x += (mp2_t)target[i] + mod[i];
 313           target[i] = x;
 314           x >>= MP_T_BITS;
 315         }
 316     }
 317 }
 318 #endif
 319
 320
 321 static int
 322 mpdsa(int pl, mp_t *p, int ql, mp_t *q, mp_t *g, mp_t *y, mp_t *r, mp_t *s, int hl, mp_t *h)
 323 {
 324   mp_t *w;
 325   mp_t *tmp;
 326   mp_t *u1, *u2;
 327   mp_t *gu1, *yu2;
 328   int res;
 329 #if 0
 330   mpdump(pl, p, "p = ");
 331   mpdump(ql, q, "q = ");
 332   mpdump(pl, g, "g = ");
 333   mpdump(pl, y, "y = ");
 334   mpdump(ql, r, "r = ");
 335   mpdump(ql, s, "s = ");
 336   mpdump(hl, h, "h = ");
 337 #endif
 338   if (pl < ql || !mpisless(pl, g, p) || !mpisless(pl, y, p))
 339     return 0;                           /* hmm, bad pubkey? */
 340   if (!mpisless(ql, r, q) || mpiszero(ql, r))
 341     return 0;
 342   if (!mpisless(ql, s, q) || mpiszero(ql, s))
 343     return 0;
 344   tmp = mpnew(pl);                      /* note pl */
 345   mpcpy(ql, tmp, q);                    /* tmp = q */
 346   mpdec(ql, tmp);                       /* tmp-- */
 347   mpdec(ql, tmp);                       /* tmp-- */
 348   w = mpnew(ql);
 349   mppow(ql, w, s, ql, tmp, q);          /* w = s ^ tmp = (s ^ -1) */
 350   u1 = mpnew(pl);                       /* note pl */
 351   /* order is important here: h can be >= q */
 352   mpmul(ql, u1, w, hl, h, q);           /* u1 = w * h */
 353   u2 = mpnew(ql);                       /* u2 = 0 */
 354   mpmul(ql, u2, w, ql, r, q);           /* u2 = w * r */
 355   free(w);
 356   gu1 = mpnew(pl);
 357   yu2 = mpnew(pl);
 358   mppow(pl, gu1, g, ql, u1, p);         /* gu1 = g ^ u1 */
 359   mppow(pl, yu2, y, ql, u2, p);         /* yu2 = y ^ u2 */
 360   mpmul(pl, u1, gu1, pl, yu2, p);       /* u1 = gu1 * yu2 */
 361   free(gu1);
 362   free(yu2);
 363   mpzero(ql, u2);
 364   u2[0] = 1;                            /* u2 = 1 */
 365   mpmul(ql, tmp, u2, pl, u1, q);        /* tmp = u2 * u1 */
 366   free(u1);
 367   free(u2);
 368 #if 0
 369   mpdump(ql, tmp, "res = ");
 370 #endif
 371   res = mpisequal(ql, tmp, r);
 372   free(tmp);
 373   return res;
 374 }
 375
 376 static int
 377 mprsa(int nl, mp_t *n, int el, mp_t *e, mp_t *m, mp_t *c)
 378 {
 379   mp_t *tmp;
 380   int res;
 381 #if 0
 382   mpdump(nl, n, "n = ");
 383   mpdump(el, e, "e = ");
 384   mpdump(nl, m, "m = ");
 385   mpdump(nl, c, "c = ");
 386 #endif
 387   if (!mpisless(nl, m, n))
 388     return 0;
 389   if (!mpisless(nl, c, n))
 390     return 0;
 391   tmp = mpnew(nl);
 392   mppow(nl, tmp, m, el, e, n);          /* tmp = m ^ e */
 393 #if 0
 394   mpdump(nl, tmp, "res = ");
 395 #endif
 396   res = mpisequal(nl, tmp, c);
 397   free(tmp);
 398   return res;
 399 }
 400
 401 #if ENABLE_PGPVRFY_ED25519
 402 # include "solv_ed25519.h"
 403 #endif
 404
 405 /* create mp with size tbits from data with size dbits */
 406 static mp_t *
 407 mpbuild(const unsigned char *d, int dbits, int tbits, int *mplp)
 408 {
 409   int l = (tbits + MP_T_BITS - 1) / MP_T_BITS;
 410   mp_t *out = mpnew(l ? l : 1);
 411   if (mplp)
 412     *mplp = l;
 413   mpsetfrombe(l, out, d, (dbits + 7) / 8);
 414   return out;
 415 }
 416
 417 static const unsigned char *
 418 findmpi(const unsigned char **mpip, int *mpilp, int maxbits, int *outlen)
 419 {
 420   int mpil = *mpilp;
 421   const unsigned char *mpi = *mpip;
 422   int bits, l;
 423
 424   *outlen = 0;
 425   if (mpil < 2)
 426     return 0;
 427   bits = mpi[0] << 8 | mpi[1];
 428   l = 2 + (bits + 7) / 8;
 429   if (bits > maxbits || mpil < l || (bits && !mpi[2]))
 430     {
 431       *mpilp = 0;
 432       return 0;
 433     }
 434   *outlen = bits;
 435   *mpilp = mpil - l;
 436   *mpip = mpi + l;
 437   return mpi + 2;
 438 }
 439
 440 /* sig: 0:algo 1:hash 2-:mpidata */
 441 /* pub: 0:algo 1-:mpidata */
 442 int
 443 solv_pgpvrfy(const unsigned char *pub, int publ, const unsigned char *sig, int sigl)
 444 {
 445   int hashl;
 446   unsigned char *oid = 0;
 447   const unsigned char *mpi;
 448   int mpil;
 449   int res = 0;
 450
 451   if (!pub || !sig || publ < 1 || sigl < 2)
 452     return 0;
 453   if (pub[0] != sig[0])
 454     return 0;           /* key algo mismatch */
 455   switch(sig[1])
 456     {
 457     case 1:
 458       hashl = 16;       /* MD5 */
 459       oid = (unsigned char *)"\022\060\040\060\014\006\010\052\206\110\206\367\015\002\005\005\000\004\020";
 460       break;
 461     case 2:
 462       hashl = 20;       /* SHA-1 */
 463       oid = (unsigned char *)"\017\060\041\060\011\006\005\053\016\003\002\032\005\000\004\024";
 464       break;
 465     case 8:
 466       hashl = 32;       /* SHA-256 */
 467       oid = (unsigned char *)"\023\060\061\060\015\006\011\140\206\110\001\145\003\004\002\001\005\000\004\040";
 468       break;
 469     case 9:
 470       hashl = 48;       /* SHA-384 */
 471       oid = (unsigned char *)"\023\060\101\060\015\006\011\140\206\110\001\145\003\004\002\002\005\000\004\060";
 472       break;
 473     case 10:
 474       hashl = 64;       /* SHA-512 */
 475       oid = (unsigned char *)"\023\060\121\060\015\006\011\140\206\110\001\145\003\004\002\003\005\000\004\100";
 476       break;
 477     case 11:
 478       hashl = 28;       /* SHA-224 */
 479       oid = (unsigned char *)"\023\060\061\060\015\006\011\140\206\110\001\145\003\004\002\004\005\000\004\034";
 480       break;
 481     default:
 482       return 0;         /* unsupported hash algo */
 483     }
 484   if (sigl < 2 + hashl)
 485     return 0;
 486   switch (pub[0])
 487     {
 488     case 1:             /* RSA */
 489       {
 490         const unsigned char *n, *e, *m;
 491         unsigned char *c;
 492         int nlen, elen, mlen, clen;
 493         mp_t *nx, *ex, *mx, *cx;
 494         int nxl, exl;
 495
 496         mpi = pub + 1;
 497         mpil = publ - 1;
 498         n = findmpi(&mpi, &mpil, 8192, &nlen);
 499         e = findmpi(&mpi, &mpil, 1024, &elen);
 500         mpi = sig + 2 + hashl;
 501         mpil = sigl - (2 + hashl);
 502         m = findmpi(&mpi, &mpil, nlen, &mlen);
 503         if (!n || !e || !m || !nlen || !elen)
 504           return 0;
 505         /* build padding block */
 506         clen = (nlen - 1) / 8;
 507         if (hashl + *oid + 2 > clen)
 508           return 0;
 509         c = solv_malloc(clen);
 510         memset(c, 0xff, clen);
 511         c[0] = 1;
 512         memcpy(c + clen - hashl, sig + 2, hashl);
 513         memcpy(c + clen - hashl - *oid, oid + 1, *oid);
 514         c[clen - hashl - *oid - 1] = 0;
 515         clen = clen * 8 - 7;    /* always <= nlen */
 516         nx = mpbuild(n, nlen, nlen, &nxl);
 517         ex = mpbuild(e, elen, elen, &exl);
 518         mx = mpbuild(m, mlen, nlen, 0);
 519         cx = mpbuild(c, clen, nlen, 0);
 520         free(c);
 521         res = mprsa(nxl, nx, exl, ex, mx, cx);
 522         free(nx);
 523         free(ex);
 524         free(mx);
 525         free(cx);
 526         break;
 527       }
 528     case 17:            /* DSA */
 529       {
 530         const unsigned char *p, *q, *g, *y, *r, *s;
 531         int plen, qlen, glen, ylen, rlen, slen, hlen;
 532         mp_t *px, *qx, *gx, *yx, *rx, *sx, *hx;
 533         int pxl, qxl, hxl;
 534
 535         mpi = pub + 1;
 536         mpil = publ - 1;
 537         p = findmpi(&mpi, &mpil, 8192, &plen);
 538         q = findmpi(&mpi, &mpil, 1024, &qlen);
 539         g = findmpi(&mpi, &mpil, plen, &glen);
 540         y = findmpi(&mpi, &mpil, plen, &ylen);
 541         mpi = sig + 2 + hashl;
 542         mpil = sigl - (2 + hashl);
 543         r = findmpi(&mpi, &mpil, qlen, &rlen);
 544         s = findmpi(&mpi, &mpil, qlen, &slen);
 545         if (!p || !q || !g || !y || !r || !s || !plen || !qlen)
 546           return 0;
 547         hlen = (qlen + 7) & ~7;
 548         if (hlen > hashl * 8)
 549           return 0;
 550         px = mpbuild(p, plen, plen, &pxl);
 551         qx = mpbuild(q, qlen, qlen, &qxl);
 552         gx = mpbuild(g, glen, plen, 0);
 553         yx = mpbuild(y, ylen, plen, 0);
 554         rx = mpbuild(r, rlen, qlen, 0);
 555         sx = mpbuild(s, slen, qlen, 0);
 556         hx = mpbuild(sig + 2, hlen, hlen, &hxl);
 557         res = mpdsa(pxl, px, qxl, qx, gx, yx, rx, sx, hxl, hx);
 558         free(px);
 559         free(qx);
 560         free(gx);
 561         free(yx);
 562         free(rx);
 563         free(sx);
 564         free(hx);
 565         break;
 566       }
 567 #if ENABLE_PGPVRFY_ED25519
 568     case 22:            /* EdDSA */
 569       {
 570         unsigned char sigdata[64];
 571         const unsigned char *r, *s;
 572         int rlen, slen;
 573
 574         /* check the curve */
 575         if (publ < 11 || memcmp(pub + 1, "\011\053\006\001\004\001\332\107\017\001", 10) != 0)
 576           return 0;     /* we only support the Ed25519 curve */
 577         /* the pubkey always has 7 + 256 bits */
 578         if (publ != 1 + 10 + 2 + 1 + 32 || pub[1 + 10 + 0] != 1 || pub[1 + 10 + 1] != 7 || pub[1 + 10 + 2] != 0x40)
 579           return 0;
 580         mpi = sig + 2 + hashl;
 581         mpil = sigl - (2 + hashl);
 582         r = findmpi(&mpi, &mpil, 256, &rlen);
 583         s = findmpi(&mpi, &mpil, 256, &slen);
 584         if (!r || !s)
 585           return 0;
 586         memset(sigdata, 0, 64);
 587         rlen = (rlen + 7) / 8;
 588         slen = (slen + 7) / 8;
 589         if (rlen)
 590           memcpy(sigdata + 32 - rlen, r, rlen);
 591         if (slen)
 592           memcpy(sigdata + 64 - slen, s, rlen);
 593         res = mped25519(pub + 1 + 10 + 2 + 1, sigdata, sig + 2, hashl);
 594         break;
 595       }
 596 #endif
 597     default:
 598       return 0;         /* unsupported pubkey algo */
 599     }
 600   return res;
 601 }
 602