1/*
2 * Copyright (c) 2009 Kungliga Tekniska Högskolan
3 * (Royal Institute of Technology, Stockholm, Sweden).
4 * All rights reserved.
5 *
6 * Portions Copyright (c) 2009 - 2010 Apple Inc. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 *    notice, this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 *
19 * 3. Neither the name of the Institute nor the names of its contributors
20 *    may be used to endorse or promote products derived from this software
21 *    without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 */
35
36#include "der_locl.h"
37#include <com_err.h>
38
39enum trigger_method { FOFF, FRANDOM, FLINEAR, FLINEAR_SIZE };
40
41#ifdef ASN1_FUZZER
42static enum trigger_method method = FOFF;
43
44/* FLINEAR */
45static unsigned long fnum, fcur, fsize;
46#endif
47
48int
49asn1_fuzzer_method(const char *mode)
50{
51#ifdef ASN1_FUZZER
52    if (mode == NULL || strcasecmp(mode, "off") == 0) {
53	method = FOFF;
54    } else if (strcasecmp(mode, "random") == 0) {
55	method = FRANDOM;
56    } else if (strcasecmp(mode, "linear") == 0) {
57	method = FLINEAR;
58    } else if (strcasecmp(mode, "linear-size") == 0) {
59	method = FLINEAR_SIZE;
60    } else
61	return 1;
62    return 0;
63#else
64    return 1;
65#endif
66}
67
68void
69asn1_fuzzer_reset(void)
70{
71#ifdef ASN1_FUZZER
72    fcur = 0;
73    fsize = 0;
74    fnum = 0;
75#endif
76}
77
78void
79asn1_fuzzer_next(void)
80{
81#ifdef ASN1_FUZZER
82    fcur = 0;
83    fsize = 0;
84    fnum++;
85#endif
86}
87
88int
89asn1_fuzzer_done(void)
90{
91#ifndef ASN1_FUZZER
92    abort();
93#else
94    /* since code paths */
95    return (fnum > 10000);
96#endif
97}
98
99#ifdef ASN1_FUZZER
100
101static int
102fuzzer_trigger(unsigned int chance)
103{
104    switch(method) {
105    case FOFF:
106	return 0;
107    case FRANDOM:
108	if ((rk_random() % chance) != 1)
109	    return 0;
110	return 1;
111    case FLINEAR:
112	if (fnum == fcur++)
113	    return 1;
114	return 0;
115    case FLINEAR_SIZE:
116	return 0;
117    }
118    return 0;
119}
120
121static int
122fuzzer_size_trigger(unsigned long *cur)
123{
124    if (method != FLINEAR_SIZE)
125	return 0;
126    if (fnum == (*cur)++)
127	return 1;
128    return 0;
129}
130
131static size_t
132fuzzer_length_len (size_t len)
133{
134    if (fuzzer_size_trigger(&fsize)) {
135	len = 0;
136    } else if (fuzzer_size_trigger(&fsize)) {
137	len = 129;
138    } else if (fuzzer_size_trigger(&fsize)) {
139	len = 0xffff;
140    }
141
142    if (len < 128)
143	return 1;
144    else {
145	int ret = 0;
146	do {
147	    ++ret;
148	    len /= 256;
149	} while (len);
150	return ret + 1;
151    }
152}
153
154static int
155fuzzer_put_length (unsigned char *p, size_t len, size_t val, size_t *size)
156{
157    if (len < 1)
158	return ASN1_OVERFLOW;
159
160    if (fuzzer_size_trigger(&fcur)) {
161	val = 0;
162    } else if (fuzzer_size_trigger(&fcur)) {
163	val = 129;
164    } else if (fuzzer_size_trigger(&fcur)) {
165	val = 0xffff;
166    }
167
168    if (val < 128) {
169	*p = val;
170	*size = 1;
171    } else {
172	size_t l = 0;
173
174	while(val > 0) {
175	    if(len < 2)
176		return ASN1_OVERFLOW;
177	    *p-- = val % 256;
178	    val /= 256;
179	    len--;
180	    l++;
181	}
182	*p = 0x80 | l;
183	if(size)
184	    *size = l + 1;
185    }
186    return 0;
187}
188
189static int
190fuzzer_put_tag (unsigned char *p, size_t len, Der_class class, Der_type type,
191		unsigned int tag, size_t *size)
192{
193    unsigned fcont = 0;
194
195    if (tag <= 30) {
196	if (len < 1)
197	    return ASN1_OVERFLOW;
198	if (fuzzer_trigger(100))
199	    *p = MAKE_TAG(class, type, 0x1f);
200	else
201	    *p = MAKE_TAG(class, type, tag);
202	*size = 1;
203    } else {
204	size_t ret = 0;
205	unsigned int continuation = 0;
206
207	do {
208	    if (len < 1)
209		return ASN1_OVERFLOW;
210	    *p-- = tag % 128 | continuation;
211	    len--;
212	    ret++;
213	    tag /= 128;
214	    continuation = 0x80;
215	} while(tag > 0);
216	if (len < 1)
217	    return ASN1_OVERFLOW;
218	if (fuzzer_trigger(100))
219	    *p-- = MAKE_TAG(class, type, 0);
220	else
221	    *p-- = MAKE_TAG(class, type, 0x1f);
222	ret++;
223	*size = ret;
224    }
225    return 0;
226}
227
228static int
229fuzzer_put_length_and_tag (unsigned char *p, size_t len, size_t len_val,
230			   Der_class class, Der_type type,
231			   unsigned int tag, size_t *size)
232{
233    size_t ret = 0;
234    size_t l;
235    int e;
236
237    e = fuzzer_put_length (p, len, len_val, &l);
238    if(e)
239	return e;
240    p -= l;
241    len -= l;
242    ret += l;
243    e = fuzzer_put_tag (p, len, class, type, tag, &l);
244    if(e)
245	return e;
246
247    ret += l;
248    *size = ret;
249    return 0;
250}
251
252static int
253fuzzer_put_general_string (unsigned char *p, size_t len,
254			   const heim_general_string *str, size_t *size)
255{
256    size_t slen = strlen(*str);
257
258    if (len < slen)
259	return ASN1_OVERFLOW;
260    p -= slen;
261    if (slen >= 2 && fuzzer_trigger(100)) {
262	memcpy(p+1, *str, slen);
263	memcpy(p+1, "%s", 2);
264    } else if (slen >= 2 && fuzzer_trigger(100)) {
265	memcpy(p+1, *str, slen);
266	memcpy(p+1, "%n", 2);
267    } else if (slen >= 4 && fuzzer_trigger(100)) {
268	memcpy(p+1, *str, slen);
269	memcpy(p+1, "%10n", 4);
270    } else if (slen >= 10 && fuzzer_trigger(100)) {
271	memcpy(p+1, *str, slen);
272	memcpy(p+1, "%n%n%n%n%n", 10);
273    } else if (slen >= 10 && fuzzer_trigger(100)) {
274	memcpy(p+1, *str, slen);
275	memcpy(p+1, "%n%p%s%d%x", 10);
276    } else if (slen >= 7 && fuzzer_trigger(100)) {
277	memcpy(p+1, *str, slen);
278	memcpy(p+1, "%.1024d", 7);
279    } else if (slen >= 7 && fuzzer_trigger(100)) {
280	memcpy(p+1, *str, slen);
281	memcpy(p+1, "%.2049d", 7);
282    } else if (fuzzer_trigger(100)) {
283	memset(p+1, 0, slen);
284    } else if (fuzzer_trigger(100)) {
285	memset(p+1, 0xff, slen);
286    } else if (fuzzer_trigger(100)) {
287	memset(p+1, 'A', slen);
288    } else {
289	memcpy(p+1, *str, slen);
290    }
291    *size = slen;
292    return 0;
293}
294
295
296struct asn1_type_func fuzzerprim[A1T_NUM_ENTRY] = {
297#define fuzel(name, type) {				\
298	(asn1_type_encode)fuzzer_put_##name,		\
299	(asn1_type_decode)der_get_##name,		\
300	(asn1_type_length)der_length_##name,		\
301	(asn1_type_copy)der_copy_##name,		\
302	(asn1_type_release)der_free_##name,		\
303	sizeof(type)					\
304    }
305#define el(name, type) {				\
306	(asn1_type_encode)der_put_##name,		\
307	(asn1_type_decode)der_get_##name,		\
308	(asn1_type_length)der_length_##name,		\
309	(asn1_type_copy)der_copy_##name,		\
310	(asn1_type_release)der_free_##name,		\
311	sizeof(type)					\
312    }
313#define elber(name, type) {				\
314	(asn1_type_encode)der_put_##name,		\
315	(asn1_type_decode)der_get_##name##_ber,		\
316	(asn1_type_length)der_length_##name,		\
317	(asn1_type_copy)der_copy_##name,		\
318	(asn1_type_release)der_free_##name,		\
319	sizeof(type)					\
320    }
321    el(integer, int),
322    el(heim_integer, heim_integer),
323    el(integer, int),
324    el(unsigned, unsigned),
325    fuzel(general_string, heim_general_string),
326    el(octet_string, heim_octet_string),
327    elber(octet_string, heim_octet_string),
328    el(ia5_string, heim_ia5_string),
329    el(bmp_string, heim_bmp_string),
330    el(universal_string, heim_universal_string),
331    el(printable_string, heim_printable_string),
332    el(visible_string, heim_visible_string),
333    el(utf8string, heim_utf8_string),
334    el(generalized_time, time_t),
335    el(utctime, time_t),
336    el(bit_string, heim_bit_string),
337    { (asn1_type_encode)der_put_boolean, (asn1_type_decode)der_get_boolean,
338      (asn1_type_length)der_length_boolean, (asn1_type_copy)der_copy_integer,
339      (asn1_type_release)der_free_integer, sizeof(int)
340    },
341    el(oid, heim_oid),
342    el(general_string, heim_general_string),
343#undef fuzel
344#undef el
345#undef elber
346};
347
348
349
350int
351_asn1_encode_fuzzer(const struct asn1_template *t,
352		    unsigned char *p, size_t len,
353		    const void *data, size_t *size)
354{
355    size_t elements = A1_HEADER_LEN(t);
356    int ret = 0;
357    size_t oldlen = len;
358
359    t += A1_HEADER_LEN(t);
360
361    while (elements) {
362	switch (t->tt & A1_OP_MASK) {
363	case A1_OP_TYPE:
364	case A1_OP_TYPE_EXTERN: {
365	    size_t newsize;
366	    const void *el = DPOC(data, t->offset);
367
368	    if (t->tt & A1_FLAG_OPTIONAL) {
369		void **pel = (void **)el;
370		if (*pel == NULL)
371		    break;
372		el = *pel;
373	    }
374
375	    if ((t->tt & A1_OP_MASK) == A1_OP_TYPE) {
376		ret = _asn1_encode_fuzzer(t->ptr, p, len, el, &newsize);
377	    } else {
378		const struct asn1_type_func *f = t->ptr;
379		ret = (f->encode)(p, len, el, &newsize);
380	    }
381
382	    if (ret)
383		return ret;
384	    p -= newsize; len -= newsize;
385
386	    break;
387	}
388	case A1_OP_TAG: {
389	    const void *olddata = data;
390	    size_t l, datalen;
391
392	    data = DPOC(data, t->offset);
393
394	    if (t->tt & A1_FLAG_OPTIONAL) {
395		void **el = (void **)data;
396		if (*el == NULL) {
397		    data = olddata;
398		    break;
399		}
400		data = *el;
401	    }
402
403	    ret = _asn1_encode_fuzzer(t->ptr, p, len, data, &datalen);
404	    if (ret)
405		return ret;
406
407	    len -= datalen; p -= datalen;
408
409	    ret = fuzzer_put_length_and_tag(p, len, datalen,
410					    A1_TAG_CLASS(t->tt),
411					    A1_TAG_TYPE(t->tt),
412					    A1_TAG_TAG(t->tt), &l);
413	    if (ret)
414		return ret;
415
416	    p -= l; len -= l;
417
418	    data = olddata;
419
420	    break;
421	}
422	case A1_OP_PARSE: {
423	    unsigned int type = A1_PARSE_TYPE(t->tt);
424	    size_t newsize;
425	    const void *el = DPOC(data, t->offset);
426
427	    if (type > sizeof(fuzzerprim)/sizeof(fuzzerprim[0])) {
428		ABORT_ON_ERROR();
429		return ASN1_PARSE_ERROR;
430	    }
431
432	    ret = (fuzzerprim[type].encode)(p, len, el, &newsize);
433	    if (ret)
434		return ret;
435	    p -= newsize; len -= newsize;
436
437	    break;
438	}
439	case A1_OP_SETOF: {
440	    const struct template_of *el = DPOC(data, t->offset);
441	    size_t ellen = _asn1_sizeofType(t->ptr);
442	    heim_octet_string *val;
443	    unsigned char *elptr = el->val;
444	    size_t i, totallen;
445
446	    if (el->len == 0)
447		break;
448
449	    if (el->len > UINT_MAX/sizeof(val[0]))
450		return ERANGE;
451
452	    val = malloc(sizeof(val[0]) * el->len);
453	    if (val == NULL)
454		return ENOMEM;
455
456	    for(totallen = 0, i = 0; i < el->len; i++) {
457		unsigned char *next;
458		size_t l;
459
460		val[i].length = _asn1_length(t->ptr, elptr);
461		val[i].data = malloc(val[i].length);
462
463		ret = _asn1_encode_fuzzer(t->ptr, DPO(val[i].data, val[i].length - 1),
464					  val[i].length, elptr, &l);
465		if (ret)
466		    break;
467
468		next = elptr + ellen;
469		if (next < elptr) {
470		    ret = ASN1_OVERFLOW;
471		    break;
472		}
473		elptr = next;
474		totallen += val[i].length;
475	    }
476	    if (ret == 0 && totallen > len)
477		ret = ASN1_OVERFLOW;
478	    if (ret) {
479		do {
480		    free(val[i].data);
481		} while(i-- > 0);
482		free(val);
483		return ret;
484	    }
485
486	    len -= totallen;
487
488	    qsort(val, el->len, sizeof(val[0]), _heim_der_set_sort);
489
490	    i = el->len - 1;
491	    do {
492		p -= val[i].length;
493		memcpy(p + 1, val[i].data, val[i].length);
494		free(val[i].data);
495	    } while(i-- > 0);
496	    free(val);
497
498	    break;
499
500	}
501	case A1_OP_SEQOF: {
502	    struct template_of *el = DPO(data, t->offset);
503	    size_t ellen = _asn1_sizeofType(t->ptr);
504	    size_t newsize;
505	    unsigned int i;
506	    unsigned char *elptr = el->val;
507
508	    if (el->len == 0)
509		break;
510
511	    elptr += ellen * (el->len - 1);
512
513	    for (i = 0; i < el->len; i++) {
514		ret = _asn1_encode_fuzzer(t->ptr, p, len,
515				   elptr,
516				   &newsize);
517		if (ret)
518		    return ret;
519		p -= newsize; len -= newsize;
520		elptr -= ellen;
521	    }
522
523	    break;
524	}
525	case A1_OP_BMEMBER: {
526	    const struct asn1_template *bmember = t->ptr;
527	    size_t size = bmember->offset;
528	    size_t elements = A1_HEADER_LEN(bmember);
529	    size_t pos;
530	    unsigned char c = 0;
531	    unsigned int bitset = 0;
532	    int rfc1510 = (bmember->tt & A1_HBF_RFC1510);
533
534	    bmember += elements;
535
536	    if (rfc1510)
537		pos = 31;
538	    else
539		pos = bmember->offset;
540
541	    while (elements && len) {
542		while (bmember->offset / 8 < pos / 8) {
543		    if (rfc1510 || bitset || c) {
544			if (len < 1)
545			    return ASN1_OVERFLOW;
546			*p-- = c; len--;
547		    }
548		    c = 0;
549		    pos -= 8;
550		}
551		_asn1_bmember_put_bit(&c, data, bmember->offset, size, &bitset);
552		elements--; bmember--;
553	    }
554	    if (rfc1510 || bitset) {
555		if (len < 1)
556		    return ASN1_OVERFLOW;
557		*p-- = c; len--;
558	    }
559
560	    if (len < 1)
561		return ASN1_OVERFLOW;
562	    if (rfc1510 || bitset == 0)
563		*p-- = 0;
564	    else
565		*p-- = bitset - 1;
566
567	    len--;
568
569	    break;
570	}
571	case A1_OP_CHOICE: {
572	    const struct asn1_template *choice = t->ptr;
573	    const unsigned int *element = DPOC(data, choice->offset);
574	    size_t datalen;
575	    const void *el;
576
577	    if (*element > A1_HEADER_LEN(choice)) {
578		printf("element: %d\n", *element);
579		return ASN1_PARSE_ERROR;
580	    }
581
582	    if (*element == 0) {
583		ret += der_put_octet_string(p, len,
584					    DPOC(data, choice->tt), &datalen);
585	    } else {
586		choice += *element;
587		el = DPOC(data, choice->offset);
588		ret = _asn1_encode_fuzzer(choice->ptr, p, len, el, &datalen);
589		if (ret)
590		    return ret;
591	    }
592	    len -= datalen; p -= datalen;
593
594	    break;
595	}
596	default:
597	    ABORT_ON_ERROR();
598	}
599	t--;
600	elements--;
601    }
602
603    if (fuzzer_trigger(1000)) {
604	memset(p + 1, 0, oldlen - len);
605    } else if (fuzzer_trigger(1000)) {
606	memset(p + 1, 0x41, oldlen - len);
607    } else if (fuzzer_trigger(1000)) {
608	memset(p + 1, 0xff, oldlen - len);
609    }
610
611    if (size)
612	*size = oldlen - len;
613
614    return 0;
615}
616
617size_t
618_asn1_length_fuzzer(const struct asn1_template *t, const void *data)
619{
620    size_t elements = A1_HEADER_LEN(t);
621    size_t ret = 0;
622
623    t += A1_HEADER_LEN(t);
624
625    while (elements) {
626	switch (t->tt & A1_OP_MASK) {
627	case A1_OP_TYPE:
628	case A1_OP_TYPE_EXTERN: {
629	    const void *el = DPOC(data, t->offset);
630
631	    if (t->tt & A1_FLAG_OPTIONAL) {
632		void **pel = (void **)el;
633		if (*pel == NULL)
634		    break;
635		el = *pel;
636	    }
637
638	    if ((t->tt & A1_OP_MASK) == A1_OP_TYPE) {
639		ret += _asn1_length(t->ptr, el);
640	    } else {
641		const struct asn1_type_func *f = t->ptr;
642		ret += (f->length)(el);
643	    }
644	    break;
645	}
646	case A1_OP_TAG: {
647	    size_t datalen;
648	    const void *olddata = data;
649
650	    data = DPO(data, t->offset);
651
652	    if (t->tt & A1_FLAG_OPTIONAL) {
653		void **el = (void **)data;
654		if (*el == NULL) {
655		    data = olddata;
656		    break;
657		}
658		data = *el;
659	    }
660	    datalen = _asn1_length(t->ptr, data);
661	    ret += der_length_tag(A1_TAG_TAG(t->tt)) + fuzzer_length_len(datalen);
662	    ret += datalen;
663	    data = olddata;
664	    break;
665	}
666	case A1_OP_PARSE: {
667	    unsigned int type = A1_PARSE_TYPE(t->tt);
668	    const void *el = DPOC(data, t->offset);
669
670	    if (type > sizeof(asn1_template_prim)/sizeof(asn1_template_prim[0])) {
671		ABORT_ON_ERROR();
672		break;
673	    }
674	    ret += (asn1_template_prim[type].length)(el);
675	    break;
676	}
677	case A1_OP_SETOF:
678	case A1_OP_SEQOF: {
679	    const struct template_of *el = DPOC(data, t->offset);
680	    size_t ellen = _asn1_sizeofType(t->ptr);
681	    const unsigned char *element = el->val;
682	    unsigned int i;
683
684	    for (i = 0; i < el->len; i++) {
685		ret += _asn1_length(t->ptr, element);
686		element += ellen;
687	    }
688
689	    break;
690	}
691	case A1_OP_BMEMBER: {
692	    const struct asn1_template *bmember = t->ptr;
693	    size_t size = bmember->offset;
694	    size_t elements = A1_HEADER_LEN(bmember);
695	    int rfc1510 = (bmember->tt & A1_HBF_RFC1510);
696
697	    if (rfc1510) {
698		ret += 5;
699	    } else {
700
701		ret += 1;
702
703		bmember += elements;
704
705		while (elements) {
706		    if (_asn1_bmember_isset_bit(data, bmember->offset, size)) {
707			ret += (bmember->offset / 8) + 1;
708			break;
709		    }
710		    elements--; bmember--;
711		}
712	    }
713	    break;
714	}
715	case A1_OP_CHOICE: {
716	    const struct asn1_template *choice = t->ptr;
717	    const unsigned int *element = DPOC(data, choice->offset);
718
719	    if (*element > A1_HEADER_LEN(choice))
720		break;
721
722	    if (*element == 0) {
723		ret += der_length_octet_string(DPOC(data, choice->tt));
724	    } else {
725		choice += *element;
726		ret += _asn1_length(choice->ptr, DPOC(data, choice->offset));
727	    }
728	    break;
729	}
730	default:
731	    ABORT_ON_ERROR();
732	    break;
733	}
734	elements--;
735	t--;
736    }
737    return ret;
738}
739
740#endif /* ASN1_FUZZER */
741