Hot answers tagged

60

The reason that salts are used is that people tend to choose the same passwords, and not at all randomly. Many used passwords out there are short real words, to make it easy to remember, but this also enables for an attack. As you may know, passwords are generally not stored in cleartext, but rather hashed. If you are unsure of the purpose of a ...


51

These types of cryptographic primitive can be distinguished by the security goals they fulfill (in the simple protocol of "appending to a message"): Integrity: Can the recipient be confident that the message has not been accidentally modified? Authentication: Can the recipient be confident that the message originates from the sender? Non-repudiation: If ...


48

For password-hashing, you should not use a normal cryptographic hash, but something made specially to protect passwords, like bcrypt. See How to safely store a password for details (this article advocates the use of bcrypt). The important point is that password crackers don't have to bruteforce the hash output space ($2^{160}$ for SHA-1), but only the ...


42

Combining is what SSL/TLS does with MD5 and SHA-1, in its definition of its internal "PRF" (which is actually a Key Derivation Function). For a given hash function, TLS defines a KDF which relies on HMAC which relies on the hash function. Then the KDF is invoked twice, once with MD5 and once with SHA-1, and the results are XORed together. The idea was to ...


34

SHA-512 truncated to 256 bits is as safe as SHA-256 as far as we know. The NIST did basically that with SHA-512/256 introduced March 2012 in FIPS 180-4 (because it is faster than SHA-256 when implemented in software on many 64-bit CPUs). SHA-224 is just as safe as using 224 bits of SHA-256, because that's basically how SHA-224 is constructed. What bits are ...


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


32

We call a primitive broken, if there is any attack faster than bruteforce/what we expect of an ideal primitive. Broken does not mean that there are practical attacks. There are no known collisions in SHA-1. Still we call collision resistance of SHA-1 is broken, because there is a theoretical attack that can find collisions using fewer than $2^{80}$ calls to ...


30

SHA-1 processes data by 512-bit blocks (64 bytes). For a given input message m, it first appends some bits (at least 65, at most 576) so that the total length is a multiple of 512. Let's call p the added bits (that's the padding). The padding bits depend only on the length of m (these bits include an encoding of that length, but they do not depend on the ...


30

If you repeatedly apply a generic function on its result, in a finite domain, you tend to obtain a "rho" structure: at some point, you enter a cycle whose length is (roughly) $\sqrt{N}$, where $N$ is the size of the output space for your function. In the case of MD5, $N = 2^{128}$ (MD5 outputs 128-bit values), so the cycle will have length about $2^{64}$ ...


29

You are correct that it is a "bad hash". In fact it is not a hash at all. I've worked at a company that used a slightly different scheme for obfuscating database keys/numbers in URLs. And I also worked for another company that used a scheme that looked surprisingly similar for unlock codes for electronic devices. The formula for converting "hashes" back ...


29

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

You were right with your ideas in the the original question. If what you want to protect against is pre-images then chaining hash functions produces a function at least as strong as the strongest of its two components: H∘(x) = H₀(H₁(x)) If what you want to protect against is collisions, then concatenation is at least as strong as the strongest of its two ...


26

As a general rule, you should avoid SHA1 for new applications and instead go with one of the hash functions from the SHA-2 family. As far as truncating a hash goes, that's fine. It's explicitly endorsed by the NIST, and there are hash functions in the SHA-2 family that are simple truncated variants of their full brethren: SHA-256/224, SHA-512/224, ...


24

It would be very freakish if it turned out to be true. It is not an expected property of SHA-512 to have such bijectivity. It would be worrisome, even, because that's a kind of structure that should not appear in a proper cryptographic hash function. Actually proving that SHA-512, for 512-bit blocks, is not bijective, would already be a kind of a problem. ...


23

Many cryptographic algorithms are expressed as iterative algorithms. E.g., when encrypting a message with a block cipher in CBC mode, each message "block" is first XORed with the previous encrypted block, and the result of the XOR is then encrypted. The first block has no "previous block" hence we must supply a conventional alternate "zero-th block" which we ...


23

The word "secure hash function" usually means (for a function $H$) Preimage resistance: Given a value $h$, it is hard to find a message $x$ so that $h = H(x)$. Second preimage resistance: Given a message $x$, it is hard to find a message $x' \neq x$ such that $H(x) = H(x')$. Collision resistance: It is hard to find two messages $x$, $x'$ such that $H(x) = ...


23

If taking the first or last bits of a SHA-256 output made any difference, it would be viewed as a serious blow against the security of SHA-256. Right now, no such weakness is known in SHA-256. So, as far as we know, you can use whatever bits you want. If you need a more "administrative" answer, have a look at SHA-224 (also specified in FIPS 180-3). This is ...


23

Would you use HMAC-SHA1 or HMAC-SHA256 for message authentication? Yes. That is a semi-serious answer; both are very good choices, assuming, of course, that a Message Authentication Code is the appropriate solution (that is, both sides share a secret key), and you don't need extreme speed. How much HMAC-SHA256 is slower than HMAC-SHA1? Those ...


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


21

I sent an email to Ron Rivest and got an answer back. The digits of $\pi$ are used as a sort of random number generator that is used in the Durstenfeld shuffle (see also Knuth vol 3, sec 3.4.2). Below is some pseudocode adapted from the description and code he sent me. S = [0, 1, ..., 255] digits_Pi = [3, 1, 4, 1, 5, 9, ...] # the digits of pi def ...


20

MD5 and SHA-1 have a lot in common; SHA-1 was clearly inspired on either MD5 or MD4, or both (SHA-1 is a patched version of SHA-0, which was published in 1993, while MD5 was described as a RFC in 1992). The main structural differences are the following: SHA-1 has a larger state: 160 bits vs 128 bits. SHA-1 has more rounds: 80 vs 64. SHA-1 rounds have an ...


20

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


20

Length extension attack The reason why $H(k || m)$ is insecure with most older hashes is that they use the Merkle–Damgård construction which suffers from length extensions. When length extensions are available it's possible to compute $H(k || m || m^\prime)$ knowing only $H(k || m)$ but not $k$. This violates the security requirements of a MAC. Like all ...


20

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


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


19

I do worry, but not for the resistance of SHA-3; I worry for its acceptance. Technically, what NIST wants to do is sound. They do want to somehow "break" a traditional rule, which is that a hash function with an output of n bits ought to resist collisions with strength 2n/2, and preimages (first and second) with strength 2n. Instead, NIST wants harmonized ...


18

If I get the suggested construction correctly, it is to 1) hash n values (with SHA-256); 2) add theses hashes, perhaps mod 2256; 3) hash the sum (with RIPEMD-160). This would be potentially unsafe: creating a collision or even second pre-image at step 2) reduces to a knapsack problem, and this has a poor safety record; it might be workable when the ...


18

Initially there was MD4, then MD5; MD5 was designed later, but both were published as open standards simultaneously. MD5 had been designed because of suspected weaknesses in MD4 (which were very real !). So MD5 was the first (and, at that time, believed secure) efficient hash function with a public, readable specification. MD5 was immediately widely popular. ...


18

A new result shows how to generate single block MD5 collisions, including an example collision: Message 1 Message 2 > md5sum message1.bin message2.bin > 008ee33a9d58b51cfeb425b0959121c9 message1.bin > 008ee33a9d58b51cfeb425b0959121c9 message2.bin There is an earlier example of a single block collision but not technique for generating it was ...



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