A birthday attack is a cryptanalytic technique. Birthday attacks can be used to find collisions in a cryptographic hash function. For instance, suppose we have a hash function which, when supplied with a random input, returns one of $k$ equally likely values. By repeatedly evaluating the function on ...

learn more… | top users | synonyms

-1
votes
0answers
21 views

cryptographic hash function [on hold]

Consider an ideal cryptographic hash function H : {0, 1}∗ → {0, 1}n, in other words, H takes a string of arbitrary length and returns a string of n bits, and it is assumed that H acts like a “random ...
0
votes
1answer
86 views

How much work is required to detect multiple collisions for a hash function?

Assume an ideal hash function of output size n bits, detecting one collision requires approximately 2^(n/2) evaluations of the ...
1
vote
1answer
109 views

N way collision of hashes

For a collision $H(A_1) = H(A_2)$, the number of queries is $T^{1/2}$ where $\log_2(T)$ is length of hash output. Then, what would be the number of queries requried to find an $n$-collision ($H(A_1) = ...
2
votes
1answer
290 views

CMAC vs HMAC security strength

From the perspective of a Birthday Paradox attack, isn't it true that CMAC based on AES-128 is weaker than HMAC-SHA-1? The attack on CMAC-AES-128 requires about $2^{64}$ operations whereas the same ...
0
votes
1answer
114 views

No Birthday Attack to TCR

I'm reading the paper “Collision-Resistant Hashing? Towards Making UOWHFs Practical” , which compared TCR (Target Collision Resistant) and ACR (Any collision Resistant). It says we wish to stress ...
11
votes
1answer
1k views

Three-way hash collision

According to the birthday paradox we need approximately $O(|T|^{1/2})$ samples from the tag-space to find a collision for a hash function $h:K\times M \to T$. But how many samples are needed to find a ...
5
votes
3answers
493 views

Birthday Attack

I am reading the birthday attack in wikipedia. We consider the following experiment. From a set of $H$ values we choose $n$ values uniformly at random thereby allowing repetitions. Let $p(n; ...
10
votes
1answer
4k views

How does a birthday attack on a hashing algorithm work?

A "normal", brute-force attack on a cryptographic hashing algorithm $H$ should have a complexity of about $2^{n}$ for a hash algorithm with an output length of $n$ bits. That means it takes about ...
9
votes
2answers
294 views

Why would you expect to find a collision in a hash function after approximately $\sqrt{n}$ hashes?

I can't get an intuitive understanding of why it's $2^{(\frac{n}{2})}$ and not $2^n$, where $n$ is the number of bits of which the key consists.
11
votes
1answer
719 views

Security of N bit HMAC

Lets say that I am using 128 bit HMAC. How many operations are needed to find a "non secure" message. Is a birthday attack possible?