ext/solv_pgpvrfy.c

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