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