random32: fix off-by-one in seeding requirement
[linux-3.10.git] / lib / asn1_decoder.c
1 /* Decoder for ASN.1 BER/DER/CER encoded bytestream
2  *
3  * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
4  * Written by David Howells (dhowells@redhat.com)
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public Licence
8  * as published by the Free Software Foundation; either version
9  * 2 of the Licence, or (at your option) any later version.
10  */
11
12 #include <linux/export.h>
13 #include <linux/kernel.h>
14 #include <linux/errno.h>
15 #include <linux/asn1_decoder.h>
16 #include <linux/asn1_ber_bytecode.h>
17
18 static const unsigned char asn1_op_lengths[ASN1_OP__NR] = {
19         /*                                      OPC TAG JMP ACT */
20         [ASN1_OP_MATCH]                         = 1 + 1,
21         [ASN1_OP_MATCH_OR_SKIP]                 = 1 + 1,
22         [ASN1_OP_MATCH_ACT]                     = 1 + 1     + 1,
23         [ASN1_OP_MATCH_ACT_OR_SKIP]             = 1 + 1     + 1,
24         [ASN1_OP_MATCH_JUMP]                    = 1 + 1 + 1,
25         [ASN1_OP_MATCH_JUMP_OR_SKIP]            = 1 + 1 + 1,
26         [ASN1_OP_MATCH_ANY]                     = 1,
27         [ASN1_OP_MATCH_ANY_ACT]                 = 1         + 1,
28         [ASN1_OP_COND_MATCH_OR_SKIP]            = 1 + 1,
29         [ASN1_OP_COND_MATCH_ACT_OR_SKIP]        = 1 + 1     + 1,
30         [ASN1_OP_COND_MATCH_JUMP_OR_SKIP]       = 1 + 1 + 1,
31         [ASN1_OP_COND_MATCH_ANY]                = 1,
32         [ASN1_OP_COND_MATCH_ANY_ACT]            = 1         + 1,
33         [ASN1_OP_COND_FAIL]                     = 1,
34         [ASN1_OP_COMPLETE]                      = 1,
35         [ASN1_OP_ACT]                           = 1         + 1,
36         [ASN1_OP_RETURN]                        = 1,
37         [ASN1_OP_END_SEQ]                       = 1,
38         [ASN1_OP_END_SEQ_OF]                    = 1     + 1,
39         [ASN1_OP_END_SET]                       = 1,
40         [ASN1_OP_END_SET_OF]                    = 1     + 1,
41         [ASN1_OP_END_SEQ_ACT]                   = 1         + 1,
42         [ASN1_OP_END_SEQ_OF_ACT]                = 1     + 1 + 1,
43         [ASN1_OP_END_SET_ACT]                   = 1         + 1,
44         [ASN1_OP_END_SET_OF_ACT]                = 1     + 1 + 1,
45 };
46
47 /*
48  * Find the length of an indefinite length object
49  * @data: The data buffer
50  * @datalen: The end of the innermost containing element in the buffer
51  * @_dp: The data parse cursor (updated before returning)
52  * @_len: Where to return the size of the element.
53  * @_errmsg: Where to return a pointer to an error message on error
54  */
55 static int asn1_find_indefinite_length(const unsigned char *data, size_t datalen,
56                                        size_t *_dp, size_t *_len,
57                                        const char **_errmsg)
58 {
59         unsigned char tag, tmp;
60         size_t dp = *_dp, len, n;
61         int indef_level = 1;
62
63 next_tag:
64         if (unlikely(datalen - dp < 2)) {
65                 if (datalen == dp)
66                         goto missing_eoc;
67                 goto data_overrun_error;
68         }
69
70         /* Extract a tag from the data */
71         tag = data[dp++];
72         if (tag == 0) {
73                 /* It appears to be an EOC. */
74                 if (data[dp++] != 0)
75                         goto invalid_eoc;
76                 if (--indef_level <= 0) {
77                         *_len = dp - *_dp;
78                         *_dp = dp;
79                         return 0;
80                 }
81                 goto next_tag;
82         }
83
84         if (unlikely((tag & 0x1f) == ASN1_LONG_TAG)) {
85                 do {
86                         if (unlikely(datalen - dp < 2))
87                                 goto data_overrun_error;
88                         tmp = data[dp++];
89                 } while (tmp & 0x80);
90         }
91
92         /* Extract the length */
93         len = data[dp++];
94         if (len <= 0x7f) {
95                 dp += len;
96                 goto next_tag;
97         }
98
99         if (unlikely(len == ASN1_INDEFINITE_LENGTH)) {
100                 /* Indefinite length */
101                 if (unlikely((tag & ASN1_CONS_BIT) == ASN1_PRIM << 5))
102                         goto indefinite_len_primitive;
103                 indef_level++;
104                 goto next_tag;
105         }
106
107         n = len - 0x80;
108         if (unlikely(n > sizeof(size_t) - 1))
109                 goto length_too_long;
110         if (unlikely(n > datalen - dp))
111                 goto data_overrun_error;
112         for (len = 0; n > 0; n--) {
113                 len <<= 8;
114                 len |= data[dp++];
115         }
116         dp += len;
117         goto next_tag;
118
119 length_too_long:
120         *_errmsg = "Unsupported length";
121         goto error;
122 indefinite_len_primitive:
123         *_errmsg = "Indefinite len primitive not permitted";
124         goto error;
125 invalid_eoc:
126         *_errmsg = "Invalid length EOC";
127         goto error;
128 data_overrun_error:
129         *_errmsg = "Data overrun error";
130         goto error;
131 missing_eoc:
132         *_errmsg = "Missing EOC in indefinite len cons";
133 error:
134         *_dp = dp;
135         return -1;
136 }
137
138 /**
139  * asn1_ber_decoder - Decoder BER/DER/CER ASN.1 according to pattern
140  * @decoder: The decoder definition (produced by asn1_compiler)
141  * @context: The caller's context (to be passed to the action functions)
142  * @data: The encoded data
143  * @datasize: The size of the encoded data
144  *
145  * Decode BER/DER/CER encoded ASN.1 data according to a bytecode pattern
146  * produced by asn1_compiler.  Action functions are called on marked tags to
147  * allow the caller to retrieve significant data.
148  *
149  * LIMITATIONS:
150  *
151  * To keep down the amount of stack used by this function, the following limits
152  * have been imposed:
153  *
154  *  (1) This won't handle datalen > 65535 without increasing the size of the
155  *      cons stack elements and length_too_long checking.
156  *
157  *  (2) The stack of constructed types is 10 deep.  If the depth of non-leaf
158  *      constructed types exceeds this, the decode will fail.
159  *
160  *  (3) The SET type (not the SET OF type) isn't really supported as tracking
161  *      what members of the set have been seen is a pain.
162  */
163 int asn1_ber_decoder(const struct asn1_decoder *decoder,
164                      void *context,
165                      const unsigned char *data,
166                      size_t datalen)
167 {
168         const unsigned char *machine = decoder->machine;
169         const asn1_action_t *actions = decoder->actions;
170         size_t machlen = decoder->machlen;
171         enum asn1_opcode op;
172         unsigned char tag = 0, csp = 0, jsp = 0, optag = 0, hdr = 0;
173         const char *errmsg;
174         size_t pc = 0, dp = 0, tdp = 0, len = 0;
175         int ret;
176
177         unsigned char flags = 0;
178 #define FLAG_INDEFINITE_LENGTH  0x01
179 #define FLAG_MATCHED            0x02
180 #define FLAG_CONS               0x20 /* Corresponds to CONS bit in the opcode tag
181                                       * - ie. whether or not we are going to parse
182                                       *   a compound type.
183                                       */
184
185 #define NR_CONS_STACK 10
186         unsigned short cons_dp_stack[NR_CONS_STACK];
187         unsigned short cons_datalen_stack[NR_CONS_STACK];
188         unsigned char cons_hdrlen_stack[NR_CONS_STACK];
189 #define NR_JUMP_STACK 10
190         unsigned char jump_stack[NR_JUMP_STACK];
191
192         if (datalen > 65535)
193                 return -EMSGSIZE;
194
195 next_op:
196         pr_debug("next_op: pc=\e[32m%zu\e[m/%zu dp=\e[33m%zu\e[m/%zu C=%d J=%d\n",
197                  pc, machlen, dp, datalen, csp, jsp);
198         if (unlikely(pc >= machlen))
199                 goto machine_overrun_error;
200         op = machine[pc];
201         if (unlikely(pc + asn1_op_lengths[op] > machlen))
202                 goto machine_overrun_error;
203
204         /* If this command is meant to match a tag, then do that before
205          * evaluating the command.
206          */
207         if (op <= ASN1_OP__MATCHES_TAG) {
208                 unsigned char tmp;
209
210                 /* Skip conditional matches if possible */
211                 if ((op & ASN1_OP_MATCH__COND &&
212                      flags & FLAG_MATCHED) ||
213                     dp == datalen) {
214                         pc += asn1_op_lengths[op];
215                         goto next_op;
216                 }
217
218                 flags = 0;
219                 hdr = 2;
220
221                 /* Extract a tag from the data */
222                 if (unlikely(dp >= datalen - 1))
223                         goto data_overrun_error;
224                 tag = data[dp++];
225                 if (unlikely((tag & 0x1f) == ASN1_LONG_TAG))
226                         goto long_tag_not_supported;
227
228                 if (op & ASN1_OP_MATCH__ANY) {
229                         pr_debug("- any %02x\n", tag);
230                 } else {
231                         /* Extract the tag from the machine
232                          * - Either CONS or PRIM are permitted in the data if
233                          *   CONS is not set in the op stream, otherwise CONS
234                          *   is mandatory.
235                          */
236                         optag = machine[pc + 1];
237                         flags |= optag & FLAG_CONS;
238
239                         /* Determine whether the tag matched */
240                         tmp = optag ^ tag;
241                         tmp &= ~(optag & ASN1_CONS_BIT);
242                         pr_debug("- match? %02x %02x %02x\n", tag, optag, tmp);
243                         if (tmp != 0) {
244                                 /* All odd-numbered tags are MATCH_OR_SKIP. */
245                                 if (op & ASN1_OP_MATCH__SKIP) {
246                                         pc += asn1_op_lengths[op];
247                                         dp--;
248                                         goto next_op;
249                                 }
250                                 goto tag_mismatch;
251                         }
252                 }
253                 flags |= FLAG_MATCHED;
254
255                 len = data[dp++];
256                 if (len > 0x7f) {
257                         if (unlikely(len == ASN1_INDEFINITE_LENGTH)) {
258                                 /* Indefinite length */
259                                 if (unlikely(!(tag & ASN1_CONS_BIT)))
260                                         goto indefinite_len_primitive;
261                                 flags |= FLAG_INDEFINITE_LENGTH;
262                                 if (unlikely(2 > datalen - dp))
263                                         goto data_overrun_error;
264                         } else {
265                                 int n = len - 0x80;
266                                 if (unlikely(n > 2))
267                                         goto length_too_long;
268                                 if (unlikely(dp >= datalen - n))
269                                         goto data_overrun_error;
270                                 hdr += n;
271                                 for (len = 0; n > 0; n--) {
272                                         len <<= 8;
273                                         len |= data[dp++];
274                                 }
275                                 if (unlikely(len > datalen - dp))
276                                         goto data_overrun_error;
277                         }
278                 }
279
280                 if (flags & FLAG_CONS) {
281                         /* For expected compound forms, we stack the positions
282                          * of the start and end of the data.
283                          */
284                         if (unlikely(csp >= NR_CONS_STACK))
285                                 goto cons_stack_overflow;
286                         cons_dp_stack[csp] = dp;
287                         cons_hdrlen_stack[csp] = hdr;
288                         if (!(flags & FLAG_INDEFINITE_LENGTH)) {
289                                 cons_datalen_stack[csp] = datalen;
290                                 datalen = dp + len;
291                         } else {
292                                 cons_datalen_stack[csp] = 0;
293                         }
294                         csp++;
295                 }
296
297                 pr_debug("- TAG: %02x %zu%s\n",
298                          tag, len, flags & FLAG_CONS ? " CONS" : "");
299                 tdp = dp;
300         }
301
302         /* Decide how to handle the operation */
303         switch (op) {
304         case ASN1_OP_MATCH_ANY_ACT:
305         case ASN1_OP_COND_MATCH_ANY_ACT:
306                 ret = actions[machine[pc + 1]](context, hdr, tag, data + dp, len);
307                 if (ret < 0)
308                         return ret;
309                 goto skip_data;
310
311         case ASN1_OP_MATCH_ACT:
312         case ASN1_OP_MATCH_ACT_OR_SKIP:
313         case ASN1_OP_COND_MATCH_ACT_OR_SKIP:
314                 ret = actions[machine[pc + 2]](context, hdr, tag, data + dp, len);
315                 if (ret < 0)
316                         return ret;
317                 goto skip_data;
318
319         case ASN1_OP_MATCH:
320         case ASN1_OP_MATCH_OR_SKIP:
321         case ASN1_OP_MATCH_ANY:
322         case ASN1_OP_COND_MATCH_OR_SKIP:
323         case ASN1_OP_COND_MATCH_ANY:
324         skip_data:
325                 if (!(flags & FLAG_CONS)) {
326                         if (flags & FLAG_INDEFINITE_LENGTH) {
327                                 ret = asn1_find_indefinite_length(
328                                         data, datalen, &dp, &len, &errmsg);
329                                 if (ret < 0)
330                                         goto error;
331                         } else {
332                                 dp += len;
333                         }
334                         pr_debug("- LEAF: %zu\n", len);
335                 }
336                 pc += asn1_op_lengths[op];
337                 goto next_op;
338
339         case ASN1_OP_MATCH_JUMP:
340         case ASN1_OP_MATCH_JUMP_OR_SKIP:
341         case ASN1_OP_COND_MATCH_JUMP_OR_SKIP:
342                 pr_debug("- MATCH_JUMP\n");
343                 if (unlikely(jsp == NR_JUMP_STACK))
344                         goto jump_stack_overflow;
345                 jump_stack[jsp++] = pc + asn1_op_lengths[op];
346                 pc = machine[pc + 2];
347                 goto next_op;
348
349         case ASN1_OP_COND_FAIL:
350                 if (unlikely(!(flags & FLAG_MATCHED)))
351                         goto tag_mismatch;
352                 pc += asn1_op_lengths[op];
353                 goto next_op;
354
355         case ASN1_OP_COMPLETE:
356                 if (unlikely(jsp != 0 || csp != 0)) {
357                         pr_err("ASN.1 decoder error: Stacks not empty at completion (%u, %u)\n",
358                                jsp, csp);
359                         return -EBADMSG;
360                 }
361                 return 0;
362
363         case ASN1_OP_END_SET:
364         case ASN1_OP_END_SET_ACT:
365                 if (unlikely(!(flags & FLAG_MATCHED)))
366                         goto tag_mismatch;
367         case ASN1_OP_END_SEQ:
368         case ASN1_OP_END_SET_OF:
369         case ASN1_OP_END_SEQ_OF:
370         case ASN1_OP_END_SEQ_ACT:
371         case ASN1_OP_END_SET_OF_ACT:
372         case ASN1_OP_END_SEQ_OF_ACT:
373                 if (unlikely(csp <= 0))
374                         goto cons_stack_underflow;
375                 csp--;
376                 tdp = cons_dp_stack[csp];
377                 hdr = cons_hdrlen_stack[csp];
378                 len = datalen;
379                 datalen = cons_datalen_stack[csp];
380                 pr_debug("- end cons t=%zu dp=%zu l=%zu/%zu\n",
381                          tdp, dp, len, datalen);
382                 if (datalen == 0) {
383                         /* Indefinite length - check for the EOC. */
384                         datalen = len;
385                         if (unlikely(datalen - dp < 2))
386                                 goto data_overrun_error;
387                         if (data[dp++] != 0) {
388                                 if (op & ASN1_OP_END__OF) {
389                                         dp--;
390                                         csp++;
391                                         pc = machine[pc + 1];
392                                         pr_debug("- continue\n");
393                                         goto next_op;
394                                 }
395                                 goto missing_eoc;
396                         }
397                         if (data[dp++] != 0)
398                                 goto invalid_eoc;
399                         len = dp - tdp - 2;
400                 } else {
401                         if (dp < len && (op & ASN1_OP_END__OF)) {
402                                 datalen = len;
403                                 csp++;
404                                 pc = machine[pc + 1];
405                                 pr_debug("- continue\n");
406                                 goto next_op;
407                         }
408                         if (dp != len)
409                                 goto cons_length_error;
410                         len -= tdp;
411                         pr_debug("- cons len l=%zu d=%zu\n", len, dp - tdp);
412                 }
413
414                 if (op & ASN1_OP_END__ACT) {
415                         unsigned char act;
416                         if (op & ASN1_OP_END__OF)
417                                 act = machine[pc + 2];
418                         else
419                                 act = machine[pc + 1];
420                         ret = actions[act](context, hdr, 0, data + tdp, len);
421                 }
422                 pc += asn1_op_lengths[op];
423                 goto next_op;
424
425         case ASN1_OP_ACT:
426                 ret = actions[machine[pc + 1]](context, hdr, tag, data + tdp, len);
427                 pc += asn1_op_lengths[op];
428                 goto next_op;
429
430         case ASN1_OP_RETURN:
431                 if (unlikely(jsp <= 0))
432                         goto jump_stack_underflow;
433                 pc = jump_stack[--jsp];
434                 goto next_op;
435
436         default:
437                 break;
438         }
439
440         /* Shouldn't reach here */
441         pr_err("ASN.1 decoder error: Found reserved opcode (%u)\n", op);
442         return -EBADMSG;
443
444 data_overrun_error:
445         errmsg = "Data overrun error";
446         goto error;
447 machine_overrun_error:
448         errmsg = "Machine overrun error";
449         goto error;
450 jump_stack_underflow:
451         errmsg = "Jump stack underflow";
452         goto error;
453 jump_stack_overflow:
454         errmsg = "Jump stack overflow";
455         goto error;
456 cons_stack_underflow:
457         errmsg = "Cons stack underflow";
458         goto error;
459 cons_stack_overflow:
460         errmsg = "Cons stack overflow";
461         goto error;
462 cons_length_error:
463         errmsg = "Cons length error";
464         goto error;
465 missing_eoc:
466         errmsg = "Missing EOC in indefinite len cons";
467         goto error;
468 invalid_eoc:
469         errmsg = "Invalid length EOC";
470         goto error;
471 length_too_long:
472         errmsg = "Unsupported length";
473         goto error;
474 indefinite_len_primitive:
475         errmsg = "Indefinite len primitive not permitted";
476         goto error;
477 tag_mismatch:
478         errmsg = "Unexpected tag";
479         goto error;
480 long_tag_not_supported:
481         errmsg = "Long tag not supported";
482 error:
483         pr_debug("\nASN1: %s [m=%zu d=%zu ot=%02x t=%02x l=%zu]\n",
484                  errmsg, pc, dp, optag, tag, len);
485         return -EBADMSG;
486 }
487 EXPORT_SYMBOL_GPL(asn1_ber_decoder);