 |
|
| Science Forum Index » Cryptography Forum » Slightly OT - "widening" a hash... |
|
Page 1 of 1 |
|
| Author |
Message |
| Ivan Voras... |
 Posted: Mon Oct 19, 2009 11:27 am |
|
|
|
Guest
|
For a purpose completely unrelated to cryptography I need a good but
"wide" hash function and by "wide" I mean large output, much larger
than SHA512. So I'm thinking about a possibly silly idea - what if I
misuse a short but narrow hash function such as MD4 or MD5 (speed is
also important) by applying it multiple times to the data prepended
with a counter, i.e.
H1(d) = H( '1' + d) + H('2' + d) + ... + H('10' + d) -> "1280 bit
hash"
(where "+" is string concatenation and H is e.g. MD4)
Has something like this been analyzed before and if not - are there
any obvious problems?
Also: am I missing a better way to make a wide hash? |
|
|
| Back to top |
|
|
|
| Thomas Pornin... |
| Posted: Mon Oct 19, 2009 3:45 pm |
|
|
|
Guest
|
According to Ivan Voras <ivoras at (no spam) gmail.com>:
[quote]Has something like this been analyzed before and if not - are there
any obvious problems?
[/quote]
It is called a "concatenated hash function". It has been analyzed at
length. Downside is that despite its larger output, it is not really
stronger than the base hash function alone. On the upside, it is no
weaker either.
Hence that construction may be appropriate for cryptographic purposes,
provided that you use a proper, strong base hash function (i.e. not
MD4 or MD5). For a slightly more complex construction, which is more
easily "proven" and employs both MD5 and SHA-1 (it should resist to
the break of either -- but not both), see the PRF described in the
TLS standard (RFC 5246, section 5: http://tools.ietf.org/html/rfc5246 ).
[quote]Also: am I missing a better way to make a wide hash?
[/quote]
Building a wide hash, which matches the "security level" which could
be expected from a hash value with a wide output, is not an easy task.
It actually is an active research subject and I know of no succesfull
construction so far.
If you are only after a decent protection level (e.g. "128-bit security")
then the PRF from TLS (possibly adapted to some more modern hash functions,
such as SHA-256) should be fine.
--Thomas Pornin |
|
|
| Back to top |
|
|
|
| Maaartin... |
| Posted: Tue Oct 20, 2009 7:00 am |
|
|
|
Guest
|
Thomas Pornin wrote:
[quote]Hence that construction may be appropriate for cryptographic purposes,
provided that you use a proper, strong base hash function (i.e. not
MD4 or MD5). For a slightly more complex construction, which is more
easily "proven" and employs both MD5 and SHA-1 (it should resist to
the break of either -- but not both), see the PRF described in the
TLS standard (RFC 5246, section 5: http://tools.ietf.org/html/rfc5246 ).
[/quote]
There's neither MD5 nor SHA-1 mentioned in section 5 of rfc5246
(describing TLS 1.2), there's SHA-256 instead. There's a combination
of MD5 and SHA-1 in section 5 of http://tools.ietf.org/html/rfc2246
describing TLS 1.1.
Could you provide me a pointer to a security proof for the
combination? I tried google, but without any success. |
|
|
| Back to top |
|
|
|
| Thomas Pornin... |
| Posted: Wed Oct 21, 2009 4:33 am |
|
|
|
Guest
|
According to Maaartin <grajcar1 at (no spam) seznam.cz>:
[quote]There's neither MD5 nor SHA-1 mentioned in section 5 of rfc5246
(describing TLS 1.2), there's SHA-256 instead. There's a combination
of MD5 and SHA-1 in section 5 of http://tools.ietf.org/html/rfc2246
describing TLS 1.1.
[/quote]
My bad, I should have checked more thoroughly. The PRF which combines
MD5 and SHA-1 is used in TLS 1.0 (RFC 2246) and TLS 1.1 (RFC 4346),
whereas TLS 1.2 (RFC 5246) uses SHA-256 only.
[quote]Could you provide me a pointer to a security proof for the
combination? I tried google, but without any success.
[/quote]
For the security of the PRF construction with HMAC, see for instance:
"HMAC is a Randomness Extractor and Applications to TLS" (Fouque,
Pointcheval and Zimmer, ASIACCS'0 :
http://www.di.ens.fr/~zimmer/pub/asiaccs08.pdf
As for the combination itself: in TLS 1.0 and 1.1, there are two PRF,
one with MD5 and one with SHA-1, and they use distinct inputs: the
"shared secret" is split into two halves, nominally independant, each
used as input for one of the PRF. Thus, the combination is no weaker
than the strongest of the PRF. For a more rigourous formulation, the
article title "On the Security of RSA Encryption in TLS" (Jonsson and
Kaliski, CRYPTO 2002) may be an appropriate reference.
--Thomas Pornin |
|
|
| Back to top |
|
|
|
| Joseph Ashwood... |
| Posted: Fri Oct 23, 2009 4:53 am |
|
|
|
Guest
|
"Ivan Voras" <ivoras at (no spam) gmail.com> wrote in message
news:c9c640e5-43e8-446e-a9ad-ce8291641dc8 at (no spam) d4g2000vbm.googlegroups.com...
[quote]Also: am I missing a better way to make a wide hash?
[/quote]
Probably. It isn't difficult to make one that is reasonable (security if a
different matter). Take Rijndael, choose a sufficiently large block/enough
rounds, and use the Miyaguchi-Preneel compression function. Take a look at
the Whirlpool hash function for how to do this.
Joe |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Thu Nov 26, 2009 7:11 pm
|
|