4 ms·

Another advantage is that SHA-3 just uses AND, XOR, ROT, NOT, but not SHR (logical shift right) which allows for much easier formal analysis of the algorithm!

baby 9y ago
That's not true: https://github.com/gvanas/KeccakCodePackage/blob/master/Standalone/CompactFIPS202/Keccak-readable-and-compact.c#L183 https://github.com/gvanas/KeccakCodePackage/blob/master/Stan...
- koenigdavidmj 9y ago
  Which is ROT(ate), one of the listed options, even though you have to express it with shifts when writing C.
  - baby 9y ago
    I'm not sure I understand what you two mean. 1) How does not having SHR makes it easier to audit? 2) how are sha-3 implementations actually using SHR not making the parent's comment moot?
    - an27 9y ago
      GP disputed SHR is used in the snippet you highlighted.
    - remcob 9y ago
      A rotate operation is invertible, a logic shift by itself is not. Another fun one is x ^= x >> n with n some strictly positive constant, this is also invertible. It's used a lot in the murmurhash family of non-cryptograhic hash functions.
      - oh_sigh 9y ago
        Why does invertibility matter? AND and OR are not invertible, but they are used?
        baby 9y ago
        Indeed, the whole permutation is invertible and I'm not sure why either.
        yorwba 9y ago
        Permutations are always invertible. Otherwise several different inputs will be mapped to the same output, which needlessly reduces your state space. The inverse is also required for decryption: If you encrypt as ciphertext = permutation(plaintext + key), decryption is plaintext = inverse(ciphertext) - key.
        baby 9y ago
        My question is why does Keccak not use a one-way function instead of a permutation. > The inverse is also required for decryption: If you encrypt as ciphertext = permutation(plaintext + key), decryption is plaintext = inverse(ciphertext) - key. This is not how encryption/decryption works with Keccak. Keccak is used to create a stream (it is then XORed with the plaintext or ciphertext).
        baby 9y ago
        Here's an answer: https://crypto.stackexchange.com/questions/47872/why-is-keccak-f-reversible https://crypto.stackexchange.com/questions/47872/why-is-kecc... 1) it forces you to allocate more memory (to do the Davies-Mayer construction) 2) it complicates the security analysis because you get collisions (if you do not use a permutation, it means you have an injective construction)
        baby 9y ago
        And more from http://sponge.noekeon.org/CSF-0.1.pdf http://sponge.noekeon.org/CSF-0.1.pdf section 8.1.3 screenshot here: http://i.imgur.com/4xncceB.png http://i.imgur.com/4xncceB.png
oh_sigh 9y ago
Could you comment(or provide a link) on why SHR is more difficult for formal analysis than ROT?

baby 9y ago

That's not true: https://github.com/gvanas/KeccakCodePackage/blob/master/Standalone/CompactFIPS202/Keccak-readable-and-compact.c#L183 https://github.com/gvanas/KeccakCodePackage/blob/master/Stan...

koenigdavidmj 9y ago
Which is ROT(ate), one of the listed options, even though you have to express it with shifts when writing C.
- baby 9y ago
  I'm not sure I understand what you two mean. 1) How does not having SHR makes it easier to audit? 2) how are sha-3 implementations actually using SHR not making the parent's comment moot?
  - an27 9y ago
    GP disputed SHR is used in the snippet you highlighted.
  - remcob 9y ago
    A rotate operation is invertible, a logic shift by itself is not. Another fun one is x ^= x >> n with n some strictly positive constant, this is also invertible. It's used a lot in the murmurhash family of non-cryptograhic hash functions.
    - oh_sigh 9y ago
      Why does invertibility matter? AND and OR are not invertible, but they are used?
      - baby 9y ago
        Indeed, the whole permutation is invertible and I'm not sure why either.
        yorwba 9y ago
        Permutations are always invertible. Otherwise several different inputs will be mapped to the same output, which needlessly reduces your state space. The inverse is also required for decryption: If you encrypt as ciphertext = permutation(plaintext + key), decryption is plaintext = inverse(ciphertext) - key.
        baby 9y ago
        My question is why does Keccak not use a one-way function instead of a permutation. > The inverse is also required for decryption: If you encrypt as ciphertext = permutation(plaintext + key), decryption is plaintext = inverse(ciphertext) - key. This is not how encryption/decryption works with Keccak. Keccak is used to create a stream (it is then XORed with the plaintext or ciphertext).
      - baby 9y ago
        Here's an answer: https://crypto.stackexchange.com/questions/47872/why-is-keccak-f-reversible https://crypto.stackexchange.com/questions/47872/why-is-kecc... 1) it forces you to allocate more memory (to do the Davies-Mayer construction) 2) it complicates the security analysis because you get collisions (if you do not use a permutation, it means you have an injective construction)
        baby 9y ago
        And more from http://sponge.noekeon.org/CSF-0.1.pdf http://sponge.noekeon.org/CSF-0.1.pdf section 8.1.3 screenshot here: http://i.imgur.com/4xncceB.png http://i.imgur.com/4xncceB.png

oh_sigh 9y ago

Could you comment(or provide a link) on why SHR is more difficult for formal analysis than ROT?