# Questions tagged [birthday-attack]

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 $1.2\sqrt{k}$ different inputs, it is likely we will find some pair of inputs that produce the same output (a collision).

86 questions
Filter by
Sorted by
Tagged with
31 views

### MuSig: could the rogue key attack be mitigated by using commitments instead of key transformations?

Background MuSig is an extension of/derivation from Schnorr signatures using cyclic groups on elliptic curves. In the original paper, the authors point out that naive multi-Schnorr is vulnerable to a ...
69 views

### Is generalized birthday attack only suitable for the problem with multiple solutions?

In David Wagner's article A Generalized Birthday Problem, he said and I quote: Our algorithm works only when one can extend the size of the lists freely, i.e, in the special case where there are ...
53 views

### Merkle-Damgård construction

Let $H^f$ be a hash function designed using Merkle-Damgård construction on $f:\{0,1\}^{2n}\to\{0,1\}^n$. Write an algorithm that makes approximately $2.2^{n/2}$ many queries to $f$ and find four ...
237 views

### Yuval's birthday attack

I found this paper: https://www.researchgate.net/profile/Ganesh-Gupta-7/publication/271704029_What_is_Birthday_attack/links/54cfbdcc0cf24601c0958a1e/What-is-Birthday-attack.pdf The following attack is ...
157 views

### Calculating minimum number of messages hashed a 50% probability of a collision (Birthday Paradox)

I encountered this while solving a crypto puzzle. This is the puzzle. ...
48 views

### Security Proof, Sequence of games and birthday paradox

The sequence of games security proof approach is very confusing. For example, I am trying to understand it in the following paper https://www.dropbox.com/s/dhsgsognxviwacv/Provably%20Secure%...
152 views

### Cryptographic limit to total accounts in secp256k1

Factoring in birth day attacks and all that, with 256-bit elliptic curve cryptography, lets take secp256k1 as example that Bitcoin uses, what is the maximum number of accounts that are secure? It isn'...
99 views

### Understanding birthday attacks on 256 bit hashing and 512 bit hashing [duplicate]

Does it make a difference against birthday attacks if the algorithm that I am using is 512 bit hashing?
1k views

### Are My Answers to This Hash Question Correct?

Question When determining the security of a hash system, the cryptanalyst tries the following attacks. (a) If the attacker is NOT allowed to modify the original message, determine the number of hash ...
88 views

### Birthday-paradox for big numbers and more than one person: Computing the approximate probability of $k$ hash collisions for $n$ hashes

Given a cryptographic hashing function, with say a $256$ bit-length, I want to calculate the probability that out of $n$ hashes we have at least $k$ hashes that collide in the first $32$-bit (...
389 views

### SHA-256 security for initial 32 bits

I have concerns regarding truncated SHA-256 hashes in an application I am building at the moment: Nomenclature secret - the full 256-bit SHA-256 result of hashing ...
28 views

### Is finding a three way hash collision infeasible [duplicate]

Is there an equivalent to the birthday paradox for more than 2 messages. Solving Hash(x) = 0 takes $2^{bits}$ steps on average Solving ...
501 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 ...
144 views

### How many hashes for high probability of finding a collision (specific case)?

Suppose Bob managed to obtain 220 different digests that were generated by a hash function employed by a target system. The hash function outputs 8-byte digest of a message. Bob now wants to find a ...
250 views

### Birthday Attack Probability of Collision in Introduction to Modern Cryptography

I have some questions about the chapter of Birthday Attack in Introduction to Modern Cryptography. When $q=\Theta(2^{l/2})$ the probability of this collision is roughly $1/2$ What's the meaning of ...
182 views

### Hash multiset to point on elliptic curve where $A = 0$

I want to hash a multiset to a point on the elliptic curve $y^2 = x^3 + 3$ over a finite field of some 254-bit prime order, where $P = 3 \pmod 4$. Moreover, I want this hash to be incremental, in that ...
250 views

### How does concatenating diverse hash functions affect collision resistance?

Let's suppose I take 3 different types of hash functions and concatenate them for future safety so that: digest = Hash3( Hash2( Hash1( text ))) Does the birthday attack mean in this case that I must ...
146 views

137 views

### Are Feistel ciphers subject to the birthday bound?

This paper seems to be saying that a balanced Feistel cipher can be broken when an adversary has $2^{0.5 \cdot n}$ pairs of plaintext and cipher text blocks where $n$ is the block size in bits. Is ...
152 views

85 views

3k views

### Understanding calculation of collisions in hash-functions

I am going through some of my notes from class (About Information Security) and I'm stuck understanding how my teacher got this result. The question is: How many collisions would you expect to find ...
368 views

### birthday attack again [closed]

Suppose that we have a d-bit hashing function, and assume that the dimensionality of the input space is unbounded. The probability of finding a collision in 2d/2 steps is 1/2, and we call this a “...
197 views

### Strength of key derived from a hash function considering the birthday attack

When a hash function is used to derive a key from a shared secret (either by simply hashing the shared secret or using a more robust construct like HKDF) what's the strength of the derived material? ...
2k views

### What is the probability of any two users generating the same 128, 256, 2048 bit key?

There are some protocols that require the user to generate some random key locally (client-side) with no server authority to "approve" or "reject" their key and are based on the assumption that it's ...