# Tag Info

10

Well, first of all, you need to be clear about the meanings of various cryptographical primitives. Cryptographic hash function; this is a function that takes an input string, and generates a hash. The idea is that we don't know how to create two input strings with the same hash, and so the hash can be used as a replacement for the original string. Now, ...

8

Preimage resistance is about the most basic property of a hash function which can be thought. It means: For a given $h$ in the output space of the hash function, it is hard to find any message $x$ with $H(x) = h$. (Note that the it is hard here and in the next definitions is not formally defined, but can be formalized by looking at families of hash ...

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

5

The answer to the original question would have been: Yes, it would be impossibly difficult to exhibit workfactor, salt, password0, password1 such that bcrypt(workfactor, salt, password0) = bcrypt(workfactor, salt, password1); but even if that was feasible, it would not matter much, because in normal use at least one of the password is unknown to an adversary ...

4

Accidental collisions are interesting for certain applications, and one would expect accidental collisions to occur less frequently in a system than malicious collisions. So, if you are not worried about malicious collisions, only accidental, it is easy to compute how many digests you would need to compute before seeing an accidental collision. If the ...

3

As far as we know, it is totally infeasible for anyone to create an RSA private key with a public key that has a specific 32 character fingerprint. This remains true if you give the adversary a budget of a few billion dollars; the best approach for an adversary would be to try to break in and steal (or purchase) the private key (and the second best approach ...

3

If the hash outputs 160-bit integers, and the product operation is integer multiplication, then this is probably not secure, for reasons fgrieu outlines. For instance, about $1/2^{19}$ of all 160-bit integers are $B$-smooth, if we take $B$ to be the $2^{20}$th prime. Consequently, after hashing $2^{45}$ different candidate messages, we expect to find about ...

3

I'll assume that in $H(S)=\prod_{x\in{S}}{h(x)}$, the notation $\prod$ stands for the product of the integers represented by the bitstrings $h(x)$. If $\prod$ stands for a product on some (semi)group other than $\mathbb N$, tell us which! There really are three different questions: In the title: Is $H$ collision resistant? That is: is it possible to ...

3

Pre-image resistant but not 2nd pre-image resistant? describes the relationship between the three basic hash function security notions: Collision Resistance, Second Preimage Resistance and Preimage Resistance. In short, Collision Resistance implies Second Preimage Resistance (but not vice-versa) - there is a good diagram on page 4 of RogawayShrimpton04 that ...

3

While the EAX mode permits truncating the tag to any length $\tau$ between 0 and $n$ bits, where $n$ is the block size of the underlying block cipher, this should only be taken as a statement that truncating the tag in EAX mode does not introduce any security issues beyond the obvious (an attacker only needs $2^\tau$ attempts to froge a $\tau$-bit tag by ...

3

Often the hash (iterated and salted mostly) of a password is saved in a database, instead of the password. If a user logs in, the hash is computed and compared against the stored hash value. This way a user that can see the database of hashes does not see the password directly, but this property depends crucially on the hash being resistant to a pre-image ...

3

A collision attack is the ability to find two inputs that produce the same result, but that result is not known ahead of time. In a typical case (e.g., the attack on MD5) only a relatively small number of specific inputs are known to produce collisions. Collision resistance obviously means that a collision attack is difficult (for some definition of ...

3

Yes, it makes sense to truncate the hash to 128 bits. The security proof actually says that if finding a preimage for F requires effort 2^n, then breaking the Lamport signature scheme with G having k-bit digests requires effort (2^n)/(2k). So strictly speaking, with F truncated to 128 bits and G having 256 bits (2k=512=2^9), you will have 128-9=119 bits of ...

2

No, it's not possible. RSA based signatures can only be generated if you know the private key. At the RSA primitive level, signing is the same as decrypting a message (where the data being decrypted in this instance is a hash of the message). If you change the hash, then verification of that signature would fail. Without knowledge of the corresponding ...

2

Yes, there have been real life inputs with collisions working on the full length of MD5. There is a pair of X.509 certificates that share an MD5 hash. There is also a pair of PostScript documents that are an MD5 collision. There are also two binary strings a mere 6 bits different that are a collision. The whole length of MD5 has been broken. Attacks that ...

2

I think most would agree that 2^128 is not plausible without UFO space alien technology (i.e., wildly successful quantum computers). There is no currently known way to find collisions over SHA-2-256 in any plausible amount of time, with any plausible number of inputs. As long as the key is secret, there is no known way to someone to find a username or ...

1

An asymptotic formalization cares only about what happens when the security parameter becomes "large enough". Since we use (essentially) one fixed security parameter, it is certainly possible to construct cryptosystems that would be insecure for some fixed security parameters, but secure in an asymptotic formalization. This means that a non-asymptotic ...

1

Hash functions are usually designed to be both collision and preimage resistant. In practice, due to lower complexity, collision attacks usually come first. For instance, collisions for MD5 were theoretically constructed in 1996, and practically in 2004, whereas the first preimage attack with complexity 2^123 appeared in 2009 and has not been much improved ...

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