asn1_decoder.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /* Decoder for ASN.1 BER/DER/CER encoded bytestream
  3. *
  4. * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
  5. * Written by David Howells (dhowells@redhat.com)
  6. */
  7. #ifdef __UBOOT__
  8. #include <linux/compat.h>
  9. #else
  10. #include <linux/export.h>
  11. #endif
  12. #include <linux/kernel.h>
  13. #include <linux/errno.h>
  14. #ifndef __UBOOT__
  15. #include <linux/module.h>
  16. #endif
  17. #include <linux/asn1_decoder.h>
  18. #include <linux/asn1_ber_bytecode.h>
  19. static const unsigned char asn1_op_lengths[ASN1_OP__NR] = {
  20. /* OPC TAG JMP ACT */
  21. [ASN1_OP_MATCH] = 1 + 1,
  22. [ASN1_OP_MATCH_OR_SKIP] = 1 + 1,
  23. [ASN1_OP_MATCH_ACT] = 1 + 1 + 1,
  24. [ASN1_OP_MATCH_ACT_OR_SKIP] = 1 + 1 + 1,
  25. [ASN1_OP_MATCH_JUMP] = 1 + 1 + 1,
  26. [ASN1_OP_MATCH_JUMP_OR_SKIP] = 1 + 1 + 1,
  27. [ASN1_OP_MATCH_ANY] = 1,
  28. [ASN1_OP_MATCH_ANY_OR_SKIP] = 1,
  29. [ASN1_OP_MATCH_ANY_ACT] = 1 + 1,
  30. [ASN1_OP_MATCH_ANY_ACT_OR_SKIP] = 1 + 1,
  31. [ASN1_OP_COND_MATCH_OR_SKIP] = 1 + 1,
  32. [ASN1_OP_COND_MATCH_ACT_OR_SKIP] = 1 + 1 + 1,
  33. [ASN1_OP_COND_MATCH_JUMP_OR_SKIP] = 1 + 1 + 1,
  34. [ASN1_OP_COND_MATCH_ANY] = 1,
  35. [ASN1_OP_COND_MATCH_ANY_OR_SKIP] = 1,
  36. [ASN1_OP_COND_MATCH_ANY_ACT] = 1 + 1,
  37. [ASN1_OP_COND_MATCH_ANY_ACT_OR_SKIP] = 1 + 1,
  38. [ASN1_OP_COND_FAIL] = 1,
  39. [ASN1_OP_COMPLETE] = 1,
  40. [ASN1_OP_ACT] = 1 + 1,
  41. [ASN1_OP_MAYBE_ACT] = 1 + 1,
  42. [ASN1_OP_RETURN] = 1,
  43. [ASN1_OP_END_SEQ] = 1,
  44. [ASN1_OP_END_SEQ_OF] = 1 + 1,
  45. [ASN1_OP_END_SET] = 1,
  46. [ASN1_OP_END_SET_OF] = 1 + 1,
  47. [ASN1_OP_END_SEQ_ACT] = 1 + 1,
  48. [ASN1_OP_END_SEQ_OF_ACT] = 1 + 1 + 1,
  49. [ASN1_OP_END_SET_ACT] = 1 + 1,
  50. [ASN1_OP_END_SET_OF_ACT] = 1 + 1 + 1,
  51. };
  52. /*
  53. * Find the length of an indefinite length object
  54. * @data: The data buffer
  55. * @datalen: The end of the innermost containing element in the buffer
  56. * @_dp: The data parse cursor (updated before returning)
  57. * @_len: Where to return the size of the element.
  58. * @_errmsg: Where to return a pointer to an error message on error
  59. */
  60. static int asn1_find_indefinite_length(const unsigned char *data, size_t datalen,
  61. size_t *_dp, size_t *_len,
  62. const char **_errmsg)
  63. {
  64. unsigned char tag, tmp;
  65. size_t dp = *_dp, len, n;
  66. int indef_level = 1;
  67. next_tag:
  68. if (unlikely(datalen - dp < 2)) {
  69. if (datalen == dp)
  70. goto missing_eoc;
  71. goto data_overrun_error;
  72. }
  73. /* Extract a tag from the data */
  74. tag = data[dp++];
  75. if (tag == ASN1_EOC) {
  76. /* It appears to be an EOC. */
  77. if (data[dp++] != 0)
  78. goto invalid_eoc;
  79. if (--indef_level <= 0) {
  80. *_len = dp - *_dp;
  81. *_dp = dp;
  82. return 0;
  83. }
  84. goto next_tag;
  85. }
  86. if (unlikely((tag & 0x1f) == ASN1_LONG_TAG)) {
  87. do {
  88. if (unlikely(datalen - dp < 2))
  89. goto data_overrun_error;
  90. tmp = data[dp++];
  91. } while (tmp & 0x80);
  92. }
  93. /* Extract the length */
  94. len = data[dp++];
  95. if (len <= 0x7f)
  96. goto check_length;
  97. if (unlikely(len == ASN1_INDEFINITE_LENGTH)) {
  98. /* Indefinite length */
  99. if (unlikely((tag & ASN1_CONS_BIT) == ASN1_PRIM << 5))
  100. goto indefinite_len_primitive;
  101. indef_level++;
  102. goto next_tag;
  103. }
  104. n = len - 0x80;
  105. if (unlikely(n > sizeof(len) - 1))
  106. goto length_too_long;
  107. if (unlikely(n > datalen - dp))
  108. goto data_overrun_error;
  109. len = 0;
  110. for (; n > 0; n--) {
  111. len <<= 8;
  112. len |= data[dp++];
  113. }
  114. check_length:
  115. if (len > datalen - dp)
  116. goto data_overrun_error;
  117. dp += len;
  118. goto next_tag;
  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. * asn1_ber_decoder - Decoder BER/DER/CER ASN.1 according to pattern
  139. * @decoder: The decoder definition (produced by asn1_compiler)
  140. * @context: The caller's context (to be passed to the action functions)
  141. * @data: The encoded data
  142. * @datalen: The size of the encoded data
  143. *
  144. * Decode BER/DER/CER encoded ASN.1 data according to a bytecode pattern
  145. * produced by asn1_compiler. Action functions are called on marked tags to
  146. * allow the caller to retrieve significant data.
  147. *
  148. * LIMITATIONS:
  149. *
  150. * To keep down the amount of stack used by this function, the following limits
  151. * have been imposed:
  152. *
  153. * (1) This won't handle datalen > 65535 without increasing the size of the
  154. * cons stack elements and length_too_long checking.
  155. *
  156. * (2) The stack of constructed types is 10 deep. If the depth of non-leaf
  157. * constructed types exceeds this, the decode will fail.
  158. *
  159. * (3) The SET type (not the SET OF type) isn't really supported as tracking
  160. * what members of the set have been seen is a pain.
  161. */
  162. int asn1_ber_decoder(const struct asn1_decoder *decoder,
  163. void *context,
  164. const unsigned char *data,
  165. size_t datalen)
  166. {
  167. const unsigned char *machine = decoder->machine;
  168. const asn1_action_t *actions = decoder->actions;
  169. size_t machlen = decoder->machlen;
  170. enum asn1_opcode op;
  171. unsigned char tag = 0, csp = 0, jsp = 0, optag = 0, hdr = 0;
  172. const char *errmsg;
  173. size_t pc = 0, dp = 0, tdp = 0, len = 0;
  174. int ret;
  175. unsigned char flags = 0;
  176. #define FLAG_INDEFINITE_LENGTH 0x01
  177. #define FLAG_MATCHED 0x02
  178. #define FLAG_LAST_MATCHED 0x04 /* Last tag matched */
  179. #define FLAG_CONS 0x20 /* Corresponds to CONS bit in the opcode tag
  180. * - ie. whether or not we are going to parse
  181. * a compound type.
  182. */
  183. #define NR_CONS_STACK 10
  184. unsigned short cons_dp_stack[NR_CONS_STACK];
  185. unsigned short cons_datalen_stack[NR_CONS_STACK];
  186. unsigned char cons_hdrlen_stack[NR_CONS_STACK];
  187. #define NR_JUMP_STACK 10
  188. unsigned char jump_stack[NR_JUMP_STACK];
  189. if (datalen > 65535)
  190. return -EMSGSIZE;
  191. next_op:
  192. pr_debug("next_op: pc=\e[32m%zu\e[m/%zu dp=\e[33m%zu\e[m/%zu C=%d J=%d\n",
  193. pc, machlen, dp, datalen, csp, jsp);
  194. if (unlikely(pc >= machlen))
  195. goto machine_overrun_error;
  196. op = machine[pc];
  197. if (unlikely(pc + asn1_op_lengths[op] > machlen))
  198. goto machine_overrun_error;
  199. /* If this command is meant to match a tag, then do that before
  200. * evaluating the command.
  201. */
  202. if (op <= ASN1_OP__MATCHES_TAG) {
  203. unsigned char tmp;
  204. /* Skip conditional matches if possible */
  205. if ((op & ASN1_OP_MATCH__COND && flags & FLAG_MATCHED) ||
  206. (op & ASN1_OP_MATCH__SKIP && dp == datalen)) {
  207. flags &= ~FLAG_LAST_MATCHED;
  208. pc += asn1_op_lengths[op];
  209. goto next_op;
  210. }
  211. flags = 0;
  212. hdr = 2;
  213. /* Extract a tag from the data */
  214. if (unlikely(datalen - dp < 2))
  215. goto data_overrun_error;
  216. tag = data[dp++];
  217. if (unlikely((tag & 0x1f) == ASN1_LONG_TAG))
  218. goto long_tag_not_supported;
  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. /* Determine whether the tag matched */
  230. tmp = optag ^ tag;
  231. tmp &= ~(optag & ASN1_CONS_BIT);
  232. pr_debug("- match? %02x %02x %02x\n", tag, optag, tmp);
  233. if (tmp != 0) {
  234. /* All odd-numbered tags are MATCH_OR_SKIP. */
  235. if (op & ASN1_OP_MATCH__SKIP) {
  236. pc += asn1_op_lengths[op];
  237. dp--;
  238. goto next_op;
  239. }
  240. goto tag_mismatch;
  241. }
  242. }
  243. flags |= FLAG_MATCHED;
  244. len = data[dp++];
  245. if (len > 0x7f) {
  246. if (unlikely(len == ASN1_INDEFINITE_LENGTH)) {
  247. /* Indefinite length */
  248. if (unlikely(!(tag & ASN1_CONS_BIT)))
  249. goto indefinite_len_primitive;
  250. flags |= FLAG_INDEFINITE_LENGTH;
  251. if (unlikely(2 > datalen - dp))
  252. goto data_overrun_error;
  253. } else {
  254. int n = len - 0x80;
  255. if (unlikely(n > 2))
  256. goto length_too_long;
  257. if (unlikely(n > datalen - dp))
  258. goto data_overrun_error;
  259. hdr += n;
  260. for (len = 0; n > 0; n--) {
  261. len <<= 8;
  262. len |= data[dp++];
  263. }
  264. if (unlikely(len > datalen - dp))
  265. goto data_overrun_error;
  266. }
  267. } else {
  268. if (unlikely(len > datalen - dp))
  269. goto data_overrun_error;
  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. pr_debug("- TAG: %02x %zu%s\n",
  288. tag, len, flags & FLAG_CONS ? " CONS" : "");
  289. tdp = dp;
  290. }
  291. /* Decide how to handle the operation */
  292. switch (op) {
  293. case ASN1_OP_MATCH:
  294. case ASN1_OP_MATCH_OR_SKIP:
  295. case ASN1_OP_MATCH_ACT:
  296. case ASN1_OP_MATCH_ACT_OR_SKIP:
  297. case ASN1_OP_MATCH_ANY:
  298. case ASN1_OP_MATCH_ANY_OR_SKIP:
  299. case ASN1_OP_MATCH_ANY_ACT:
  300. case ASN1_OP_MATCH_ANY_ACT_OR_SKIP:
  301. case ASN1_OP_COND_MATCH_OR_SKIP:
  302. case ASN1_OP_COND_MATCH_ACT_OR_SKIP:
  303. case ASN1_OP_COND_MATCH_ANY:
  304. case ASN1_OP_COND_MATCH_ANY_OR_SKIP:
  305. case ASN1_OP_COND_MATCH_ANY_ACT:
  306. case ASN1_OP_COND_MATCH_ANY_ACT_OR_SKIP:
  307. if (!(flags & FLAG_CONS)) {
  308. if (flags & FLAG_INDEFINITE_LENGTH) {
  309. size_t tmp = dp;
  310. ret = asn1_find_indefinite_length(
  311. data, datalen, &tmp, &len, &errmsg);
  312. if (ret < 0)
  313. goto error;
  314. }
  315. pr_debug("- LEAF: %zu\n", len);
  316. }
  317. if (op & ASN1_OP_MATCH__ACT) {
  318. unsigned char act;
  319. if (op & ASN1_OP_MATCH__ANY)
  320. act = machine[pc + 1];
  321. else
  322. act = machine[pc + 2];
  323. ret = actions[act](context, hdr, tag, data + dp, len);
  324. if (ret < 0)
  325. return ret;
  326. }
  327. if (!(flags & FLAG_CONS))
  328. dp += len;
  329. pc += asn1_op_lengths[op];
  330. goto next_op;
  331. case ASN1_OP_MATCH_JUMP:
  332. case ASN1_OP_MATCH_JUMP_OR_SKIP:
  333. case ASN1_OP_COND_MATCH_JUMP_OR_SKIP:
  334. pr_debug("- MATCH_JUMP\n");
  335. if (unlikely(jsp == NR_JUMP_STACK))
  336. goto jump_stack_overflow;
  337. jump_stack[jsp++] = pc + asn1_op_lengths[op];
  338. pc = machine[pc + 2];
  339. goto next_op;
  340. case ASN1_OP_COND_FAIL:
  341. if (unlikely(!(flags & FLAG_MATCHED)))
  342. goto tag_mismatch;
  343. pc += asn1_op_lengths[op];
  344. goto next_op;
  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. case ASN1_OP_END_SET:
  353. case ASN1_OP_END_SET_ACT:
  354. if (unlikely(!(flags & FLAG_MATCHED)))
  355. goto tag_mismatch;
  356. /* fall through */
  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. if (op & ASN1_OP_END__ACT) {
  404. unsigned char act;
  405. if (op & ASN1_OP_END__OF)
  406. act = machine[pc + 2];
  407. else
  408. act = machine[pc + 1];
  409. ret = actions[act](context, hdr, 0, data + tdp, len);
  410. if (ret < 0)
  411. return ret;
  412. }
  413. pc += asn1_op_lengths[op];
  414. goto next_op;
  415. case ASN1_OP_MAYBE_ACT:
  416. if (!(flags & FLAG_LAST_MATCHED)) {
  417. pc += asn1_op_lengths[op];
  418. goto next_op;
  419. }
  420. /* fall through */
  421. case ASN1_OP_ACT:
  422. ret = actions[machine[pc + 1]](context, hdr, tag, data + tdp, len);
  423. if (ret < 0)
  424. return ret;
  425. pc += asn1_op_lengths[op];
  426. goto next_op;
  427. case ASN1_OP_RETURN:
  428. if (unlikely(jsp <= 0))
  429. goto jump_stack_underflow;
  430. pc = jump_stack[--jsp];
  431. flags |= FLAG_MATCHED | FLAG_LAST_MATCHED;
  432. goto next_op;
  433. default:
  434. break;
  435. }
  436. /* Shouldn't reach here */
  437. pr_err("ASN.1 decoder error: Found reserved opcode (%u) pc=%zu\n",
  438. op, pc);
  439. return -EBADMSG;
  440. data_overrun_error:
  441. errmsg = "Data overrun error";
  442. goto error;
  443. machine_overrun_error:
  444. errmsg = "Machine overrun error";
  445. goto error;
  446. jump_stack_underflow:
  447. errmsg = "Jump stack underflow";
  448. goto error;
  449. jump_stack_overflow:
  450. errmsg = "Jump stack overflow";
  451. goto error;
  452. cons_stack_underflow:
  453. errmsg = "Cons stack underflow";
  454. goto error;
  455. cons_stack_overflow:
  456. errmsg = "Cons stack overflow";
  457. goto error;
  458. cons_length_error:
  459. errmsg = "Cons length error";
  460. goto error;
  461. missing_eoc:
  462. errmsg = "Missing EOC in indefinite len cons";
  463. goto error;
  464. invalid_eoc:
  465. errmsg = "Invalid length EOC";
  466. goto error;
  467. length_too_long:
  468. errmsg = "Unsupported length";
  469. goto error;
  470. indefinite_len_primitive:
  471. errmsg = "Indefinite len primitive not permitted";
  472. goto error;
  473. tag_mismatch:
  474. errmsg = "Unexpected tag";
  475. goto error;
  476. long_tag_not_supported:
  477. errmsg = "Long tag not supported";
  478. error:
  479. pr_debug("\nASN1: %s [m=%zu d=%zu ot=%02x t=%02x l=%zu]\n",
  480. errmsg, pc, dp, optag, tag, len);
  481. return -EBADMSG;
  482. }
  483. EXPORT_SYMBOL_GPL(asn1_ber_decoder);
  484. MODULE_LICENSE("GPL");