asn1/a_int.c: remove code duplicate and optimize branches,
[openssl.git] / crypto / asn1 / a_int.c
1 /*
2  * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the OpenSSL license (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #include <stdio.h>
11 #include "internal/cryptlib.h"
12 #include "internal/numbers.h"
13 #include <limits.h>
14 #include <openssl/asn1.h>
15 #include <openssl/bn.h>
16 #include "asn1_locl.h"
17
18 ASN1_INTEGER *ASN1_INTEGER_dup(const ASN1_INTEGER *x)
19 {
20     return ASN1_STRING_dup(x);
21 }
22
23 int ASN1_INTEGER_cmp(const ASN1_INTEGER *x, const ASN1_INTEGER *y)
24 {
25     int neg, ret;
26     /* Compare signs */
27     neg = x->type & V_ASN1_NEG;
28     if (neg != (y->type & V_ASN1_NEG)) {
29         if (neg)
30             return -1;
31         else
32             return 1;
33     }
34
35     ret = ASN1_STRING_cmp(x, y);
36
37     if (neg)
38         return -ret;
39     else
40         return ret;
41 }
42
43 /*-
44  * This converts a big endian buffer and sign into its content encoding.
45  * This is used for INTEGER and ENUMERATED types.
46  * The internal representation is an ASN1_STRING whose data is a big endian
47  * representation of the value, ignoring the sign. The sign is determined by
48  * the type: if type & V_ASN1_NEG is true it is negative, otherwise positive.
49  *
50  * Positive integers are no problem: they are almost the same as the DER
51  * encoding, except if the first byte is >= 0x80 we need to add a zero pad.
52  *
53  * Negative integers are a bit trickier...
54  * The DER representation of negative integers is in 2s complement form.
55  * The internal form is converted by complementing each octet and finally
56  * adding one to the result. This can be done less messily with a little trick.
57  * If the internal form has trailing zeroes then they will become FF by the
58  * complement and 0 by the add one (due to carry) so just copy as many trailing
59  * zeros to the destination as there are in the source. The carry will add one
60  * to the last none zero octet: so complement this octet and add one and finally
61  * complement any left over until you get to the start of the string.
62  *
63  * Padding is a little trickier too. If the first bytes is > 0x80 then we pad
64  * with 0xff. However if the first byte is 0x80 and one of the following bytes
65  * is non-zero we pad with 0xff. The reason for this distinction is that 0x80
66  * followed by optional zeros isn't padded.
67  */
68
69 /*
70  * If |pad| is zero, the operation is effectively reduced to memcpy,
71  * and if |pad| is 0xff, then it performs two's complement, ~dst + 1.
72  * Note that in latter case sequence of zeros yields itself, and so
73  * does 0x80 followed by any number of zeros. These properties are
74  * used elsewhere below...
75  */
76 static void twos_complement(unsigned char *dst, const unsigned char *src,
77                             size_t len, unsigned char pad)
78 {
79     unsigned int carry = pad & 1;
80
81     /* Begin at the end of the encoding */
82     dst += len;
83     src += len;
84     /* two's complement value: ~value + 1 */
85     while (len-- != 0) {
86         *(--dst) = (unsigned char)(carry += *(--src) ^ pad);
87         carry >>= 8;
88     }
89 }
90
91 static size_t i2c_ibuf(const unsigned char *b, size_t blen, int neg,
92                        unsigned char **pp)
93 {
94     unsigned int pad = 0;
95     size_t ret, i;
96     unsigned char *p, pb = 0;
97
98     if (b != NULL && blen) {
99         ret = blen;
100         i = b[0];
101         if (!neg && (i > 127)) {
102             pad = 1;
103             pb = 0;
104         } else if (neg) {
105             pb = 0xFF;
106             if (i > 128) {
107                 pad = 1;
108             } else if (i == 128) {
109                 /*
110                  * Special case [of minimal negative for given length]:
111                  * if any other bytes non zero we pad, otherwise we don't.
112                  */
113                 for (pad = 0, i = 1; i < blen; i++)
114                     pad |= b[i];
115                 pb = pad != 0 ? 0xffU : 0;
116                 pad = pb & 1;
117             }
118         }
119         ret += pad;
120     } else {
121         ret = 1;
122         blen = 0;   /* reduce '(b == NULL || blen == 0)' to '(blen == 0)' */
123     }
124
125     if (pp == NULL || (p = *pp) == NULL)
126         return ret;
127
128     /*
129      * This magically handles all corner cases, such as '(b == NULL ||
130      * blen == 0)', non-negative value, "negative" zero, 0x80 followed
131      * by any number of zeros...
132      */
133     *p = pb;
134     p += pad;       /* yes, p[0] can be written twice, but it's little
135                      * price to pay for eliminated branches */
136     twos_complement(p, b, blen, pb);
137
138     *pp += ret;
139     return ret;
140 }
141
142 /*
143  * convert content octets into a big endian buffer. Returns the length
144  * of buffer or 0 on error: for malformed INTEGER. If output buffer is
145  * NULL just return length.
146  */
147
148 static size_t c2i_ibuf(unsigned char *b, int *pneg,
149                        const unsigned char *p, size_t plen)
150 {
151     int neg, pad;
152     /* Zero content length is illegal */
153     if (plen == 0) {
154         ASN1err(ASN1_F_C2I_IBUF, ASN1_R_ILLEGAL_ZERO_CONTENT);
155         return 0;
156     }
157     neg = p[0] & 0x80;
158     if (pneg)
159         *pneg = neg;
160     /* Handle common case where length is 1 octet separately */
161     if (plen == 1) {
162         if (b != NULL) {
163             if (neg)
164                 b[0] = (p[0] ^ 0xFF) + 1;
165             else
166                 b[0] = p[0];
167         }
168         return 1;
169     }
170     if (p[0] == 0 || p[0] == 0xFF)
171         pad = 1;
172     else
173         pad = 0;
174     /* reject illegal padding: first two octets MSB can't match */
175     if (pad && (neg == (p[1] & 0x80))) {
176         ASN1err(ASN1_F_C2I_IBUF, ASN1_R_ILLEGAL_PADDING);
177         return 0;
178     }
179
180     /* skip over pad */
181     p += pad;
182     plen -= pad;
183
184     if (b != NULL)
185         twos_complement(b, p, plen, neg ? 0xffU : 0);
186
187     return plen;
188 }
189
190 int i2c_ASN1_INTEGER(ASN1_INTEGER *a, unsigned char **pp)
191 {
192     return i2c_ibuf(a->data, a->length, a->type & V_ASN1_NEG, pp);
193 }
194
195 /* Convert big endian buffer into uint64_t, return 0 on error */
196 static int asn1_get_uint64(uint64_t *pr, const unsigned char *b, size_t blen)
197 {
198     size_t i;
199     if (blen > sizeof(*pr)) {
200         ASN1err(ASN1_F_ASN1_GET_UINT64, ASN1_R_TOO_LARGE);
201         return 0;
202     }
203     *pr = 0;
204     if (b == NULL)
205         return 0;
206     for (i = 0; i < blen; i++) {
207         *pr <<= 8;
208         *pr |= b[i];
209     }
210     return 1;
211 }
212
213 static size_t asn1_put_uint64(unsigned char *b, uint64_t r)
214 {
215     if (r >= 0x100) {
216         unsigned char *p;
217         uint64_t rtmp = r;
218         size_t i = 0;
219
220         /* Work out how many bytes we need */
221         while (rtmp) {
222             rtmp >>= 8;
223             i++;
224         }
225
226         /* Copy from end to beginning */
227         p = b + i - 1;
228
229         do {
230             *p-- = r & 0xFF;
231             r >>= 8;
232         } while (p >= b);
233
234         return i;
235     }
236
237     b[0] = (unsigned char)r;
238     return 1;
239
240 }
241
242 /*
243  * Absolute value of INT64_MIN: we can't just use -INT64_MIN as it produces
244  * overflow warnings.
245  */
246
247 #define ABS_INT64_MIN \
248     ((uint64_t)INT64_MAX + (uint64_t)(-(INT64_MIN + INT64_MAX)))
249
250 /* signed version of asn1_get_uint64 */
251 static int asn1_get_int64(int64_t *pr, const unsigned char *b, size_t blen,
252                           int neg)
253 {
254     uint64_t r;
255     if (asn1_get_uint64(&r, b, blen) == 0)
256         return 0;
257     if (neg) {
258         if (r > ABS_INT64_MIN) {
259             ASN1err(ASN1_F_ASN1_GET_INT64, ASN1_R_TOO_SMALL);
260             return 0;
261         }
262         *pr = 0 - (uint64_t)r;
263     } else {
264         if (r > INT64_MAX) {
265             ASN1err(ASN1_F_ASN1_GET_INT64, ASN1_R_TOO_LARGE);
266             return 0;
267         }
268         *pr = (int64_t)r;
269     }
270     return 1;
271 }
272
273 /* Convert ASN1 INTEGER content octets to ASN1_INTEGER structure */
274 ASN1_INTEGER *c2i_ASN1_INTEGER(ASN1_INTEGER **a, const unsigned char **pp,
275                                long len)
276 {
277     ASN1_INTEGER *ret = NULL;
278     size_t r;
279     int neg;
280
281     r = c2i_ibuf(NULL, NULL, *pp, len);
282
283     if (r == 0)
284         return NULL;
285
286     if ((a == NULL) || ((*a) == NULL)) {
287         ret = ASN1_INTEGER_new();
288         if (ret == NULL)
289             return NULL;
290         ret->type = V_ASN1_INTEGER;
291     } else
292         ret = *a;
293
294     if (ASN1_STRING_set(ret, NULL, r) == 0)
295         goto err;
296
297     c2i_ibuf(ret->data, &neg, *pp, len);
298
299     if (neg)
300         ret->type |= V_ASN1_NEG;
301
302     *pp += len;
303     if (a != NULL)
304         (*a) = ret;
305     return ret;
306  err:
307     ASN1err(ASN1_F_C2I_ASN1_INTEGER, ERR_R_MALLOC_FAILURE);
308     if ((a == NULL) || (*a != ret))
309         ASN1_INTEGER_free(ret);
310     return NULL;
311 }
312
313 static int asn1_string_get_int64(int64_t *pr, const ASN1_STRING *a, int itype)
314 {
315     if (a == NULL) {
316         ASN1err(ASN1_F_ASN1_STRING_GET_INT64, ERR_R_PASSED_NULL_PARAMETER);
317         return 0;
318     }
319     if ((a->type & ~V_ASN1_NEG) != itype) {
320         ASN1err(ASN1_F_ASN1_STRING_GET_INT64, ASN1_R_WRONG_INTEGER_TYPE);
321         return 0;
322     }
323     return asn1_get_int64(pr, a->data, a->length, a->type & V_ASN1_NEG);
324 }
325
326 static int asn1_string_set_int64(ASN1_STRING *a, int64_t r, int itype)
327 {
328     unsigned char tbuf[sizeof(r)];
329     size_t l;
330     a->type = itype;
331     if (r < 0) {
332         l = asn1_put_uint64(tbuf, -r);
333         a->type |= V_ASN1_NEG;
334     } else {
335         l = asn1_put_uint64(tbuf, r);
336         a->type &= ~V_ASN1_NEG;
337     }
338     if (l == 0)
339         return 0;
340     return ASN1_STRING_set(a, tbuf, l);
341 }
342
343 static int asn1_string_get_uint64(uint64_t *pr, const ASN1_STRING *a,
344                                   int itype)
345 {
346     if (a == NULL) {
347         ASN1err(ASN1_F_ASN1_STRING_GET_UINT64, ERR_R_PASSED_NULL_PARAMETER);
348         return 0;
349     }
350     if ((a->type & ~V_ASN1_NEG) != itype) {
351         ASN1err(ASN1_F_ASN1_STRING_GET_UINT64, ASN1_R_WRONG_INTEGER_TYPE);
352         return 0;
353     }
354     if (a->type & V_ASN1_NEG) {
355         ASN1err(ASN1_F_ASN1_STRING_GET_UINT64, ASN1_R_ILLEGAL_NEGATIVE_VALUE);
356         return 0;
357     }
358     return asn1_get_uint64(pr, a->data, a->length);
359 }
360
361 static int asn1_string_set_uint64(ASN1_STRING *a, uint64_t r, int itype)
362 {
363     unsigned char tbuf[sizeof(r)];
364     size_t l;
365     a->type = itype;
366     l = asn1_put_uint64(tbuf, r);
367     if (l == 0)
368         return 0;
369     return ASN1_STRING_set(a, tbuf, l);
370 }
371
372 /*
373  * This is a version of d2i_ASN1_INTEGER that ignores the sign bit of ASN1
374  * integers: some broken software can encode a positive INTEGER with its MSB
375  * set as negative (it doesn't add a padding zero).
376  */
377
378 ASN1_INTEGER *d2i_ASN1_UINTEGER(ASN1_INTEGER **a, const unsigned char **pp,
379                                 long length)
380 {
381     ASN1_INTEGER *ret = NULL;
382     const unsigned char *p;
383     unsigned char *s;
384     long len;
385     int inf, tag, xclass;
386     int i;
387
388     if ((a == NULL) || ((*a) == NULL)) {
389         if ((ret = ASN1_INTEGER_new()) == NULL)
390             return (NULL);
391         ret->type = V_ASN1_INTEGER;
392     } else
393         ret = (*a);
394
395     p = *pp;
396     inf = ASN1_get_object(&p, &len, &tag, &xclass, length);
397     if (inf & 0x80) {
398         i = ASN1_R_BAD_OBJECT_HEADER;
399         goto err;
400     }
401
402     if (tag != V_ASN1_INTEGER) {
403         i = ASN1_R_EXPECTING_AN_INTEGER;
404         goto err;
405     }
406
407     /*
408      * We must OPENSSL_malloc stuff, even for 0 bytes otherwise it signifies
409      * a missing NULL parameter.
410      */
411     s = OPENSSL_malloc((int)len + 1);
412     if (s == NULL) {
413         i = ERR_R_MALLOC_FAILURE;
414         goto err;
415     }
416     ret->type = V_ASN1_INTEGER;
417     if (len) {
418         if ((*p == 0) && (len != 1)) {
419             p++;
420             len--;
421         }
422         memcpy(s, p, (int)len);
423         p += len;
424     }
425
426     OPENSSL_free(ret->data);
427     ret->data = s;
428     ret->length = (int)len;
429     if (a != NULL)
430         (*a) = ret;
431     *pp = p;
432     return (ret);
433  err:
434     ASN1err(ASN1_F_D2I_ASN1_UINTEGER, i);
435     if ((a == NULL) || (*a != ret))
436         ASN1_INTEGER_free(ret);
437     return (NULL);
438 }
439
440 static ASN1_STRING *bn_to_asn1_string(const BIGNUM *bn, ASN1_STRING *ai,
441                                       int atype)
442 {
443     ASN1_INTEGER *ret;
444     int len;
445
446     if (ai == NULL) {
447         ret = ASN1_STRING_type_new(atype);
448     } else {
449         ret = ai;
450         ret->type = atype;
451     }
452
453     if (ret == NULL) {
454         ASN1err(ASN1_F_BN_TO_ASN1_STRING, ERR_R_NESTED_ASN1_ERROR);
455         goto err;
456     }
457
458     if (BN_is_negative(bn) && !BN_is_zero(bn))
459         ret->type |= V_ASN1_NEG_INTEGER;
460
461     len = BN_num_bytes(bn);
462
463     if (len == 0)
464         len = 1;
465
466     if (ASN1_STRING_set(ret, NULL, len) == 0) {
467         ASN1err(ASN1_F_BN_TO_ASN1_STRING, ERR_R_MALLOC_FAILURE);
468         goto err;
469     }
470
471     /* Correct zero case */
472     if (BN_is_zero(bn))
473         ret->data[0] = 0;
474     else
475         len = BN_bn2bin(bn, ret->data);
476     ret->length = len;
477     return ret;
478  err:
479     if (ret != ai)
480         ASN1_INTEGER_free(ret);
481     return (NULL);
482 }
483
484 static BIGNUM *asn1_string_to_bn(const ASN1_INTEGER *ai, BIGNUM *bn,
485                                  int itype)
486 {
487     BIGNUM *ret;
488
489     if ((ai->type & ~V_ASN1_NEG) != itype) {
490         ASN1err(ASN1_F_ASN1_STRING_TO_BN, ASN1_R_WRONG_INTEGER_TYPE);
491         return NULL;
492     }
493
494     ret = BN_bin2bn(ai->data, ai->length, bn);
495     if (ret == NULL) {
496         ASN1err(ASN1_F_ASN1_STRING_TO_BN, ASN1_R_BN_LIB);
497         return NULL;
498     }
499     if (ai->type & V_ASN1_NEG)
500         BN_set_negative(ret, 1);
501     return ret;
502 }
503
504 int ASN1_INTEGER_get_int64(int64_t *pr, const ASN1_INTEGER *a)
505 {
506     return asn1_string_get_int64(pr, a, V_ASN1_INTEGER);
507 }
508
509 int ASN1_INTEGER_set_int64(ASN1_INTEGER *a, int64_t r)
510 {
511     return asn1_string_set_int64(a, r, V_ASN1_INTEGER);
512 }
513
514 int ASN1_INTEGER_get_uint64(uint64_t *pr, const ASN1_INTEGER *a)
515 {
516     return asn1_string_get_uint64(pr, a, V_ASN1_INTEGER);
517 }
518
519 int ASN1_INTEGER_set_uint64(ASN1_INTEGER *a, uint64_t r)
520 {
521     return asn1_string_set_uint64(a, r, V_ASN1_INTEGER);
522 }
523
524 int ASN1_INTEGER_set(ASN1_INTEGER *a, long v)
525 {
526     return ASN1_INTEGER_set_int64(a, v);
527 }
528
529 long ASN1_INTEGER_get(const ASN1_INTEGER *a)
530 {
531     int i;
532     int64_t r;
533     if (a == NULL)
534         return 0;
535     i = ASN1_INTEGER_get_int64(&r, a);
536     if (i == 0)
537         return -1;
538     if (r > LONG_MAX || r < LONG_MIN)
539         return -1;
540     return (long)r;
541 }
542
543 ASN1_INTEGER *BN_to_ASN1_INTEGER(const BIGNUM *bn, ASN1_INTEGER *ai)
544 {
545     return bn_to_asn1_string(bn, ai, V_ASN1_INTEGER);
546 }
547
548 BIGNUM *ASN1_INTEGER_to_BN(const ASN1_INTEGER *ai, BIGNUM *bn)
549 {
550     return asn1_string_to_bn(ai, bn, V_ASN1_INTEGER);
551 }
552
553 int ASN1_ENUMERATED_get_int64(int64_t *pr, const ASN1_ENUMERATED *a)
554 {
555     return asn1_string_get_int64(pr, a, V_ASN1_ENUMERATED);
556 }
557
558 int ASN1_ENUMERATED_set_int64(ASN1_ENUMERATED *a, int64_t r)
559 {
560     return asn1_string_set_int64(a, r, V_ASN1_ENUMERATED);
561 }
562
563 int ASN1_ENUMERATED_set(ASN1_ENUMERATED *a, long v)
564 {
565     return ASN1_ENUMERATED_set_int64(a, v);
566 }
567
568 long ASN1_ENUMERATED_get(const ASN1_ENUMERATED *a)
569 {
570     int i;
571     int64_t r;
572     if (a == NULL)
573         return 0;
574     if ((a->type & ~V_ASN1_NEG) != V_ASN1_ENUMERATED)
575         return -1;
576     if (a->length > (int)sizeof(long))
577         return 0xffffffffL;
578     i = ASN1_ENUMERATED_get_int64(&r, a);
579     if (i == 0)
580         return -1;
581     if (r > LONG_MAX || r < LONG_MIN)
582         return -1;
583     return (long)r;
584 }
585
586 ASN1_ENUMERATED *BN_to_ASN1_ENUMERATED(const BIGNUM *bn, ASN1_ENUMERATED *ai)
587 {
588     return bn_to_asn1_string(bn, ai, V_ASN1_ENUMERATED);
589 }
590
591 BIGNUM *ASN1_ENUMERATED_to_BN(const ASN1_ENUMERATED *ai, BIGNUM *bn)
592 {
593     return asn1_string_to_bn(ai, bn, V_ASN1_ENUMERATED);
594 }
595
596 /* Internal functions used by x_int64.c */
597 int c2i_uint64_int(uint64_t *ret, int *neg, const unsigned char **pp, long len)
598 {
599     unsigned char buf[sizeof(uint64_t)];
600     size_t buflen;
601
602     buflen = c2i_ibuf(NULL, NULL, *pp, len);
603     if (buflen == 0)
604         return 0;
605     if (buflen > sizeof(uint64_t)) {
606         ASN1err(ASN1_F_C2I_UINT64_INT, ASN1_R_TOO_LARGE);
607         return 0;
608     }
609     (void)c2i_ibuf(buf, neg, *pp, len);
610     return asn1_get_uint64(ret, buf, buflen);
611 }
612
613 int i2c_uint64_int(unsigned char *p, uint64_t r, int neg)
614 {
615     unsigned char buf[sizeof(uint64_t)];
616     size_t buflen;
617
618     buflen = asn1_put_uint64(buf, r);
619     return i2c_ibuf(buf, buflen, neg, &p);
620 }
621