Re: [lists] Combining Hashes

[Elliott Bäck]

Kent Borg wrote:

>I admit I don't know why this might be significantly better than
>d1+d2, I was hoping someone here would.
>
>

I think there are a couple things going on here. First, since + is
concatenation, SHA-1(SHA-1(data)+data+MD5(data)) provides an input to
the hash that is three times as long as before. I'm also not familiar
with the inner workings on SHA-1 and MD-5, but the second idea here is
that they both represent (somewhat) orthogonal solution spaces, so that
the concatenation of both of them adds more dimensionality and therefore
more uniqueness.

However, I am just guessing here off the top of my head.

Thanks,
Elliott C. Bäck

607-229-0623
http://elliottback.com

[Felix Cuello]

On Fri, Feb 18, 2005 at 10:24:19AM -0500, Kent Borg wrote:
> Concatenating two different hashes, for example SHA-1 and MD5,
> ...

SHA and MD5 are weak algorithms [and we do not use it since now]. But
what about old digitally signed documents? There is a protocol to
re-sign our old digitally signed documents [hashed using SHA or MD5]?

regards,

F.

--
Félix Cuello
felix@qodiga.com
- 249 -

[exon]

Kent Borg wrote:
> Concatenating two different hashes, for example SHA-1 and MD5,
> apparently does not add as much security as one might hope.
>
> What about more complicated compositions? For example, a reader
> comment posted on Bruce Schneier's blog
> (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html)
> suggests the following:
>
> d1=SHA-1(data)
> d2=MD5(data)
> d3=SHA-1(d1+data+d2)
>
> The final digest would be d1+d2+d3
>
> (where "+" is concatenation)
>
>
> I admit I don't know why this might be significantly better than
> d1+d2, I was hoping someone here would.
>

It's not. It's just backwards compatible with buffer sizes for programs
that already handle SHA-1 (and presumably also MD5) hashes so that less
and smaller changes are required to the code.

It's really quite clever, since the input would have to collide in both
MD5 and SHA1 for it to collide in the final output.

>
> -kb
>
>

[Ivan Krstic]

Aaron Mizrachi (unmanarc) wrote:
> I dont recomend something as: HASH(HASH(data)+data) until a research of
> propietries of that where investigated and mathematical proved. The better
> method (i think) is: HASH(HASH(data)), because adds two layer... and have the
> same or more security than HASH(data).

The two options differ in speed and security. Doing h(h(m) + m) where h
is your hash function and m your message, is slow and requires m to be
buffered. It also defeats length extension and partial message attacks,
so is considered a relatively complete solution to many inherent hash
function weaknesses.

Doing h(h(m)) is faster, but you can only claim n/2 bits of security for
an otherwise n-bit hash function h. Speed for security is usually a bad
tradeoff, so I recommend h(h(m) + m) as a better approach. Schneier and
Ferguson also take this approach in "Practical Cryptography" (Wiley
Publishing, 2003).

-IK

[Frank Knobbe]

--=-bgX91wFugNngFP8ijFYL
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

On Sat, 2005-02-19 at 00:54 -0400, Aaron Mizrachi wrote:
> [...] The better=20
> method (i think) is: HASH(HASH(data)), because adds two layer... and have=
the=20
> same or more security than HASH(data).=20

That's not an improvement. If you can fiddle data so that the inner hash
has the same value as before the fiddling, the outer hash remains the
same as well -- doesn't give you anything except a false sense of
security. Kent's idea was better in that you would have to find common
collisions in both algorithms in order to keep both hashes.=20

Regards,
Frank
=20

--=-bgX91wFugNngFP8ijFYL
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (FreeBSD)

iD8DBQBCGMkdwBQKb2zelzoRArhiAJ9+PZvpf2K3z8oxQxg2H7 2TrOU8GQCfRUQM
LL90HQ+llY8mE3NKYneESZg=
=pZqW
-----END PGP SIGNATURE-----

--=-bgX91wFugNngFP8ijFYL--

[Joel Maslak]

On Sat, 19 Feb 2005, Felix Cuello wrote:

> SHA and MD5 are weak algorithms [and we do not use it since now]. But
> what about old digitally signed documents? There is a protocol to
> re-sign our old digitally signed documents [hashed using SHA or MD5]?

Not really.

One solution if someone has a large store of digitally signed documents
where the original signer is not available is to rehash them with a better
algorithm and use that hash to create a digital timestamp (of document +
original signature) that the document existed before this was easily
exploitable. Then the original signature is still preserved and can be
verified, knowing that if there is a new timestamp of whatever date your
risk assessment decides is too late to be secure any longer, that then
the document was not compromised by these weaknesses.

That assumes of course that these are not trivial weaknesses to exploit.

I still advocate using multiple hashes and public key algorithms to sign
documents - for instance, 5 years ago I would have said to use RSA + MD5
and DSA + SHA1 to create two separate digital signatures for each
document. I would have said the security was mathematically as strong as
the strongest individual signature. I would not say that "Well, SHA1 is
168 bits and MD5 is 128 bits, so the security is 168+128 bits." I would
have said, "I don't want to bet everything on the fact that there isn't
someone that finds a novel way to crack one of these algorithms due to a
weakness no one previously knew about." None of the mathematical proofs
of strength can account for the "lucky break", but I can account for it
somewhat with risk management and multiple algorithms.

--
Joel