servers/exchange/xntlm/xntlm-des.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
   2
   3 /* Copyright (C) 2001-2004 Novell, Inc.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of version 2 of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this program; if not, write to the
  16  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA 02110-1301, USA.
  18  */
  19
  20 #ifdef HAVE_CONFIG_H
  21 #include <config.h>
  22 #endif
  23
  24 #include "xntlm-des.h"
  25 #include <string.h>
  26
  27 /* Public domain DES implementation from Phil Karn */
  28
  29 static guint32 Spbox[8][64] = {
  30         { 0x01010400,0x00000000,0x00010000,0x01010404,
  31           0x01010004,0x00010404,0x00000004,0x00010000,
  32           0x00000400,0x01010400,0x01010404,0x00000400,
  33           0x01000404,0x01010004,0x01000000,0x00000004,
  34           0x00000404,0x01000400,0x01000400,0x00010400,
  35           0x00010400,0x01010000,0x01010000,0x01000404,
  36           0x00010004,0x01000004,0x01000004,0x00010004,
  37           0x00000000,0x00000404,0x00010404,0x01000000,
  38           0x00010000,0x01010404,0x00000004,0x01010000,
  39           0x01010400,0x01000000,0x01000000,0x00000400,
  40           0x01010004,0x00010000,0x00010400,0x01000004,
  41           0x00000400,0x00000004,0x01000404,0x00010404,
  42           0x01010404,0x00010004,0x01010000,0x01000404,
  43           0x01000004,0x00000404,0x00010404,0x01010400,
  44           0x00000404,0x01000400,0x01000400,0x00000000,
  45           0x00010004,0x00010400,0x00000000,0x01010004 },
  46         { 0x80108020,0x80008000,0x00008000,0x00108020,
  47           0x00100000,0x00000020,0x80100020,0x80008020,
  48           0x80000020,0x80108020,0x80108000,0x80000000,
  49           0x80008000,0x00100000,0x00000020,0x80100020,
  50           0x00108000,0x00100020,0x80008020,0x00000000,
  51           0x80000000,0x00008000,0x00108020,0x80100000,
  52           0x00100020,0x80000020,0x00000000,0x00108000,
  53           0x00008020,0x80108000,0x80100000,0x00008020,
  54           0x00000000,0x00108020,0x80100020,0x00100000,
  55           0x80008020,0x80100000,0x80108000,0x00008000,
  56           0x80100000,0x80008000,0x00000020,0x80108020,
  57           0x00108020,0x00000020,0x00008000,0x80000000,
  58           0x00008020,0x80108000,0x00100000,0x80000020,
  59           0x00100020,0x80008020,0x80000020,0x00100020,
  60           0x00108000,0x00000000,0x80008000,0x00008020,
  61           0x80000000,0x80100020,0x80108020,0x00108000 },
  62         { 0x00000208,0x08020200,0x00000000,0x08020008,
  63           0x08000200,0x00000000,0x00020208,0x08000200,
  64           0x00020008,0x08000008,0x08000008,0x00020000,
  65           0x08020208,0x00020008,0x08020000,0x00000208,
  66           0x08000000,0x00000008,0x08020200,0x00000200,
  67           0x00020200,0x08020000,0x08020008,0x00020208,
  68           0x08000208,0x00020200,0x00020000,0x08000208,
  69           0x00000008,0x08020208,0x00000200,0x08000000,
  70           0x08020200,0x08000000,0x00020008,0x00000208,
  71           0x00020000,0x08020200,0x08000200,0x00000000,
  72           0x00000200,0x00020008,0x08020208,0x08000200,
  73           0x08000008,0x00000200,0x00000000,0x08020008,
  74           0x08000208,0x00020000,0x08000000,0x08020208,
  75           0x00000008,0x00020208,0x00020200,0x08000008,
  76           0x08020000,0x08000208,0x00000208,0x08020000,
  77           0x00020208,0x00000008,0x08020008,0x00020200 },
  78         { 0x00802001,0x00002081,0x00002081,0x00000080,
  79           0x00802080,0x00800081,0x00800001,0x00002001,
  80           0x00000000,0x00802000,0x00802000,0x00802081,
  81           0x00000081,0x00000000,0x00800080,0x00800001,
  82           0x00000001,0x00002000,0x00800000,0x00802001,
  83           0x00000080,0x00800000,0x00002001,0x00002080,
  84           0x00800081,0x00000001,0x00002080,0x00800080,
  85           0x00002000,0x00802080,0x00802081,0x00000081,
  86           0x00800080,0x00800001,0x00802000,0x00802081,
  87           0x00000081,0x00000000,0x00000000,0x00802000,
  88           0x00002080,0x00800080,0x00800081,0x00000001,
  89           0x00802001,0x00002081,0x00002081,0x00000080,
  90           0x00802081,0x00000081,0x00000001,0x00002000,
  91           0x00800001,0x00002001,0x00802080,0x00800081,
  92           0x00002001,0x00002080,0x00800000,0x00802001,
  93           0x00000080,0x00800000,0x00002000,0x00802080 },
  94         { 0x00000100,0x02080100,0x02080000,0x42000100,
  95           0x00080000,0x00000100,0x40000000,0x02080000,
  96           0x40080100,0x00080000,0x02000100,0x40080100,
  97           0x42000100,0x42080000,0x00080100,0x40000000,
  98           0x02000000,0x40080000,0x40080000,0x00000000,
  99           0x40000100,0x42080100,0x42080100,0x02000100,
 100           0x42080000,0x40000100,0x00000000,0x42000000,
 101           0x02080100,0x02000000,0x42000000,0x00080100,
 102           0x00080000,0x42000100,0x00000100,0x02000000,
 103           0x40000000,0x02080000,0x42000100,0x40080100,
 104           0x02000100,0x40000000,0x42080000,0x02080100,
 105           0x40080100,0x00000100,0x02000000,0x42080000,
 106           0x42080100,0x00080100,0x42000000,0x42080100,
 107           0x02080000,0x00000000,0x40080000,0x42000000,
 108           0x00080100,0x02000100,0x40000100,0x00080000,
 109           0x00000000,0x40080000,0x02080100,0x40000100 },
 110         { 0x20000010,0x20400000,0x00004000,0x20404010,
 111           0x20400000,0x00000010,0x20404010,0x00400000,
 112           0x20004000,0x00404010,0x00400000,0x20000010,
 113           0x00400010,0x20004000,0x20000000,0x00004010,
 114           0x00000000,0x00400010,0x20004010,0x00004000,
 115           0x00404000,0x20004010,0x00000010,0x20400010,
 116           0x20400010,0x00000000,0x00404010,0x20404000,
 117           0x00004010,0x00404000,0x20404000,0x20000000,
 118           0x20004000,0x00000010,0x20400010,0x00404000,
 119           0x20404010,0x00400000,0x00004010,0x20000010,
 120           0x00400000,0x20004000,0x20000000,0x00004010,
 121           0x20000010,0x20404010,0x00404000,0x20400000,
 122           0x00404010,0x20404000,0x00000000,0x20400010,
 123           0x00000010,0x00004000,0x20400000,0x00404010,
 124           0x00004000,0x00400010,0x20004010,0x00000000,
 125           0x20404000,0x20000000,0x00400010,0x20004010 },
 126         { 0x00200000,0x04200002,0x04000802,0x00000000,
 127           0x00000800,0x04000802,0x00200802,0x04200800,
 128           0x04200802,0x00200000,0x00000000,0x04000002,
 129           0x00000002,0x04000000,0x04200002,0x00000802,
 130           0x04000800,0x00200802,0x00200002,0x04000800,
 131           0x04000002,0x04200000,0x04200800,0x00200002,
 132           0x04200000,0x00000800,0x00000802,0x04200802,
 133           0x00200800,0x00000002,0x04000000,0x00200800,
 134           0x04000000,0x00200800,0x00200000,0x04000802,
 135           0x04000802,0x04200002,0x04200002,0x00000002,
 136           0x00200002,0x04000000,0x04000800,0x00200000,
 137           0x04200800,0x00000802,0x00200802,0x04200800,
 138           0x00000802,0x04000002,0x04200802,0x04200000,
 139           0x00200800,0x00000000,0x00000002,0x04200802,
 140           0x00000000,0x00200802,0x04200000,0x00000800,
 141           0x04000002,0x04000800,0x00000800,0x00200002 },
 142         { 0x10001040,0x00001000,0x00040000,0x10041040,
 143           0x10000000,0x10001040,0x00000040,0x10000000,
 144           0x00040040,0x10040000,0x10041040,0x00041000,
 145           0x10041000,0x00041040,0x00001000,0x00000040,
 146           0x10040000,0x10000040,0x10001000,0x00001040,
 147           0x00041000,0x00040040,0x10040040,0x10041000,
 148           0x00001040,0x00000000,0x00000000,0x10040040,
 149           0x10000040,0x10001000,0x00041040,0x00040000,
 150           0x00041040,0x00040000,0x10041000,0x00001000,
 151           0x00000040,0x10040040,0x00001000,0x00041040,
 152           0x10001000,0x00000040,0x10000040,0x10040000,
 153           0x10040040,0x10000000,0x00040000,0x10001040,
 154           0x00000000,0x10041040,0x00040040,0x10000040,
 155           0x10040000,0x10001000,0x10001040,0x00000000,
 156           0x10041040,0x00041000,0x00041000,0x00001040,
 157           0x00001040,0x00040040,0x10000000,0x10041000 }
 158 };
 159
 160 #undef F
 161 #define F(l,r,key){\
 162         work = ((r >> 4) | (r << 28)) ^ key[0];\
 163         l ^= Spbox[6][work & 0x3f];\
 164         l ^= Spbox[4][(work >> 8) & 0x3f];\
 165         l ^= Spbox[2][(work >> 16) & 0x3f];\
 166         l ^= Spbox[0][(work >> 24) & 0x3f];\
 167         work = r ^ key[1];\
 168         l ^= Spbox[7][work & 0x3f];\
 169         l ^= Spbox[5][(work >> 8) & 0x3f];\
 170         l ^= Spbox[3][(work >> 16) & 0x3f];\
 171         l ^= Spbox[1][(work >> 24) & 0x3f];\
 172 }
 173 /* Encrypt or decrypt a block of data in ECB mode */
 174 void
 175 xntlm_des(XNTLM_DES_KS ks, unsigned char block[8])
 176 {
 177         guint32 left,right,work;
 178
 179         /* Read input block and place in left/right in big-endian order */
 180         left = ((guint32)block[0] << 24)
 181          | ((guint32)block[1] << 16)
 182          | ((guint32)block[2] << 8)
 183          | (guint32)block[3];
 184         right = ((guint32)block[4] << 24)
 185          | ((guint32)block[5] << 16)
 186          | ((guint32)block[6] << 8)
 187          | (guint32)block[7];
 188
 189         /* Hoey's clever initial permutation algorithm, from Outerbridge
 190          * (see Schneier p 478)
 191          *
 192          * The convention here is the same as Outerbridge: rotate each
 193          * register left by 1 bit, i.e., so that "left" contains permuted
 194          * input bits 2, 3, 4, ... 1 and "right" contains 33, 34, 35, ... 32
 195          * (using origin-1 numbering as in the FIPS). This allows us to avoid
 196          * one of the two rotates that would otherwise be required in each of
 197          * the 16 rounds.
 198          */
 199         work = ((left >> 4) ^ right) & 0x0f0f0f0f;
 200         right ^= work;
 201         left ^= work << 4;
 202         work = ((left >> 16) ^ right) & 0xffff;
 203         right ^= work;
 204         left ^= work << 16;
 205         work = ((right >> 2) ^ left) & 0x33333333;
 206         left ^= work;
 207         right ^= (work << 2);
 208         work = ((right >> 8) ^ left) & 0xff00ff;
 209         left ^= work;
 210         right ^= (work << 8);
 211         right = (right << 1) | (right >> 31);
 212         work = (left ^ right) & 0xaaaaaaaa;
 213         left ^= work;
 214         right ^= work;
 215         left = (left << 1) | (left >> 31);
 216
 217         /* Now do the 16 rounds */
 218         F(left,right,ks[0]);
 219         F(right,left,ks[1]);
 220         F(left,right,ks[2]);
 221         F(right,left,ks[3]);
 222         F(left,right,ks[4]);
 223         F(right,left,ks[5]);
 224         F(left,right,ks[6]);
 225         F(right,left,ks[7]);
 226         F(left,right,ks[8]);
 227         F(right,left,ks[9]);
 228         F(left,right,ks[10]);
 229         F(right,left,ks[11]);
 230         F(left,right,ks[12]);
 231         F(right,left,ks[13]);
 232         F(left,right,ks[14]);
 233         F(right,left,ks[15]);
 234
 235         /* Inverse permutation, also from Hoey via Outerbridge and Schneier */
 236         right = (right << 31) | (right >> 1);
 237         work = (left ^ right) & 0xaaaaaaaa;
 238         left ^= work;
 239         right ^= work;
 240         left = (left >> 1) | (left  << 31);
 241         work = ((left >> 8) ^ right) & 0xff00ff;
 242         right ^= work;
 243         left ^= work << 8;
 244         work = ((left >> 2) ^ right) & 0x33333333;
 245         right ^= work;
 246         left ^= work << 2;
 247         work = ((right >> 16) ^ left) & 0xffff;
 248         left ^= work;
 249         right ^= work << 16;
 250         work = ((right >> 4) ^ left) & 0x0f0f0f0f;
 251         left ^= work;
 252         right ^= work << 4;
 253
 254         /* Put the block back into the user's buffer with final swap */
 255         block[0] = right >> 24;
 256         block[1] = right >> 16;
 257         block[2] = right >> 8;
 258         block[3] = right;
 259         block[4] = left >> 24;
 260         block[5] = left >> 16;
 261         block[6] = left >> 8;
 262         block[7] = left;
 263 }
 264
 265 /* Key schedule-related tables from FIPS-46 */
 266
 267 /* permuted choice table (key) */
 268 static unsigned char pc1[] = {
 269         57, 49, 41, 33, 25, 17,  9,
 270          1, 58, 50, 42, 34, 26, 18,
 271         10,  2, 59, 51, 43, 35, 27,
 272         19, 11,  3, 60, 52, 44, 36,
 273
 274         63, 55, 47, 39, 31, 23, 15,
 275          7, 62, 54, 46, 38, 30, 22,
 276         14,  6, 61, 53, 45, 37, 29,
 277         21, 13,  5, 28, 20, 12,  4
 278 };
 279
 280 /* number left rotations of pc1 */
 281 static unsigned char totrot[] = {
 282         1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28
 283 };
 284
 285 /* permuted choice key (table) */
 286 static unsigned char pc2[] = {
 287         14, 17, 11, 24,  1,  5,
 288          3, 28, 15,  6, 21, 10,
 289         23, 19, 12,  4, 26,  8,
 290         16,  7, 27, 20, 13,  2,
 291         41, 52, 31, 37, 47, 55,
 292         30, 40, 51, 45, 33, 48,
 293         44, 49, 39, 56, 34, 53,
 294         46, 42, 50, 36, 29, 32
 295 };
 296
 297 /* End of DES-defined tables */
 298
 299
 300 /* bit 0 is left-most in byte */
 301 static int bytebit[] = {
 302         0200,0100,040,020,010,04,02,01
 303 };
 304
 305
 306 /* Generate key schedule for encryption or decryption
 307  * depending on the value of "decrypt"
 308  */
 309 void
 310 xntlm_deskey(XNTLM_DES_KS k, const unsigned char *key, int decrypt)
 311 {
 312         unsigned char pc1m[56];         /* place to modify pc1 into */
 313         unsigned char pcr[56];          /* place to rotate pc1 into */
 314         register int i,j,l;
 315         int m;
 316         unsigned char ks[8];
 317
 318         for (j=0; j<56; j++) {          /* convert pc1 to bits of key */
 319                 l=pc1[j]-1;             /* integer bit location  */
 320                 m = l & 07;             /* find bit              */
 321                 pc1m[j]=(key[l>>3] &    /* find which key byte l is in */
 322                         bytebit[m])     /* and which bit of that byte */
 323                         ? 1 : 0;        /* and store 1-bit result */
 324         }
 325         for (i=0; i<16; i++) {          /* key chunk for each iteration */
 326                 memset(ks,0,sizeof(ks));        /* Clear key schedule */
 327                 for (j=0; j<56; j++)    /* rotate pc1 the right amount */
 328                         pcr[j] = pc1m[(l=j+totrot[decrypt? 15-i : i])<(j<28? 28 : 56) ? l: l-28];
 329                         /* rotate left and right halves independently */
 330                 for (j=0; j<48; j++){   /* select bits individually */
 331                         /* check bit that goes to ks[j] */
 332                         if (pcr[pc2[j]-1]){
 333                                 /* mask it in if it's there */
 334                                 l= j % 6;
 335                                 ks[j/6] |= bytebit[l] >> 2;
 336                         }
 337                 }
 338                 /* Now convert to packed odd/even interleaved form */
 339                 k[i][0] = ((guint32)ks[0] << 24)
 340                  | ((guint32)ks[2] << 16)
 341                  | ((guint32)ks[4] << 8)
 342                  | ((guint32)ks[6]);
 343                 k[i][1] = ((guint32)ks[1] << 24)
 344                  | ((guint32)ks[3] << 16)
 345                  | ((guint32)ks[5] << 8)
 346                  | ((guint32)ks[7]);
 347         }
 348 }