# Tag Info

6

The answer to your edited question is "yes, it is possible". As a trivial example, let $H$ be an ideal $k$-bit hash function. Due to the existence of the generic birthday attack, $H$ provides only about $k/2$ bits of collision resistance — that is, an attack can, on average, find a collision after about $2^{k/2}$ hash function evaluations. Denote ...

4

I am literally quoting the paper here. You should really try to read the paper properly first before asking questions. In the notion of [22] the adversary does not get credit for finding any old collision. The adversary must still find a collision $M, M'$ but now $M$ is not allowed to depend on the key: the adversary must choose it before the key $K$ is ...

3

Can insecure algorithms be combined to form a secure algorithm? Yes: Think of any secure round-based block cipher. The independent rounds are not secure, but put together the overall cipher is. I think my favourite example is (currently) the Even Mansour cipher, which combines two xor operations and one unkeyed permutation to form a secure cipher. nb: I ...

3

You want a pair of functions $(f_1,f_2)$ from a set $S$ of possible passphrases to a key set $K$, that is $f_1,f_2: S \rightarrow K$. The functions are public, in the sense that they can be computed by anyone. Your security goal is that the cost of finding $f_2(pw)$, knowing $f_1(pw)$, should be roughly as expensive as finding $f_2(pw)$ by searching for ...

3

SHORT: SHA-1 does not have explicit key. HMAC is the way to construct keyed hash from SHA-1. Collision free means that there is no different inputs known to hash which give the same result. DETAILED The most of the currently used cryptographic hash functions have some specific initial values embedded within them. Usually Nothing up my sleeve numbers are ...

3

As a simplified case, consider a sponge hash function made from an ideal 160-bit block cipher with a 256-bit key, and mixes in a 32-bit word each round. It would be better to use an LFSR to generate the sequence of keys for each round, but let's say this simplified hash function is \begin{align} H(0) &= 0 \\ H(N) &= E(0, H(N-1) \oplus ... 2 Basically all hash functions have this "problem". Pretty much all are finite in length. The real problem happens when collisions can be generated in less work than brute force. Due to the birthday problem with an n-bit hash function we would expect to see a collision after computing n/2 digests. If n is large enough (say n=160) we would not expect ... 2 We are talking about hash-function families \{h_k\}_{k\in K} here. The parameter k is used to rule out the trivial collision search algorithm that simply prints a collision for a given h (such algorithms exist, but are difficult to find). For large K such an algorithm would be too large. The parameter k is called a key, but it is not actually ... 2 We often rank cryptographic problems according to how hard they are. One problem is not harder than another problem if an algorithm that solves the second problem can easily be turned into an algorithm that solves the first problem. Your question considers two issues: how hard the adversary's job is, and the strength of our assumption. If one problem is not ... 2 I would advise against this. When implementing slow-hashing (such as bcrypt or scrypt), it's usually recommended to select as high a work-factor as is tolerable (in relation to how much time the user is willing to wait, and/or how much strain you're willing to put on your server). Assuming you're working within this constraint, using two distinct slow ... 2 There is no why it is identical. The input form of the data does not influence what the output of a secure hash function should look like. The output of a hash should be unrelated to the output except for the mapping performed in the hash function itself. There should be no method of calculating the output other than to execute the hash function. The best ... 1 Evaluating, we have that Sha_1(38607310235)=6502c8f9f5c222b9598d4e074fd3431f506948bc So, I'm guessing the question you're actually asking is: Given an 11 digit number x, find y such that L[H(y)]=x, where L(\cdot) takes the last 11 hexadecimal characters, and H(\cdot) is the SHA-1 hash function This problem is believed to be hard to do, so ... 1 Obviously not. For example, the function h2(x) = 0 is not collision resistant, h2(h1(x)) shares that property. This remains true even in less trivial cases; if h2 is not collision resistant because its output is too short (it has an n-bit output, with 2^{n/2} being small enough to do a search over), then h2(h1(x)) will also be too short 1 Will they always be collision resistant? No For example, let h_2(x)=0. Then, h(x)=h_2(h_1(x))=0, which certainly isn't collision resistant. Can it be collision resistant? Yes For example, suppose we define h_1(x)=\mathrm{SHA256}(x) and h_2(x)=\begin{cases} 0 & |x|=1 \\ \mathrm{SHA256}(x) & \mathrm{else} \end{cases}  Then, since ...

1

No, exposing such a hash does not compromise the RSA private key, unless the hash function is sufficiently and severely broken. Of course, you don't need to hash the private exponent to identify the key. You can simply use the modulus or a hash over the (public) modulus to identify the key. This has the additional advantage that that ID will also match the ...

1

The verifier and logger start with a seed for a forward-secure pseudo-random number generator. To denote a valid ending of a log, append the string of the next $b$ bits of the PRNG's output to the end of the log. $\;\;$ To add a log entry, get the next $\:b\hspace{-0.03 in}+\hspace{-0.03 in}k\:$ bits of the PRNG's output, use the last $k$ of those bits to ...

1

I don't think doing this by hand is the right way to do this. Pencil and paper systems are unreliable because humans just aren't as good at being robots as, well, robots! Most of the work in computing a secure MAC is hugely monotonous and a single mistake, anywhere during the process, could completely destroy any security you thought you had. If your ...

1

Because MD5 has a 128 bit output, we knew up front that we could find an MD5 collision by simply hashing $2^{64}$ values; with that many values, we're likely to see the same output twice (Birthday Paradox). Today, $2^{64}$ would not be considered sufficient; there are currently large entities that could perform that much work, if it was important enough. ...

1

I don't know if that counts, but authors of recently selected SHA3 function Keccak (http://keccak.noekeon.org/) mention its ability to perform Full Domain Hashing: Variable output length hashing is an interesting feature for natively supporting a wide range of applications including full domain hashing [...]

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