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