botan: ed25519 key blinding API not found

Tor rendezvous spec3 describes how private and public key blinding works.

A.2. Tor's key derivation scheme

  We propose the following scheme for key blinding, based on Ed25519.

  (This is an ECC group, so remember that scalar multiplication is the
  trapdoor function, and it's defined in terms of iterated point
  addition. See the Ed25519 paper [Reference ED25519-REFS] for a fairly
  clear writeup.)

  Let B be the ed25519 basepoint as found in section 5 of [ED25519-B-REF]:

      B = (15112221349535400772501151409588531511454012693041857206046113283949847762202,
           46316835694926478169428394003475163141307993866256225615783033603165251855960)

  Assume B has prime order l, so lB=0. Let a master keypair be written as
  (a,A), where a is the private key and A is the public key (A=aB).

  To derive the key for a nonce N and an optional secret s, compute the
  blinding factor like this:

           h = H(BLIND_STRING | A | s | B | N)
           BLIND_STRING = "Derive temporary signing key" | INT_1(0)
           N = "key-blind" | INT_8(period-number) | INT_8(period_length)
           B = "(1511[...]2202, 4631[...]5960)"

  then clamp the blinding factor 'h' according to the ed25519 spec:

           h[0] &= 248;
           h[31] &= 63;
           h[31] |= 64;

  and do the key derivation as follows:

      private key for the period:

           a' = h a mod l
           RH' = SHA-512(RH_BLIND_STRING | RH)[:32]
           RH_BLIND_STRING = "Derive temporary signing key hash input"

      public key for the period:

           A' = h A = (ha)B

  Generating a signature of M: given a deterministic random-looking r
  (see EdDSA paper), take R=rB, S=r+hash(R,A',M)ah mod l. Send signature
  (R,S) and public key A'.

  Verifying the signature: Check whether SB = R+hash(R,A',M)A'.

  (If the signature is valid,
       SB = (r + hash(R,A',M)ah)B
          = rB + (hash(R,A',M)ah)B
          = R + hash(R,A',M)A' )

  This boils down to regular Ed25519 with key pair (a', A').

  See [KEYBLIND-REFS] for an extensive discussion on this scheme and
  possible alternatives. Also, see [KEYBLIND-PROOF] for a security
  proof of this scheme.

I was able to generate the nonce properly with the actual botan API. Clamping is not a big deal, it can be done even manually w/o botan however I don’t see any publicly available API which with private and public key derivation can be done.

In order to give an example public key derivation needs the following group operators which are botan internals (presume for good reason):

ge_frombytes_negate_vartime
ge_double_scalarmult_vartime
ge_tobytes

I’ve attached a small code snippet from tor source to ease the understanding. Any suggestion is appreciated how this can be resolved. Thanks in advance! 😃

blinding.zip

About this issue

  • Original URL
  • State: closed
  • Created 3 years ago
  • Comments: 15 (5 by maintainers)

Commits related to this issue

Most upvoted comments

OK so as I understand the code in Tor there are a couple of desires here

First, to validate the public key, namely by checking for the point not being the identity element and verifying that it is in the prime-order subgroup. Right now Ed25519_PublicKey::check_key is a no-op but it could/should adopt these checks.

Secondly, derive a new private key (and cooresponding public key) from an existing one using scalar multiplication. We can present this as a new constructor Ed25519_PrivateKey(const Ed25519_PrivateKey& base_key, const uint8_t tweak[32], const char* extra_input = nullptr). For Tor the extra_input would be the constant string “Derive temporary signing key hash input”; if nullptr/empty it is ignored. This API will still be kind of a special case for Tor, but I’d rather do that than expose internal functions.

What do you think? I’m not 100% this gives you everything you need but it seems closer anyway. The check_key behavior is generally useful so I’ll do that in any case.

I’m amazed how reactive and helpful you’re guys 😃 Here is the full spec: https://gitlab.torproject.org/tpo/core/torspec/-/blob/master/rend-spec-v3.txt