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