# Tag Info

18

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

14

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

14

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

13

There is a reasonably good explanation in Wikipedia. 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 implies at some point a ...

11

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

10

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

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

9

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

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

9

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

9

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

8

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

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

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

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

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

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

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

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

5

The distinction between real and fake salt is arbitrary. I suppose that your method would be called "fake salt" by those who make the distinction (concatenation versus "separate input parameter to the algorithm), but there is not really a difference in practice, as long as the hash algorithm is secure. A bit more secure (in the sence of "provenly secure") ...

5

Base64 provides a 1:1 transform from input to output (and back again if desired). So if you take a set of unique items and base64 encode all of them they will all be unique. So the question becomes if you run a GUID through SHA1, will the resulting hash have the same uniqueness as the GUID? The answer is practically - yes; theoretically not quite. Multiple ...

4

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

4

SHA1 is fully described (including complete test vectors) in this FIPS publication, if you wanted to do it properly. But I think checking against the final digests of a couple inputs should be enough to point you to the correct version. I extracted them for you (inputs in ASCII, quotation marks excluded): "abc" (3 bytes) ...

4

In many existing padding schemes, without padding always being added there is a trivial second preimage attack. For simplicity let's assume a 10 bit hash function $h_{10}$ (extending this to other size hash functions is trivial). Let $m_1=101$ and $m_2=1011000000$. I claim that $h_{10}(m_1)=h_{10}(m_2)$. Since $m_2$ is 10 bits, no padding is needed. Since ...

4

Essentially yes, they do. Depending on the exact hash function you choose depends on the length of output you'd expect. For example, SHA256 produces 256 bits of output. This does then beg the question "but the length of the hash is fixed and there are infinite possible inputs??!!". That's correct, except that $2^{256}$ is ...

4

Great question, I'd love to see more proofs as well. This is pretty cool: https://class.coursera.org/crypto-preview/lecture/29 This is a very easy to follow and interesting proof based on the Merkle-Damgard construction (used for SHA1) that if you have a collision resistance function for a short message -> you have a collision resistance function for long ...

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