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