File indexing completed on 2024-05-12 05:46:50
0001 /* 0002 * Software DES functions 0003 * 0004 * Copyright 1988-1991 Phil Karn <karn@ka9q.net> 0005 * Copyright 2003 Nikos Mavroyanopoulos <nmav@hellug.gr> 0006 * 0007 * Taken from libmcrypt (http://mcrypt.hellug.gr/lib/index.html). 0008 * 0009 * This library is free software; you can redistribute it and/or 0010 * modify it under the terms of the GNU Lesser General Public 0011 * License as published by the Free Software Foundation. 0012 * 0013 * This library is distributed in the hope that it will be useful, 0014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 0015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0016 * Lesser General Public License for more details. 0017 * 0018 * You should have received a copy of the GNU Lesser General Public 0019 * License along with this library; if not, write to the Free Software 0020 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 0021 * MA 02110-1301 USA 0022 */ 0023 0024 /* Software DES functions 0025 * written 12 Dec 1986 by Phil Karn, KA9Q; large sections adapted from 0026 * the 1977 public-domain program by Jim Gillogly 0027 * Modified for additional speed - 6 December 1988 Phil Karn 0028 * Modified for parameterized key schedules - Jan 1991 Phil Karn 0029 * Callers now allocate a key schedule as follows: 0030 * kn = (char (*)[8])malloc(sizeof(char) * 8 * 16); 0031 * or 0032 * char kn[16][8]; 0033 */ 0034 0035 /* modified in order to use the libmcrypt API by Nikos Mavroyanopoulos 0036 * All modifications are placed under the license of libmcrypt. 0037 */ 0038 0039 #include "des.h" 0040 0041 #include <string.h> 0042 #include <qendian.h> 0043 0044 static void permute_ip(unsigned char *inblock, DES_KEY *key, unsigned char *outblock); 0045 static void permute_fp(unsigned char *inblock, DES_KEY *key, unsigned char *outblock); 0046 static void perminit_ip(DES_KEY *key); 0047 static void spinit(DES_KEY *key); 0048 static void perminit_fp(DES_KEY *key); 0049 static quint32 f(DES_KEY *key, quint32 r, char *subkey); 0050 0051 /* Tables defined in the Data Encryption Standard documents */ 0052 0053 /* initial permutation IP */ 0054 static const char ip[] = { 0055 58, 50, 42, 34, 26, 18, 10, 2, 0056 60, 52, 44, 36, 28, 20, 12, 4, 0057 62, 54, 46, 38, 30, 22, 14, 6, 0058 64, 56, 48, 40, 32, 24, 16, 8, 0059 57, 49, 41, 33, 25, 17, 9, 1, 0060 59, 51, 43, 35, 27, 19, 11, 3, 0061 61, 53, 45, 37, 29, 21, 13, 5, 0062 63, 55, 47, 39, 31, 23, 15, 7 0063 }; 0064 0065 /* final permutation IP^-1 */ 0066 static const char fp[] = { 0067 40, 8, 48, 16, 56, 24, 64, 32, 0068 39, 7, 47, 15, 55, 23, 63, 31, 0069 38, 6, 46, 14, 54, 22, 62, 30, 0070 37, 5, 45, 13, 53, 21, 61, 29, 0071 36, 4, 44, 12, 52, 20, 60, 28, 0072 35, 3, 43, 11, 51, 19, 59, 27, 0073 34, 2, 42, 10, 50, 18, 58, 26, 0074 33, 1, 41, 9, 49, 17, 57, 25 0075 }; 0076 0077 /* expansion operation matrix 0078 * This is for reference only; it is unused in the code 0079 * as the f() function performs it implicitly for speed 0080 */ 0081 #ifdef notdef 0082 static const char ei[] = { 0083 32, 1, 2, 3, 4, 5, 0084 4, 5, 6, 7, 8, 9, 0085 8, 9, 10, 11, 12, 13, 0086 12, 13, 14, 15, 16, 17, 0087 16, 17, 18, 19, 20, 21, 0088 20, 21, 22, 23, 24, 25, 0089 24, 25, 26, 27, 28, 29, 0090 28, 29, 30, 31, 32, 1 0091 }; 0092 #endif 0093 0094 /* permuted choice table (key) */ 0095 static const char pc1[] = { 0096 57, 49, 41, 33, 25, 17, 9, 0097 1, 58, 50, 42, 34, 26, 18, 0098 10, 2, 59, 51, 43, 35, 27, 0099 19, 11, 3, 60, 52, 44, 36, 0100 0101 63, 55, 47, 39, 31, 23, 15, 0102 7, 62, 54, 46, 38, 30, 22, 0103 14, 6, 61, 53, 45, 37, 29, 0104 21, 13, 5, 28, 20, 12, 4 0105 }; 0106 0107 /* number left rotations of pc1 */ 0108 static const char totrot[] = { 0109 1, 2, 4, 6, 8, 10, 12, 14, 15, 17, 19, 21, 23, 25, 27, 28 0110 }; 0111 0112 /* permuted choice key (table) */ 0113 static const char pc2[] = { 0114 14, 17, 11, 24, 1, 5, 0115 3, 28, 15, 6, 21, 10, 0116 23, 19, 12, 4, 26, 8, 0117 16, 7, 27, 20, 13, 2, 0118 41, 52, 31, 37, 47, 55, 0119 30, 40, 51, 45, 33, 48, 0120 44, 49, 39, 56, 34, 53, 0121 46, 42, 50, 36, 29, 32 0122 }; 0123 0124 /* The (in)famous S-boxes */ 0125 static const char si[8][64] = { 0126 /* S1 */ 0127 { 0128 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, 0129 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8, 0130 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0, 0131 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13 0132 }, 0133 0134 /* S2 */ 0135 { 0136 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10, 0137 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5, 0138 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15, 0139 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9 0140 }, 0141 0142 /* S3 */ 0143 { 0144 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8, 0145 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1, 0146 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7, 0147 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12 0148 }, 0149 0150 /* S4 */ 0151 { 0152 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15, 0153 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9, 0154 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4, 0155 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14 0156 }, 0157 0158 /* S5 */ 0159 { 0160 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9, 0161 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6, 0162 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14, 0163 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3 0164 }, 0165 0166 /* S6 */ 0167 { 0168 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11, 0169 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8, 0170 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6, 0171 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13 0172 }, 0173 0174 /* S7 */ 0175 { 0176 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1, 0177 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6, 0178 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2, 0179 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12 0180 }, 0181 0182 /* S8 */ 0183 { 0184 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7, 0185 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2, 0186 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8, 0187 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11 0188 }, 0189 0190 }; 0191 0192 /* 32-bit permutation function P used on the output of the S-boxes */ 0193 static const char p32i[] = { 0194 16, 7, 20, 21, 0195 29, 12, 28, 17, 0196 1, 15, 23, 26, 0197 5, 18, 31, 10, 0198 2, 8, 24, 14, 0199 32, 27, 3, 9, 0200 19, 13, 30, 6, 0201 22, 11, 4, 25 0202 }; 0203 0204 /* End of DES-defined tables */ 0205 0206 /* Lookup tables initialized once only at startup by desinit() */ 0207 0208 /* bit 0 is left-most in byte */ 0209 static const int bytebit[] = { 0210 0200, 0100, 040, 020, 010, 04, 02, 01 0211 }; 0212 0213 static const int nibblebit[] = { 0214 010, 04, 02, 01 0215 }; 0216 0217 /* Allocate space and initialize DES lookup arrays 0218 * mode == 0: standard Data Encryption Algorithm 0219 */ 0220 static int 0221 desinit(DES_KEY *key) 0222 { 0223 0224 spinit(key); 0225 perminit_ip(key); 0226 perminit_fp(key); 0227 0228 return 0; 0229 } 0230 0231 /* Set key (initialize key schedule array) */ 0232 int 0233 ntlm_des_set_key(DES_KEY *dkey, char *user_key, int /*len*/) 0234 { 0235 char pc1m[56]; /* place to modify pc1 into */ 0236 char pcr[56]; /* place to rotate pc1 into */ 0237 int i, j, l; 0238 int m; 0239 0240 memset(dkey, 0, sizeof(DES_KEY)); 0241 desinit(dkey); 0242 0243 /* Clear key schedule */ 0244 0245 for (j = 0; j < 56; ++j) { 0246 /* convert pc1 to bits of key */ 0247 l = pc1[j] - 1; /* integer bit location */ 0248 m = l & 07; /* find bit */ 0249 pc1m[j] = (user_key[l >> 3] & /* find which key byte l is in */ 0250 bytebit[m]) /* and which bit of that byte */ 0251 ? 1 : 0; /* and store 1-bit result */ 0252 0253 } 0254 for (i = 0; i < 16; ++i) { 0255 /* key chunk for each iteration */ 0256 for (j = 0; j < 56; ++j) { /* rotate pc1 the right amount */ 0257 pcr[j] = pc1m[(l = j + totrot[i]) < (j < 28 ? 28 : 56) ? l : l - 28]; 0258 } 0259 /* rotate left and right halves independently */ 0260 for (j = 0; j < 48; ++j) { 0261 /* select bits individually */ 0262 /* check bit that goes to kn[j] */ 0263 if (pcr[pc2[j] - 1]) { 0264 /* mask it in if it's there */ 0265 l = j % 6; 0266 dkey->kn[i][j / 6] |= bytebit[l] >> 2; 0267 } 0268 } 0269 } 0270 return 0; 0271 } 0272 0273 /* In-place encryption of 64-bit block */ 0274 static void 0275 ntlm_des_encrypt(DES_KEY *key, unsigned char *block) 0276 { 0277 quint32 left, right; 0278 char *knp; 0279 quint32 work[2]; /* Working data storage */ 0280 0281 permute_ip(block, key, (unsigned char *) work); /* Initial Permutation */ 0282 left = qFromBigEndian(work[0]); 0283 right = qFromBigEndian(work[1]); 0284 0285 /* Do the 16 rounds. 0286 * The rounds are numbered from 0 to 15. On even rounds 0287 * the right half is fed to f() and the result exclusive-ORs 0288 * the left half; on odd rounds the reverse is done. 0289 */ 0290 knp = &key->kn[0][0]; 0291 left ^= f(key, right, knp); 0292 knp += 8; 0293 right ^= f(key, left, knp); 0294 knp += 8; 0295 left ^= f(key, right, knp); 0296 knp += 8; 0297 right ^= f(key, left, knp); 0298 knp += 8; 0299 left ^= f(key, right, knp); 0300 knp += 8; 0301 right ^= f(key, left, knp); 0302 knp += 8; 0303 left ^= f(key, right, knp); 0304 knp += 8; 0305 right ^= f(key, left, knp); 0306 knp += 8; 0307 left ^= f(key, right, knp); 0308 knp += 8; 0309 right ^= f(key, left, knp); 0310 knp += 8; 0311 left ^= f(key, right, knp); 0312 knp += 8; 0313 right ^= f(key, left, knp); 0314 knp += 8; 0315 left ^= f(key, right, knp); 0316 knp += 8; 0317 right ^= f(key, left, knp); 0318 knp += 8; 0319 left ^= f(key, right, knp); 0320 knp += 8; 0321 right ^= f(key, left, knp); 0322 0323 /* Left/right half swap, plus byte swap if little-endian */ 0324 work[1] = qToBigEndian(left); 0325 work[0] = qToBigEndian(right); 0326 0327 permute_fp((unsigned char *) work, key, block); /* Inverse initial permutation */ 0328 } 0329 0330 /* Permute inblock with perm */ 0331 static void 0332 permute_ip(unsigned char *inblock, DES_KEY *key, unsigned char *outblock) 0333 { 0334 unsigned char *ib, *ob; /* ptr to input or output block */ 0335 char *p, *q; 0336 int j; 0337 0338 /* Clear output block */ 0339 memset(outblock, 0, 8); 0340 0341 ib = inblock; 0342 for (j = 0; j < 16; j += 2, ++ib) { 0343 /* for each input nibble */ 0344 ob = outblock; 0345 p = key->iperm[j][(*ib >> 4) & 0xf]; 0346 q = key->iperm[j + 1][*ib & 0xf]; 0347 /* and each output byte, OR the masks together */ 0348 *ob++ |= *p++ | *q++; 0349 *ob++ |= *p++ | *q++; 0350 *ob++ |= *p++ | *q++; 0351 *ob++ |= *p++ | *q++; 0352 *ob++ |= *p++ | *q++; 0353 *ob++ |= *p++ | *q++; 0354 *ob++ |= *p++ | *q++; 0355 *ob++ |= *p++ | *q++; 0356 } 0357 } 0358 0359 /* Permute inblock with perm */ 0360 static void 0361 permute_fp(unsigned char *inblock, DES_KEY *key, unsigned char *outblock) 0362 { 0363 unsigned char *ib, *ob; /* ptr to input or output block */ 0364 char *p, *q; 0365 int j; 0366 0367 /* Clear output block */ 0368 memset(outblock, 0, 8); 0369 0370 ib = inblock; 0371 for (j = 0; j < 16; j += 2, ++ib) { 0372 /* for each input nibble */ 0373 ob = outblock; 0374 p = key->fperm[j][(*ib >> 4) & 0xf]; 0375 q = key->fperm[j + 1][*ib & 0xf]; 0376 /* and each output byte, OR the masks together */ 0377 *ob++ |= *p++ | *q++; 0378 *ob++ |= *p++ | *q++; 0379 *ob++ |= *p++ | *q++; 0380 *ob++ |= *p++ | *q++; 0381 *ob++ |= *p++ | *q++; 0382 *ob++ |= *p++ | *q++; 0383 *ob++ |= *p++ | *q++; 0384 *ob++ |= *p++ | *q++; 0385 } 0386 } 0387 0388 /* The nonlinear function f(r,k), the heart of DES */ 0389 static quint32 0390 f(DES_KEY *key, quint32 r, char *subkey) 0391 { 0392 quint32 *spp; 0393 quint32 rval, rt; 0394 int er; 0395 0396 #ifdef TRACE 0397 printf("f(%08lx, %02x %02x %02x %02x %02x %02x %02x %02x) = ", 0398 r, 0399 subkey[0], subkey[1], subkey[2], 0400 subkey[3], subkey[4], subkey[5], subkey[6], subkey[7]); 0401 #endif 0402 /* Run E(R) ^ K through the combined S & P boxes. 0403 * This code takes advantage of a convenient regularity in 0404 * E, namely that each group of 6 bits in E(R) feeding 0405 * a single S-box is a contiguous segment of R. 0406 */ 0407 subkey += 7; 0408 0409 /* Compute E(R) for each block of 6 bits, and run thru boxes */ 0410 er = ((int) r << 1) | ((r & 0x80000000) ? 1 : 0); 0411 spp = &key->sp[7][0]; 0412 rval = spp[(er ^ *subkey--) & 0x3f]; 0413 spp -= 64; 0414 rt = (quint32) r >> 3; 0415 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 0416 spp -= 64; 0417 rt >>= 4; 0418 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 0419 spp -= 64; 0420 rt >>= 4; 0421 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 0422 spp -= 64; 0423 rt >>= 4; 0424 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 0425 spp -= 64; 0426 rt >>= 4; 0427 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 0428 spp -= 64; 0429 rt >>= 4; 0430 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 0431 spp -= 64; 0432 rt >>= 4; 0433 rt |= (r & 1) << 5; 0434 rval |= spp[((int) rt ^ *subkey) & 0x3f]; 0435 #ifdef TRACE 0436 printf(" %08lx\n", rval); 0437 #endif 0438 return rval; 0439 } 0440 0441 /* initialize a perm array */ 0442 static void 0443 perminit_ip(DES_KEY *key) 0444 { 0445 int l, j, k; 0446 int i, m; 0447 0448 /* Clear the permutation array */ 0449 memset(key->iperm, 0, 16 * 16 * 8); 0450 0451 for (i = 0; i < 16; ++i) /* each input nibble position */ 0452 for (j = 0; j < 16; ++j) /* each possible input nibble */ 0453 for (k = 0; k < 64; ++k) { 0454 /* each output bit position */ 0455 l = ip[k] - 1; /* where does this bit come from */ 0456 if ((l >> 2) != i) { /* does it come from input posn? */ 0457 continue; /* if not, bit k is 0 */ 0458 } 0459 if (!(j & nibblebit[l & 3])) { 0460 continue; /* any such bit in input? */ 0461 } 0462 m = k & 07; /* which bit is this in the byte */ 0463 key->iperm[i][j][k >> 3] |= bytebit[m]; 0464 } 0465 } 0466 0467 static void 0468 perminit_fp(DES_KEY *key) 0469 { 0470 int l, j, k; 0471 int i, m; 0472 0473 /* Clear the permutation array */ 0474 memset(key->fperm, 0, 16 * 16 * 8); 0475 0476 for (i = 0; i < 16; ++i) /* each input nibble position */ 0477 for (j = 0; j < 16; ++j) /* each possible input nibble */ 0478 for (k = 0; k < 64; ++k) { 0479 /* each output bit position */ 0480 l = fp[k] - 1; /* where does this bit come from */ 0481 if ((l >> 2) != i) { /* does it come from input posn? */ 0482 continue; /* if not, bit k is 0 */ 0483 } 0484 if (!(j & nibblebit[l & 3])) { 0485 continue; /* any such bit in input? */ 0486 } 0487 m = k & 07; /* which bit is this in the byte */ 0488 key->fperm[i][j][k >> 3] |= bytebit[m]; 0489 } 0490 } 0491 0492 /* Initialize the lookup table for the combined S and P boxes */ 0493 static void 0494 spinit(DES_KEY *key) 0495 { 0496 char pbox[32]; 0497 int p, i, s, j, rowcol; 0498 quint32 val; 0499 0500 /* Compute pbox, the inverse of p32i. 0501 * This is easier to work with 0502 */ 0503 for (p = 0; p < 32; ++p) { 0504 for (i = 0; i < 32; ++i) { 0505 if (p32i[i] - 1 == p) { 0506 pbox[p] = i; 0507 break; 0508 } 0509 } 0510 } 0511 for (s = 0; s < 8; ++s) { 0512 /* For each S-box */ 0513 for (i = 0; i < 64; ++i) { 0514 /* For each possible input */ 0515 val = 0; 0516 /* The row number is formed from the first and last 0517 * bits; the column number is from the middle 4 0518 */ 0519 rowcol = (i & 32) | ((i & 1) ? 16 : 0) | ((i >> 1) & 0xf); 0520 for (j = 0; j < 4; j++) { 0521 /* For each output bit */ 0522 if (si[s][rowcol] & (8 >> j)) { 0523 val |= 1L << (31 - pbox[4 * s + j]); 0524 } 0525 } 0526 key->sp[s][i] = val; 0527 } 0528 } 0529 } 0530 0531 int 0532 ntlm_des_ecb_encrypt(const void *plaintext, int len, DES_KEY *akey, 0533 unsigned char output[8]) 0534 { 0535 int j; 0536 const unsigned char *plain = (const unsigned char *) plaintext; 0537 0538 for (j = 0; j < len / 8; ++j) { 0539 memcpy(&output[j * 8], &plain[j * 8], 8); 0540 ntlm_des_encrypt(akey, &output[j * 8]); 0541 } 0542 0543 if (j == 0 && len != 0) { 0544 return -1; /* no blocks were encrypted */ 0545 } 0546 return 0; 0547 }