Tag Info

1

Given message $A$, you have to find message $B$, such that the first 64 bits (say, MSB) of their hashes collide: $$MSB_{64}(H(A)) = MSB_{64}(H(B))$$ This problem is called Second Preimage Search for the function $MSB_{64}(H)$, or Partial Second Preimage Search for the hash function $H$ alone. When $H$ is the full round SHA-1, there is no result, ...

-2

I don't think you can have file lengths in bits. So I will consider Bytes here, converting 64 bit to 8 bytes. 1 byte: 256 combinations 2 bytes: 256*256 combinations 3 bytes: 256^3 combinations ... 8 bytes: 256^8 combinations The general sum is $$\sum_{i=1}^{n} 256^{i} = \frac{256}{255} \cdot (256^n-1)$$

3

To add some more perspective to this: this question has been studied quite extensively in the context of hash function combiners. A combiner is simply a function that gets (black-box) access to two hash functions and implements a new hash function. The question there is: does a combiner with "short output" exist that is robust for collision resistant hash ...

1

First of all, "Is collision less likely for individual characters than for strings?" The answer to this is yes. In fact, experimentally verifying shows that for 8-bit ASCII characters the collision chance with FNV1a is 0. This is however not an impressive feat, seeing that the output is 4 times as large as the input. However, using this you no longer have ...

1

Obviously not. For example, the function $h2(x) = 0$ is not collision resistant, $h2(h1(x))$ shares that property. This remains true even in less trivial cases; if $h2$ is not collision resistant because its output is too short (it has an $n$-bit output, with $2^{n/2}$ being small enough to do a search over), then $h2(h1(x))$ will also be too short

1

Will they always be collision resistant? No For example, let $h_2(x)=0$. Then, $h(x)=h_2(h_1(x))=0$, which certainly isn't collision resistant. Can it be collision resistant? Yes For example, suppose we define $h_1(x)=\mathrm{SHA256}(x)$ and $$h_2(x)=\begin{cases} 0 & |x|=1 \\ \mathrm{SHA256}(x) & \mathrm{else} \end{cases}$$ Then, since ...

8

The answer to your edited question is "yes, it is possible". As a trivial example, let $H$ be an ideal $k$-bit hash function. Due to the existence of the generic birthday attack, $H$ provides only about $k/2$ bits of collision resistance — that is, an attack can, on average, find a collision after about $2^{k/2}$ hash function evaluations. Denote ...

2

CF is a randomized algorithm with input $K$. As a randomized algorithm, it is allowed to do random decisions in its calculations – this can be thought of flipping a coin. The results of these coin-tosses (i.e. a list of heads and tails) – can be thought as another "input". For each key $K$ and each list of coins, the algorithm either finds a collision or ...

2

Well, ECC takes about $2^{n/2}$ time to break because there are smarter ways to attack it than literally trying each possible key separately. With AES, the best known-attack is to try a key, and see if it works. If it doesn't, all you've learned is that that specific key wasn't it, only $2^{n}-1$ more to go... However, with ECC, there are other methods. ...

Top 50 recent answers are included