5
$\begingroup$

In the EdDSA for more curve paper the authors defines:

Keys

An EdDSA secret key is a $b$-bit string $k$. The hash $H(k) = (h_0, h_1, ... , h_{2b−1})$ determines an integer $s = 2^n+\sum_{c≤i<n} 2^ih_i$ , which in turn determines the multiple $A = sB$. The corresponding EdDSA public key is $A$.

Note that $B$ is defined to be a point of order $l$ where the cardinality of the curve is $\#E(p)=2^cl$

Signature

The signature of a message $M$ under key $k$ is created as:

  • Define $r = H(h_b, ...., h_{2b-1},M) \in \{0,1,...,2^{2b}-1\}$.
  • Define $R = rB$.
  • Define $S = (r + H(\underline{R},\underline{A},M)s) \mod l$

Output: $(\underline{R},\underline{S})$ (note that underline is a byte encoding of points or integers which doesn't matter for this question)

Verification

Verification of a signature $(\underline{R},\underline{S})$ of a message $M$ is defined as:

$2^cSB = 2^cR+2^cH(\underline{R},\underline{A},M)A$

Cofactorless Verification

Cofactorless verification of a signature $(\underline{R},\underline{S})$ of a message $M$ is defined as: $SB = R+H(\underline{R},\underline{A},M)A$


They comment that:

Any alleged signature that passes cofactorless verification will also pass verification. The signature of a message will pass cofactorless verification, so it will also pass verification. However, a signer using a secret key outside the above signing procedure can create strings that pass verification without passing cofactorless verification.

I can't really understand the above comment and I have a few questions.

  1. What does it mean "secret key outside the above signing procedure" ? Does it mean that $s$ is a string without a leading nth-bit set and not multiple of $2^c$ ?
  2. How does the $2^c$ factor affects the verification compared to cofactorless verification?
  3. Can you provide me an example/way of generating a secret key "outside the above signing procedure" that generates a signature that pass verification without passing cofactorless verification ?
$\endgroup$
  • $\begingroup$ I am not sure, but maybe they mean the following: If $C$ is an element from $E$ with $2^c C = 0$ , then $A' = A+C$ satisfies the cofactor equation but not the cofactorless equation. The same argument applies to $R' = R + C$. $\endgroup$ – user27950 Nov 7 '15 at 7:38
  • $\begingroup$ @Cryptostasis. Thanks, I agree with you. Interestingly, a user can generate multiple different signatures (by adding different $C$ to $R$) which will pass verification. But nor this, nor $A'$ can be obtained with "secret key outside the above signing procedure". I'll try to edit the question to better focus on this. $\endgroup$ – Ruggero Nov 9 '15 at 10:38
3
$\begingroup$

1. It means that someone possessing the private key $s$ can create signatures which pass verification but not cofactorless verification with respect to the public key $A$.

3. For example, if $C\in E$ is a point of even order (e.g. $2^c$), and the signer replaces $R:=rB$ in step 2 of the signing procedure by $R:=rB+C$, then $$ 2^cR+2^cH(\underline R,\underline A,M)A \;=\; 2^cSB+2^cC \;=\; 2^cSB $$ but $$ R+H(\underline R,\underline A,M)A \;=\; SB+C \;\neq\; SB \text. $$ The private key is necessary to create such a signature because anyone modifying $R$ (or one of the other parameters) after the signature has been finalized (e.g., someone who does not know the private key) is very likely to be caught by $H(\underline R,\underline A,M)$ contributing to the verification formula. (Note this contradicts Cryptostasis' comment above.)

2. Due to the Pohlig-Hellman algorithm, the security of the whole system is dependent on the large prime-order subgroup $E[\ell]$ of $E$, while small prime factors of the group order do not reasonably contribute to the hardness of computing discrete logarithms. Group-theoretically, multiplication by $2^c$ realizes a projection to the subgroup of $E$ of size $\ell$, which is a direct factor: From the structure theorem of finite abelian groups, $$ E\;\cong\;E[\ell]\times G\text, $$ where $G$ is an abelian group of order $2^c$, hence multiplication by $2^c$ maps an element to $E[\ell]\times\{e\}\leq E[\ell]\times G$. (And since $\ell$ is coprime to $2$, multiplication by $2^c$ is an automorphism on $E[\ell]\times\{e\}$.) Thus multiplication by $2^c$ throws away a little bit of information from the factor group $G$, but that wasn't useful anyway.
In practice, it is not going to matter which variant you use. As explained above, cofactorless verification is a little stricter, hence you might run into interoperability problems with non-conforming signers (but I see no reason why anyone would implement it in a way that makes this happen). On the other hand, verification (with multiplication by $2^c$) will take a few cycles more.

$\endgroup$
  • $\begingroup$ For some protocols it does matter, at least that the variant is precisely specified. Consider a Bitcoin-like block chain protocol that uses EdDSA signatures to authorize transactions. (Bitcoin uses only ECDSA, but Zcash also uses EdDSA.) If some implementations accept a class of non-conforming signatures that others do not, then the different implementations can be made to follow different chain forks, which is a denial of service and can potentially be used for double spending. The fact that the private key is needed to generate a non-conforming signature does not prevent this attack. $\endgroup$ – Daira Hopwood Jan 10 '18 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.