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


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


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


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

Because a hash function essentially destroys the inputs, or information. For example, a common operation in hashing is modular math, which is basically the remainder after the division. 9 mod 2 = 1 (9 / 2 = 4, remainder 1). The 1 moves on in the hashing function. But the modular operation is irreversible - all that is left is the output of 1, but there ...


5

SHA256 gives 256 bits, which is 32 bytes, not 64 "characters" (please use the well-defined bits and bytes). When written in hexadecimal notation, you need 64 characters from 0-9a-f, but the length of the hash is 256 bits. Yes, you could invert the hash. Unfortunately, a straightforward lookup table would be too large to store, but you can still do brute ...


4

MD4 is Not One-Way. The attack described in the 2008 paper is a theoretical attack with complexity $2^{102}$, which is better than the brute force complexity of $2^{128}$. In later theoretical results reported here the complexity dropped to $2^{94.98}$ and here it dropped even further to $2^{69.4}$ for secondary pre-image attacks. Similarly, The MD2 Hash ...


4

There are different birthday bounds when we draw independent uniform random integers less then $d$  (for some large $d$, including $d=2^{32}$ of the question) and watch for collision(s): In crypto, we often consider the bound of $\sqrt d$  ($65536$ for $d=2^{32}$) draws, at which there is a fair probability of collision: $p\approx1-1/\sqrt ...


4

The question "why is preimage resistance needed for hash functions" is not really relevant. This is because collision resistance implies preimage resistance. Thus, it is just a fact that if you have collision resistance then you must have preimage resistance. So, instead, I will relate to what preimage resistance is good for at all. In more technical ...


4

If we use $H_1(X) = H_0(X) \oplus firstnbits(X)$, this would seem to be trivial. EDIT: As Cédric Van Rompay pointed out, this is only a counterexample if $H_1$ winds up being preimage-resistant. This may not be a necessary consequence of $H_0$ being preimage-resistant, but I really only need one case where it is.


3

According to the version of FIPS 180 available back in 2005, SHA-1 has an input length limitation, which means there are not an infinite number of messages that are valid SHA-1 inputs to begin with. The reason for this constraint is the padding contains a fixed length input bit length field. Older algorithm of a similar design, such as MD5, also have fixed ...


3

For a good hash function, like Skein, diversity of inputs has no impact on diversity of outputs. So, if you have no information about the space of possible pre-images (e.g., it is not a human generated password, it is a completely random input from your prospective), then the expected number of attempts before retrieving the pre-image is the same in either ...


3

SHA-256 - or any cryptographically secure hash - relies on the internal construction of the hash to have the one-way property. This one-way property is maintained for any kind and size of input. However, if the input domain is small enough then it may be able to brute force the hash value. As SHA-256 is not keyed anybody can perform the calculations. So all ...


3

SipHash is a MAC (aka Pseudo Random Function Family) with 64-bit output and 128-bit key, rather than a hash (aka random public member of a Pseudo Random Function Family). It is explicitly designed to be used with a secret random key. Quoting Jean-Philippe Aumasson and Daniel J. Bernstein's SipHash: a fast short-input PRF (in proceedings of Indocrypt 2012): ...


3

As far as we know, SHA512 acts like a random function. So, the only way we know to find a preimage whose hash starts with 0x12345678, is to go through distinct preimages, and hash each one until we find one that starts with 0x12345678. If the output of SHA512 is equidistributed (and we have no reason to believe it isn't), then the probability of any hash ...


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

Your error is here: An OR gate cannot be reversed, since it fundamentally losses information. However, a possible input can be derived from any given output. A set of possible inputs can be derived from any given output. For each output that is a 1, there are three possible combinations of input (01, 10, and 11). If you add enough gates in sequence, ...


1

As I understand it, preimage resistance means that it is hard for an adversary to find two messages that produce the same digest Nope: collision resistance means that it is hard for an adversary to find two (distinct) messages that produce the same digest. Preimage resistance means that, given a hash output, it is hard for an adversary to find a ...


1

First the obvious; checking $M_L=D_L$: is unnecessary from a security standpoint IF $H$ really is secure, by definition of that; but who knows what's really secure? can't harm preimage resistance (first or/and second), nor collision resistance; can greatly increase speed, if the hash is computed only after checking $M_L=D_L$; that's a common reason to ...


1

Why can't I reverse a hash to a possible input? Actually, depending on the individual hash and explicitly ignoring all computational feasibility issues, you could. Just don’t expect the result of your reversal to be the same as the “original input”. Furthermore you should be aware of the fact that, depending on the type of hash and depending on the ...


1

You try to dis-prove something that is not a feature of a hash function. You can always brute-force a hash function by trying all possible inputs upto a given length until you find a preimage of a given hash. The claim for a cryptographic hash function is that it is computationally difficult to find such a preimage. In fact, this claim is not proven for any ...


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

There are a lot of other uses for hash functions than signature algorithms. For example, when used as a MAC – whether directly or in HMAC – a preimage attack would recover the key and allow forgery for arbitrary messages. Even specifically in signature algorithms there's the Lamport signature which requires preimage resistance.


1

Consider this hash: $$H(m) = m$$ Where we define it's domain to be messages of some arbitrary fixed-length. It is completely second pre-image resistant. It is not at all first pre-image resistant. Therefore: Second pre-image resistance does not imply first pre-image resistance.



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