ldap/model/src/main/java/org/apache/directory/api/ldap/model/password/PasswordUtil.java

/*
 *   or more contributor license agreements.  See the NOTICE file
 *   Licensed to the Apache Software Foundation (ASF) under one
 *   distributed with this work for additional information
 *   regarding copyright ownership.  The ASF licenses this file
 *   to you under the Apache License, Version 2.0 (the
 *   "License"); you may not use this file except in compliance
 *   with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *   Unless required by applicable law or agreed to in writing,
 *   software distributed under the License is distributed on an
 *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *   KIND, either express or implied.  See the License for the
 *   specific language governing permissions and limitations
 *   under the License.
 *
 */

package org.apache.directory.api.ldap.model.password;


import java.security.Key;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.security.spec.KeySpec;
import java.util.Arrays;
import java.util.Date;

import javax.crypto.SecretKeyFactory;
import javax.crypto.spec.PBEKeySpec;

import org.apache.commons.codec.digest.Crypt;
import org.apache.directory.api.i18n.I18n;
import org.apache.directory.api.ldap.model.constants.LdapSecurityConstants;
import org.apache.directory.api.util.Base64;
import org.apache.directory.api.util.DateUtils;
import org.apache.directory.api.util.TimeProvider;
import org.apache.directory.api.util.Strings;

/**
 * A utility class containing methods related to processing passwords.
 *
 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
 */
public final class PasswordUtil
{

    /** The SHA1 hash length */
    public static final int SHA1_LENGTH = 20;

    /** The SHA256 hash length */
    public static final int SHA256_LENGTH = 32;

    /** The SHA384 hash length */
    public static final int SHA384_LENGTH = 48;

    /** The SHA512 hash length */
    public static final int SHA512_LENGTH = 64;

    /** The MD5 hash length */
    public static final int MD5_LENGTH = 16;

    /** The PKCS5S2 hash length */
    public static final int PKCS5S2_LENGTH = 32;

    /** The CRYPT (DES) hash length */
    public static final int CRYPT_LENGTH = 11;

    /** The CRYPT (MD5) hash length */
    public static final int CRYPT_MD5_LENGTH = 22;

    /** The CRYPT (SHA-256) hash length */
    public static final int CRYPT_SHA256_LENGTH = 43;

    /** The CRYPT (SHA-512) hash length */
    public static final int CRYPT_SHA512_LENGTH = 86;

    /** The CRYPT (BCrypt) hash length */
    public static final int CRYPT_BCRYPT_LENGTH = 31;

    private static final byte[] CRYPT_SALT_CHARS = Strings
        .getBytesUtf8( "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" );

    private PasswordUtil()
    {
    }


    /**
     * Get the algorithm from the stored password. 
     * It can be found on the beginning of the stored password, between 
     * curly brackets.
     * @param credentials the credentials of the user
     * @return the name of the algorithm to use
     */
    public static LdapSecurityConstants findAlgorithm( byte[] credentials )
    {
        if ( ( credentials == null ) || ( credentials.length == 0 ) )
        {
            return null;
        }

        if ( credentials[0] == '{' )
        {
            // get the algorithm
            int pos = 1;

            while ( pos < credentials.length )
            {
                if ( credentials[pos] == '}' )
                {
                    break;
                }

                pos++;
            }

            if ( pos < credentials.length )
            {
                if ( pos == 1 )
                {
                    // We don't have an algorithm : return the credentials as is
                    return null;
                }

                String algorithm = Strings.toLowerCaseAscii( Strings.utf8ToString( credentials, 1, pos - 1 ) );

                // support for crypt additional encryption algorithms (e.g. {crypt}$1$salt$ez2vlPGdaLYkJam5pWs/Y1)
                if ( credentials.length > pos + 3 && credentials[pos + 1] == '$'
                    && Character.isDigit( credentials[pos + 2] ) )
                {
                    if ( credentials[pos + 3] == '$' )
                    {
                        algorithm += Strings.utf8ToString( credentials, pos + 1, 3 );
                    }
                    else if ( credentials.length > pos + 4 && credentials[pos + 4] == '$' )
                    {
                        algorithm += Strings.utf8ToString( credentials, pos + 1, 4 );
                    }
                }

                return LdapSecurityConstants.getAlgorithm( algorithm );
            }
            else
            {
                // We don't have an algorithm
                return null;
            }
        }
        else
        {
            // No '{algo}' part
            return null;
        }
    }


    /**
     * @see #createStoragePassword(byte[], LdapSecurityConstants)
     * 
     * @param credentials The password
     * @param algorithm The algorithm to use
     * @return The resulting byte[] containing the paswword
     */
    public static byte[] createStoragePassword( String credentials, LdapSecurityConstants algorithm )
    {
        return createStoragePassword( Strings.getBytesUtf8( credentials ), algorithm );
    }


    /**
     * create a hashed password in a format that can be stored in the server.
     * If the specified algorithm requires a salt then a random salt of 8 byte size is used
     *  
     * @param credentials the plain text password
     * @param algorithm the hashing algorithm to be applied
     * @return the password after hashing with the given algorithm 
     */
    public static byte[] createStoragePassword( byte[] credentials, LdapSecurityConstants algorithm )
    {
        // check plain text password
        if ( algorithm == null )
        {
            return credentials;
        }

        byte[] salt;

        switch ( algorithm )
        {
            case HASH_METHOD_SSHA:
            case HASH_METHOD_SSHA256:
            case HASH_METHOD_SSHA384:
            case HASH_METHOD_SSHA512:
            case HASH_METHOD_SMD5:
                // we use 8 byte salt always except for "crypt" which needs 2 byte salt
                salt = new byte[8];
                new SecureRandom().nextBytes( salt );
                break;

            case HASH_METHOD_PKCS5S2:
                // we use 16 byte salt for PKCS5S2
                salt = new byte[16];
                new SecureRandom().nextBytes( salt );
                break;

            case HASH_METHOD_CRYPT:
                salt = generateCryptSalt( 2 );
                break;

            case HASH_METHOD_CRYPT_MD5:
            case HASH_METHOD_CRYPT_SHA256:
            case HASH_METHOD_CRYPT_SHA512:
                salt = generateCryptSalt( 8 );
                break;
                
            case HASH_METHOD_CRYPT_BCRYPT:
                salt = Strings.getBytesUtf8( BCrypt.genSalt() );
                break;

            default:
                salt = null;
        }

        byte[] hashedPassword = encryptPassword( credentials, algorithm, salt );
        StringBuilder sb = new StringBuilder();

        sb.append( '{' ).append( Strings.upperCase( algorithm.getPrefix() ) ).append( '}' );

        if ( algorithm == LdapSecurityConstants.HASH_METHOD_CRYPT
            || algorithm == LdapSecurityConstants.HASH_METHOD_CRYPT_BCRYPT )
        {
            sb.append( Strings.utf8ToString( salt ) );
            sb.append( Strings.utf8ToString( hashedPassword ) );
        }
        else if ( algorithm == LdapSecurityConstants.HASH_METHOD_CRYPT_MD5
            || algorithm == LdapSecurityConstants.HASH_METHOD_CRYPT_SHA256
            || algorithm == LdapSecurityConstants.HASH_METHOD_CRYPT_SHA512 )
        {
            sb.append( algorithm.getSubPrefix() );
            sb.append( Strings.utf8ToString( salt ) );
            sb.append( '$' );
            sb.append( Strings.utf8ToString( hashedPassword ) );
        }
        else if ( salt != null )
        {
            byte[] hashedPasswordWithSaltBytes = new byte[hashedPassword.length + salt.length];

            if ( algorithm == LdapSecurityConstants.HASH_METHOD_PKCS5S2 )
            {
                merge( hashedPasswordWithSaltBytes, salt, hashedPassword );
            }
            else
            {
                merge( hashedPasswordWithSaltBytes, hashedPassword, salt );
            }

            sb.append( String.valueOf( Base64.encode( hashedPasswordWithSaltBytes ) ) );
        }
        else
        {
            sb.append( String.valueOf( Base64.encode( hashedPassword ) ) );
        }

        return Strings.getBytesUtf8( sb.toString() );
    }


    /**
     * 
     * Compare the credentials.
     * We have at least 6 algorithms to encrypt the password :
     * <ul>
     * <li>- SHA</li>
     * <li>- SSHA (salted SHA)</li>
     * <li>- SHA-2(256, 384 and 512 and their salted versions)</li>
     * <li>- MD5</li>
     * <li>- SMD5 (slated MD5)</li>
     * <li>- PKCS5S2 (PBKDF2)</li>
     * <li>- crypt (unix crypt)</li>
     * <li>- plain text, ie no encryption.</li>
     * </ul>
     * <p>
     *  If we get an encrypted password, it is prefixed by the used algorithm, between
     *  brackets : {SSHA}password ...
     *  </p>
     *  If the password is using SSHA, SMD5 or crypt, some 'salt' is added to the password :
     *  <ul>
     *  <li>- length(password) - 20, starting at 21st position for SSHA</li>
     *  <li>- length(password) - 16, starting at 16th position for SMD5</li>
     *  <li>- length(password) - 2, starting at 3rd position for crypt</li>
     *  </ul>
     *  <p>
     *  For (S)SHA, SHA-256 and (S)MD5, we have to transform the password from Base64 encoded text
     *  to a byte[] before comparing the password with the stored one.
     *  </p>
     *  <p>
     *  For PKCS5S2 the salt is stored in the beginning of the password
     *  </p>
     *  <p>
     *  For crypt, we only have to remove the salt.
     *  </p>
     *  <p>
     *  At the end, we use the digest() method for (S)SHA and (S)MD5, the crypt() method for
     *  the CRYPT algorithm and a straight comparison for PLAIN TEXT passwords.
     *  </p>
     *  <p>
     *  The stored password is always using the unsalted form, and is stored as a bytes array.
     *  </p>
     *
     * @param receivedCredentials the credentials provided by user
     * @param storedCredentials the credentials stored in the server
     * @return true if they are equal, false otherwise
     */
    public static boolean compareCredentials( byte[] receivedCredentials, byte[] storedCredentials )
    {
        LdapSecurityConstants algorithm = findAlgorithm( storedCredentials );

        if ( algorithm != null )
        {
            // Let's get the encrypted part of the stored password
            // We should just keep the password, excluding the algorithm
            // and the salt, if any.
            // But we should also get the algorithm and salt to
            // be able to encrypt the submitted user password in the next step
            PasswordDetails passwordDetails = PasswordUtil.splitCredentials( storedCredentials );

            // Reuse the saltedPassword information to construct the encrypted
            // password given by the user.
            byte[] userPassword = PasswordUtil.encryptPassword( receivedCredentials, passwordDetails.getAlgorithm(),
                passwordDetails.getSalt() );

            return compareBytes( userPassword, passwordDetails.getPassword() );
        }
        else
        {
            return compareBytes( receivedCredentials, storedCredentials );
        }
    }
    
    
    /**
     * Compare two byte[] in a constant time. This is necessary because using an Array.equals() is
     * not Timing attack safe ([1], [2] and [3]), a breach that can be exploited to break some hashes.
     * 
     *  [1] https://en.wikipedia.org/wiki/Timing_attack
     *  [2] http://rdist.root.org/2009/05/28/timing-attack-in-google-keyczar-library/
     *  [3] https://cryptocoding.net/index.php/Coding_rules
     *  
     * @param provided The provided password
     * @param stored The stored password
     * @return <tt>true</tt> if the compared passwords are equal
     */
    private static boolean compareBytes( byte[] provided, byte[] stored )
    {
        if ( stored == null )
        {
            return provided == null;
        }
        else if ( provided == null )
        {
            return false;
        }
        
        // Now, compare the two passwords, using a constant time method
        if ( stored.length != provided.length )
        {
            return false;
        }
        
        // loop on *every* byte in both passwords, and at the end, if one char at least is different, return false.
        int result = 0;
        
        for ( int i = 0; i < stored.length; i++ )
        {
            // If both bytes are equal, xor will be == 0, otherwise it will be != 0 and so will result.
            result |= ( stored[i] ^ provided[i] );
        }
        
        return result == 0;
    }


    /**
     * encrypts the given credentials based on the algorithm name and optional salt
     *
     * @param credentials the credentials to be encrypted
     * @param algorithm the algorithm to be used for encrypting the credentials
     * @param salt value to be used as salt (optional)
     * @return the encrypted credentials
     */
    private static byte[] encryptPassword( byte[] credentials, LdapSecurityConstants algorithm, byte[] salt )
    {
        switch ( algorithm )
        {
            case HASH_METHOD_SHA:
            case HASH_METHOD_SSHA:
                return digest( LdapSecurityConstants.HASH_METHOD_SHA, credentials, salt );

            case HASH_METHOD_SHA256:
            case HASH_METHOD_SSHA256:
                return digest( LdapSecurityConstants.HASH_METHOD_SHA256, credentials, salt );

            case HASH_METHOD_SHA384:
            case HASH_METHOD_SSHA384:
                return digest( LdapSecurityConstants.HASH_METHOD_SHA384, credentials, salt );

            case HASH_METHOD_SHA512:
            case HASH_METHOD_SSHA512:
                return digest( LdapSecurityConstants.HASH_METHOD_SHA512, credentials, salt );

            case HASH_METHOD_MD5:
            case HASH_METHOD_SMD5:
                return digest( LdapSecurityConstants.HASH_METHOD_MD5, credentials, salt );

            case HASH_METHOD_CRYPT:
                String saltWithCrypted = Crypt.crypt( Strings.utf8ToString( credentials ), Strings
                    .utf8ToString( salt ) );
                String crypted = saltWithCrypted.substring( 2 );
                return Strings.getBytesUtf8( crypted );

            case HASH_METHOD_CRYPT_MD5:
            case HASH_METHOD_CRYPT_SHA256:
            case HASH_METHOD_CRYPT_SHA512:
                String saltWithCrypted2 = Crypt.crypt( Strings.utf8ToString( credentials ),
                    algorithm.getSubPrefix() + Strings.utf8ToString( salt ) );
                String crypted2 = saltWithCrypted2.substring( saltWithCrypted2.lastIndexOf( '$' ) + 1 );
                return Strings.getBytesUtf8( crypted2 );

            case HASH_METHOD_CRYPT_BCRYPT:
                String crypted3 = BCrypt.hashPw( Strings.utf8ToString( credentials ), Strings.utf8ToString( salt ) );
                return Strings.getBytesUtf8( crypted3.substring( crypted3.length() - 31 ) );
                
            case HASH_METHOD_PKCS5S2:
                return generatePbkdf2Hash( credentials, algorithm, salt );

            default:
                return credentials;
        }
    }


    /**
     * Compute the hashed password given an algorithm, the credentials and 
     * an optional salt.
     *
     * @param algorithm the algorithm to use
     * @param password the credentials
     * @param salt the optional salt
     * @return the digested credentials
     */
    private static byte[] digest( LdapSecurityConstants algorithm, byte[] password, byte[] salt )
    {
        MessageDigest digest;

        try
        {
            digest = MessageDigest.getInstance( algorithm.getAlgorithm() );
        }
        catch ( NoSuchAlgorithmException e1 )
        {
            return null;
        }

        if ( salt != null )
        {
            digest.update( password );
            digest.update( salt );
            return digest.digest();
        }
        else
        {
            return digest.digest( password );
        }
    }


    /**
     * Decompose the stored password in an algorithm, an eventual salt
     * and the password itself.
     *
     * If the algorithm is SHA, SSHA, MD5 or SMD5, the part following the algorithm
     * is base64 encoded
     *
     * @param credentials The byte[] containing the credentials to split
     * @return The password
     */
    public static PasswordDetails splitCredentials( byte[] credentials )
    {
        LdapSecurityConstants algorithm = findAlgorithm( credentials );

        // check plain text password
        if ( algorithm == null )
        {
            return new PasswordDetails( null, null, credentials );
        }

        int algoLength = algorithm.getPrefix().length() + 2;
        byte[] password;

        switch ( algorithm )
        {
            case HASH_METHOD_MD5:
            case HASH_METHOD_SMD5:
                return getCredentials( credentials, algoLength, MD5_LENGTH, algorithm );

            case HASH_METHOD_SHA:
            case HASH_METHOD_SSHA:
                return getCredentials( credentials, algoLength, SHA1_LENGTH, algorithm );

            case HASH_METHOD_SHA256:
            case HASH_METHOD_SSHA256:
                return getCredentials( credentials, algoLength, SHA256_LENGTH, algorithm );

            case HASH_METHOD_SHA384:
            case HASH_METHOD_SSHA384:
                return getCredentials( credentials, algoLength, SHA384_LENGTH, algorithm );

            case HASH_METHOD_SHA512:
            case HASH_METHOD_SSHA512:
                return getCredentials( credentials, algoLength, SHA512_LENGTH, algorithm );

            case HASH_METHOD_PKCS5S2:
                return getPbkdf2Credentials( credentials, algoLength, algorithm );

            case HASH_METHOD_CRYPT:
                // The password is associated with a salt. Decompose it
                // in two parts, no decoding required.
                // The salt comes first, not like for SSHA and SMD5, and is 2 bytes long
                // The algorithm, salt, and password will be stored into the PasswordDetails structure.
                byte[] salt = new byte[2];
                password = new byte[credentials.length - salt.length - algoLength];
                split( credentials, algoLength, salt, password );
                return new PasswordDetails( algorithm, salt, password );

            case HASH_METHOD_CRYPT_BCRYPT:
                    salt = Arrays.copyOfRange( credentials, algoLength, credentials.length - 31 );
                    password = Arrays.copyOfRange( credentials, credentials.length - 31, credentials.length );
                    
                    return new PasswordDetails( algorithm, salt, password );

            case HASH_METHOD_CRYPT_MD5:
            case HASH_METHOD_CRYPT_SHA256:
            case HASH_METHOD_CRYPT_SHA512:
                // skip $x$
                algoLength = algoLength + 3;
                return getCryptCredentials( credentials, algoLength, algorithm );

            default:
                // unknown method
                throw new IllegalArgumentException( I18n.err( I18n.ERR_13010_UNKNOWN_HASH_ALGO, algorithm ) );
        }
    }


    /**
     * Compute the credentials
     * 
     * @param credentials the credentials
     * @param algoLength The algorithm length
     * @param hashLen The hash length
     * @param algorithm the algorithm to use
     * @return The split password string, containing the credentials, the salt and the password
     */
    private static PasswordDetails getCredentials( byte[] credentials, int algoLength, int hashLen,
        LdapSecurityConstants algorithm )
    {
        // The password is associated with a salt. Decompose it
        // in two parts, after having decoded the password.
        // The salt is at the end of the credentials.
        // The algorithm, salt, and password will be stored into the PasswordDetails structure.
        byte[] passwordAndSalt = Base64
            .decode( Strings.utf8ToString( credentials, algoLength, credentials.length - algoLength ).toCharArray() );

        int saltLength = passwordAndSalt.length - hashLen;
        byte[] salt = saltLength == 0 ? null : new byte[saltLength];
        byte[] password = new byte[hashLen];
        split( passwordAndSalt, 0, password, salt );

        return new PasswordDetails( algorithm, salt, password );
    }


    private static void split( byte[] all, int offset, byte[] left, byte[] right )
    {
        System.arraycopy( all, offset, left, 0, left.length );
        if ( right != null )
        {
            System.arraycopy( all, offset + left.length, right, 0, right.length );
        }
    }


    private static void merge( byte[] all, byte[] left, byte[] right )
    {
        System.arraycopy( left, 0, all, 0, left.length );
        System.arraycopy( right, 0, all, left.length, right.length );
    }


    /**
     * checks if the given password's change time is older than the max age 
     *
     * @param pwdChangedZtime time when the password was last changed
     * @param pwdMaxAgeSec the max age value in seconds
     * @param timeProvider The TimeProvider instance to use
     * @return true if expired, false otherwise
     */
    public static boolean isPwdExpired( String pwdChangedZtime, int pwdMaxAgeSec, TimeProvider timeProvider )
    {
        Date pwdChangeDate = DateUtils.getDate( pwdChangedZtime );

        //DIRSERVER-1735
        long time = pwdMaxAgeSec * 1000L;
        time += pwdChangeDate.getTime();

        Date expiryDate = DateUtils.getDate( DateUtils.getGeneralizedTime( time ) );
        Date now = DateUtils.getDate( DateUtils.getGeneralizedTime( timeProvider ) );

        boolean expired = false;

        if ( expiryDate.equals( now ) || expiryDate.before( now ) )
        {
            expired = true;
        }

        return expired;
    }


    /**
     * generates a hash based on the <a href="http://en.wikipedia.org/wiki/PBKDF2">PKCS5S2 spec</a>
     * 
     * Note: this has been implemented to generate hashes compatible with what JIRA generates.
     *       See the <a href="http://pythonhosted.org/passlib/lib/passlib.hash.atlassian_pbkdf2_sha1.html">JIRA's passlib</a>
     *       
     * @param credentials the credentials
     * @param algorithm the algorithm to use
     * @param salt the optional salt
     * @return the digested credentials
     */
    private static byte[] generatePbkdf2Hash( byte[] credentials, LdapSecurityConstants algorithm, byte[] salt )
    {
        try
        {
            SecretKeyFactory sk = SecretKeyFactory.getInstance( algorithm.getAlgorithm() );
            char[] password = Strings.utf8ToString( credentials ).toCharArray();
            KeySpec keySpec = new PBEKeySpec( password, salt, 10000, PKCS5S2_LENGTH * 8 );
            Key key = sk.generateSecret( keySpec );
            return key.getEncoded();
        }
        catch ( Exception e )
        {
            throw new RuntimeException( e );
        }
    }


    /**
     * Gets the credentials from a PKCS5S2 hash.
     * The salt for PKCS5S2 hash is prepended to the password
     * 
     * @param credentials The password
     * @param algoLength The length of the algorithm part
     * @param algorithm The algorithm in use
     * @return The split credentials, containing the algorithm, the salt and the password 
     */
    private static PasswordDetails getPbkdf2Credentials( byte[] credentials, int algoLength, LdapSecurityConstants algorithm )
    {
        // The password is associated with a salt. Decompose it
        // in two parts, after having decoded the password.
        // The salt is at the *beginning* of the credentials, and is 16 bytes long
        // The algorithm, salt, and password will be stored into the PasswordDetails structure.
        byte[] passwordAndSalt = Base64
            .decode( Strings.utf8ToString( credentials, algoLength, credentials.length - algoLength ).toCharArray() );

        int saltLength = passwordAndSalt.length - PKCS5S2_LENGTH;
        byte[] salt = new byte[saltLength];
        byte[] password = new byte[PKCS5S2_LENGTH];

        split( passwordAndSalt, 0, salt, password );

        return new PasswordDetails( algorithm, salt, password );
    }


    private static byte[] generateCryptSalt( int length )
    {
        byte[] salt = new byte[length];
        SecureRandom sr = new SecureRandom();
        for ( int i = 0; i < salt.length; i++ )
        {
            salt[i] = CRYPT_SALT_CHARS[sr.nextInt( CRYPT_SALT_CHARS.length )];
        }
        
        return salt;
    }


    private static PasswordDetails getCryptCredentials( byte[] credentials, int algoLength,
        LdapSecurityConstants algorithm )
    {
        // The password is associated with a salt. Decompose it
        // in two parts, no decoding required.
        // The salt length is dynamic, between the 2nd and 3rd '$'.
        // The algorithm, salt, and password will be stored into the PasswordDetails structure.

        // skip {crypt}$x$
        int pos = algoLength;
        while ( pos < credentials.length )
        {
            if ( credentials[pos] == '$' )
            {
                break;
            }

            pos++;
        }

        byte[] salt = Arrays.copyOfRange( credentials, algoLength, pos );
        byte[] password = Arrays.copyOfRange( credentials, pos + 1, credentials.length );

        return new PasswordDetails( algorithm, salt, password );
    }

}