3
$\begingroup$

I am looking to implement the Fortuna algorithm (https://www.schneier.com/fortuna.pdf) on a system with very restrictive memory constraints, using AES-128 as the underlying cipher.

As the key size is only 128 bits, using a 256-bit entropy pool hashing algorithm to maintain each pool would seem to be excessive (and a waste of memory). I would like to use a hashing algorithm for which I only need to maintain 128 bits of state information for each pool. Given this, I have a couple of questions:

Would it be possible to use something like SHA-256, but only save (and restore) 128 bits of the internal state between invocations? Would this somehow risk losing entropy in the process, or produce other undesirable effects?

Alternately, the crypto library I'm using also supports MD5, which does only require 128 bits of internal state. Would it be better to use MD5 for this application, despite its potential weaknesses compared to SHA-2 hashes, or would SHA-256 be stronger, even when maintaining only half its internal state between calls?

$\endgroup$
  • $\begingroup$ Just to be sure: from the sparse information present in the question, I understand you need multiple invocations of SHA-256 because you want to implement a Password Based Key Derivation Function (PBKDF)? $\endgroup$ – Maarten Bodewes Sep 4 '15 at 10:55
  • 1
    $\begingroup$ @MaartenBodewes: No, this is being used for entropy pool compression (see schneier.com/fortuna.pdf for more info on the general idea). $\endgroup$ – Foogod Sep 4 '15 at 18:44
1
$\begingroup$

Use SHA-256. Truncating the hash does reduce its collision resistance, but you can't "lose entropy" if you're only keeping 128 bits in each pool anyway.

$\endgroup$
  • $\begingroup$ My question was not actually about truncating the final digest (I agree that should be OK), but specifically about deleting half of the internal state (repeatedly) in the middle of an ongoing hashing process. It's not clear to me that the two are necessarily equivalent... $\endgroup$ – Foogod Sep 4 '15 at 6:07
  • $\begingroup$ That wouldn't be equivalent. If you truncated the internal state, the algorithm would no longer be SHA-256, and you wouldn't have the benefit of any of its strength guarantees nor all the analysis that has been done. $\endgroup$ – rmalayter Sep 4 '15 at 14:27
  • $\begingroup$ Yes, I'm aware of that, which is exactly why I'm asking this question on SE, about what impact the behavior of such a modified-SHA-256 algorithm would have on entropy accumulation and mixing characteristics.. $\endgroup$ – Foogod Sep 4 '15 at 18:57
  • $\begingroup$ Here's a thought. Benchmark the overall performance & memory difference between using full-but-truncated SHA-256 vs MD5 as part of the whole system. I'll bet it doesn't matter at all, and you can just use full SHA-256 with confidence. A micro-optimization that cripples security isn't worth it. $\endgroup$ – rmalayter Sep 4 '15 at 22:41

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.