SHA-1 hash code generator (SHA1)

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
Post Reply
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

SHA-1 hash code generator (SHA1)

Post by D.J.Peters »

I needed the SHA-1 hash code to implement the WebSocket protocol.

wikipedia: https://en.wikipedia.org/wiki/SHA-1

Later I use it on microcontrollers for my CAN BUS Model Railway system.

However this is a easy to read implementation not optimized in any way !

Joshy

Code: Select all

' SHA-1 (Secure Hash Algorithm 1) generator 
' https://en.wikipedia.org/wiki/SHA-1
const as ubyte BIT0 = asc("0")
const as ubyte BIT1 = asc("1")
function _NOT(a as string) as string
  var result = space(32)
  for i as integer = 0 to 31
    result[i]=iif( a[i]=BIT1, BIT0,BIT1 )
  next  
  return result
end function
function _AND(a as string, b as string) as string
  var result = space(32)
  for i as integer = 0 to 31
    result[i]=iif( a[i]=BIT1 and b[i]=BIT1, BIT1,BIT0 )
  next  
  return result
end function
function _OR(a as string, b as string) as string
  var result = space(32)
  for i as integer = 0 to 31
    result[i]=iif( a[i]=BIT1 or b[i]=BIT1, BIT1,BIT0 )
  next  
  return result
end function
function _XOR(a as string, b as string) as string
  var result = space(32)
  for i as integer = 0 to 31
    result[i]=iif( a[i]=b[i], BIT0,BIT1 )
  next  
  return result
end function
function _ADD(a as string, b as string) as string
  dim as ulong a32 = val("&B" & a)
  dim as ulong b32 = val("&B" & b)
  dim as ulongint r64 = a32 + b32
  var result = bin(r64) 
  if len(result)<32 then result = bin(r64,32)
  return result
end function
function _ROTL(a as string, n as integer) as string
  var result = space(32)
  result[31]=a[0]
  for i as integer=0 to 30
    result[i]=a[i+1]
  next
  n-=1
  while n
    var tmp=result[0]
    for i as integer=0 to 30
      result[i]=result[i+1]
    next
    result[31]=tmp
    n-=1
  wend  
  return result
end function
function _TRUNC(a as string, n as integer) as string
  var result = ""
  if len(a)<=n then
    result = a
  else
    result = left(a,n)
  end if
  return result
end function

' i used any ptr so you can get the hash code von any kind of data
' getSHA1(strptr(aString),len(aString))
' getSHA1(@array(0),nBytes_in_array) 
' ...
function getSHA1(byval src as any ptr, byval nBytes as integer, byval bLCase as boolean=false) as string
  dim as string s = space(nBytes*8+1)
  dim as ubyte ptr p=src
  for i as integer = 0 to nBytes-1
    var b = bin(p[i],8)
    for j as integer = 0 to 7
      s[i*8+j]=b[j]
    next  
  next
  ' add one bit more 
  s[nBytes*8] = BIT1
  ' reserve at least one frame with 448bits (pading "0")
  while (len(s) mod 512)<>448: s &= "0" : wend
  ' add source length pading 64 with "0" NOTE 448 + 64 = 512
  s &= bin(nBytes*8,64)
  ' break bitstream of 512 bit frames in chunks of 16 x 32bit words (but reserve 80 words)
  var nChunks = len(s) : nChunks shr= 9 ' \512
  dim as string chunks80(nChunks-1,79)
  for i as integer = 0 to nChunks-1
    for j as integer = 0 to 15
      chunks80(i,j) = mid(s,1 + i*512+j*32,32)
    next  
  next
  ' extend chunks from 16x32bit words to 80x32bit words
  for i as integer = 0 to nChunks-1
    for j as integer = 16 to 79
      var wordA = chunks80(i,j- 3)
      var wordB = chunks80(i,j- 8)
      var wordC = chunks80(i,j-14)
      var wordD = chunks80(i,j-16)
      var xorA = _XOR(wordA,wordB)
      var xorB = _XOR(xorA,wordC)
      var xorC = _XOR(xorB,wordD)
      var newWord = _ROTL(xorC,1)
      chunks80(i,j) = newWord
    next  
  next  

  var h0 = "01100111010001010010001100000001"
  var h1 = "11101111110011011010101110001001"
  var h2 = "10011000101110101101110011111110"
  var h3 = "00010000001100100101010001110110"
  var h4 = "11000011110100101110000111110000"  
  
  ' generate the hash code
  for i as integer = 0 to nChunks-1
    var a = h0, b = h1, c = h2, d = h3, e = h4   
    var f = ""
    var k = ""
    for j as integer = 0 to 79
      if (j<20) then
        var BandC = _AND(b,c)  
        var notB = _AND(_NOT(b),d)
        f = _OR(BandC, notB)
        k = "01011010100000100111100110011001"
      elseif (j<40) then
        var BxorC = _XOR(b,c)  
        var notB = _AND(_NOT(b),d)
        f = _XOR(BxorC, d)
        k = "01101110110110011110101110100001"      
      elseif (j<60) then
        var BandC = _AND(b,c)
        var BandD = _AND(b,d)
        var CandD = _AND(c,d)
        var BandCorBandD = _OR(BandC,BandD)
        f = _OR(BandCorBandD,CandD)
        k = "10001111000110111011110011011100"
      else
        var BxorC = _XOR(b,c)
        f = _XOR(BxorC,d)
        k = "11001010011000101100000111010110"
      end if
      var tempA = _ADD(_ROTL(a,5),f)
      var tempB = _ADD(tempA,e)
      var tempC = _ADD(tempB,k)
      var word32 = chunks80(i,j)
      var temp = _ADD(tempC,word32)
      temp = _TRUNC(temp,32)
      e = d
      d = c
      c = _ROTL(b,30)
      b = a
      a = temp
    next
    h0 = _TRUNC(_ADD(h0,a),32)
    h1 = _TRUNC(_ADD(h1,b),32)
    h2 = _TRUNC(_ADD(h2,c),32)
    h3 = _TRUNC(_ADD(h3,d),32)
    h4 = _TRUNC(_ADD(h4,e),32)
  next
  ' build the final hash code as hex string
  var hash = hex(val("&B" & h0),8)
  hash &= hex(val("&B" & h1),8)
  hash &= hex(val("&B" & h2),8)
  hash &= hex(val("&B" & h3),8)
  hash &= hex(val("&B" & h4),8)
  if bLCase then hash = lcase(hash)
  return hash
end function  
'
' main
'
var aString = "The quick brown fox jumps over the lazy cog"
var nBytes = len(aString)
var SHA1 = getSHA1(strptr(aString),nBytes,true)
print "SHA-1 from string '" & aString & "' are " & SHA1

if SHA1 = "de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3" then
  print "generated hash is ok !"
else
  print "generated hash is wrong !"
  beep
end if
sleep
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

Re: SHA-1 hash code generator (SHA1)

Post by D.J.Peters »

I added the optinal argument bLCase !
FreeBASIC used uppercase hex digits but if you need a lower case hash code set bLCase = TRUE

Joshy

Code: Select all

function getSHA1(byval src as any ptr, byval nBytes as integer, byval bLCase as boolean=false) as string
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: SHA-1 hash code generator (SHA1)

Post by deltarho[1859] »

@D.J.Peters

Nice. Image

Blake2 may be worthwhile considering. Blake2b-256, optimized for 64-bit platforms, is faster than MD5, SHA-1, SHA-2, and SHA-3. It came to fruition after the NIST competition for an alternative to SHA-2. Blake3 s faster still but hasn't had enough cryptanalysis yet for my liking (2020).

The second link below has some pseudocode. The third link is the full implementation.

BLAKE2 — fast secure hashing
BLAKE (hash function)
RFC 793
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: SHA-1 hash code generator (SHA1)

Post by deltarho[1859] »

There is asm code at the PowerBASIC forum here with some test code at post #3.
TJF
Posts: 3809
Joined: Dec 06, 2009 22:27
Location: N47°, E15°
Contact:

Re: SHA-1 hash code generator (SHA1)

Post by TJF »

There's a GSocketConnection in GIOStream object, handling all that low level stuff.
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

Re: SHA-1 hash code generator (SHA1)

Post by D.J.Peters »

I'm a pro and can do it all in super fast and short SSE assembler trust me ;-)
I posted a simple readable BASIC version for the people in the back they don't understand wikipedia pseudocode.

@deltarho[1859] thank you for the links but Websockets used SHA-1 hash code only.

Joshy
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: SHA-1 hash code generator (SHA1)

Post by deltarho[1859] »

Joshy wrote:Websockets used SHA-1 hash code only.
Someone needs to look at that - 80-bit security strength is too weak nowadays.
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: SHA-1 hash code generator (SHA1)

Post by jj2007 »

Another option: GetHash(pContent, nBytes) uses the Windows API CryptGetHashParam. See also BCrypt*
Gunslinger
Posts: 103
Joined: Mar 08, 2016 19:10
Location: The Netherlands

Re: SHA-1 hash code generator (SHA1)

Post by Gunslinger »

Hi D.J.Peters,

I'm looking for hash code like this, thanks.
When compile your code under windows 64bit i got a "generated hash is wrong !"
When i did 32bit the hash is ok.
i have replaced some integer with long types, what did not help.
badidea
Posts: 2586
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: SHA-1 hash code generator (SHA1)

Post by badidea »

Gunslinger wrote:When compile your code under windows 64bit i got a "generated hash is wrong !"
When i did 32bit the hash is ok.
The problem is in the ADD function, change to this and it should work:

Code: Select all

function _ADD(a as string, b as string) as string
  dim as ulong a32 = val("&B" & a)
  dim as ulong b32 = val("&B" & b)
  dim as ulongint r64 = a32 + b32
  'var result = bin(r64)
  'if len(result)<32 then result = bin(r64,32)
  var result = bin(r64,32)
  return result
end function
When compiling with 64 bit fbc, len(result) can be > 32. The bin function does not remove digits, only adds zeros if needed.
Not sure why it works ok on 32-bit fbc. I expected that a32 + b32 always result in a 32-bit integer in that case.

Actually, changing r64 to ulong also works. Is the 'overflow bit' not needed for the calculation?
Gunslinger
Posts: 103
Joined: Mar 08, 2016 19:10
Location: The Netherlands

Re: SHA-1 hash code generator (SHA1)

Post by Gunslinger »

Thanks for the fix.
I have no idea how it works i let hash functions for pro's :)
Post Reply