yubikey.c revision 1.5 
1/* $OpenBSD: yubikey.c,v 1.5 2014/10/08 04:47:20 deraadt 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#include <stdlib.h>
37#include <wchar.h>
38#include <locale.h>
39#include <errno.h>
40
41#include "yubikey.h"
42#include "keymaps.h"
43
44static const uint8_t RC[] = {
45	0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36
46};
47
48static const uint8_t rijndael_sbox[] = {
49	0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5,
50	0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
51	0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0,
52	0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
53	0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC,
54	0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
55	0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A,
56	0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
57	0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0,
58	0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
59	0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B,
60	0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
61	0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85,
62	0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
63	0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5,
64	0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
65	0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17,
66	0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
67	0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88,
68	0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
69	0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C,
70	0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
71	0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9,
72	0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
73	0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6,
74	0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
75	0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E,
76	0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
77	0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94,
78	0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
79	0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68,
80	0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16
81};
82
83static const uint8_t rijndael_inv_sbox[] = {
84	0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38,
85	0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
86	0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87,
87	0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
88	0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D,
89	0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
90	0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2,
91	0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
92	0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16,
93	0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
94	0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA,
95	0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
96	0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A,
97	0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
98	0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02,
99	0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
100	0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA,
101	0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
102	0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85,
103	0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
104	0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89,
105	0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
106	0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20,
107	0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
108	0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31,
109	0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
110	0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D,
111	0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
112	0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0,
113	0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
114	0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26,
115	0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D
116};
117
118static inline uint8_t
119xtime(uint8_t b)
120{
121	return (b & 0x80) ? ((b << 1) ^ 0x1b) : (b << 1);
122}
123
124#define NUMBER_OF_ROUNDS 10
125
126void
127yubikey_aes_decrypt(uint8_t *state, const uint8_t *key)
128{
129	uint8_t i, j, round_key[0x10];
130	uint8_t a02x, a13x;
131	uint8_t a02xx, a13xx;
132	uint8_t k1, k2;
133
134	memcpy(round_key, key, sizeof(round_key));
135	for (i = 0; i < NUMBER_OF_ROUNDS; i++) {
136		round_key[0] ^= RC[i];
137
138		round_key[0] ^= rijndael_sbox[round_key[13]];
139		round_key[1] ^= rijndael_sbox[round_key[14]];
140		round_key[2] ^= rijndael_sbox[round_key[15]];
141		round_key[3] ^= rijndael_sbox[round_key[12]];
142
143		for (j = 4; j < 16; j++)
144			round_key[j] ^= round_key[j - 4];
145	}
146	for (i = 0; i < 0x10; i++)
147		state[i] ^= round_key[i];
148
149	for (i = 1; i <= NUMBER_OF_ROUNDS; i++) {
150		/* inv_byte_sub_shift_row(); */
151
152		/* First row: 0 shift, 0 4 8 12 */
153		state[0] = rijndael_inv_sbox[state[0]];
154		state[4] = rijndael_inv_sbox[state[4]];
155		state[8] = rijndael_inv_sbox[state[8]];
156		state[12] = rijndael_inv_sbox[state[12]];
157
158		/* Second row: -1 shift, 1 5 9 13 */
159		j = state[13];
160		state[13] = rijndael_inv_sbox[state[9]];
161		state[9] = rijndael_inv_sbox[state[5]];
162		state[5] = rijndael_inv_sbox[state[1]];
163		state[1] = rijndael_inv_sbox[j];
164
165		/* Third row: -2 shift, 2 6 10 14 */
166		j = state[2];
167		state[2] = rijndael_inv_sbox[state[10]];
168		state[10] = rijndael_inv_sbox[j];
169		j = state[6];
170		state[6] = rijndael_inv_sbox[state[14]];
171		state[14] = rijndael_inv_sbox[j];
172
173		/* Fourth row: -3 shift, 3 7 11 15 */
174		j = state[3];
175		state[3] = rijndael_inv_sbox[state[7]];
176		state[7] = rijndael_inv_sbox[state[11]];
177		state[11] = rijndael_inv_sbox[state[15]];
178		state[15] = rijndael_inv_sbox[j];
179
180		/* get_inv_round_key(i); */
181
182		for (j = 15; j > 3; j--)
183			round_key[j] ^= round_key[j - 4];
184
185		round_key[0] ^= (RC[NUMBER_OF_ROUNDS - i] ^
186		    rijndael_sbox[round_key[13]]);
187
188		round_key[1] ^= rijndael_sbox[round_key[14]];
189		round_key[2] ^= rijndael_sbox[round_key[15]];
190		round_key[3] ^= rijndael_sbox[round_key[12]];
191
192		for (j = 0; j < 16; j++)
193			state[j] ^= round_key[j];
194		if (i != NUMBER_OF_ROUNDS) {
195			/* inv_mix_column(); */
196
197			for (j = 0; j < 16; j += 4) {
198				k1 = state[j] ^ state[j + 2];
199				a02x = xtime(k1);
200				k2 = state[j + 1] ^ state[j + 3];
201				a13x = xtime(k2);
202
203				k1 ^= (k2 ^ xtime(state[j + 1] ^ state[j + 2]));
204				k2 = k1;
205
206				a02xx = xtime(a02x);
207				a13xx = xtime(a13x);
208
209
210				k1 ^= (xtime(a02xx ^ a13xx) ^ a02xx);
211				k2 ^= (xtime(a02xx ^ a13xx) ^ a13xx);
212
213				state[j] ^= (k1 ^ a02x);
214				state[j + 1] ^= k2;
215				state[j + 2] ^= (k1 ^ a13x);
216				state[j + 3] ^= (k2 ^ a02x ^ a13x);
217			}
218		}
219
220	}
221}
222
223uint16_t
224yubikey_crc16(const uint8_t *buf, size_t buf_size)
225{
226	uint16_t m_crc = 0xffff;
227
228	while (buf_size--) {
229		int i, j;
230
231		m_crc ^= (uint8_t)*buf++ & 0xFF;
232		for (i = 0; i < 8; i++) {
233			j = m_crc & 1;
234			m_crc >>= 1;
235			if (j)
236				m_crc ^= 0x8408;
237		}
238	}
239	return m_crc;
240}
241
242static const char hex_trans[] = "0123456789abcdef";
243
244void
245yubikey_hex_encode(char *dst, const char *src, size_t srcSize)
246{
247	while (srcSize--) {
248		*dst++ = hex_trans[(*src >> 4) & 0xf];
249		*dst++ = hex_trans[*src++ & 0xf];
250	}
251	*dst = '\0';
252}
253
254void
255yubikey_hex_decode(char *dst, const char *src, size_t dstSize)
256{
257	char b;
258	int flag = 0;
259	char *p1;
260
261	for (; *src && dstSize > 0; src++) {
262		p1 = strchr(hex_trans, tolower((unsigned char)*src));
263		if (p1 == NULL)
264			b = 0;
265		else
266			b = (char)(p1 - hex_trans);
267		if ((flag = !flag))
268			*dst = b;
269		else {
270			*dst = (*dst << 4) | b;
271			dst++;
272			dstSize--;
273		}
274	}
275	while (dstSize--)
276		*dst++ = 0;
277}
278
279static const char modhex_trans[] = "cbdefghijklnrtuv";
280
281void
282yubikey_modhex_decode(char *dst, const char *src, size_t dstSize)
283{
284	char b;
285	int flag = 0;
286	char *p1;
287
288	for (; *src && dstSize > 0; src++) {
289		p1 = strchr(modhex_trans, tolower((unsigned char)*src));
290		if (p1 == NULL)
291			b = 0;
292		else
293			b = (char)(p1 - modhex_trans);
294
295		if ((flag = !flag))
296			*dst = b;
297		else {
298			*dst = (*dst << 4) | b;
299			dst++;
300			dstSize--;
301		}
302	}
303	while (dstSize--)
304		*dst++ = 0;
305}
306
307uint8_t
308yubikey_keymap_decode(wchar_t *wpassword, char *token, int index)
309{
310	int c, j, found;
311	for (j=0; j<YUBIKEY_TOKEN_SIZE; j++) {
312		found = 0;
313		for (c=0; c<16; c++) {
314			if (wpassword[j] == keymaps[index][c]) {
315				token[j] = modhex_trans[c];
316				found++;
317				break;
318			}
319		}
320		if (found == 0)
321			return 1;
322	}
323	return 0;
324}
325
326int
327yubikey_parse(const uint8_t *password, const uint8_t key[YUBIKEY_KEY_SIZE],
328    yubikey_token_t out, int index)
329{
330	wchar_t *wpassword, *pp;
331	char token[YUBIKEY_TOKEN_SIZE + 1], *lc_ctype;
332	int len;
333
334	if (index < 0 || index >= YUBIKEY_KEYMAP_COUNT)
335		return -1;
336
337	len = strlen(password);
338	pp = wpassword = reallocarray(NULL, len + 1, sizeof(wchar_t));
339	if (pp == NULL)
340		return ENOMEM;
341
342	memset(out, 0, sizeof(*out));
343	memset(token, 0, YUBIKEY_TOKEN_SIZE + 1);
344
345	lc_ctype = getenv("LC_CTYPE");
346	setlocale(LC_CTYPE, lc_ctype ? lc_ctype : "C.UTF-8");
347	len = mbstowcs(wpassword, password, len);
348	if (len < 0) {
349		return errno;
350	}
351	setlocale(LC_CTYPE, "C");
352
353	if (len > YUBIKEY_TOKEN_SIZE)
354		pp = pp + len - YUBIKEY_TOKEN_SIZE;
355	if (len < YUBIKEY_TOKEN_SIZE)
356		return EMSGSIZE;
357
358	if (yubikey_keymap_decode(pp, token, index))
359		return EINVAL;
360	yubikey_modhex_decode((void *)out, token, sizeof(*out));
361	yubikey_aes_decrypt((void *)out, key);
362	return 0;
363}
364