yubikey.c revision 1.3 
1/* $OpenBSD: yubikey.c,v 1.3 2012/11/23 23:53:54 halex Exp $ */
2
3/*
4 * Written by Simon Josefsson <simon@josefsson.org>.
5 * Copyright (c) 2006, 2007, 2008, 2009 Yubico AB
6 * Copyright (c) 2010 Daniel Hartmeier <daniel@benzedrine.cx>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions are
11 * met:
12 *
13 * * Redistributions of source code must retain the above copyright
14 *   notice, this list of conditions and the following disclaimer.
15 *
16 * * Redistributions in binary form must reproduce the above
17 *   copyright notice, this list of conditions and the following
18 *   disclaimer in the documentation and/or other materials provided
19 *   with the distribution.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 *
33 */
34
35#include <ctype.h>
36
37#include "yubikey.h"
38
39static const uint8_t RC[] = {
40	0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36
41};
42
43static const uint8_t rijndael_sbox[] = {
44	0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5,
45	0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
46	0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0,
47	0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
48	0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC,
49	0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
50	0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A,
51	0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
52	0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0,
53	0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
54	0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B,
55	0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
56	0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85,
57	0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
58	0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5,
59	0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
60	0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17,
61	0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
62	0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88,
63	0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
64	0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C,
65	0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
66	0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9,
67	0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
68	0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6,
69	0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
70	0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E,
71	0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
72	0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94,
73	0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
74	0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68,
75	0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16
76};
77
78static const uint8_t rijndael_inv_sbox[] = {
79	0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38,
80	0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
81	0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87,
82	0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
83	0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D,
84	0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
85	0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2,
86	0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
87	0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16,
88	0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
89	0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA,
90	0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
91	0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A,
92	0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
93	0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02,
94	0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
95	0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA,
96	0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
97	0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85,
98	0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
99	0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89,
100	0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
101	0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20,
102	0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
103	0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31,
104	0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
105	0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D,
106	0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
107	0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0,
108	0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
109	0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26,
110	0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D
111};
112
113static inline uint8_t
114xtime(uint8_t b)
115{
116	return (b & 0x80) ? ((b << 1) ^ 0x1b) : (b << 1);
117}
118
119#define NUMBER_OF_ROUNDS 10
120
121void
122yubikey_aes_decrypt(uint8_t *state, const uint8_t *key)
123{
124	uint8_t i, j, round_key[0x10];
125	uint8_t a02x, a13x;
126	uint8_t a02xx, a13xx;
127	uint8_t k1, k2;
128
129	memcpy(round_key, key, sizeof(round_key));
130	for (i = 0; i < NUMBER_OF_ROUNDS; i++) {
131		round_key[0] ^= RC[i];
132
133		round_key[0] ^= rijndael_sbox[round_key[13]];
134		round_key[1] ^= rijndael_sbox[round_key[14]];
135		round_key[2] ^= rijndael_sbox[round_key[15]];
136		round_key[3] ^= rijndael_sbox[round_key[12]];
137
138		for (j = 4; j < 16; j++)
139			round_key[j] ^= round_key[j - 4];
140	}
141	for (i = 0; i < 0x10; i++)
142		state[i] ^= round_key[i];
143
144	for (i = 1; i <= NUMBER_OF_ROUNDS; i++) {
145		/* inv_byte_sub_shift_row(); */
146
147		/* First row: 0 shift, 0 4 8 12 */
148		state[0] = rijndael_inv_sbox[state[0]];
149		state[4] = rijndael_inv_sbox[state[4]];
150		state[8] = rijndael_inv_sbox[state[8]];
151		state[12] = rijndael_inv_sbox[state[12]];
152
153		/* Second row: -1 shift, 1 5 9 13 */
154		j = state[13];
155		state[13] = rijndael_inv_sbox[state[9]];
156		state[9] = rijndael_inv_sbox[state[5]];
157		state[5] = rijndael_inv_sbox[state[1]];
158		state[1] = rijndael_inv_sbox[j];
159
160		/* Third row: -2 shift, 2 6 10 14 */
161		j = state[2];
162		state[2] = rijndael_inv_sbox[state[10]];
163		state[10] = rijndael_inv_sbox[j];
164		j = state[6];
165		state[6] = rijndael_inv_sbox[state[14]];
166		state[14] = rijndael_inv_sbox[j];
167
168		/* Fourth row: -3 shift, 3 7 11 15 */
169		j = state[3];
170		state[3] = rijndael_inv_sbox[state[7]];
171		state[7] = rijndael_inv_sbox[state[11]];
172		state[11] = rijndael_inv_sbox[state[15]];
173		state[15] = rijndael_inv_sbox[j];
174
175		/* get_inv_round_key(i); */
176
177		for (j = 15; j > 3; j--)
178			round_key[j] ^= round_key[j - 4];
179
180		round_key[0] ^= (RC[NUMBER_OF_ROUNDS - i] ^
181		    rijndael_sbox[round_key[13]]);
182
183		round_key[1] ^= rijndael_sbox[round_key[14]];
184		round_key[2] ^= rijndael_sbox[round_key[15]];
185		round_key[3] ^= rijndael_sbox[round_key[12]];
186
187		for (j = 0; j < 16; j++)
188			state[j] ^= round_key[j];
189		if (i != NUMBER_OF_ROUNDS) {
190			/* inv_mix_column(); */
191
192			for (j = 0; j < 16; j += 4) {
193				k1 = state[j] ^ state[j + 2];
194				a02x = xtime(k1);
195				k2 = state[j + 1] ^ state[j + 3];
196				a13x = xtime(k2);
197
198				k1 ^= (k2 ^ xtime(state[j + 1] ^ state[j + 2]));
199				k2 = k1;
200
201				a02xx = xtime(a02x);
202				a13xx = xtime(a13x);
203
204
205				k1 ^= (xtime(a02xx ^ a13xx) ^ a02xx);
206				k2 ^= (xtime(a02xx ^ a13xx) ^ a13xx);
207
208				state[j] ^= (k1 ^ a02x);
209				state[j + 1] ^= k2;
210				state[j + 2] ^= (k1 ^ a13x);
211				state[j + 3] ^= (k2 ^ a02x ^ a13x);
212			}
213		}
214
215	}
216}
217
218uint16_t
219yubikey_crc16(const uint8_t *buf, size_t buf_size)
220{
221	uint16_t m_crc = 0xffff;
222
223	while (buf_size--) {
224		int i, j;
225
226		m_crc ^= (uint8_t)*buf++ & 0xFF;
227		for (i = 0; i < 8; i++) {
228			j = m_crc & 1;
229			m_crc >>= 1;
230			if (j)
231				m_crc ^= 0x8408;
232		}
233	}
234	return m_crc;
235}
236
237static const char hex_trans[] = "0123456789abcdef";
238
239void
240yubikey_hex_encode(char *dst, const char *src, size_t srcSize)
241{
242	while (srcSize--) {
243		*dst++ = hex_trans[(*src >> 4) & 0xf];
244		*dst++ = hex_trans[*src++ & 0xf];
245	}
246	*dst = '\0';
247}
248
249void
250yubikey_hex_decode(char *dst, const char *src, size_t dstSize)
251{
252	char b;
253	int flag = 0;
254	char *p1;
255
256	for (; *src && dstSize > 0; src++) {
257		p1 = strchr(hex_trans, tolower((unsigned char)*src));
258		if (p1 == NULL)
259			b = 0;
260		else
261			b = (char)(p1 - hex_trans);
262		if ((flag = !flag))
263			*dst = b;
264		else {
265			*dst = (*dst << 4) | b;
266			dst++;
267			dstSize--;
268		}
269	}
270	while (dstSize--)
271		*dst++ = 0;
272}
273
274static const char modhex_trans[] = "cbdefghijklnrtuv";
275
276void
277yubikey_modhex_decode(char *dst, const char *src, size_t dstSize)
278{
279	char b;
280	int flag = 0;
281	char *p1;
282
283	for (; *src && dstSize > 0; src++) {
284		p1 = strchr(modhex_trans, tolower((unsigned char)*src));
285		if (p1 == NULL)
286			b = 0;
287		else
288			b = (char)(p1 - modhex_trans);
289
290		if ((flag = !flag))
291			*dst = b;
292		else {
293			*dst = (*dst << 4) | b;
294			dst++;
295			dstSize--;
296		}
297	}
298	while (dstSize--)
299		*dst++ = 0;
300}
301
302void
303yubikey_parse(const uint8_t token[32], const uint8_t key[16],
304    yubikey_token_t out)
305{
306	memset(out, 0, sizeof(*out));
307	yubikey_modhex_decode((void *)out, (char *)token, sizeof(*out));
308	yubikey_aes_decrypt((void *)out, key);
309}
310