# Tag Info

27

We call a primitive broken, if there is any attack faster than bruteforce/what we expect of an ideal primitive. Broken does not mean that there are practical attacks. There are no known collisions in SHA-1. Still we call collision resistance of SHA-1 is broken, because there is a theoretical attack that can find collisions using fewer than $2^{80}$ calls to ...

21

As a general rule, you should avoid SHA1 for new applications and instead go with one of the hash functions from the SHA-2 family. As far as truncating a hash goes, that's fine. It's explicitly endorsed by the NIST, and there are hash functions in the SHA-2 family that are simple truncated variants of their full brethren: SHA-256/224, SHA-512/224, ...

15

Wikipedia has a reasonably good explanation about the Merkle–Damgård construction. The idea is the following: SHA-1 is built around an internal "compression function" which takes as input the 160-bit state and a 512-bit message block, and returns a new state. The padding is designed so that it can be proven that a collision over the hash function necessarily ...

15

No. The wikipedia article is in my honest opinion misrepresenting this article on a reduced round attack on the SHA-2 family of hashes. Although these attacks improve upon the existing reduced round SHA-2 attacks, they do not threaten the security of the full SHA-2 family. In other words, no collisions have been found in any of the SHA-2 hashes. The ...

12

echo -n "06b2f82fd81b2c20" | sha1sum e42d65afd2bc126a2e8e609257287084c43fc06a echo -n "02c60cb75083ceef" | sha1sum e42d65afd277988908c01bc539c9d71aff728322 Notice the first ten characters of the SHA1 hash match, indicating a 40-bit match. Other pairs are 0534164decf1166c, 06670357183cba13 and 0addd115537e4b39, 09a3cbdd0d00773b. Note that I am ...

12

No, theoretically a SHA1 hash can be any 160-bit value, including the string of 160 zeroes. As for your second question, if we fudge a little bit and consider SHA1 a truly random function this becomes the same question as the following: If we flip 160 coins, what is the probability that at least 128 of them will be heads? Solution is left as an exercise ...

12

Short answer: don't. Use a password hash like PBKDF2, scrypt or bcrypt. Also, if at all possible, use a library that takes care of the low level stuff like password database for you. E.g. passlib might work if you use Python. I'm sorry if that sounds blunt, but that's how it is. To answer your actual questions: There is just only one thing which ...

11

MD5 and SHA-1 have a lot in common; SHA-1 was clearly inspired on either MD5 or MD4, or both (SHA-1 is a patched version of SHA-0, which was published in 1993, while MD5 was described as a RFC in 1992). The main structural differences are the following: SHA-1 has a larger state: 160 bits vs 128 bits. SHA-1 has more rounds: 80 vs 64. SHA-1 rounds have an ...

11

I would recommend phasing out SHA-1 in any scenario where collision-resistance of a hash is required, for there is a wide consensus that an attack with $2^{69}$ complexity would work, it would already be feasible by a resourceful entity, and attacks only get better. I'm still confident that SHA-1 is preimage and second-preimage resistant for all practical ...

10

Here is the relevant part of the algorithm (from Wikipedia, reformatted): Pre-processing: append the bit 1 to the message append 0 ≤ k < 512 bits 0, so that the resulting message length (in bits) is congruent to 448 ≡ −64 (mod 512) append length of message (before pre-processing), in bits, as 64-bit big-endian integer This ...

10

The chance of a collision in such a set is approximately $\frac{1/2 \cdot n^2}{2^{160}}$, which for n=100k evaluates to about $3.4 \cdot 10^{-39}$. So it is fair to say, such a collision won't occur accidentially. AFAIK nobody has every found a SHA-1 collision. Collisions become likely once you generate about $2^{80}$ or $10^{24}$ hashes. If ...

10

The echo command will include a newline at the end. So when you use echo 'Rosetta Code' | sha1sum you are actually hashing the string Rosetta Code\n. Do the test using echo -n, the -n flag prevents the trailing newline character. Doing echo -n 'Rosetta Code' | sha1sum gives the same 48c98f7e5a6e736d790ab740dfc3f51a61abe2b5 hash that you were seeing ...

10

The initial values to a Merkle–Damgård type hash function are essentially the plaintext to a block cipher, with the input to the hash function becoming the key. The maximum length of the hash is determined by the amount of bits of initial value. Five 32-bit words gives SHA1 a state size and maximum output of 160 bits. In order for an MD type hash function to ...

10

Would you use HMAC-SHA1 or HMAC-SHA256 for message authentication? Yes. That is a semi-serious answer; both are very good choices, assuming, of course, that a Message Authentication Code is the appropriate solution (that is, both sides share a secret key), and you don't need extreme speed. How much HMAC-SHA256 is slower than HMAC-SHA1? Those ...

9

password = sha1 ( mainPassword . domainName . number ) Is this secure enough? Answer is no. Let me explain. The only part that is really unknown in the above is mainPassword. The rest can easily be guessed by a hacker. If your original password is weak (not many characters, no digits, no specials characters), the number of combinations to test is ...

8

Systems that do this already exist, such as SuperGenPass. To address your questions in order: I mean if somebody know my algorithm and one or many passwords, could he find easily one of my other password? Easily? No. As long as SHA1 remains a secure hash function (which is currently the case, but all hash functions have a lifetime), the only way for ...

7

The main route of attack on your algorithm is not somehow "breaking SHA-1", but a brute-force/dictionary attack on all possible values of mainPassword. For this, using n-times iterated SHA-1 takes n-times the work as normal SHA-1, both for you and for the attacker. To make this really helpful, you should take a really high value for n - such as 2^20 or ...

7

If your password database will never be compromised, you can store plaintext passwords and nobody will be bothered. The only thing about plaintext passwords is that they can be accidentally remembered by admins who see them - a simple base64 will fix that. Equivalently, MD5 or SHA1, with salt or without, is just as fine. If your password database is ...

7

Well, the entire point of a cryptographical hash function is that no one can practically devise two messages that hash to the same value. Now, the SHA family of hashes use the Merkle–Damgård construction; that is, they have an iterated hash function, and each invocation of the hash function takes as input a fixed block size (either 512 or 1024 bits in the ...

7

Well, SHA-1 and SHA-256 are both limited to inputs of no more than $2^{64}-1$ bits; the HMAC architecture itself prepends a logical IPAD (which is 512 bits); hence both HMAC-SHA160 and HMAC-SHA256 are both limited to inputs of no more than $2^{64} - 513$ bits, which is about 2 exabytes. I rather suspect that this is not a serious limitation to your ...

7

In early years of hash function design it was unclear how to choose constants (not only initial vectors), and it was widely assumed that the more random they look, the more secure the function is. There is still not much research in this direction. However, there have been several attacks (rotational cryptanalysis, slide attacks, internal difference attacks) ...

7

They are actually the same, because you missed W^=V in the second link. When you work out the XORs, you arrive at the same constants.

6

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 ...

6

In practice (i.e. when actually implementing the function), you do not really calculate $k$. Things rather work like this: you have a 64-byte buffer. You process incoming data through that buffer; when it is full, you apply the compression function, which mutates the internal state (five 32-bit words for SHA-1, eight for SHA-256), and begin again at offset 0 ...

6

If you have an implementation of an integer modulo operator, then $$k = (447 - l) \bmod 512$$ should be the right solution. If your modulo operator can return negative results, do this: $$k = ((447 - l) \bmod 512 + 512) \bmod 512$$ This seems simpler than using your division and flooring. That said, you actually don't really need the number of zero ...

6

If the question is 'why are those variables initialized at all', well, that's because those values will be used as inputs to the initial SHA-1 compression function; they must be consistent values; otherwise, the resulting hash will be different (depending on what values were used). If the question is 'why are those specific values used (rather than other ...

6

There is no such proof, on the contrary it has been proven that SHA-1 does not possess the ideal 80 bit collision resistance. Rather it is down to around 61 bits of resistance, uncomfortably close to being practically exploitable, and even if no further weaknesses are found advances in computing power are almost guaranteed to make it reasonably practical ...

6

Because the RFC says so. Signing and verifying using this key format is done according to the Digital Signature Standard [FIPS-186-2] using the SHA-1 hash [FIPS-180-2]. It says the same for RSA half a page down. Apparently the signature algorithm is a defined part of the public key method's specification, rather than being negotiated ...

6

The cost of finding collision for SHA-1 is currently estimated as $2^{61}$ SHA-1 calls. To understand how much (or how little) it is, we could look at Bitcoin mining. Right now (September 2014) the entire mining network computes 200,000,000 giga-double-hashes of SHA-256 per second, or $2^{61}$ hashes in three seconds.

5

325 MB/s is already good, i.e. you will not get much more with another implementation. Also, SHA-1 is a sequential algorithm, so multiple cores or a GPU will not help you. Specialized hardware is probably your best bet to make SHA-1 faster. (Also, if SHA-1 is the bottleneck then you are able to move data around faster than that, which is impressive; ...

Only top voted, non community-wiki answers of a minimum length are eligible