0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Keccak-f as a whole is reversible. $\endgroup$
    – Biv
    Feb 16, 2017 at 8:20

2 Answers 2

Reset to default
6
$\begingroup$

I'm going to expand a bit on @Biv's point about the sponge construction.

I get the sense that someone could make an argument that SHA-3 as a whole is reversible?

keccak-f is a permutation. The sponge construction allows us construct non-invertible hash functions from invertible bijective permutations. The output becomes invertible because half of the state is simply dropped from the output. If you don't consider the truncation step at the end where the capacity section is dropped, then yes, it is invertible.

To see why truncation makes the output uninvertible even if the function is an invertible permutation, take AES and encrypt a block, then set half of the ciphertext block to 0s. It will now take time exponential in the amount of dropped space in order to invert the half-ciphertext back to the original plaintext. Additionally, if you did not already know the plaintext, you have no way to validate your guesses, so each of the guesses you make has an equally valid chance of being the right plaintext.

Translating this back to hashing and the sponge construction, our "plaintext" is the hash input, and our "ciphertext" is a sha-3 hash. You could technically take your hash output, stick in the rate section of the keccak permutations state, fill the capacity section with your guess, then start to invert the permutation the appropriate number of times to find the preimage that produces such a hash. The problem is that in practice everything you "rewind" this way will not rewind back to a valid initial state (one where the capacity section is empty with your preimage in the rate section). The probability of success is related to the size of the capacity, which is chosen to be large enough to preclude any known attacks. So using this technique to find collisions is technically possible, however, the parameters have been specifically chosen to make such an attack infeasible (as well as others).

Note that this is not a bad thing; Knowing about the best attacks and setting your security parameter such that they become intractable is a good way to design a primitive. This is how key sizes for RSA and DH are selected, for example.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I was very short sighted, I hadn't considered the truncation step as being significant. Question way outside the scope of my knowledge bare with me...Wouldn't that mean whoever is generating the hash would have to make sure that the portion of the hash that does get truncated never gets stored? Really only matters if you're running through a single iteration though. $\endgroup$
    – Q-Club
    Feb 16, 2017 at 19:05
  • $\begingroup$ @back_seat_driver Basically, yes; This is why the bits from the capacity section are never output, and only the bits from the rate section are output. As a rule of thumb, if a transformation throws away information, it loses the ability to be inverted to a unique preimage. $\endgroup$
    – Ella Rose
    Feb 16, 2017 at 19:37
5
$\begingroup$

Unfortunately, this won't be the answer you expect.

I. About the bit version

because there is currently no open source SHA-3 implementation bit compliant see here.

Why do we need a bit version of SHA-3 when the minimum size of an input is a multiple of byte ? I have never heard of messages with a length of 7 bits! Thus why bother with a bit implementation when a Byte oriented one will be faster?

There are no open source SHA-3 implementations that can accurately produce hashes with inputs $\ge 576$ bits.

Pardon my French but... WTF? Do you have any ground/proof for such strong assertion? You are saying that SHA-3 implementations can not produce an accurate hash if the input is longer than 72 bytes. By the way if you look for an open source implementation in python here is one from their website (team keccak).

II. About the reversibility of Keccak-f

The fact that Keccak-f is reversible (which is the case because it is a permutation) is not a problem for SHA-3 security. You are completely ignoring the sponge construction which makes SHA-3 secure (adding the extremely fast propagation of differences): you don't know the content of the capacity.

What you have in mind are attacks that relies on solving equations to find preimages. The trouble comes from the dependencies and the number of equations that you have to satisfy to find a correct input (their number increases quadratically with the number of rounds). They have been used to construct preimage on 2 to 5 rounds over the 24! see here.

So no, I don't think that SHA-3 will be deprecated before SHA-256 is broken.

Improve this answer
$\endgroup$
6
  • $\begingroup$ "A Byte oriented one will be faster" yes, and is that not an undesired characteristics of hash functions? And because wouldn't a bit implementation necessarily byte oriented? Yes I was stupid and ignored the XOR steps in the domain extender (sponge construction). As for my inflammatory statement, it's in response to the padding ambiguity in FIPS 202 with respect to the provided test vectors. And yes I've read section B2. I've been here $\endgroup$
    – Q-Club
    Feb 16, 2017 at 18:31
  • $\begingroup$ I just can't for the life of me see how section B2 is implemented for this test vector $\endgroup$
    – Q-Club
    Feb 16, 2017 at 18:32
  • $\begingroup$ You read my answer in the linked question. SHA-224 has a bit-rate of 1152 (or 144 bytes) so you basically absorb the 144 first bytes (A3...), do the 24 rounds and apply the padding the the remaining 56 bytes left (see page 39 of the test vector) $\endgroup$
    – Biv
    Feb 16, 2017 at 21:23
  • $\begingroup$ Also pay attention at how to read the bit... they wrote it backward... 1 1 0 0 0 1 0 1 = 1010 0011 = A3. (yeah they kinda messed up there) $\endgroup$
    – Biv
    Feb 16, 2017 at 21:31
  • $\begingroup$ So are you saying there was an unnecessary conversion step that took place? As for your answer/the nist process I can follow it just fine all the way to the actual sample hash output! The problem is when I try to check my script, which is producing correct ouputs at 1600 bit inputs (according to the sample hash output provided?), I can't match with any implementation I can find. Any advice in this situation, as to where I might have went wrong? My current mode of operation is monkey-see-monkey-do! $\endgroup$
    – Q-Club
    Feb 16, 2017 at 22:23

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.