    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.java 1619948 2014-08-22 22:53:55Z 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</code> 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}