1
$\begingroup$

Sorry if this is elementary, but is there such a thing as a dynamic length (output) hash function? Something that would be a fast way to calculate hashes and output different lengths of strings for the output.

This may give away some of the length of the message, and could be undesirable for many other reasons, but would possibly avoid collisions?

$\endgroup$
  • $\begingroup$ It would destroy one basic goal, to have limited length hashes for arbitrary length inputs with good collision, 1st preimage, 2nd preimage properties. I suppose you could allow a range of lengths, say 512 to 4096 bits, but it is unclear how much of an advantage this would give to a principled way of avoiding collisions. $\endgroup$ – kodlu Mar 27 '18 at 22:51
  • 1
    $\begingroup$ Look into the SHAKE functions of the new SHA3. en.wikipedia.org/wiki/SHA-3 $\endgroup$ – mikeazo Mar 27 '18 at 22:53
  • 3
    $\begingroup$ mikeazo is right. The set of dynamic length hash functions has been given a name too: XOF, an extendable output function. They don't give away any info on the length of the message by the way. The amount of output is decoupled from the size of the input. $\endgroup$ – Maarten Bodewes Mar 27 '18 at 23:47
3
$\begingroup$

[...][I]s there such a thing as a dynamic length (output) hash function?

Yes, these are called extendable output functions (XOFs), with the most well-known instances being SHAKE128 and SHAKE256 from NIST FIPS 202. Given an arbitrary-length input, they essentially produce an arbitrary length output that you may truncate at any point and that enjoys the usual security properties for hashes.

But beware of the determinism of these functions, that is if you hash $m$ with them, and then take the first 256 and the first 512 bits in two different places, they will both share 256 bits!

[...][It] but would possibly avoid collisions?

As the names suggest, SHAKE128 aims at a 128-bit security level, meaning you'll need $2^{\min(128,d/2)}$ operations to find a collision, where $d$ is the length of the output. So why does it "only" provide 128-bit security at most? Because you can find a collision on the internal structure with $2^{128}$ operations that will result in a collision on the output stream.

$\endgroup$
  • $\begingroup$ Thank you for the articles, I'll take a look. These SHAKEs are different from fuzzy hashes, right? $\endgroup$ – Jeff Mar 28 '18 at 15:23
  • $\begingroup$ @Jeff, yes they are different. $\endgroup$ – mikeazo Mar 28 '18 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.