3
$\begingroup$

The two main security definitions for signatures are EUF-CMA and the strong version of it sEUF-CMA.

What I see that their difference is that in EUF-CMA experiment, the adversary needs to produce a valid signature for a message of its choosing, where the message has not been queried before (i.e., a message for which the adversary hasn't made queries to the oracle).

Whereas in the sEUF-CMA experiment, similar thing happens, though now the adversary needs to make sure that it hasn't queried the oracle with the forged (message, signature) pair. So, simply the signature also enters into the equation in sEUF-CMA.

  1. The part that I don't understand is why the sEUF-CMA actually constitutes a stronger definition than regular EUF-CMA definition? Why does including the signature makes it stronger?

  2. Also, for example in ECDSA, for a message $m$ and a valid signature $\sigma = (r,s)$, the signature $\sigma' = (r, -s \bmod N)$ is also valid. So, in a sense you get a new signature $\sigma'$, but, actually the signed message is the same $m$.

    So, this seems to me that it does violate sEUF-CMA as, although the message is the same one, the signature is different, so adversary wins. Whereas, this cannot violate EUF-CMA, while there we care only for the message, so we don't care if adversary can produce a forgery for an already queried message. So, it achieves EUF-CMA security, but not sEUF-CMA, right?.

  3. I think the situation is also different in textbook RSA, where it has homomorphic properties, so given a valid $(m, \sigma)$ pair, using the homomorphic properties one can produce a valid signature $\sigma'$ for a new message $m'$, and it seem does not satisfy any of the provided security definitions, is that right?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

What I see that their difference is that in EUF-CMA experiment, the adversary needs to produce a valid signature for a message of its choosing, where the message has not been queried before (i.e., a message for which the adversary hasn't made queries to the oracle).

Whereas in the sEUF-CMA experiment, similar thing happens, though now the adversary needs to make sure that it hasn't queried the oracle with the forged (message, signature) pair. So, simply the signature also enters into the equation in sEUF-CMA.

Right. The point of EUF-CMA is the forger simply can't find a signature on any message it didn't send to the oracle. With sEUF-CMA, the forger can't find a message/signature pair it didn't get from the oracle—not even a second signature on a message it did send to the oracle.

  1. The part that I don't understand is why the sEUF-CMA actually constitutes a stronger definition than regular EUF-CMA definition? Why does including the signature makes it stronger?
  • Can you forge signatures for messages not previously seen in an sEUF-CMA signature scheme, or can you prove that that's not possible? What does that imply about whether an sEUF-CMA signature scheme is necessarily EUF-CMA?
  • Can you find a signature scheme that satisfies EUF-CMA but not sEUF-CMA? (Hint: you already did!) What does that imply about whether an EUC-CMA signature scheme is necessarily sEUF-CMA?

‘Strong’ just mean it implies other properties which don't necessarily imply it conversely. Most protocols don't rely on strong unforgeability. While Bitcoin doesn't rely on strong unforgeability, the first Bitcoin exchange, MtGox, did; it was exploited, because ECDSA does not provide strong unforgeability, and the subsequent demise of MtGox was later blamed on transaction malleability, whether rightly or not (paywall-free).

Another relevant property is signature uniqueness where even the signer can't come up with a second signature for a message—for this you may even want a VRF, a verifiably pseudorandom function, which is a PRF to anyone who doesn't know the key and is a signature to anyone who does and gives a verifiable proof of uniqueness.

  1. Also, for example in ECDSA, for a message $m$ and a valid signature $\sigma = (r,s)$, the signature $\sigma' = (r, -s \bmod N)$ is also valid. So, in a sense you get a new signature $\sigma'$, but, actually the signed message is the same $m$.

    So, this seems to me that it does violate sEUF-CMA as, although the message is the same one, the signature is different, so adversary wins. Whereas, this cannot violate EUF-CMA, while there we care only for the message, so we don't care if adversary can produce a forgery for an already queried message. So, it achieves EUF-CMA security, but not sEUF-CMA, right?.

Correct.

  1. I think the situation is also different in textbook RSA, where it has homomorphic properties, so given a valid $(m, \sigma)$ pair, using the homomorphic properties one can produce a valid signature $\sigma'$ for a new message $m'$, and it seem does not satisfy any of the provided security definitions, is that right?

Textbook RSA signature is, indeed, completely broken. RSA was the first idea for how to make a signature scheme, but it was completely insecure; the first secure signature scheme was Rabin's in 1979.

The crucial insight of Rabin was that hashing is an integral part of a signature scheme. Some textbooks will confusingly describe hashing as an afterthought to compress long messages, and talk of hash-then-sign, which is a dangerously wrong idea that can lead people to make mistakes that destroy security.

The computation of a hash and the computation of fancy math can be done separately, but only when they are combined into a verification equation like $\sigma^e \equiv H(m) \pmod n$ do you get a secure signature scheme.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the reply. Though, answer to my first question is still unclear to me. It is apparent that there are schemes that satisfy EUF-CMA definition but not the sEUF-CMA, but I just don't understand what that intuitively means for a signature scheme. That it is just non-malleable? Simply, what does sEUF-CMA definition want to tell us, why is checking whether we queried the oracle with the specific signature necessary also? Btw, which signature satisfies sEUF-CMA definition, since ECDSA doesn't seem to do it. $\endgroup$
    – user4936
    Mar 21, 2019 at 16:20
  • $\begingroup$ You may be able to add extra verification criteria to make signatures nonmalleable. For example, in ECDSA, you could require that $s$ be ‘positive’, meaning $s \leq (n - 1)/2$ where $n$ is the order of the group. Signature malleability caused some trouble for Bitcoin—see transaction malleability. But in most protocols it doesn't matter; for those where you do need signature uniqueness, you may even want a VRF instead. $\endgroup$
    – Squeamish Ossifrage
    Mar 21, 2019 at 16:35
0
$\begingroup$

Little bit late. sEUF-CMA is stronger, because an adversary has more freedom. It can try to find a new hash to messages it already has queried before. If an adversary has no luck in sEUF-CMA, it has no luck in EUF-CMA either. Here the adversary makes no use of its advantage. sEUF-CMA security implies EUF-CMA security, and if we are talking about an deterministic MAC method (Sign(k,m) is deterministic and Verify(k,m,t)=1 <=> Sign(k,m)=t), then sEUF-CMA is equivalent to EUF-CMA, since every m has only one hash. So you cannot find a new hash to the tupel (m,t).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.