Hashing of short fixed length messages
in [Cryptography]
|
From: Tom St Denis on 14 Jun 2010 07:56 On Jun 14, 6:24 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > 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.[snip] > > Certainly I don't understand your goal. Normally one hashes something > to something shorter. You have very short length to start with. To how > many bytes you want to hash or do you want a bijective mapping (in > which case any established block cipher would naturally provide such a > one but there might be other possibilities, I suppose)? Maybe his application domain space is smaller than 2^128 and he wants a one-way function? Hint: mapping passwords.
From: Paul Rubin on 14 Jun 2010 13:24 Maaartin <grajcar1(a)seznam.cz> writes: > 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: Can I ask what the application is, where speed is so important? If it's for passwords or key diversification, slow speed may even be a virtue. 0. Compute md5(x). AFAIK, MD5 is still secure w.r.t. the preimage, isn't it? Probably ok in practice, but MD5 is deprecated and if it's for a high-security application, I'd stick to something standard. Note MD5 does have a theoretical preimage attack (Sasaki and Aoki, Eurocrypt 2009) which is not practical, but attacks only get better as they say. 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. You mean just use the compression function once. Given MD5's problems I can't help wonder if the second compression isn't more useful than it it would be if the compression function worked as intended. 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. If AES is an ideal cipher, this should be ok. Assuming only that AES is a PRP, though I don't see a way to turn a break against it into a break against AES. 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. If k is secret, then fine, but then it's not a hash function, since you have to keep the key secret. With reasonable constraints on the amount of hashes available to the attacker, You don't even need the (x ^) because of the PRP-PRF switching lemma. If k is public, you're in situation 2 again.
From: Tom St Denis on 14 Jun 2010 13:32 On Jun 14, 1:24 pm, Paul Rubin <no.em...(a)nospam.invalid> wrote: > Maaartin <grajc...(a)seznam.cz> writes: > > 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: > > Can I ask what the application is, where speed is so important? If it's > for passwords or key diversification, slow speed may even be a virtue. > > 0. Compute md5(x). AFAIK, MD5 is still secure w.r.t. the preimage, > isn't it? > > Probably ok in practice, but MD5 is deprecated and if it's for a > high-security application, I'd stick to something standard. Note MD5 > does have a theoretical preimage attack (Sasaki and Aoki, Eurocrypt > 2009) which is not practical, but attacks only get better as they say. > > 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. > > You mean just use the compression function once. Given MD5's problems I > can't help wonder if the second compression isn't more useful than it > it would be if the compression function worked as intended. > > 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. > > If AES is an ideal cipher, this should be ok. Assuming only that AES is > a PRP, though I don't see a way to turn a break against it into a break > against AES. There was a eurocrypt paper that surveyed 64 permutations of turning a cipher into a hash. Of all of them but 16 are trivially weak, of those I think only a few are ideally strong [assuming a good PRP]. I totally forget the year or authors or title ... but it's in the 90s somewhere iirc. AFAIK S = x xor cipher_x(x) is not one of the secure hash functions. Tom
From: Tom St Denis on 14 Jun 2010 13:36 On Jun 14, 1:32 pm, Tom St Denis <t...(a)iahu.ca> wrote: > On Jun 14, 1:24 pm, Paul Rubin <no.em...(a)nospam.invalid> wrote: > > > > > > > Maaartin <grajc...(a)seznam.cz> writes: > > > 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: > > > Can I ask what the application is, where speed is so important? If it's > > for passwords or key diversification, slow speed may even be a virtue. > > > 0. Compute md5(x). AFAIK, MD5 is still secure w.r.t. the preimage, > > isn't it? > > > Probably ok in practice, but MD5 is deprecated and if it's for a > > high-security application, I'd stick to something standard. Note MD5 > > does have a theoretical preimage attack (Sasaki and Aoki, Eurocrypt > > 2009) which is not practical, but attacks only get better as they say. > > > 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. > > > You mean just use the compression function once. Given MD5's problems I > > can't help wonder if the second compression isn't more useful than it > > it would be if the compression function worked as intended. > > > 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. > > > If AES is an ideal cipher, this should be ok. Assuming only that AES is > > a PRP, though I don't see a way to turn a break against it into a break > > against AES. > > There was a eurocrypt paper that surveyed 64 permutations of turning a > cipher into a hash. Of all of them but 16 are trivially weak, of > those I think only a few are ideally strong [assuming a good PRP]. I > totally forget the year or authors or title ... but it's in the 90s > somewhere iirc. > > AFAIK S = x xor cipher_x(x) is not one of the secure hash functions. > > Tom Found it: http://www.cosic.esat.kuleuven.be/publications/article-48.ps Turns out #7 from Table 3 is H_i = H_{i-1} xor M_i xor E_{M_i}(H_{i-1}) Which is close to the OPs model. Where H_{i-1} might as well be zero, the hash H = x xor AES(x, x) should in theory be secure provided x is <= 16 bytes in length. Tom
From: Tom St Denis on 14 Jun 2010 13:40
On Jun 14, 1:36 pm, Tom St Denis <t...(a)iahu.ca> wrote: > On Jun 14, 1:32 pm, Tom St Denis <t...(a)iahu.ca> wrote: > > > > > > > On Jun 14, 1:24 pm, Paul Rubin <no.em...(a)nospam.invalid> wrote: > > > > Maaartin <grajc...(a)seznam.cz> writes: > > > > 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: > > > > Can I ask what the application is, where speed is so important? If it's > > > for passwords or key diversification, slow speed may even be a virtue.. > > > > 0. Compute md5(x). AFAIK, MD5 is still secure w.r.t. the preimage, > > > isn't it? > > > > Probably ok in practice, but MD5 is deprecated and if it's for a > > > high-security application, I'd stick to something standard. Note MD5 > > > does have a theoretical preimage attack (Sasaki and Aoki, Eurocrypt > > > 2009) which is not practical, but attacks only get better as they say.. > > > > 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. > > > > You mean just use the compression function once. Given MD5's problems I > > > can't help wonder if the second compression isn't more useful than it > > > it would be if the compression function worked as intended. > > > > 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. > > > > If AES is an ideal cipher, this should be ok. Assuming only that AES is > > > a PRP, though I don't see a way to turn a break against it into a break > > > against AES. > > > There was a eurocrypt paper that surveyed 64 permutations of turning a > > cipher into a hash. Of all of them but 16 are trivially weak, of > > those I think only a few are ideally strong [assuming a good PRP]. I > > totally forget the year or authors or title ... but it's in the 90s > > somewhere iirc. > > > AFAIK S = x xor cipher_x(x) is not one of the secure hash functions. > > > Tom > > Found it: > > http://www.cosic.esat.kuleuven.be/publications/article-48.ps > > Turns out #7 from Table 3 is > > H_i = H_{i-1} xor M_i xor E_{M_i}(H_{i-1}) > > Which is close to the OPs model. Where H_{i-1} might as well be zero, > the hash H = x xor AES(x, x) should in theory be secure provided x is > <= 16 bytes in length. Actually sorry #9 is closest (multitasking fail) where H_{i-1} can't be zero (but can be anything else). So H = x xor AES(x xor 0xDEADBEEF, x); Would be fine. Or for the more sensitive in the crowd H = x xor AES(x xor 0xEA71EAF, x); Should do :-) Tom |