1
$\begingroup$

since we can put 448 bit of the actual message in every block(56 characters), if I have a string of 56 charcters ba7816bf8f01cfea414140de5dae2223bda12ae1a5324sfdserew3ra does it mean that I only have one message block with the binary of below? I have also added the 1 and the length:

01100010011000010011011100111000001100010011011001100010011001100011100001100110001100000011000101100011011001100110010101100001001101000011000100110100001100010011010000110000011001000110010100110101011001000110000101100101001100100011001000110010001100110110001001100100011000010011000100110010011000010110010100110001011000010011010100110011001100100011010001110011011001100110010001110011011001010111001001100101011101110011001101110010011000011000000000000000000000000000000000000000000000000000000111000000

Edit:

I'm trying to learn each step of sha256, so I wrote a code with python that uses the binary strings instead of math operations to fully understand it.

The code works fine when the input is less than 56 characters but when it's equal or more than 56 characters the output is incorrect:

For exmaple when the input is: ba7816bf8f01cfea414140de5dae2223bda12ae1a5324sfdserew3ra

instead of 1caa150674ab1aed030dc69f9b86dbcbc412e6e1dd20344eeaa21687acae7789

I get 8492782cc396d4454980c9b63f127c5730da7d838822f8f37b1c7705d2630b88

Code:

Operations.py

  class Operations:
        def add(self, data1, data2):
              x = data1
              y = data2

              carry = 0
              result = ""

              for i in range(len(data1) -1, -1, -1):
                    r = carry
                    r += 1 if x[i] == '1' else 0
                    r += 1 if y[i] == '1' else 0
                    result = ('1' if r % 2 == 1 else '0') + result
                    carry = 0 if r < 2 else 1

              if carry != 0: result = '1' + result

              return result[-len(data1):]

        def xor(self, data1, data2):
              result = ""
              for i in range(len(data1)):
                    temp1 = data1[i]
                    temp2 = data2[i]
                    if (temp1 == "0" and temp2 == "0") or (temp1 == "1" and temp2 == "1"):
                          result += "0"
                    else:
                          result += "1"

              return result

        def shiftRight(self, data, turn):
              result = "0" * turn + data
              return result[:len(data)]

        def rotateRight(self, data, turn):
              result = None
              for i in range(turn):
                    if result:
                          temp = result[-1]
                          result = (temp + result)[:len(data)]
                    else:
                          temp = data[-1]
                          result = (temp + data)[:len(data)]

              return result

Functions.py

  from operations import Operations

  class Functions(Operations):
        def sigma0(self, data): # Lowercase sigma
              temp1 = self.rotateRight(data, 7)
              temp2 = self.rotateRight(data, 18)
              temp3 = self.shiftRight(data, 3)
              result = self.xor(temp3, self.xor(temp1, temp2))
              return result

        def sigma1(self, data): # Lowercase sigma
              temp1 = self.rotateRight(data, 17)
              temp2 = self.rotateRight(data, 19)
              temp3 = self.shiftRight(data, 10)
              result = self.xor(temp3, self.xor(temp1, temp2))
              return result

        def gamma0(self, data): # Uppercase sigma
              temp1 = self.rotateRight(data, 2)
              temp2 = self.rotateRight(data, 13)
              temp3 = self.rotateRight(data, 22)
              result = self.xor(temp3, self.xor(temp1, temp2))
              return result

        def gamma1(self, data): # Uppercase sigma
              temp1 = self.rotateRight(data, 6)
              temp2 = self.rotateRight(data, 11)
              temp3 = self.rotateRight(data, 25)
              result = self.xor(temp3, self.xor(temp1, temp2))
              return result

        def choice(self, x, y, z):
              result = ""
              for i in range(len(x)):
                    result += y[i] if x[i] == "1" else z[i]

              return result

        def majority(self, x, y, z):
              result = ""
              for i in range(len(x)):
                    temp0 = 0
                    temp1 = 0

                    temp0 += 1 if x[i] == "0" else 0 
                    temp1 += 1 if x[i] == "1" else 0

                    temp0 += 1 if y[i] == "0" else 0                  
                    temp1 += 1 if y[i] == "1" else 0

                    temp0 += 1 if z[i] == "0" else 0
                    temp1 += 1 if z[i] == "1" else 0
                    
                    if temp0 > temp1:
                          result += "0"
                    else:
                          result += "1"

              return result

Main.py

  from math import ceil
  from copy import copy
  from functions import Functions

  _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]

  _h = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
        0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]

  class SHA256(Functions):
        blocks = []

        def __init__(self):
              global _k, _h            
              _k = [f'{i:b}'.zfill(32) for i in _k]
              _h = [f'{i:b}'.zfill(32) for i in _h]

        def message_to_blocks(self, message):
              chunk = 56
              data = [format(ord(x), 'b').zfill(8) for x in message]

              for i in range(ceil(len(data) / chunk)):
                    self.blocks.append(data[chunk * i:chunk * (i + 1)])

                    self.blocks[i] = ''.join(self.blocks[i])
                    length = f'{len(self.blocks[i]):b}'
                    self.blocks[i] += '1'
                    self.blocks[i] = self.blocks[i].ljust(512, '0')

                    # add length to last 64 bit
                    self.blocks[i] = self.blocks[i][:-len(length)]
                    self.blocks[i] += length

        def message_schedule(self, data):
              schedule = []
              n = 32
              # first 16 words
              schedule = [(data[i:i+n]) for i in range(0, len(data), n)]
              # generate the rest
              for i in range(16, 64):
                    temp1 = self.sigma1(schedule[-2])
                    temp2 = self.sigma0(schedule[-15])
                    result = self.add(temp1, self.add(schedule[-7], self.add(temp2, schedule[-16])))
                    schedule.append(result)

              return schedule

        def compress(self):
              for block in self.blocks:
                    temp_h = copy(_h)
                    _w = self.message_schedule(block)
                    for i in range(64):
                          T1 = [self.gamma1(_h[4]), self.choice(_h[4], _h[5], _h[6]), _h[7], _k[i], _w[i]]
                          T1 = self.add(T1[0], self.add(T1[1], self.add(T1[2], self.add(T1[3], T1[4]))))

                          T2 = [self.gamma0(_h[0]), self.majority(_h[0], _h[1], _h[2])]
                          T2 = self.add(T2[0], T2[1])
                          
                          # shift all constants down
                          _h[7] = _h[6] # h
                          _h[6] = _h[5] # g
                          _h[5] = _h[4] # f
                          _h[4] = _h[3] # e
                          _h[3] = _h[2] # d
                          _h[2] = _h[1] # c
                          _h[1] = _h[0] # b

                          # compress
                          _h[0] = self.add(T1, T2)
                          _h[4] = self.add(_h[4], T1)

                    # add with initial values
                    _h[0] = self.add(_h[0], temp_h[0])
                    _h[1] = self.add(_h[1], temp_h[1])
                    _h[2] = self.add(_h[2], temp_h[2])
                    _h[3] = self.add(_h[3], temp_h[3])
                    _h[4] = self.add(_h[4], temp_h[4])
                    _h[5] = self.add(_h[5], temp_h[5])
                    _h[6] = self.add(_h[6], temp_h[6])
                    _h[7] = self.add(_h[7], temp_h[7])

              return self.digest(_h)

        def digest(self, hashes):
              final_hash = ""
              for hash in hashes:
                    t = hex(int(hash, 2))
                    final_hash += t[2:]

              return final_hash

  a = SHA256()
  a.message_to_blocks("ba7816bf8f01cfea414140de5dae2223bda12ae1a5324sfdserew3ra")
  print(a.compress())
$\endgroup$
2
$\begingroup$

You are confusing the padding scheme of SHA-256 NIST 180-4 page 13

Suppose that the length of the message, $M$, is $\ell$ bits. Append the bit $1$ to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation $$ \ell - 1 - k \equiv 448 \pmod{512}.$$ Then append the 64-bit block that is equal to the number $\ell$ expressed using a binary representation.

As we can see, the padding is applied to the end of the message, not for each block. If necessary, a new block is formed. Once the padding is performed, the message can be divide into 512-bit parts that can be represented as 16 32-bit words, see section 5.2 from the NIST 180-4.

In the programming, the message may not be ready to apply the padding first, especially in large files or in file streamings. Then, one processes the file in 512-bit blocks and can apply the padding during the final block, if necessary adding a new block, too.

$$\texttt{message}\mathbin\|\texttt{1}\mathbin\|\texttt{k-zeroes}\mathbin\|\texttt{64-bit encoded lenght}$$

The padded zeroes ($k$) can be zero, however, the appended 1 and the 64-bit length must be there. So if a message is larger than 448 in the last block a new block must be formed.

In your code, you use only 448 bits of each block, this is incorrect.

The 448 is correct if your message length is exactly $448$ bits. If smaller then $k$ zeroes are needed. If the message length is $> 448$ then the padding is only needed for the last block. The other blocks are always used in full size, 512.

Your encoding on the top of the question is correct for a message size of 56 characters and you have only one block to hash.

$\endgroup$
3
  • $\begingroup$ I updated the question, is the problem message blocks or the compression? $\endgroup$ – Silent-B May 21 at 15:55
  • $\begingroup$ Sorry, the question turn more into a Stack Overflow question. In Cryptography.SE we are not related to coding issues even they are related to cryptography. I've seen your knowledge mistake, and provide the real padding scheme. $\endgroup$ – kelalaka May 21 at 16:03
  • $\begingroup$ Your message_to_blocks is not correct, it carries your knowledge mistake. Still, the code has no place. here. $\endgroup$ – kelalaka May 21 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.