1

I have two sha256 hashes as hex strings

HASH1=b5bb9d8014a0f9b1d61e21e796d78dccdf1352f23cd32812f4850b878ae4944c
HASH2=7d865e959b2466918c9863afca942d0fb89d7c9ac0c99bafc3749504ded97730

now I want to create a new SHA256 that depends on these two hashes (for a merkle-tree structure). Any two hex representations of the same hashes should in any case always result in a representation of the same binary hash (so for example if I go off the string representations, then it must be some canonical form of it, like ascii encoded lower case)

I know that I need to use an injective function, but what's the best way to go?

should I use the string values and some delimiter and then hash the binary representation of that string (and rely on bash using ASCII encodinng for it)?

NEW_HASH=$(echo -n "${HASH1,,},${HASH2,,}" | openssl dgst -sha256 | sed 's/(stdin)= //')

Or is it better to convert the hex representations to binary first and then just concatenate the binary representations (since the two hashes have fixed length, the result would be unambiguous)?

BIN1=$(echo -n "$HASH1" | xxd -r -p -)
BIN2=$(echo -n "$HASH2" | xxd -r -p -)
NEW_HASH=$(echo -n "$BIN1$BIN2" | openssl dgst -sha256 | sed 's/(stdin)= //')

What's the better approach and why?

5
  • This does not look like an actual information security issue to me, more a programming problem. Feb 20 at 15:59
  • It's programming related, true, but the underlying question is an information security question (since both approaches work programming wise). I tried asking this on stackoverflow (stackoverflow.com/questions/66269658/…) but did not receive any answers Feb 20 at 16:12
  • Are trying to build a Merle-Tree?
    – kelalaka
    Feb 20 at 17:57
  • @kelalaka it is for a structure that has properties of a merkle-tree, yes Feb 20 at 19:51
  • An actual (binary) hash value can contain any bytes 0-255, but bash and most other shells cannot store 0 (or anything after 0) in a variable; zsh can, but can only pass such a value to a shell special or builtin command, not an external process (program or script). Of course a proper program in a language like C++, Java, python, or even perl doesn't have this limitation. Feb 21 at 3:39
0

Crypto functions operate on raw bytes. So, if given hex-encoded strings, it's generally a good idea to decode these strings first, then feed the underlying array of bytes into the crypto function.

In your case, you need to concatenate two hex-encoded byte arrays together, then take the SHA256 hash of the result. There are two ways you can do this:

a) Concatenate your two hex-encoded strings, then decode the concatenated hex-encoded string to a byte array, then take the SHA256 hash of the byte array.

b) Decode each hex-encoded string to a byte array, then concatenate the two byte arrays together, then take the SHA256 hash of the byte array.

Both of the above methods produce the same results.

For (a), you can do:

{ echo -n "b5bb9d8014a0f9b1d61e21e796d78dccdf1352f23cd32812f4850b878ae4944c"; echo -n "7d865e959b2466918c9863afca942d0fb89d7c9ac0c99bafc3749504ded97730"; } | xxd -p -r | sha256sum

Which produces:

fc87504c81f99f46407174938c24d0d0b6c65179565a2ac0fd6bd12c2016cbe8

For (b), you can do:

{ echo -n "b5bb9d8014a0f9b1d61e21e796d78dccdf1352f23cd32812f4850b878ae4944c" | xxd -p -r; echo -n "7d865e959b2466918c9863afca942d0fb89d7c9ac0c99bafc3749504ded97730" | xxd -p -r; } | sha256sum

Which (as expected) also produces:

fc87504c81f99f46407174938c24d0d0b6c65179565a2ac0fd6bd12c2016cbe8
0

The problem with standard Merkle-Tree is that can enable second-preimage attack or worst signature forgeries.

For simplicity assume that the parent of nodes (e1,e2) is H(h1||h2) with h1=H(e1) and h2=H(e2). Now, the attacker can use this to find a second preimage for the list; h1||h2, and this will be hashed to to H(h1||h2). Now attacker can replace the (e1,e2) with a single node h1||h2 and it will be a valid Merkle Tree.

The worst can happen if the signature includes the Merkle node H(h1||h2) then we can forge a signature for h1||h2 even that has no meaning.

Therefore the Merkle Tree needs countermeasures against these. The solution is prepending 0 for the left node and 1 for the right node, and adding the level, too ( lowest level 0). H(left||right||leaf) if child is a leaf and otherwise H(left||right||left,right). This makes the domain separation.

For more detail of Merkle Tree, Squeamish Ossifrage's answer in Cryptography.SE

Encoding is not really important in the security sense if there are no attacks. Remember the prefix collision attack on SHA-1 uses the file format properties like PDF. Just note that SHA-1 was already fallen way earlier before the attack.

The format can affect the speed, binary encoding can be faster if the message size exceeds the 224-bit. In this case, if you represent it in hex, then SHA256 will need a double compression call. For faster speeds, you may consider BLAKE2s and its parallel version BLAKE3. If you need the NIST hash function then use SHA-512 since it is designed for 64-bit CPUs. If you need only 256-bit output then it has already that version, too; SHA-512/256 and this has protection against the length extesion attacks as BLAKE2 and SHA3 series,

6
  • what exactly does the || denote here? if the hashes are ordered and of fixed length, how can a second preimage be found? Feb 20 at 20:32
  • concatenation. It is about the Merkle tree. It is a single list with one entry. Updated that part.
    – kelalaka
    Feb 20 at 20:39
  • Ah I see, but that's only for the case that the number of children is not fixed, right? if it is clear that there are exactly two children, this is not possible, correct? Feb 20 at 20:43
  • Will your algorithm check that? In cryptography, we want to reduce the attacks due to coding errors. This happens many times like in the incorrect implementation of the PKCS#1v1.5 padding scheme of RSA even though there was nothing wrong with the scheme. A secure scheme can be broken with implementation, too.
    – kelalaka
    Feb 20 at 20:47
  • yes my structure is a binary tree where each node is either a leaf or it has two children which are ordered (left and right) Feb 20 at 21:00
0

Hash is a set of bits. If you really want to work with hashes, you should use their binary representation, not the text representation.

For instance, "b5" in your example means that the first byte of your hash is "10110101". But if you consider it as a text, it will mean that every character will be considered separately, so "b5" will be represented as "0110001000110101" ("b" -> 98 -> "01100010", "5" -> 53 -> "00110101").

4
  • If that's true, then the encoding would indeed be unambiguous if the strings were used. However, afaik in ASCII (and in extension UTF-8) all characters used in a hex string are guaranteed to be represented by exactly 8 bits, no? Feb 20 at 20:23
  • 1) The first 128 characters are the same in ASCII and UTF-8. Thus if you have a single character, you cannot say much about encoding. But I don't see how is it related to your question. 2) No, it would not be unambiguous, because string representation is ambigous, e.g. it can be "b5" or "B5", both meaning the same. Where as when you decode hexadecimal string to bytes, the result is always the same, both "b5" and "B5" mean the same binary number "10110101".
    – mentallurg
    Feb 21 at 0:03
  • exactly, which is why i referred to a 'canonical form' of the hex string (i.e. ${HASH1,,} converts characters to all lower case). What I don't quite get is how you arrive at 13 bits for "b5". But yes, part of the question is whether one can rely on bash always using ASCII encoding for a string that is representable in ascii (from my testing, it does) Feb 21 at 0:10
  • @matthias_buehlmann: 13 bits? Good point. Of course it should be 16. I converted each number and forgot leading zeroes up to 8 bits :) I have updated the answer. To bash: Ideally, the approach should not depend on a particular tool. First decide what exactly you need, what algorithm fits your goal. Then look for tools.
    – mentallurg
    Feb 21 at 3:03

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.