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}