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


7

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


7

Hash + digital signature If the hash is not collision resistant, the attacker can produce two messages having the same hash. They'll request a signature on the first and present the signature on the second, a forgery. When second pre-image resistance is violated, this attack becomes much more severe, since now the attacker doesn't need control over both ...


6

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


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


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


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

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


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


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

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


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


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

You'd still need to iterate over all the possible passwords to do this, using a brute force or dictionary attack (i.e. a pre-image attack with regards to the hash). That is, unless the hash algorithm used isn't one way; i.e. you can retrieve more information about the passwords. A 32 bit hash is not common, so this could be possible. Fortunately most ...


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.


2

The inverse cannot be calculated, you're right. However, in can be guessed. In many scenarios, for example cracking hashed password, it's enough for the attacker to know a set of possible inputs which result in certain output (of course if their number is reliable) instead of one certain value. So if the one-to-many function is weak, given the output $y$ ...


1

No, it is still non-trivial to reverse the hash. However, knowing the message length and allowed characters places an upper bound on the number of possible messages.


1

Preimage resistance is usually defined not for all the inputs, but for all the outputs, since what you are trying to model is the inability to, given any output $y$, obtain an input $x$ such that $H(x) = y$. I'm not going to solve the problem for you since you may be able to do it by yourself. Just try to think of the patterns in the output and if this can ...


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

Generating collisions for a 32-bit hash is trivial; thanks to birthday paradox, the expected effort is only about 217 hash evaluations. If you don't believe me, try running this Perl code: use strict; use warnings; use Digest::SHA 'sha256'; my $message = "a"; my %preimages; while (1) { my $hash = unpack("H8", sha256($message)); print "$hash: $...


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


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



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