# Tag Info

22

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

5

Here are some hints on how it's done on Mega: The password provided is passed through a KDF to derive a key, that is used to en-/decrypt the master key (later provided by the server through an API call). To bring it down to the crucial bits: The KDF applies $2^{16}$ rounds of AES-128 with it. The details can be found in the function prepare_key() of the ...

4

A compression function takes two fixed size inputs: a chaining value and a message and returns a fixed size value. So it's essentially a hash function with fixed input size. Merkle-Damgård is a domain extender, which turns that compression function into a hash which supports arbitrarily long messages. MD uses the output of the compression of one block as ...

4

Indeed hashing is used to ensure integrity, but not this way. What you have in mind it seems is sending (msg, Hash(msg)). Indeed this is not secure because of the attack you describe. The first step starts with something you say by yourself: hashing algorithms are universal algorithms The name is not univesal but public, it means anyone knows it. ...

4

Yes, these notations always seem to mean that H^n(x) (or $H^n(x)$ in mathematical notation) means that $x$ is the first input, and that the next outputs are a hash of the previous output: H^0(x) = x // just defined as x below H^1(x) = H(x) H^2(x) = H(H^1(x)) = H(H(x)) H^3(x) = H(H^2(x)) = ... = H(H(H(x))) H^4(x) = ............... = H(H(H(H(x)))) ...

3

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

3

Your math is wrong — not the numerical calculation, but your interpretation of it. There are $256^{17}$ possible inputs and $256^{16}$ possible outputs. On average, there are $256$ inputs for each output. But there are no guarantees that this is the case for all outputs: it's in fact overwhelmingly likely that some outputs have more and others have fewer. ...

3

Yes, the output should have an entropy of 512 bit (or slightly less). Using it as a key is a good idea. If you want to generate more than 512 bits of key material out of the 512 bit you need to use a Key Derivation Function (KDF). You do not need to stretch the key, because it is no password and has a high amount of entropy - enough to make any brute force ...

2

If I understand your question correctly, you want to generate a short value $v(T)$ from a table $T$ such that if $T_1$ and $T_2$ have the same size and the same elements in each corresponding cell, then $v(T_1) = v(T_2)$, and if the tables have different sizes or different elements then $v(T_1) \ne v(T_2)$. What you need for that is two ingredients: A ...

2

The entropy of passwords is not universally distributed. So hashing can be used to concentrate the input of a hash. The concentration of entropy from another source is called extraction by HKDF, which is a key based key derivation function (which should not be used for passwords). This is from the introduction of RFC 5869, which defined HKDF: Thus, the ...

2

No, since passwords are usually far from uniformly distributed.

1

If the passwords are uniformly randomly generated among all possible byte sequences of the chosen length, then there is no point in having a password that's longer than min(hash length, brute force resistance) where brute force resistance is the number of brute force attempts that you want to resist. Picking a 32-byte password gives you a huge safety margin ...

1

Using AES as a Davies Meyer compression function is a bad idea: It has a block size of 128 bits, which limits its collision resistance to 64 bits, which is rather weak. This limitation could be overcome by using Rijndael with a 256 bit block size, but then you'd need to use a higher number of rounds. AES has been designed to work with randomly chosen ...

1

Using simply a hash function is not strong enough, even if the key is not stored. We the users tend to choose very crappy passwords, such as "1234" or "password". If you only use a hash function for generating the key, then there are a lot of chances that the generated keys are SHA256("1234") or SHA256("password"). That is, this method is very vulnerable to ...

1

It all depends on whether the rest of the input is guessable. The best attack we know for finding the input to SHA1, given the output and partial knowledge about the input, is a brute-force attack: For each candidate at the full input, try hashing that input with SHA1 and see if it matches the known output. So, the running time of the attack will be ...

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