Hashing of short fixed length messages
in [Cryptography]
|
From: Maaartin on 13 Jun 2010 12:09 I wonder if there's a more efficient way to compute a hash when I know, that all messages are of given length, say 16 bytes. I need only (first) preimage resistance, nothing more. I'd like somebody to comment on the following possibilities: 0. Compute md5(x). AFAIK, MD5 is still secure w.r.t. the preimage, isn't it? 1. Take an algorithm like MD5 and remove the padding step. This leads to a speed-up factor of two, but I don't think it's secure. 2. Compute x ^ aes(x, x). I don't know if this is faster then computing md5(x) and have no idea how secure it is. 3. Compute x ^ aes(k, x), where k is a fixed key. This is probably faster then computing md5(x) and I have no idea how secure it is.
From: Francois Grieu on 13 Jun 2010 13:12 On 13/06/2010 18:09, Maaartin wrote: > I wonder if there's a more efficient way to compute a hash when I > know, that all messages are of given length, say 16 bytes. I need only > (first) preimage resistance, nothing more. I'd like somebody to > comment on the following possibilities: > > 0. Compute md5(x). AFAIK, MD5 is still secure w.r.t. the preimage, > isn't it? Yes. > 1. Take an algorithm like MD5 and remove the padding step. This leads > to a speed-up factor of two, but I don't think it's secure. If the input is of fixed length, the padding adds little to the security. At least, in MD5's design rationale, padding is here to protect against appendix attacks, nothing else. > 2. Compute x ^ aes(x, x). I don't know if this is faster then > computing md5(x) and have no idea how secure it is. It would be a blowout to AES if that was breakable, even with x ^ removed. > 3. Compute x ^ aes(k, x), where k is a fixed key. This is probably > faster then computing md5(x) and I have no idea how secure it is. It would be a blowout to AES if that was breakable. On machines with hardware AES support (AESENC..) this is going to be pretty fast. Francois Grieu
From: Greg Rose on 13 Jun 2010 16:18 In article <4c15118e$0$23927$426a74cc(a)news.free.fr>, Francois Grieu <fgrieu(a)gmail.com> wrote: >On 13/06/2010 18:09, Maaartin wrote: >> I wonder if there's a more efficient way to compute a hash when I >> know, that all messages are of given length, say 16 bytes. I need only >> (first) preimage resistance, nothing more. I'd like somebody to >> comment on the following possibilities: >> >> 0. Compute md5(x). AFAIK, MD5 is still secure w.r.t. the preimage, >> isn't it? > >Yes. > >> 1. Take an algorithm like MD5 and remove the padding step. This leads >> to a speed-up factor of two, but I don't think it's secure. > >If the input is of fixed length, the padding adds little to the >security. At least, in MD5's design rationale, padding is here to >protect against appendix attacks, nothing else. I agree that padding isn't important with fixed-length inputs, but based on "speed-up factor", I think he's referring to the data expansion and number of rounds. I definitely wouldn't tinker with those. Greg. --
From: Maaartin on 13 Jun 2010 17:04 On Jun 13, 10:18 pm, g...(a)nope.ucsd.edu (Greg Rose) wrote: > >> 1. Take an algorithm like MD5 and remove the padding step. This leads > >> to a speed-up factor of two, but I don't think it's secure. > > >If the input is of fixed length, the padding adds little to the > >security. At least, in MD5's design rationale, padding is here to > >protect against appendix attacks, nothing else. > > I agree that padding isn't important with > fixed-length inputs, but based on "speed-up > factor", I think he's referring to the data > expansion and number of rounds. I definitely > wouldn't tinker with those. Let me clarify what I meant: Hashing exactly 16 bytes with MD5 means two invocations of the compression function, the first one processing the data and the second one processing only the padding, which is fixed here. With respect to the data, it means doing twice as much rounds when compared to the removed padding version. I know there was a similar optimization for short messages in Luffa, which was removed when advanced to the second round of SHA3 (see Reason4Mod.pdf in http://www.sdl.hitachi.co.jp/crypto/luffa/Luffa_v2_Round2Package_20090915.zip). OTOH, as I looking at the compression function of MD5, it's bijective and trivially invertible w.r.t. the state, so the optimized version is here exactly as secure as the original one. Unless I'm overlooking something obvious. On Jun 13, 7:12 pm, Francois Grieu <fgr...(a)gmail.com> wrote: > On 13/06/2010 18:09, Maaartin wrote: > > 2. Compute x ^ aes(x, x). I don't know if this is faster then > > computing md5(x) and have no idea how secure it is. > > It would be a blowout to AES if that was breakable, even with x ^ removed.. Could you prove it or give me good hints how to do it? > > 3. Compute x ^ aes(k, x), where k is a fixed key. This is probably > > faster then computing md5(x) and I have no idea how secure it is. > > It would be a blowout to AES if that was breakable. On machines with > hardware AES support (AESENC..) this is going to be pretty fast. Again, I'd love to see a proof. I'd suppose the previous case is way easier to prove, but even that is too hard for me now.
From: Greg Rose on 13 Jun 2010 20:50
In article <234258fd-926b-4626-9bc8-05e10910323a(a)q12g2000yqj.googlegroups.com>, Maaartin <grajcar1(a)seznam.cz> wrote: >On Jun 13, 10:18�pm, g...(a)nope.ucsd.edu (Greg Rose) wrote: >> >> 1. Take an algorithm like MD5 and remove the padding step. This leads >> >> to a speed-up factor of two, but I don't think it's secure. >> >> >If the input is of fixed length, the padding adds little to the >> >security. At least, in MD5's design rationale, padding is here to >> >protect against appendix attacks, nothing else. >> >> I agree that padding isn't important with >> fixed-length inputs, but based on "speed-up >> factor", I think he's referring to the data >> expansion and number of rounds. I definitely >> wouldn't tinker with those. > >Let me clarify what I meant: > >Hashing exactly 16 bytes with MD5 means two invocations of the >compression function, the first one processing the data and the second >one processing only the padding, which is fixed here. With respect to >the data, it means doing twice as much rounds when compared to the >removed padding version. Not correct I'm afraid. The input block to MD5 is 64 bytes. The padding consists of a byte 0x80 (actually that's really just one bit), then a bunch of zeros, until the last 64 bits, which will have the length (128) in bits of the input, in some order which I can't remember at the moment. There is only one call to the compression function. >I know there was a similar optimization for short messages in Luffa, >which was removed when advanced to the second round of SHA3 (see >Reason4Mod.pdf in >http://www.sdl.hitachi.co.jp/crypto/luffa/Luffa_v2_Round2Package_20090915.zip). I can't comment on Luffa without going to look at it in more detail. Clearly something is different. Greg. -- |