aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorDavid Howells <dhowells@redhat.com>2012-09-24 12:11:16 -0400
committerRusty Russell <rusty@rustcorp.com.au>2012-10-07 23:20:20 -0400
commit42d5ec27f873c654a68f7f865dcd7737513e9508 (patch)
treea52fdc8d71dfc3724e4b2828fd53958e3774c761 /lib
parent4520c6a49af833c83de6c74525ce8e07bbe6d783 (diff)
X.509: Add an ASN.1 decoder
Add an ASN.1 BER/DER/CER decoder. This uses the bytecode from the ASN.1 compiler in the previous patch to inform it as to what to expect to find in the encoded byte stream. The output from the compiler also tells it what functions to call on what tags, thus allowing the caller to retrieve information. The decoder is called as follows: int asn1_decoder(const struct asn1_decoder *decoder, void *context, const unsigned char *data, size_t datalen); The decoder argument points to the bytecode from the ASN.1 compiler. context is the caller's context and is passed to the action functions. data and datalen define the byte stream to be decoded. Note that the decoder is currently limited to datalen being less than 64K. This reduces the amount of stack space used by the decoder because ASN.1 is a nested construct. Similarly, the decoder is limited to a maximum of 10 levels of constructed data outside of a leaf node also in an effort to keep stack usage down. These restrictions can be raised if necessary. Signed-off-by: David Howells <dhowells@redhat.com> Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Diffstat (limited to 'lib')
-rw-r--r--lib/Makefile2
-rw-r--r--lib/asn1_decoder.c477
2 files changed, 479 insertions, 0 deletions
diff --git a/lib/Makefile b/lib/Makefile
index b0428960939f..ca856b69a21d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -140,6 +140,8 @@ $(foreach file, $(libfdt_files), \
140 $(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt)) 140 $(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt))
141lib-$(CONFIG_LIBFDT) += $(libfdt_files) 141lib-$(CONFIG_LIBFDT) += $(libfdt_files)
142 142
143obj-$(CONFIG_ASN1) += asn1_decoder.o
144
143hostprogs-y := gen_crc32table 145hostprogs-y := gen_crc32table
144clean-files := crc32table.h 146clean-files := crc32table.h
145 147
diff --git a/lib/asn1_decoder.c b/lib/asn1_decoder.c
new file mode 100644
index 000000000000..2e4196ddf06f
--- /dev/null
+++ b/lib/asn1_decoder.c
@@ -0,0 +1,477 @@
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
18static 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 */
50static int asn1_find_indefinite_length(const unsigned char *data, size_t datalen,
51 const char **_errmsg, size_t *_err_dp)
52{
53 unsigned char tag, tmp;
54 size_t dp = 0, len, n;
55 int indef_level = 1;
56
57next_tag:
58 if (unlikely(datalen - dp < 2)) {
59 if (datalen == dp)
60 goto missing_eoc;
61 goto data_overrun_error;
62 }
63
64 /* Extract a tag from the data */
65 tag = data[dp++];
66 if (tag == 0) {
67 /* It appears to be an EOC. */
68 if (data[dp++] != 0)
69 goto invalid_eoc;
70 if (--indef_level <= 0)
71 return dp;
72 goto next_tag;
73 }
74
75 if (unlikely((tag & 0x1f) == 0x1f)) {
76 do {
77 if (unlikely(datalen - dp < 2))
78 goto data_overrun_error;
79 tmp = data[dp++];
80 } while (tmp & 0x80);
81 }
82
83 /* Extract the length */
84 len = data[dp++];
85 if (len < 0x7f) {
86 dp += len;
87 goto next_tag;
88 }
89
90 if (unlikely(len == 0x80)) {
91 /* Indefinite length */
92 if (unlikely((tag & ASN1_CONS_BIT) == ASN1_PRIM << 5))
93 goto indefinite_len_primitive;
94 indef_level++;
95 goto next_tag;
96 }
97
98 n = len - 0x80;
99 if (unlikely(n > sizeof(size_t) - 1))
100 goto length_too_long;
101 if (unlikely(n > datalen - dp))
102 goto data_overrun_error;
103 for (len = 0; n > 0; n--) {
104 len <<= 8;
105 len |= data[dp++];
106 }
107 dp += len;
108 goto next_tag;
109
110length_too_long:
111 *_errmsg = "Unsupported length";
112 goto error;
113indefinite_len_primitive:
114 *_errmsg = "Indefinite len primitive not permitted";
115 goto error;
116invalid_eoc:
117 *_errmsg = "Invalid length EOC";
118 goto error;
119data_overrun_error:
120 *_errmsg = "Data overrun error";
121 goto error;
122missing_eoc:
123 *_errmsg = "Missing EOC in indefinite len cons";
124error:
125 *_err_dp = dp;
126 return -1;
127}
128
129/**
130 * asn1_ber_decoder - Decoder BER/DER/CER ASN.1 according to pattern
131 * @decoder: The decoder definition (produced by asn1_compiler)
132 * @context: The caller's context (to be passed to the action functions)
133 * @data: The encoded data
134 * @datasize: The size of the encoded data
135 *
136 * Decode BER/DER/CER encoded ASN.1 data according to a bytecode pattern
137 * produced by asn1_compiler. Action functions are called on marked tags to
138 * allow the caller to retrieve significant data.
139 *
140 * LIMITATIONS:
141 *
142 * To keep down the amount of stack used by this function, the following limits
143 * have been imposed:
144 *
145 * (1) This won't handle datalen > 65535 without increasing the size of the
146 * cons stack elements and length_too_long checking.
147 *
148 * (2) The stack of constructed types is 10 deep. If the depth of non-leaf
149 * constructed types exceeds this, the decode will fail.
150 *
151 * (3) The SET type (not the SET OF type) isn't really supported as tracking
152 * what members of the set have been seen is a pain.
153 */
154int asn1_ber_decoder(const struct asn1_decoder *decoder,
155 void *context,
156 const unsigned char *data,
157 size_t datalen)
158{
159 const unsigned char *machine = decoder->machine;
160 const asn1_action_t *actions = decoder->actions;
161 size_t machlen = decoder->machlen;
162 enum asn1_opcode op;
163 unsigned char tag = 0, csp = 0, jsp = 0, optag = 0, hdr = 0;
164 const char *errmsg;
165 size_t pc = 0, dp = 0, tdp = 0, len = 0;
166 int ret;
167
168 unsigned char flags = 0;
169#define FLAG_INDEFINITE_LENGTH 0x01
170#define FLAG_MATCHED 0x02
171#define FLAG_CONS 0x20 /* Corresponds to CONS bit in the opcode tag
172 * - ie. whether or not we are going to parse
173 * a compound type.
174 */
175
176#define NR_CONS_STACK 10
177 unsigned short cons_dp_stack[NR_CONS_STACK];
178 unsigned short cons_datalen_stack[NR_CONS_STACK];
179 unsigned char cons_hdrlen_stack[NR_CONS_STACK];
180#define NR_JUMP_STACK 10
181 unsigned char jump_stack[NR_JUMP_STACK];
182
183 if (datalen > 65535)
184 return -EMSGSIZE;
185
186next_op:
187 pr_debug("next_op: pc=\e[32m%zu\e[m/%zu dp=\e[33m%zu\e[m/%zu C=%d J=%d\n",
188 pc, machlen, dp, datalen, csp, jsp);
189 if (unlikely(pc >= machlen))
190 goto machine_overrun_error;
191 op = machine[pc];
192 if (unlikely(pc + asn1_op_lengths[op] > machlen))
193 goto machine_overrun_error;
194
195 /* If this command is meant to match a tag, then do that before
196 * evaluating the command.
197 */
198 if (op <= ASN1_OP__MATCHES_TAG) {
199 unsigned char tmp;
200
201 /* Skip conditional matches if possible */
202 if ((op & ASN1_OP_MATCH__COND &&
203 flags & FLAG_MATCHED) ||
204 dp == datalen) {
205 pc += asn1_op_lengths[op];
206 goto next_op;
207 }
208
209 flags = 0;
210 hdr = 2;
211
212 /* Extract a tag from the data */
213 if (unlikely(dp >= datalen - 1))
214 goto data_overrun_error;
215 tag = data[dp++];
216 if (unlikely((tag & 0x1f) == 0x1f))
217 goto long_tag_not_supported;
218
219 if (op & ASN1_OP_MATCH__ANY) {
220 pr_debug("- any %02x\n", tag);
221 } else {
222 /* Extract the tag from the machine
223 * - Either CONS or PRIM are permitted in the data if
224 * CONS is not set in the op stream, otherwise CONS
225 * is mandatory.
226 */
227 optag = machine[pc + 1];
228 flags |= optag & FLAG_CONS;
229
230 /* Determine whether the tag matched */
231 tmp = optag ^ tag;
232 tmp &= ~(optag & ASN1_CONS_BIT);
233 pr_debug("- match? %02x %02x %02x\n", tag, optag, tmp);
234 if (tmp != 0) {
235 /* All odd-numbered tags are MATCH_OR_SKIP. */
236 if (op & ASN1_OP_MATCH__SKIP) {
237 pc += asn1_op_lengths[op];
238 dp--;
239 goto next_op;
240 }
241 goto tag_mismatch;
242 }
243 }
244 flags |= FLAG_MATCHED;
245
246 len = data[dp++];
247 if (len > 0x7f) {
248 if (unlikely(len == 0x80)) {
249 /* Indefinite length */
250 if (unlikely(!(tag & ASN1_CONS_BIT)))
251 goto indefinite_len_primitive;
252 flags |= FLAG_INDEFINITE_LENGTH;
253 if (unlikely(2 > datalen - dp))
254 goto data_overrun_error;
255 } else {
256 int n = len - 0x80;
257 if (unlikely(n > 2))
258 goto length_too_long;
259 if (unlikely(dp >= datalen - n))
260 goto data_overrun_error;
261 hdr += n;
262 for (len = 0; n > 0; n--) {
263 len <<= 8;
264 len |= data[dp++];
265 }
266 if (unlikely(len > datalen - dp))
267 goto data_overrun_error;
268 }
269 }
270
271 if (flags & FLAG_CONS) {
272 /* For expected compound forms, we stack the positions
273 * of the start and end of the data.
274 */
275 if (unlikely(csp >= NR_CONS_STACK))
276 goto cons_stack_overflow;
277 cons_dp_stack[csp] = dp;
278 cons_hdrlen_stack[csp] = hdr;
279 if (!(flags & FLAG_INDEFINITE_LENGTH)) {
280 cons_datalen_stack[csp] = datalen;
281 datalen = dp + len;
282 } else {
283 cons_datalen_stack[csp] = 0;
284 }
285 csp++;
286 }
287
288 pr_debug("- TAG: %02x %zu%s\n",
289 tag, len, flags & FLAG_CONS ? " CONS" : "");
290 tdp = dp;
291 }
292
293 /* Decide how to handle the operation */
294 switch (op) {
295 case ASN1_OP_MATCH_ANY_ACT:
296 case ASN1_OP_COND_MATCH_ANY_ACT:
297 ret = actions[machine[pc + 1]](context, hdr, tag, data + dp, len);
298 if (ret < 0)
299 return ret;
300 goto skip_data;
301
302 case ASN1_OP_MATCH_ACT:
303 case ASN1_OP_MATCH_ACT_OR_SKIP:
304 case ASN1_OP_COND_MATCH_ACT_OR_SKIP:
305 ret = actions[machine[pc + 2]](context, hdr, tag, data + dp, len);
306 if (ret < 0)
307 return ret;
308 goto skip_data;
309
310 case ASN1_OP_MATCH:
311 case ASN1_OP_MATCH_OR_SKIP:
312 case ASN1_OP_MATCH_ANY:
313 case ASN1_OP_COND_MATCH_OR_SKIP:
314 case ASN1_OP_COND_MATCH_ANY:
315 skip_data:
316 if (!(flags & FLAG_CONS)) {
317 if (flags & FLAG_INDEFINITE_LENGTH) {
318 len = asn1_find_indefinite_length(
319 data + dp, datalen - dp, &errmsg, &dp);
320 if (len < 0)
321 goto error;
322 }
323 pr_debug("- LEAF: %zu\n", len);
324 dp += len;
325 }
326 pc += asn1_op_lengths[op];
327 goto next_op;
328
329 case ASN1_OP_MATCH_JUMP:
330 case ASN1_OP_MATCH_JUMP_OR_SKIP:
331 case ASN1_OP_COND_MATCH_JUMP_OR_SKIP:
332 pr_debug("- MATCH_JUMP\n");
333 if (unlikely(jsp == NR_JUMP_STACK))
334 goto jump_stack_overflow;
335 jump_stack[jsp++] = pc + asn1_op_lengths[op];
336 pc = machine[pc + 2];
337 goto next_op;
338
339 case ASN1_OP_COND_FAIL:
340 if (unlikely(!(flags & FLAG_MATCHED)))
341 goto tag_mismatch;
342 pc += asn1_op_lengths[op];
343 goto next_op;
344
345 case ASN1_OP_COMPLETE:
346 if (unlikely(jsp != 0 || csp != 0)) {
347 pr_err("ASN.1 decoder error: Stacks not empty at completion (%u, %u)\n",
348 jsp, csp);
349 return -EBADMSG;
350 }
351 return 0;
352
353 case ASN1_OP_END_SET:
354 case ASN1_OP_END_SET_ACT:
355 if (unlikely(!(flags & FLAG_MATCHED)))
356 goto tag_mismatch;
357 case ASN1_OP_END_SEQ:
358 case ASN1_OP_END_SET_OF:
359 case ASN1_OP_END_SEQ_OF:
360 case ASN1_OP_END_SEQ_ACT:
361 case ASN1_OP_END_SET_OF_ACT:
362 case ASN1_OP_END_SEQ_OF_ACT:
363 if (unlikely(csp <= 0))
364 goto cons_stack_underflow;
365 csp--;
366 tdp = cons_dp_stack[csp];
367 hdr = cons_hdrlen_stack[csp];
368 len = datalen;
369 datalen = cons_datalen_stack[csp];
370 pr_debug("- end cons t=%zu dp=%zu l=%zu/%zu\n",
371 tdp, dp, len, datalen);
372 if (datalen == 0) {
373 /* Indefinite length - check for the EOC. */
374 datalen = len;
375 if (unlikely(datalen - dp < 2))
376 goto data_overrun_error;
377 if (data[dp++] != 0) {
378 if (op & ASN1_OP_END__OF) {
379 dp--;
380 csp++;
381 pc = machine[pc + 1];
382 pr_debug("- continue\n");
383 goto next_op;
384 }
385 goto missing_eoc;
386 }
387 if (data[dp++] != 0)
388 goto invalid_eoc;
389 len = dp - tdp - 2;
390 } else {
391 if (dp < len && (op & ASN1_OP_END__OF)) {
392 datalen = len;
393 csp++;
394 pc = machine[pc + 1];
395 pr_debug("- continue\n");
396 goto next_op;
397 }
398 if (dp != len)
399 goto cons_length_error;
400 len -= tdp;
401 pr_debug("- cons len l=%zu d=%zu\n", len, dp - tdp);
402 }
403
404 if (op & ASN1_OP_END__ACT) {
405 unsigned char act;
406 if (op & ASN1_OP_END__OF)
407 act = machine[pc + 2];
408 else
409 act = machine[pc + 1];
410 ret = actions[act](context, hdr, 0, data + tdp, len);
411 }
412 pc += asn1_op_lengths[op];
413 goto next_op;
414
415 case ASN1_OP_ACT:
416 ret = actions[machine[pc + 1]](context, hdr, tag, data + tdp, len);
417 pc += asn1_op_lengths[op];
418 goto next_op;
419
420 case ASN1_OP_RETURN:
421 if (unlikely(jsp <= 0))
422 goto jump_stack_underflow;
423 pc = jump_stack[--jsp];
424 goto next_op;
425
426 default:
427 break;
428 }
429
430 /* Shouldn't reach here */
431 pr_err("ASN.1 decoder error: Found reserved opcode (%u)\n", op);
432 return -EBADMSG;
433
434data_overrun_error:
435 errmsg = "Data overrun error";
436 goto error;
437machine_overrun_error:
438 errmsg = "Machine overrun error";
439 goto error;
440jump_stack_underflow:
441 errmsg = "Jump stack underflow";
442 goto error;
443jump_stack_overflow:
444 errmsg = "Jump stack overflow";
445 goto error;
446cons_stack_underflow:
447 errmsg = "Cons stack underflow";
448 goto error;
449cons_stack_overflow:
450 errmsg = "Cons stack overflow";
451 goto error;
452cons_length_error:
453 errmsg = "Cons length error";
454 goto error;
455missing_eoc:
456 errmsg = "Missing EOC in indefinite len cons";
457 goto error;
458invalid_eoc:
459 errmsg = "Invalid length EOC";
460 goto error;
461length_too_long:
462 errmsg = "Unsupported length";
463 goto error;
464indefinite_len_primitive:
465 errmsg = "Indefinite len primitive not permitted";
466 goto error;
467tag_mismatch:
468 errmsg = "Unexpected tag";
469 goto error;
470long_tag_not_supported:
471 errmsg = "Long tag not supported";
472error:
473 pr_debug("\nASN1: %s [m=%zu d=%zu ot=%02x t=%02x l=%zu]\n",
474 errmsg, pc, dp, optag, tag, len);
475 return -EBADMSG;
476}
477EXPORT_SYMBOL_GPL(asn1_ber_decoder);
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-02 12:23:14 -0400