Skip to main content
25 votes

How difficult is it to practically detect a forgery in a cryptosystem?

There are several standard methods for cryptographically detecting forged messages: A cryptographic message authentication code (MAC) can be applied to the message, preferably after it has been ...
Ilmari Karonen's user avatar
25 votes
Accepted

How difficult is it to practically detect a forgery in a cryptosystem?

Confidentiality does not imply authenticity. Many common ciphers are trivially malleable—an attacker that doesn't know the key can nevertheless modify ciphertexts in ways that cause predictable ...
Luis Casillas's user avatar
21 votes
Accepted

What is the new attack on OCB2 and how does it work?

How does the attack work (on a high level)? It's an unfortunate consequence of how the pad of the last encryption block is computed. The pad can essentially be used to both eliminate the block cipher ...
puzzlepalace's user avatar
  • 4,052
17 votes
Accepted

Existential unforgeability vs strong unforgeability

It is easy to construct a signature scheme that is existentially unforgeable but not strong. All you have to do is add a bit to the end of a strong scheme, and ignore it upon verification. This ...
Yehuda Lindell's user avatar
9 votes
Accepted

GMAC vs HMAC in message forgery and bandwidth

Saarinen in his work GCM, GHASH and Weak Keys says that; This paper is not very clear and has led many people into regrettable confusion about universal hashing authenticators. The paper—both the ...
Squeamish Ossifrage's user avatar
7 votes
Accepted

Forgery attack for Merkle–Damgård MAC scheme with prefix method

A lot of this is explained well on the wikipedia article. The function $f$ is called the compression function. It is a function $$f:\left\{0,1\right\}^n\times\left\{0,1\right\}^\ell\to\left\{0,1\...
CurveEnthusiast's user avatar
6 votes
Accepted

Why is ECDSA secure?

We don't. As far as I know there is no proof of security for ECDSA in any model. There is, however, almost 2 decades of usage in the wild, including by Bitcoin and Ethereum, which would allow any ...
Andrew Poelstra's user avatar
5 votes

Question on MAC Forgery

The key part of the entry is "...where σ was not produced by the legitimate signer.". The legitimate signer is the key holder. We assume the adversary does not possess the key, but would like to have ...
Ella Rose's user avatar
  • 19.7k
5 votes

How to forge signatures in the Schnorr scheme if $r=g^k$ is eliminated?

I suppose that you address the question to a signature scheme, in which the signature is still the pair $(r,s)$ with $r=g^k \bmod p$ as the exponentiated nonce and $$s = H(m)\cdot x + k \mod q,$$ ...
U. Haboeck's user avatar
5 votes
Accepted

Forging RSA1024 signature with e=3 where hash is right justified

When $\gcd(e, \phi(n)) = 1$, integers modulo $n$ coprime to $n$ have a unique $e$th root modulo $n$. This is the basis of RSA. Unlike for an unfactored RSA modulus, $\phi(2^{160})$ is easy to ...
Myria's user avatar
  • 2,595
4 votes

How can I resolve this basic MAC paradox I’m stumbling upon in my proof?

Your attack on $S$ involves computing $S'(k,m_i)$ for arbitrary messages $m_1,\dots,m_q$. In order to do that, you must compute $S(k,m_i)$ and $S(k,0^n)$, and thus you have obtained $S(k,0^n)$. This ...
fkraiem's user avatar
  • 8,152
4 votes

How does hash function in Elgamal signature scheme prevent existential forgery attack?

Existential forgery attacks allow the attacker to choose (or calculate) a signature, and then the message is derived from this signature (and the public key) using the existential forgery attack ...
Raymond Smith's user avatar
4 votes
Accepted

Does using crypto_stream_xor allow listeners to forge crypto_secretbox messages?

crypto_secretbox uses the first 32 bytes of XSalsa20 output as the key for Poly1305. Thus you are correct that using ...
CodesInChaos's user avatar
  • 24.9k
4 votes
Accepted

Is ECDSA signature strongly EUF-CMA?

From SEC1 v2.0 (§4.1, pp. 43–47), a public key is a point $Q \in E$, and a signature on a message $m$ is a pair of integers $(r, s)$ satisfying the signature equation (condensed from several steps): \...
Squeamish Ossifrage's user avatar
4 votes
Accepted

How to use cryptography to protect video from forgery?

Most video formats generate periodic key frames where the entire picture is rendered and then specify subsequent frames which are differences from the previous image. This is beneficial because this ...
bk2204's user avatar
  • 3,476
3 votes

GMAC vs HMAC in message forgery and bandwidth

What is the convenience of universal hashes provides? They are simple to describe: $X_i=(X_{i-1}+D_i)\cdot H$, with $D_i$ being the $i$-th data word and $H$ being a key/iv-dependent secret and are ...
SEJPM's user avatar
  • 46.1k
3 votes

Security of CBC-MAC fixed length with zero padding

Let's simplify this to one-block messages with a 128-bit block. Your scheme to authenticate a message whose length in bits $n$ is anywhere from 0 to 128 is $$\operatorname{MAC}_k(m) = \operatorname{...
Squeamish Ossifrage's user avatar
3 votes
Accepted

Knowing you can combine 2 signatures, Is it possible to remove part of the signature?

As soon as you are working using standard textbook RSA without padding (or hashing), you can fully exploit the malleability of the RSA cipher. So, let's say you have a message $m$ which is equal to $...
Lery's user avatar
  • 7,719
3 votes
Accepted

Is this Bleichenbacher '06 style signature forgery possible? (Or more like, why isn't it?)

Now, I'm wondering about the case where an implementation does check that the hash is right-justified, but doesn't check the previous bytes at all. That case is completely broken for $e=3$ ...
poncho's user avatar
  • 148k
3 votes
Accepted

El Gamal existential forgery using Pointcheval–Stern signature algorithm

The scheme you consider is the original ElGamal signature. This scheme is known to be existentially forgeable. By definition, a valid original ElGamal signature on a message $m \in \{1, \dots, p-1\...
user94293's user avatar
  • 1,779
3 votes

What is the probability of attacking SHA1 used in RSA signature with small exponent?

This is not an answer; rather, I attempt to improve the method outlined in the question. Problem statement (slightly simplified): it is given an RSA public key $(N,e)$ with $2^{n-1}<N<2^n$, $n=...
fgrieu's user avatar
  • 142k
3 votes

Is it possible to cryptographically sign a message with a private key while keeping the pre-image content public?

The security of the signature schemes doesn't require the message to be encrypted. The hash algorithm and the signature algorithm parameters are publicly known and the only secret the signer's key ...
kelalaka's user avatar
  • 49k
3 votes

Why can't RSA signatures be forged algebraically?

Solving $s'^e = h' \mod n$ for $s'$ means calculating the $e$th root of $h'$ in $\mathbb{Z}/n\mathbb{Z}$. There is no efficient generic method to do that. The holder of the private key solves this ...
Gilles 'SO- stop being evil''s user avatar
3 votes

How does padding in RSA prevent existenial forgery attacks in RSA?

If we consider "textbook" RSA signatures where messages a message $m$ is signed by $s=m^d\mod N$ where $d$ is the private signing key and verfied by computing $s^e\mod N$ and comparing it to ...
Daniel S's user avatar
  • 24.1k
2 votes

How can I resolve this basic MAC paradox I’m stumbling upon in my proof?

First remark: Throw at $S′$ some $m\neq0^n$, and extract the value $s=S(k,0^n)$ out of the tag. Then, the message $0^n$ and tag $(s,s)$ is our forgery. Building a forgery is exposing $m$ and $m'$ ...
Biv's user avatar
  • 10k
2 votes

Selective Forgery of a Digital Signature - Goldwasser et al

The reference is Shafi Goldwasser, Silvio Micali, Ronald L. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, in SIAM Journal on Computing, 1988. It defines ...
fgrieu's user avatar
  • 142k
2 votes
Accepted

How to forge a Shamir secret share?

Mike's answer is correct; however it turns out that, for $k>2$, the attacker can do better. Assuming that the attacker knows: The actual shared secret His correct share The $x$-coordinates of ...
poncho's user avatar
  • 148k
2 votes

How to forge a Shamir secret share?

For us to make it exciting, let's first define the meaning of two sample messages: $m : $ "yes, in case of m.a.d., do fire the missiles" $m' : $ "no, do not fire missiles" Let's guess that the ...
dusk's user avatar
  • 1,175
2 votes

Universal forgery based on mathematical problem

Elliptic Curve Digital Signature Algorithm admits universal forgery if the Attacker can solve the equation $$z=\frac{\psi_{k-1}(x,y)\psi_{k+1}(x,y)}{\psi_{k}(x,y)^2},$$ where $k$ is unknown, $\psi_{k}(...
Alexey Ustinov's user avatar
2 votes

In W-OTS, is it trivial to forge smaller N values?

W-OTS has a checksum that ensures that kind of attack doesn't work. In essence, the checksum is the sum of the value of every other component subtracted, so that if you hash one component one more ...
DannyNiu's user avatar
  • 9,451

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