I've been working on developing alternative documentation for the sub-function chi() in SHA-3. My main question (Expanded below): Can the method I used for chi() can be applied to the function theta()?
My method was to change a single bit in the input of chi() to determine its effect on the output. Below is a sample input/output to chi() for SHA-3.
set_input= ['1000000000000000000000000000000000000000000000000000000000000000',
'1000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
##
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
##
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
##
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
##
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000']
set_output= ['1000000000000000000000000000000000000000000000000000000000000000',
'1000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'1000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
##
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
##
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
##
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
##
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000']
The import thing to note is that the only input bits that were manipulated were contained in the first five lanes of the input, and further more in these lanes only the left most bits were manipulated. This holds for all 5 sets (of 5 64 bit lanes) that comprise the total input of chi().
It's trivial to check 2^5 number of possible set values. But what was more interesting was that chi() was an one-to-one function. A characteristic that was already brought up here but I still wanted to see for myself. The before and after scripts are located below. There were a few internal functions I had to add to maintain how the data was structured.
def chi_old(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 _chi_new(s):
set_0=['00000','00101','01011','01010',
'10110','10111','10001','10100',
'01101','01000','01110','01111',
'00011','00010','01100','01001',
'11010','11101','10011','10000',
'11100','11111','11001','11110',
'00110','00001','00111','00100',
'11000','11011','10101','10010']
set_1=['00000','00001','00011','00010',
'00110','00111','00101','00100',
'01100','01101','01111','01110',
'01010','01011','01001','01000',
'11000','11001','11011','11010',
'11110','11111','11101','11100',
'10100','10101','10111','10110',
'10010','10011','10001','10000']
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 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 rc_con(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)
to_return=[]
to_iter=L_P(s,5)
for i in range(len(to_iter)):
insert=[]
convert=rc_con(to_iter[i])
for x in range(len(convert)):
insert.append(set_0[set_1.index(convert[x])])
insert=rc_con(insert)
to_return.append(insert)
return(list_concat(to_return))
Below is the integer mapping for anyone who is interested.
(0, 0)
(5, 1)
(11, 3)
(10, 2)
(22, 6)
(23, 7)
(17, 5)
(20, 4)
(13, 12)
(8, 13)
(14, 15)
(15, 14)
(3, 10)
(2, 11)
(12, 9)
(9, 8)
(26, 24)
(29, 25)
(19, 27)
(16, 26)
(28, 30)
(31, 31)
(25, 29)
(30, 28)
(6, 20)
(1, 21)
(7, 23)
(4, 22)
(24, 18)
(27, 19)
(21, 17)
(18, 16)
Now if we apply the same ideas to theta() we immediately notice that we're no longer isolated to 5 bit chunks. Rather we have to consider all 25 lane columns. Now $2^{25}$ is a fairly manageable number, and also unfortunately a naive. Given the left circular rotations contained in theta() the column mappings would very likely be unique. So then $64*(2^{25})$ is a more appropriate number, and slightly less manageable, but assuming there is no symmetry that can be leveraged.
I also have to consider the fact that I'm making some very risky assumptions, the first being that while I can bound the input/output columns that are manipulated, I can't bound the minimum column sample width, in this case it's 2, by the left circular rotation of theta(). Yikes, $64*(2^{25})$ is incorrect. Looks like $64*((2^{25})^2)$ is more accurate, and unfortunately entirely too large for me to work with. However in this instance we're still only mapping to $2^{25}$ unique values. I welcome all practical ideas past this point.
Finally if the answer to this question is correct, and since we know from above chi() is reversible, and it's trivial to see that rho(), pi(), and iota() are also reversible. If you keep the bit string (input) you intend to hash $<576$ bits, because there is currently no open source SHA-3 implementation bit compliant see here. I get the sense that someone could make an argument that SHA-3 as a whole is reversible? I welcome dissenting opinions with open arms.