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

Filter by
Sorted by
Tagged with
1 vote
0 answers
73 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 ...
  • 77
1 vote
1 answer
299 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-...
0 votes
1 answer
59 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?
  • 1
2 votes
2 answers
775 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 ...
  • 151
1 vote
1 answer
242 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 ...
  • 151
1 vote
2 answers
249 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 ...
  • 113
7 votes
1 answer
149 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 ...
2 votes
1 answer
83 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 ...
  • 357
0 votes
0 answers
154 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 ...
3 votes
1 answer
461 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 ...
  • 31
1 vote
2 answers
986 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. ...
  • 2,036
2 votes
1 answer
332 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'...
0 votes
0 answers
236 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?
4 votes
2 answers
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 ...
  • 43
1 vote
1 answer
145 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 (...
2 votes
1 answer
779 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 ...
0 votes
0 answers
29 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 ...
  • 3
0 votes
3 answers
970 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 ...
  • 195
0 votes
1 answer
231 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 ...
0 votes
2 answers
371 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 ...
6 votes
1 answer
202 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 ...
  • 171
0 votes
1 answer
480 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 ...
  • 33
1 vote
1 answer
176 views

Birthday attack on hash functions derived from a collision-resistant hash function [closed]

$H_1$ is a collision-resistant hash function with an $L$-bit output. 2 hash functions are created based on it as follows: $$H_2((k_1,k_2);m) = (H_1(k_1;m), \space H_1(k_2;m))$$ $$H_3((k_1,k_2);(m_1,...
6 votes
2 answers
890 views

What does this paraphrase of the birthday problem mean?

The following is an excerpt from A Generalized Birthday Problem - David Wagner: One of the best-known combinatorial tools in cryptology is the birthday problem: Problem 1. Given two lists $L_1, \...
  • 161
4 votes
2 answers
304 views

What is the error in this collision probability approximation?

Theorem: Choose $Q$ random natural numbers in the set $\{1,2, \dots, M\}.$ The probability of getting at least one collision is $$P_C(Q) = 1 - \frac{M - (Q - 1)}{M} P_{\neg C}(Q-1).$$ Notation: By ...
  • 409
1 vote
2 answers
421 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,221
0 votes
1 answer
695 views

Birthday Attack against Cryptocurrency

One of my friends is creating his own cryptocurrency, just as a fun project, and he made some design choices that I think are insecure, but I personally don't have enough expertise to evaluate. ...
6 votes
2 answers
2k views

Elliptic curve and "vanity" public keys

I want to find an algorithm to get a private/public key pair where one coordinate of the public key has some specific prefix (for example: 20 leading zeroes). In the secp256k1 case (the Bitcoin curve),...
3 votes
1 answer
143 views

Block cipher birthday bound and a KDF workaround

Can the birthday bound arising from a block cipher’s block size be worked around by deriving different keys from the master key with a KBKDF using a tweak? For example consider the following scheme, ...
  • 326
3 votes
1 answer
524 views

Why is counter mode encryption with a 16-byte cipher block not broken?

We determine a system IND-CPA secure when an adversary has a negligible advantage after any feasible amount of queries. AES256-GCM uses a 128bit block cipher. We know that the distinguishability ...
0 votes
3 answers
224 views

Do storage encryption systems care about size of data?

I was studying about Psuedorandom functions and their use as encryption functions. One of the things that I read was "birthday bound" or "birthday attack". When encryption is used for something ...
  • 407
0 votes
1 answer
2k 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
1 answer
845 views

Which answer is true regarding birthday attack on digital signatures?

The actual question is: A sender $S$ sends a message $m$ to receiver $R$, which is digitally signed by $S$ with its private key. In this scenario, one or more of the following security violations can ...
9 votes
3 answers
4k views

Why does Birthday attack work only with random messages and not with chosen messages?

Considering unkeyed hashing functions, I studied that the birthday attack can only work generating random messages and not with messages chosen from the attacker, but I didn't understand why. For ...
2 votes
1 answer
1k 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 : ...
  • 123
1 vote
0 answers
107 views

Maximum number of blocks that can be safely encrypted using a block cipher with a counter

Assume that we have a block cipher with a key size of $\ell_{K}$ bits, a tweak size of $\ell_{T}$ bits, and a block size of $\ell_{X}$ bits. Formally, the encryption of a given block of data is $$E(K, ...
  • 3,467
1 vote
2 answers
151 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 ...
  • 3,467
2 votes
1 answer
164 views

Is it possible for this tweakable block cipher scheme to be secure for more than $2^\frac{n}{2}$ blocks? $2^{n}$ blocks?

In the title, $n$ is the block size in bits and will not be used to denote it in the body of this question unless otherwise stated. Imagine that we have $\mathbb{K} \in \{0, 1\}^{\ell_{K}}$, $\mathbb{...
  • 3,467
1 vote
0 answers
57 views

Upper bound of this derivative of counter mode?

Suppose that: $\boldsymbol{K} \in \{0, 1\}^{\ell_{K}}$. $\boldsymbol{IV} \in \{0, 1\}^{\ell_{IV}}$. $\boldsymbol{I} \in \{0, 1\}^{\ell_{I}}$. $\boldsymbol{X} \in \{0, 1\}^{\ell_{X}}$. $E(K, X): \...
  • 3,467
1 vote
0 answers
97 views

Using an Even-Mansour block cipher in a tweakable mode of operation

Assume that: $P(X): \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$. $Q(X): \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$. $E(K, X): \{0, 1\}^{\ell_{K}} \times \{0, 1\}^{\ell_{X}} \...
  • 3,467
3 votes
0 answers
213 views

Does XEX mode specify how the whitening value is generated?

When the term "XEX" or the phrase "XOR-encrypt-XOR" is used, does it refer only to the scheme $CT = E_{K}(PT \oplus T) \oplus T$/$PT = E_{K}(CT \oplus T) \oplus T$ (where $T$ is the whitening/tweak ...
  • 3,467
-1 votes
1 answer
3k views

Birthday attack against SHA256 [duplicate]

Lets say I have a database that contains X SHA256 hashes . How do I calculate the likelihood of a me creating a hash out of random values that collides with any hash in the stored database?
  • 101
0 votes
1 answer
1k views

How many time does a SHA-1 computation require on modern CPU/GPU? [closed]

I am considering how long a SHA-1 computation will need on modern CPU/GPU's. Just in case we are interested in brute forcing and consider the birthday paradoxon, then we need consider the SHA-1 output ...
  • 407
1 vote
1 answer
2k views

Are MACs vulnerable to birthday attacks?

Às the title already indicates, I would like to know: Are MACs vulnerable to birthday attacks?
5 votes
1 answer
529 views

Should AES-CMAC key cryptoperiod be affected by MAC truncation to avoid birthday-attacks?

Given a 128-bit key used for authentication based on AES-CMAC, the NIST 800-38B recommendations suggest at least two criteria for a good key cryptoperiod: after 'MaxInvalids' error messages the key ...
  • 254
3 votes
1 answer
766 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 ...
2 votes
2 answers
236 views

Can the birthday attack be extended in this case?

Let $H:\{0,1\}^*\to\{0,1\}^n$ be a cryptographic hash function as a black-box, and suppose we have unlimited space. As I understand, finding $x$ such that $H(x)=0$ (if such exists) would require a ...
  • 145
6 votes
1 answer
1k views

What is a wide block cipher and why does it avoid birthday bound problems?

I've recently heard the claim that wide block ciphers avoid birthday bound problems. Trying to figure out what exactly "wide block encryption" is, a quick search turned up this paper which is trying ...
  • 4,853
5 votes
1 answer
747 views

Proof of $\sqrt{\pi/2}$ in birthday paradox?

I had found in the past a publication in a crypto conference (in 80s if i am not mistaken) which I believe was the first proof why for example a random function $f:X\rightarrow X$ with $\#X=2^n,$ is ...
4 votes
1 answer
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 ...
  • 141