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).
93
questions
40
votes
2
answers
13k
views
How does hashing twice protect against birthday attacks?
The bitcoin wiki says:
Bitcoin is using two hash iterations (denoted SHA256^2 ie "SHA256 function squared") and the reason for this relates to a partial attack on the smaller but related SHA1 hash. ...
- 503
19
votes
1
answer
21k
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 $2^{...
- 1,798
18
votes
1
answer
6k
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 ...
- 485
15
votes
1
answer
2k
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?
- 451
10
votes
2
answers
1k
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.
- 201
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 ...
9
votes
3
answers
1k
views
Birthday Attack
I am reading about 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(...
- 2,701
9
votes
1
answer
10k
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 ...
- 38.6k
8
votes
1
answer
9k
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 ...
8
votes
1
answer
356
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 ...
- 183
7
votes
1
answer
3k
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 other ...
- 101
6
votes
2
answers
3k
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),...
- 89
6
votes
2
answers
917
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
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,913
6
votes
1
answer
228
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
5
votes
1
answer
985
views
Why is a HMAC using a 32bit tag not prone to birthday attacks?
Why is a HMAC using a 32bit tag not prone to birthday attacks?
I have read that it has something to do with the fact a birthday attack isn't really possible if the output size is not large enough. ...
- 69
5
votes
1
answer
343
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.
- 4,793
5
votes
1
answer
911
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 ...
- 165
5
votes
2
answers
607
views
implementing GCM with dev/urandom for a nonce
I'm currently trying to integrate GCM into my code, and I have just enough knowledge to know I'm probably doing this wrong. I know for GCM and other CTR like ciphers, using the same key with the same ...
- 53
5
votes
1
answer
591
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
4
votes
1
answer
740
views
Locker room birthday paradox
The local YMCA has new locker rooms with built-in 3-digit combination locks. If I understand the Birthday Paradox correctly, I have a better than 50% chance of finding a lock combination with 33 tries ...
- 273
4
votes
2
answers
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 ...
- 43
4
votes
2
answers
333
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
4
votes
1
answer
376
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 ...
- 540
4
votes
1
answer
230
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.
- 337
4
votes
1
answer
4k
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
4
votes
1
answer
283
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?
...
- 41
3
votes
1
answer
3k
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 ...
- 517
3
votes
1
answer
1k
views
Is HMAC prone to birthday attacks?
Popular attacks on cryptographic hash algorithms are "birthday attacks" .
At high level ,
if a hash function produces $n$ bits of output, an attacker who computes only $2^{n/2}$ hash operations on ...
- 6,184
3
votes
1
answer
2k
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 ...
- 736
3
votes
1
answer
3k
views
Security of Keccak/SHA3 against birthday attacks
If I understand it correctly the security of $\operatorname{Keccak}$ depends on the capacity $c$, which means that I get a security level of $2^{128}$ for $c=128$ (I omitted the value $r$ here because ...
- 105
3
votes
2
answers
732
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 ...
- 635
3
votes
1
answer
820
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 ...
- 143
3
votes
1
answer
240
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 ...
- 273
3
votes
1
answer
601
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
3
votes
1
answer
548
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 ...
- 51
3
votes
1
answer
887
views
Birthday attack on AES-CCM with 32-bit Authentication Tag
I would like to use AES-CCM with a very small Authentication Tag length of 32 bits. Thus, I have a question about the vulnerability to birthday attacks.
How vulnerable is CCM to birthday attacks?
...
- 425
3
votes
1
answer
162
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
148
views
High volume encryption with AES-GCM: AWS KMS vs CloudHSM
In my current project we will have to encrypt a lot of S3 objects (a few billions) with AWS KMS.
Our security department requires that we use KMS keys backed by CloudHSM. But since CloudHSM incurs ...
- 31
3
votes
0
answers
222
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,655
2
votes
2
answers
984
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
2
votes
2
answers
403
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 ...
- 123
2
votes
1
answer
275
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....
- 23
2
votes
1
answer
96
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 ...
- 377
2
votes
1
answer
868
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 ...
- 21
2
votes
2
answers
253
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
2
votes
1
answer
301
views
64 bits cipher and birthday boundaries in ECB
I am using a 64 bits symmetric ciphers (blowfish), to encrypt a plain block using ECB.
The plaintext is always 64 bits long, but due to some limitations I have to use the same key (448 bits long) ...
- 21
2
votes
1
answer
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 ...
2
votes
1
answer
152
views
Security of hash functions over input extended with a random value
Hashing a single message say $H(M)$ is vulnerable to a birthday attack.
But what if a combination is hashed, such has $H(M,R)$? Is it still vulnerable to the attack?
I think it is because $M, R$ can ...
- 31
2
votes
1
answer
496
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'...
