2
* SHA1 hash implementation and interface functions
3
* Copyright (c) 2003-2005, Jouni Malinen <jkmaline@cc.hut.fi>
5
* This program is free software; you can redistribute it and/or modify
6
* it under the terms of the GNU General Public License version 2 as
7
* published by the Free Software Foundation.
9
* Alternatively, this software may be distributed under the terms of BSD
12
* See README and COPYING for more details.
20
#include "config-knmstorage.h"
22
/* Define types for stupid code. Userspace should
23
* be using u_*_t rather than kernel-space u* types.
26
typedef u_int16_t u16;
27
typedef u_int32_t u32;
28
typedef u_int64_t u64;
30
void sha1_vector(size_t num_elem, const u8 *addr[], const size_t *len, u8 *mac);
31
void sha1_transform(u8 *state, const u8 data[64]);
33
void sha1_mac(const u8 *key, size_t key_len, const u8 *data, size_t data_len,
44
sha1_vector(3, addr, len, mac);
48
/* HMAC code is based on RFC 2104 */
49
void hmac_sha1_vector(const u8 *key, size_t key_len, size_t num_elem,
50
const u8 *addr[], const size_t *len, u8 *mac)
52
unsigned char k_pad[64]; /* padding - key XORd with ipad/opad */
59
* Fixed limit on the number of fragments to avoid having to
60
* allocate memory (which could fail).
65
/* if key is longer than 64 bytes reset it to key = SHA1(key) */
67
sha1_vector(1, &key, &key_len, tk);
72
/* the HMAC_SHA1 transform looks like:
74
* SHA1(K XOR opad, SHA1(K XOR ipad, text))
76
* where K is an n byte key
77
* ipad is the byte 0x36 repeated 64 times
78
* opad is the byte 0x5c repeated 64 times
79
* and text is the data being protected */
81
/* start out by storing key in ipad */
82
memset(k_pad, 0, sizeof(k_pad));
83
memcpy(k_pad, key, key_len);
84
/* XOR key with ipad values */
85
for (i = 0; i < 64; i++)
88
/* perform inner SHA1 */
91
for (i = 0; i < num_elem; i++) {
92
_addr[i + 1] = addr[i];
95
sha1_vector(1 + num_elem, _addr, _len, mac);
97
memset(k_pad, 0, sizeof(k_pad));
98
memcpy(k_pad, key, key_len);
99
/* XOR key with opad values */
100
for (i = 0; i < 64; i++)
103
/* perform outer SHA1 */
107
_len[1] = SHA1_MAC_LEN;
108
sha1_vector(2, _addr, _len, mac);
112
void hmac_sha1(const u8 *key, size_t key_len, const u8 *data, size_t data_len,
115
hmac_sha1_vector(key, key_len, 1, &data, &data_len, mac);
119
void sha1_prf(const u8 *key, size_t key_len, const char *label,
120
const u8 *data, size_t data_len, u8 *buf, size_t buf_len)
122
u8 zero = 0, counter = 0;
124
u8 hash[SHA1_MAC_LEN];
125
size_t label_len = strlen(label);
126
const unsigned char *addr[4];
129
addr[0] = (u8 *) label;
139
while (pos < buf_len) {
140
plen = buf_len - pos;
141
if (plen >= SHA1_MAC_LEN) {
142
hmac_sha1_vector(key, key_len, 4, addr, len,
146
hmac_sha1_vector(key, key_len, 4, addr, len,
148
memcpy(&buf[pos], hash, plen);
156
static void pbkdf2_sha1_f(const char *passphrase, const char *ssid,
157
size_t ssid_len, int iterations, int count,
160
unsigned char tmp[SHA1_MAC_LEN], tmp2[SHA1_MAC_LEN];
162
unsigned char count_buf[4];
165
size_t passphrase_len = strlen(passphrase);
167
addr[0] = (u8 *) ssid;
172
/* F(P, S, c, i) = U1 xor U2 xor ... Uc
173
* U1 = PRF(P, S || i)
178
count_buf[0] = (count >> 24) & 0xff;
179
count_buf[1] = (count >> 16) & 0xff;
180
count_buf[2] = (count >> 8) & 0xff;
181
count_buf[3] = count & 0xff;
182
hmac_sha1_vector((u8 *) passphrase, passphrase_len, 2, addr, len, tmp);
183
memcpy(digest, tmp, SHA1_MAC_LEN);
185
for (i = 1; i < iterations; i++) {
186
hmac_sha1((u8 *) passphrase, passphrase_len, tmp, SHA1_MAC_LEN,
188
memcpy(tmp, tmp2, SHA1_MAC_LEN);
189
for (j = 0; j < SHA1_MAC_LEN; j++)
190
digest[j] ^= tmp2[j];
195
void pbkdf2_sha1(const char *passphrase, const char *ssid, size_t ssid_len,
196
int iterations, u8 *buf, size_t buflen)
199
unsigned char *pos = buf;
200
size_t left = buflen;
202
unsigned char digest[SHA1_MAC_LEN];
206
pbkdf2_sha1_f(passphrase, ssid, ssid_len, iterations, count,
208
plen = left > SHA1_MAC_LEN ? SHA1_MAC_LEN : left;
209
memcpy(pos, digest, plen);
216
#ifndef EAP_TLS_FUNCS
221
unsigned char buffer[64];
224
static void SHA1Init(SHA1_CTX *context);
225
static void SHA1Update(SHA1_CTX *context, const void *data, u32 len);
226
static void SHA1Final(unsigned char digest[20], SHA1_CTX* context);
227
static void SHA1Transform(u32 state[5], const unsigned char buffer[64]);
231
* sha1_vector - SHA-1 hash for data vector
232
* @num_elem: Number of elements in the data vector
233
* @addr: Pointers to the data areas
234
* @len: Lengths of the data blocks
235
* @mac: Buffer for the hash
237
void sha1_vector(size_t num_elem, const u8 *addr[], const size_t *len,
244
for (i = 0; i < num_elem; i++)
245
SHA1Update(&ctx, addr[i], len[i]);
246
SHA1Final(mac, &ctx);
251
* sha1_transform - Perform one SHA-1 transform step
252
* @state: SHA-1 state
253
* @data: Input data for the SHA-1 transform
255
* This function is used to implement random number generation specified in
256
* NIST FIPS Publication 186-2 for EAP-SIM. This PRF uses a function that is
257
* similar to SHA-1, but has different message padding and as such, access to
258
* just part of the SHA-1 is needed.
260
void sha1_transform(u8 *state, const u8 data[64])
262
SHA1Transform((u32 *) state, data);
266
/* ===== start - public domain SHA1 implementation ===== */
270
By Steve Reid <sreid@sea-to-sky.net>
275
By James H. Brown <jbrown@burgoyne.com>
276
Still 100% Public Domain
278
Corrected a problem which generated improper hash values on 16 bit machines
279
Routine SHA1Update changed from
280
void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned int
283
void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned
286
The 'len' parameter was declared an int which works fine on 32 bit machines.
287
However, on 16 bit machines an int is too small for the shifts being done
289
it. This caused the hash function to generate incorrect values if len was
290
greater than 8191 (8K - 1) due to the 'len << 3' on line 3 of SHA1Update().
292
Since the file IO in main() reads 16K at a time, any file 8K or larger would
293
be guaranteed to generate the wrong hash (e.g. Test Vector #3, a million
296
I also changed the declaration of variables i & j in SHA1Update to
297
unsigned long from unsigned int for the same reason.
299
These changes should make no difference to any 32 bit implementations since
301
int and a long are the same size in those environments.
304
I also corrected a few compiler warnings generated by Borland C.
305
1. Added #include <process.h> for exit() prototype
306
2. Removed unused variable 'j' in SHA1Final
307
3. Changed exit(0) to return(0) at end of main.
309
ALL changes I made can be located by searching for comments containing 'JHB'
312
By Steve Reid <sreid@sea-to-sky.net>
313
Still 100% public domain
315
1- Removed #include <process.h> and used return() instead of exit()
316
2- Fixed overwriting of finalcount in SHA1Final() (discovered by Chris Hall)
317
3- Changed email address from steve@edmweb.com to sreid@sea-to-sky.net
321
By Saul Kravitz <Saul.Kravitz@celera.com>
323
Modified to run on Compaq Alpha hardware.
327
By Jouni Malinen <jkmaline@cc.hut.fi>
328
Minor changes to match the coding style used in Dynamics.
330
Modified September 24, 2004
331
By Jouni Malinen <jkmaline@cc.hut.fi>
332
Fixed alignment issue in SHA1Transform when SHA1HANDSOFF is defined.
337
Test Vectors (from FIPS PUB 180-1)
339
A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D
340
"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
341
84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1
342
A million repetitions of "a"
343
34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F
348
#define rol(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits))))
350
/* blk0() and blk() perform the initial expand. */
351
/* I got the idea of expanding during the round function from SSLeay */
352
#ifndef WORDS_BIGENDIAN
353
#define blk0(i) (block->l[i] = (rol(block->l[i], 24) & 0xFF00FF00) | \
354
(rol(block->l[i], 8) & 0x00FF00FF))
356
#define blk0(i) block->l[i]
358
#define blk(i) (block->l[i & 15] = rol(block->l[(i + 13) & 15] ^ \
359
block->l[(i + 8) & 15] ^ block->l[(i + 2) & 15] ^ block->l[i & 15], 1))
361
/* (R0+R1), R2, R3, R4 are the different operations used in SHA1 */
362
#define R0(v,w,x,y,z,i) \
363
z += ((w & (x ^ y)) ^ y) + blk0(i) + 0x5A827999 + rol(v, 5); \
365
#define R1(v,w,x,y,z,i) \
366
z += ((w & (x ^ y)) ^ y) + blk(i) + 0x5A827999 + rol(v, 5); \
368
#define R2(v,w,x,y,z,i) \
369
z += (w ^ x ^ y) + blk(i) + 0x6ED9EBA1 + rol(v, 5); w = rol(w, 30);
370
#define R3(v,w,x,y,z,i) \
371
z += (((w | x) & y) | (w & x)) + blk(i) + 0x8F1BBCDC + rol(v, 5); \
373
#define R4(v,w,x,y,z,i) \
374
z += (w ^ x ^ y) + blk(i) + 0xCA62C1D6 + rol(v, 5); \
378
#ifdef VERBOSE /* SAK */
379
void SHAPrintContext(SHA1_CTX *context, char *msg)
381
printf("%s (%d,%d) %x %x %x %x %x\n",
383
context->count[0], context->count[1],
392
/* Hash a single 512-bit block. This is the core of the algorithm. */
394
void SHA1Transform(u32 state[5], const unsigned char buffer[64])
404
block = (CHAR64LONG16 *) workspace;
405
memcpy(block, buffer, 64);
407
block = (CHAR64LONG16 *) buffer;
409
/* Copy context->state[] to working vars */
415
/* 4 rounds of 20 operations each. Loop unrolled. */
416
R0(a,b,c,d,e, 0); R0(e,a,b,c,d, 1); R0(d,e,a,b,c, 2); R0(c,d,e,a,b, 3);
417
R0(b,c,d,e,a, 4); R0(a,b,c,d,e, 5); R0(e,a,b,c,d, 6); R0(d,e,a,b,c, 7);
418
R0(c,d,e,a,b, 8); R0(b,c,d,e,a, 9); R0(a,b,c,d,e,10); R0(e,a,b,c,d,11);
419
R0(d,e,a,b,c,12); R0(c,d,e,a,b,13); R0(b,c,d,e,a,14); R0(a,b,c,d,e,15);
420
R1(e,a,b,c,d,16); R1(d,e,a,b,c,17); R1(c,d,e,a,b,18); R1(b,c,d,e,a,19);
421
R2(a,b,c,d,e,20); R2(e,a,b,c,d,21); R2(d,e,a,b,c,22); R2(c,d,e,a,b,23);
422
R2(b,c,d,e,a,24); R2(a,b,c,d,e,25); R2(e,a,b,c,d,26); R2(d,e,a,b,c,27);
423
R2(c,d,e,a,b,28); R2(b,c,d,e,a,29); R2(a,b,c,d,e,30); R2(e,a,b,c,d,31);
424
R2(d,e,a,b,c,32); R2(c,d,e,a,b,33); R2(b,c,d,e,a,34); R2(a,b,c,d,e,35);
425
R2(e,a,b,c,d,36); R2(d,e,a,b,c,37); R2(c,d,e,a,b,38); R2(b,c,d,e,a,39);
426
R3(a,b,c,d,e,40); R3(e,a,b,c,d,41); R3(d,e,a,b,c,42); R3(c,d,e,a,b,43);
427
R3(b,c,d,e,a,44); R3(a,b,c,d,e,45); R3(e,a,b,c,d,46); R3(d,e,a,b,c,47);
428
R3(c,d,e,a,b,48); R3(b,c,d,e,a,49); R3(a,b,c,d,e,50); R3(e,a,b,c,d,51);
429
R3(d,e,a,b,c,52); R3(c,d,e,a,b,53); R3(b,c,d,e,a,54); R3(a,b,c,d,e,55);
430
R3(e,a,b,c,d,56); R3(d,e,a,b,c,57); R3(c,d,e,a,b,58); R3(b,c,d,e,a,59);
431
R4(a,b,c,d,e,60); R4(e,a,b,c,d,61); R4(d,e,a,b,c,62); R4(c,d,e,a,b,63);
432
R4(b,c,d,e,a,64); R4(a,b,c,d,e,65); R4(e,a,b,c,d,66); R4(d,e,a,b,c,67);
433
R4(c,d,e,a,b,68); R4(b,c,d,e,a,69); R4(a,b,c,d,e,70); R4(e,a,b,c,d,71);
434
R4(d,e,a,b,c,72); R4(c,d,e,a,b,73); R4(b,c,d,e,a,74); R4(a,b,c,d,e,75);
435
R4(e,a,b,c,d,76); R4(d,e,a,b,c,77); R4(c,d,e,a,b,78); R4(b,c,d,e,a,79);
436
/* Add the working vars back into context.state[] */
443
a = b = c = d = e = 0;
445
memset(block, 0, 64);
450
/* SHA1Init - Initialize new context */
452
static void SHA1Init(SHA1_CTX* context)
454
/* SHA1 initialization constants */
455
context->state[0] = 0x67452301;
456
context->state[1] = 0xEFCDAB89;
457
context->state[2] = 0x98BADCFE;
458
context->state[3] = 0x10325476;
459
context->state[4] = 0xC3D2E1F0;
460
context->count[0] = context->count[1] = 0;
464
/* Run your data through this. */
466
static void SHA1Update(SHA1_CTX* context, const void *_data, u32 len)
469
const unsigned char *data = (const unsigned char*) _data;
472
SHAPrintContext(context, "before");
474
j = (context->count[0] >> 3) & 63;
475
if ((context->count[0] += len << 3) < (len << 3))
477
context->count[1] += (len >> 29);
478
if ((j + len) > 63) {
479
memcpy(&context->buffer[j], data, (i = 64-j));
480
SHA1Transform(context->state, context->buffer);
481
for ( ; i + 63 < len; i += 64) {
482
SHA1Transform(context->state, &data[i]);
487
memcpy(&context->buffer[j], &data[i], len - i);
489
SHAPrintContext(context, "after ");
494
/* Add padding and return the message digest. */
496
static void SHA1Final(unsigned char digest[20], SHA1_CTX* context)
499
unsigned char finalcount[8];
501
for (i = 0; i < 8; i++) {
502
finalcount[i] = (unsigned char)
503
((context->count[(i >= 4 ? 0 : 1)] >>
504
((3-(i & 3)) * 8) ) & 255); /* Endian independent */
506
SHA1Update(context, (unsigned char *) "\200", 1);
507
while ((context->count[0] & 504) != 448) {
508
SHA1Update(context, (unsigned char *) "\0", 1);
510
SHA1Update(context, finalcount, 8); /* Should cause a SHA1Transform()
512
for (i = 0; i < 20; i++) {
513
digest[i] = (unsigned char)
514
((context->state[i >> 2] >> ((3 - (i & 3)) * 8)) &
519
memset(context->buffer, 0, 64);
520
memset(context->state, 0, 20);
521
memset(context->count, 0, 8);
522
memset(finalcount, 0, 8);
525
/* ===== end - public domain SHA1 implementation ===== */
527
#endif /* EAP_TLS_FUNCS */
534
0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b,
535
0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b,
536
0x0b, 0x0b, 0x0b, 0x0b
538
static u8 data0[] = "Hi There";
541
0xbc, 0xd4, 0xc6, 0x50, 0xb3, 0x0b, 0x96, 0x84,
542
0x95, 0x18, 0x29, 0xe0, 0xd7, 0x5f, 0x9d, 0x54,
543
0xb8, 0x62, 0x17, 0x5e, 0xd9, 0xf0, 0x06, 0x06,
544
0xe1, 0x7d, 0x8d, 0xa3, 0x54, 0x02, 0xff, 0xee,
545
0x75, 0xdf, 0x78, 0xc3, 0xd3, 0x1e, 0x0f, 0x88,
546
0x9f, 0x01, 0x21, 0x20, 0xc0, 0x86, 0x2b, 0xeb,
547
0x67, 0x75, 0x3e, 0x74, 0x39, 0xae, 0x24, 0x2e,
548
0xdb, 0x83, 0x73, 0x69, 0x83, 0x56, 0xcf, 0x5a
551
static u8 key1[] = "Jefe";
552
static u8 data1[] = "what do ya want for nothing?";
555
0x51, 0xf4, 0xde, 0x5b, 0x33, 0xf2, 0x49, 0xad,
556
0xf8, 0x1a, 0xeb, 0x71, 0x3a, 0x3c, 0x20, 0xf4,
557
0xfe, 0x63, 0x14, 0x46, 0xfa, 0xbd, 0xfa, 0x58,
558
0x24, 0x47, 0x59, 0xae, 0x58, 0xef, 0x90, 0x09,
559
0xa9, 0x9a, 0xbf, 0x4e, 0xac, 0x2c, 0xa5, 0xfa,
560
0x87, 0xe6, 0x92, 0xc4, 0x40, 0xeb, 0x40, 0x02,
561
0x3e, 0x7b, 0xab, 0xb2, 0x06, 0xd6, 0x1d, 0xe7,
562
0xb9, 0x2f, 0x41, 0x52, 0x90, 0x92, 0xb8, 0xfc
568
0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa,
569
0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa,
570
0xaa, 0xaa, 0xaa, 0xaa
574
0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd,
575
0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd,
576
0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd,
577
0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd,
578
0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd,
579
0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd, 0xdd,
584
0xe1, 0xac, 0x54, 0x6e, 0xc4, 0xcb, 0x63, 0x6f,
585
0x99, 0x76, 0x48, 0x7b, 0xe5, 0xc8, 0x6b, 0xe1,
586
0x7a, 0x02, 0x52, 0xca, 0x5d, 0x8d, 0x8d, 0xf1,
587
0x2c, 0xfb, 0x04, 0x73, 0x52, 0x52, 0x49, 0xce,
588
0x9d, 0xd8, 0xd1, 0x77, 0xea, 0xd7, 0x10, 0xbc,
589
0x9b, 0x59, 0x05, 0x47, 0x23, 0x91, 0x07, 0xae,
590
0xf7, 0xb4, 0xab, 0xd4, 0x3d, 0x87, 0xf0, 0xa6,
591
0x8f, 0x1c, 0xbd, 0x9e, 0x2b, 0x6f, 0x76, 0x07
595
struct passphrase_test {
601
static struct passphrase_test passphrase_tests[] =
607
0xf4, 0x2c, 0x6f, 0xc5, 0x2d, 0xf0, 0xeb, 0xef,
608
0x9e, 0xbb, 0x4b, 0x90, 0xb3, 0x8a, 0x5f, 0x90,
609
0x2e, 0x83, 0xfe, 0x1b, 0x13, 0x5a, 0x70, 0xe2,
610
0x3a, 0xed, 0x76, 0x2e, 0x97, 0x10, 0xa1, 0x2e
617
0x0d, 0xc0, 0xd6, 0xeb, 0x90, 0x55, 0x5e, 0xd6,
618
0x41, 0x97, 0x56, 0xb9, 0xa1, 0x5e, 0xc3, 0xe3,
619
0x20, 0x9b, 0x63, 0xdf, 0x70, 0x7d, 0xd5, 0x08,
620
0xd1, 0x45, 0x81, 0xf8, 0x98, 0x27, 0x21, 0xaf
624
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
625
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
627
0xbe, 0xcb, 0x93, 0x86, 0x6b, 0xb8, 0xc3, 0x83,
628
0x2c, 0xb7, 0x77, 0xc2, 0xf5, 0x59, 0x80, 0x7c,
629
0x8c, 0x59, 0xaf, 0xcb, 0x6e, 0xae, 0x73, 0x48,
630
0x85, 0x00, 0x13, 0x00, 0xa9, 0x81, 0xcc, 0x62
635
#define NUM_PASSPHRASE_TESTS \
636
(sizeof(passphrase_tests) / sizeof(passphrase_tests[0]))
639
int main(int argc, char *argv[])
644
printf("PRF-SHA1 test cases:\n");
646
sha1_prf(key0, sizeof(key0), "prefix", data0, sizeof(data0) - 1,
648
if (memcmp(res, prf0, sizeof(prf0)) == 0)
649
printf("Test case 0 - OK\n");
651
printf("Test case 0 - FAILED!\n");
655
sha1_prf(key1, sizeof(key1) - 1, "prefix", data1, sizeof(data1) - 1,
657
if (memcmp(res, prf1, sizeof(prf1)) == 0)
658
printf("Test case 1 - OK\n");
660
printf("Test case 1 - FAILED!\n");
664
sha1_prf(key2, sizeof(key2), "prefix", data2, sizeof(data2),
666
if (memcmp(res, prf2, sizeof(prf2)) == 0)
667
printf("Test case 2 - OK\n");
669
printf("Test case 2 - FAILED!\n");
673
ret += test_eap_fast();
675
printf("PBKDF2-SHA1 Passphrase test cases:\n");
676
for (i = 0; i < NUM_PASSPHRASE_TESTS; i++) {
678
struct passphrase_test *test = &passphrase_tests[i];
679
pbkdf2_sha1(test->passphrase,
680
test->ssid, strlen(test->ssid),
682
if (memcmp(psk, test->psk, 32) == 0)
683
printf("Test case %d - OK\n", i);
685
printf("Test case %d - FAILED!\n", i);
692
#endif /* TEST_MAIN */