# Tag Info

18

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

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

7

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

7

For the first part of your question: Yes, if Mallory manages to publish is own public key under Alice's name, then there is really nothing to stop him. This problem is addressed with public key infrastuctures and public key certificates. That is, for Bob to believe that the public key is Alice's key, Mallory would need to have a trusted third party attest, ...

6

If the message is random each additional signature halves the security level. If the message is chosen by the attacker, two signatures (of messages where each bit differs) are enough for a complete break. A security level of about 64 bits can be broken by a determined attacker, and a level of 32 bits can be trivially broken on a single home computer. So if ...

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

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

4

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

4

If you don't want to store the anti-CSRF tokens on the server, for most purposes it is sufficient to simply store the token as an HTTP cookie on the client. The OWASP wiki calls this technique "Double Submit Cookies". The reason this works is that, in the standard CSRF attack scenarios, the attacker cannot directly read or modify the user's cookies. ...

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

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,... 3 Look at it this way; consider the value of: (2^{1019} - N * 2^{34} / 3)^3 Using the binomial expansion, we see that it equal to: (2^{1019})^3 - 3 * (2^{1019})^2 * N * 2^{34}/3 + 3 * 2^{1019} * (N * 2^{34} / 3)^2 - (N * 2^{34} / 3)^3 or (simplifying): 2^{3057} - N * 2^{2072} + G where G = N^2/3 * 2^{1087} - N^3/27 * 2^{102} < 2^{2072} for the ... 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 Considering the padding as an addition, padded message passed to sign is m\cdot 2^{16}+0101, 0101 in hexadecimal, assuming padding is done on the lower bytes (for higher bytes the logic is just the same). Being e the private exponent, and m^2 computed in the size of m, (m\cdot 2^{16}+0101)^e \pmod m is very different from (m^2\cdot 2^{16}+0101)^... 2 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 \\...

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 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.... 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$0<k&...

1

I assume that the deadline for the homework is passed, so I will provide an answer: Let us assume that we have the public key $y=g^x \pmod p$ and the private key to be $x$. Computing an ElGamal signature for a message $m \in Z_p^*$ amounts to: choosing $k\in Z_p^*$ $r\equiv g^k \pmod p$ $s\equiv (m-xk)k^{-1} \pmod{p-1}$ which is equivalent to $m\equiv ... 1 What do you mean by forge? If you are asking about (the common) existential forgery, then two message, signature pairs are enough, given that the messages differ in at least two bits. As an example consider that you have the signatures for$m_1 = 1111$and$m_2 = 1100$. Considering the preimages you now have, you can forge signatures for$m_3=1101$and$m_4=...

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