# Tag Info

37

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

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

28

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

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

17

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

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

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

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 ... 11 The disadvantage of this approach is that block ciphers are not necessarily designed with this goal in mind. Specifically, AES has related-key problems, and DES completely breaks in Davies-Meyer. In general, block ciphers are not necessarily ideal ciphers and should be used as intended which is as pseudorandom permutations. In contrast, SHA256 and the like ... 10 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, ... 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 value.... 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 to ... 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 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$\binom{...

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

7

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

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

I see two problems with this idea. The first problem is Shor's algorithm; that's a quantum algorithm that is able to find the cycle length of a group (and if you can solve that problem, it is easy to factor and compute discrete logs). In this case, if we define the group of elements defined by the initial start state in the signature, where $H^n$ is the ...

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