Score:4

Can the security of ECDSA be compromised by the chosen parameters?

de flag
CCS

The recommended parameters for a secp256k1 ECDSA curve are:

(All values are in hexadecimal)

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 
    FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
a = 00000000 00000000 00000000 00000000
    00000000 00000000 00000000 00000000 
b = 00000000 00000000 00000000 00000000
    00000000 00000000 00000000 00000007
G = 02
    79BE667E F9DCBBAC 55A06295 CE870B07
    029BFCDB 2DCE28D9 59F2815B 16F81798 (compressed version)
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE
    BAAEDCE6 AF48A03B BFD25E8C D0364141
h = 01

However, if I change any of those parameters and used them, then will the security of the trapdoor function be compromised significantly?

For example, I could use:

G = 02
    B3949141 E36A5EE6 22754219 A87D849B
    DC5EA332 F2944A03 1A585112 F05673EA  (compressed version)

as the value of $G$ to generate public keys instead of the recommended value of above. Will the security of the trapdoor function - and subsequently, the public keys - be compromised significantly?

Maarten Bodewes avatar
in flag
This site supports both MarkDown (that the formatting buttons generate) and MathJax / Latex. Please format your questions to the best of your abilities before posting.
Score:4
in flag

For example, I could use:

If the discrete log is already backdoored with the standard base point $G$, then changing the base to another point on the curve doesn't solve this issue.

Let you know that $G$ is backdoored and you changed the base to $G' \neq G$. Then the entity that created the backdoor can use this to find the private keys.

Let $P = [k]G'$ be a public key with the new base. The attacker solves Dlog of $G' = [a]G$ only once. Using this they forms $P = [ak]G$. This is in the backdoored base so that they can solve the discrete logairhtmm to find $ak$. Once $ak$ is found, extracting the secret key can be performed with a simple modular arithmetic $k = ak \cdot a^{-1} \bmod n$ where the $a^{-1}$ is the inverse of $a$ in the modulo $n$.

As a result, once you have a backdoored discrete logarithm, then the curve is not safe to use. It is all in one, if a base point has a trapdoor then all base points have trapdoors!

However, if I change any of those parameters and used them, then will the security of the trapdoor function be compromised significantly?

Changing the parameters $p,a$, and $b$ that defines $n$ and $h$, except the basepoint, change the curve and the new curve needs to be extensively analyzed;

  1. Does the curve order has a prime or has a large prime factor?
  2. Does the twist of the curve have large prime order?
  3. Does it have a safe discrete log?
  4. ...

These are the basics, more on this see safecurves

CCS avatar
de flag
CCS
So changing the base point G will not have any effect on the security, however, changing any other parameter will?
kelalaka avatar
in flag
Yes, changing $G$ doesn't have an effect, changing the curve parameters $(p,a,b)$ will define a new curve and that needs to be analyzed. A random curve doesn't need to be a safe curve.
Yehuda Lindell avatar
us flag
@kelaka Your answers prove that the discrete log relative to different generators is hard, up to solving a single discrete log. However, given that we don't have a full reduction of ECDSA to discrete log, it is theoretically possible that ECDSA is easy for some $G'$ and not for others. Furthermore, if $G'$ is chosen in a special way and such that its discrete log relative to $G$ isn't known, then theoretically this could break ECDSA. There may be another proof, and in practice my guess would be that you're right, but this doesn't prove it.
kelalaka avatar
in flag
@YehudaLindell thanks for the enlightening comment.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.