# Tagged Questions

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

31 views

### Why k-lists generalized birthday problem when $k=2$ is classical birthday problem?

David Wagner in his article A Generalized Birthday Problem in CRYPTO 2002 says that in k-dimensional (also k-lists) generalization of birthday problem (GBP), when $k=2$ "this is just the extremely ...
231 views

### Why Merkle Tree doesn't suffer Birthday attack?

I am trying to understand why Merkle Tree doesn't suffer the birthday attack? Can you help me?
1k 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?
95 views

### How is the block size of a block cipher related to how susceptible the block cipher is to a birthday attack?

For example what can you say about how susceptible Triple-DES is to a birthday attack due to the fact that it has a block size of 64-bits.
65 views

### Block cipher mode of operation with beyond-birthday-bound security

I am looking for block cipher modes of operation that are secure even when the number of blocks encrypted exceeds the birthday bound.
158 views

### Is finding collisions in a part-hash not often enough a bad problem?

My situation: I've been working now for a couple of months on my own unique hash function, I've changed it many times and had two main versions but I won't bore anyone with the details of my work; at ...
123 views

### Is there any function that does not suffers birthday problem?

I am eager to know that if there is any function that does not suffer birthday problem and how to prove it formally that the function is not suffering the birthday problem.
79 views

### What are the time considerations with regard to security against birthday attack?

When designing security for a physical safe, one of the critical specifications is how long will the safe resist attack, this tells you how quickly you must detect and respond to an attack on the safe....
454 views

### Applicability of birthday attack to AES brute force

Is the following snippet from a recently published cryptography book correct? EDIT: Expand the snippet from the book to make the context (symmetric key search) more clear. You can apply this to ...
74 views

### k(k-1)/2: Combinations and the Birthday bound

Disclaimer: I'm new to cryptography. Background: I'm reading Cryptography Engineering by Ferguson, Schneier, and Kohno, where, in Chapter 2, the authors write this: Question: What is $k(k-1)/2$ ...
50 views

### Effect of the birthday bound on AES-GCM

What is the effect of the birthday bound on the security of AES-GCM, when a very large number of messages are encrypted? I am looking for attacks that are useful in obtaining information about the ...
93 views

### Probability approximation of no collisions

I am comparing the actual probability of no collisions to the probability approximation formula of no collisions from the Understanding Cryptography text. The approximation is as follows: P(\text{...
131 views

### Is it possible to reverse the birthday attack calculation?

I find that for every 100 password salts in our database, we only average 94.73 distinct salt values (averaged over a total of around 18 million). Is there a way to take that observation and calculate ...
119 views

### Birthday-attack calculation in planning password salting strategy

The book Cryptography Engineering by Fergusun, Schneier, Kohno section 2.7.1 explains Birthday Attacks: "In general, if an element can take on N different values, then you can expect the first ...
346 views

### Formula for the number of expected collisions

Say we have a hash function that produces $n$ bit outputs. From the birthday problem that after around $\sqrt{2^n}$ different inputs to the has function, we can expect a collision. Say instead that ...
2k views

### What are the differences between collision attack and birthday attack?

From my understanding both types of attack, collision and birthday, are based on the principle of two randomly/pseudo-randomly chosen plaintext to hash to the same value. I don't want to launch any ...
1k views

### Practical brute-force attack on 128 bit encryption

In brute-force attack calculations cryptographers say we should assume an attacker will find the key after $2^{(n/2)}$ tries. If n=128, then n/2=64. We know that this is practical (A 64 bit key is ...
177 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 ...