Re: Question about hashing algorithms

From: Milan VXdgsvt (milan_vxdgsvt_at_seznam.cz)
Date: 08/27/05 

Date: Sat, 27 Aug 2005 14:34:02 +0000 (UTC)

bigzaphod@gmail.com wrote:

> Are any hashing algorithms that are secure for short data and have
> short signatures? As I understand it, SHA-1, MD5, etc. were pretty
> much designed to work for any size of data. Sometimes that seems like
> overkill, though. If I have small bits of data (say, a few kilobytes
> or so) and I want to verify each chunk with a hash, it seems a little
> wasteful to require a 160 bit hash that matches up with what might
> only be 2K of data most of the time.

It all depends on how much effort should it take for the attacker to
submit fake data. Sadly, this only depends on the signature size, not
on the data size.
I suggest using a Merkle Tree hash, such as in DC++ where they have
chosen Tiger Tree Hash. You split the file in 1KB chunks, each is
hashed. Each pair of successive hashes is concatenated, and a hash of
those computed. This forms a higher level of hashes. This is repeated
all the way up to create a single ("root") hash for the whole file.
You only need to transfer a single hash for any subtree, be it 1KB or
1MB. You can also verify that a lower-level hashes are right, if you
already know the higher-level, e.g. the root.
This is all explained at
http://www.open-content.net/specs/draft-jchapweske-thex-02.html
or in the DC++ source code (DCPlusPlus project on SourceForge).

  Milan

Relevant Pages

  • RE: [7.8.2002 44916] Notice of Copyright Infringement]
    ... Appending a single bit onto the end of the file makes a different hash. ... and you no longer match the hashes. ... The only way to prove you're breaking copyright is to download at ... |"real" warezed version of whatever movie. ...
    (Vuln-Dev)
  • Re: ACCEPT and the SCREEN SECTION.
    ... General-purpose hashes, for hash tables and similar data structures, ... In short, cryptographic hashes like MD5 are used to verify data, ... if a client asks for and receives a chunk ...
    (comp.lang.cobol)
  • Re: what is probability to create two equal hashes for md5 algorithm
    ... Other than that, if the hash is statistically good, the longer the hash, the ... few cases the hashes match. ... md5 and crc32)? ... How much does it cost to compare two hashes? ...
    (sci.crypt)
  • Re: Parsing problem
    ... > I get into hashes I get a headache. ... First off a 'hash' is simply an 'associative array'. ... They are in turn a reference to a hash. ... a punchcard column formated cobol wingDingDingDing style ...
    (perl.beginners)
  • Re: Is MD5 outdated ?
    ... >> produce identical hashes, never mind hashes differing by 1 bit? ... > bit will themselves differ in roughly half their bits, ... > in one crucial way and yet hash to the same digest is far easier said ... > desired way and yet produce the same hash. ...
    (sci.crypt)