Skip to main content

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
0 answers
64 views

Is sha256 quantum secure? [duplicate]

I've been reading about the security implications of quantum computing on cryptographic algorithms and came across some discussions regarding SHA-256. I understand that SHA-256 is currently considered ...
Nerses Asaturyan's user avatar
3 votes
1 answer
175 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 ...
Florian's user avatar
  • 31
1 vote
1 answer
134 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?
LightBit's user avatar
  • 1,659
1 vote
0 answers
150 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 ...
hasin's user avatar
  • 77
2 votes
1 answer
1k 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-...
Neil Madden's user avatar
0 votes
1 answer
81 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?
N-K's user avatar
  • 1
2 votes
2 answers
1k 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 ...
Tim's user avatar
  • 151
1 vote
1 answer
387 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 ...
Tim's user avatar
  • 151
2 votes
2 answers
418 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 ...
Simon's user avatar
  • 123
8 votes
1 answer
412 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 ...
Jonathan Voss's user avatar
2 votes
1 answer
97 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 ...
Laura's user avatar
  • 377
0 votes
0 answers
206 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 ...
ram kumar's user avatar
3 votes
1 answer
616 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 ...
guest's user avatar
  • 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. ...
user93353's user avatar
  • 2,160
2 votes
1 answer
527 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'...
Secretary Peetwoo's user avatar
0 votes
0 answers
446 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?
Marko Peterson's user avatar
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 ...
John's user avatar
  • 43
1 vote
1 answer
177 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 (...
securitymensch's user avatar
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 ...
Maximilian Kraus's user avatar
0 votes
0 answers
36 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 ...
quohay's user avatar
  • 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 ...
sanjihan's user avatar
  • 205
0 votes
1 answer
289 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 ...
wongsimon's user avatar
0 votes
2 answers
437 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 ...
Simon Hu's user avatar
6 votes
1 answer
230 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 ...
Alan's user avatar
  • 171
0 votes
1 answer
536 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 ...
yacrc's user avatar
  • 33
1 vote
1 answer
195 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,...
thecryptoalice's user avatar
6 votes
2 answers
920 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, \...
SedriX's user avatar
  • 161
4 votes
2 answers
340 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 ...
user45491's user avatar
  • 409
1 vote
2 answers
634 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 ...
user1868607's user avatar
  • 1,243
0 votes
1 answer
778 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. ...
Lev Knoblock's user avatar
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),...
arulbero's user avatar
3 votes
1 answer
167 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, ...
orip's user avatar
  • 326
3 votes
1 answer
551 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 ...
Sap Chicken's user avatar
1 vote
3 answers
246 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 ...
Limit's user avatar
  • 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 ...
Serena89's user avatar
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 ...
poda_badu's user avatar
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 ...
alex_the_great's user avatar
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 : ...
ge45mue's user avatar
  • 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, ...
Melab's user avatar
  • 3,675
1 vote
2 answers
182 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 ...
Melab's user avatar
  • 3,675
2 votes
1 answer
174 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{...
Melab's user avatar
  • 3,675
1 vote
0 answers
59 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): \...
Melab's user avatar
  • 3,675
2 votes
0 answers
110 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}} \...
Melab's user avatar
  • 3,675
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 ...
Melab's user avatar
  • 3,675
0 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?
no nein's user avatar
  • 111
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 ...
Shalec's user avatar
  • 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?
Bruno Lourenço's user avatar
5 votes
1 answer
597 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 ...
gentooise's user avatar
  • 254
3 votes
1 answer
823 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 ...
Thomas Vanhelden's user avatar
2 votes
2 answers
255 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 ...
user45323's user avatar
  • 145