001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.codec.digest;
018
019import java.security.MessageDigest;
020import java.security.NoSuchAlgorithmException;
021import java.util.Arrays;
022import java.util.regex.Matcher;
023import java.util.regex.Pattern;
024
025import org.apache.commons.codec.Charsets;
026
027/**
028 * SHA2-based Unix crypt implementation.
029 * <p>
030 * Based on the C implementation released into the Public Domain by Ulrich Drepper &lt;drepper@redhat.com&gt;
031 * http://www.akkadia.org/drepper/SHA-crypt.txt
032 * <p>
033 * Conversion to Kotlin and from there to Java in 2012 by Christian Hammers &lt;ch@lathspell.de&gt; and likewise put
034 * into the Public Domain.
035 * <p>
036 * This class is immutable and thread-safe.
037 * 
038 * @version $Id: Sha2Crypt.html 891688 2013-12-24 20:49:46Z ggregory $
039 * @since 1.7
040 */
041public class Sha2Crypt {
042
043    /** Default number of rounds if not explicitly specified. */
044    private static final int ROUNDS_DEFAULT = 5000;
045
046    /** Maximum number of rounds. */
047    private static final int ROUNDS_MAX = 999999999;
048
049    /** Minimum number of rounds. */
050    private static final int ROUNDS_MIN = 1000;
051
052    /** Prefix for optional rounds specification. */
053    private static final String ROUNDS_PREFIX = "rounds=";
054
055    /** The number of bytes the final hash value will have (SHA-256 variant). */
056    private static final int SHA256_BLOCKSIZE = 32;
057
058    /** The prefixes that can be used to identify this crypt() variant (SHA-256). */
059    static final String SHA256_PREFIX = "$5$";
060
061    /** The number of bytes the final hash value will have (SHA-512 variant). */
062    private static final int SHA512_BLOCKSIZE = 64;
063
064    /** The prefixes that can be used to identify this crypt() variant (SHA-512). */
065    static final String SHA512_PREFIX = "$6$";
066
067    /** The pattern to match valid salt values. */
068    private static final Pattern SALT_PATTERN = Pattern
069            .compile("^\\$([56])\\$(rounds=(\\d+)\\$)?([\\.\\/a-zA-Z0-9]{1,16}).*");
070
071    /**
072     * Generates a libc crypt() compatible "$5$" hash value with random salt.
073     * <p>
074     * See {@link Crypt#crypt(String, String)} for details.
075     * 
076     * @param keyBytes
077     *            plaintext to hash
078     * @return complete hash value
079     * @throws RuntimeException
080     *             when a {@link java.security.NoSuchAlgorithmException} is caught.
081     */
082    public static String sha256Crypt(final byte[] keyBytes) {
083        return sha256Crypt(keyBytes, null);
084    }
085
086    /**
087     * Generates a libc6 crypt() compatible "$5$" hash value.
088     * <p>
089     * See {@link Crypt#crypt(String, String)} for details.
090     * 
091     * @param keyBytes
092     *            plaintext to hash
093     * @param salt
094     *            real salt value without prefix or "rounds="
095     * @return complete hash value including salt
096     * @throws IllegalArgumentException
097     *             if the salt does not match the allowed pattern
098     * @throws RuntimeException
099     *             when a {@link java.security.NoSuchAlgorithmException} is caught.
100     */
101    public static String sha256Crypt(final byte[] keyBytes, String salt) {
102        if (salt == null) {
103            salt = SHA256_PREFIX + B64.getRandomSalt(8);
104        }
105        return sha2Crypt(keyBytes, salt, SHA256_PREFIX, SHA256_BLOCKSIZE, MessageDigestAlgorithms.SHA_256);
106    }
107
108    /**
109     * Generates a libc6 crypt() compatible "$5$" or "$6$" SHA2 based hash value.
110     * <p>
111     * This is a nearly line by line conversion of the original C function. The numbered comments are from the algorithm
112     * description, the short C-style ones from the original C code and the ones with "Remark" from me.
113     * <p>
114     * See {@link Crypt#crypt(String, String)} for details.
115     * 
116     * @param keyBytes
117     *            plaintext to hash
118     * @param salt
119     *            real salt value without prefix or "rounds="
120     * @param saltPrefix
121     *            either $5$ or $6$
122     * @param blocksize
123     *            a value that differs between $5$ and $6$
124     * @param algorithm
125     *            {@link MessageDigest} algorithm identifier string
126     * @return complete hash value including prefix and salt
127     * @throws IllegalArgumentException
128     *             if the given salt is {@code null} or does not match the allowed pattern
129     * @throws IllegalArgumentException
130     *             when a {@link NoSuchAlgorithmException} is caught
131     * @see MessageDigestAlgorithms
132     */
133    private static String sha2Crypt(final byte[] keyBytes, final String salt, final String saltPrefix,
134            final int blocksize, final String algorithm) {
135
136        final int keyLen = keyBytes.length;
137
138        // Extracts effective salt and the number of rounds from the given salt.
139        int rounds = ROUNDS_DEFAULT;
140        boolean roundsCustom = false;
141        if (salt == null) {
142            throw new IllegalArgumentException("Salt must not be null");
143        }
144
145        final Matcher m = SALT_PATTERN.matcher(salt);
146        if (m == null || !m.find()) {
147            throw new IllegalArgumentException("Invalid salt value: " + salt);
148        }
149        if (m.group(3) != null) {
150            rounds = Integer.parseInt(m.group(3));
151            rounds = Math.max(ROUNDS_MIN, Math.min(ROUNDS_MAX, rounds));
152            roundsCustom = true;
153        }
154        final String saltString = m.group(4);
155        final byte[] saltBytes = saltString.getBytes(Charsets.UTF_8);
156        final int saltLen = saltBytes.length;
157
158        // 1. start digest A
159        // Prepare for the real work.
160        MessageDigest ctx = DigestUtils.getDigest(algorithm);
161
162        // 2. the password string is added to digest A
163        /*
164         * Add the key string.
165         */
166        ctx.update(keyBytes);
167
168        // 3. the salt string is added to digest A. This is just the salt string
169        // itself without the enclosing '$', without the magic salt_prefix $5$ and
170        // $6$ respectively and without the rounds=<N> specification.
171        //
172        // NB: the MD5 algorithm did add the $1$ salt_prefix. This is not deemed
173        // necessary since it is a constant string and does not add security
174        // and /possibly/ allows a plain text attack. Since the rounds=<N>
175        // specification should never be added this would also create an
176        // inconsistency.
177        /*
178         * The last part is the salt string. This must be at most 16 characters and it ends at the first `$' character
179         * (for compatibility with existing implementations).
180         */
181        ctx.update(saltBytes);
182
183        // 4. start digest B
184        /*
185         * Compute alternate sha512 sum with input KEY, SALT, and KEY. The final result will be added to the first
186         * context.
187         */
188        MessageDigest altCtx = DigestUtils.getDigest(algorithm);
189
190        // 5. add the password to digest B
191        /*
192         * Add key.
193         */
194        altCtx.update(keyBytes);
195
196        // 6. add the salt string to digest B
197        /*
198         * Add salt.
199         */
200        altCtx.update(saltBytes);
201
202        // 7. add the password again to digest B
203        /*
204         * Add key again.
205         */
206        altCtx.update(keyBytes);
207
208        // 8. finish digest B
209        /*
210         * Now get result of this (32 bytes) and add it to the other context.
211         */
212        byte[] altResult = altCtx.digest();
213
214        // 9. For each block of 32 or 64 bytes in the password string (excluding
215        // the terminating NUL in the C representation), add digest B to digest A
216        /*
217         * Add for any character in the key one byte of the alternate sum.
218         */
219        /*
220         * (Remark: the C code comment seems wrong for key length > 32!)
221         */
222        int cnt = keyBytes.length;
223        while (cnt > blocksize) {
224            ctx.update(altResult, 0, blocksize);
225            cnt -= blocksize;
226        }
227
228        // 10. For the remaining N bytes of the password string add the first
229        // N bytes of digest B to digest A
230        ctx.update(altResult, 0, cnt);
231
232        // 11. For each bit of the binary representation of the length of the
233        // password string up to and including the highest 1-digit, starting
234        // from to lowest bit position (numeric value 1):
235        //
236        // a) for a 1-digit add digest B to digest A
237        //
238        // b) for a 0-digit add the password string
239        //
240        // NB: this step differs significantly from the MD5 algorithm. It
241        // adds more randomness.
242        /*
243         * Take the binary representation of the length of the key and for every 1 add the alternate sum, for every 0
244         * the key.
245         */
246        cnt = keyBytes.length;
247        while (cnt > 0) {
248            if ((cnt & 1) != 0) {
249                ctx.update(altResult, 0, blocksize);
250            } else {
251                ctx.update(keyBytes);
252            }
253            cnt >>= 1;
254        }
255
256        // 12. finish digest A
257        /*
258         * Create intermediate result.
259         */
260        altResult = ctx.digest();
261
262        // 13. start digest DP
263        /*
264         * Start computation of P byte sequence.
265         */
266        altCtx = DigestUtils.getDigest(algorithm);
267
268        // 14. for every byte in the password (excluding the terminating NUL byte
269        // in the C representation of the string)
270        //
271        // add the password to digest DP
272        /*
273         * For every character in the password add the entire password.
274         */
275        for (int i = 1; i <= keyLen; i++) {
276            altCtx.update(keyBytes);
277        }
278
279        // 15. finish digest DP
280        /*
281         * Finish the digest.
282         */
283        byte[] tempResult = altCtx.digest();
284
285        // 16. produce byte sequence P of the same length as the password where
286        //
287        // a) for each block of 32 or 64 bytes of length of the password string
288        // the entire digest DP is used
289        //
290        // b) for the remaining N (up to 31 or 63) bytes use the first N
291        // bytes of digest DP
292        /*
293         * Create byte sequence P.
294         */
295        final byte[] pBytes = new byte[keyLen];
296        int cp = 0;
297        while (cp < keyLen - blocksize) {
298            System.arraycopy(tempResult, 0, pBytes, cp, blocksize);
299            cp += blocksize;
300        }
301        System.arraycopy(tempResult, 0, pBytes, cp, keyLen - cp);
302
303        // 17. start digest DS
304        /*
305         * Start computation of S byte sequence.
306         */
307        altCtx = DigestUtils.getDigest(algorithm);
308
309        // 18. repeast the following 16+A[0] times, where A[0] represents the first
310        // byte in digest A interpreted as an 8-bit unsigned value
311        //
312        // add the salt to digest DS
313        /*
314         * For every character in the password add the entire password.
315         */
316        for (int i = 1; i <= 16 + (altResult[0] & 0xff); i++) {
317            altCtx.update(saltBytes);
318        }
319
320        // 19. finish digest DS
321        /*
322         * Finish the digest.
323         */
324        tempResult = altCtx.digest();
325
326        // 20. produce byte sequence S of the same length as the salt string where
327        //
328        // a) for each block of 32 or 64 bytes of length of the salt string
329        // the entire digest DS is used
330        //
331        // b) for the remaining N (up to 31 or 63) bytes use the first N
332        // bytes of digest DS
333        /*
334         * Create byte sequence S.
335         */
336        // Remark: The salt is limited to 16 chars, how does this make sense?
337        final byte[] sBytes = new byte[saltLen];
338        cp = 0;
339        while (cp < saltLen - blocksize) {
340            System.arraycopy(tempResult, 0, sBytes, cp, blocksize);
341            cp += blocksize;
342        }
343        System.arraycopy(tempResult, 0, sBytes, cp, saltLen - cp);
344
345        // 21. repeat a loop according to the number specified in the rounds=<N>
346        // specification in the salt (or the default value if none is
347        // present). Each round is numbered, starting with 0 and up to N-1.
348        //
349        // The loop uses a digest as input. In the first round it is the
350        // digest produced in step 12. In the latter steps it is the digest
351        // produced in step 21.h. The following text uses the notation
352        // "digest A/C" to describe this behavior.
353        /*
354         * Repeatedly run the collected hash value through sha512 to burn CPU cycles.
355         */
356        for (int i = 0; i <= rounds - 1; i++) {
357            // a) start digest C
358            /*
359             * New context.
360             */
361            ctx = DigestUtils.getDigest(algorithm);
362
363            // b) for odd round numbers add the byte sequense P to digest C
364            // c) for even round numbers add digest A/C
365            /*
366             * Add key or last result.
367             */
368            if ((i & 1) != 0) {
369                ctx.update(pBytes, 0, keyLen);
370            } else {
371                ctx.update(altResult, 0, blocksize);
372            }
373
374            // d) for all round numbers not divisible by 3 add the byte sequence S
375            /*
376             * Add salt for numbers not divisible by 3.
377             */
378            if (i % 3 != 0) {
379                ctx.update(sBytes, 0, saltLen);
380            }
381
382            // e) for all round numbers not divisible by 7 add the byte sequence P
383            /*
384             * Add key for numbers not divisible by 7.
385             */
386            if (i % 7 != 0) {
387                ctx.update(pBytes, 0, keyLen);
388            }
389
390            // f) for odd round numbers add digest A/C
391            // g) for even round numbers add the byte sequence P
392            /*
393             * Add key or last result.
394             */
395            if ((i & 1) != 0) {
396                ctx.update(altResult, 0, blocksize);
397            } else {
398                ctx.update(pBytes, 0, keyLen);
399            }
400
401            // h) finish digest C.
402            /*
403             * Create intermediate result.
404             */
405            altResult = ctx.digest();
406        }
407
408        // 22. Produce the output string. This is an ASCII string of the maximum
409        // size specified above, consisting of multiple pieces:
410        //
411        // a) the salt salt_prefix, $5$ or $6$ respectively
412        //
413        // b) the rounds=<N> specification, if one was present in the input
414        // salt string. A trailing '$' is added in this case to separate
415        // the rounds specification from the following text.
416        //
417        // c) the salt string truncated to 16 characters
418        //
419        // d) a '$' character
420        /*
421         * Now we can construct the result string. It consists of three parts.
422         */
423        final StringBuilder buffer = new StringBuilder(saltPrefix);
424        if (roundsCustom) {
425            buffer.append(ROUNDS_PREFIX);
426            buffer.append(rounds);
427            buffer.append("$");
428        }
429        buffer.append(saltString);
430        buffer.append("$");
431
432        // e) the base-64 encoded final C digest. The encoding used is as
433        // follows:
434        // [...]
435        //
436        // Each group of three bytes from the digest produces four
437        // characters as output:
438        //
439        // 1. character: the six low bits of the first byte
440        // 2. character: the two high bits of the first byte and the
441        // four low bytes from the second byte
442        // 3. character: the four high bytes from the second byte and
443        // the two low bits from the third byte
444        // 4. character: the six high bits from the third byte
445        //
446        // The groups of three bytes are as follows (in this sequence).
447        // These are the indices into the byte array containing the
448        // digest, starting with index 0. For the last group there are
449        // not enough bytes left in the digest and the value zero is used
450        // in its place. This group also produces only three or two
451        // characters as output for SHA-512 and SHA-512 respectively.
452
453        // This was just a safeguard in the C implementation:
454        // int buflen = salt_prefix.length() - 1 + ROUNDS_PREFIX.length() + 9 + 1 + salt_string.length() + 1 + 86 + 1;
455
456        if (blocksize == 32) {
457            B64.b64from24bit(altResult[0], altResult[10], altResult[20], 4, buffer);
458            B64.b64from24bit(altResult[21], altResult[1], altResult[11], 4, buffer);
459            B64.b64from24bit(altResult[12], altResult[22], altResult[2], 4, buffer);
460            B64.b64from24bit(altResult[3], altResult[13], altResult[23], 4, buffer);
461            B64.b64from24bit(altResult[24], altResult[4], altResult[14], 4, buffer);
462            B64.b64from24bit(altResult[15], altResult[25], altResult[5], 4, buffer);
463            B64.b64from24bit(altResult[6], altResult[16], altResult[26], 4, buffer);
464            B64.b64from24bit(altResult[27], altResult[7], altResult[17], 4, buffer);
465            B64.b64from24bit(altResult[18], altResult[28], altResult[8], 4, buffer);
466            B64.b64from24bit(altResult[9], altResult[19], altResult[29], 4, buffer);
467            B64.b64from24bit((byte) 0, altResult[31], altResult[30], 3, buffer);
468        } else {
469            B64.b64from24bit(altResult[0], altResult[21], altResult[42], 4, buffer);
470            B64.b64from24bit(altResult[22], altResult[43], altResult[1], 4, buffer);
471            B64.b64from24bit(altResult[44], altResult[2], altResult[23], 4, buffer);
472            B64.b64from24bit(altResult[3], altResult[24], altResult[45], 4, buffer);
473            B64.b64from24bit(altResult[25], altResult[46], altResult[4], 4, buffer);
474            B64.b64from24bit(altResult[47], altResult[5], altResult[26], 4, buffer);
475            B64.b64from24bit(altResult[6], altResult[27], altResult[48], 4, buffer);
476            B64.b64from24bit(altResult[28], altResult[49], altResult[7], 4, buffer);
477            B64.b64from24bit(altResult[50], altResult[8], altResult[29], 4, buffer);
478            B64.b64from24bit(altResult[9], altResult[30], altResult[51], 4, buffer);
479            B64.b64from24bit(altResult[31], altResult[52], altResult[10], 4, buffer);
480            B64.b64from24bit(altResult[53], altResult[11], altResult[32], 4, buffer);
481            B64.b64from24bit(altResult[12], altResult[33], altResult[54], 4, buffer);
482            B64.b64from24bit(altResult[34], altResult[55], altResult[13], 4, buffer);
483            B64.b64from24bit(altResult[56], altResult[14], altResult[35], 4, buffer);
484            B64.b64from24bit(altResult[15], altResult[36], altResult[57], 4, buffer);
485            B64.b64from24bit(altResult[37], altResult[58], altResult[16], 4, buffer);
486            B64.b64from24bit(altResult[59], altResult[17], altResult[38], 4, buffer);
487            B64.b64from24bit(altResult[18], altResult[39], altResult[60], 4, buffer);
488            B64.b64from24bit(altResult[40], altResult[61], altResult[19], 4, buffer);
489            B64.b64from24bit(altResult[62], altResult[20], altResult[41], 4, buffer);
490            B64.b64from24bit((byte) 0, (byte) 0, altResult[63], 2, buffer);
491        }
492
493        /*
494         * Clear the buffer for the intermediate result so that people attaching to processes or reading core dumps
495         * cannot get any information.
496         */
497        // Is there a better way to do this with the JVM?
498        Arrays.fill(tempResult, (byte) 0);
499        Arrays.fill(pBytes, (byte) 0);
500        Arrays.fill(sBytes, (byte) 0);
501        ctx.reset();
502        altCtx.reset();
503        Arrays.fill(keyBytes, (byte) 0);
504        Arrays.fill(saltBytes, (byte) 0);
505
506        return buffer.toString();
507    }
508
509    /**
510     * Generates a libc crypt() compatible "$6$" hash value with random salt.
511     * <p>
512     * See {@link Crypt#crypt(String, String)} for details.
513     * 
514     * @param keyBytes
515     *            plaintext to hash
516     * @return complete hash value
517     * @throws RuntimeException
518     *             when a {@link java.security.NoSuchAlgorithmException} is caught.
519     */
520    public static String sha512Crypt(final byte[] keyBytes) {
521        return sha512Crypt(keyBytes, null);
522    }
523
524    /**
525     * Generates a libc6 crypt() compatible "$6$" hash value.
526     * <p>
527     * See {@link Crypt#crypt(String, String)} for details.
528     * 
529     * @param keyBytes
530     *            plaintext to hash
531     * @param salt
532     *            real salt value without prefix or "rounds="
533     * @return complete hash value including salt
534     * @throws IllegalArgumentException
535     *             if the salt does not match the allowed pattern
536     * @throws RuntimeException
537     *             when a {@link java.security.NoSuchAlgorithmException} is caught.
538     */
539    public static String sha512Crypt(final byte[] keyBytes, String salt) {
540        if (salt == null) {
541            salt = SHA512_PREFIX + B64.getRandomSalt(8);
542        }
543        return sha2Crypt(keyBytes, salt, SHA512_PREFIX, SHA512_BLOCKSIZE, MessageDigestAlgorithms.SHA_512);
544    }
545}