Hot answers tagged

35

Are checksums basically toned-down versions of cryptographic hashes? As in: they are supposed to detect errors that occur naturally/randomly as opposed to being designed to prevent a knowledgeable attacker's meticulous engineering feat? That is one way to look at it. However, hash functions have many purposes. They are also meant to be one-way (an ...


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


30

For hash function $h : \{0,1\}^* \rightarrow \{0,1\}^k$, this is not possible. This is because there are more possible inputs than outputs (pigeon hole principle). And this means that for some $A < B$ we have $h(A) = h(B)$. Thus there will be no way to tell the order of $A$ and $B$. Addition: To address some of the comments; note that this answer only ...


27

Definition In the Damgard-Merkle construction for hash functions the compression function takes as input: a message block and a chaining value. For the very first block there is not previous "chaining value". Instead a particular value, called an initialisation vector (IV) is given. A freestart collision is a collision where the attacker can choose ...


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


22

This isn't necessarily unexpected. 32-bit platforms vs 64-bit platforms can make a significant difference, as well as the amount of data you're hashing. $ uname -m x86_64 $ openssl speed sha256 sha512 The 'numbers' are in 1000s of bytes per second processed. type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes sha256 ...


21

Observation: An individual 1-byte pearson hash behaves like an 8 bit block cipher, encrypting the initial state using the message as key. This means that given a fixed message, each possible initial state produces a different output. This implies that a combined hash will never contain duplicate bytes. Without this property a hash would forget about the ...


20

No, it is not possible to construct a function $\operatorname{Hash}$ with the desired properties, as long as an adversary is able to obtain the output of that function for arbitrary input (even if the function takes an additional secret parameter unknown to an adversary). Proof sketch: given $A=\operatorname{Hash}(X)$ for unknown integer $X$, we can find ...


16

SHA-512 has 25% more rounds than SHA-256. On a 64-bit processor each round takes the same amount of operations, yet can process double the data per round, because the instructions process 64-bit words instead of 32-bit words. Therefore, 2 / 1.25 = 1.6, which is how much faster SHA-512 can be under optimal conditions. Of course there is memory overhead, ...


16

Contrary to the other answer, I'll be assuming the hash function is of the password-oriented kind; and my answer will be: input size has almost no influence on speed in good practice, even for much longer input than in the question. Password-oriented (or entropy-stretching, key-stretching) hash functions are, for example, suitable to transform a (password, ...


16

As Richie Frame noted in the comments, you basically listed them in order of ascending collision resistance. The latter hashes have greater collision resistance due to their increased output size. With the exception of SHA-1 and MD5, this is denoted by the number in the name of the algorithm. For example, SHA-512 produces 512 bits of output. The size of ...


15

HMAC remains unbroken with MD5 and SHA1 because it has a secret key that the attacker doesn't know. Therefore, the attacker cannot carry out huge computations on itself (as is required for finding collisions). [A parenthetic comment: please do not misunderstand me; MD5 is completely broken and should not be used anywhere including in HMAC.] In contrast, when ...


12

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


11

Contrary to your assumption, this is done, and it is secure: For instance, the hash functions SHA-224 and SHA-384 are basically the same algorithms as SHA-256 and SHA-512! The only differences are in the initial values for the Merkle-Damgård construction used internally and, of course, in that only the first $224$ or $384$ bits of the resulting hash are ...


11

The functions used by SHA-2, called $Ch$ and $Maj$ are defined like this in the standard: $$Ch(x, y, z) = (x \land y) \oplus (\lnot x \land z)$$ $$Maj(x, y, z) = (x \land y) \oplus (x \land z) \oplus (y \land z)$$ However, an equivalent way to define them replaces the XOR with OR, as the standard (pdf) states: Each of the algorithms include $Ch(x, y, ...


11

First of all, yes, the message digest is the hash of the message. Secondly, do not mix things up. You are talking about public key encryption and signature. Let's redefine them to make sure we have everything right. Alice and Bob got pairs of key ($A_{pub}$, $A_{priv}$), ($B_{pub}$, $B_{priv}$). Alice knows $B_{pub}$ and Bob knows $A_{pub}$. Alice wants ...


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


10

I'll review the standard mathematical notations used for $H_1:\{0,1\}^*\times\mathbb Z_p^∗\to\mathbb Z_q^∗$ , going from the bottom up. Hopefully, that will make the rest evident. $\{0,1\}$ is the set with the two elements $0$ and $1$, known as Booleans. $\{0,1\}^k$ (for some non-negative integer $k$ ) is the set of tuples with $k$ Booleans, or ...


10

Hash functions must be public, so if you want use RSA as hash function you should fix $K$. Now let $n$ be the RSA module and $H$ denote RSA hash function. We have $$H(M)=H(M+n)$$ so this function is not second preimage and collision resistant. Also this system is not first preimage resistant (with known public and private key): Let $M^k=h \pmod n$ ...


10

Because it is not secure enough. Hash functions rely a lot on diffusion (a single bit change must change half of the other bits) and confusion (the value of a bit should depend on the value of other bits). This is also known as the avalanche effect. Because it lacks a permutation, my first intuition: it lacks diffusion and has weakness to differential ...


10

So in general, isn't this equivalent to what Bcrypt and PBKDF2 do in terms of password storage security? PBKDF2, yes, pretty much. The only real difference is that salt/password are used the other way around, with the password mixed in at every step. Bcrypt, however, is different. In your case an attacker only needs a small amount of memory compared ...


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


8

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


8

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


8

Grover's algorithm treats the function it is evaluating as a black box and finds, with high probability, an input to the black box such that it outputs a specified value in $O(N^{1/2})$ evaluations of the function. Since Grover's algorithm works on the function as a black box, your modification does not hinder Grover's algorithm at all in finding the ...


8

They don't, and in fact the sponge construction used in Keccak (SHA-3) allows for variable length output. In other hashes the Merkle-Damgård construction was used which has a fixed output length due to the nature of its design. But there is no reason to not allow for variable output length other than ease of development or use.


8

I think it's more helpful to think of checksums as toned-down versions of message authentication codes (not hashes). Message authentication codes (MACs) are designed to detect any modification to a message, while it is in transit. They are secure against even adversarially-chosen modifications. Checksums are designed to detect some modifications to a ...


8

You are correct: The 'workhorses' or primitives of cryptography, hash functions and block ciphers, can be used in such a way that they accomplish each others tasks: A hash function can be used to generate a key stream just as a stream cipher or block cipher in CTR mode (see e.g. Salsa20). And a block cipher can be transformed into a hash function (e.g. a ...


7

SHA-512 (and SHA-384) is usually faster on 64-bit platforms, and SHA-256 is usually faster on 32-bit platforms.


7

Well, if you can assume that the website hasn't been hacked, then providing a SHA2 hash of a program would allow you do make sure you downloaded (from anywhere on the internet) a good version of the software. You are right, however, that since the method is publicly known, if someone can replace the binary on the site, they can also replace the hash on the ...



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