diff options
-rw-r--r-- | include/linux/oid_registry.h | 90 | ||||
-rw-r--r-- | lib/.gitignore | 2 | ||||
-rw-r--r-- | lib/Kconfig | 5 | ||||
-rw-r--r-- | lib/Makefile | 16 | ||||
-rwxr-xr-x | lib/build_OID_registry | 209 | ||||
-rw-r--r-- | lib/oid_registry.c | 89 |
6 files changed, 410 insertions, 1 deletions
diff --git a/include/linux/oid_registry.h b/include/linux/oid_registry.h new file mode 100644 index 000000000000..5928546bf00a --- /dev/null +++ b/include/linux/oid_registry.h | |||
@@ -0,0 +1,90 @@ | |||
1 | /* ASN.1 Object identifier (OID) registry | ||
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 | #ifndef _LINUX_OID_REGISTRY_H | ||
13 | #define _LINUX_OID_REGISTRY_H | ||
14 | |||
15 | #include <linux/types.h> | ||
16 | |||
17 | /* | ||
18 | * OIDs are turned into these values if possible, or OID__NR if not held here. | ||
19 | * | ||
20 | * NOTE! Do not mess with the format of each line as this is read by | ||
21 | * build_OID_registry.pl to generate the data for look_up_OID(). | ||
22 | */ | ||
23 | enum OID { | ||
24 | OID_id_dsa_with_sha1, /* 1.2.840.10030.4.3 */ | ||
25 | OID_id_dsa, /* 1.2.840.10040.4.1 */ | ||
26 | OID_id_ecdsa_with_sha1, /* 1.2.840.10045.4.1 */ | ||
27 | OID_id_ecPublicKey, /* 1.2.840.10045.2.1 */ | ||
28 | |||
29 | /* PKCS#1 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1)} */ | ||
30 | OID_rsaEncryption, /* 1.2.840.113549.1.1.1 */ | ||
31 | OID_md2WithRSAEncryption, /* 1.2.840.113549.1.1.2 */ | ||
32 | OID_md3WithRSAEncryption, /* 1.2.840.113549.1.1.3 */ | ||
33 | OID_md4WithRSAEncryption, /* 1.2.840.113549.1.1.4 */ | ||
34 | OID_sha1WithRSAEncryption, /* 1.2.840.113549.1.1.5 */ | ||
35 | OID_sha256WithRSAEncryption, /* 1.2.840.113549.1.1.11 */ | ||
36 | OID_sha384WithRSAEncryption, /* 1.2.840.113549.1.1.12 */ | ||
37 | OID_sha512WithRSAEncryption, /* 1.2.840.113549.1.1.13 */ | ||
38 | OID_sha224WithRSAEncryption, /* 1.2.840.113549.1.1.14 */ | ||
39 | /* PKCS#7 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-7(7)} */ | ||
40 | OID_data, /* 1.2.840.113549.1.7.1 */ | ||
41 | OID_signed_data, /* 1.2.840.113549.1.7.2 */ | ||
42 | /* PKCS#9 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-9(9)} */ | ||
43 | OID_email_address, /* 1.2.840.113549.1.9.1 */ | ||
44 | OID_content_type, /* 1.2.840.113549.1.9.3 */ | ||
45 | OID_messageDigest, /* 1.2.840.113549.1.9.4 */ | ||
46 | OID_signingTime, /* 1.2.840.113549.1.9.5 */ | ||
47 | OID_smimeCapabilites, /* 1.2.840.113549.1.9.15 */ | ||
48 | OID_smimeAuthenticatedAttrs, /* 1.2.840.113549.1.9.16.2.11 */ | ||
49 | |||
50 | /* {iso(1) member-body(2) us(840) rsadsi(113549) digestAlgorithm(2)} */ | ||
51 | OID_md2, /* 1.2.840.113549.2.2 */ | ||
52 | OID_md4, /* 1.2.840.113549.2.4 */ | ||
53 | OID_md5, /* 1.2.840.113549.2.5 */ | ||
54 | |||
55 | OID_certAuthInfoAccess, /* 1.3.6.1.5.5.7.1.1 */ | ||
56 | OID_msOutlookExpress, /* 1.3.6.1.4.1.311.16.4 */ | ||
57 | OID_sha1, /* 1.3.14.3.2.26 */ | ||
58 | |||
59 | /* Distinguished Name attribute IDs [RFC 2256] */ | ||
60 | OID_commonName, /* 2.5.4.3 */ | ||
61 | OID_surname, /* 2.5.4.4 */ | ||
62 | OID_countryName, /* 2.5.4.6 */ | ||
63 | OID_locality, /* 2.5.4.7 */ | ||
64 | OID_stateOrProvinceName, /* 2.5.4.8 */ | ||
65 | OID_organizationName, /* 2.5.4.10 */ | ||
66 | OID_organizationUnitName, /* 2.5.4.11 */ | ||
67 | OID_title, /* 2.5.4.12 */ | ||
68 | OID_description, /* 2.5.4.13 */ | ||
69 | OID_name, /* 2.5.4.41 */ | ||
70 | OID_givenName, /* 2.5.4.42 */ | ||
71 | OID_initials, /* 2.5.4.43 */ | ||
72 | OID_generationalQualifier, /* 2.5.4.44 */ | ||
73 | |||
74 | /* Certificate extension IDs */ | ||
75 | OID_subjectKeyIdentifier, /* 2.5.29.14 */ | ||
76 | OID_keyUsage, /* 2.5.29.15 */ | ||
77 | OID_subjectAltName, /* 2.5.29.17 */ | ||
78 | OID_issuerAltName, /* 2.5.29.18 */ | ||
79 | OID_basicConstraints, /* 2.5.29.19 */ | ||
80 | OID_crlDistributionPoints, /* 2.5.29.31 */ | ||
81 | OID_certPolicies, /* 2.5.29.32 */ | ||
82 | OID_authorityKeyIdentifier, /* 2.5.29.35 */ | ||
83 | OID_extKeyUsage, /* 2.5.29.37 */ | ||
84 | |||
85 | OID__NR | ||
86 | }; | ||
87 | |||
88 | extern enum OID look_up_OID(const void *data, size_t datasize); | ||
89 | |||
90 | #endif /* _LINUX_OID_REGISTRY_H */ | ||
diff --git a/lib/.gitignore b/lib/.gitignore index 3bef1ea94c99..09aae85418ab 100644 --- a/lib/.gitignore +++ b/lib/.gitignore | |||
@@ -3,4 +3,4 @@ | |||
3 | # | 3 | # |
4 | gen_crc32table | 4 | gen_crc32table |
5 | crc32table.h | 5 | crc32table.h |
6 | 6 | oid_registry_data.c | |
diff --git a/lib/Kconfig b/lib/Kconfig index bb94c1ba616a..4b31a46fb307 100644 --- a/lib/Kconfig +++ b/lib/Kconfig | |||
@@ -396,4 +396,9 @@ config SIGNATURE | |||
396 | config LIBFDT | 396 | config LIBFDT |
397 | bool | 397 | bool |
398 | 398 | ||
399 | config OID_REGISTRY | ||
400 | tristate | ||
401 | help | ||
402 | Enable fast lookup object identifier registry. | ||
403 | |||
399 | endmenu | 404 | endmenu |
diff --git a/lib/Makefile b/lib/Makefile index 42d283edc4d3..b0428960939f 100644 --- a/lib/Makefile +++ b/lib/Makefile | |||
@@ -150,3 +150,19 @@ quiet_cmd_crc32 = GEN $@ | |||
150 | 150 | ||
151 | $(obj)/crc32table.h: $(obj)/gen_crc32table | 151 | $(obj)/crc32table.h: $(obj)/gen_crc32table |
152 | $(call cmd,crc32) | 152 | $(call cmd,crc32) |
153 | |||
154 | # | ||
155 | # Build a fast OID lookip registry from include/linux/oid_registry.h | ||
156 | # | ||
157 | obj-$(CONFIG_OID_REGISTRY) += oid_registry.o | ||
158 | |||
159 | $(obj)/oid_registry.c: $(obj)/oid_registry_data.c | ||
160 | |||
161 | $(obj)/oid_registry_data.c: $(srctree)/include/linux/oid_registry.h \ | ||
162 | $(src)/build_OID_registry | ||
163 | $(call cmd,build_OID_registry) | ||
164 | |||
165 | quiet_cmd_build_OID_registry = GEN $@ | ||
166 | cmd_build_OID_registry = perl $(srctree)/$(src)/build_OID_registry $< $@ | ||
167 | |||
168 | clean-files += oid_registry_data.c | ||
diff --git a/lib/build_OID_registry b/lib/build_OID_registry new file mode 100755 index 000000000000..dfbdaab81bc8 --- /dev/null +++ b/lib/build_OID_registry | |||
@@ -0,0 +1,209 @@ | |||
1 | #!/usr/bin/perl -w | ||
2 | # | ||
3 | # Build a static ASN.1 Object Identified (OID) registry | ||
4 | # | ||
5 | # Copyright (C) 2012 Red Hat, Inc. All Rights Reserved. | ||
6 | # Written by David Howells (dhowells@redhat.com) | ||
7 | # | ||
8 | # This program is free software; you can redistribute it and/or | ||
9 | # modify it under the terms of the GNU General Public Licence | ||
10 | # as published by the Free Software Foundation; either version | ||
11 | # 2 of the Licence, or (at your option) any later version. | ||
12 | # | ||
13 | |||
14 | use strict; | ||
15 | |||
16 | my @names = (); | ||
17 | my @oids = (); | ||
18 | |||
19 | if ($#ARGV != 1) { | ||
20 | print STDERR "Format: ", $0, " <in-h-file> <out-c-file>\n"; | ||
21 | exit(2); | ||
22 | } | ||
23 | |||
24 | # | ||
25 | # Open the file to read from | ||
26 | # | ||
27 | open IN_FILE, "<$ARGV[0]" || die; | ||
28 | while (<IN_FILE>) { | ||
29 | chomp; | ||
30 | if (m!\s+OID_([a-zA-z][a-zA-Z0-9_]+),\s+/[*]\s+([012][.0-9]*)\s+[*]/!) { | ||
31 | push @names, $1; | ||
32 | push @oids, $2; | ||
33 | } | ||
34 | } | ||
35 | close IN_FILE || die; | ||
36 | |||
37 | # | ||
38 | # Open the files to write into | ||
39 | # | ||
40 | open C_FILE, ">$ARGV[1]" or die; | ||
41 | print C_FILE "/*\n"; | ||
42 | print C_FILE " * Automatically generated by ", $0, ". Do not edit\n"; | ||
43 | print C_FILE " */\n"; | ||
44 | |||
45 | # | ||
46 | # Split the data up into separate lists and also determine the lengths of the | ||
47 | # encoded data arrays. | ||
48 | # | ||
49 | my @indices = (); | ||
50 | my @lengths = (); | ||
51 | my $total_length = 0; | ||
52 | |||
53 | print "Compiling ", $#names + 1, " OIDs\n"; | ||
54 | |||
55 | for (my $i = 0; $i <= $#names; $i++) { | ||
56 | my $name = $names[$i]; | ||
57 | my $oid = $oids[$i]; | ||
58 | |||
59 | my @components = split(/[.]/, $oid); | ||
60 | |||
61 | # Determine the encoded length of this OID | ||
62 | my $size = $#components; | ||
63 | for (my $loop = 2; $loop <= $#components; $loop++) { | ||
64 | my $c = $components[$loop]; | ||
65 | |||
66 | # We will base128 encode the number | ||
67 | my $tmp = ($c == 0) ? 0 : int(log($c)/log(2)); | ||
68 | $tmp = int($tmp / 7); | ||
69 | $size += $tmp; | ||
70 | } | ||
71 | push @lengths, $size; | ||
72 | push @indices, $total_length; | ||
73 | $total_length += $size; | ||
74 | } | ||
75 | |||
76 | # | ||
77 | # Emit the look-up-by-OID index table | ||
78 | # | ||
79 | print C_FILE "\n"; | ||
80 | if ($total_length <= 255) { | ||
81 | print C_FILE "static const unsigned char oid_index[OID__NR + 1] = {\n"; | ||
82 | } else { | ||
83 | print C_FILE "static const unsigned short oid_index[OID__NR + 1] = {\n"; | ||
84 | } | ||
85 | for (my $i = 0; $i <= $#names; $i++) { | ||
86 | print C_FILE "\t[OID_", $names[$i], "] = ", $indices[$i], ",\n" | ||
87 | } | ||
88 | print C_FILE "\t[OID__NR] = ", $total_length, "\n"; | ||
89 | print C_FILE "};\n"; | ||
90 | |||
91 | # | ||
92 | # Encode the OIDs | ||
93 | # | ||
94 | my @encoded_oids = (); | ||
95 | |||
96 | for (my $i = 0; $i <= $#names; $i++) { | ||
97 | my @octets = (); | ||
98 | |||
99 | my @components = split(/[.]/, $oids[$i]); | ||
100 | |||
101 | push @octets, $components[0] * 40 + $components[1]; | ||
102 | |||
103 | for (my $loop = 2; $loop <= $#components; $loop++) { | ||
104 | my $c = $components[$loop]; | ||
105 | |||
106 | # Base128 encode the number | ||
107 | my $tmp = ($c == 0) ? 0 : int(log($c)/log(2)); | ||
108 | $tmp = int($tmp / 7); | ||
109 | |||
110 | for (; $tmp > 0; $tmp--) { | ||
111 | push @octets, (($c >> $tmp * 7) & 0x7f) | 0x80; | ||
112 | } | ||
113 | push @octets, $c & 0x7f; | ||
114 | } | ||
115 | |||
116 | push @encoded_oids, \@octets; | ||
117 | } | ||
118 | |||
119 | # | ||
120 | # Create a hash value for each OID | ||
121 | # | ||
122 | my @hash_values = (); | ||
123 | for (my $i = 0; $i <= $#names; $i++) { | ||
124 | my @octets = @{$encoded_oids[$i]}; | ||
125 | |||
126 | my $hash = $#octets; | ||
127 | foreach (@octets) { | ||
128 | $hash += $_ * 33; | ||
129 | } | ||
130 | |||
131 | $hash = ($hash >> 24) ^ ($hash >> 16) ^ ($hash >> 8) ^ ($hash); | ||
132 | |||
133 | push @hash_values, $hash & 0xff; | ||
134 | } | ||
135 | |||
136 | # | ||
137 | # Emit the OID data | ||
138 | # | ||
139 | print C_FILE "\n"; | ||
140 | print C_FILE "static const unsigned char oid_data[", $total_length, "] = {\n"; | ||
141 | for (my $i = 0; $i <= $#names; $i++) { | ||
142 | my @octets = @{$encoded_oids[$i]}; | ||
143 | print C_FILE "\t"; | ||
144 | print C_FILE $_, ", " foreach (@octets); | ||
145 | print C_FILE "\t// ", $names[$i]; | ||
146 | print C_FILE "\n"; | ||
147 | } | ||
148 | print C_FILE "};\n"; | ||
149 | |||
150 | # | ||
151 | # Build the search index table (ordered by length then hash then content) | ||
152 | # | ||
153 | my @index_table = ( 0 .. $#names ); | ||
154 | |||
155 | @index_table = sort { | ||
156 | my @octets_a = @{$encoded_oids[$a]}; | ||
157 | my @octets_b = @{$encoded_oids[$b]}; | ||
158 | |||
159 | return $hash_values[$a] <=> $hash_values[$b] | ||
160 | if ($hash_values[$a] != $hash_values[$b]); | ||
161 | return $#octets_a <=> $#octets_b | ||
162 | if ($#octets_a != $#octets_b); | ||
163 | for (my $i = $#octets_a; $i >= 0; $i--) { | ||
164 | return $octets_a[$i] <=> $octets_b[$i] | ||
165 | if ($octets_a[$i] != $octets_b[$i]); | ||
166 | } | ||
167 | return 0; | ||
168 | |||
169 | } @index_table; | ||
170 | |||
171 | # | ||
172 | # Emit the search index and hash value table | ||
173 | # | ||
174 | print C_FILE "\n"; | ||
175 | print C_FILE "static const struct {\n"; | ||
176 | print C_FILE "\tunsigned char hash;\n"; | ||
177 | if ($#names <= 255) { | ||
178 | print C_FILE "\tenum OID oid : 8;\n"; | ||
179 | } else { | ||
180 | print C_FILE "\tenum OID oid : 16;\n"; | ||
181 | } | ||
182 | print C_FILE "} oid_search_table[OID__NR] = {\n"; | ||
183 | for (my $i = 0; $i <= $#names; $i++) { | ||
184 | my @octets = @{$encoded_oids[$index_table[$i]]}; | ||
185 | printf(C_FILE "\t[%3u] = { %3u, OID_%-35s }, // ", | ||
186 | $i, | ||
187 | $hash_values[$index_table[$i]], | ||
188 | $names[$index_table[$i]]); | ||
189 | printf C_FILE "%02x", $_ foreach (@octets); | ||
190 | print C_FILE "\n"; | ||
191 | } | ||
192 | print C_FILE "};\n"; | ||
193 | |||
194 | # | ||
195 | # Emit the OID debugging name table | ||
196 | # | ||
197 | #print C_FILE "\n"; | ||
198 | #print C_FILE "const char *const oid_name_table[OID__NR + 1] = {\n"; | ||
199 | # | ||
200 | #for (my $i = 0; $i <= $#names; $i++) { | ||
201 | # print C_FILE "\t\"", $names[$i], "\",\n" | ||
202 | #} | ||
203 | #print C_FILE "\t\"Unknown-OID\"\n"; | ||
204 | #print C_FILE "};\n"; | ||
205 | |||
206 | # | ||
207 | # Polish off | ||
208 | # | ||
209 | close C_FILE or die; | ||
diff --git a/lib/oid_registry.c b/lib/oid_registry.c new file mode 100644 index 000000000000..33cfd171f627 --- /dev/null +++ b/lib/oid_registry.c | |||
@@ -0,0 +1,89 @@ | |||
1 | /* ASN.1 Object identifier (OID) registry | ||
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/oid_registry.h> | ||
14 | #include "oid_registry_data.c" | ||
15 | |||
16 | /** | ||
17 | * look_up_OID - Find an OID registration for the specified data | ||
18 | * @data: Binary representation of the OID | ||
19 | * @datasize: Size of the binary representation | ||
20 | */ | ||
21 | enum OID look_up_OID(const void *data, size_t datasize) | ||
22 | { | ||
23 | const unsigned char *octets = data; | ||
24 | enum OID oid; | ||
25 | unsigned char xhash; | ||
26 | unsigned i, j, k, hash; | ||
27 | size_t len; | ||
28 | |||
29 | /* Hash the OID data */ | ||
30 | hash = datasize - 1; | ||
31 | |||
32 | for (i = 0; i < datasize; i++) | ||
33 | hash += octets[i] * 33; | ||
34 | hash = (hash >> 24) ^ (hash >> 16) ^ (hash >> 8) ^ hash; | ||
35 | hash &= 0xff; | ||
36 | |||
37 | /* Binary search the OID registry. OIDs are stored in ascending order | ||
38 | * of hash value then ascending order of size and then in ascending | ||
39 | * order of reverse value. | ||
40 | */ | ||
41 | i = 0; | ||
42 | k = OID__NR; | ||
43 | while (i < k) { | ||
44 | j = (i + k) / 2; | ||
45 | |||
46 | xhash = oid_search_table[j].hash; | ||
47 | if (xhash > hash) { | ||
48 | k = j; | ||
49 | continue; | ||
50 | } | ||
51 | if (xhash < hash) { | ||
52 | i = j + 1; | ||
53 | continue; | ||
54 | } | ||
55 | |||
56 | oid = oid_search_table[j].oid; | ||
57 | len = oid_index[oid + 1] - oid_index[oid]; | ||
58 | if (len > datasize) { | ||
59 | k = j; | ||
60 | continue; | ||
61 | } | ||
62 | if (len < datasize) { | ||
63 | i = j + 1; | ||
64 | continue; | ||
65 | } | ||
66 | |||
67 | /* Variation is most likely to be at the tail end of the | ||
68 | * OID, so do the comparison in reverse. | ||
69 | */ | ||
70 | while (len > 0) { | ||
71 | unsigned char a = oid_data[oid_index[oid] + --len]; | ||
72 | unsigned char b = octets[len]; | ||
73 | if (a > b) { | ||
74 | k = j; | ||
75 | goto next; | ||
76 | } | ||
77 | if (a < b) { | ||
78 | i = j + 1; | ||
79 | goto next; | ||
80 | } | ||
81 | } | ||
82 | return oid; | ||
83 | next: | ||
84 | ; | ||
85 | } | ||
86 | |||
87 | return OID__NR; | ||
88 | } | ||
89 | EXPORT_SYMBOL_GPL(look_up_OID); | ||