[Cryptography] Sha3

[Jerry Leichter]

On Oct 5, 2013, at 6:12 PM, Ben Laurie wrote:
> I have to take issue with this:
> 
> "The security is not reduced by adding these suffixes, as this is only
> restricting the input space compared to the original Keccak. If there
> is no security problem on Keccak(M), there is no security problem on
> Keccak(M|suffix), as the latter is included in the former."
I also found the argument here unconvincing.  After all, Keccak restricted to the set of strings of the form M|suffix reveals that it's input ends with "suffix", which the original Keccak did not.  The problem is with the vague nature of "no security problem".

To really get at this, I suspect you have to make some statement saying that your expectation about last |suffix| bits of the output is the same before and after you see the Keccak output, given your prior expectation about those bits.  But of course that's clearly the kind of statement you need *in general*:  Keccak("Hello world") is some fixed value, and if you see it, your expectation that the input was "Hello world" will get close to 1 as you receive more output bits!

> In other words, I have to also make an argument about the nature of
> the suffix and how it can't have been chosen s.t. it influences the
> output in a useful way.
If the nature of the suffix and how it's chosen could affect Keccak's output in some predictable way, it would be secure.  Keccak's security is defined in terms of indistinguishability from a sponge with the same internal construction but a random round function (chosen from some appropriate class).  A random function won't show any particular interactions with chosen suffixes, so Keccak had better not either.

> I suspect I should agree with the conclusion, but I can't agree with
> the reasoning.
Yes, it would be nice to see this argued more fully.

                                                        -- Jerry