SHA-3 Sub-Function Reversibility Clarification
I just finished a very slow and clunky python implementation of SHA-3 (224,256,384,512). The exercise was not designed for speed. My only objective was to gain insight into the underlining functionality of the SHA-3 family of functions, and to document it in a manner that I find readable.
References Include the Following:
SHA-3 Documentation-
https://pdfs.semanticscholar.org/8450/06456ff132a406444fa85aa7b5636266a8d0.pdf http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
Theta() Documentation-
Can anyone breifly explain the 'theta step' of compression box in SHA3?
Intermediate Value Documentation-
http://csrc.nist.gov/groups/ST/toolkit/examples.html
I found during this process a variety of discrepancies between the two sets of SHA-3 documentation, and with regards to FIPS 202, some areas, specifically 3.2.2 and 3.2.3, where the documentation could use both editing and clarification(IMO). In those areas, to my dissatisfaction, I resorted to reversing the provided intermediate values to derive both pi() and rho(), as it was ultimately easier that deciphering the provided documentation.
With that, the following is directly quoted from FIPS 202 Section 4 regarding Sponge Construction:
“The SHA-3 functions, specified in Sec. 6 are instances of the sponge construction in which the underlying function f is invertible, i.e., a permutation, although the sponge construction does not require f to be invertible.”
This is clearly evident in the reversibility of both pi() and rho(). And given the constraints of SHA-3 iota() is also reversible. As functionally it’s just a XOR operation with a round constant.
Analysis of theta() and chi() will take longer.
I’ll be living here for a while:
What criteria make the theta step of Keccak's round function reversible?
My specific question: Why would the SHA-3 designers not make every sub-function irreversible?
My code for the curious.
def bin_8bit(dec):
return(str(format(dec,'08b')))
def bin_32bit(dec):
return(str(format(dec,'032b')))
def bin_4bit(dec):
return(str(format(dec,'04b')))
def bin_64bit(dec):
return(str(format(dec,'064b')))
def hex_return(dec):
return(str(format(dec,'08x')))
def hex_double(dec):
return(str(format(dec,'02x')))
def hex_single(dec):
return(str(format(dec,'01x')))
def dec_return_bin(bin_string):
return(int(bin_string,2))
def dec_return_hex(hex_string):
return(int(hex_string,16))
def L_P(SET,n):
to_return=[]
j=0
k=n
while k<len(SET)+1:
to_return.append(SET[j:k])
j=k
k+=n
return(to_return)
def s_l(bit_string):
bit_list=[]
for i in range(len(bit_string)):
bit_list.append(bit_string[i])
return(bit_list)
def l_s(bit_list):
bit_string=''
for i in range(len(bit_list)):
bit_string+=bit_list[i]
return(bit_string)
def rotate_left(bit_string,n):
if n==0:
return(bit_string)
bit_list = s_l(bit_string)
count=0
while count <= n-1:
list_main=list(bit_list)
var_0=list_main.pop(0)
list_main=list(list_main+[var_0])
bit_list=list(list_main)
count+=1
return(l_s(list_main))
def rotate_right(bit_string,n):
if n==0:
return(bit_string)
bit_list = s_l(bit_string)
count=0
while count <= n-1:
list_main=list(bit_list)
var_0=list_main.pop(-1)
list_main=list([var_0]+list_main)
bit_list=list(list_main)
count+=1
return(l_s(list_main))
def shift_right(bit_string,n):
bit_list=s_l(bit_string)
count=0
while count <= n-1:
bit_list.pop(-1)
count+=1
front_append=['0']*n
return(l_s(front_append+bit_list))
def mod_32_addition(input_set):
value=0
for i in range(len(input_set)):
value+=input_set[i]
mod_32 = 4294967296
return(value%mod_32)
def xo(bit_string_1,bit_string_2):
xor_list=[]
for i in range(len(bit_string_1)):
if bit_string_1[i]=='0' and bit_string_2[i]=='0':
xor_list.append('0')
if bit_string_1[i]=='1' and bit_string_2[i]=='1':
xor_list.append('0')
if bit_string_1[i]=='0' and bit_string_2[i]=='1':
xor_list.append('1')
if bit_string_1[i]=='1' and bit_string_2[i]=='0':
xor_list.append('1')
return(l_s(xor_list))
def and_2str(bit_string_1,bit_string_2):
and_list=[]
for i in range(len(bit_string_1)):
if bit_string_1[i]=='1' and bit_string_2[i]=='1':
and_list.append('1')
else:
and_list.append('0')
return(l_s(and_list))
def or_2str(bit_string_1,bit_string_2):
or_list=[]
for i in range(len(bit_string_1)):
if bit_string_1[i]=='0' and bit_string_2[i]=='0':
or_list.append('0')
else:
or_list.append('1')
return(l_s(or_list))
def not_str(bit_string):
not_list=[]
for i in range(len(bit_string)):
if bit_string[i]=='0':
not_list.append('1')
else:
not_list.append('0')
return(l_s(not_list))
def init_array():
int_bits = L_P(L_P('0'*1600,64),5)
return(int_bits)
def sub_str_concat(list_of_lists):
to_return=[]
for i in range(len(list_of_lists)):
insert=''
for x in range(len(list_of_lists[i])):
insert+=list_of_lists[i][x]
to_return.append(insert)
return(to_return)
def str_concat(list_of_strings):
to_return=''
for i in range(len(list_of_strings)):
to_return+=list_of_strings[i]
return(to_return)
def list_concat(list_of_lists):
to_return=[]
for i in range(len(list_of_lists)):
to_return+=list_of_lists[i]
return(to_return)
def flip_string(a_string):
to_return=''
for i in range(1,len(a_string)+1):
to_return+=a_string[-i]
return(to_return)
def message_append(str_msg):
return(str_msg+'01')
def sha_3_rate(output_len):
if output_len==224:
return(1152)
if output_len==256:
return(1088)
if output_len==384:
return(832)
if output_len==512:
return(576)
def pad(x,m):
j=(-m-2)%x
return('1'+'0'*j+'1')
def trunc(string,index):
return(string[0:index])
def message_processing(bit_string,digest_len):
msg_bs = message_append(bit_string)
p = msg_bs + pad(sha_3_rate(digest_len),len(msg_bs))
to_split = L_P(p,8)
new_hex=[]
for i in range(len(to_split)):
new_hex.append(hex_double(int(flip_string(to_split[i]),2)))
back_append = 200-len(new_hex)
new_hex = new_hex+['00']*back_append
total_string=''
for i in range(len(new_hex)):
total_string+=new_hex[i]
to_insert = L_P(total_string,16)
to_return=[]
for i in range(len(to_insert)):
to_return.append(flip_string(L_P(to_insert[i],2)))
return(to_return)
def message_expansion(hex_list):
to_convert=''
for i in range(len(hex_list)):
to_convert+=bin_8bit(int(hex_list[i],16))
return(to_convert)
def theta(s):
c_xz=[]
for i in range(5):
c_xz.append(xo(xo(xo(xo(s[i],s[i+5]),s[i+10]),s[i+15]),s[i+20]))
d_xz=[]
for i in range(5):
d_xz.append(xo(c_xz[(i-1)%5],rotate_left(c_xz[(i+1)%5],1)))
a_xyz=[]
for i in range(5):
a_xyz.append([xo(s[i],d_xz[i]),
xo(s[i+5],d_xz[i]),
xo(s[i+10],d_xz[i]),
xo(s[i+15],d_xz[i]),
xo(s[i+20],d_xz[i])])
a_xyz=list_concat(a_xyz)
order_return=[]
for i in range(5):
order_return.append([a_xyz[i],a_xyz[i+5],a_xyz[i+10],a_xyz[i+15],a_xyz[i+20]])
return(list_concat(order_return))
def rho(s):
off_set=[0,1,190,28,91,
36,300,6,55,276,
3,10,171,153,231,
105,45,15,21,136,
210,66,253,120,78]
to_return=[]
for i in range(len(s)):
to_return.append(rotate_left(s[i],off_set[i]))
return(to_return)
def pi(s):
index=[0,6,12,18,24,
3,9,10,16,22,
1,7,13,19,20,
4,5,11,17,23,
2,8,14,15,21]
to_return=[]
for i in range(len(index)):
for x in range(len(s)):
if index[i]==x:
to_return.append(s[x])
return(to_return)
def chi(s):
def sf(find_list,set_main):
return(set_main.index(find_list))
sm=[[0,0],[1,0],[2,0],[3,0],[4,0],
[0,1],[1,1],[2,1],[3,1],[4,1],
[0,2],[1,2],[2,2],[3,2],[4,2],
[0,3],[1,3],[2,3],[3,3],[4,3],
[0,4],[1,4],[2,4],[3,4],[4,4]]
to_return=[]
for i in range(25):
to_return.append(xo(s[i],and_2str(not_str(s[sf([(sm[i][0]+1)%5,sm[i][1]],sm)]),s[sf([(sm[i][0]+2)%5,sm[i][1]],sm)])))
return(to_return)
def iota(s,i_r):
def rc(t):
def xor_bit(a,b):
return('1' if ((a == '1') ^ (b == '1')) else '0')
if t%255==0:
return('1')
r=['1','0','0','0','0','0','0','0']
for i in range(1,(t%255)+1):
r = ['0'] + r
r[0] = xor_bit(r[0],r[8])
r[4] = xor_bit(r[4],r[8])
r[5] = xor_bit(r[5],r[8])
r[6] = xor_bit(r[6],r[8])
r = trunc(r,8)
return(r[0])
to_index=[]
for x in range(24):
to_check=''
RC = ['0']*64
for i in range(7):
RC[(2**i)-1]=rc(i+(7*x))
to_index.append(flip_string(str_concat(RC)))
s[0]=xo(s[0],to_index[i_r])
return(s)
def message_bit_return(string_input):
bit_list=[]
for i in range(len(string_input)):
bit_list.append(bin_8bit(ord(string_input[i])))
return(l_s(bit_list))
def processing(message_string):
to_invert=L_P(message_bit_return(message_string),8)
to_return=[]
for i in range(len(to_invert)):
to_return.append(flip_string(to_invert[i]))
return(str_concat(to_return))
def sha_3(to_hash,digest_len):
x = L_P(message_expansion(L_P(str_concat(message_processing(processing(to_hash),digest_len)),2)),64)
for i in range(24):
x = iota(chi(pi(rho(theta(x)))),i)
to_flip=[]
for i in range(digest_len/64):
to_flip.append(x[i])
to_convert=[]
for i in range(len(to_flip)):
to_convert.append(L_P(to_flip[i],8))
bin_list=[]
for i in range(len(to_convert)):
bin_list.append(flip_string(to_convert[i]))
bin_list=L_P(str_concat(bin_list),4)
to_return=[]
for i in range(len(bin_list)):
to_return.append(hex_single(int(bin_list[i],2)))
to_return=str_concat(to_return)
return(to_return)