[Cryptography] please dont weaken pre-image resistance of SHA3 (Re: NIST about to weaken SHA3?)
On Tue, Oct 01, 2013 at 12:47:56PM -0400, John Kelsey wrote: The actual technical question is whether an across the board 128 bit security level is sufficient for a hash function with a 256 bit output. This weakens the proposed SHA3-256 relative to SHA256 in preimage resistance, where SHA256 is expected to provide 256 bits of preimage resistance. If you think that 256 bit hash functions (which are normally used to achieve a 128 bit security level) should guarantee 256 bits of preimage resistance, then you should oppose the plan to reduce the capacity to 256 bits. I think hash functions clearly should try to offer full (256-bit) preimage security, not dumb it down to match 128-bit birthday collision resistance. All other common hash functions have tried to do full preimage security so it will lead to design confusion, to vary an otherwise standard assumption. It will probably have bad-interactions with many existing KDF, MAC, merkle-tree designs and combined cipher+integrity modes, hashcash (partial preimage as used in bitcoin as a proof of work) that use are designed in a generic way to a hash as a building block that assume the hash has full length pre-image protection. Maybe some of those generic designs survive because they compose multiple iterations, eg HMAC, but why create the work and risk to go analyse them all, remove from implementations, or mark as safe for all hashes except SHA3 as an exception. If MD5 had 64-bit preimage, we'd be looking at preimages right now being expensive but computable. Bitcoin is pushing 60bit hashcash-sha256 preimage every 10mins (1.7petaHash/sec network hashrate). Now obviously 128-bits is another scale, but MD5 is old, broken, and there maybe partial weakenings along the way. eg say design aim of 128 slips towards 80 (in another couple of decades of computing progress). Why design in a problem for the future when we KNOW and just spent a huge thread on this list discussing that its very hard to remove upgrade algorithms from deployment. Even MD5 is still in the field. Is there a clear work-around proposed for when you do need 256? (Some composition mode or parameter tweak part of the spec?) And generally where does one go to add ones vote to the protest for not weakening the 2nd-preimage propoerty? Adam ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] please dont weaken pre-image resistance of SHA3 (Re: NIST about to weaken SHA3?)
Adam,
I guess I should preface this by saying I am speaking only for myself. That's
always true here--it's why I'm using my personal email address. But in
particular, right now, I'm not *allowed* to work. But just speaking my own
personal take on things
We go pretty *overwhelming* feedback in this direction in the last three weeks.
(For the previous several months, we got almost no feedback about it at all,
despite giving presentations and posting stuff on hash forum about our plans.).
But since we're shut down right now, we can't actually make any decisions or
changes. This is really frustrating on all kinds of levels.
Personally, I have looked at the technical arguments against the change and I
don't really find any of them very convincing, for reasons I described at some
length on the hash forum list, and that the Keccak designers also laid out in
their post. The core of that is that an attacker who can't do 2^{128} work
can't do anything at all to SHA3 with a 256 bit capacity that he couldn't also
do to SHA3 with a 512 bit capacity, including finding preimages.
But there's pretty much zero chance that we're going to put a standard out that
most of the crypto community is uncomfortable with. The normal process for a
FIPS is that we would put out a draft and get 60 or 90 days of public comments.
As long as this issue is on the table, it's pretty obvious what the public
comments would all be about.
The place to go for current comments, if you think more are necessary, is the
hash forum list. The mailing list is still working, but I think both the
archives and the process of being added to the list are frozen thanks to the
shutdown. I haven't looked at the hash forum since we shut down, so when we
get back there will be a flood of comments there. The last I saw, the Keccak
designers had their own proposal for changing what we put into the FIPS, but I
don't know what people think about their proposal.
--John, definitely speaking only for myself
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] please dont weaken pre-image resistance of SHA3 (Re: NIST about to weaken SHA3?)
On 14/10/13 17:51 PM, Adam Back wrote: On Tue, Oct 01, 2013 at 12:47:56PM -0400, John Kelsey wrote: The actual technical question is whether an across the board 128 bit security level is sufficient for a hash function with a 256 bit output. This weakens the proposed SHA3-256 relative to SHA256 in preimage resistance, where SHA256 is expected to provide 256 bits of preimage resistance. If you think that 256 bit hash functions (which are normally used to achieve a 128 bit security level) should guarantee 256 bits of preimage resistance, then you should oppose the plan to reduce the capacity to 256 bits. I think hash functions clearly should try to offer full (256-bit) preimage security, not dumb it down to match 128-bit birthday collision resistance. All other common hash functions have tried to do full preimage security so it will lead to design confusion, to vary an otherwise standard assumption. It will probably have bad-interactions with many existing KDF, MAC, merkle-tree designs and combined cipher+integrity modes, hashcash (partial preimage as used in bitcoin as a proof of work) that use are designed in a generic way to a hash as a building block that assume the hash has full length pre-image protection. Maybe some of those generic designs survive because they compose multiple iterations, eg HMAC, but why create the work and risk to go analyse them all, remove from implementations, or mark as safe for all hashes except SHA3 as an exception. I tend to look at it differently. There are ephemeral uses and there are long term uses. For ephemeral uses (like HMACs) then 128 bit protection is fine. For long term uses, one should not sign (hash) what the other side presents (put in a nonce) and one should always keep what is signed around (or otherwise neuter a hash failure). Etc. Either way, one wants here a bit longer protection for the long term hash. That 'time' axis is how I look at it. Simplistic or simple? Alternatively, there is the hash cryptographer's outlook, which tends to differentiate collisions, preimages, 2nd preimages and lookbacks. From my perspective the simpler statement of SHA3-256 having 128 bit protection across the board is interesting, perhaps it is OK? If MD5 had 64-bit preimage, we'd be looking at preimages right now being expensive but computable. Bitcoin is pushing 60bit hashcash-sha256 preimage every 10mins (1.7petaHash/sec network hashrate). I might be able to differentiate the preimage / collision / 2nd pi stuff here if I thought about if for a long time ... but even if I could, I would have no confidence that I'd got it right. Or, more importantly, my design gets it right in the future. And as we're dealing with money, I'd *want to get it right*. I'd actually be somewhat happier if the hash had a clear number of 128. Now obviously 128-bits is another scale, but MD5 is old, broken, and there maybe partial weakenings along the way. eg say design aim of 128 slips towards 80 (in another couple of decades of computing progress). Why design in a problem for the future when we KNOW and just spent a huge thread on this list discussing that its very hard to remove upgrade algorithms from deployment. Even MD5 is still in the field. Um. Seems like this argument only works if people drop in SHA3 without being aware of the subtle switch in preimage protection, *and* they designed for it earlier on. For my money, let 'em hang. Is there a clear work-around proposed for when you do need 256? (Some composition mode or parameter tweak part of the spec?) Use SHA3-512 or SHA3-384? What is the preimage protection of SHA3-512 when truncated to 256? It seems that SHA3-384 still gets 256. And generally where does one go to add ones vote to the protest for not weakening the 2nd-preimage propoerty? For now, refer to Congress of the USA, it's in Washington DC. Hopefully, it'll be closed soon too... iang ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
