0
$\begingroup$

It's an unfortunate fact that, right now (2019), browsers don't expose standardized streaming hashing interfaces in SubtleCrypto. The only way to hash a file, is to load it into an ArrayBuffer in its entirety, which for large files, this could be prohibitvely costly memory-wise.

To get around it, I'm thinking of building a custom hash function using HMAC as its compression function, in a usual Merkal-Damgaard construct.

$ \text{compress}(IV, M) = \text{HMAC-SHA256}_{IV}(M)\\ IV_i = \text{compress}(IV_{i-1},M_i) \\ IV_0 = \text{00h}^\text{hashlen} \\ H(M_1|M_2|...|M_n) = IV_n $

The specific questions I have are:

Q1: Do I still need to include file length in the final block? I'm guessing no because the HMAC compression function already length-pad my message during processing.

Q2: What are the characteristics of such construct with regard to length-extension attack? I'm using SHA256 because it's standardized in Web Crypto, and it's length-extendable, so I wouldn't be bothering to defend against it in my HMAC-Hash construct.

$\endgroup$
  • $\begingroup$ …what are you really trying to do? Why are you trying to hash a large file? Is there a secret key involved? What security properties are you hoping for? $\endgroup$ – Squeamish Ossifrage Dec 3 '19 at 2:37
  • $\begingroup$ I'm trying to hash a large file part-by-part with out loading it entirely into memory. There is no key involved, I just want a streaming hash function. It should be as secure as SHA256. $\endgroup$ – DannyNiu Dec 3 '19 at 2:41
  • $\begingroup$ ‘As secure’ meaning what? Are you hoping for collision resistance? Pseudorandomness under a secret prefix? A construction with random oracle indifferentiability? What are you planning to do with the hash once you compute it? $\endgroup$ – Squeamish Ossifrage Dec 3 '19 at 2:44
  • $\begingroup$ Same collision and preimage resistance as SHA256, randomness isn't necessary. It's used to identify files in a file upload system so that the same files that had previously been partially uploaded can restart from where it left off. $\endgroup$ – DannyNiu Dec 3 '19 at 3:11
1
$\begingroup$

The collision resistance of this hash will be the collision resistance of $\operatorname{HMAC-SHA256}_{IV}(M)$. Beware of the fact that pre-hashing of the key is a thing with HMAC, so $$\operatorname{HMAC-SHA256}_{\text{ReallyLongIV}}(M)=\operatorname{HMAC-SHA256}_{\operatorname{SHA256}(\text{ReallyLongIV})}(M)$$

Do I still need to include file length in the final block?

To get the benefits of the Merkle-Damgard proof? Yes, because abstractly your HMAC invocations are just compression function calls.
However if you're willing to assume that it's impossible / really hard to find $(IV',m')$ such that $\operatorname{HMAC-SHA256}_{IV'}(m')=IV_0$ then you don't need to pad with the message length. You see this when you follow the standard Merkle-Damgard proof. That is go backwards through the message and if at any point the inputs differ but the outputs match you got a collision in the underlying compression function. There will be a point where one message may be shorter than the other, assumning both end with the same suffix - because otherwise there would be a collision - both end up at $IV_0$ at some point and as one message is longer one of them must expose a preimage to $IV_0$.

What are the characteristics of such construct with regard to length-extension attack?

It's a standard Merkle-Damgard, so it has the same length-extension weakness. To fix this you could e.g. use HAIFA and use $C(S,M,P)=\operatorname{HMAC-SHA256}_S(P\mathbin\|M)$ as HAIFA's compression function for some fixed-length integer $P$.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ I thought if we could find an IV-m tuple that hashes to arbitrary intermediate state resulting from a different IV-m tuple, then there's a collision. Does it have to be $IV_0$ as mentioned in the current answer? $\endgroup$ – DannyNiu Dec 5 '19 at 6:58
  • $\begingroup$ So the basic premise of this answer is that it's hard to find two different IV-m pairs that map to the same output. Then in addition there's a special case needed for $IV_0$ that it's hard to find any IV-m pair that maps specifically to $IV_0$. This would mean (among potentially other things) that it's unwise to choose $IV_0$ as the result of some application of the compression function. $\endgroup$ – SEJPM Dec 5 '19 at 14:05

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.