Hot answers tagged

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

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$. ...


2

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 ...


2

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, ..., ...


2

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 ...


1

This depends on the MAC because there are different kinds of attacks to consider. If the best attack is randomly trying authentication tags, then the key does not matter. If the best attack is brute forcing the key, then key renewal does mean that the attacker has to "start anew", but as long as the key space is large enough that the probability of finding ...


1

The reason for this is because it is impossible to generate an MD5 for just any $y$, where $y$ is the output of any $x$ that isn't pre-computed. MD5 is broken but it is not completely broken. Using the common terms, MD5 is broken with regards to collision attacks, but not broken with regards to pre-image attacks. So your assumption that "Both methods ...


1

There exist polynomial time attacks against RSA signatures with constant padding. So, this actually does not exploit the missing check for the padding. It uses index calculus The latest paper that I am aware of in this series is http://www.dtc.umn.edu/~odlyzko/doc/index.calculation.rsa.pdf but you might also be interested in this paper: ...


1

To obtain the tag, OCB xors the plaintext blocks and encrypts them. Thus a sufficient condition for a forgery is finding another plaintext with the same xor as an existing plaintext. Consider a known plaintext attack where the attacker obtained (plaintext, ciphertext) pairs for two messages encrypted using the same key and nonce. The attacker picks between ...


1

Daniel Bleichenbacher has described such kind of attacks in his article Generating ElGamal signatures without knowing the secret key. (PDF) He noticed that if verifier would accept signatures where $r$ is larger than $p$ then any signature $(r,s)$ on $H(M)$ could be used to generate a signature $(r2, s2)$ on arbitrary hash value $H(M2)$. For that attacker ...


1

It's not a complete answer because an adversary needs control on the random choice of a signing algorithm. First let me define ElGamal signature to not get lost in notation. $x \in N$ is the secret key. $p$ is a prime, it defines $Z_p^*$. $g$ is a generator of $Z_p^*$. $y=g^x$ and the public key is $(p, g, g^x)$. Then $k$ is picked at random from ...



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