Implementation of SHA512-crypt vs MD5-crypt

If you have a new installation, you’re probably using SHA512-based passwords instead of the older MD5-based passwords described in detail in the previous post, which I’ll assume you’ve read. sha512-crypt is very similar to md5-crypt, but with some interesting differences.

Since the implementation of sha512 is really less interesting than the comparison with md5-crypt, I’ll describe it by striking out the relevant parts of the md5-crypt description and writing in what sha512-crypt does instead.

Like md5-crypt, it can be divided into three phases. Initialization, loop, and finalization.

1. Generate a simple md5 sha512 hash based on the salt and password
2. Loop 1000 5000 times, calculating a new sha512 hash based on the previous hash concatenated with alternatingly the hash of the password and the salt. Additionally, sha512-crypt allows you to specify a custom number of rounds, from 1000 to 999999999
3. Use a special base64 encoding on the final hash to create the password hash string

The main differences are the higher number of rounds, which can be user selected for better (or worse) security, the use of the hashed password and salt in each round, rather than the unhashed ones, and a few tweaks of the initialization step.

Here’s the real sha512-crypt initialization.

1. Let “password” be the user’s ascii password, “salt” the ascii salt (truncated to 8 16chars) , and “magic” the string “$1$”
2. Start by computing the Alternate sum, sha512(password + salt + password)
3. Compute the Intermediate₀ sum by hashing the concatenation of the following strings:
   1. Password
   2. Magic
   3. Salt
   4. length(password) bytes of the Alternate sum, repeated as necessary
   5. For each bit in length(password), from low to high and stopping after the most significant set bit
      • If the bit is set, append a NUL byte the Alternate sum
      • If it’s unset, append the first byte of the password
4. New: Let S_factor be 16 + the first byte of Intermediate₀
5. New: Compute the S bytes, length(salt) bytes of sha512(salt, concatenated S_factor times).
6. New: Compute the P bytes, length(password) bytes of sha512(password), repeated as necessary

Step 3.5 — which was very strange in md5-crypt — now makes a little more sense. We also calculated the S bytes and P bytes, which from here on will be used just like salt and password was in md5-crypt.

From this point on, the calculations will only involve the password P bytes, salt S bytes, and the Intermediate₀ sum. Now we loop 5000 times (by default), to stretch the algorithm.

• For i = 0 to 4999 (inclusive), compute Intermediate_i+1 by concatenating and hashing the following:
  1. If i is even, Intermediate_i
  2. If i is odd, password P bytes
  3. If i is not divisible by 3, salt S bytes
  4. If i is not divisible by 7, password P bytes
  5. If i is even, password P bytes
  6. If i is odd, Intermediate_i
  At this point you don’t need Intermediate_i anymore.

You will now have ended up with Intermediate₅₀₀₀. Let’s call this the Final sum. Since sha512 is 512bit, this is 64 bytes long.

The bytes will be rearranged, and then encoded as 86 ascii characters using the same base64 encoding as md5-crypt.

1. Output the magic, “$6$”
2. New: If using a custom number of rounds, output “rounds=12345$”
3. Output the salt
4. Output a “$” to separate the salt from the encrypted section
5. Pick out the 64 bytes in this order: 63 62 20 41 40 61 19 18 39 60 59 17 38 37 58 16 15 36 57 56 14 35 34 55 13 12 33 54 53 11 32 31 52 10 9 30 51 50 8 29 28 49 7 6 27 48 47 5 26 25 46 4 3 24 45 44 2 23 22 43 1 0 21 42
   • For each group of 6 bits (there’s 86 groups), starting with the least significant
     • Output the corresponding base64 character with this index

And yes, I do have a shell script for this as well: sha512crypt. This one takes about a minute to generate a hash, due to the higher number of rounds. However, it doesn’t support custom rounds.

I hope these two posts have provided an interesting look at two exceedingly common, but often overlooked, algorithms!

 sha512crypt

#!/bin/bash

# sha512-crypt
# sha512-crypt for GNU and Bash

b64="./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

stringToNumber() { 
    expression=0
    for((i=0; i<${#1}; i++))
    do
        expression=$(printf '(%s)*256+%d' "$expression" "'${1:$i:1}")
    done
    bc <<< "$expression"
}

# Turn some string into a \xd4\x1d hex string
stringToHex() { 
    for((i=0; i<${#1}; i++))
    do
        printf '\\x%x' "'${1:i:1}"
    done
}

# Turn stdin into a \xd4\x1d style sha512 hash
sha512hex() { 
    sum=$(sha512sum) 
    read sum rest <<< "$sum" # remove trailing dash
    hex=$(sed 's/../\\x&/g' <<< "$sum")
    echo "$hex"
}

# Turn an integer into a crypt base64 string with n characters
intToBase64() { 
    number=$1
    n=$2
    for((j=0; j>=1)) 
        do
            if (( i & 1 ))
            then
                printf "$alternate"
            else 
                printf "$password" 
            fi
        done

    } | sha512hex
    )
    firstByte=$(hexToInt $(getBytes "$intermediate" 0))

    p_bytes=$(for((i=0; i<$passwordLength; i++)); do printf "$password"; done | sha512hex | head -c $((passwordLength*4)) )
    s_bytes=$(for((i=0; i<16+${firstByte}; i++)); do printf "$salt"; done  | sha512hex | head -c $((saltLength*4)) )


    for((i=0; i<5000; i++))
    do
        intermediate=$({
            (( i & 1 )) && printf "$p_bytes" || printf "$intermediate"
            (( i % 3 )) && printf "$s_bytes"
            (( i % 7 )) && printf "$p_bytes"
            (( i & 1 )) && printf "$intermediate" || printf "$p_bytes"
        } | sha512hex)
    done

    # Rearrange the bytes and crypt-base64 encode them
    hex=$(base64EncodeBytes 86 "$intermediate" \
        63  62 20 41  40 61 19  18 39 60  59 17 38  37 58 16  15 36 57  56 14 35 \
            34 55 13  12 33 54  53 11 32  31 52 10   9 30 51  50  8 29  28 49  7 \
             6 27 48  47  5 26  25 46  4   3 24 45  44  2 23  22 43  1   0 21 42)

    printf "%s$salt\$%s\n" "$magic" "$hex" 

}


if [[ $# < 1 ]] 
then
    echo "Usage: $0 password [salt]" >&2 
    exit 1
fi

password=$(stringToHex "$1")
salt=$(stringToHex "$2")
[[ -z $salt ]] && salt=$(tr -cd 'a-zA-Z0-9' < /dev/urandom | head -c 16) 

doHash "$password" "$salt" '$6$'