SHA-3 Sub-Function Reversibility Clarification

Question

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)

Answer 1

Hash functions are generally designed by splitting the problem into two parts:

1. A fixed size core function. This is called the compression function in most hashes, but in Keccak it's called the permutation.
2. A domain extender—an algorithm that uses the fixed-size core function to process arbitrary-length inputs. In older hashes like SHA-2 this is the Merkle-Damgård construction; in Keccak it is the sponge construction.

The core function is normally evaluated by cryptanalysis; cryptographers attempt to actually crack it in practice. The domain extenders on the other hand are often evaluated through security proofs: cryptographers try to find a mathematical argument that shows that if the resulting hash function is insecure, it's not the domain extender's fault.

Bertoni, Daemen, Peeters and Assche's paper "Cryptographic Sponge Functions" contains security proofs for the sponge construction. They carry out their proofs using two kinds of core functions:

1. Random transformation: Any randomly selected function with $b$-bit blocks as its domain and range.
2. Random permutation: Randomly selected among permutations of $b$-bit blocks—i.e., invertible functions with the same domain and range.

And they conclude (p. 65):

Remarkably, using a random permutation [in the sponge construction's security proof] results in a better [random-oracle indifferentiability] bound than using a random transformation.

The reasons are extremely technical, but the answer to your question bottoms out to that: the security proofs for the sponge construction tells us that using permutations as its core function works better.

Answer 2

Let's suppose our algorithm is irreversible. Can we - in that case - guarantee that states will not narrow down into some subdomain? Can we prove the security level provided by digest size or capacity?

We cannot span the space of digest-message pairs when using irreversible functions. The only way of the proving the security level is using reversible sub-functions. The one-to-one relationship between inputs and the outputs of sub-functions is used to provide this demonstration.