Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
52 votes
Accepted

How does hashing twice protect against birthday attacks?

A collision in any hash function gives a collision in a "squared" variant of the hash function. This is easy to see. If hash(x)==hash(y), then hashing the outputs ...
mikeazo's user avatar
  • 38.6k
19 votes
Accepted

Why does Birthday attack work only with random messages and not with chosen messages?

Birthday attacks do indeed work also for messages chosen by the attacker. For example, consider the case that I want to get a collision between a letter of recommendation and a letter that I was fired....
Yehuda Lindell's user avatar
14 votes
Accepted

Locker room birthday paradox

No, that is not correct. Assuming that the lock combinations are assigned randomly, and you have no apriori knowledge of the combination, you need 500 tries before you get a 50% chance of success. ...
poncho's user avatar
  • 148k
12 votes

How does hashing twice protect against birthday attacks?

Strictly speaking, hashing twice might actually increase the chances of a collision. If there is a hash collision of two outputs of the hash function then any string that has that colliding hash will ...
Kaithar's user avatar
  • 279
8 votes
Accepted

What is a wide block cipher and why does it avoid birthday bound problems?

I don't think the term "wide block cipher" has a hard definition beyond has a larger block size than the current standard algorithm(s) which right now in most cases would equal to has a block ...
SEJPM's user avatar
  • 46.1k
8 votes
Accepted

Is HMAC prone to birthday attacks?

Is the same true for HMAC ? Yes, HMAC outputs are hashes of something so after $2^{n/2}$ you expect two to match. However, this alone does not help the attacker. The attacker cannot compute the MAC ...
otus's user avatar
  • 32.1k
8 votes
Accepted

Why is a HMAC using a 32bit tag not prone to birthday attacks?

"Birthday attacks" relate to the mathematical phenomenon colloquially known as the birthday problem, which states that if you generate random value in a space of size $N$, you expect to hit your first ...
Thomas Pornin's user avatar
7 votes

Why does Birthday attack work only with random messages and not with chosen messages?

For example if there is a trade contract between two parties A and B ... why can A not generate a huge number of possible modified documents (for instance modifying space, dots, commas, etc. of D) and ...
poncho's user avatar
  • 148k
7 votes
Accepted

Do storage encryption systems care about size of data?

It's common for encryption algorithm specs to specify a hard limit of how much data you should encrypt with the same key. For example, consider the AES-XTS encryption algorithm, which was designed ...
Luis Casillas's user avatar
7 votes
Accepted

Are My Answers to This Hash Question Correct?

What needs to be memorized in applied science (physics, crypto) is not a set of formulas. It's, for a few of the simplest formulas studied: what the formula yields, for what inputs, the units for ...
fgrieu's user avatar
  • 142k
7 votes
Accepted

Beyond birthday bound security in AES-GCM-SIV

AES-GCM-SIV is misuse resistant authenticated encryption (MRAE), but like all MRAE schemes it still leaks information (equality of plaintexts) in a nonce reuse situation and is not IND-CPA-secure in ...
Taylor R Campbell's user avatar
6 votes
Accepted

Security of Keccak/SHA3 against birthday attacks

Let us correct some of your numbers. The size of the capacity is twice the size of the expected security margin (against a birthday attack). This is the idea of flat sponge clain etc When using a ...
Biv's user avatar
  • 9,988
6 votes
Accepted

Elliptic curve and "vanity" public keys

Maxwell's vanity public key is a result of how the generator of the secp256k1 was chosen; as explained by Maxwell himself. For some reason, the generator $G$ is the double of the point: ...
Conrado's user avatar
  • 6,464
5 votes
Accepted

Proof of $\sqrt{\pi/2}$ in birthday paradox?

The paper you are looking for is: "Random Mapping Statistics" by Flajolet and Odlyzko, first published in Advances in Cryptology — EUROCRYPT ’89. EUROCRYPT 1989. Lecture Notes in Computer Science, ...
SEJPM's user avatar
  • 46.1k
5 votes
Accepted

Birthday attack for combination of hashes

We first need to refine the definition of the problem. The most natural assumption in a cryptographic context is that "How many hash values do you have to calculate" implies that we consider a ...
fgrieu's user avatar
  • 142k
5 votes

Are MACs vulnerable to birthday attacks?

Are Message Authentication Codes (MAC) are vulnerable to birthday attacks... Like most things in life, it depends. Certainly, if you have an $n$-bit MAC, then after about $O(2^{n/2})$ MAC'ed ...
poncho's user avatar
  • 148k
5 votes

Birthday Attack with probability of 1

To get a collision with probability 1, you need to hash $H+1$ distinct values. You can see that because it is possible that if you hash only $H$ values, each one might happen to hash to a unique hash ...
poncho's user avatar
  • 148k
5 votes

What does this paraphrase of the birthday problem mean?

$x_1 \oplus x_2 = 0$ is equivalent to $x_1=x_2$ (because $\oplus$ is bitwise XOR, and that equivalence stands for bits, and multibit quantities being equal in all their respective bits is equivalent ...
fgrieu's user avatar
  • 142k
5 votes
Accepted

MuSig: could the rogue key attack be mitigated by using commitments instead of key transformations?

Yes, the rogue key attack can be prevented by committing to a public key before exchanging the keys. But this requires that you never use a public key with more than one group of signers. If you use ...
nickler's user avatar
  • 271
5 votes
Accepted

Why is the output size exactly half the capacity for sha-3?

Why is the output size exactly half the capacity for SHA-3? Because collision attacks are not the only ones of interest; we also expect that, for preimage (and second preimage) attacks, the best ...
poncho's user avatar
  • 148k
5 votes

How does birthday attack on message authentication work?

In this context, a transaction $t_i$ contains many messages $m_i^t$ where each message is MAC'ed with the transaction key $k_i$. Now assume that the MAC key of each transaction is generated uniformly ...
kelalaka's user avatar
  • 48.7k
4 votes

Is there any function that does not suffers birthday problem?

If $f:\{0,1\}^m\rightarrow \{0,1\}^n$ with $n\geq m,$ then of course there are, the set of one-to-one functions, but such a function is not a cryptographic hash function, since it lacks the ...
kodlu's user avatar
  • 22.6k
4 votes
Accepted

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....
poncho's user avatar
  • 148k
4 votes

Why k-lists generalized birthday problem when $k=2$ is classical birthday problem?

They are essentially the same, certainly in terms of complexity. Any collision $x=y$ with $x\in L_x$ and $y\in L_y$ is a collision in a single list $L_x \cup L_y$ of size at most twice the size of the ...
kodlu's user avatar
  • 22.6k
4 votes
Accepted

How many time does a SHA-1 computation require on modern CPU/GPU?

SHA-1 runs at 2.24 cpb on an AMD Ryzen 1700 (at 2994MHz) for somewhat short messages (ie 576 bytes) which is a very relevant number given that you don't want to hash large messages, but many messages. ...
SEJPM's user avatar
  • 46.1k
4 votes

What is the error in this collision probability approximation?

Clearly, for $x\in (0,1)$ which is our case, $$ e^{-x}-(1-x)< x^2/2, $$ and thus the relative multiplicative error between the estimate and actual answer satisfies $$ \frac{\widehat{P}_{\neg C}(Q)}{...
kodlu's user avatar
  • 22.6k
4 votes

What is the error in this collision probability approximation?

kodlu provided an approximation to the error term, but you might also be interested in firm bounds on the collision probability, which you can get without diving into the higher-order terms of the ...
Squeamish Ossifrage's user avatar
4 votes

Birthday Attack Probability of Collision in Introduction to Modern Cryptography

We say $f(n)=\theta(g(n))$ if $$ cg(n)\leq f(n)\leq Cf(n),\quad 0<c\leq C<\infty $$ as $n\rightarrow \infty.$ Apply the $\ell-$bit hash function to $k$ randomly chosen inputs. Let $n=2^{\ell}....
kodlu's user avatar
  • 22.6k
4 votes
Accepted

Derivation of birthday paradox probability

The probability becomes more intuitive when one pictures the $t$ persons entering one by one in the room. Before the first person enters, there's no collision/coincidence of birth-date, thus ...
fgrieu's user avatar
  • 142k
4 votes

Are My Answers to This Hash Question Correct?

You're wrong. Hint: a value of 8 bits has 256 possible values, not 8.
poncho's user avatar
  • 148k

Only top scored, non community-wiki answers of a minimum length are eligible