Version 20 of SHA-256

Updated 2006-02-22 21:56:55 by RML

if {0} { LM 2006-02-13:

A didactic implementation of SHA-256 in pure Tcl. It follows exactly the indication of FIPS180-2 document.

Note that all variables are unsigned 32-bit integers and all calculations have to be performed modulo 2^32.

A conservative programming technique was adopted; some optimisations are possible.

There is the possibility of calculating the sha256 hash value with a multistep strategy (see the following Long Message test).

Comments and suggestions are appreciated.


AK: Note that the CVS head of Tcllib has an implementation of sha224/256 as well.

(See sha2)


 }

 # sha-256.tcl
 # SHA-256 hash algorithm
 #
 # Lino Monaco - Feb 2006
 # _________________________________________


 proc sha256_init {} {
   global K
   global h0 h1 h2 h3 h4 h5 h6 h7

   # Set the SHA-256 constants  
   set K {0x428a2f98 0x71374491 0xb5c0fbcf 0xe9b5dba5 \
          0x3956c25b 0x59f111f1 0x923f82a4 0xab1c5ed5 \
          0xd807aa98 0x12835b01 0x243185be 0x550c7dc3 \
          0x72be5d74 0x80deb1fe 0x9bdc06a7 0xc19bf174 \
          0xe49b69c1 0xefbe4786 0x0fc19dc6 0x240ca1cc \
          0x2de92c6f 0x4a7484aa 0x5cb0a9dc 0x76f988da \
          0x983e5152 0xa831c66d 0xb00327c8 0xbf597fc7 \
          0xc6e00bf3 0xd5a79147 0x06ca6351 0x14292967 \
          0x27b70a85 0x2e1b2138 0x4d2c6dfc 0x53380d13 \
          0x650a7354 0x766a0abb 0x81c2c92e 0x92722c85 \
          0xa2bfe8a1 0xa81a664b 0xc24b8b70 0xc76c51a3 \
          0xd192e819 0xd6990624 0xf40e3585 0x106aa070 \
          0x19a4c116 0x1e376c08 0x2748774c 0x34b0bcb5 \
          0x391c0cb3 0x4ed8aa4a 0x5b9cca4f 0x682e6ff3 \
          0x748f82ee 0x78a5636f 0x84c87814 0x8cc70208 \
          0x90befffa 0xa4506ceb 0xbef9a3f7 0xc67178f2 }
   # ... and initial hash value
   set h0 0x6a09e667 
   set h1 0xbb67ae85 
   set h2 0x3c6ef372 
   set h3 0xa54ff53a
   set h4 0x510e527f 
   set h5 0x9b05688c 
   set h6 0x1f83d9ab 
   set h7 0x5be0cd19
 }

 # SHA-256 logical functions ___________________________________________________ 
 proc Ch {x y z} {
   return [expr {($x & $y) ^ (~($x) & $z)}]
 }

 proc Maj {x y z} {
   return [expr {($x & $y) ^ ($x & $z) ^ ($y & $z)}]
 }

 proc SIGMA_0 {x} {
   set a [expr {(($x >> 2) & 0x3FFFFFFF) | (($x << (32 - 2)) & 0xFFFFFFFF)}]
   set b [expr {(($x >> 13) & 0x0007FFFF) | (($x << (32 - 13)) & 0xFFFFFFFF)}]
   set c [expr {(($x >> 22) & 0x000003FF) | (($x << (32 - 22)) & 0xFFFFFFFF)}]        
   return [expr {$a ^ $b ^$c}]
 } 

 proc SIGMA_1 {x} {
   set a [expr {(($x >> 6) & 0x03FFFFFF) | (($x << (32 - 6)) & 0xFFFFFFFF)}]
   set b [expr {(($x >> 11) & 0x001FFFFF) | (($x << (32 - 11)) & 0xFFFFFFFF)}]
   set c [expr {(($x >> 25) & 0x0000007F) | (($x << (32 - 25)) & 0xFFFFFFFF)}]
   return [expr {$a ^ $b ^$c}]
 } 

 proc sigma0 {x} {
   set a [expr {(($x >> 7) & 0x01FFFFFF) | (($x << (32 - 7)) & 0xFFFFFFFF)}]
   set b [expr {(($x >> 18) & 0x00003FFF) | (($x << (32 - 18)) & 0xFFFFFFFF)}]
   set c [expr {($x >> 3) & 0x1FFFFFFF}]
   return [expr {$a ^ $b ^$c}]
 }

 proc sigma1 {x} {
   set a [expr {(($x >> 17) & 0x00007FFF) | (($x << (32 - 17)) & 0xFFFFFFFF)}]
   set b [expr {(($x >> 19) & 0x00001FFF) | (($x << (32 - 19)) & 0xFFFFFFFF)}]
   set c [expr {($x >> 10) & 0x003FFFFF}]
   return [expr {$a ^ $b ^$c}]
 }
 #______________________________________________________________________________

 proc sha256_pad {msg len} {
   # Padding function: works only with messages that have a byte-aligned length
   # "len" is the total bytes length of whole message

   # append the value 0x80 to message
   #
   append msg [binary format c 0x80]

   # append "0" bits until the message length is equal to 64 - 8 - 1 bytes
   #
   set mlen [expr {($len + 8 + 1) % 64}]
   while {$mlen < 64} {
     append msg [binary format c 0x0]
     incr mlen
   }

   # append a 64-bits big-endian integer giving the original message length (in bits)
   #
   append msg [binary format W [expr {$len*8}]]
   return $msg
 }

 proc sha256_round {msg} {
   global K
   global h0 h1 h2 h3 h4 h5 h6 h7

   # Divide the message into 32-bits integer
   #
   binary scan $msg I* crunch
   set len [llength $crunch]

   # Work 16 integers at a time
   #
   for {set i 0} {$i < $len} {incr i 16} { 

     # Prepare the message scheduler
     #
     set W {}
     for {set j 0} {$j < 16} {incr j} {
       lappend W [lindex $crunch [expr {$i + $j}]]
     }        
     for {set j 16} {$j < 64} {incr j} {
       set W15 [lindex $W [expr {$j - 15}]]
       set W2  [lindex $W [expr {$j - 2}]]
       set W16 [lindex $W [expr {$j - 16}]]
       set W7  [lindex $W [expr {$j - 7}]]
       set s0  [sigma0 $W15]
       set s1  [sigma1 $W2]
       lappend W [expr {($W16 + $s0 + $W7 + $s1) & 0xFFFFFFFF}]
     }

     # Initialize the working variables        
     #
     set a $h0
     set b $h1
     set c $h2
     set d $h3
     set e $h4
     set f $h5
     set g $h6
     set h $h7

     # 64 Hash rounds
     #
     for {set j 0} {$j < 64} {incr j} {        
       set s0 [SIGMA_0 $a]
       set maj [Maj $a $b $c]
       set t0 [expr {($s0 + $maj) & 0xFFFFFFFF}]
       set s1 [SIGMA_1 $e]
       set ch [Ch $e $f $g]
       set Kj [lindex $K $j]
       set Wj [lindex $W $j]
       set t1 [expr {($h + $s1 + $ch + $Kj + $Wj) & 0xFFFFFFFF}]

       set h $g
       set g $f
       set f $e
       set e [expr { ($d + $t1) & 0xFFFFFFFF}]
       set d $c
       set c $b
       set b $a
       set a [expr {($t0 + $t1) & 0xFFFFFFFF}] 
     }

     # Compute the intermediate hash value
     #
     set h0 [expr {($h0 + $a) & 0xffffffff}]
     set h1 [expr {($h1 + $b) & 0xffffffff}] 
     set h2 [expr {($h2 + $c) & 0xffffffff}]
     set h3 [expr {($h3 + $d) & 0xffffffff}]
     set h4 [expr {($h4 + $e) & 0xffffffff}]
     set h5 [expr {($h5 + $f) & 0xffffffff}]
     set h6 [expr {($h6 + $g) & 0xffffffff}] 
     set h7 [expr {($h7 + $h) & 0xffffffff}]
   }
 }

 proc sha256_end {} {
   global h0 h1 h2 h3 h4 h5 h6 h7

   # format the hashing value        
   #
   set h0 [format %08X $h0]
   set h1 [format %08X $h1] 
   set h2 [format %08X $h2]
   set h3 [format %08X $h3]
   set h4 [format %08X $h4]
   set h5 [format %08X $h5]
   set h6 [format %08X $h6] 
   set h7 [format %08X $h7]

   return "$h0 $h1 $h2 $h3 $h4 $h5 $h6 $h7"
 }
 proc sha256 {msg} {

   # glue all the work
   #
   sha256_init
   set msg [sha256_pad $msg [string bytelength $msg]]
   sha256_round $msg
   sha256_end
 }

 # Test vectors and results 
 #
 set msg "abc"
 puts "One block message test: $msg"
 puts "[sha256 $msg]\n"


 set msg "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
 puts "Multi-block message test: $msg"
 puts "[sha256 $msg]\n"


 # In case of very long messages, the hash calculation can be executed
 # in more steps. 
 # The message has to be divided into 64 bytes pieces calling repeatedly 
 # "sha256_round" procedure. The last time giving as input parameter the 
 # result of "sha256_pad".
 #
 # The padding procedure has to be called with the last bytes of the message
 # if < 64 or an empty string in case of a message with a length multiple of
 # 64 bytes.
 # 
 # 
 puts "Long Message test:"
 puts "a string which consists of 1,000,000 repetition of the character 'a'"
 set msg [string repeat a 64]
 sha256_init

 #
 #                   15625 * 64 = 1,000,000
 for {set i 0} {$i < 15625} {incr i} { 
   sha256_round $msg
 }
 sha256_round [sha256_pad "" 1000000]
 puts "[sha256_end]\n"

if {0} {

 Test results:

 One block message test: abc
 BA7816BF 8F01CFEA 414140DE 5DAE2223 B00361A3 96177A9C B410FF61 F20015AD

 Multi-block message test: abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq
 248D6A61 D20638B8 E5C02693 0C3E6039 A33CE459 64FF2167 F6ECEDD4 19DB06C1

 Long Message test:
 a string which consists of 1,000,000 repetition of the character 'a'
 CDC76E5C 9914FB92 81A1C7E2 84D73E67 F1809A48 A497200E 046D39CC C7112CD0

}


if {0} {

LM 2006-02-14

This is an optimised version of SHA-256 hash algorithm implementation: less code and it runs faster on my test machine.

 time {sha256 abc} 1000
 672 microseconds per iteration

vs.

 766 microseconds per iteration 

of the original version.

}

 # sha-256.tcl
 # SHA-256 hash algorithm optimised implementation
 #
 # Lino Monaco - Feb 2006
 # _______________________________________________

 proc sha256_init {} {
   global K
   global H

   # Set the SHA-256 constants  
   set K {0x428a2f98 0x71374491 0xb5c0fbcf 0xe9b5dba5 \
          0x3956c25b 0x59f111f1 0x923f82a4 0xab1c5ed5 \
          0xd807aa98 0x12835b01 0x243185be 0x550c7dc3 \
          0x72be5d74 0x80deb1fe 0x9bdc06a7 0xc19bf174 \
          0xe49b69c1 0xefbe4786 0x0fc19dc6 0x240ca1cc \
          0x2de92c6f 0x4a7484aa 0x5cb0a9dc 0x76f988da \
          0x983e5152 0xa831c66d 0xb00327c8 0xbf597fc7 \
          0xc6e00bf3 0xd5a79147 0x06ca6351 0x14292967 \
          0x27b70a85 0x2e1b2138 0x4d2c6dfc 0x53380d13 \
          0x650a7354 0x766a0abb 0x81c2c92e 0x92722c85 \
          0xa2bfe8a1 0xa81a664b 0xc24b8b70 0xc76c51a3 \
          0xd192e819 0xd6990624 0xf40e3585 0x106aa070 \
          0x19a4c116 0x1e376c08 0x2748774c 0x34b0bcb5 \
          0x391c0cb3 0x4ed8aa4a 0x5b9cca4f 0x682e6ff3 \
          0x748f82ee 0x78a5636f 0x84c87814 0x8cc70208 \
          0x90befffa 0xa4506ceb 0xbef9a3f7 0xc67178f2 }
   # ... and initial hash value
   set H {0x6a09e667 0xbb67ae85 0x3c6ef372 0xa54ff53a \
          0x510e527f 0x9b05688c 0x1f83d9ab 0x5be0cd19}
 }

 # SHA-256 logical functions ___________________________________________________ 
 proc Ch {x y z} {
   return [expr {($x & $y) ^ (~($x) & $z)}]
 }

 proc Maj {x y z} {
   return [expr {($x & $y) ^ ($x & $z) ^ ($y & $z)}]
 }

 proc SIGMA_0 {x} {
   return [expr {((($x >> 2) & 0x3FFFFFFF) | ($x << (32 - 2))) ^
                 ((($x >> 13) & 0x0007FFFF) | ($x << (32 - 13))) ^
                 ((($x >> 22) & 0x000003FF) | ($x << (32 - 22))) & 0xffffffff }]
 } 

 proc SIGMA_1 {x} {
   return [expr {((($x >> 6) & 0x03FFFFFF) | ($x << (32 - 6))) ^
                 ((($x >> 11) & 0x001FFFFF) | ($x << (32 - 11))) ^
                 ((($x >> 25) & 0x0000007F) | ($x << (32 - 25))) & 0xffffffff }]
 } 

 proc sigma0 {x} {
   return [expr {((($x >> 7) & 0x01FFFFFF) | ($x << (32 - 7))) ^
                 ((($x >> 18) & 0x00003FFF) | ($x << (32 - 18))) ^
                 (($x >> 3) & 0x1FFFFFFF) & 0xffffffff}]
 }

 proc sigma1 {x} {
   return [expr {((($x >> 17) & 0x00007FFF) | ($x << (32 - 17))) ^
                 ((($x >> 19) & 0x00001FFF) | ($x << (32 - 19))) ^
                 (($x >> 10) & 0x003FFFFF) & 0xffffffff}]
 }
 #______________________________________________________________________________

 proc sha256_pad {msg len} {
   # Padding function: works only with messages that have a byte-aligned length
   # "len" is the total bytes length of whole message

   # append the value 0x80 to message
   #
   append msg [binary format c 0x80]

   # append "0" bits until the message length is equal to 64 - 8 - 1 bytes
   #
   set mlen [expr {64 - (($len + 8 + 1) % 64)}]
   append msg [string repeat [binary format c 0x00] $mlen]

   # append a 64-bits big-endian integer giving the original message length (in bits)
   #
   append msg [binary format W [expr {$len*8}]]
   return $msg
 }

 proc sha256_round {msg} {
   global K
   global H

   # Divide the message into 32-bits integer
   #
   binary scan $msg I* crunch
   set len [llength $crunch]

   # Work 16 integers at a time
   #
   for {set i 0} {$i < $len} {incr i 16} { 
     # Prepare the message scheduler
     #
     set W {}
     for {set j 0} {$j < 16} {incr j} {
       lappend W [lindex $crunch [expr {$i + $j}]]
     }        
     for {set j 16} {$j < 64} {incr j} {
           lappend W [expr {( [lindex $W [expr {$j - 16}]] +
                              [sigma0 [lindex $W [expr {$j - 15}]]] +
                              [lindex $W [expr {$j - 7}]] +
                              [sigma1 [lindex $W [expr {$j - 2}]]] ) & 0xffffffff }]
     }

     # Initialize the working variables        
     #
         foreach {a b c d e f g h} $H {}

     # 64 Hash rounds
     #
     for {set j 0} {$j < 64} {incr j} {        
           set t0 [expr {([SIGMA_0 $a] + [Maj $a $b $c]) & 0xffffffff}]   
           set t1 [expr {( $h + [SIGMA_1 $e] + [Ch $e $f $g] + 
                                [lindex $K $j] + [lindex $W $j]) & 0xffffffff}]
           foreach {h g f e d c b a} [list $g $f $e [expr { ($d + $t1) & 0xFFFFFFFF}] \
                                           $c $b $a [expr {($t0 + $t1) & 0xFFFFFFFF}]] {}
     }

     # Compute the intermediate hash value
     #
         set H1 {}
         foreach hh $H tt [list $a $b $c $d $e $f $g $h] {
                lappend H1 [expr {($hh + $tt) & 0xffffffff}]
         }
         set H $H1
   }
 }

 proc sha256_end {} {
   global H

   # format the hashing value        
   #
   set res ""
   foreach hh $H {
     append res [format "%08X " $hh]
   }
   return $res
 }

 proc sha256 {msg} {

   # glue all the work
   #
   sha256_init
   set msg [sha256_pad $msg [string bytelength $msg]]
   sha256_round $msg
   sha256_end
 }

 # Test vectors and results 
 #
 set msg "abc"
 puts "One block message test: $msg"
 puts "[sha256 $msg]\n"


 set msg "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
 puts "Multi-block message test: $msg"
 puts "[sha256 $msg]\n"


 puts "Long Message test:"
 puts "a string which consists of 1,000,000 repetition of the character 'a'"
 set msg [string repeat a 64]
 sha256_init

 #
 #                   15625 * 64 = 1,000,000
 for {set i 0} {$i < 15625} {incr i} { 
   sha256_round $msg
 }
 sha256_round [sha256_pad "" 1000000]
 puts "[sha256_end]\n"

RML: 2006-02-22

I found this code very helpful but I ran into two issue:

1) I found that when using multi-byte characters, this code fails. This was fixed by making the following change in the sha256 procedure:

 set msg [sha256_pad $msg [string bytelength $msg]]

to:

 set msg [sha256_pad $msg [string length $msg]]

2) In the sha256_pad procedure, this line:

 append msg [binary format W [expr {$len*8}]]

only works in Tcl 8.4+ since that's when the W option was introduced. For folks, like myself, using earlier versions, this can be replaced by this line to get things working:

 append msg [binary format II 0 [expr {$len*8}]]

See also sha2, sha1, md4, md5, ripemd, cryptkit

[ Category Package, subset Tcllib | Category Cryptography ]