Hot answers tagged

33

It is correct that any hash function used in cryptography, restricted to fixed (or bounded) input size, can be implemented as a finite number of NOT and OR gates. What's more: the gates can be given an index such that the input of any gate consists of either an input of the hash function, or an output of a gate with lower index; this insures the construction ...


30

If you repeatedly apply a generic function on its result, in a finite domain, you tend to obtain a "rho" structure: at some point, you enter a cycle whose length is (roughly) $\sqrt{N}$, where $N$ is the size of the output space for your function. In the case of MD5, $N = 2^{128}$ (MD5 outputs 128-bit values), so the cycle will have length about $2^{64}$ ...


29

For hash function $h : \{0,1\}^* \rightarrow \{0,1\}^k$, this is not possible. This is because there are more possible inputs than outputs (pigeon hole principle). And this means that for some $A < B$ we have $h(A) = h(B)$. Thus there will be no way to tell the order of $A$ and $B$. Addition: To address some of the comments; note that this answer only ...


23

What you're missing is the fact that multiple logic gates can share the same input(s). So you can't look at each logic gate individually and "reverse" the entire circuit that way, because choosing the inputs of a logic gate may constrain the outputs of other logic gates (so not all possible choices of input for any logic gate will work, only some will). So ...


20

Definition In the Damgard-Merkle construction for hash functions the compression function takes as input: a message block and a chaining value. For the very first block there is not previous "chaining value". Instead a particular value, called an initialisation vector (IV) is given. A freestart collision is a collision where the attacker can choose ...


20

This isn't necessarily unexpected. 32-bit platforms vs 64-bit platforms can make a significant difference, as well as the amount of data you're hashing. $ uname -m x86_64 $ openssl speed sha256 sha512 The 'numbers' are in 1000s of bytes per second processed. type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes sha256 ...


20

No, it is not possible to construct a function $\operatorname{Hash}$ with the desired properties, as long as an adversary is able to obtain the output of that function for arbitrary input (even if the function takes an additional secret parameter unknown to an adversary). Proof sketch: given $A=\operatorname{Hash}(X)$ for unknown integer $X$, we can find ...


16

SHA-512 has 25% more rounds than SHA-256. On a 64-bit processor each round takes the same amount of operations, yet can process double the data per round, because the instructions process 64-bit words instead of 32-bit words. Therefore, 2 / 1.25 = 1.6, which is how much faster SHA-512 can be under optimal conditions. Of course there is memory overhead, ...


15

HMAC remains unbroken with MD5 and SHA1 because it has a secret key that the attacker doesn't know. Therefore, the attacker cannot carry out huge computations on itself (as is required for finding collisions). [A parenthetic comment: please do not misunderstand me; MD5 is completely broken and should not be used anywhere including in HMAC.] In contrast, when ...


14

The echo command appends a new line at the end, by default. The -n option omits this character. Compare these two executions: > echo -n "test123" | md5sum cc03e747a6afbbcbf8be7668acfebee5 > echo "test123" | md5sum 4a251a2ef9bbf4ccc35f97aba2c9cbda So the difference between the hash values is simply caused by the new line character.


11

Expanding then shrinking in SHA-1 refers to the process, performed for each round (each 512-bit block of padded message), of message expansion from 512 bits to 2560 bits; keeping only 160 bits of state for the next round. The later directly follows from the construction of SHA-1 as a Merkle-Damgård hash of 160 bit. The former occurs because SHA-1's ...


11

Contrary to your assumption, this is done, and it is secure: For instance, the hash functions SHA-224 and SHA-384 are basically the same algorithms as SHA-256 and SHA-512! The only differences are in the initial values for the Merkle-Damgård construction used internally and, of course, in that only the first $224$ or $384$ bits of the resulting hash are ...


11

What choice did they have? F1 is a bitwise function with three inputs and one output. There are $2^8 = 256$ such functions. Only 70 of them are "unbiased" (i.e. have as many 0 and 1 outputs in their image). If you further require that each input, as well as the order of inputs, matters for the output, you are left with only 36. However, those 36 are all ...


11

The functions used by SHA-2, called $Ch$ and $Maj$ are defined like this in the standard: $$Ch(x, y, z) = (x \land y) \oplus (\lnot x \land z)$$ $$Maj(x, y, z) = (x \land y) \oplus (x \land z) \oplus (y \land z)$$ However, an equivalent way to define them replaces the XOR with OR, as the standard (pdf) states: Each of the algorithms include $Ch(x, y, ...


10

I believe Thomas Pornin's answer is by far superior to mine, but perhaps this answer can provide a simplification to his answer. When you initially hash some data, the possible input is infinite/limitless. You could input "abcdefghi...", "123456...", etcetera. However, the resulting hash possibilities are finite/limited. One of the beautiful things about ...


10

This is trivially true via the pigeonhole principle. SHA-2/512 has $2^{512}$ possible outputs, but $2^{2^{128}} - 1$ possible inputs. Trying $2^{512}+1$ unique inputs is sufficient to produce at least one collision. That said, SHA-2/512 is designed to be collision resistant, which implies that it should be hard to find two inputs that hash to the same ...


9

As rightly pointed by Henrick Hellström and Otus, FIPS 186-4 defines SHA-1 with a maximum message length of $2^{64}-1$ bits, hence it is certain that no 160-bit value is the hash of an infinite number of messages. In the following, unless otherwise stated, I assume that we modify the definition of SHA-1 to allow for an infinite number of messages, by ...


9

I'll review the standard mathematical notations used for $H_1:\{0,1\}^*\times\mathbb Z_p^∗\to\mathbb Z_q^∗$ , going from the bottom up. Hopefully, that will make the rest evident. $\{0,1\}$ is the set with the two elements $0$ and $1$, known as Booleans. $\{0,1\}^k$ (for some non-negative integer $k$ ) is the set of tuples with $k$ Booleans, or ...


9

Hash functions must be public, so if you want use RSA as hash function you should fix $K$. Now let $n$ be the RSA module and $H$ denote RSA hash function. We have $$H(M)=H(M+n)$$ so this function is not second preimage and collision resistant. Also this system is not first preimage resistant (with known public and private key): Let $M^k=h \pmod n$ ...


8

Grover's algorithm treats the function it is evaluating as a black box and finds, with high probability, an input to the black box such that it outputs a specified value in $O(N^{1/2})$ evaluations of the function. Since Grover's algorithm works on the function as a black box, your modification does not hinder Grover's algorithm at all in finding the ...


8

The entropy for the output of SHA-256 truncated to its first $128$ bits when fed a random $128$-bit input is about $127.173$ bit, down from very close to $128$ bit before truncation (see final note). The truncation does not halve the entropy, because the halves are not independent. The right line of thought is that SHA-256 truncated to its first $128$ bits ...


8

The expected number of collisions (assuming that the hash function can be modeled as a random function) is precisely $2^{-n}\binom{m}{2}$; that is, the expected number of pairs of values $x \ne y$ with $H(x) = H(y)$ (and so, to answer Ricky's question, $H(x) = H(y) = H(z)$ would count as three collisions). The reasoning is the obvious one; there are ...


8

I would use HMAC-SHA256. While poncho's answer that both are secure is reasonable, there are several reasons I would prefer to use SHA-256 as the hash: Attacks only get better. SHA-1 collision resistance is already broken, so it's not impossible that other attacks will also be possible in the future. It allows you to depend on just one hash function, ...


8

They don't, and in fact the sponge construction used in Keccak (SHA-3) allows for variable length output. In other hashes the Merkle-Damgård construction was used which has a fixed output length due to the nature of its design. But there is no reason to not allow for variable output length other than ease of development or use.


7

Secure against what and for what purpose? MD5 remains too fast for most human typed passwords. You should use something like bcrypt or PBKDF or sha256crypt where there are a tunable amount of thousands to millions (or more) rounds of hashing to generate each hash. You really don't want to allow users to try several billion hashes per second per GPU. ...


7

SHA-512 (and SHA-384) is usually faster on 64-bit platforms, and SHA-256 is usually faster on 32-bit platforms.


7

Well, if you can assume that the website hasn't been hacked, then providing a SHA2 hash of a program would allow you do make sure you downloaded (from anywhere on the internet) a good version of the software. You are right, however, that since the method is publicly known, if someone can replace the binary on the site, they can also replace the hash on the ...


7

Most standard-use iterative hash functions (including SHA-512) are build in a way that these types of operation are not possible (without breaking the hash function). They work generally in this way: The message is split in same-size blocks (usually with some padding at the end to fill the last block): $pad(M) = M_0 || M_1 || M_2 ... || M_n$. There is ...


7

There's a problem with boundaries here; how much "complication" is allowed? I could argue that SHA-2 is a complication of SHA-1 because they both use a Merkle-Damgård construction and have other similar elements. Then again, they are significantly different internally. On the other hand the addition of a single bitwise rotation did make SHA-1 significantly ...


7

I assume you're asking whether there exists a hash function $H: \{0,1\}^* \to \{0,1\}^\ell$, and a permutation $m: \{0,1\}^* \to \{0,1\}^*$, such that $$H(x) = H(y) \implies H(m(x)) \ne H(m(y))$$ for all $x \ne y$. The answer, alas, is no — there is no such $H$ and $m$. If there was, we could construct a collision-free hash function $H': \{0,1\}^* ...



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