Linked Questions

38
votes
2answers
11k views

How does hashing twice protect against birthday attacks?

The bitcoin wiki says: Bitcoin is using two hash iterations (denoted SHA256^2 ie "SHA256 function squared") and the reason for this relates to a partial attack on the smaller but related SHA1 hash. ...
18
votes
5answers
2k views

How many hex digits do I need to compare when manually checking hash functions?

I sometimes run sha256sum on large files after transferring them from one place to another, and will just skim the hash output to verify it's correct. But, I usually just look at the first/last 5 or 6 ...
11
votes
1answer
6k views

Are there any well-known examples of SHA-256 collisions?

The popularity of SHA-256 as a hashing algorithm, along with the fact that it has 2256 buckets to choose from leads me to believe that collisions do exist but are quite rare. Are there any well-...
4
votes
2answers
7k views

Computational requirements for breaking SHA-256?

Let's define "breaking" a hash function $H$ as being threefold (corresponding to the main properties of a cryptographic hash function): preimage attacks to get $m$ knowing $H(m)$ second-preimage ...
9
votes
2answers
523 views

Is there a guarantee that for each possible hash y there exists a number x such that with hash function H, H(x) = y?

Specifically talking about SHA-256 here and its involvement in Bitcoin, this was a question someone asked me which I didn't know the answer to. Yes, I am aware that SHA-256 can only have a hash from $...
3
votes
1answer
630 views

Difficulty of collision vs preimage vs second-preimage attacks

It seems at first glance that brute-forcing a collision would be exactly as difficult for all of them. They all (I would expect) work like this: select a hash value, and then try messages to get an ...
3
votes
1answer
615 views

Birthday attack for combination of hashes

I have to answer the following question for a homework assignment: You have a hash algorithm that converts a $2\cdot n$ bit number to an n bit number. How many hash values do you have to ...
1
vote
1answer
748 views

Is CRC32 birthday attack independent of input?

I have a configuration table which stores all device of a system and the corresponding serial numbers : ...
2
votes
2answers
199 views

More general - what is the hard problem of recovering r from r*p mod q?

I would like to know the cryptographic hard problem that is most closely tied to recovering integer $r$ from the modular product $r\times p\mod q$. (This is a simplification of an earlier post that ...
0
votes
1answer
381 views

Doubt about the possible attacks on HMAC

I have a question about the security of HMAC: If I know the value of the seed and the value of the HMAC but I don't know the key then I can't do the birthday attack because I can't generate an ...
2
votes
1answer
121 views

Is Paillier secure from known plaintext attack for single character message?

Assuming I have three messages m1,m2,m3 where m1=m2=m3=1 and I compute c1,c2 and c3. Does that mean that c1=c2=c3 in cipher-text from ? If not, how many times can I encrypt a message m=1 and still ...
1
vote
2answers
143 views

On a lower bound for the birthday problem

I'm now familiar with a lower bound for the birthday problem as exposed in the theorem A.16 of Katz and Lindell book (alternatively see this webpage). If one denotes by $C(q,N)$ the probability of ...
1
vote
1answer
223 views

hash collision chance using a 5 chars hash made of a-z A-Z and 0-9 (62 chars total)

What is the chance for collision or resistance of a hash made out of 5 chars randomly picked from this sets a-z A-Z and 0-9 (62 ...
0
votes
3answers
100 views

Derivation of birthday paradox probability

I am trying to come up with an explanation of the probability of birthday collision. $P$(no collision among t people) = $(1− \frac{1}{365}) · (1-\frac{2}{365}) ··· (1-\frac{t-1}{365})$ For one ...
4
votes
1answer
106 views

For a random permutation $P$, what's the probability of the following event?

For a random permutation $P$ and $q$ distinct inputs $x_1,\ldots,x_q\in\{0,1\}^n$, what's the probability of the event that there exists at least one collision among $\{P(x_1)\oplus x_1,\ldots,P(x_q)\...

15 30 50 per page