# Order of hashing concatenation

A = hash("blue" + X);
B = hash("pink" + X);


If A and the literals are known and X is unknown, are there attacks on B aside from the attacks on directly on hash()? In other words, is B safe?

Would it be better to reverse the concatenation?

A = Hash(X + "blue");
B = Hash(X + "pink");


If it matters, I am using hash=sha256.

-
Not sure what exactly you're trying to protect against. Could you clarify that? – CodesInChaos May 5 '12 at 20:46
Probably HMAC is a better choice – CodesInChaos May 5 '12 at 20:47
I'm trying to protect against someone being able to determine B, given A, the literals and the hashing function. – Fantius May 5 '12 at 23:44
Given Hash(X + "blue"), it might be easy to compute Hash(X + "blue pink") using a length-extension attack (assuming an iterated hash function, such as MD5, SHA-1, or SHA-2). As CodeInChaos mentioned, you probably want to use a message authentication code, such as HMAC, rather than a hash function. – Seth May 6 '12 at 0:52
Actually, yes, it is. That is, given A = Hash(X + "blue"), it is possible to compute B = Hash(X + "blue pink") for specific values of " pink". Now, this observation is valid for only very specific suffixes, the fact that it occurs for any suffix makes us question that particular construction (especially since there are other constructions that don't share that weakness) – poncho May 6 '12 at 22:54

## 2 Answers

It looks like you want a message authentication code (MAC).

A MAC is a computable function $M$ of two inputs $k$ and $x$ (usually with variable-sized $x$ and fixed-sized $k$ and output) such that:

• Given a lot of pairs $(x_i, m_i)$ with $m_i = M(k, x_i)$ (and not given $k$), it is hard to find $(m, x)$ with $m = M(k, x)$ and $x$ is not one of the $x_i$s).

You actually only need a slightly weaker condition:

• Given a lot of pairs $(x_i, m_i)$ with $m_i = M(k, x_i)$ and an $x$ which is not one of the $x_i$s (and not given $k$), and it is hard to find $m = M(k, x)$.

While a random oracle with simple concatenation of the inputs (in either order) would do fine as a MAC, real-life hash functions are not random oracles. Thus we usually use specially-made MAC functions for this goal - there are ones based on hash functions (specifically HMAC which can be instantiated with every hash function), and others based on block ciphers.

It might be that SHA-256 is safe anyways (maybe depending on the length of your strings), but this is not what SHA-256 was made for.

Simply use HMAC-SHA-256 instead (with your $X$ in the key position).

-

There are no direct way to derive $A = H(C_1||X)$ from $B = H(C_2||X)$ if $|X|>0$. However, for short $X$ exhaustive search is practical, so this is a weak scheme.

-
However, it's still a bad choice of algorithms because a person with the ability to place his own values of X in the B equation might be able to get values of A even though he has no access to the A equation, and it's trivial to pick algorithms that don't have this weakness. (As poncho explained.) – David Schwartz May 8 '12 at 7:55
X is a very large and expensive hash value. – Fantius May 9 '12 at 1:23