2
$\begingroup$

So I was wondering about what will be the dependence of the outputs when I padded one input with two different strings two times for technically generating two different strings, say the input string is 123 and the first time I have padded 12 before 123 $$H(12\mathbin\|234)$$ and next time I have padded '24' before '123' $$H(24\mathbin\|234).$$ Can I safely deduce that the outputs are completely independent even if the inputs are somehow related?

Asking this because I don't completely know the internal mechanisms of sha256 and how they are hashing stuff like this. I have good ideas about universal hash functions but kind of ignorant of cryptographic hash functions. So I have something developed using 3 wise independent hash functions but I am trying to shift everything using sha256 and in order to prove a lot of theoretical part concepts, I was looking for answers like this. I was looking for some sort of rigorous math proof/conceptual proof in this regard. Would appreciate any sort of help.

$\endgroup$
1
  • $\begingroup$ @kelalaka from what I have read in the post you mentioned above, it is safe to assume that they are independent? If I understand correctly $\endgroup$ Aug 13 '20 at 22:18
2
$\begingroup$

You are making a domain seperation with a prefix, and that is very common in random oracles (RO) instead of initiating another RO, one can use domain separation to use only one RO. Since the RO are like hash functions the same idea is used in the hash functions, too. That is the correct term and the correct way.

We expect that SHA256 outputs are indistinguishable from uniformly random.

Also, we expect that SHA256 ( like any cryptographic hash functions) has the avalanche effect;

  • a one-bit change in the input bits flips each output bit with a 50% probability. So some bits flip some bits doesn't.

If hash values with the prefixes are not independent there will be lots of problems for the used hash function. Also, consider that due to the padding, there are already lots of similar parts at the end of each message that didn't cause dependency.

One might note that SHA256 is vulnerable to length extension attack ( not only SHA256 though), but this may also be a problem for your scheme or not. Assume you have $h= \operatorname{SHA256}(12\mathbin\|234)$ then the attacker can use the output hash $h$ as the initial value for $\operatorname{SHA256'}(h,\text{extension})$ where this function controls the initial values of SHA256, then they can extend the message with a different hash value without knowing the prefix or the message. If $h= \operatorname{SHA256}(\text{prefix}\mathbin\|234)$ is used for MAC, although the attacker cannot produce the same output for the extended message, they can inject the extended message to execute a forgery.

$\endgroup$
3
  • 1
    $\begingroup$ "We expect that SHA256 outputs uniformly random." We really don't, since they're not. We're hoping that they are indistinguishable from uniformly random in some ill-defined sense. $\endgroup$
    – Maeher
    Aug 14 '20 at 12:54
  • $\begingroup$ @Maeher anything else to add? Thanks $\endgroup$
    – kelalaka
    Aug 14 '20 at 13:47
  • $\begingroup$ Thanks so much :) This was very helpful $\endgroup$ Aug 14 '20 at 16:33

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.