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