We just launched a new product: Collectives on Stack Overflow. How do they work? Listen to learn more.

Hot answers tagged

32

In addition to the performance problems poncho already mentioned when using RSA signatures without hashing I just want to add on the security warning of poncho: Reordering If you have a message $m>N$ with $N$ being the RSA modulus, then you have to perform at least 2 RSA signatures as $m$ does not longer fit into $Z_N$. Let us assume that it requires $k$ ...


25

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 changes to the plaintext. Authenticated encryption solves this problem. I wanted to know how will one know that the decrypted text is not correct? My point is ...


24

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 encrypted. Such MACs can be built e.g. from block ciphers or from hash functions. Such codes are computed using a key shared by the sender and the recipient (which ...


21

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 operation for a chosen ciphertext's decryption (allowing the attacker to determine the plaintext) and the pad can be used as the tag in this attack. It's quite ...


15

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 enables an attacker to flip a bit and have the new signature accepted. In some "real" settings this arises as well. For example, with ECDSA, a signature $(r,s)$ can ...


14

Well, one reason to hash the data before signing it is because RSA can handle only so much data; we might want to sign messages longer than that. For example, suppose we are using a 2k RSA key; that means that the RSA operation can handle messages up to 2047 bits; or 255 bytes. We often want to sign messages longer than 255 bytes. By hashing the message ...


12

If Bob does NOT care to check signatures (as in the question), Eve can send ANY message she wants to Bob pretending to be Alice, including but not limited to messages Eve got from Alice; all Eve needs is Bob's public key (which, as the name implies, is assumed public knowledge thus known to Eve) and straight use of PGP. Therefore the right question is: Can ...


8

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 manuscript you cited and the conference paper at FSE 2012—contains misleading claims and misattribution of ideas; describes attacks that apply only beyond the ...


7

No, the signer is per definition in possession of the secret signing key and thus can always produce signatures for any message of his choice. Consequently, a notion of unforgeability is not meaningful with respect to the signer. For a signature scheme one requires unforgeability for parties who are not in possession of the secret signing key but only the ...


7

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\right\}^n.$$ That is, it takes as input an $n$-bit value and an $\ell$-bit value, and outputs an $n$-bit value. This function is a building block for the function $...


6

If we note $|m|$ the number of bits in the bytestring coding the message $m$, the first padding considered is $m\mapsto \tilde m=257\cdot2^{|m|}+m$, and the signature is $m\mapsto\tilde S(m)=S(\tilde m)=\tilde m^d\bmod N$, where $S$ is the textbook/naked RSA signing $m\mapsto m^d\bmod N$. Notice that for any $m$ small enough that $m^2$ can be signed, we can ...


6

If you were using $e=3$, then there is a well known attack by Bleichenbacher that enables the trivial generation of a signature that passes verification. This attack was never published, but is described here. Note that this attack appeared in a real vulnerability in Kindle (and some versions of Android). In any case, the attack does not work for $e=65536$. ...


6

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 would-be attacker to make a tremendous amount of profit. The fact that this appears to have never happened is good empirical evidence for its security. I've also ...


5

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,$$ where $h = H(m)$ depends solely on the message $m$ being signed. Here $x$ denotes the secret signing key and $q$ the order of the generator $g$ of a prime ...


5

The attack is even more simple with RSA than with symmetric keys, because the asymmetric encryption key is assumed to be public. Let me tell you a story involving Alice, Bob and Mallory :). Alice wants to send a message to Bob using RSA. Alice encrypts the message using Bob's public key and sends it Mallory performs a Man-In-The-Middle attack, and ...


5

As correctly pointed out in a comment, the authenticated encryption model assumes that the attacker knows the algorithm; the attacker can query the encryption oracle with any plaintext $P$ (and a unique nonce $N$) and get MAC-then-Encrypt ciphertext $C$; the attacker can query the decryption oracle with any string $C$ pretending to be a ciphertext. No ...


5

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 a way to produce MAC tags anyways.


5

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 compute: it's $2^{159}$. You can calculate this cube root the same way that you do RSA, essentially. Treat $2^{160}$ as if it were an RSA modulus, with $e = 3$. ...


4

Given a set of (unhashed) Lamport signatures using the same key, an attacker can trivially forge a signature for any message whose $k$-th bit, for each $k$, is equal to the $k$-th bit of at least one of the signed messages. For example, let's say I know the Lamport signatures for the following 16-bit messages using the same key: $$ m_1 = 0001111101110001 \\...


4

It seems that you mix things up. ElGamal signatures are existentially forgeable in various different ways if it's not using the hash-then-sign paradigm, i.e., you sign the message directly instead of signing the message $m=H(M)$ with $H$ being a secure cryptographic hash function. Given the type of forgery in your question that works, you compute your $m$...


4

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 algorithm. The signature is valid for the derived message, but the problem is that the attacker cannot control the message. It could be anything. Hashing the ...


4

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 means that $0^n$ must be added to the list of invalid forgeries, and so in order to present a valid forgery for $S$, you must have $$(m,S(k,m)) \notin \{(0^n,S(k,...


4

There is a way to generate forgeries for (EC)DSA when the hash function is not one-way: Let $n$ be the order of the group, $P$ a generator, and $Q = aP$ for some secret $a$; Pick arbitrary $\alpha$ and $\beta$ $\in \{0, \dotsc, n\}$; $r = x \bmod n$, where $(x, y) = \alpha P + \beta Q$; $s = r \beta^{-1} \bmod n$; $h = s \alpha \bmod n$; Invert $H(h)$ to ...


4

If Eve can find an $n'$ that is prime (and $n'-1$ is relatively prime to $e$),then she can easily sign any message with that $n', e$ pair. So, the question is: what is the probability that there exists a prime $n'$ such that there is only one bit difference between $n$ and $n'$, and $n' \not\equiv 1 \pmod {e}$ ? The answer is that it is quite good if $e &...


4

One property that this unpadded system is that it is homomorphic; if $A^d = X$ and $B^d = Y$, then we know that $(AB)^d = XY$, and it doesn't matter if we don't know what $d$ is. More generally, if we have a collection of $H_1, H_2, H_3, ... H_n$, and a collection of signatures $S_1, S_2, S_3, ..., S_n$, then for any set of integers $e_1, e_2, e_3, ..., e_n$...


4

crypto_secretbox uses the first 32 bytes of XSalsa20 output as the key for Poly1305. Thus you are correct that using crypto_stream_xor on a known plaintext will reveal the authentication-key used by crypto_secretbox, allowing forgeries under that key and nonce. Not using a key for multiple purposes is a general crypto design principle. Perhaps that's why ...


4

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): \begin{equation*} r \stackrel?= f\bigl(x([H(m) s^{-1}]G + [r s^{-1}]Q)\bigr), \end{equation*} where $f\colon \mathbb Z/p\mathbb Z \to \mathbb Z/n\mathbb Z$ ...


4

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 dramatically reduces the amount of data that needs to be transmitted, while still allowing periodic seeking. It would be possible to embed a cryptographic ...


3

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=2048$, $e=41$, a hash function $H=\operatorname{SHA-1}$ with output of $w=160$ bits. It is asked an $(m,s)$ with $0\le s<N$ and $H(m)=(s^e\bmod N)\bmod2^w$. ...


3

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\}$ is a pair $(r,s)$ satisfying $g^m \equiv y^r \cdot r^s \pmod p$. With $r = g^e \cdot y^v \bmod p$ and $s = -r\cdot v^{-1} \bmod (p-1)$ for random integers $...


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