2 * Copyright (c) 2013-2020, SUSE LLC.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
8 /* simple and slow pgp signature verification code. */
15 #include "solv_pgpvrfy.h"
17 #ifndef ENABLE_PGPVRFY_ED25519
18 #define ENABLE_PGPVRFY_ED25519 1
21 typedef unsigned int mp_t;
22 typedef unsigned long long mp2_t;
25 #define MP_T_BITS (MP_T_BYTES * 8)
30 return solv_calloc(len, MP_T_BYTES);
34 mpzero(int len, mp_t *target)
36 memset(target, 0, MP_T_BYTES * len);
40 mpcpy(int len, mp_t *target, mp_t *source)
42 memcpy(target, source, len * MP_T_BYTES);
46 mpsetfrombe(int len, mp_t *target, const unsigned char *buf, int bufl)
48 int i, mpl = len * MP_T_BYTES;
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));
59 mpisless(int len, mp_t *a, mp_t *b)
62 for (i = len - 1; i >= 0; i--)
71 mpisequal(int len, mp_t *a, mp_t *b)
73 return memcmp(a, b, len * MP_T_BYTES) == 0;
77 mpiszero(int len, mp_t *a)
80 for (i = 0; i < len; i++)
87 static void mpdump(int l, mp_t *a, char *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");
98 /* subtract mod from target. target >= mod */
99 static inline void mpsubmod(int len, mp_t *target, mp_t *mod)
103 for (n = 0, i = 0; i < len; i++)
105 mp2_t n2 = (mp2_t)mod[i] + n;
106 n = n2 > target[i] ? 1 : 0;
107 target[i] -= (mp_t)n2;
111 /* target[len] = x, target = target % mod
112 * assumes that target < (mod << MP_T_BITS)! */
114 mpdomod(int len, mp_t *target, mp2_t x, mp_t *mod)
117 for (i = len - 1; i >= 0; i--)
119 x = (x << MP_T_BITS) | target[i];
126 while (x >= 2 * (mp2_t)mod[i])
129 mp2_t z = x / ((mp2_t)mod[i] + 1);
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++)
147 if (x > mod[i] || (x == mod[i] && !mpisless(i, target, mod)))
148 mpsubmod(i + 1, target, mod);
151 /* target += src * m */
153 mpmul_add_int(int len, mp_t *target, mp_t *src, mp2_t m, mp_t *mod)
157 for (i = 0; i < len; i++)
159 x += src[i] * m + target[i];
163 mpdomod(len, target, x, mod);
166 /* target = target << MP_T_BITS */
168 mpshift(int len, mp_t *target, mp_t *mod)
175 memmove(target + 1, target, (len - 1) * MP_T_BYTES);
177 mpdomod(len, target, x, mod);
180 /* target += m1 * m2 */
182 mpmul_add(int len, mp_t *target, mp_t *m1, int m2len, mp_t *m2, mp_t *tmp, mp_t *mod)
185 for (j = m2len - 1; j >= 0; j--)
191 for (i = 0; i < j; i++)
194 mpmul_add_int(len, target, tmp, m2[i], mod);
195 mpshift(len, tmp, mod);
198 mpmul_add_int(len, target, tmp, m2[i], mod);
201 /* target = target * m */
203 mpmul_inplace(int len, mp_t *target, mp_t *m, mp_t *tmp1, mp_t *tmp2, mp_t *mod)
206 mpmul_add(len, tmp1, target, len, m, tmp2, mod);
207 mpcpy(len, target, tmp1);
210 /* target = target ^ 16 * b ^ e */
212 mppow_int(int len, mp_t *target, mp_t *t, mp_t *mod, int e)
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);
220 mpmul_inplace(len, target, t + len * e, t, t2, mod);
223 /* target = b ^ e (b < mod) */
225 mppow(int len, mp_t *target, mp_t *b, int elen, mp_t *e, mp_t *mod)
231 for (i = elen - 1; i >= 0; i--)
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);
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);
259 /* target = m1 * m2 (m1 < mod) */
261 mpmul(int len, mp_t *target, mp_t *m1, int m2len, mp_t *m2, mp_t *mod)
263 mp_t *tmp = mpnew(len);
265 mpmul_add(len, target, m1, m2len, m2, tmp, mod);
270 mpdec(int len, mp_t *a)
273 for (i = 0; i < len; i++)
278 #if ENABLE_PGPVRFY_ED25519
279 /* target = m1 + m2 (m1, m2 < mod). target may be m1 or m2 */
281 mpadd(int len, mp_t *target, mp_t *m1, mp_t *m2, mp_t *mod)
285 for (i = 0; i < len; i++)
287 x += (mp2_t)m1[i] + m2[i];
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);
296 /* target = m1 - m2 (m1, m2 < mod). target may be m1 or m2 */
298 mpsub(int len, mp_t *target, mp_t *m1, mp_t *m2, mp_t *mod)
302 for (i = 0; i < len; i++)
304 x = (mp2_t)m1[i] - m2[i] - x;
306 x = x & ((mp2_t)1 << MP_T_BITS) ? 1 : 0;
310 for (x = 0, i = 0; i < len; i++)
312 x += (mp2_t)target[i] + mod[i];
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)
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 = ");
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))
342 if (!mpisless(ql, s, q) || mpiszero(ql, s))
344 tmp = mpnew(pl); /* note pl */
345 mpcpy(ql, tmp, q); /* tmp = q */
346 mpdec(ql, tmp); /* tmp-- */
347 mpdec(ql, tmp); /* tmp-- */
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 */
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 */
364 u2[0] = 1; /* u2 = 1 */
365 mpmul(ql, tmp, u2, pl, u1, q); /* tmp = u2 * u1 */
369 mpdump(ql, tmp, "res = ");
371 res = mpisequal(ql, tmp, r);
377 mprsa(int nl, mp_t *n, int el, mp_t *e, mp_t *m, mp_t *c)
382 mpdump(nl, n, "n = ");
383 mpdump(el, e, "e = ");
384 mpdump(nl, m, "m = ");
385 mpdump(nl, c, "c = ");
387 if (!mpisless(nl, m, n))
389 if (!mpisless(nl, c, n))
392 mppow(nl, tmp, m, el, e, n); /* tmp = m ^ e */
394 mpdump(nl, tmp, "res = ");
396 res = mpisequal(nl, tmp, c);
401 #if ENABLE_PGPVRFY_ED25519
402 # include "solv_ed25519.h"
405 /* create mp with size tbits from data with size dbits */
407 mpbuild(const unsigned char *d, int dbits, int tbits, int *mplp)
409 int l = (tbits + MP_T_BITS - 1) / MP_T_BITS;
410 mp_t *out = mpnew(l ? l : 1);
413 mpsetfrombe(l, out, d, (dbits + 7) / 8);
417 static const unsigned char *
418 findmpi(const unsigned char **mpip, int *mpilp, int maxbits, int *outlen)
421 const unsigned char *mpi = *mpip;
427 bits = mpi[0] << 8 | mpi[1];
428 l = 2 + (bits + 7) / 8;
429 if (bits > maxbits || mpil < l || (bits && !mpi[2]))
440 /* sig: 0:algo 1:hash 2-:mpidata */
441 /* pub: 0:algo 1-:mpidata */
443 solv_pgpvrfy(const unsigned char *pub, int publ, const unsigned char *sig, int sigl)
446 unsigned char *oid = 0;
447 const unsigned char *mpi;
451 if (!pub || !sig || publ < 1 || sigl < 2)
453 if (pub[0] != sig[0])
454 return 0; /* key algo mismatch */
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";
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";
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";
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";
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";
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";
482 return 0; /* unsupported hash algo */
484 if (sigl < 2 + hashl)
490 const unsigned char *n, *e, *m;
492 int nlen, elen, mlen, clen;
493 mp_t *nx, *ex, *mx, *cx;
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)
505 /* build padding block */
506 clen = (nlen - 1) / 8;
507 if (hashl + *oid + 2 > clen)
509 c = solv_malloc(clen);
510 memset(c, 0xff, clen);
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);
521 res = mprsa(nxl, nx, exl, ex, mx, cx);
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;
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)
547 hlen = (qlen + 7) & ~7;
548 if (hlen > hashl * 8)
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);
567 #if ENABLE_PGPVRFY_ED25519
570 unsigned char sigdata[64];
571 const unsigned char *r, *s;
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)
580 mpi = sig + 2 + hashl;
581 mpil = sigl - (2 + hashl);
582 r = findmpi(&mpi, &mpil, 256, &rlen);
583 s = findmpi(&mpi, &mpil, 256, &slen);
586 memset(sigdata, 0, 64);
587 rlen = (rlen + 7) / 8;
588 slen = (slen + 7) / 8;
590 memcpy(sigdata + 32 - rlen, r, rlen);
592 memcpy(sigdata + 64 - slen, s, rlen);
593 res = mped25519(pub + 1 + 10 + 2 + 1, sigdata, sig + 2, hashl);
598 return 0; /* unsupported pubkey algo */