001 /* 002 * CDDL HEADER START 003 * 004 * The contents of this file are subject to the terms of the 005 * Common Development and Distribution License, Version 1.0 only 006 * (the "License"). You may not use this file except in compliance 007 * with the License. 008 * 009 * You can obtain a copy of the license at 010 * trunk/opends/resource/legal-notices/OpenDS.LICENSE 011 * or https://OpenDS.dev.java.net/OpenDS.LICENSE. 012 * See the License for the specific language governing permissions 013 * and limitations under the License. 014 * 015 * When distributing Covered Code, include this CDDL HEADER in each 016 * file and include the License file at 017 * trunk/opends/resource/legal-notices/OpenDS.LICENSE. If applicable, 018 * add the following below this CDDL HEADER, with the fields enclosed 019 * by brackets "[]" replaced with your own identifying information: 020 * Portions Copyright [yyyy] [name of copyright owner] 021 * 022 * CDDL HEADER END 023 * 024 * 025 * Copyright 2008 Sun Microsystems, Inc. 026 */ 027 /* 028 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 029 * Use is subject to license terms. 030 */ 031 032 /* Copyright (c) 1984,1988 AT&T */ 033 /* All Rights Reserved */ 034 package org.opends.server.util; 035 036 037 038 /** 039 * UNIX Crypt cipher, ported from the Sun OpenSolaris project. 040 * */ 041 @org.opends.server.types.PublicAPI( 042 stability=org.opends.server.types.StabilityLevel.VOLATILE, 043 mayInstantiate=true, 044 mayExtend=false, 045 mayInvoke=true) 046 public final class Crypt 047 { 048 049 /* LINTLIBRARY */ 050 /* 051 * This program implements the Proposed Federal Information Processing Data 052 * Encryption Standard. See Federal Register, March 17, 1975 (40FR12134) 053 */ 054 055 /* 056 * Initial permutation, 057 */ 058 private static final byte IP[] = 059 { 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 060 12, 4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8, 57, 061 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3, 61, 53, 45, 37, 062 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7, }; 063 064 /* 065 * Final permutation, FP = IP^(-1) 066 */ 067 private static final byte FP[] = 068 { 40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 069 63, 31, 38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29, 36, 070 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27, 34, 2, 42, 10, 071 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25, }; 072 073 /* 074 * Permuted-choice 1 from the key bits to yield C and D. Note that bits 075 * 8,16... are left out: They are intended for a parity check. 076 */ 077 private static final byte PC1_C[] = 078 { 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 079 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36, }; 080 081 private static final byte PC1_D[] = 082 { 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22, 083 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4, }; 084 085 /* 086 * Sequence of shifts used for the key schedule. 087 */ 088 private static final byte shifts[] = 089 { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, }; 090 091 /* 092 * Permuted-choice 2, to pick out the bits from the CD array that generate the 093 * key schedule. 094 */ 095 private static final int PC2_C[] = 096 { 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 097 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, }; 098 099 private static final byte PC2_D[] = 100 { 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 101 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32, }; 102 103 /** 104 * Container for many variables altered throughout the encryption process. 105 * */ 106 private static class SubCrypt 107 { 108 /* 109 * The C and D arrays used to calculate the key schedule. 110 */ 111 int _C[] = new int[28]; 112 113 int _D[] = new int[28]; 114 115 /* 116 * The key schedule. Generated from the key. 117 */ 118 int _KS[][] = new int[16][48]; 119 120 /* 121 * The E bit-selection table. 122 */ 123 int _E[] = new int[48]; 124 125 /* 126 * The current block, divided into 2 halves. 127 */ 128 int _L[] = new int[32]; 129 130 int _R[] = new int[32]; 131 132 int _tempL[] = new int[32]; 133 134 int _f[] = new int[32]; 135 136 /* 137 * The combination of the key and the input, before selection. 138 */ 139 int _preS[] = new int[48]; 140 141 /* 142 * Temps for crypt 143 */ 144 int _ablock[] = new int[66]; 145 146 int _iobuf[] = new int[16]; 147 } 148 149 private final SubCrypt _crypt; 150 151 /** 152 * Constructor. 153 */ 154 public Crypt() { 155 _crypt = new SubCrypt(); 156 157 for (int i = 0; i < _crypt._E.length; i++) 158 _crypt._E[i] = e[i]; 159 } 160 161 162 /** 163 * Sets up the key schedule from the key. 164 */ 165 private void setkey(int[] key) 166 { 167 int i, j, k; 168 int t; 169 SubCrypt _c = _crypt; 170 171 /* 172 * if (_c == null) { _cryptinit(); _c = __crypt; } 173 */ 174 /* 175 * First, generate C and D by permuting the key. The low order bit of each 176 * 8-bit char is not used, so C and D are only 28 bits apiece. 177 */ 178 for (i = 0; i < 28; i++) 179 { 180 _c._C[i] = key[PC1_C[i] - 1]; 181 _c._D[i] = key[PC1_D[i] - 1]; 182 } 183 /* 184 * To generate Ki, rotate C and D according to schedule and pick up a 185 * permutation using PC2. 186 */ 187 for (i = 0; i < 16; i++) 188 { 189 /* 190 * rotate. 191 */ 192 for (k = 0; k < shifts[i]; k++) 193 { 194 t = _c._C[0]; 195 for (j = 0; j < 28 - 1; j++) 196 _c._C[j] = _c._C[j + 1]; 197 _c._C[27] = t; 198 t = _c._D[0]; 199 for (j = 0; j < 28 - 1; j++) 200 _c._D[j] = _c._D[j + 1]; 201 _c._D[27] = t; 202 } 203 /* 204 * get Ki. Note C and D are concatenated. 205 */ 206 for (j = 0; j < 24; j++) 207 { 208 _c._KS[i][j] = _c._C[PC2_C[j] - 1]; 209 _c._KS[i][j + 24] = _c._D[PC2_D[j] - 28 - 1]; 210 } 211 } 212 } 213 214 /* 215 * The E bit-selection table. 216 */ 217 private static final byte e[] = 218 { 32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 219 13, 12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 220 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1, }; 221 222 /* 223 * The 8 selection functions. For some reason, they give a 0-origin index, 224 * unlike everything else. 225 */ 226 private static final int S[][] = 227 { 228 { 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, 0, 15, 7, 4, 14, 229 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8, 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 230 9, 7, 3, 10, 5, 0, 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13 }, 231 232 { 233 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10, 3, 13, 4, 7, 15, 2, 234 8, 14, 12, 0, 1, 10, 6, 9, 11, 5, 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 235 6, 9, 3, 2, 15, 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9 }, 236 237 { 238 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8, 13, 7, 0, 9, 3, 4, 239 6, 10, 2, 8, 5, 14, 12, 11, 15, 1, 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 240 12, 5, 10, 14, 7, 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12 }, 241 242 { 243 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15, 13, 8, 11, 5, 6, 244 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9, 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 245 3, 14, 5, 2, 8, 4, 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14 }, 246 247 { 248 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9, 14, 11, 2, 12, 4, 249 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6, 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 250 5, 6, 3, 0, 14, 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3 }, 251 252 { 253 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11, 10, 15, 4, 2, 7, 254 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8, 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 255 10, 1, 13, 11, 6, 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13 }, 256 257 { 258 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1, 13, 0, 11, 7, 4, 9, 259 1, 10, 14, 3, 5, 12, 2, 15, 8, 6, 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 260 8, 0, 5, 9, 2, 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12 }, 261 262 { 263 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7, 1, 15, 13, 8, 10, 264 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2, 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 265 13, 15, 3, 5, 8, 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11 } 266 }; 267 268 /* 269 * P is a permutation on the selected combination of the current L and key. 270 */ 271 private static final int P[] = 272 { 16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 273 10, 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25, }; 274 275 /** 276 * Encrypts a block in place. 277 */ 278 private final void encrypt(int block[], int edflag) 279 { 280 int i, ii; 281 int t, j, k; 282 SubCrypt _c = _crypt; 283 284 int a = 0; 285 286 /* 287 * First, permute the bits in the input 288 */ 289 for (j = 0; j < 64; j++) 290 { 291 a = IP[j] - 1; 292 int b = block[a]; 293 if (j <= 31) 294 _c._L[j] = b; 295 else 296 _c._R[j - 32] = b; 297 298 } 299 /* 300 * Perform an encryption operation 16 times. 301 */ 302 for (ii = 0; ii < 16; ii++) 303 { 304 /* 305 * Set direction 306 */ 307 if (edflag != 0) 308 { 309 i = 15 - ii; 310 } 311 else 312 { 313 i = ii; 314 } 315 /* 316 * Save the R array, which will be the new L. 317 */ 318 for (j = 0; j < 32; j++) 319 _c._tempL[j] = _c._R[j]; 320 /* 321 * Expand R to 48 bits using the E selector; exclusive-or with the current 322 * key bits. 323 */ 324 for (j = 0; j < 48; j++) 325 _c._preS[j] = _c._R[_c._E[j] - 1] ^ _c._KS[i][j]; 326 /* 327 * The pre-select bits are now considered in 8 groups of 6 bits each. The 328 * 8 selection functions map these 6-bit quantities into 4-bit quantities 329 * and the results permuted to make an f(R, K). The indexing into the 330 * selection functions is peculiar; it could be simplified by rewriting 331 * the tables. 332 */ 333 for (j = 0; j < 8; j++) 334 { 335 t = 6 * j; 336 k = S[j][(_c._preS[t + 0] << 5) + (_c._preS[t + 1] << 3) 337 + (_c._preS[t + 2] << 2) + (_c._preS[t + 3] << 1) 338 + (_c._preS[t + 4] << 0) + (_c._preS[t + 5] << 4)]; 339 t = 4 * j; 340 _c._f[t + 0] = (k >> 3) & 01; 341 _c._f[t + 1] = (k >> 2) & 01; 342 _c._f[t + 2] = (k >> 1) & 01; 343 _c._f[t + 3] = (k >> 0) & 01; 344 } 345 /* 346 * The new R is L ^ f(R, K). The f here has to be permuted first, though. 347 */ 348 for (j = 0; j < 32; j++) 349 _c._R[j] = _c._L[j] ^ _c._f[P[j] - 1]; 350 /* 351 * Finally, the new L (the original R) is copied back. 352 */ 353 for (j = 0; j < 32; j++) 354 _c._L[j] = _c._tempL[j]; 355 } 356 /* 357 * The output L and R are reversed. 358 */ 359 for (j = 0; j < 32; j++) 360 { 361 t = _c._L[j]; 362 _c._L[j] = _c._R[j]; 363 _c._R[j] = t; 364 } 365 /* 366 * The final output gets the inverse permutation of the very original. 367 */ 368 for (j = 0; j < 64; j++) 369 { 370 int iv = FP[j] - 1; 371 a = (iv <= 31) ? _c._L[iv] : _c._R[iv - 32]; 372 block[j] = a; 373 } 374 } 375 376 private Object digestLock = new Object(); 377 378 /** 379 * Encode the supplied password in unix crypt form with the provided 380 * salt. 381 * 382 * @param pw A password to encode. 383 * @param salt A salt array of any size, of which only the first 384 * 2 bytes will be considered. 385 * @return A trimmed array 386 * 387 * */ 388 public byte[] crypt(byte[] pw, byte[] salt) 389 { 390 int[] r; 391 synchronized (digestLock) 392 { 393 r = _crypt(pw, salt); 394 } 395 396 //TODO: crypt always returns same size array? So don't mess 397 // around calculating the number of zeros at the end. 398 399 // The _crypt algorithm pads the 400 // result block with zeros; we need to 401 // copy the array into a byte string, 402 // but without these zeros. 403 int zeroCount = 0; 404 for (int i = r.length - 1; i >= 0; --i) 405 { 406 if (r[i] == 0) 407 { 408 ++zeroCount; 409 } 410 else 411 { 412 // Zeros can only occur at the end 413 // of the block. 414 break; 415 } 416 } 417 byte[] b = new byte[r.length - zeroCount]; 418 419 // Convert to byte 420 for (int i = 0; i < b.length; ++i) 421 { 422 b[i] = (byte) r[i]; 423 } 424 return b; 425 } 426 427 private int[] _crypt(byte[] pw, byte[] salt) 428 { 429 int i, j, c, n; 430 int temp; 431 SubCrypt _c = _crypt; 432 433 for (i = 0; i < 66; i++) 434 _c._ablock[i] = 0; 435 for (i = 0, n = 0; n < pw.length && i < 64; n++) 436 { 437 c = pw[n]; 438 for (j = 0; j < 7; j++, i++) 439 _c._ablock[i] = (c >> (6 - j)) & 01; 440 i++; 441 } 442 443 setkey(_c._ablock); 444 445 for (i = 0; i < 66; i++) 446 _c._ablock[i] = 0; 447 448 for (i = 0; i < 48; i++) 449 _c._E[i] = e[i]; 450 451 for (i = 0; i < 2; i++) 452 { 453 c = salt[i]; 454 _c._iobuf[i] = c; 455 if (c > 'Z') c -= 6; 456 if (c > '9') c -= 7; 457 c -= '.'; 458 for (j = 0; j < 6; j++) 459 { 460 if (((c >> j) & 01) != 0) 461 { 462 temp = _c._E[6 * i + j]; 463 _c._E[6 * i + j] = _c._E[6 * i + j + 24]; 464 _c._E[6 * i + j + 24] = temp; 465 } 466 } 467 } 468 469 for (i = 0; i < 25; i++) 470 encrypt(_c._ablock, 0); 471 472 for (i = 0; i < 11; i++) 473 { 474 c = 0; 475 for (j = 0; j < 6; j++) 476 { 477 c <<= 1; 478 c |= _c._ablock[6 * i + j]; 479 } 480 c += '.'; 481 if (c > '9') c += 7; 482 if (c > 'Z') c += 6; 483 _c._iobuf[i + 2] = c; 484 } 485 _c._iobuf[i + 2] = 0; 486 if (_c._iobuf[1] == 0) _c._iobuf[1] = _c._iobuf[0]; 487 return (_c._iobuf); 488 } 489 } 490