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
2
votes
0answers
31 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
1answer
69 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 ...
0
votes
0answers
53 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
1answer
237 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 ...
0
votes
1answer
157 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. ...
0
votes
0answers
48 views

Security Proof, Sequence of games and birthday paradox

The sequence of games security proof approach is very confusing. For example, I am trying to understand it in the following paper https://www.dropbox.com/s/dhsgsognxviwacv/Provably%20Secure%...
2
votes
1answer
152 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
0answers
99 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
2answers
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 ...
1
vote
1answer
88 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
1answer
389 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
0answers
28 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
501 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
144 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
250 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
1answer
182 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
250 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
146 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
2answers
882 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
256 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
314 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
votes
1answer
546 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
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
1answer
129 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
488 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
204 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
964 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
756 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 ...
8
votes
3answers
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
1answer
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 : ...
1
vote
0answers
105 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
137 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
152 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
52 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
85 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
199 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
2k 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
697 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
1k 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
481 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
691 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
2answers
229 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
836 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 ...
5
votes
1answer
614 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
1answer
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 ...
-2
votes
1answer
368 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 “...
4
votes
1answer
197 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? ...
-1
votes
2answers
2k 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
253 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
721 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 ...