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


24

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

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


4

See NIST SP 800-107, section 5.3.4: The effective security strength of the HMAC key is the minimum of the security strength of $K$ and the value of $2C$. That is, security strength = min(security strength of $K$, $2C$). For example, if the security strength of $K$ is 128 bits, and SHA-1 is used, then the effective security strength of the HMAC key is 128 ...


3

No, it is easy to show that (assuming that there are preimage-resistant functions at all) there are functions that the preimage-resistant, but not second-preimage resistant. If we assume that SHA512 is preimage resistant, one such function is: $$H(x) = SHA512(Trunc(x))$$ where $Trunc(x)$ just returns $x$ with the last byte removed. $H$ is not ...


3

You cannot uniquely invert it. Your hash will have the form $$y_1 \quad y_2 \quad \dots \quad y_m$$ with $y_i=\sum_{k=1}^m x_k^{i-1}.$ First look at the special case $m=2$. $y_1$ will always be $y_1=m=2,\,$ the other equation is $y_2=x_1 + x_2$. You cannot uniquely determine both $x_1,x_2$. In the general case you have $y_1=m$ and $m-1$ equations for the ...


3

I think you could calculate it manually or write code to solve this. You need to calculate X values from starting with end. For example : $X_{32}$ = 84 = $X_{32}^{31}$ $mod_{117} $ When you get $X_{32}$ value then you can calculate $X_{31}$: $X_{31}$ = 62 = $X_{31}^{30}$+$X_{32}^{30}$ $mod_{117} $ The only unknown value is $X_{31}$ here. You need ...


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

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

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


2

Use the number of occurrences of each letter as the unknowns you're solving for. This gives you 32 linear equations to solve for 16 unknowns. Use standard approaches for solving systems of linear equations. Finally use the fact that the letters are ordered alphabetically to reconstruct the $x_i$ values.


1

In general, you never want to use CRC/weak checksum for any computations on secret material (like keys). CRC is a linear function and by showing CRC of a key, you reveal a lot of equations that hold among the key bits. This is equivalent to showing the same number of bits of the key as the length of the checksum. The proper way of doing it has been ...


1

Assuming that by 'decrypt' you mean finding the preimage, this is not possible in general. The fact that you know the hash input is a 256-bit value does not help you in any way. A rainbow table could cover only a tiny portion of the $2^{256}$ possible inputs. Something like $2^{80}$ hashes would be on the upper end, if not beyond, a feasible amount of work ...


1

SHA-256 is¹ a cryptographic hash function. As such, it has preimage resistance: given a hash value, there is no way to find a string with that hash, except by trying all strings until you find one that works. Therefore you'll have to try all possible inputs, i.e. all strings that contain the known substring. (You can of course be smart about it: try the most ...


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

If you can use numbers larger than 64 bits, you can have your cake and eat it too. By choosing a random starting point and then incrementing a counter, you do not need to save any state, but also do not need to generate expensive random numbers for every hash. An essentially similar idea is using a part of the previous hash as the next input (a hash chain). ...



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