10
$\begingroup$

From what I've been reading, Keccak's round function is reversible. That's pretty obvious for the $\rho$, $\pi$ and $\iota$ transforms. For $\chi$ to be reversible, $x$'s range has to be odd — but that's alright since Keccak's $x$ has a range of 5. Yet, what criteria make the theta step reversible?

Checking some small $x$, $y$ and $z$ ranges, it shows that:

  • where [x][y][z]'s ranges are [3][3][2], $\theta$ is not reversible, and
  • where [x][y][z]'s ranges are [3][3][3], $\theta$ is not reversible either.

So, what makes the $\theta$ for (eg) [5][5][64] reversible?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Playing around with it, I've come to the suspicion that $\theta$ is invertible except when $x$ is odd and $y$ is a multiple of 3. I don't have a proof of that, though... $\endgroup$
    – poncho
    Commented Aug 14, 2013 at 16:57
  • 1
    $\begingroup$ Nope, it turns out to be more subtle than I thought: $x$ odd, $y=5$ and $z=15$ also turns out to be noninvertible. I'm pretty sure I can prove that, in the $y=5$ case, that $\theta$ is invertible unless $x$ is odd and $z$ is a multiple of 15. $\endgroup$
    – poncho
    Commented Aug 14, 2013 at 20:58

3 Answers 3

Reset to default
13
$\begingroup$

I went through it, and while this isn't a complete answer, it should shed some light (and note: when I'm talking about $x$, $y$ and $z$, I'm referring to the ranges those indicies can take on; not any specific index)

First rule: if $x$ is even, then $\theta$ is invertible. The proof of that is actually fairly elegant; however it's also rather irrelevant to Keccak (because even if you were going to tweak Keccak, the $\chi$ step requires $x$ to be odd).

Now, from here on down, we'll assume $x$ is odd.

Here is how it works; there is a function $L(y)$ that maps the range of $y$ into a set of integers; $\theta$ with the parameters $(x, y, z)$ is invertible iff $z$ is not a multiple of any of the integers within the set $L(y)$

$L(y)$ has the property that $L(a) \cup L(b) \subseteq L(ab)$

Here is the list of $L(y)$ for $y<38$:

$L(2^n) = \emptyset$

That is, if $y$ is a power of 2, $\theta$ is always invertible

$L(3n) = \{ 1 \}$

What that means is that, since all values of $z$ are multiples of 1, then $\theta$ is never invertible if $y$ is a multiple of 3.

$L(5) = \{ 15 \}$

In the Keccak case, the actual value of $z = 64$ is not a multiple of 15, and hence $\theta$ is invertible.

$L(7) = \{ 7 \}$

$L(10) = \{ 15 \}$

$L(11) = \{ 341 \}$

$L(13) = \{ 819 \}$

$L(14) = \{ 7 \}$

$L(17) = \{ 85 \}$

$L(19) = \{ 9709 \}$

$L(20) = \{ 15 \}$

$L(22) = \{ 341 \}$

$L(23) = \{ 2047 \}$

$L(25) = \{ 15 \}$

$L(26) = \{ 819 \}$

$L(28) = \{ 7 \}$

$L(29) = \{ 475107 \}$

$L(31) = \{ 31 \}$

$L(34) = \{ 85 \}$

$L(35) = \{ 7, 15 \}$

$L(37) = \{ 3233097 \}$

Now, there are certain obvious regularities with above listed $L$ function values; for example, if $y$ is prime other than 2, then every $L(y)$ listed consists of a single element which is a divisor of $2^{y-1}-1$; and in every case listed, we have $L(ab) = L(a) \cup L(b)$; however I cannot prove either of those observations hold in general.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @e-sushi It appears some comments have been removed! $\endgroup$
    – Q-Club
    Commented Jan 5, 2018 at 19:51
0
$\begingroup$

It’s my understanding that the features of theta, that make it reversible, can be displayed in the fact that the function’s structure allows for a significant reduction in the total number of input bits. While my solution at it's core is just a partially optimized brute force solution, my argument is that the characteristics of the optimization are the necessary criteria for the reversibility provided you only have access to the computing power of a single personal computer.

My final approach was to break theta into its sub functions. See the definition of theta provided directly below. 

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))

If you look to the last for loop in the above definition of theta (it's also defined below with it's respective supporting functions). The final output is taken by concatenating the set of every 5th index. This is a very import function that I named t_3 and is defined below. 

def t_3(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))

If you apply t_3 to both the input and output of theta, combined with the characteristics of a_xyz, you will get the relationship displayed in the below sample theta input and output.

example_one  = t_3(theta_input)

example_two = t_3(theta_output)


example_one=
 ['0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000',

  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000',                   
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000',

  '1000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000',

  '1000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000',

  '1000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000', 
  '0000000000000000000000000000000000000000000000000000000000000000']

example_two=
  ['1000000000000000000000000000000000000000000000000000000000000000', 
   '1000000000000000000000000000000000000000000000000000000000000000', 
   '1000000000000000000000000000000000000000000000000000000000000000', 
   '1000000000000000000000000000000000000000000000000000000000000000', 
   '1000000000000000000000000000000000000000000000000000000000000000',

   '0000000000000000000000000000000000000000000000000000000000000001', 
   '0000000000000000000000000000000000000000000000000000000000000001', 
   '0000000000000000000000000000000000000000000000000000000000000001', 
   '0000000000000000000000000000000000000000000000000000000000000001', 
   '0000000000000000000000000000000000000000000000000000000000000001',

   '1000000000000000000000000000000000000000000000000000000000000001', 
   '0000000000000000000000000000000000000000000000000000000000000001', 
   '0000000000000000000000000000000000000000000000000000000000000001', 
   '0000000000000000000000000000000000000000000000000000000000000001', 
   '0000000000000000000000000000000000000000000000000000000000000001',

   '0000000000000000000000000000000000000000000000000000000000000001', 
   '1000000000000000000000000000000000000000000000000000000000000001', 
   '1000000000000000000000000000000000000000000000000000000000000001', 
   '1000000000000000000000000000000000000000000000000000000000000001', 
   '1000000000000000000000000000000000000000000000000000000000000001',

   '0000000000000000000000000000000000000000000000000000000000000000', 
   '1000000000000000000000000000000000000000000000000000000000000000', 
   '1000000000000000000000000000000000000000000000000000000000000000', 
   '1000000000000000000000000000000000000000000000000000000000000000', 
   '1000000000000000000000000000000000000000000000000000000000000000']

Now if you look at respective 5-blocks in example_one and example_two you just have to compare their 5-bit columns, and see that they're the bitwise negation of each other. This is true for all input/output pairings, such that there are only 320 possible "bits" to compare for an arbitrary input/output pairing. In the sense that a "bit" can take on only one of two possible binary values in the integer range[0,31]. From here on a bit will be defined as a value in the range I previously defined.

Now the difficulty is being able to brute force a solution with less that 2^320 calls to theta! My approach was to build all the possible output columns provided with an arbitrary theta output. This is where it gets tricky because you have to deal with the left circular rotation...for the method I've provided. It's can be shown, provided the previous definition of a bit, that there are 10 possible input bits that effect any output column. Then you build all output columns that satisfy the original theta output. Then call THETA_INVERT(op) and in ~5 min it will return the original input.

def THETA_INVERT(op):
    data=[]
    for i in range(64):
        data.append(MOD_5_THETA_BREAK(op,i))
        print(i)
    to_return=[]
    for i in range(len(data[0])):
        for x in range(len(data[1])):
            if THETA_COMPARE(data[0][i],data[1][x],1)==True:
                i_0=THETA_COL_EXTRACT(data[0][i],[0,1])
                i_1=THETA_COL_EXTRACT(data[1][x],[2])
                to_insert=THETA_COL_INSERT(i_0+i_1,[0,1,2])
                to_check=theta(to_insert)
                if THETA_SET_COMPARE(to_check,op,[0,1])==True:
                    to_return.append(to_insert)
    to_hold=[to_return]
    for meta in range(2,63):
        insert=[]
        print(meta)
        for i in range(len(data[meta])):
            for x in range(len(to_hold[-1])):
                if THETA_COMPARE(data[meta][i],to_hold[-1][x],meta)==True:
                    i_0=THETA_COL_EXTRACT(to_hold[-1][x],range(meta+1))
                    i_1=THETA_COL_EXTRACT(data[meta][i],[meta+1])
                    to_insert=THETA_COL_INSERT(i_0+i_1,range(meta+2))
                    to_check=theta(to_insert)
                    if THETA_SET_COMPARE(to_check,op,range(meta+1))==True:
                        insert.append(to_insert)
        to_hold.append(insert)
    for i in range(len(to_hold[-1])):
        if theta(to_hold[-1][i])==op:
            return(to_hold[-1][i])

Note that for THETA_INVERT to work all of the below code needs to be present, and if you want to run a test numpy should also be installed. 

def to_print(object):
    for i in range(len(object)):
        print(object[i])

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 bin_n_bit(dec,n):
    return(str(format(dec,'0'+n+'b')))

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 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 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 THETA_COMPARE(t_0,t_1,col):
    #Theta compare will take two possible theta through puts and returns True
    #if both col's of the theta through puts are equal values. Returns
    #False is the theta through puts are not the same values.
    for i in range(len(t_0)):
        if t_0[i][col]!=t_1[i][col]:
            return(False)
    return(True)

def THETA_SET_COMPARE(t_0,t_1,col_set):
    for i in range(len(col_set)):
        if THETA_COMPARE(t_0,t_1,col_set[i])==False:
            return(False)
    return(True)

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 index_search(a_set,index_set):
    #This function will take a set and a respective index set and
    #return the index locations if a_set
    to_return=[]
    for i in range(len(index_set)):
        to_return.append(a_set[index_set[i]])
    return(to_return)

def rc_con(sub_set):
    #Function to take take some set and do a row column split
    to_return=[]
    for i in range(len(sub_set[0])):
        insert=''
        for x in range(len(sub_set)):
            insert+=sub_set[x][i]
        to_return.append(insert)
    return(to_return)

def rc_lcon(sub_set):
    to_return=[]
    for i in range(len(sub_set[0])):
        insert=[]
        for x in range(len(sub_set)):
            insert+=[sub_set[x][i]]
        to_return.append(insert)
    return(to_return)

def str_build(a_list):
    to_return=''
    for i in range(len(a_list)):
        to_return+=str(a_list[i])
    return(to_return)

def set_main_build(size,iter_len):
    import numpy
    to_return=[]
    for i in range(iter_len):
        to_return.append(str_build(list(numpy.random.randint(2,size=(size,)))))
    return(to_return)

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 t_3(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 mod_5_split(theta_through_put):
    #Function will take a theta throug put and will grab 5 row checks
    #for processing. Once 5 rwo chucks are returned the function return
    #do a row column conversion.
    to_convert=L_P(theta_through_put,5)
    to_return=[]
    for i in range(len(to_convert)):
        to_return.append(rc_con(to_convert[i]))
    return(to_return)


def COI_RETURN(op,coi):
    #First call to mod_5_split 
    if coi != 63:
        to_iter=mod_5_split(t_3(op))
        set_0=[]
        for i in range(len(to_iter)):
            set_0.append(to_iter[i][coi])
        to_return_0=[]
        for i in range(len(set_0)):
            to_return_0.append([set_0[i],not_str(set_0[i])])
        set_1=[]
        for i in range(len(to_iter)):
            set_1.append(to_iter[i][coi+1])
        to_return_1=[]
        for i in range(len(set_1)):
            to_return_1.append([set_1[i],not_str(set_1[i])])
        return(to_return_0,to_return_1)
    if coi == 63:
        to_iter=mod_5_split(t_3(op))
        set_0=[]
        for i in range(len(to_iter)):
            set_0.append(to_iter[i][coi])
        to_return_0=[]
        for i in range(len(set_0)):
            to_return_0.append([set_0[i],not_str(set_0[i])])
        set_1=[]
        for i in range(len(to_iter)):
            set_1.append(to_iter[i][0])
        to_return_1=[]
        for i in range(len(set_1)):
            to_return_1.append([set_1[i],not_str(set_1[i])])
        return(to_return_0,to_return_1)


def theta_allocation_builder(str_set_0,str_set_1,coi):
    #This is a lazy step to handel end point index wrapping code length could
    #be reduced pointing to the index 63 for to_allocate[i][0].  
    if coi != 63:
        to_allocate=L_P([0]*1600,64)
        for i in range(len(str_set_0)):
            to_allocate[i][coi]=str_set_0[i]
            to_allocate[i][coi+1]=str_set_1[i]
        to_return=[]
        for i in range(len(to_allocate)):
            insert=''
            for x in range(len(to_allocate[i])):
                if type(to_allocate[i][x])!=type(''):
                    insert+=str(to_allocate[i][x])
                if type(to_allocate[i][x])==type(''):
                    insert+=to_allocate[i][x]
            to_return.append(insert)
        return(to_return)
    if coi == 63:
        to_allocate=L_P([0]*1600,64)
        for i in range(len(str_set_0)):
            to_allocate[i][coi]=str_set_0[i]
            to_allocate[i][0]=str_set_1[i]
        to_return=[]
        for i in range(len(to_allocate)):
            insert=''
            for x in range(len(to_allocate[i])):
                if type(to_allocate[i][x])!=type(''):
                    insert+=str(to_allocate[i][x])
                if type(to_allocate[i][x])==type(''):
                    insert+=to_allocate[i][x]
            to_return.append(insert)
        return(to_return)

def MOD_5_THETA_BREAK(op,coi):
    coi_hold=list_concat(COI_RETURN(op,coi))
    to_return=[]
    for i in range(1024):
        a_str=''
        c_str=bin_n_bit(i,'10')
        for x in range(len(c_str)):
            if c_str[x]=='0':
                a_str+=coi_hold[x][0]
            if c_str[x]=='1':
                a_str+=coi_hold[x][1]
        allocation_set=L_P(a_str,25)
        insert=t_3(theta_allocation_builder(allocation_set[0],allocation_set[1],coi))
        a_theta=theta(insert)
        if THETA_COMPARE(a_theta,op,coi)==True:
            to_return.append(insert)   
    return(to_return)

def THETA_COL_EXTRACT(a_theta,col_set):
    return(index_search(rc_con(a_theta),col_set))

def THETA_COL_INSERT(insert_val_str_set,col_set):
    to_allocate=rc_lcon(L_P([0]*1600,64))
    for i in range(len(col_set)):
        for x in range(len(to_allocate)):
            to_allocate[col_set[i]]=insert_val_str_set[i]
    to_return=[]
    for i in range(len(to_allocate)):
        if type(to_allocate[i])!=type(''):
            to_return.append('0'*25)
        if type(to_allocate[i])==type(''):
            to_return.append(to_allocate[i])
    return(rc_con(to_return))

def THETA_INVERT(op):
    data=[]
    for i in range(64):
        data.append(MOD_5_THETA_BREAK(op,i))
        print(i)
    to_return=[]
    for i in range(len(data[0])):
        for x in range(len(data[1])):
            if THETA_COMPARE(data[0][i],data[1][x],1)==True:
                i_0=THETA_COL_EXTRACT(data[0][i],[0,1])
                i_1=THETA_COL_EXTRACT(data[1][x],[2])
                to_insert=THETA_COL_INSERT(i_0+i_1,[0,1,2])
                to_check=theta(to_insert)
                if THETA_SET_COMPARE(to_check,op,[0,1])==True:
                    to_return.append(to_insert)
    to_hold=[to_return]
    for meta in range(2,63):
        insert=[]
        print(meta)
        for i in range(len(data[meta])):
            for x in range(len(to_hold[-1])):
                if THETA_COMPARE(data[meta][i],to_hold[-1][x],meta)==True:
                    i_0=THETA_COL_EXTRACT(to_hold[-1][x],range(meta+1))
                    i_1=THETA_COL_EXTRACT(data[meta][i],[meta+1])
                    to_insert=THETA_COL_INSERT(i_0+i_1,range(meta+2))
                    to_check=theta(to_insert)
                    if THETA_SET_COMPARE(to_check,op,range(meta+1))==True:
                        insert.append(to_insert)
        to_hold.append(insert)
    for i in range(len(to_hold[-1])):
        if theta(to_hold[-1][i])==op:
            return(to_hold[-1][i])

def test():
    ip=set_main_build(64,25)
    answer=THETA_INVERT(theta(ip)) 
    return(ip,answer)
Improve this answer
$\endgroup$
0
$\begingroup$

Not exactly an answer, but you may want to look at section 2.3.2.1 of "The Keccak Reference". There they represent the state as a polynomial in $$ \mathbb{F}_2[x,y,z]/(1+x^5,1+y^5,1+z^w) $$ where multiplication by $x,y,z$ gives cyclic translation in those directions. $\theta$ is explicitly given as multiplication by $$ 1+(1+y+y^2+y^3+y^4)(x+x^4z). $$ [Where the 1 copies the state, the $\sum_iy^i$ is parity in the $y$ direction, which is applied in adjacent $x$ directions ($x$ and $x^4$), one of which is shifted in the $z$ direction ($x^4z$)].

In any case, they give an outline of invertibility. Given the exposition, I would say that the designers had the geometric picture in mind and perhaps retroactively looked for assurances that $\theta$ was invertible.

Perhaps working in this setting would allow any generalizations you seek (e.g. replacing $(5,5,w)$ with other parameters).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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