Anyone implemented SHA-1?

Monkey Forums/Monkey Programming/Anyone implemented SHA-1?

Tibit

(Posted 2013) [#1]

In Monkey?

Found this from Bmax. Can always convert if it hasn't been done.

How would you suggest that one tests the SHA1 function to see if it works correctly?

Was going to use this to encrypt user ID's over network.

Function SHA1$(in$)
  Local h0 = $67452301, h1 = $EFCDAB89, h2 = $98BADCFE, h3 = $10325476, h4 = $C3D2E1F0
  
  Local intCount = (((in$.length + 8) Shr 6) + 1) Shl 4
  Local data[intCount]
  
  For Local c=0 Until in$.length
    data[c Shr 2] = (data[c Shr 2] Shl 8) | (in$[c] & $FF)
  Next
  data[in$.length Shr 2] = ((data[in$.length Shr 2] Shl 8) | $80) Shl ((3 - (in$.length & 3)) Shl 3) 
  data[data.length - 2] = (Long(in$.length) * 8) Shr 32
  data[data.length - 1] = (Long(in$.length) * 8) & $FFFFFFFF
  
  For Local chunkStart=0 Until intCount Step 16
    Local a = h0, b = h1, c = h2, d = h3, e = h4

    Local w[] = data[chunkStart..chunkStart + 16]
    w = w[..80]
    
    For Local i=16 To 79
      w[i] = Rol(w[i - 3] ~ w[i - 8] ~ w[i - 14] ~ w[i - 16], 1)
    Next
    
    For Local i=0 To 19
      Local t = Rol(a, 5) + (d ~ (b & (c ~ d))) + e + $5A827999 + w[i]
      
      e = d ; d = c
      c = Rol(b, 30)
      b = a ; a = t
    Next
    
    For Local i=20 To 39
      Local t = Rol(a, 5) + (b ~ c ~ d) + e + $6ED9EBA1 + w[i]
      
      e = d ; d = c
      c = Rol(b, 30)
      b = a ; a = t
    Next
    
    For Local i=40 To 59
      Local t = Rol(a, 5) + ((b & c) | (d & (b | c))) + e + $8F1BBCDC + w[i]
      
      e = d ; d = c
      c = Rol(b, 30)
      b = a ; a = t
    Next

    For Local i=60 To 79
      Local t = Rol(a, 5) + (b ~ c ~ d) + e + $CA62C1D6 + w[i]
      
      e = d ; d = c
      c = Rol(b, 30)
      b = a ; a = t
    Next
    
    h0 :+ a ; h1 :+ b ; h2 :+ c
    h3 :+ d ; h4 :+ e
  Next
  
  Return (Hex(h0) + Hex(h1) + Hex(h2) + Hex(h3) + Hex(h4)).ToLower()  
End Function

Function Rol(val, shift)
  Return (val Shl shift) | (val Shr (32 - shift))
End Function

Function Ror(val, shift)
  Return (val Shr shift) | (val Shl (32 - shift))
End Function

Function LEHex$(val)
  Local out$ = Hex(val)
  
  Return out$[6..8] + out$[4..6] + out$[2..4] + out$[0..2]
End Function

Goodlookinguy

(Posted 2013) [#2]

How would you suggest that one tests the SHA1 function to see if it works correctly?

Check if "Hello World" outputs "0a4d55a8d778e5022fab701977c5d840bbc486d0"? That's similar to what I did when I was creating the CRC32 hash implementation.

Was going to use this to encrypt user ID's over network.

Why? Even if you do, someone peeking on the network could still figure out their ID if they have a rainbow table of numbers and the like. Seems pointless.

Tibit

(Posted 2013) [#3]

Why?

It is not really for my own sake:

"Due to privacy regulations all unique user identifiers retrieved must be encrypted before being submitted to GameAnalytics."
http://support.gameanalytics.com/entries/23053213-Encrypting-user-identifiers

So :)

I think this is by extension because of Apple's privacy concerns on tracking people's deviceID and similar identifiers such as Mac or userAccountID.

blabz

(Posted 2013) [#4]

Aren't Rainbow tables just large databases that compare string input to hashed outputs?

Rainbow tables are good, but they're not perfect.

Goodlookinguy

(Posted 2013) [#5]

Aren't Rainbow tables just large databases that compare string input to hashed outputs?

Rainbow tables are good, but they're not perfect.

Yes, while this is true for normal strings. You can expect a proper rainbow table to contain all numbers from the largest negative long value to the largest unsigned long value. If user IDs are only numbers, it's extraordinarily easy to find.

Edit: I should note that I worked in network security and the like for a few years, so I'm pretty familiar with this kind of technology.

blabz

(Posted 2013) [#6]

That makes sense, number wise.

String wise though complicates things, and from what I've seen in most applications they concatenate strings with the number value to generate the hash on the client end, then on the server do the same and compare the hash's before the data is digested. So you're still submitting an integer but the hash is "salted"(i think that's the correct term).

Ferdi

(Posted 2013) [#7]

Here is my port of SHA1. It is a port of Flash Sha1:

https://code.google.com/p/as3corelib/source/browse/trunk/src/com/adobe/crypto/SHA1.as?r=2

It was hard to get working because Flash has a nice logical shift right (>>>), and Monkey doesn't. Anyway, I implement LSR in pure monkey, seems to work just ok =)

ToHex is from http://www.monkeycoder.co.nz/Community/posts.php?topic=4058 Thanks Adam!


Strict

Function ToHex:String(i:Int)

	''p=32-bit
	Local r%=i, s%, p%=32, n:Int[p/4+1]

	While (p>0)
		
		s = (r&$f)+48
		If s>57 Then s+=7
		
		p-=4
		n[p Shr 2] = s
		r = r Shr 4
		 
	Wend

	Return String.FromChars(n)
	
End

Function Lsr:Int(val:Int, shift:Int)
	
	Return (val Shr shift) & ((1 Shl (32 - shift)) - 1)

End Function

Function Rol:Int(val:Int, shift:Int)

	Return (val Shl shift) | Lsr(val, (32 - shift))

End Function

' Converts a String To a sequence of 16-word blocks
' that we'll do the processing on.  Appends padding
' And length in the process.
'
' @param s The String To split into blocks
' @Return An Array containing the blocks that s was
'                      split into.

Function CreateBlocks:Int[]( s:String )

	Local len:Int = s.Length * 8
	Local blockLen:Int = ( ( ( len + 64 ) Shr 9 ) Shl 4 ) + 15 + 1
	Local blocks:Int[] = New Int[blockLen]
	Local mask:Int = $FF ' ignore hi byte of characters > 0xFF
	Local chars:Int[] = s.ToChars()

	For Local i:Int = 0 Until len Step 8
		blocks[ (i Shr 5) ] |= ( chars[ (i / 8) ] & mask ) Shl (24 - i Mod 32)
	End For

	' append padding And length
	blocks[ len Shr 5 ] |= $80 Shl ( 24 - len Mod 32 )
	blocks[ ( ( ( len + 64 ) Shr 9 ) Shl 4 ) + 15 ] = len

	'Local blockLen:Int = ( ( ( len + 64 ) Shr 9 ) Shl 4 ) + 15
	'Print "Len: " + len
	'Print "block length: " + blockLen

	Return blocks

End Function

' Performs the logical Function based on t
Function f:Int( t:Int, b:Int, c:Int, d:Int )

	If t < 20 Then
		Return ( b & c ) | ( ~b & d )
	Else If t < 40 Then
		Return b ~ c ~ d
	Else If t < 60 Then
		Return ( b & c ) | ( b & d ) | ( c & d )
	End If

	Return b ~ c ~ d

End Function
                
' Determines the constant value based on t
Function k:Int( t:Int )

	If t < 20 Then
		Return $5a827999
	Else If ( t < 40 )
		'DebugStop()
		Return $6ed9eba1
	Else If ( t < 60 )
		Return $8f1bbcdc
	End If

	Return $ca62c1d6

End Function

Function HashToByteArray:Void( s:String )

	'DebugStop()

	' initialize the h's
	Local h0:Int = $67452301
	Local h1:Int = $efcdab89
	Local h2:Int = $98badcfe
	Local h3:Int = $10325476
	Local h4:Int = $c3d2e1f0
                        
	' create the blocks from the String And
	' save the length as a Local var To reduce
	' lookup in the loop below
	Local blocks:Int[] = CreateBlocks( s )
	Local len:Int = blocks.Length;

	Local w:Int[] = New Int[ 80 ]

	' loop over all of the blocks
	For Local i:Int = 0 Until len Step 16 
                        
		' 6.1.c
		Local a:Int = h0
		Local b:Int = h1
		Local c:Int = h2
		Local d:Int = h3
		Local e:Int = h4

		' 80 steps To process each block
		' TODO: unroll For faster execution, Or 4 loops of
		' 20 each To avoid the k And f Function calls
		For Local t:Int = 0 Until 80

			If t < 16 Then
				' 6.1.a
				'DebugStop()
				w[ t ] = blocks[ i + t ]
			Else
				'DebugStop()
				' 6.1.b
				w[ t ] = Rol( w[ t - 3 ] ~ w[ t - 8 ] ~ w[ t - 14 ] ~ w[ t - 16 ], 1 )
			End If

			' 6.1.d
			Local r:Int = Rol( a, 5 )
			Local f:Int = f( t, b, c, d )
			Local wt:Int = w[ t ]
			Local k:Int = k(t)
			Local temp:Int = r +  f + e + wt + k
                                        
			'DebugStop()

			e = d
			d = c
			c = Rol( b, 30 )
			b = a
			a = temp

		End For

		' 6.1.e
		h0 += a
		h1 += b
		h2 += c
		h3 += d
		h4 += e

	End For

	Print "String: " + s                        
	Print "h0: " + ToHex(h0) + ", " + h0
	Print "h1: " + ToHex(h1) + ", " + h1
	Print "h2: " + ToHex(h2) + ", " + h2
	Print "h3: " + ToHex(h3) + ", " + h3
	Print "h4: " + ToHex(h4) + ", " + h4

End Function
    
Function Main:Int()

	HashToByteArray("The quick brown fox jumps over the lazy dog")
	HashToByteArray("The quick brown fox jumps over the lazy cog")
	HashToByteArray("")
	HashToByteArray("Hello World")
	
	Return 0

End Function

Result: (only tested on HTML5 and GLFW Windows 7)

Check the result at: http://en.wikipedia.org/wiki/SHA-1 (Examples and pseudocode)

String: The quick brown fox jumps over the lazy dog
h0: 2FD4E1C6, 802480582
h1: 7A2D28FC, 2049779964
h2: ED849EE1, -310075679
h3: BB76E739, -1149835463
h4: 1B93EB12, 462678802
String: The quick brown fox jumps over the lazy cog
h0: DE9F2C7F, 3734973567
h1: D25E1B3A, -5060551878
h2: FAD3E85A, -86775718
h3: 0BD17D9B, 198278555
h4: 100DB4B3, 269333683
String: 
h0: DA39A3EE, -633756690
h1: 5E6B4B0D, -2710877427
h2: 3255BFEF, -3450486801
h3: 95601890, -1788864368
h4: AFD80709, -1344796919
String: Hello World
h0: 0A4D55A8, -4122126936
h1: D778E502, 3615024386
h2: 2FAB7019, -3495202791
h3: 77C5D840, 2009454656
h4: BBC486D0, -1144748336

Let me know if there are any problems.

Goodlookinguy

(Posted 2013) [#8]

@Ferdi

It's neat that you made a Monkey-based Logical Shift Right, although I do have a native implementation for most, if not all, targets here http://www.monkeycoder.co.nz/Community/post.php?topic=1707&post=28645 if you wanted it to process a bit faster. Although, in modern devices, processing seems to be the least of my worries nowadays.

Ferdi

(Posted 2013) [#9]

Doh! Should have done a search on the forum, instead of mucking around and wrote my own. Thanks for that! I did thought about doing it natively, but I thought it was an overkill for what I was going to use it for. Probably going to be called once or twice in a single game.

Dip	(Posted 2014) [#10]

Thanks, this was exactly what I was looking for!

Paul - Taiphoz

(Posted 2014) [#11]

For apples policy on encryption do they define what encryption is ?, just wondering if doing a quick homebrew sypher on the id's might have been enough, or are they forcing you to use sha or md5 ?

Sub_Zero

(Posted 2014) [#12]

Anyone got an encryption algorithm completely done in monkey?

Dip	(Posted 2014) [#13]

I got around to testing this out in my game, and kept running into issues (I needed the whole hash returned as one string, rather than separated). I came across an interesting side effect of String.FromChars. Whenever I tried to concatenate the hashes together, I'd only get the first one. After much head scratching, I changed this line in ToHex:
Local r%=i, s%, p%=32, n:Int[p/4+1]
to:
Local r%=i, s%, p%=32, n:Int[p/4]
and it was able to work properly. This wouldn't be noticed in the code the way it is presented, as each hex part is printed separately. When you try to concatenate them, however, you'll find you can add to the beginning of them but not the end. I assume this is because Monkey determines strings based on null terminations, which would throw away anything past the 'end' of the string. The Return String.FromChars(n) line was adding a null from n being one array element longer than it needed to be.

Just posting this in case it helps someone else.