29

a. No such double hashing doesn't do a bit of good. Anything which collides after a single hash will definetly collide after a double hash. It preserves all collisions and adds new ones. We might consider other constructions which may provide some strength e.g $H(H(m) || m)$ however: b. We have no need for any such double hashing of SHA1 as we have newer ...


18

With all well-regarded hash functions, the bits of the hash all have equal worth: as far as anyone knows (unless they aren't telling), the bits are not correlated. If you take $k$ bits of an $n$-bit hash, you get a $k$-bit hash function. Truncating SHA-256 to 255 bits gives you a hash that's almost as good as SHA-256: it has $2^{255}$ strength against ...


12

This is due to the Brassard et al.'s method on hash functions. That has $\mathcal{O}(\sqrt[3]{n})$ attack time for n-bit hash function where as the Grover's method has $\mathcal{O}(\sqrt{n})$-time. Level I: At least as hard to break as AES-128 $\mathcal{O}(\sqrt{2^{128}}) = \mathcal{O}(2^{64})$ - by Grover Level II: At least as hard to break as SHA-256 $\...


11

SHA-1 is broken in practice in terms of finding collisions. This shattered attack (identical-prefix collision attack) requires roughly $2^{63.1}$ SHA-1 evaluations and this is approximately 100,000 faster than finding collisions with generic birthday attack on 160-bit output that has $2^{80}$- time complexity. That is, for a hash function with $\ell$-bit ...


8

Let $M$ be the number of queries to a uniform random function $F$ at distinct points $X_1, X_2, \dots, X_M$. The probability of a repeated value $F(X_i) = F(X_j)$ for $i \ne j$ is at most $M^2\!\big/2^N$ by the birthday paradox. For $M = 2^{N/3}$, this is $2^{2N/3}\!\big/2^N = 1\big/2^{N - 2N/3} = 1\big/2^{N/3}$. If your calculation doesn't fit this bound,...


8

$2^m$ requirement is for the pre-image attack. You have to hash approximately $2^m$ messages to find the message that has the same value you were looking for if the hash function has pre-image resistance. In a collision attack, you are looking for two messages that have the same hash value. If you look at Wikipedia Birthday Paradox at section Cast as a ...


7

No, the length extension attack/property is not considered a collision. It does not allow to build a collision. The length extension property is that given the hash of a bitstring $M$ of given length $l$ (but arbitrary and unknown content), it is possible to compute the hash of $M\mathbin\|F(l)\mathbin\|E$ with $F(l)$ a short bitstring deduced from the ...


6

Apart from the slightly reduced resistances, there is no problem: Resistances for SHA3-512; Pre-image resistance decreased to $2^{511}$ or $2^{504}$, if 1 bit or 1 byte trimmed, respectively. Secondary preimage resistance decreased to o $2^{511}$ or $2^{504}$, if 1 bit or 1 byte trimmed, respectively. Collision resistance decreased to o $\sqrt{2^{511}} = \...


6

SHA-1, like the earlier MD5 and SHA(-0), and the later SHA-2, is built per a carefully devised hierarchical design: Merkle-Damgård at the outer, building a collision+preimage-resistant hash with a security argument based on a fixed-width compression function. Davies-Meyer to build that compression function, with a security argument based on a block cipher ...


5

We can consider Merkle-Damgard(MD) based hash functions like MD4, MD5, SHA-1, SHA-256, SHA-512, and derivatives as a rotated block cipher, where the key is the message and the input is the previous state. A bit more formally, for SHA-1, there is a block cipher, named SHACAL, that takes a 512-bit key and 160-bit block as the input. Then the MD construction ...


4

Are there security problems with such a design that wouldn't exist with a normal hash algorithm? At least not for collision resistance. Suppose you could come up with a collision for the composite construction $H_p$ based on the hash function $H$. Then you'd have two inputs $x\neq x'$ such that $H_p(x)=H_p(x')$. Then either there is a collision on the ...


4

It is correct that the set of possible $H_n$ over all the possible $S$ reduces as $n$ grows. However the attack evaluates the $H_i$ for a fixed random $S$, not for multiple $S$; thus that reduction is immaterial to the success of the attack. In other words: it is evaluated the number of possible $H_i$ for random $S$ as a function of $i$, and from that drawn ...


3

Lets get one thing out of the way: forcing one bit to 0 or 1 does not change the output size of the hash. A hash output is not a number, so the output size would not be affected. Reducing hash output is common practice. Although maybe not a direct requirement, generally the output of a hash is considered indistinguishable from random - if the input is ...


3

There are about $2^{256}$ distinct inputs, secp256k1 private keys, and about $2^{160}$ distinct outputs, Ethereum addresses. By the pigeonhole principle, there is at least one address which is shared by many private keys. In principle, there could be $2^{160} - 1$ addresses each with exactly one private key, and another address with $2^{256} - (2^{160} - 1)...


3

Yes. If you publish such a commitment. And you model the hash as a random function it willl not only be preimage resistant but there will be many possible pairs of random string and message which will match the commitment. If the random string is as big as the hash output most possible message values can produce the commitment for some random string. So ...


3

My thought: assume there a black box, that given a cryptographic hash function $h$, finds some $x$ and $r$ in polynomial time, such that applying $h()$, $r$ times gives $x$: $$ h(h(h\ldots(h(x))) = x $$ I thought about this, and I found that the answer is yes. The oracle can be used to find preimages and collisions in an arbitrary function $$h : \{0,1\}^n ...


3

Generic collisions The generic collision attack on SHA-512 trimmed to $n=160$-bit will require $2^{80}$ complexity by the birthday paradox with a 50% success probability. The generic attack doesn't require any knowledge about the internals of the target hash function. It is about collecting hash outputs and looking collision among them by building a table ...


3

In the Bitcoin mining, hashcash version 2 (2002), one looks for the input $m$ such that $\operatorname{SHA256d}(m)$ is the desired output hash value that is below the current threshold of zeros. In other words $$\operatorname{SHA256d}(x)/2^{(n-k)} = 0$$ where $k$ is the work factor, that is the number of leading zeros and $n$ is the output size that is 256 ...


2

Counterexample [from poncho in comments]: let $H_0\colon \{0,1\}^* \to \{0,1\}^{256}$; then $H(x) := p \cdot H_0(x)$, where $H_0(x)$ is interpreted as an integer in little-endian, is obviously collision-resistant but $H'(x) := \sum H(\cdots) \bmod p$ is identically zero and therefore very much not collision-resistant no matter what goes in the ellipsis.


2

Collision-resistance implies one-wayness. Proof by reduction: if you have an algorithm $A$ which is able to invert $H: b^* \rightarrow b^n$, we can build an algorithm $B$ which is able to find a collision (with almost the same time and probability). Here $b$ means $\{0,1\}$. Let's consider only input strings of some length $l\ge n$. Notice that $H$ splits ...


2

Let the hash length be $d$. If we consider finite groups, like addition modulo $2^d,$ this problem is well understood. Fix $k=n+m.$ If the vectors are randomly generated and form a list of size roughly at least $2^{d/k},$ there exists a solution with constant probability bounded away from zero. This is because a list of size $M$ contains $$F:=\binom{M}{k}$$ ...


2

For the function $F(x) = ax \bmod n$, where the inputs are limited to the range $[0, n)$, this function will be a bijection (that is, no collisions) if and only if $a$ and $n$ are relatively prime. Here is a proof in the direction you're asking about: Suppose there exists a collision, that is, we have a pair $x, y$ with $0 \le x < y < n$ where $F(x) =...


2

A. Find two identical messages with different hashes This is fundamentally impossible, assuming you're talking about a regular hash and not a keyed hash (like HMAC). As hashes are deterministic, two identical messages will always result in an identical hash. B. Find two identical messages with the same hash This is not only possible, but guaranteed. Two ...


2

There are no known attacks on SHA3 series that are faster than the generic attacks. Your problem is the 2nd pre-image attack: given a message $m_1$ finding another message $m_2$ such that $m_1 \neq m_2$ and $Hash(m_1)=Hash(m_2)$. SHA3-256 has $2^{256}$ 2nd preimage resistance. Now, you only allow the attacker first 20-byte which is 160-bit of your data. ...


2

I think what you're asking is: We know there certainly exist two 33-byte strings $m \ne m'$ such that $H(m) = H(m')$, when $H$ is (say) SHAKE128-256, because there are only $2^{256}$ distinct possible outputs of $H$ and $2^{262}$ distinct possible 33-byte messages. Do there exist two <32-byte strings, say 16-byte strings, $m \ne m'$ such that $H(m)...


2

Let the range $Y$ of the function $f$ have size $N$ A collision resistant function cannot be better than an ideal function which maps uniformly into $Y$ since collision probability is minimized by the uniform distribution. Thus, given $(x_0,f(x_0))$ the number $k$ of random points $x_i\neq x_0$ that must be tried before the probability that $f(x_i)=f(x_0)$ ...


2

1) All common cryptographic hash functions are better than CRC, even MD5. This is due to the fact that they are designed to detect malicious tampering, whereas CRC is not. MD5 is still crackable, but CRC can be trivially manipulated. 2) hash function collision resistance determines how "good" they are at integrity verification, as there are more possible ...


2

It's certainly better to move to a modern hash function without significant known weaknesses than to stick with one that is known to be broken. Furthermore using a larger state for the hashing process helps mitigate certain attacks, even if your output size is limited. In an ideal world you would make the system support longer hashes, but if the choice is ...


2

It will never be secure to hash just part of a file. It will always be trivial to generate two distinct files which produce the same hash. (Just look for which parts of the file the lazy hash doesn't touch and modify those sections.) If you don't need security, then you might be able to come up with some scheme that works most of the time for "natural" (not ...


2

Generic expected pre-image resistance for a hash function with $n$-bit output is $\mathcal{O}(2^n)$ Generic expected collision resistance for a hash function with $n$-bit output is $\mathcal{O}(\sqrt{2^n}) = \mathcal{O}(2^{n/2})$ due to the generic birthday attack on the hash functions. \begin{array}{|c|c|c|c|}\hline \text{name} & \text{output size} &...


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