# Tag Info

## Hot answers tagged hash

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

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

6

SHA-1 is still thought to be secure whenever collision resistance isn't required. The hash is both used for signing certificates and ECDHE public keys. There's however a difference with regard to collision attacks. It is possible for an attacker to attack the collision resistance with certificates by getting their own certificate signed by a CA. In ECDHE ...

6

With respect to collisions, hashing twice can not increase security, because if $x$ and $x'\ne x$ collide for $H$, that is $H(x)=H(x')$, then $H(H(x))=H(H(x'))$. Otherwise said, any collision for $H$ is a collision for the double hash $H\circ H$. It is therefore trivial to exhibit collisions for $\operatorname{MD5}\circ\operatorname{MD5}$. Hence the answer ...

5

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

5

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

4

As pointed out by poncho, a hash function $H(.)$ that would consistently map two close strings $s_1$ and $s_2$ to the same value, would have to map all the strings to the same value. (Since you could go from one string to the next and it would always have to map to the same value.) So this does not make any sense. I think, like you also suggest, that an ...

3

Actually, if you define the $H_i$ functions properly, it can be done. I'll make the simplifying assumption that we can treat the $H_i$ and $F$ functions as Oracles (that is, you're not allowed to look inside their implementation); I believe that it's still possible without that assumption (but the solution may be more complex). For our primitives, we'll ...

3

Ignore the integer overflow issue I mentioned in a comment, for a moment. I don't see how this adds any security. For all $n>2$, the function you are calling Fibonacci is one-to-one, and since $n<256$, you could easily build a lookup table without much memory to invert the function. Therefore, to break this, all one has to do is invert the Fibonacci ...

3

With a hash function that is vulnerable to length extension attacks, like SHA-256, you can turn any random collision into a collision with that random string concatenated with some (partially) chosen data. In any use case where random initial data does not matter, you could use it to generate two documents which have the same hash value and thus the same ...

2

You could combine locality sensitive hashing ($LSH$) with a one-way function $H$. E.g. you could do $H(LSH(x))$ for data $x$. This is one-way and has the feature that two values that fulfill some locality condition map to the same value. Compared to the coding approach, it has the advantage that it works for any domain element. However, locality here is ...

2

Any PRNG with a finite state size is eventually periodic. The maximum period possible is $2^n$ for an $n$-bit state, but the average with a well mixed state is $2^{n/2}$. Here the hash function used is SHA-512, but the state is 1024 bits. A first guess would be a period of $2^{512}$, rather than the $2^{256}$ mephisto gives. Let's look at the cycles. Both ...

2

Assuming that you know that $h_0$ is the root hash of a Merkle tree for the file, you can be sure that $h_1$ is a hash of a section of the file if you know that it's one of the hashes of the sections one level below the root and you know its sibling hashes, i.e. you have values $(h_1^1, \dots, h_1^{m_1})$ such that $\mathscr{H}(h_1^1, \dots, h_1^{m_1}) = ... 2 SipHash doesn't claim to be a secure hash function. Only a secure MAC. So if you try to use it as a hash function, with a constant, public key, you are on your own. SHA-512/64 should be a "secure" 64-bit hash, which is of course not enough for a truly secure hash, since it only has 32-bit collision resistance. However, since you only desire preimage ... 2 Proof by contradiction is easy in this case. Assume the construction is not collision resistant. Then there's an adversary who can efficiently find a pair$H(x) = H(x')$. However, that also gives them$H_1(x) = H_1(x')$and$H_2(x) = H_2(x')$, so neither hash function is collision resistant, which contradicts the assumption. 2 No, that's not possible, as you calculate sha512(F2) without the state of sha512(F1). What you require is compress(mix(compress(mix(IH, F1)), F2)) while what you have is compress(mix(IH, F1)) and compress(mix(IH, F2)). So you would have to undo that last compression, which is obviously not possible. Here IH is the initial state (the values of$h_1$etc.) ... 2 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, ... 2 When the lower 63 bits of current_block are 0 (that is, for current_block either$0$or$2^{63}$), the step last += current_block is the same as last ^= current_block, and all operations in compress are linear. Otherwise said each bit of the output of compress is a function that reduces to the XOR of some of the input bits. We express this as a boolean ... 1 Yes, this PRG is theoretically periodic. Approximately after generating$2^{512}$outputs a state will be generated that collides with a previous state. (A previous version of this answer said$2^{256}$as I missed that two outputs are used for the state. Otus answer pointed out this mistake.) This follows from the birthday problem. However,$2^{512}$is ... 1 Short answer: Yes, you're right. 1 A quick resarch showed that there are no (good) attacks on Siphash. For SHA-512 there are defintely no known attacks. The first 64 bits of SHA-512 should have the same security guarantees as full SHA-512 has. So breaking any of the two comes down to how fast they are. SHA-512 is slower, in particular it achieves 192.5 cycles / byte in a 64-bit C ... 1 Well, firstly, SHA-1 still seems to have 160-bit preimage and second preimage resistance, so using it in HMAC requires more than 128-bit AES keys to get equivalent security. AES 192 would be sufficient, but isn't used in e.g. TLS – RFC 3268 says: The AES supports key lengths of 128, 192 and 256 bits. However, this document only defines ... 1 The goal of this method is to achieve collision-resilience (resistance against collision attacks). The second hash can be viewed as$H(R || M)$for message M and some randomness R that is unknown to an attacker. Now, even if an attacker could efficiently find collisions for$H\$, he cannot use this ability to run the standard forgery attack that works as ...

1

It is not true that there would always be at most two hashes required per elided range. Suppose you have an eight-byte long content and want to elide all but the last. You need to supply one hash for the left half, one to cover the next two and one more to cover the last one. Similarly, with 16 bytes of content, eliding the first 15 requires four hashes. ...

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