Sep 25, 2016

So, Season 5 of New Girl just came out on Netflix. I think you know where this is going, but effectively I sat in the Lovesac and watched TV all day. To feel a little bit better, I thought I should exercise my fingers a bit. Anyway here goes, back by popular demand, an F# implementation of SHA1. Now, before you look at my crap code and start asking questions. This is pretty much my first time ever using F#. Anyway, it compiles, and I've tested it a few times, so it seems 100% ready to ship.

raw

// Converts an ascii string into a byte sequence
let getBytes (input: string) = seq {for c in input -> (byte)c}

// Get a uint32 from a sequence of 4 bytes in big endian
let bytesToUi (input: seq<byte>) = 
    let i = ref 3

    // My decrementor function because I didnt realize value assignment don't return a value
    let dec value =
        let t = !value
        value := (!value - 1)
        t
    // Fold the 4 bytes into a uint
    Seq.fold (fun (acc : uint32) (b : byte) -> acc ||| (uint32(b) <<< (dec i) * 8)) 0u input

// Rotate left
let rotl (input: uint32) (amount) =
    (input <<< amount) ||| (input >>> (32 - amount))

// Runs SHA1 on a string
let sha1 (input: string) =
    // Get length of input in bytes
    let messageLen = uint32(input.Length)

    // Get length of input in bits
    let bitlen = uint64(8u * messageLen)

    // Get the amount we need to pad. Include the bit (0x80) we append to the message and the ulong at the end of the message for length
    let padlen = 
        match ((messageLen + 9u) % 64u) with
        | 0u -> 0
        | _ -> int(64u - ((messageLen + 9u) % 64u))

    // Append the bit to the end of the message
    let asciibytes = Seq.append (getBytes(input)) (Seq.singleton 0x80uy)

    // Pad with 0s. Assume the length is not going to be larger than uint32, so set the highest order 4 bytes to zero as well
    let asciibytes = Seq.append asciibytes (seq {for i in 1.. (padlen+4) -> 0uy})

    // Append 64 bits of message length
    let messageBytes = Seq.append asciibytes (seq {for i in (List.rev [0..7]) -> ((byte)(bitlen >>> (i * 8)))})

    // Constants
    let mutable h0 = 0x67452301u
    let mutable h1 = 0xEFCDAB89u
    let mutable h2 = 0x98BADCFEu
    let mutable h3 = 0x10325476u
    let mutable h4 = 0xC3D2E1F0u

    // Get the total message length
    let totalBytes = Seq.length messageBytes

    // For each 64 byte chunk
    for chunk = 0 to ((totalBytes / 64)-1) do
        let w = [| for i in 1 .. 80 -> 0u|]

        // Populate the array
        for i = 0 to 15 do
            w.[i] <- bytesToUi (Seq.take 4 (Seq.skip (i*4 + chunk * 64) messageBytes))
        for i = 16 to 79 do
            w.[i] <- rotl ((w.[i-3]) ^^^ (w.[i-8]) ^^^ (w.[i-14]) ^^^ (w.[i-16])) 1

        // Set up the locals
        let mutable a, b, c, d, e = h0, h1, h2, h3, h4
        let mutable k = 0u
        let mutable f = 0u

        for i in 0 .. 79 do
            let round = match i with
                        | m when m < 20 -> (0x5A827999u, ((b &&& c) ||| ((~~~b) &&& d)))
                        | m when m < 40 -> (0x6ED9EBA1u, (b ^^^ c ^^^ d))
                        | m when m < 60 -> (0x8F1BBCDCu, ((b &&& c) ||| (b &&& d) ||| (c &&& d)))
                        | _ -> (0xCA62C1D6u, (b ^^^ c ^^^ d))
            let temp = (rotl a 5) + (snd round) + e + (fst round) + w.[i]
            e <- d
            d <- c
            c <- rotl b 30
            b <- a
            a <- temp

        h0 <- h0 + a
        h1 <- h1 + b
        h2 <- h2 + c
        h3 <- h3 + d
        h4 <- h4 + e

    [h0; h1; h2; h3; h4]




Have you ever thought to yourself, "How does a deprecated standard like SHA1 work, and how could it be implemented in powershell?". Well look no further. Actually, it was a litte harder than it seems, since powershell REALLY loves signed numbers. Lets take for example: 0xFFFFFFFF, which one would assume is ?equal to 4294967295?. Well.. Check out this simple line of code.

raw

#This wont throw an exception right?
[uint32]0xFFFFFFFF

Well, in powershell this just throws an exception. You know why!? Because under the hood, PShelly goes OH "0xFFFFFFFF", that's 32 bits. Let me stick it in a 32 bit signed integer. But wait... "0xFFFFFFFF" is just 32 1s. But oh crap, in 2s complement, that's -1. So in powershell 0xFFFFFFFF == -1. So now its pretty clear why the above code throws an exception, there is no unsigned value to represent -1. Seriously, just go type "0xFFFFFFFF" into powershell. So.. because of that, everything here has to be done in a 64 bit integer.

raw

#
# Implemenation of SHA1
#
function SHA1
{
    [CmdLetBinding()]
    param
    (
        [Parameter(Mandatory = $false, Position=1)][string]$Str
    )
    process
    {
        #
        # Truncate a value to UInt32
        #
        function TUI
        {
            param($val)
            process
            {
                [uint64]($val -band (((-bnot [uint64]0)) -shr 32))
            }
        }

        #
        # Get a 32 bit value from a byte array
        #
        function GetBigEndianUInt
        {
            param
            (
                [byte[]]$bytes,
                [int]$index
            )
            process
            {
                return ([uint64]$bytes[$index] -shl 24) -bor ([uint64]$bytes[$index+1] -shl 16) -bor ([uint64]$bytes[$index+2] -shl 8) -bor ([uint64]$bytes[$index+3])
            }
        }

        #
        # Left rotate
        #
        function LeftRotate
        {
            param
            (
                [uint64]$val,
                [int]$amount
            )
            process
            {
                $res = TUI ([uint64]$val -shr (32 - $amount))
                $res = $res -bor ($val -shl $amount)
                return TUI $res
            }
        }

        # Initialize constants
        $h0 = TUI 0x67452301
        $h1 = TUI 0xEFCDAB89
        $h2 = TUI 0x98BADCFE
        $h3 = TUI 0x10325476
        $h4 = TUI 0xC3D2E1F0
        
        # Get the message bytes
        $message = [System.Text.ASCIIEncoding]::ASCII.GetBytes($Str)

        # Get the length in bytes which we need. Message length + 0x80 + (64bit message len)
        $len = ($message.Length + 9)
        
        # Get the padded length of our our byte array
        if($len % 64 -ne 0){
            $len += (64 - ($len % 64))
        }

        # Copy the bytes in the message to our byte array
        $bytes = ([byte[]]0 * $len)
        for($i = 0; $i -lt $message.Length; $i++){
            $bytes[$i] = [byte]$message[$i]
        }

        # Pad the message with 1000 0000
        $bytes[$i] = 128

        # The message length in bits
        $bitLen = $message.Length * 8

        # Set the last [uint64] as the messsage length. (We only do 32 bits)
        $bytes[$len-1] = [byte]($bitLen -band 0xFF)
        $bytes[$len-2] = [byte](($bitLen -shr 8) -band 0xFF)
        $bytes[$len-3] = [byte](($bitLen -shr 16) -band 0xFF)
        $bytes[$len-4] = [byte](($bitLen -shr 24) -band 0xFF)

        # Divide the message into 512 bit chunks
        for($chunk = 0; $chunk -lt $bytes.Length; $chunk += 64)
        {
            $w = ([uint64[]]0 * 80)

            # Copy the chunk into our working array as uints
            for($i = 0; $i -lt 16; $i++){
                $w[$i] = GetBigEndianUInt -bytes $bytes -index ($i*4 + $chunk)
            }

            for($i = 16; $i -lt 80; $i++){
                $w[$i] = LeftRotate -val (TUI ($w[$i-3] -bxor $w[$i-8] -bxor $w[$i-14] -bxor $w[$i-16])) -amount 1
            }

            $a = TUI $h0
            $b = TUI $h1
            $c = TUI $h2
            $d = TUI $h3
            $e = TUI $h4

            # A bunch of crazy stuff
            for($i = 0; $i -lt 80; $i++){
                $k=0
                if($i -lt 20){
                    $f = TUI (($b -band $c) -bor ((-bnot $b) -band $d))
                    $k = TUI 0x5A827999
                }
                elseif($i -lt 40){
                    $f = TUI ($b -bxor $c -bxor $d)
                    $k = TUI 0x6ED9EBA1
                }
                elseif($i -lt 60){
                    $f = TUI (($b -band $c) -bor ($b -band $d) -bor ($c -band $d))
                    $k = TUI 0x8F1BBCDC
                }
                else{
                    $f = TUI ($b -bxor $c -bxor $d)
                    $k = TUI 0xCA62C1D6
                }
            
                $temp = TUI ((LeftRotate -val $a -amount 5) + $f + $e + $k + $w[$i])

                $e = $d
                $d = $c
                $c = LeftRotate -val $b -amount 30
                $b = $a
                $a = $temp
            }

            $h0 = TUI ($h0 + $a)
            $h1 = TUI ($h1 + $b)
            $h2 = TUI ($h2 + $c)
            $h3 = TUI ($h3 + $d)
            $h4 = TUI ($h4 + $e)   
        }

        '{0:X8}{1:X8}{2:X8}{3:X8}{4:X8}' -f $h0, $h1, $h2, $h3, $h4
    }
}

There it is. I may have overused my TUI(To uint) function a little bit, since values larger than 32 bits could actually cause problems. I got most of the implementation details from the wikipedia artical on SHA1.




© 2019 - Peter Sulucz | disclaimer

log in