We’re rewarding the question askers & reputations are being recalculated! Read more.

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
0
votes
0answers
20 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 ...
0
votes
3answers
97 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 ...
0
votes
1answer
75 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
2answers
91 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 ...
4
votes
1answer
130 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 ...
0
votes
1answer
46 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
1answer
107 views

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

$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
2answers
841 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, \...
4
votes
2answers
203 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 ...
1
vote
2answers
141 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 ...
0
votes
1answer
379 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
2answers
924 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
1answer
95 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, ...
3
votes
1answer
359 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
3answers
153 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 ...
0
votes
1answer
375 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
1answer
591 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 ...
7
votes
3answers
3k 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
1answer
747 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 : ...
1
vote
0answers
98 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, ...
1
vote
2answers
117 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 ...
2
votes
1answer
109 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{...
1
vote
0answers
45 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): \...
1
vote
0answers
74 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
votes
0answers
138 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 ...
-1
votes
1answer
859 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?
-1
votes
1answer
381 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 ...
1
vote
1answer
677 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
1answer
375 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 ...
3
votes
1answer
614 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
1answer
177 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 ...
6
votes
1answer
592 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
votes
1answer
463 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 ...
3
votes
1answer
2k 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 ...
-2
votes
1answer
315 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 “...
3
votes
1answer
133 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? ...
-2
votes
2answers
679 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 ...
2
votes
1answer
196 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) ...
4
votes
1answer
700 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 ...
5
votes
2answers
350 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 ...
38
votes
2answers
11k 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. ...
1
vote
0answers
300 views

Time complexity of birthday attack type problem

I have two sorted lists: $A=\{a_1, \ldots, a_n\}$ and $B=\{b_1, \ldots, b_m\}$. I know that the probability of $a_i=b_j$ is $c$ for $1 \leq i \leq n$ and $1\leq j \leq m$. The time complexity of ...
4
votes
1answer
468 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. ...
1
vote
2answers
317 views

Birthday Attack with probability of 1

According to Wikipedia, $n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$ Let n(p; H) be the smallest number of values we have to choose, such that the probability for finding a collision is at least p. ...
3
votes
1answer
995 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 ...
0
votes
1answer
1k views

Collision in SHA-1 first 8 bytes [closed]

I'm trying a Birthday Attack to randomly generated strings and its $\mathop{SHA-1}$ hashes using a Mapped table of values in order to find a collision on only the first 8 bytes. With the first 4 or 5 ...
2
votes
1answer
147 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 ...
2
votes
1answer
405 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? ...
1
vote
1answer
94 views

Mathematical calculation to determine probability of observing the character space used for a set of string inputs

I am designing some methodology to determine the composition of wireless router security passphrases in terms of the character space used to generate them. The problem I am having is I am unsure what ...
3
votes
1answer
545 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 ...