| blob | 609e010153d0aeff5eda23a2ae9362487d4c8861 |
1 /* des.c --- DES and Triple-DES encryption/decryption Algorithm
2 * Copyright (C) 1998, 1999, 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 * Free Software Foundation, Inc.
4 *
5 * This file is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published
7 * by the Free Software Foundation; either version 2, or (at your
8 * option) any later version.
9 *
10 * This file is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this file; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
18 * 02110-1301, USA.
19 *
20 * ----------------------------------------------------------------------
21 * Functions to compute MD4 message digest of files or memory blocks.
22 * according to the definition of MD4 in RFC 1320 from April 1992. Copyright
23 * (C) 1995,1996,1997,1999,2000,2001,2002,2003,2005,2006 Free Software
24 * Foundation, Inc.
25 *
26 * This program is free software; you can redistribute it and/or modify it
27 * under the terms of the GNU General Public License as published by the
28 * Free Software Foundation; either version 2, or (at your option) any
29 * later version.
30 *
31 * This program is distributed in the hope that it will be useful,
32 * but WITHOUT ANY WARRANTY; without even the implied warranty of
33 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
34 * GNU General Public License for more details.
35 *
36 * You should have received a copy of the GNU General Public License
37 * along with this program; if not, write to the Free Software Foundation,
38 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
39 */
41 #include <sys/types.h>
42 #include <stddef.h>
43 #include <stdlib.h>
44 #include <string.h>
45 #include <stdbool.h>
46 #include <stdint.h>
51 #define SWAP(n) U32LE(n)
53 #define BLOCKSIZE 4096
54 #if BLOCKSIZE % 64 != 0
56 #endif
58 /*
59 * To check alignment gcc has an appropriate operator. Other compilers don't.
60 */
61 # if __GNUC__ >= 2
62 # define UNALIGNED_P(p) (((uintptr_t) p) % __alignof__ (uint32_t) != 0)
63 # else
64 # define alignof(type) offsetof (struct { char c; type x; }, x)
65 # define UNALIGNED_P(p) (((size_t) p) % alignof (uint32_t) != 0)
66 # endif
68 # define MD4_DIGEST_SIZE 16
70 /* MD4 round constants */
71 #define K1 0x5a827999
72 #define K2 0x6ed9eba1
74 /* Round functions. */
75 #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
76 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
77 #define H(x, y, z) ((x) ^ (y) ^ (z))
78 #define rol(x, n) (((x) << (n)) | ((uint32_t) (x) >> (32 - (n))))
79 #define R1(a,b,c,d,k,s) a=rol(a+F(b,c,d)+x[k],s);
80 #define R2(a,b,c,d,k,s) a=rol(a+G(b,c,d)+x[k]+K1,s);
81 #define R3(a,b,c,d,k,s) a=rol(a+H(b,c,d)+x[k]+K2,s);
83 /* This array contains the bytes used to pad the buffer to the next
84 64-byte boundary. (RFC 1320, 3.1: Step 1) */
87 /*
88 * The s-box values are permuted according to the 'primitive function P'
89 * and are rotated one bit to the left.
90 */
103 };
117 };
131 };
145 };
159 };
173 };
187 };
201 };
203 /*
204 * These two tables are part of the 'permuted choice 1' function.
205 * In this implementation several speed improvements are done.
206 */
212 };
219 };
221 /*
222 * Numbers of left shifts per round for encryption subkeys. To
223 * calculate the decryption subkeys we just reverse the ordering of
224 * the calculated encryption subkeys, so there is no need for a
225 * decryption rotate tab.
226 */
229 };
231 /*
232 * Table with weak DES keys sorted in ascending order. In DES there
233 * are 64 known keys which are weak. They are weak because they
234 * produce only one, two or four different subkeys in the subkey
235 * scheduling process. The keys in this table have all their parity
236 * bits cleared.
237 */
303 };
310 /* clear parity bits */
314 /* binary search in the weak key table */
318 {
326 else
328 }
331 }
333 /*
334 * Macro to swap bits across two words.
335 */
336 #define DO_PERMUTATION(a, temp, b, offset, mask) \
337 temp = ((a>>offset) ^ b) & mask; \
338 b ^= temp; \
339 a ^= temp<<offset;
342 /*
343 * This performs the 'initial permutation' of the data to be encrypted
344 * or decrypted. Additionally the resulting two words are rotated one bit
345 * to the left.
346 */
347 #define INITIAL_PERMUTATION(left, temp, right) \
348 DO_PERMUTATION(left, temp, right, 4, 0x0f0f0f0f) \
349 DO_PERMUTATION(left, temp, right, 16, 0x0000ffff) \
350 DO_PERMUTATION(right, temp, left, 2, 0x33333333) \
351 DO_PERMUTATION(right, temp, left, 8, 0x00ff00ff) \
352 right = (right << 1) | (right >> 31); \
353 temp = (left ^ right) & 0xaaaaaaaa; \
354 right ^= temp; \
355 left ^= temp; \
356 left = (left << 1) | (left >> 31);
358 /*
359 * The 'inverse initial permutation'.
360 */
361 #define FINAL_PERMUTATION(left, temp, right) \
362 left = (left << 31) | (left >> 1); \
363 temp = (left ^ right) & 0xaaaaaaaa; \
364 left ^= temp; \
365 right ^= temp; \
366 right = (right << 31) | (right >> 1); \
367 DO_PERMUTATION(right, temp, left, 8, 0x00ff00ff) \
368 DO_PERMUTATION(right, temp, left, 2, 0x33333333) \
369 DO_PERMUTATION(left, temp, right, 16, 0x0000ffff) \
370 DO_PERMUTATION(left, temp, right, 4, 0x0f0f0f0f)
373 /*
374 * A full DES round including 'expansion function', 'sbox substitution'
375 * and 'primitive function P' but without swapping the left and right word.
376 * Please note: The data in 'from' and 'to' is already rotated one bit to
377 * the left, done in the initial permutation.
378 */
379 #define DES_ROUND(from, to, work, subkey) \
380 work = from ^ *subkey++; \
381 to ^= sbox8[ work & 0x3f ]; \
382 to ^= sbox6[ (work>>8) & 0x3f ]; \
383 to ^= sbox4[ (work>>16) & 0x3f ]; \
384 to ^= sbox2[ (work>>24) & 0x3f ]; \
385 work = ((from << 28) | (from >> 4)) ^ *subkey++; \
386 to ^= sbox7[ work & 0x3f ]; \
387 to ^= sbox5[ (work>>8) & 0x3f ]; \
388 to ^= sbox3[ (work>>16) & 0x3f ]; \
389 to ^= sbox1[ (work>>24) & 0x3f ];
391 /*
392 * Macros to convert 8 bytes from/to 32bit words.
393 */
394 #define READ_64BIT_DATA(data, left, right) \
395 left = (data[0] << 24) | (data[1] << 16) | (data[2] << 8) | data[3]; \
396 right = (data[4] << 24) | (data[5] << 16) | (data[6] << 8) | data[7];
398 #define WRITE_64BIT_DATA(data, left, right) \
399 data[0] = (left >> 24) &0xff; data[1] = (left >> 16) &0xff; \
400 data[2] = (left >> 8) &0xff; data[3] = left &0xff; \
401 data[4] = (right >> 24) &0xff; data[5] = (right >> 16) &0xff; \
402 data[6] = (right >> 8) &0xff; data[7] = right &0xff;
404 /*
405 * des_key_schedule(): Calculate 16 subkeys pairs (even/odd) for
406 * 16 encryption rounds.
407 * To calculate subkeys for decryption the caller
408 * have to reorder the generated subkeys.
409 *
410 * rawkey: 8 Bytes of key data
411 * subkey: Array of at least 32 uint32_ts. Will be filled
412 * with calculated subkeys.
413 *
414 */
446 {
497 }
498 }
506 {
509 }
510 }
519 }
541 }
543 /* Process LEN bytes of BUFFER, accumulating context into CTX.
544 It is assumed that LEN % 64 == 0. */
555 /* First increment the byte count. RFC 1320 specifies the possible
556 length of the file up to 2^64 bits. Here we only compute the
557 number of bytes. Do a double word increment. */
562 /* Process all bytes in the buffer with 64 bytes in each round of
563 the loop. */
565 {
568 {
570 words++;
571 }
573 /* Round 1. */
591 /* Round 2. */
609 /* Round 3. */
631 }
632 }
634 /* Initialize structure containing state of computation.
635 (RFC 1320, 3.3: Step 3) */
644 }
646 /* Put result from CTX in first 16 bytes following RESBUF. The result
647 must be in little endian byte order.
649 IMPORTANT: On some systems it is required that RESBUF is correctly
650 aligned for a 32 bits value. */
658 }
660 /* Process the remaining bytes in the internal buffer and the usual
661 prolog according to the standard and write the result to RESBUF.
663 IMPORTANT: On some systems it is required that RESBUF is correctly
664 aligned for a 32 bits value. */
666 /* Take yet unprocessed bytes into account. */
670 /* Now count remaining bytes. */
678 /* Put the 64-bit file length in *bits* at the end of the buffer. */
683 /* Process last bytes. */
687 }
690 /* When we already have some bits in our internal buffer concatenate
691 both inputs first. */
693 {
701 {
705 /* The regions in the following copy operation cannot overlap. */
708 }
712 }
714 /* Process available complete blocks. */
716 {
717 #if !_STRING_ARCH_unaligned
720 {
724 }
725 else
726 #endif
727 {
731 }
732 }
734 /* Move remaining bytes in internal buffer. */
736 {
742 {
746 }
748 }
749 }
751 /* Compute MD4 message digest for bytes read from STREAM. The
752 resulting message digest number will be written into the 16 bytes
753 beginning at RESBLOCK. */
759 /* Initialize the computation context. */
762 /* Iterate over full file contents. */
764 {
765 /* We read the file in blocks of BLOCKSIZE bytes. One call of the
766 computation function processes the whole buffer so that with the
767 next round of the loop another block can be read. */
771 /* Read block. Take care for partial reads. */
773 {
782 {
783 /* Check for the error flag IFF N == 0, so that we don't
784 exit the loop after a partial read due to e.g., EAGAIN
785 or EWOULDBLOCK. */
789 }
791 /* We've read at least one byte, so ignore errors. But always
792 check for EOF, since feof may be true even though N > 0.
793 Otherwise, we could end up calling fread after EOF. */
796 }
798 /* Process buffer with BLOCKSIZE bytes. Note that
799 BLOCKSIZE % 64 == 0
800 */
802 }
804 process_partial_block:;
806 /* Process any remaining bytes. */
810 /* Construct result in desired memory. */
813 }
815 /* Compute MD4 message digest for LEN bytes beginning at BUFFER. The
816 result is always in little endian byte order, so that a byte-wise
817 output yields to the wanted ASCII representation of the message
818 digest. */
822 /* Initialize the computation context. */
825 /* Process whole buffer but last len % 64 bytes. */
828 /* Put result in desired memory area. */
830 }
840 }
843 {
850 /* Reduce the key's size, so that it becomes <= 64 bytes large. */
853 {
862 }
864 /* Compute INNERHASH from KEY and IN. */
876 /* Compute result from KEY and INNERHASH. */
889 }
893 /* Initialize structure containing state of computation.
894 (RFC 1321, 3.3: Step 3) */
895 void
897 {
905 }
907 /* Put result from CTX in first 16 bytes following RESBUF. The result
908 must be in little endian byte order.
910 IMPORTANT: On some systems it is required that RESBUF is correctly
911 aligned for a 32-bit value. */
914 {
921 }
923 /* Process the remaining bytes in the internal buffer and the usual
924 prolog according to the standard and write the result to RESBUF.
926 IMPORTANT: On some systems it is required that RESBUF is correctly
927 aligned for a 32-bit value. */
930 {
931 /* Take yet unprocessed bytes into account. */
935 /* Now count remaining bytes. */
940 /* Put the 64-bit file length in *bits* at the end of the buffer. */
946 /* Process last bytes. */
950 }
952 /* Compute MD5 message digest for bytes read from STREAM. The
953 resulting message digest number will be written into the 16 bytes
954 beginning at RESBLOCK. */
955 int
957 {
962 /* Initialize the computation context. */
965 /* Iterate over full file contents. */
967 {
968 /* We read the file in blocks of BLOCKSIZE bytes. One call of the
969 computation function processes the whole buffer so that with the
970 next round of the loop another block can be read. */
974 /* Read block. Take care for partial reads. */
976 {
985 {
986 /* Check for the error flag IFF N == 0, so that we don't
987 exit the loop after a partial read due to e.g., EAGAIN
988 or EWOULDBLOCK. */
992 }
994 /* We've read at least one byte, so ignore errors. But always
995 check for EOF, since feof may be true even though N > 0.
996 Otherwise, we could end up calling fread after EOF. */
999 }
1001 /* Process buffer with BLOCKSIZE bytes. Note that
1002 BLOCKSIZE % 64 == 0
1003 */
1005 }
1007 process_partial_block:
1009 /* Process any remaining bytes. */
1013 /* Construct result in desired memory. */
1016 }
1018 /* Compute MD5 message digest for LEN bytes beginning at BUFFER. The
1019 result is always in little endian byte order, so that a byte-wise
1020 output yields to the wanted ASCII representation of the message
1021 digest. */
1024 {
1027 /* Initialize the computation context. */
1030 /* Process whole buffer but last len % 64 bytes. */
1033 /* Put result in desired memory area. */
1035 }
1038 void
1040 {
1041 /* When we already have some bits in our internal buffer concatenate
1042 both inputs first. */
1044 {
1052 {
1056 /* The regions in the following copy operation cannot overlap. */
1060 }
1064 }
1066 /* Process available complete blocks. */
1068 {
1069 #if !_STRING_ARCH_unaligned
1072 {
1076 }
1077 else
1078 #endif
1079 {
1083 }
1084 }
1086 /* Move remaining bytes in internal buffer. */
1088 {
1094 {
1098 }
1100 }
1101 }
1104 /* These are the four functions used in the four steps of the MD5 algorithm
1105 and defined in the RFC 1321. The first function is a little bit optimized
1106 (as found in Colin Plumbs public domain implementation). */
1107 /* #define FF(b, c, d) ((b & c) | (~b & d)) */
1108 #define FF(b, c, d) (d ^ (b & (c ^ d)))
1109 #define FG(b, c, d) FF (d, b, c)
1110 #define FH(b, c, d) (b ^ c ^ d)
1111 #define FI(b, c, d) (c ^ (b | ~d))
1113 /* Process LEN bytes of BUFFER, accumulating context into CTX.
1114 It is assumed that LEN % 64 == 0. */
1116 void
1118 {
1128 /* First increment the byte count. RFC 1321 specifies the possible
1129 length of the file up to 2^64 bits. Here we only compute the
1130 number of bytes. Do a double word increment. */
1135 /* Process all bytes in the buffer with 64 bytes in each round of
1136 the loop. */
1138 {
1145 /* First round: using the given function, the context and a constant
1146 the next context is computed. Because the algorithms processing
1147 unit is a 32-bit word and it is determined to work on words in
1148 little endian byte order we perhaps have to change the byte order
1149 before the computation. To reduce the work for the next steps
1150 we store the swapped words in the array CORRECT_WORDS. */
1152 #define OP(a, b, c, d, s, T) \
1153 do \
1154 { \
1155 a += FF (b, c, d) + (*cwp++ = SWAP (*words)) + T; \
1156 ++words; \
1157 CYCLIC (a, s); \
1158 a += b; \
1159 } \
1160 while (0)
1162 /* It is unfortunate that C does not provide an operator for
1163 cyclic rotation. Hope the C compiler is smart enough. */
1164 #define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
1166 /* Before we start, one word to the strange constants.
1167 They are defined in RFC 1321 as
1169 T[i] = (int) (4294967296.0 * fabs (sin (i))), i=1..64
1171 Here is an equivalent invocation using Perl:
1173 perl -e 'foreach(1..64){printf "0x%08x\n", int (4294967296 * abs (sin $_))}'
1174 */
1176 /* Round 1. */
1194 /* For the second to fourth round we have the possibly swapped words
1195 in CORRECT_WORDS. Redefine the macro to take an additional first
1196 argument specifying the function to use. */
1197 #undef OP
1198 #define OP(f, a, b, c, d, k, s, T) \
1199 do \
1200 { \
1201 a += f (b, c, d) + correct_words[k] + T; \
1202 CYCLIC (a, s); \
1203 a += b; \
1204 } \
1205 while (0)
1207 /* Round 2. */
1225 /* Round 3. */
1243 /* Round 4. */
1261 /* Add the starting values of the context. */
1266 }
1268 /* Put checksum in context given as argument. */
1273 }