1 /* 2 * DES and 3DES-EDE ciphers 3 * 4 * Modifications to LibTomCrypt implementation: 5 * Copyright (c) 2006-2009, Jouni Malinen <j (at) w1.fi> 6 * 7 * This software may be distributed under the terms of the BSD license. 8 * See README for more details. 9 */ 10 11 #include "includes.h" 12 13 #include "common.h" 14 #include "crypto.h" 15 #include "des_i.h" 16 17 /* 18 * This implementation is based on a DES implementation included in 19 * LibTomCrypt. The version here is modified to fit in wpa_supplicant/hostapd 20 * coding style. 21 */ 22 23 /* LibTomCrypt, modular cryptographic library -- Tom St Denis 24 * 25 * LibTomCrypt is a library that provides various cryptographic 26 * algorithms in a highly modular and flexible manner. 27 * 28 * The library is free for all purposes without any express 29 * guarantee it works. 30 * 31 * Tom St Denis, tomstdenis (at) gmail.com, http://libtomcrypt.com 32 */ 33 34 /** 35 DES code submitted by Dobes Vandermeer 36 */ 37 38 #define ROLc(x, y) \ 39 ((((unsigned long) (x) << (unsigned long) ((y) & 31)) | \ 40 (((unsigned long) (x) & 0xFFFFFFFFUL) >> \ 41 (unsigned long) (32 - ((y) & 31)))) & 0xFFFFFFFFUL) 42 #define RORc(x, y) \ 43 (((((unsigned long) (x) & 0xFFFFFFFFUL) >> \ 44 (unsigned long) ((y) & 31)) | \ 45 ((unsigned long) (x) << (unsigned long) (32 - ((y) & 31)))) & \ 46 0xFFFFFFFFUL) 47 48 49 static const u32 bytebit[8] = 50 { 51 0200, 0100, 040, 020, 010, 04, 02, 01 52 }; 53 54 static const u32 bigbyte[24] = 55 { 56 0x800000UL, 0x400000UL, 0x200000UL, 0x100000UL, 57 0x80000UL, 0x40000UL, 0x20000UL, 0x10000UL, 58 0x8000UL, 0x4000UL, 0x2000UL, 0x1000UL, 59 0x800UL, 0x400UL, 0x200UL, 0x100UL, 60 0x80UL, 0x40UL, 0x20UL, 0x10UL, 61 0x8UL, 0x4UL, 0x2UL, 0x1L 62 }; 63 64 /* Use the key schedule specific in the standard (ANSI X3.92-1981) */ 65 66 static const u8 pc1[56] = { 67 56, 48, 40, 32, 24, 16, 8, 0, 57, 49, 41, 33, 25, 17, 68 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 69 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 70 13, 5, 60, 52, 44, 36, 28, 20, 12, 4, 27, 19, 11, 3 71 }; 72 73 static const u8 totrot[16] = { 74 1, 2, 4, 6, 75 8, 10, 12, 14, 76 15, 17, 19, 21, 77 23, 25, 27, 28 78 }; 79 80 static const u8 pc2[48] = { 81 13, 16, 10, 23, 0, 4, 2, 27, 14, 5, 20, 9, 82 22, 18, 11, 3, 25, 7, 15, 6, 26, 19, 12, 1, 83 40, 51, 30, 36, 46, 54, 29, 39, 50, 44, 32, 47, 84 43, 48, 38, 55, 33, 52, 45, 41, 49, 35, 28, 31 85 }; 86 87 88 static const u32 SP1[64] = 89 { 90 0x01010400UL, 0x00000000UL, 0x00010000UL, 0x01010404UL, 91 0x01010004UL, 0x00010404UL, 0x00000004UL, 0x00010000UL, 92 0x00000400UL, 0x01010400UL, 0x01010404UL, 0x00000400UL, 93 0x01000404UL, 0x01010004UL, 0x01000000UL, 0x00000004UL, 94 0x00000404UL, 0x01000400UL, 0x01000400UL, 0x00010400UL, 95 0x00010400UL, 0x01010000UL, 0x01010000UL, 0x01000404UL, 96 0x00010004UL, 0x01000004UL, 0x01000004UL, 0x00010004UL, 97 0x00000000UL, 0x00000404UL, 0x00010404UL, 0x01000000UL, 98 0x00010000UL, 0x01010404UL, 0x00000004UL, 0x01010000UL, 99 0x01010400UL, 0x01000000UL, 0x01000000UL, 0x00000400UL, 100 0x01010004UL, 0x00010000UL, 0x00010400UL, 0x01000004UL, 101 0x00000400UL, 0x00000004UL, 0x01000404UL, 0x00010404UL, 102 0x01010404UL, 0x00010004UL, 0x01010000UL, 0x01000404UL, 103 0x01000004UL, 0x00000404UL, 0x00010404UL, 0x01010400UL, 104 0x00000404UL, 0x01000400UL, 0x01000400UL, 0x00000000UL, 105 0x00010004UL, 0x00010400UL, 0x00000000UL, 0x01010004UL 106 }; 107 108 static const u32 SP2[64] = 109 { 110 0x80108020UL, 0x80008000UL, 0x00008000UL, 0x00108020UL, 111 0x00100000UL, 0x00000020UL, 0x80100020UL, 0x80008020UL, 112 0x80000020UL, 0x80108020UL, 0x80108000UL, 0x80000000UL, 113 0x80008000UL, 0x00100000UL, 0x00000020UL, 0x80100020UL, 114 0x00108000UL, 0x00100020UL, 0x80008020UL, 0x00000000UL, 115 0x80000000UL, 0x00008000UL, 0x00108020UL, 0x80100000UL, 116 0x00100020UL, 0x80000020UL, 0x00000000UL, 0x00108000UL, 117 0x00008020UL, 0x80108000UL, 0x80100000UL, 0x00008020UL, 118 0x00000000UL, 0x00108020UL, 0x80100020UL, 0x00100000UL, 119 0x80008020UL, 0x80100000UL, 0x80108000UL, 0x00008000UL, 120 0x80100000UL, 0x80008000UL, 0x00000020UL, 0x80108020UL, 121 0x00108020UL, 0x00000020UL, 0x00008000UL, 0x80000000UL, 122 0x00008020UL, 0x80108000UL, 0x00100000UL, 0x80000020UL, 123 0x00100020UL, 0x80008020UL, 0x80000020UL, 0x00100020UL, 124 0x00108000UL, 0x00000000UL, 0x80008000UL, 0x00008020UL, 125 0x80000000UL, 0x80100020UL, 0x80108020UL, 0x00108000UL 126 }; 127 128 static const u32 SP3[64] = 129 { 130 0x00000208UL, 0x08020200UL, 0x00000000UL, 0x08020008UL, 131 0x08000200UL, 0x00000000UL, 0x00020208UL, 0x08000200UL, 132 0x00020008UL, 0x08000008UL, 0x08000008UL, 0x00020000UL, 133 0x08020208UL, 0x00020008UL, 0x08020000UL, 0x00000208UL, 134 0x08000000UL, 0x00000008UL, 0x08020200UL, 0x00000200UL, 135 0x00020200UL, 0x08020000UL, 0x08020008UL, 0x00020208UL, 136 0x08000208UL, 0x00020200UL, 0x00020000UL, 0x08000208UL, 137 0x00000008UL, 0x08020208UL, 0x00000200UL, 0x08000000UL, 138 0x08020200UL, 0x08000000UL, 0x00020008UL, 0x00000208UL, 139 0x00020000UL, 0x08020200UL, 0x08000200UL, 0x00000000UL, 140 0x00000200UL, 0x00020008UL, 0x08020208UL, 0x08000200UL, 141 0x08000008UL, 0x00000200UL, 0x00000000UL, 0x08020008UL, 142 0x08000208UL, 0x00020000UL, 0x08000000UL, 0x08020208UL, 143 0x00000008UL, 0x00020208UL, 0x00020200UL, 0x08000008UL, 144 0x08020000UL, 0x08000208UL, 0x00000208UL, 0x08020000UL, 145 0x00020208UL, 0x00000008UL, 0x08020008UL, 0x00020200UL 146 }; 147 148 static const u32 SP4[64] = 149 { 150 0x00802001UL, 0x00002081UL, 0x00002081UL, 0x00000080UL, 151 0x00802080UL, 0x00800081UL, 0x00800001UL, 0x00002001UL, 152 0x00000000UL, 0x00802000UL, 0x00802000UL, 0x00802081UL, 153 0x00000081UL, 0x00000000UL, 0x00800080UL, 0x00800001UL, 154 0x00000001UL, 0x00002000UL, 0x00800000UL, 0x00802001UL, 155 0x00000080UL, 0x00800000UL, 0x00002001UL, 0x00002080UL, 156 0x00800081UL, 0x00000001UL, 0x00002080UL, 0x00800080UL, 157 0x00002000UL, 0x00802080UL, 0x00802081UL, 0x00000081UL, 158 0x00800080UL, 0x00800001UL, 0x00802000UL, 0x00802081UL, 159 0x00000081UL, 0x00000000UL, 0x00000000UL, 0x00802000UL, 160 0x00002080UL, 0x00800080UL, 0x00800081UL, 0x00000001UL, 161 0x00802001UL, 0x00002081UL, 0x00002081UL, 0x00000080UL, 162 0x00802081UL, 0x00000081UL, 0x00000001UL, 0x00002000UL, 163 0x00800001UL, 0x00002001UL, 0x00802080UL, 0x00800081UL, 164 0x00002001UL, 0x00002080UL, 0x00800000UL, 0x00802001UL, 165 0x00000080UL, 0x00800000UL, 0x00002000UL, 0x00802080UL 166 }; 167 168 static const u32 SP5[64] = 169 { 170 0x00000100UL, 0x02080100UL, 0x02080000UL, 0x42000100UL, 171 0x00080000UL, 0x00000100UL, 0x40000000UL, 0x02080000UL, 172 0x40080100UL, 0x00080000UL, 0x02000100UL, 0x40080100UL, 173 0x42000100UL, 0x42080000UL, 0x00080100UL, 0x40000000UL, 174 0x02000000UL, 0x40080000UL, 0x40080000UL, 0x00000000UL, 175 0x40000100UL, 0x42080100UL, 0x42080100UL, 0x02000100UL, 176 0x42080000UL, 0x40000100UL, 0x00000000UL, 0x42000000UL, 177 0x02080100UL, 0x02000000UL, 0x42000000UL, 0x00080100UL, 178 0x00080000UL, 0x42000100UL, 0x00000100UL, 0x02000000UL, 179 0x40000000UL, 0x02080000UL, 0x42000100UL, 0x40080100UL, 180 0x02000100UL, 0x40000000UL, 0x42080000UL, 0x02080100UL, 181 0x40080100UL, 0x00000100UL, 0x02000000UL, 0x42080000UL, 182 0x42080100UL, 0x00080100UL, 0x42000000UL, 0x42080100UL, 183 0x02080000UL, 0x00000000UL, 0x40080000UL, 0x42000000UL, 184 0x00080100UL, 0x02000100UL, 0x40000100UL, 0x00080000UL, 185 0x00000000UL, 0x40080000UL, 0x02080100UL, 0x40000100UL 186 }; 187 188 static const u32 SP6[64] = 189 { 190 0x20000010UL, 0x20400000UL, 0x00004000UL, 0x20404010UL, 191 0x20400000UL, 0x00000010UL, 0x20404010UL, 0x00400000UL, 192 0x20004000UL, 0x00404010UL, 0x00400000UL, 0x20000010UL, 193 0x00400010UL, 0x20004000UL, 0x20000000UL, 0x00004010UL, 194 0x00000000UL, 0x00400010UL, 0x20004010UL, 0x00004000UL, 195 0x00404000UL, 0x20004010UL, 0x00000010UL, 0x20400010UL, 196 0x20400010UL, 0x00000000UL, 0x00404010UL, 0x20404000UL, 197 0x00004010UL, 0x00404000UL, 0x20404000UL, 0x20000000UL, 198 0x20004000UL, 0x00000010UL, 0x20400010UL, 0x00404000UL, 199 0x20404010UL, 0x00400000UL, 0x00004010UL, 0x20000010UL, 200 0x00400000UL, 0x20004000UL, 0x20000000UL, 0x00004010UL, 201 0x20000010UL, 0x20404010UL, 0x00404000UL, 0x20400000UL, 202 0x00404010UL, 0x20404000UL, 0x00000000UL, 0x20400010UL, 203 0x00000010UL, 0x00004000UL, 0x20400000UL, 0x00404010UL, 204 0x00004000UL, 0x00400010UL, 0x20004010UL, 0x00000000UL, 205 0x20404000UL, 0x20000000UL, 0x00400010UL, 0x20004010UL 206 }; 207 208 static const u32 SP7[64] = 209 { 210 0x00200000UL, 0x04200002UL, 0x04000802UL, 0x00000000UL, 211 0x00000800UL, 0x04000802UL, 0x00200802UL, 0x04200800UL, 212 0x04200802UL, 0x00200000UL, 0x00000000UL, 0x04000002UL, 213 0x00000002UL, 0x04000000UL, 0x04200002UL, 0x00000802UL, 214 0x04000800UL, 0x00200802UL, 0x00200002UL, 0x04000800UL, 215 0x04000002UL, 0x04200000UL, 0x04200800UL, 0x00200002UL, 216 0x04200000UL, 0x00000800UL, 0x00000802UL, 0x04200802UL, 217 0x00200800UL, 0x00000002UL, 0x04000000UL, 0x00200800UL, 218 0x04000000UL, 0x00200800UL, 0x00200000UL, 0x04000802UL, 219 0x04000802UL, 0x04200002UL, 0x04200002UL, 0x00000002UL, 220 0x00200002UL, 0x04000000UL, 0x04000800UL, 0x00200000UL, 221 0x04200800UL, 0x00000802UL, 0x00200802UL, 0x04200800UL, 222 0x00000802UL, 0x04000002UL, 0x04200802UL, 0x04200000UL, 223 0x00200800UL, 0x00000000UL, 0x00000002UL, 0x04200802UL, 224 0x00000000UL, 0x00200802UL, 0x04200000UL, 0x00000800UL, 225 0x04000002UL, 0x04000800UL, 0x00000800UL, 0x00200002UL 226 }; 227 228 static const u32 SP8[64] = 229 { 230 0x10001040UL, 0x00001000UL, 0x00040000UL, 0x10041040UL, 231 0x10000000UL, 0x10001040UL, 0x00000040UL, 0x10000000UL, 232 0x00040040UL, 0x10040000UL, 0x10041040UL, 0x00041000UL, 233 0x10041000UL, 0x00041040UL, 0x00001000UL, 0x00000040UL, 234 0x10040000UL, 0x10000040UL, 0x10001000UL, 0x00001040UL, 235 0x00041000UL, 0x00040040UL, 0x10040040UL, 0x10041000UL, 236 0x00001040UL, 0x00000000UL, 0x00000000UL, 0x10040040UL, 237 0x10000040UL, 0x10001000UL, 0x00041040UL, 0x00040000UL, 238 0x00041040UL, 0x00040000UL, 0x10041000UL, 0x00001000UL, 239 0x00000040UL, 0x10040040UL, 0x00001000UL, 0x00041040UL, 240 0x10001000UL, 0x00000040UL, 0x10000040UL, 0x10040000UL, 241 0x10040040UL, 0x10000000UL, 0x00040000UL, 0x10001040UL, 242 0x00000000UL, 0x10041040UL, 0x00040040UL, 0x10000040UL, 243 0x10040000UL, 0x10001000UL, 0x10001040UL, 0x00000000UL, 244 0x10041040UL, 0x00041000UL, 0x00041000UL, 0x00001040UL, 245 0x00001040UL, 0x00040040UL, 0x10000000UL, 0x10041000UL 246 }; 247 248 249 static void cookey(const u32 *raw1, u32 *keyout) 250 { 251 u32 *cook; 252 const u32 *raw0; 253 u32 dough[32]; 254 int i; 255 256 cook = dough; 257 for (i = 0; i < 16; i++, raw1++) { 258 raw0 = raw1++; 259 *cook = (*raw0 & 0x00fc0000L) << 6; 260 *cook |= (*raw0 & 0x00000fc0L) << 10; 261 *cook |= (*raw1 & 0x00fc0000L) >> 10; 262 *cook++ |= (*raw1 & 0x00000fc0L) >> 6; 263 *cook = (*raw0 & 0x0003f000L) << 12; 264 *cook |= (*raw0 & 0x0000003fL) << 16; 265 *cook |= (*raw1 & 0x0003f000L) >> 4; 266 *cook++ |= (*raw1 & 0x0000003fL); 267 } 268 269 os_memcpy(keyout, dough, sizeof(dough)); 270 } 271 272 273 static void deskey(const u8 *key, int decrypt, u32 *keyout) 274 { 275 u32 i, j, l, m, n, kn[32]; 276 u8 pc1m[56], pcr[56]; 277 278 for (j = 0; j < 56; j++) { 279 l = (u32) pc1[j]; 280 m = l & 7; 281 pc1m[j] = (u8) 282 ((key[l >> 3U] & bytebit[m]) == bytebit[m] ? 1 : 0); 283 } 284 285 for (i = 0; i < 16; i++) { 286 if (decrypt) 287 m = (15 - i) << 1; 288 else 289 m = i << 1; 290 n = m + 1; 291 kn[m] = kn[n] = 0L; 292 for (j = 0; j < 28; j++) { 293 l = j + (u32) totrot[i]; 294 if (l < 28) 295 pcr[j] = pc1m[l]; 296 else 297 pcr[j] = pc1m[l - 28]; 298 } 299 for (/* j = 28 */; j < 56; j++) { 300 l = j + (u32) totrot[i]; 301 if (l < 56) 302 pcr[j] = pc1m[l]; 303 else 304 pcr[j] = pc1m[l - 28]; 305 } 306 for (j = 0; j < 24; j++) { 307 if ((int) pcr[(int) pc2[j]] != 0) 308 kn[m] |= bigbyte[j]; 309 if ((int) pcr[(int) pc2[j + 24]] != 0) 310 kn[n] |= bigbyte[j]; 311 } 312 } 313 314 cookey(kn, keyout); 315 } 316 317 318 static void desfunc(u32 *block, const u32 *keys) 319 { 320 u32 work, right, leftt; 321 int cur_round; 322 323 leftt = block[0]; 324 right = block[1]; 325 326 work = ((leftt >> 4) ^ right) & 0x0f0f0f0fL; 327 right ^= work; 328 leftt ^= (work << 4); 329 330 work = ((leftt >> 16) ^ right) & 0x0000ffffL; 331 right ^= work; 332 leftt ^= (work << 16); 333 334 work = ((right >> 2) ^ leftt) & 0x33333333L; 335 leftt ^= work; 336 right ^= (work << 2); 337 338 work = ((right >> 8) ^ leftt) & 0x00ff00ffL; 339 leftt ^= work; 340 right ^= (work << 8); 341 342 right = ROLc(right, 1); 343 work = (leftt ^ right) & 0xaaaaaaaaL; 344 345 leftt ^= work; 346 right ^= work; 347 leftt = ROLc(leftt, 1); 348 349 for (cur_round = 0; cur_round < 8; cur_round++) { 350 work = RORc(right, 4) ^ *keys++; 351 leftt ^= SP7[work & 0x3fL] 352 ^ SP5[(work >> 8) & 0x3fL] 353 ^ SP3[(work >> 16) & 0x3fL] 354 ^ SP1[(work >> 24) & 0x3fL]; 355 work = right ^ *keys++; 356 leftt ^= SP8[ work & 0x3fL] 357 ^ SP6[(work >> 8) & 0x3fL] 358 ^ SP4[(work >> 16) & 0x3fL] 359 ^ SP2[(work >> 24) & 0x3fL]; 360 361 work = RORc(leftt, 4) ^ *keys++; 362 right ^= SP7[ work & 0x3fL] 363 ^ SP5[(work >> 8) & 0x3fL] 364 ^ SP3[(work >> 16) & 0x3fL] 365 ^ SP1[(work >> 24) & 0x3fL]; 366 work = leftt ^ *keys++; 367 right ^= SP8[ work & 0x3fL] 368 ^ SP6[(work >> 8) & 0x3fL] 369 ^ SP4[(work >> 16) & 0x3fL] 370 ^ SP2[(work >> 24) & 0x3fL]; 371 } 372 373 right = RORc(right, 1); 374 work = (leftt ^ right) & 0xaaaaaaaaL; 375 leftt ^= work; 376 right ^= work; 377 leftt = RORc(leftt, 1); 378 work = ((leftt >> 8) ^ right) & 0x00ff00ffL; 379 right ^= work; 380 leftt ^= (work << 8); 381 /* -- */ 382 work = ((leftt >> 2) ^ right) & 0x33333333L; 383 right ^= work; 384 leftt ^= (work << 2); 385 work = ((right >> 16) ^ leftt) & 0x0000ffffL; 386 leftt ^= work; 387 right ^= (work << 16); 388 work = ((right >> 4) ^ leftt) & 0x0f0f0f0fL; 389 leftt ^= work; 390 right ^= (work << 4); 391 392 block[0] = right; 393 block[1] = leftt; 394 } 395 396 397 /* wpa_supplicant/hostapd specific wrapper */ 398 399 void des_encrypt(const u8 *clear, const u8 *key, u8 *cypher) 400 { 401 u8 pkey[8], next, tmp; 402 int i; 403 u32 ek[32], work[2]; 404 405 /* Add parity bits to the key */ 406 next = 0; 407 for (i = 0; i < 7; i++) { 408 tmp = key[i]; 409 pkey[i] = (tmp >> i) | next | 1; 410 next = tmp << (7 - i); 411 } 412 pkey[i] = next | 1; 413 414 deskey(pkey, 0, ek); 415 416 work[0] = WPA_GET_BE32(clear); 417 work[1] = WPA_GET_BE32(clear + 4); 418 desfunc(work, ek); 419 WPA_PUT_BE32(cypher, work[0]); 420 WPA_PUT_BE32(cypher + 4, work[1]); 421 422 os_memset(pkey, 0, sizeof(pkey)); 423 os_memset(ek, 0, sizeof(ek)); 424 } 425 426 427 void des_key_setup(const u8 *key, u32 *ek, u32 *dk) 428 { 429 deskey(key, 0, ek); 430 deskey(key, 1, dk); 431 } 432 433 434 void des_block_encrypt(const u8 *plain, const u32 *ek, u8 *crypt) 435 { 436 u32 work[2]; 437 work[0] = WPA_GET_BE32(plain); 438 work[1] = WPA_GET_BE32(plain + 4); 439 desfunc(work, ek); 440 WPA_PUT_BE32(crypt, work[0]); 441 WPA_PUT_BE32(crypt + 4, work[1]); 442 } 443 444 445 void des_block_decrypt(const u8 *crypt, const u32 *dk, u8 *plain) 446 { 447 u32 work[2]; 448 work[0] = WPA_GET_BE32(crypt); 449 work[1] = WPA_GET_BE32(crypt + 4); 450 desfunc(work, dk); 451 WPA_PUT_BE32(plain, work[0]); 452 WPA_PUT_BE32(plain + 4, work[1]); 453 } 454 455 456 void des3_key_setup(const u8 *key, struct des3_key_s *dkey) 457 { 458 deskey(key, 0, dkey->ek[0]); 459 deskey(key + 8, 1, dkey->ek[1]); 460 deskey(key + 16, 0, dkey->ek[2]); 461 462 deskey(key, 1, dkey->dk[2]); 463 deskey(key + 8, 0, dkey->dk[1]); 464 deskey(key + 16, 1, dkey->dk[0]); 465 } 466 467 468 void des3_encrypt(const u8 *plain, const struct des3_key_s *key, u8 *crypt) 469 { 470 u32 work[2]; 471 472 work[0] = WPA_GET_BE32(plain); 473 work[1] = WPA_GET_BE32(plain + 4); 474 desfunc(work, key->ek[0]); 475 desfunc(work, key->ek[1]); 476 desfunc(work, key->ek[2]); 477 WPA_PUT_BE32(crypt, work[0]); 478 WPA_PUT_BE32(crypt + 4, work[1]); 479 } 480 481 482 void des3_decrypt(const u8 *crypt, const struct des3_key_s *key, u8 *plain) 483 { 484 u32 work[2]; 485 486 work[0] = WPA_GET_BE32(crypt); 487 work[1] = WPA_GET_BE32(crypt + 4); 488 desfunc(work, key->dk[0]); 489 desfunc(work, key->dk[1]); 490 desfunc(work, key->dk[2]); 491 WPA_PUT_BE32(plain, work[0]); 492 WPA_PUT_BE32(plain + 4, work[1]); 493 } 494
