Score:2

Clarification about the iota function of SHA-3

cn flag

I am trying to implement SHA-3 using this document and have a question about the iota step.

This step consists in a single XOR between the central (0, 0) lane of the state (illustration of the state p.8 if needed) and a round constant. In other terms:

for z in [0, w[:
    let new_state(0, 0, z) = state(0, 0, z) ^ RC[z]

where RC is viewed as a bit string.

The first round constant of the first round is 1, thus only one bit will be changed. As it can be seen in this document providing test vectors, we have in round #0:

After Chi
    00 00 00 00 00 00 00 00 ...
After Iota
    01 00 00 00 00 00 00 00 ... (following is equal to above)

However, there is something I don't understand: the bit that is changed in those test vectors is the eighth one, but our round constant is a 1 written on w-bits. If $w=8$ (implying a 200-bits message), everything is fine, but in the previous link, we have a message of 1600 bits, hence $w=64$. How can XOR-ing this 64-bits 0...01 change the eighth bit of the lane ?

EDIT: I will add my code below (it is still work in progress):

class Keccak(object):

    def __init__(self):
        self.l = 6
        self.w = pow(2, self.l)

        self.state = [[[0 for x in range(5)] for y in range(5)] for z in range(self.w)]
        self.tmp_state = [[[0 for x in range(5)] for y in range(5)] for z in range(self.w)]


    def init_state(self, S):
        for x in range(5):
            for y in range(5):
                for z in range(self.w):
                    self.set_state(x, y, z, int(S[self.w*(5*y + x) + z], 2))

    def init_tmp_state(self):
        for x in range(5):
            for y in range(5):
                for z in range(self.w):
                    self.set_tmp_state(x, y, z, 0)


    def index_processing(self, x, y, z):
        return (z % self.w, (y + 2) % 5, (x + 2) % 5)
        

    def get_state(self, x, y, z):
        x, y, z = self.index_processing(x, y, z)
        return self.state[x][y][z]

    def set_state(self, x, y, z, v):
        x, y, z = self.index_processing(x, y, z)
        self.state[x][y][z] = v


    def get_tmp_state(self, x, y, z):
        x, y, z = self.index_processing(x, y, z)
        return self.tmp_state[x][y][z]

    def set_tmp_state(self, x, y, z, v):
        x, y, z = self.index_processing(x, y, z)
        self.tmp_state[x][y][z] = v


    def state_to_string(self):
        bit_string = []
        for y in range(5):
            for x in range(5):
                for z in range(self.w):
                    bit_string.append(str(self.get_state(x, y, z)))

        return ''.join(bit_string)


    def rc(self, t):
        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] ^= R[8]
            R[4] ^= R[8]
            R[5] ^= R[8]
            R[6] ^= R[8]
            R = R[:8]

        return R[0]


    def iota(self, i):
        RC = [0 for j in range(self.w)]
        for j in range(self.l + 1):
            RC[pow(2, j) - 1] = self.rc(j + 7*i)

        for z in range(self.w):
            self.set_state(0, 0, z, self.get_state(0, 0, z) ^ RC[z])




def test_iota():
    initial_state = "0000000000000000D2D2D2D2D2D2D2D20000000000000000E8E8E8E8E8E8E8E83A3A3A3A3A3A3A3A535353535353535300000000000000001D1D1D1D1D1D1D1D4E4E4E4E4E4E4E4E00000000000000004141414141414141E8E8E8E8E8E8E8E80000000000000000414141414141414126262626262626261D1D1D1D1D1D1D1D0000000000000000474747474747474718181818181818184747474747474747E8E8E8E8E8E8E8E835353535353535350000000000000000AFAFAFAFAFAFAFAF1212121212121212"
    initial_state = bin(int(initial_state, 16))[2:].zfill(1600)

    keccak = Keccak()
    keccak.init_state(initial_state)
    keccak.iota(0)
    result = keccak.state_to_string()

    correct_result = "0100000000000000D2D2D2D2D2D2D2D20000000000000000E8E8E8E8E8E8E8E83A3A3A3A3A3A3A3A535353535353535300000000000000001D1D1D1D1D1D1D1D4E4E4E4E4E4E4E4E00000000000000004141414141414141E8E8E8E8E8E8E8E80000000000000000414141414141414126262626262626261D1D1D1D1D1D1D1D0000000000000000474747474747474718181818181818184747474747474747E8E8E8E8E8E8E8E835353535353535350000000000000000AFAFAFAFAFAFAFAF1212121212121212"
    correct_result = bin(int(correct_result, 16))[2:].zfill(1600)

    print("\tIota:\t" + str(result == correct_result))
    
    print(result[0:64] + '\n\n' + correct_result[0:64])

The test prints:

    Iota:   False
1000000000000000000000000000000000000000000000000000000000000000

0000000100000000000000000000000000000000000000000000000000000000
kelalaka avatar
in flag
Figure 2, the position of indexes is not standard. [0,0,1] is the center of the front slice. So when printing this will be printed.
Katoptriss avatar
cn flag
I also thought I may have messed up the indexing, but I tested my string_to_state and state_to_string functions using sections 3.1.2 and 3.1.3, and they seemed correct. But I also don't think the issue could come from anywhere else than there. I will edit to add my code. Additionally, in section 3.1.3, the bit string resulting from the state is first constructed by concatenating state(0, 0, 0) to state(0, 0, 63) : doesn't this still mean that the bit changed and later printed is the eighth one, in state(0, 0, 7) ?
Katoptriss avatar
cn flag
A thought that just occured to me: maybe this is just a silly endianness problem ? But the pi and khi functions I wrote both pass their tests and give the expected result, so I don't know about changing the endianness. I will try just in case.
Katoptriss avatar
cn flag
Well, seems the answer was that it wasn't endianness per se, but rather "bitwise endianness" where the bits have to be taken in reverse order. Weird. But I should have read the standard more carefully.
kelalaka avatar
in flag
One should read the whole document before starting.
kelalaka avatar
in flag
You can answer your question, that is ok!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.