Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Let me ask whether SHA1 is designed to be secure for the following case. You compute each SHA1 of many strings,for example 1 million, where each string is a concatenation of X+Y , where X is secret and constant and Y is public and variable.

Thank you in advance.

share|improve this question

migrated from math.stackexchange.com Mar 18 '12 at 7:47

This question came from our site for people studying math at any level and professionals in related fields.

    
You should explain what you want to protect against. i.e. what can an attacker do, and what do you want to prevent him from doing. You can't simply say some scheme is "secure", you need to specify clearly what your requirements are. –  CodesInChaos Mar 18 '12 at 9:28
add comment

2 Answers 2

up vote 6 down vote accepted

Answering the question as worded in its body: NO, $\mathrm{SHA1}$ is not designed so that the proposed construction is secure under the stated conditions. The design objective of the $\mathrm{SHA1}$ and $\mathrm{SHA2}$ hashes, as explained by NIST, is that

it is computationally infeasible to find a message that corresponds to a given message digest, or to find two different messages that produce the same message digest.

and this does not lead to the conclusion that the proposed construction is secure, under any reasonable definition.


In order to answer the (different) question as worded in its title, we need to define "secure". The question is about a construction $F: (X,Y) \to F(X,Y) = \mathrm{SHA1}(X||Y)$. One possible definition of "secure" could be that $Y \to F(X,Y)$ is computationally indistinguishable from a random function for an attacker not knowing $X$ (which implies that $X$ does not leak from examples).

With this wide definition, NO, $\mathrm{SHA1}$ is not secure. It is vulnerable to a length-extension attack, a classical weakness of the Merkle–Damgård construction used in $\mathrm{SHA1}$. An adversary knowing $\mathrm{SHA1}(X||Y)$ can compute $\mathrm{SHA1}(X||Y')$ for some $Y'\ne Y$, on the conditions that $Y'=Y||P||E$; and he knows $E$ and the length of $X||Y$; and $P$ is a specific 65-to-576-bit string depending only on that length. Having many examples of $(Y,\mathrm{SHA1}(X||Y))$ helps the adversary, in that it widens the choices for $Y'$.

To perform this length-extension attack, the adversary can choose $P$ as the 65-to-576-bit string constituting the padding for $X||Y$ when computing $\mathrm{SHA1}(X||Y)$. Then, $\mathrm{SHA1}(X||Y||P||E)$ is computed by starting the normal computation where the block with $E$ starts, with the 160-bit hash state $\mathrm{SHA1}(X||Y)$ rather than the constant specified in $\mathrm{SHA1}$. The attack has very low cost, lower than if the adversary had computed $\mathrm{SHA1}(X||Y')$ directly with knowledge of $X||Y'$.


When the conditions for the length-extension attack are not met (including if the length of $Y$ is fixed, exactly or with a small leeway of +64 bits), or when the objective of the adversary is finding $X$, the construction proposed has considerable cryptanalytic resistance. Up to some limit on the size of $X$, we know no attack much better than brute-forcing $X$. A security argument could be given based on the assumption that the cipher used in the $\mathrm{SHA1}$ round function is secure; but we know that this assumption does not hold at all, if only because of some near-practical attacks on the collision-resistance of $\mathrm{SHA1}$. Therefore I can't quantify the level of resistance better than "AFAIK unbroken for practical purposes", which is not strong enough for a recommendation.


Fortunately, there is a recommendable construct based on $\mathrm{SHA1}$ that is designed to be secure (in the wide definition we considered); this is HMAC with $\mathrm{SHA1}$ as the hash function, $X$ as the key, $Y$ as the message. This construction has a security argument that is not directly harmed by a collision-resistance attack on $\mathrm{SHA1}$. Although the absolute confidence we can have in this argument is the subject of debate and some controversy, it is still very reassuring to me about the security of HMAC, and I am not alone.

share|improve this answer
add comment

I'd recommend HMAC. It's designed to mix a key and a message in a secure way.

HMAC(K,m) = H((Key ⊕ opad) ∥ H((Key ⊕ ipad) ∥ Message)).

Where H is a normal hash function such as SHA1, opad and ipad are constants. stands for concatenation.

The main disadvantage of HMAC is that it requires two hash function calls, which makes significantly more expensive for short messages, whereas for large messages the overhead is negligible. But as always, only optimize if benchmarks indicate that something is a bottleneck. Typically IO is much slower than crypto.


Your construction is vulnerable to length extension attacks. An attacker who knows SHA1(Key ∥ Message) can compute SHA1(Key ∥ Message ∥ EvilMessage)

share|improve this answer
    
The attacker can always calculate SHA1(Key||Message||Padding||Evil message). The Davies-Meyer step is supposed to prevent an attacker from rolling back the final hash to an (unknown) intermediary step, even if the message part, including padding, corresponding to that operation is known. –  Henrick Hellström Mar 18 '12 at 10:18
    
@CodeInChaos: I disagree with the stated condition for the length extension attack to work. The right condition is that the attacker knows EvilMessage and that starts by the appropriate 65 to 576 bits. The imposed prefix of EvilMessage depends, uniquely, on the length of Key ∥ Message, and is the padding specified by SHA-1 when hashing a message of that length. Nothing special happens when that length is a multiple of 512. Knowing Message does not help. –  fgrieu Mar 18 '12 at 11:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.