12
$\begingroup$

I need a SHA3-255 or 511. What if I simply truncate a standard SHA3-256 or 512? Apart from the doubled probability of hash collision, are there any other things I should be aware of? I could also truncate one byte instead of one bit, if useful.

What I need is being able to store something different than the hash, in the same 32 bytes, or 64 bytes, so I need to sacrifice one bit to mark when the bytes represent a hash or something else.

Alternatively I could say that if the first byte, not bit, is 0xff, then the remaining ones represent something else. This should reduce the probability of hash collision, but what I would have a probability of 1/256 that a hash starts with 0xff, generating ambiguity in my encoding. I could say that if the for 4 bytes are 0xffffffff, then I would end up with probability of generating an ambiguous encoding of 1/2^32, but I would prefer having a well-defined encoding under any circumstances.

Any well known approach I'm not aware of?

$\endgroup$
  • 14
    $\begingroup$ I'm intensely curious to know why you need this. $\endgroup$ – chrylis -on strike- Sep 28 at 8:19
  • $\begingroup$ I need to identify a set or messages by a fixed length key, that must be calculated out of the messages themselves. Clearly, a hash does the job (assuming no hash collisions). Messages can be multiple kb or few bytes. Call it premature optimization or just curiosity, I'm thinking if it's possible to avoid storing the actual message in case it's smaller than the hash, so using the hashes only for longer messages and messages themselves for the short ones. But I need one bit to identify which case it is. $\endgroup$ – ragazzojp Sep 28 at 23:17
  • 2
    $\begingroup$ I'd definitely call that premature optimization, FWIW. Writing secure code is as much about writing simple, understandable code as it is writing code that's actually secure -- because the simple, understandable code will be easy to read and understand later, and easy to fix bugs in. Adding a condition based on the first bit will be ugly no matter your language, and you're not going to save much of anything -- one SHA3 call, when SHA3 is already designed to be fast. Doubly so if you ever want to interoperate with other stuff, and since you'll need 256 more bits anyway... what's the point? $\endgroup$ – Fund Monica's Lawsuit Sep 29 at 0:02
  • 2
    $\begingroup$ Sometime the point is just the discussion, yes it's probably premature optimization, but I like to thing about problems and finding solutions. For example, answers pushed me to read the NIST documents about SHA3 and I learned new things ... $\endgroup$ – ragazzojp Sep 29 at 0:20
18
$\begingroup$

With all well-regarded hash functions, the bits of the hash all have equal worth: as far as anyone knows (unless they aren't telling), the bits are not correlated. If you take $k$ bits of an $n$-bit hash, you get a $k$-bit hash function. Truncating SHA-256 to 255 bits gives you a hash that's almost as good as SHA-256: it has $2^{255}$ strength against preimage attacks and $2^{127.5}$ strength against collision attacks.

There are precedents for taking certain bits of a hash. SHA-224 and SHA-384 are obtained with calculations that are essentially the same as SHA-256 and SHA-512 respectively, just with different initial values (which shouldn't matter to the strength of the algorithm) and with the output truncated to the smaller size. Another precedent is that UUID can be constructed from 122 bits of MD5 or SHA-1 hashes (out of 128 or 160 respectively).

For SHA3, there's a cleaner construction. Instead of taking SHA3-256 and cutting off one bit, take the SHAKE256 255-bit or 248-bit output. SHAKE256 is exactly the same as SHA3-256 except for two bits near the beginning of the calculation, so it has the same security properties, but it's explicitly designed to have variable-length output. You can even use SHAKE128 instead of SHAKE256, which is slightly cheaper to compute with no meaningful security loss.

It's unlikely that there's an actual security problem with truncating a hash, but using SHAKE gives you greater confidence that nothing will go wrong. Even better, to avoid domain collisions (where two parts of the system calculate the hash of the same string for different reasons), calculate the cSHAKE output with a unique string as the customization string.

$\endgroup$
6
$\begingroup$

Apart from the slightly reduced resistances, there is no problem:

Resistances for SHA3-512;

  1. Pre-image resistance decreased to $2^{511}$ or $2^{504}$, if 1 bit or 1 byte trimmed, respectively.
  2. Secondary preimage resistance decreased to o $2^{511}$ or $2^{504}$, if 1 bit or 1 byte trimmed, respectively.
  3. Collision resistance decreased to o $\sqrt{2^{511}} = \sqrt{2}\cdot 2^{255}$ or $\sqrt{2^{504}} = 2^{252}$, if 1 bit or 1 byte trimmed, respectively.

Similarly resistances for SHA3-256;

  1. Pre-image resistance decreased to $2^{255}$ or $2^{248}$, if 1 bit or 1 byte trimmed, respectively.
  2. Secondary preimage resistance decreased to o $2^{255}$ or $2^{248}$, if 1 bit or 1 byte trimmed, respectively.
  3. Collision resistance decreased to o $\sqrt{2^{255}} = \sqrt{2}\cdot 2^{127}$ or $\sqrt{2^{248}} = 2^{124}$, if 1 bit or 1 byte trimmed, respectively.

The trimmed case resistance should be good enough for your application.

Actually, this is not uncommon, for example, SHA-224 is the truncated version of SHA-256 with different initial values that provides domain separation.

Trimming is secure as long as the generic attacks are in good bounds. We require the hash functions to have avalanche criteria on the output bits, that is a change in the any of input bits must randomly affect half of the output bits. Each bit of the hash function must depend on the input bits; removing 1 bit or 1 byte doesn't affect the results of other bits.

$\endgroup$
3
$\begingroup$

Lets get one thing out of the way: forcing one bit to 0 or 1 does not change the output size of the hash. A hash output is not a number, so the output size would not be affected.

Reducing hash output is common practice. Although maybe not a direct requirement, generally the output of a hash is considered indistinguishable from random - if the input is unknown, of course. So basically you can do with it what you want. The common thing to do is to take the leftmost bits or bytes of the hash output. You're taking the rightmost bits or bytes, and that's OK too.

As you already found out, trying to use one value out of 256 to indicate a special case is tricky. You can of course use set of bytes to escape values, but since your output size is static, you'll have to sacrifice more security for the special cases: the hashes starting with 0xFF in your case. As SHA3-512 has plenty of security, I'd just sacrifice a bit or even byte.

Finally, there is one rather odd issue with taking the leftmost bytes. You might get in trouble if you have other full hashes over the same data (the domain collision in Gilles' answer). To compensate for this, most hash functions have special bits or other constants when generating a shorter hash. Usually publishing the shorter hash is not a problem though. You could play it safe though and start off by hashing a specific magic value in advance, or by using SHAKE instead.

$\endgroup$
  • $\begingroup$ Do you know a good domain collision weakness example? Is it about beeing able to guess the pre-image if you know the input to a full hash somewhere else? $\endgroup$ – eckes Sep 28 at 15:14
  • $\begingroup$ Yes, or likewise knowing the partial hash beforehand. If you're a bit careful then you can easily avoid issues with this, but crypto is about avoiding possible weaknesses... $\endgroup$ – Maarten - reinstate Monica Sep 29 at 16:45
  • $\begingroup$ @eckes One component of an application uses SHA-256(file) as the index for a content-addressed storage system. Another component of the application uses SHA-256(file) as the encryption key to encrypt the file in a deterministic encryption scheme to keep the file content secret from the storage server (except for plaintext confirmation attacks). By combining these components, the storage server can decrypt any file! (Consider Tahoe-LAFS for an example of an application that could make this mistake, but carefully avoids it by domain separation.) $\endgroup$ – Squeamish Ossifrage Oct 21 at 2:38

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.