## 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.

``````
// 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
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 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]``````

## Sep 20, 2016

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.

``````
#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.

``````
#
# 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
\$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.