5
$\begingroup$

Alice has master EC key pair: $a$ - private key, $A$ - corresponding public key

Bob generates 2 random integers $r_1$ and $r_2$ and wants Alice to derive 2 new key pairs:

$a_1$ = $a$ + $r_1$ and $a_2$ = $a$ + $r_2$ and corresponding public keys $A_1$ and $A_2$

Questions:

  1. Is it possible for Alice to prove that she derived $A_1$ and $A_2$ from $a+r_1$ and $a+r_2$ using Schnorr proof?
  2. Is it secure for Alice to perform such calculations and share public keys considering they would be used for ECDSA?

In PHE paper key rotation is done using 2 random integers $b,c$, not one, and performed by $a*b+c$ instead of just $a+b$ so if Bob maybe generates 2 random integers per keypair it would make more sense?

$\endgroup$
1
  • $\begingroup$ I've reopened the question for you, sorry for the delay, was pre-occupied., $\endgroup$
    – Maarten Bodewes
    Commented May 6, 2023 at 22:39

1 Answer 1

3
$\begingroup$

Alice doesn't have to do anything.

A' = (a+r)*G = a*G + r*G = A + r1*G

Bob can compute these keys himself. That's usually how key diversification works. If he wants Alice to use them he just sends her the relevant r value and explains that he added r*G to her public key to get a derived key.

Security Concerns

If Alice's ECC library is well implemented, this does not cause security problems. There are a few vulnerabilities that get much worse or become actually exploitable when Bob gets to mess with Alice's secret key.

Firstly, if Alice's library is vulnerable to timing attacks (EG:it uses non-constant-time double and add point multiplication), this lets Bob modify her private key to run a timing attack. Variable time scalar operations could also leak information about the private key. Constant time code won't be vulnerable of course.

Curves whose cofactor is not 1 leak information about the secret key when multiplying points with an uncleared cofactor. (curve25519 and ed25519 have cofactor=8 and can leak 3 bits per multiplication). This lets bob leak chosen bits of the key and get the whole thing. Curve25519 scalar clamping is designed to mitigate these attacks and messing around with raw scalars can lead to problems. Some libraries will check for low order points, in others you need to manually clear the cofactor.

def secure_multiply(X,secret):
    X=Scalar_mul(X,8)
    X=Scalar_mul(X,(inverse(8)*(secret))%order)
    return X

Make sure all the operations are constant time including scalar operations.

proving things

Bob obviously doesn't need to prove to himself that he derived those keys correctly.

He might want to prove to Carol that a key he generated was derived in this way from Alice's public key. He can do a Schnorr proof that he knows r such that r*G = A'-A. Other key derivation methods can similarly be proved without sharing the values used to derive the key.

EG:

  • A'=r*A
    • prove by producing (X,s) that meet: -X=Hash(A' || X)*A' + s*A
      • Schnorr proof for dlog(A',base=A)
  • A'=r*A+s*G
    • prove by producing (X,s,t) that meet:
      • X=Hash(A' || X)*A + s*A' +t*G
      • 2 dimensional Schnorr proof for dlog(A,bases=[A',G])
      • Note, we're not doing dlog(A',bases=[A,G])) because Bob could set A'=0*A+s*G (IE:just present a new key he generated) and then he can prove knowledge of dlog(A',bases=[A,G]) = [0,s], which is a valid solution. dlog(A,bases=[A',G]) requires r!=0 for Bob to prove a solution.
$\endgroup$

Your Answer

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

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