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

1
vote
1answer
72 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
825 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, \...
3
votes
2answers
184 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
122 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
356 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
687 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
84 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
330 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
146 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
255 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
507 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
653 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
95 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
115 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
99 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
73 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
115 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
748 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
330 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 ...
0
votes
1answer
605 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
311 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
569 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 ...
1
vote
1answer
157 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
539 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
438 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
1k 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
283 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 “...
1
vote
1answer
113 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
573 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
191 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
697 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
331 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 ...
37
votes
2answers
10k 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
263 views

Time complexity of birthday attack type problem

I have two sorted list $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$. Why the time complexity of ...
4
votes
1answer
432 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
306 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
779 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
144 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
377 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
91 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
490 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 ...
2
votes
2answers
504 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 ...
1
vote
1answer
253 views

How is the block size of a block cipher related to how susceptible the block cipher is to a birthday attack?

For example what can you say about how susceptible Triple-DES is to a birthday attack due to the fact that it has a block size of 64-bits.
4
votes
1answer
213 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.
2
votes
1answer
159 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....
7
votes
1answer
2k 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 ...
0
votes
2answers
300 views

k(k-1)/2: Combinations and the Birthday bound

Disclaimer: I'm new to cryptography. Background: I'm reading Cryptography Engineering by Ferguson, Schneier, and Kohno, where, in Chapter 2, the authors write this: Question: What is $k(k-1)/2$ ...