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
1
vote
1
answer
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,649
1
vote
0
answers
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 ...
- 77
1
vote
1
answer
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-...
- 547
0
votes
1
answer
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?
- 1
2
votes
2
answers
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 ...
- 151
1
vote
1
answer
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
...
- 151
1
vote
2
answers
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 ...
- 113
8
votes
1
answer
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 ...
- 183
2
votes
1
answer
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 ...
- 377
0
votes
0
answers
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 ...
3
votes
1
answer
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 ...
- 31
1
vote
2
answers
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.
...
- 2,179
2
votes
1
answer
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'...
0
votes
0
answers
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?
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
1
vote
1
answer
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 (...
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 ...
0
votes
0
answers
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 ...
- 3
1
vote
3
answers
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 ...
- 205
0
votes
1
answer
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 ...
0
votes
2
answers
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 ...
- 1
6
votes
1
answer
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 ...
- 171
0
votes
1
answer
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 ...
- 33
1
vote
1
answer
188
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
911
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
324
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
540
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,243
0
votes
1
answer
747
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.
...
- 415
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
3
votes
1
answer
157
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
542
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
1
vote
3
answers
238
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 ...
- 417
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 ...
- 3
2
votes
1
answer
860
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
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 ...
1
vote
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 :
...
- 113
1
vote
0
answers
110
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,645
1
vote
2
answers
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 ...
- 3,645
2
votes
1
answer
170
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,645
1
vote
0
answers
58
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,645
2
votes
0
answers
107
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,645
3
votes
0
answers
217
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,645
-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
571
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
815
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
2
votes
2
answers
251
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,883
5
votes
1
answer
860
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