# Tag Info

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

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

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

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

14

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

14

The echo command appends a new line at the end, by default. The -n option omits this character. Compare these two executions: > echo -n "test123" | md5sum cc03e747a6afbbcbf8be7668acfebee5 > echo "test123" | md5sum 4a251a2ef9bbf4ccc35f97aba2c9cbda So the difference between the hash values is simply caused by the new line character.

13

Multiple hashing, in itself, is not a bad idea. What's bad is trying to design your own non-standard password hashing scheme, without understanding what features such a scheme needs in order to be secure. In fact, hashing the password many times can be a very good idea, as long as you do it sufficiently many times. This is one way to slow down the hashing ...

11

I restrict to hash functions $H$ with an output of some fixed size $n\ge1$ bit(s), accepting as input some strings, including all $n$-bit strings; MD5 (resp. SHA-1, SHA-256) is an example of such function for $n=128$ (resp. $n=160$, $n=256$). Whether there exists a solution to $H(x)=x$ depends on the particular hash function. If $H$ is a random function (as ...

11

Expanding then shrinking in SHA-1 refers to the process, performed for each round (each 512-bit block of padded message), of message expansion from 512 bits to 2560 bits; keeping only 160 bits of state for the next round. The later directly follows from the construction of SHA-1 as a Merkle-Damgård hash of 160 bit. The former occurs because SHA-1's ...

9

I don't see any obvious security problems in your approach. You can look into key derivation functions, that can provide some additional security in case one of the following occurs: Your password leaks Your secret number leaks A weakness is identified in the hash function There is a few usability issues, that would have to be addressed as well: ...

9

This is impossible for any generally useful hash: a hash must map all inputs to a fixed-length output, but you normally want to be able to take variable (and fairly long) inputs. The problem is that there are more inputs than outputs: you normally want to be able to hash any string up to a fairly big length, but the hash itself should not be too long, and ...

8

What Richie Frame describes above is correct. This is how most FDE solutions work. A new random encryption key is created whenever new container is created or disk is encrypted. That encryption key (often called Master Key) is then protected by users' password. In case of Truecrypt, master key is stored in volume header (link) and volume header is encrypted ...

8

No, because even SHA-512 was considered overkill from a security perspective. It has 256-bit collision resistance, which is unbreakable. (The link is about keys but a similar argument applies.) If you think large quantum computers will be efficient, a 512-bit hash makes some sense, but even then a 1024-bit one wouldn't. A quantum computer requires ...

8

If you mean exactly as likely, no, because the number of possible hashes is not a multiple of $100$. This is assuming all the hashes are exactly equally likely. You can come very close just by taking $SHA256 hash \pmod {100}$ This will be within one part in $\frac {2^{256}}{100}$, which is a very small number. If you want truly equal, check that the hash ...

8

When only using one-way hashing, is it possible to tell the number of characters changed between the old and new password? No. If the hash function is strong, even a single bit change will give a completely different hash. The only way to tell how many characters differ between a particular unknown hash value and a known password would be an exhaustive ...

8

The difference is in the choice of $m_1$. In the first case (second preimage resistance), the attacker is handed a fixed $m_1$ to which he has to find a different $m_2$ with equal hash. In particular, he can't choose $m_1$. In the second case (collision resistance), the attacker can freely choose both messages $m_1$ and $m_2$, with the only requirement ...

7

A fast 64-bit hash cannot be completely secure, since a $2^{32}$ brute force collision search is completely doable, and even a $2^{64}$ preimage attack could be feasible. As a MAC used for hash table keying, that doesn't really matter (unless you leak the key). Finding just a few collisions isn't a problem and gathering statistics for an attack would ...

7

A "generic attack" against a cryptographical primitive is one that can be run independently of the details of how that cryptographical primitive is implemented. The most obvious case is a cipher that takes an $N$ bit key; the generic attack of brute force takes a ciphertext, and attempts to decrypt it with all $2^N$ keys; when we find the known (or ...

7

You can in principle encrypt using a hash function, in the manner you describe (although what you have described is not necessarily a secure construction). What you are trying to do is generate a keystream from a hash function and a key. You can use counter mode to turn any strong pseudorandom function (PRF) into a stream cipher. CTR mode produces a ...

7

Yes. Let $H$ be a collision resistant hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is, $x$ and $y$ with $x\neq y$ and $H(H(x))=H(H(y))$. Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either $H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or $H(x)\neq H(y)$, hence $(H(x),H(y))$ is ...

7

The entropy for the output of SHA-256 truncated to its first $128$ bits when fed a random $128$-bit input is about $127.173$ bit, down from very close to $128$ bit before truncation (see final note). The truncation does not halve the entropy, because the halves are not independent. The right line of thought is that SHA-256 truncated to its first $128$ bits ...

7

I believe Thomas Pornin's answer is by far superior to mine, but perhaps this answer can provide a simplification to his answer. When you initially hash some data, the possible input is infinite/limitless. You could input "abcdefghi...", "123456...", etcetera. However, the resulting hash possibilities are finite/limited. One of the beautiful things about ...

7

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

6

No such function with either property would meet the requirements of a secure hash function; either of those properties would make it easy to find preimages, that is, given a value $H(x)$, you can find a value $y$ with $H(y) = H(x)$. First off, I assume that $n$ is a constant for the hash function; if we were to assume that the first property holds for any ...

6

There are some attacks on hashes keyed with a secret suffix. The proper primitive for deriving a secret from keys/passwords and an identifier is a key derivation function. In your case, if the secret number is random a fast key derivation function, like HKDF, would be enough to expand the key into several site-specific hashes. In that case there's no need ...

6

PBKDF2 (as defined by RFC 2898) is a function of the form $$DK = \text{PBKDF2}(\text{PRF}, Password, Salt, c, dkLen)$$ In most practical use cases, the $\text{PRF}$ is $\text{HMAC}$ instantiated with a Merkle-Damgård hash function such as $\text{SHA-1}$. The time to compute $\text{PBKDF2}$ is roughly linear with the iteration parameter $c$, all other ...

6

It mainly depends on how the algorithm was selected. If it was selected by a public competition like for AES, then it is likely to be secure. If it was forced in by the NSA such as Dual-EC random number generator, then you may have some doubts. Other questions you may want to ask yourself are: Is this an "original" algorithm or was the problem that it ...

6

The cost of finding collision for SHA-1 is currently estimated as $2^{61}$ SHA-1 calls. To understand how much (or how little) it is, we could look at Bitcoin mining. Right now (September 2014) the entire mining network computes 200,000,000 giga-double-hashes of SHA-256 per second, or $2^{61}$ hashes in three seconds.

6

The definition of perfect hash functions do not have any security/cryptographic requirements. For example, the hash function that simply outputs the first n bits of any string is a perfect hash function on the set of n bit strings. Obviously this function does not hide the input at all. So the answer to your questions is that it depends on the hash ...

5

Firstly, How much time will it take to crack PBKDF2 while using a 9 character password? and how do I calculate the cost? I'm not specifying any specific system or platform. If a brute force attack is made using the best ever super computer around how much time will it take to crack it? Unless the underlying PRF is broken, brute force and dictionary ...

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