# Tag Info

3

We learn the first 32 bits of the SHA1 hash of the secret (well, it's actually the SHA1 hash of the secret concatenated with some known stuff, but that amounts to the same thing). We can enumerate all $2^{56}$ possibilities for the secret. We expect that about $1/2^{32}$ of them will produce a matching 32-bit value, so about $2^{24}$ candidates for the ...

2

If you have an $m-$bit output decent hash function (such as SHA1) and you're hashing $k-$bit values, and your list $L$ of candidates is not tiny ($2^{56}$ which is the size of possible candidates, isn't) the function will behave like a random mapping on any substring of its' output, so for the 8-bit prefix you're considering you will be expected to get ...

3

SipHash is a MAC (aka Pseudo Random Function Family) with 64-bit output and 128-bit key, rather than a hash (aka random public member of a Pseudo Random Function Family). It is explicitly designed to be used with a secret random key. Quoting Jean-Philippe Aumasson and Daniel J. Bernstein's SipHash: a fast short-input PRF (in proceedings of Indocrypt 2012): ...

0

You could do something fairly simple, such as $UserSecret = Random()$ $UserID = HMAC(ServerSecret, UserSecret)$ Send the user the two values. When he reconnects, he sends the two values back. If re-calculating $UserID$ with the user's $UserSecret$ gives the same $UserID$ then that proves (to a high degree of certainty) that it's the same person that was ...

4

Word size is not a term originating in cryptography. Rather it is a term which came from the area of computer architecture. Here it specifies either how many bits are transferred over a bus at a time or the size of a register. When used in the description of cryptographic primitives (such as a compression function or a block cipher), it covers the size of ...

3

The word size in hash functions means the size of the integral unit of operation for the internal transformations. For example: for SHA-512, you'll get some input, split it and then perform operations on 64-bit words (=unsigned integers, like modulo addition or shift) whereas for SHA-256 you'll use 32-bit operations (= operations on 32-bit-integers, like ...

2

Well, if you construct what you described you basically create a function $f: \{0,1\}^{2m} \rightarrow \{0,1\}^m$. As you correctly pointed out these two strings give the same when xor'ed. So the messages $10101111$ and $00000101$ will result in the same xor and hence will get mapped to the same hash, resulting in a second preimage as you found two $x,x'$ ...

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

3

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

I did not quite understand the question. Specially the part that says under the context. The answer is no. because, The output of a hash is a fixed value, for any given input of any length (If the length of the input is shorter than the block size, depending on the HASH algorithm being used, an appropriate padding scheme is present). So whether the ...

2

No, since passwords are usually far from uniformly distributed.

6

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

28

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

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

0

I looked more into it and saw that the state input is the data input of the block cipher and the data (that is being hashed) is the key input to the underlying block cipher (SHACAL). Thanks anyway.

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

Consider this hash: $$H(m) = m$$ Where we define it's domain to be messages of some arbitrary fixed-length. It is completely second pre-image resistant. It is not at all first pre-image resistant. Therefore: Second pre-image resistance does not imply first pre-image resistance.

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

0

Very basically, the hash collision it can be used to fool CA's to sign a certificate that stores one set of information in the certificate's attributes, while there the requester uses it to create one or more certificates with different attributes. The attributes in the certificate are as important as the public key that is being signed. They contain, for ...

0

Usually Hashes are not used by themselves for integrity for exactly the reason you state. To make them stronger we take the hash and encrypt it using the private key of the sender. This way anybody who has the sender's public key can decrypt the hash and check it against a new hash of the message, but a man-in-the-middle can not fake it since they do not ...

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

0

Combining 3 sources A,B and C is not obvious. The right thing to do is not A+B+C. It is A*B+C within a field (E.G. a GF(2^8) field, which maps to bytes). This is based on a 2006 paper by Barack Impagliazzo and Wigdersen (http://dl.acm.org/citation.cfm?id=1328011) that shows that this is a good extractor. You still need to post extract the output with an ...

0

The Von Neumann whitener would not meet your needs, nor would the more modern Yuval Peres whitener (which is an iterated Von Neumann algorithm). This is because the input requirements for the algorithm are that the bits be statistically independent. No raw noise source provides statistically independent bits. Your only choice is to use an extractor that is ...

0

$h$ is a (secure?) hash function. This is standard notation. Thank you Ricky Demer, who answered this question first (in the comments)

0

I'm not very familiar with hash functions, but consider the following toy example: take any hash function $H$, and define a new function $H'$ which on input $x$ discards the last bit and applies $H$ to the result. $H'$ is not collision resistant because flipping the last bit of any input does not change the hash. Yet this may not be immediately obvious, and ...

0

A typical X.509 certificate is the combination of data (including a public key $Pub_B$), and of a signature $Sig_A$ of that data, to be verified with an unrelated public key $Pub_A$. In order for the verifier to know which hash to use when verifying $Sig_A$, there is use for a field in said data specifying the hash used by $Sig_A$, and that's the purpose of ...

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

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

Top 50 recent answers are included