[Cryptography] Sha3

[John Kelsey]

On Oct 6, 2013, at 6:29 PM, Jerry Leichter <leichter at lrw.com> wrote:

> 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".

They are talking about the change to their padding scheme, in which between 2 and 4 bits of extra padding are added to the padding scheme that was originally proposed for SHA3.  A hash function that works by processing r bits at a time till the whole message is processed (every hash function I can think of works like this) has to have a padding scheme, so that when someone tries to hash some message that's not a multiple of r bits long, the message gets padded out to r bits.  

The only security relevance of the padding scheme is that it has to be invertible--given the padded string, there must always be exactly one input string that could have led to that padded string.  If it isn't invertible, then the padding scheme would introduce collisions.  For example, if your padding scheme was "append zeros until you get the message out to a multiple of r bits," I could get collisions on your hash function by taking some message that was not a multple of r bits, and appending one or more zeros to it.  Just appending a single one bit, followed by as many zeros as are needed to get to a multiple of r bits makes a fine padding scheme, so long as the one bit is appended to *every* message, even those which start out a multiple of r bits long.  

The Keccak team proposed adding a few extra bits to their padding, to add support for tree hashing and to distinguish different fixed-length hash functions that used the same capacity internally.  They really just need to argue that they haven't somehow broken the padding so that it is no longer invertible

They're making this argument by pointing out that you could simply stick the fixed extra padding bits on the end of a message you processed with the original Keccak spec, and you would get the same result as what they are doing.  So if there is any problem introduced by sticking those extra bits at the end of the message before doing the old padding scheme, an attacker could have caused that same problem on the original Keccak by just sticking those extra bits on the end of messages before processing them with Keccak.  

>                                                        -- Jerry

--John