Adding chunk_mac() which calculates a 64-bit MAC using SipHash-2-4
[strongswan.git] / src / libstrongswan / utils / chunk.c
1 /*
2 * Copyright (C) 2008-2013 Tobias Brunner
3 * Copyright (C) 2005-2006 Martin Willi
4 * Copyright (C) 2005 Jan Hutter
5 * Hochschule fuer Technik Rapperswil
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; either version 2 of the License, or (at your
10 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
11 *
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * for more details.
16 */
17
18 #include <stdio.h>
19 #include <sys/stat.h>
20 #include <unistd.h>
21 #include <errno.h>
22 #include <ctype.h>
23
24 #include "chunk.h"
25 #include "debug.h"
26
27 /* required for chunk_hash */
28 #undef get16bits
29 #if (defined(__GNUC__) && defined(__i386__))
30 #define get16bits(d) (*((const u_int16_t*)(d)))
31 #endif
32 #if !defined (get16bits)
33 #define get16bits(d) ((((u_int32_t)(((const u_int8_t*)(d))[1])) << 8)\
34 + (u_int32_t)(((const u_int8_t*)(d))[0]) )
35 #endif
36
37 /**
38 * Empty chunk.
39 */
40 chunk_t chunk_empty = { NULL, 0 };
41
42 /**
43 * Described in header.
44 */
45 chunk_t chunk_create_clone(u_char *ptr, chunk_t chunk)
46 {
47 chunk_t clone = chunk_empty;
48
49 if (chunk.ptr && chunk.len > 0)
50 {
51 clone.ptr = ptr;
52 clone.len = chunk.len;
53 memcpy(clone.ptr, chunk.ptr, chunk.len);
54 }
55
56 return clone;
57 }
58
59 /**
60 * Described in header.
61 */
62 size_t chunk_length(const char* mode, ...)
63 {
64 va_list chunks;
65 size_t length = 0;
66
67 va_start(chunks, mode);
68 while (TRUE)
69 {
70 switch (*mode++)
71 {
72 case 'm':
73 case 'c':
74 case 's':
75 {
76 chunk_t ch = va_arg(chunks, chunk_t);
77 length += ch.len;
78 continue;
79 }
80 default:
81 break;
82 }
83 break;
84 }
85 va_end(chunks);
86 return length;
87 }
88
89 /**
90 * Described in header.
91 */
92 chunk_t chunk_create_cat(u_char *ptr, const char* mode, ...)
93 {
94 va_list chunks;
95 chunk_t construct = chunk_create(ptr, 0);
96
97 va_start(chunks, mode);
98 while (TRUE)
99 {
100 bool free_chunk = FALSE, clear_chunk = FALSE;
101 chunk_t ch;
102
103 switch (*mode++)
104 {
105 case 's':
106 clear_chunk = TRUE;
107 /* FALL */
108 case 'm':
109 free_chunk = TRUE;
110 /* FALL */
111 case 'c':
112 ch = va_arg(chunks, chunk_t);
113 memcpy(ptr, ch.ptr, ch.len);
114 ptr += ch.len;
115 construct.len += ch.len;
116 if (clear_chunk)
117 {
118 chunk_clear(&ch);
119 }
120 else if (free_chunk)
121 {
122 free(ch.ptr);
123 }
124 continue;
125 default:
126 break;
127 }
128 break;
129 }
130 va_end(chunks);
131
132 return construct;
133 }
134
135 /**
136 * Described in header.
137 */
138 void chunk_split(chunk_t chunk, const char *mode, ...)
139 {
140 va_list chunks;
141 u_int len;
142 chunk_t *ch;
143
144 va_start(chunks, mode);
145 while (TRUE)
146 {
147 if (*mode == '\0')
148 {
149 break;
150 }
151 len = va_arg(chunks, u_int);
152 ch = va_arg(chunks, chunk_t*);
153 /* a null chunk means skip len bytes */
154 if (ch == NULL)
155 {
156 chunk = chunk_skip(chunk, len);
157 continue;
158 }
159 switch (*mode++)
160 {
161 case 'm':
162 {
163 ch->len = min(chunk.len, len);
164 if (ch->len)
165 {
166 ch->ptr = chunk.ptr;
167 }
168 else
169 {
170 ch->ptr = NULL;
171 }
172 chunk = chunk_skip(chunk, ch->len);
173 continue;
174 }
175 case 'a':
176 {
177 ch->len = min(chunk.len, len);
178 if (ch->len)
179 {
180 ch->ptr = malloc(ch->len);
181 memcpy(ch->ptr, chunk.ptr, ch->len);
182 }
183 else
184 {
185 ch->ptr = NULL;
186 }
187 chunk = chunk_skip(chunk, ch->len);
188 continue;
189 }
190 case 'c':
191 {
192 ch->len = min(ch->len, chunk.len);
193 ch->len = min(ch->len, len);
194 if (ch->len)
195 {
196 memcpy(ch->ptr, chunk.ptr, ch->len);
197 }
198 else
199 {
200 ch->ptr = NULL;
201 }
202 chunk = chunk_skip(chunk, ch->len);
203 continue;
204 }
205 default:
206 break;
207 }
208 break;
209 }
210 va_end(chunks);
211 }
212
213 /**
214 * Described in header.
215 */
216 bool chunk_write(chunk_t chunk, char *path, char *label, mode_t mask, bool force)
217 {
218 mode_t oldmask;
219 FILE *fd;
220 bool good = FALSE;
221
222 if (!force && access(path, F_OK) == 0)
223 {
224 DBG1(DBG_LIB, " %s file '%s' already exists", label, path);
225 return FALSE;
226 }
227 oldmask = umask(mask);
228 fd = fopen(path, "w");
229 if (fd)
230 {
231 if (fwrite(chunk.ptr, sizeof(u_char), chunk.len, fd) == chunk.len)
232 {
233 DBG1(DBG_LIB, " written %s file '%s' (%d bytes)",
234 label, path, chunk.len);
235 good = TRUE;
236 }
237 else
238 {
239 DBG1(DBG_LIB, " writing %s file '%s' failed: %s",
240 label, path, strerror(errno));
241 }
242 fclose(fd);
243 }
244 else
245 {
246 DBG1(DBG_LIB, " could not open %s file '%s': %s", label, path,
247 strerror(errno));
248 }
249 umask(oldmask);
250 return good;
251 }
252
253
254 /** hex conversion digits */
255 static char hexdig_upper[] = "0123456789ABCDEF";
256 static char hexdig_lower[] = "0123456789abcdef";
257
258 /**
259 * Described in header.
260 */
261 chunk_t chunk_to_hex(chunk_t chunk, char *buf, bool uppercase)
262 {
263 int i, len;
264 char *hexdig = hexdig_lower;
265
266 if (uppercase)
267 {
268 hexdig = hexdig_upper;
269 }
270
271 len = chunk.len * 2;
272 if (!buf)
273 {
274 buf = malloc(len + 1);
275 }
276 buf[len] = '\0';
277
278 for (i = 0; i < chunk.len; i++)
279 {
280 buf[i*2] = hexdig[(chunk.ptr[i] >> 4) & 0xF];
281 buf[i*2+1] = hexdig[(chunk.ptr[i] ) & 0xF];
282 }
283 return chunk_create(buf, len);
284 }
285
286 /**
287 * convert a signle hex character to its binary value
288 */
289 static char hex2bin(char hex)
290 {
291 switch (hex)
292 {
293 case '0' ... '9':
294 return hex - '0';
295 case 'A' ... 'F':
296 return hex - 'A' + 10;
297 case 'a' ... 'f':
298 return hex - 'a' + 10;
299 default:
300 return 0;
301 }
302 }
303
304 /**
305 * Described in header.
306 */
307 chunk_t chunk_from_hex(chunk_t hex, char *buf)
308 {
309 int i, len;
310 u_char *ptr;
311 bool odd = FALSE;
312
313 /* subtract the number of optional ':' separation characters */
314 len = hex.len;
315 ptr = hex.ptr;
316 for (i = 0; i < hex.len; i++)
317 {
318 if (*ptr++ == ':')
319 {
320 len--;
321 }
322 }
323
324 /* compute the number of binary bytes */
325 if (len % 2)
326 {
327 odd = TRUE;
328 len++;
329 }
330 len /= 2;
331
332 /* allocate buffer memory unless provided by caller */
333 if (!buf)
334 {
335 buf = malloc(len);
336 }
337
338 /* buffer is filled from the right */
339 memset(buf, 0, len);
340 hex.ptr += hex.len;
341
342 for (i = len - 1; i >= 0; i--)
343 {
344 /* skip separation characters */
345 if (*(--hex.ptr) == ':')
346 {
347 --hex.ptr;
348 }
349 buf[i] = hex2bin(*hex.ptr);
350 if (i > 0 || !odd)
351 {
352 buf[i] |= hex2bin(*(--hex.ptr)) << 4;
353 }
354 }
355 return chunk_create(buf, len);
356 }
357
358 /** base 64 conversion digits */
359 static char b64digits[] =
360 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
361
362 /**
363 * Described in header.
364 */
365 chunk_t chunk_to_base64(chunk_t chunk, char *buf)
366 {
367 int i, len;
368 char *pos;
369
370 len = chunk.len + ((3 - chunk.len % 3) % 3);
371 if (!buf)
372 {
373 buf = malloc(len * 4 / 3 + 1);
374 }
375 pos = buf;
376 for (i = 0; i < len; i+=3)
377 {
378 *pos++ = b64digits[chunk.ptr[i] >> 2];
379 if (i+1 >= chunk.len)
380 {
381 *pos++ = b64digits[(chunk.ptr[i] & 0x03) << 4];
382 *pos++ = '=';
383 *pos++ = '=';
384 break;
385 }
386 *pos++ = b64digits[((chunk.ptr[i] & 0x03) << 4) | (chunk.ptr[i+1] >> 4)];
387 if (i+2 >= chunk.len)
388 {
389 *pos++ = b64digits[(chunk.ptr[i+1] & 0x0F) << 2];
390 *pos++ = '=';
391 break;
392 }
393 *pos++ = b64digits[((chunk.ptr[i+1] & 0x0F) << 2) | (chunk.ptr[i+2] >> 6)];
394 *pos++ = b64digits[chunk.ptr[i+2] & 0x3F];
395 }
396 *pos = '\0';
397 return chunk_create(buf, len * 4 / 3);
398 }
399
400 /**
401 * convert a base 64 digit to its binary form (inversion of b64digits array)
402 */
403 static int b642bin(char b64)
404 {
405 switch (b64)
406 {
407 case 'A' ... 'Z':
408 return b64 - 'A';
409 case 'a' ... 'z':
410 return ('Z' - 'A' + 1) + b64 - 'a';
411 case '0' ... '9':
412 return ('Z' - 'A' + 1) + ('z' - 'a' + 1) + b64 - '0';
413 case '+':
414 case '-':
415 return 62;
416 case '/':
417 case '_':
418 return 63;
419 case '=':
420 return 0;
421 default:
422 return -1;
423 }
424 }
425
426 /**
427 * Described in header.
428 */
429 chunk_t chunk_from_base64(chunk_t base64, char *buf)
430 {
431 u_char *pos, byte[4];
432 int i, j, len, outlen;
433
434 len = base64.len / 4 * 3;
435 if (!buf)
436 {
437 buf = malloc(len);
438 }
439 pos = base64.ptr;
440 outlen = 0;
441 for (i = 0; i < len; i+=3)
442 {
443 outlen += 3;
444 for (j = 0; j < 4; j++)
445 {
446 if (*pos == '=')
447 {
448 outlen--;
449 }
450 byte[j] = b642bin(*pos++);
451 }
452 buf[i] = (byte[0] << 2) | (byte[1] >> 4);
453 buf[i+1] = (byte[1] << 4) | (byte[2] >> 2);
454 buf[i+2] = (byte[2] << 6) | (byte[3]);
455 }
456 return chunk_create(buf, outlen);
457 }
458
459 /** base 32 conversion digits */
460 static char b32digits[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
461
462 /**
463 * Described in header.
464 */
465 chunk_t chunk_to_base32(chunk_t chunk, char *buf)
466 {
467 int i, len;
468 char *pos;
469
470 len = chunk.len + ((5 - chunk.len % 5) % 5);
471 if (!buf)
472 {
473 buf = malloc(len * 8 / 5 + 1);
474 }
475 pos = buf;
476 for (i = 0; i < len; i+=5)
477 {
478 *pos++ = b32digits[chunk.ptr[i] >> 3];
479 if (i+1 >= chunk.len)
480 {
481 *pos++ = b32digits[(chunk.ptr[i] & 0x07) << 2];
482 memset(pos, '=', 6);
483 pos += 6;
484 break;
485 }
486 *pos++ = b32digits[((chunk.ptr[i] & 0x07) << 2) |
487 (chunk.ptr[i+1] >> 6)];
488 *pos++ = b32digits[(chunk.ptr[i+1] & 0x3E) >> 1];
489 if (i+2 >= chunk.len)
490 {
491 *pos++ = b32digits[(chunk.ptr[i+1] & 0x01) << 4];
492 memset(pos, '=', 4);
493 pos += 4;
494 break;
495 }
496 *pos++ = b32digits[((chunk.ptr[i+1] & 0x01) << 4) |
497 (chunk.ptr[i+2] >> 4)];
498 if (i+3 >= chunk.len)
499 {
500 *pos++ = b32digits[(chunk.ptr[i+2] & 0x0F) << 1];
501 memset(pos, '=', 3);
502 pos += 3;
503 break;
504 }
505 *pos++ = b32digits[((chunk.ptr[i+2] & 0x0F) << 1) |
506 (chunk.ptr[i+3] >> 7)];
507 *pos++ = b32digits[(chunk.ptr[i+3] & 0x7F) >> 2];
508 if (i+4 >= chunk.len)
509 {
510 *pos++ = b32digits[(chunk.ptr[i+3] & 0x03) << 3];
511 *pos++ = '=';
512 break;
513 }
514 *pos++ = b32digits[((chunk.ptr[i+3] & 0x03) << 3) |
515 (chunk.ptr[i+4] >> 5)];
516 *pos++ = b32digits[chunk.ptr[i+4] & 0x1F];
517 }
518 *pos = '\0';
519 return chunk_create(buf, len * 8 / 5);
520 }
521
522 /**
523 * Described in header.
524 */
525 int chunk_compare(chunk_t a, chunk_t b)
526 {
527 int compare_len = a.len - b.len;
528 int len = (compare_len < 0)? a.len : b.len;
529
530 if (compare_len != 0 || len == 0)
531 {
532 return compare_len;
533 }
534 return memcmp(a.ptr, b.ptr, len);
535 };
536
537
538 /**
539 * Described in header.
540 */
541 bool chunk_increment(chunk_t chunk)
542 {
543 int i;
544
545 for (i = chunk.len - 1; i >= 0; i--)
546 {
547 if (++chunk.ptr[i] != 0)
548 {
549 return FALSE;
550 }
551 }
552 return TRUE;
553 }
554
555 /**
556 * Remove non-printable characters from a chunk.
557 */
558 bool chunk_printable(chunk_t chunk, chunk_t *sane, char replace)
559 {
560 bool printable = TRUE;
561 int i;
562
563 if (sane)
564 {
565 *sane = chunk_clone(chunk);
566 }
567 for (i = 0; i < chunk.len; i++)
568 {
569 if (!isprint(chunk.ptr[i]))
570 {
571 if (sane)
572 {
573 sane->ptr[i] = replace;
574 }
575 printable = FALSE;
576 }
577 }
578 return printable;
579 }
580
581 /**
582 * Helper functions for chunk_mac()
583 */
584 static inline u_int64_t sipget(u_char *in)
585 {
586 u_int64_t v = 0;
587 int i;
588
589 for (i = 0; i < 64; i += 8, ++in)
590 {
591 v |= ((u_int64_t)*in) << i;
592 }
593 return v;
594 }
595
596 static inline u_int64_t siprotate(u_int64_t v, int shift)
597 {
598 return (v << shift) | (v >> (64 - shift));
599 }
600
601 static inline void sipround(u_int64_t *v0, u_int64_t *v1, u_int64_t *v2,
602 u_int64_t *v3)
603 {
604 *v0 += *v1;
605 *v1 = siprotate(*v1, 13);
606 *v1 ^= *v0;
607 *v0 = siprotate(*v0, 32);
608
609 *v2 += *v3;
610 *v3 = siprotate(*v3, 16);
611 *v3 ^= *v2;
612
613 *v2 += *v1;
614 *v1 = siprotate(*v1, 17);
615 *v1 ^= *v2;
616 *v2 = siprotate(*v2, 32);
617
618 *v0 += *v3;
619 *v3 = siprotate(*v3, 21);
620 *v3 ^= *v0;
621 }
622
623 static inline void sipcompress(u_int64_t *v0, u_int64_t *v1, u_int64_t *v2,
624 u_int64_t *v3, u_int64_t m)
625 {
626 *v3 ^= m;
627 sipround(v0, v1, v2, v3);
628 sipround(v0, v1, v2, v3);
629 *v0 ^= m;
630 }
631
632 static inline u_int64_t siplast(size_t len, u_char *pos)
633 {
634 u_int64_t b;
635 int rem = len & 7;
636
637 b = ((u_int64_t)len) << 56;
638 switch (rem)
639 {
640 case 7:
641 b |= ((u_int64_t)pos[6]) << 48;
642 case 6:
643 b |= ((u_int64_t)pos[5]) << 40;
644 case 5:
645 b |= ((u_int64_t)pos[4]) << 32;
646 case 4:
647 b |= ((u_int64_t)pos[3]) << 24;
648 case 3:
649 b |= ((u_int64_t)pos[2]) << 16;
650 case 2:
651 b |= ((u_int64_t)pos[1]) << 8;
652 case 1:
653 b |= ((u_int64_t)pos[0]);
654 break;
655 case 0:
656 break;
657 }
658 return b;
659 }
660
661 /**
662 * Described in header.
663 */
664 u_int64_t chunk_mac(chunk_t chunk, u_char *key)
665 {
666 u_int64_t v0, v1, v2, v3, k0, k1, m;
667 size_t len = chunk.len;
668 u_char *pos = chunk.ptr, *end;
669
670 end = chunk.ptr + len - (len % 8);
671
672 k0 = sipget(key);
673 k1 = sipget(key + 8);
674
675 v0 = k0 ^ 0x736f6d6570736575ULL;
676 v1 = k1 ^ 0x646f72616e646f6dULL;
677 v2 = k0 ^ 0x6c7967656e657261ULL;
678 v3 = k1 ^ 0x7465646279746573ULL;
679
680 /* compression with c = 2 */
681 for (; pos != end; pos += 8)
682 {
683 m = sipget(pos);
684 sipcompress(&v0, &v1, &v2, &v3, m);
685 }
686 sipcompress(&v0, &v1, &v2, &v3, siplast(len, pos));
687
688 /* finalization with d = 4 */
689 v2 ^= 0xff;
690 sipround(&v0, &v1, &v2, &v3);
691 sipround(&v0, &v1, &v2, &v3);
692 sipround(&v0, &v1, &v2, &v3);
693 sipround(&v0, &v1, &v2, &v3);
694 return v0 ^ v1 ^ v2 ^ v3;
695 }
696
697 /**
698 * Described in header.
699 *
700 * The implementation is based on Paul Hsieh's SuperFastHash:
701 * http://www.azillionmonkeys.com/qed/hash.html
702 */
703 u_int32_t chunk_hash_inc(chunk_t chunk, u_int32_t hash)
704 {
705 u_char *data = chunk.ptr;
706 size_t len = chunk.len;
707 u_int32_t tmp;
708 int rem;
709
710 if (!len || data == NULL)
711 {
712 return 0;
713 }
714
715 rem = len & 3;
716 len >>= 2;
717
718 /* Main loop */
719 for (; len > 0; --len)
720 {
721 hash += get16bits(data);
722 tmp = (get16bits(data + 2) << 11) ^ hash;
723 hash = (hash << 16) ^ tmp;
724 data += 2 * sizeof(u_int16_t);
725 hash += hash >> 11;
726 }
727
728 /* Handle end cases */
729 switch (rem)
730 {
731 case 3:
732 {
733 hash += get16bits(data);
734 hash ^= hash << 16;
735 hash ^= data[sizeof(u_int16_t)] << 18;
736 hash += hash >> 11;
737 break;
738 }
739 case 2:
740 {
741 hash += get16bits(data);
742 hash ^= hash << 11;
743 hash += hash >> 17;
744 break;
745 }
746 case 1:
747 {
748 hash += *data;
749 hash ^= hash << 10;
750 hash += hash >> 1;
751 break;
752 }
753 }
754
755 /* Force "avalanching" of final 127 bits */
756 hash ^= hash << 3;
757 hash += hash >> 5;
758 hash ^= hash << 4;
759 hash += hash >> 17;
760 hash ^= hash << 25;
761 hash += hash >> 6;
762
763 return hash;
764 }
765
766 /**
767 * Described in header.
768 */
769 u_int32_t chunk_hash(chunk_t chunk)
770 {
771 return chunk_hash_inc(chunk, chunk.len);
772 }
773
774 /**
775 * Described in header.
776 */
777 int chunk_printf_hook(printf_hook_data_t *data, printf_hook_spec_t *spec,
778 const void *const *args)
779 {
780 chunk_t *chunk = *((chunk_t**)(args[0]));
781 bool first = TRUE;
782 chunk_t copy = *chunk;
783 int written = 0;
784
785 if (!spec->hash)
786 {
787 u_int chunk_len = chunk->len;
788 const void *new_args[] = {&chunk->ptr, &chunk_len};
789 return mem_printf_hook(data, spec, new_args);
790 }
791
792 while (copy.len > 0)
793 {
794 if (first)
795 {
796 first = FALSE;
797 }
798 else
799 {
800 written += print_in_hook(data, ":");
801 }
802 written += print_in_hook(data, "%02x", *copy.ptr++);
803 copy.len--;
804 }
805 return written;
806 }