# Tag Info

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

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

3

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

2

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'$ such as $S'(m,k) = S(m',k')$. Here you computed: $S'(k,m) = (S(k,m),s) = (\sigma,s)$ and $S'(k,0^n) = (s,s)$ but you do not have a collision between $(\sigma,... 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 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: https://www.iacr....

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