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

92 questions
Filter by
Sorted by
Tagged with
1 vote
105 views

### How secure is half-key Even-Mansour?

Single-key Even-Mansour is secure up to $2^{0.5 \times n}$. Where $n$ is permutation and key size. Would using $n/2$-key retain same security as $n$-key? Could the other half be used as a tweak?
1 vote
128 views

### Probability of getting a collision using chosen plaintext attacks

For university I am doing a piece of coursework right now. This question is focusing on CPA and collisions using CPA. Question: I have attempted to answer part 3, but am not very confident in the ...
1 vote
838 views

### Beyond birthday bound security in AES-GCM-SIV

AES-GCM-SIV takes a 96 bit nonce, like the original GCM. The RFC states that "it is RECOMMENDED to use this scheme with randomly chosen nonces". It uses the random nonce to generate per-...
77 views

### Double hashing scheme on not collision resistant hash

Given an hash H that is not collision resistant, for example 80-bit digest, if we use the following double hashing scheme: H(SHA2-256(x)). Does this scheme increase the collision resistance?
927 views

### How does birthday attack on message authentication work?

In Cryptography Engineering: 2.7.1 Birthday Attacks Birthday attacks are named after the birthday paradox. If you have 23 people in a room, the chance that two of them will have the same birthday ...
1 vote
336 views

### Are these both the probability of collision in birthday attack?

About birthday attack, book Cryptography Engineering says: In general, if an element can take on N different values, then you can expect the first collision after choosing about $\sqrt{N}$ random ...
1 vote
359 views

### Why is the output size exactly half the capacity for sha-3?

For the SHA-3 family of hash functions, the output size $d$ is always chosen as $d=c/2$, i.e. exactly half the capcity. What is the rational for this? Naively, I think that $d=c$ would make more sense ...
294 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 ...
94 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 ...
186 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 ...
575 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 ...
1 vote
2k 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. ...
443 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'...
329 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?
2k 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 ...
1 vote
167 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 (...
1k 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 ...
35 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 ...
1 vote
1k 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 ...
282 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 ...
421 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 ...
221 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 ...
531 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 ...
1 vote
188 views

1 vote
171 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 ...