0
$\begingroup$

I am having difficulties understanding a sponge construction, as I don't really understand whether the long internal state of a sponge construction is compressed in the squeeze phase, or whether bits are extracted from it.

So like I always do with things I don't understand: I coded a simple prototype.

So is this an example of a sponge construction, or did I not understand it correctly and code some hot garbage?

I read from Jean-Phillipe Aumassons book "serious cryptography" that if you need a longer hash value, you can just apply f again. Is the FSR-mechanism to extend the hash value meant with that? But then I also read that f compresses the state, so I'm not really sure what to believe:

def f(state):
    for i in range(len(state)):
        state[i]=((state[i]+state[i-2])+state[i-3]^state[i-1])%256
        state[i]=(state[i]^state[i]>>1^state[i]<<4^state[i]<<5&state[i]>>3|state[i]>>5)%256
    return state

def FSR(state):
    return((state[-9]^state[-2]+state[-8]^state[-4]^~state[-18]+~state[-7]^~state[-14])%256)

def sponge(data:list,hashlen):
    while (len(data)<400 | len(data)%200!=0):
        data.append(len(data))
    state = [i for i in range(200)]
    data = [data[i:(i+200)] for i in range(0,len(data),200)]
    for i in range(len(data)):
        for j in range(len(state)):
            state[j]^=data[i][j]
        state = f(state)

    hash_val = []

    while len(hash_val)<hashlen:
        hash_val.append(FSR(state))
        state = f(state)

    return "".join(hex(hash_val[i]).removeprefix("0x") for i in range(len(hash_val)))

print(sponge([0],128))
print()
print(sponge([1],128))

I would really appreciate any answers, as I am only beginning to understand this concept and I can learn a lot from this forum.

$\endgroup$

1 Answer 1

0
$\begingroup$

I don't really understand whether the long internal state of a sponge construction is compressed in the squeeze phase, or whether bits are extracted from it.

In a pure sponge construction of a hash, the later: the output is directly by extracting part of the state (e.g. at start of the block up to capacity) after a permutation of the state (the final one of the absorption phase, or later permutations for longer output).


So is this an example of a sponge construction ?

No. That's not a sponge construction, for at least two reasons.

  1. The sponge construction uses a state transformation that's a public pseudo-random permutation. Here the closest thing is the f function, but it's not a permutation. Proof: state[i] of 0x42 and 0x61 yield the same transformed value 0x43 after this line:
    state[i]=(state[i]^state[i]>>1^state[i]<<4^state[i]<<5&state[i]>>3|state[i]>>5)%256
    
  2. The amount of data absorbed for each input block (the rate) equals the state size. If f was a public permutation with efficient inversion, that would allow at least a collision attack. In a secure sponge, the rate is lower than the state size (e.g. by twice some security parameter).

As an aside, in the code the output of the hash is thru an extra transformation FSR. Perhaps that's to fix the marked non-uniformity of the state after the state transformation.


I also read that f compresses the state.

In a pure sponge construction, the state transformation is a reversible permutation, thus it does not compress the state. The absorption phase compresses the message into the state, with help of the state transformation. That transformation is applied for each (padded) message segment, after it's XORed into the (start of) the state.

$\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.