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! 😃
About this issue
- Original URL
- State: closed
- Created 3 years ago
- Comments: 15 (5 by maintainers)
Commits related to this issue
- Implement Ed25519 public key checking GH #2660 — committed to randombit/botan by randombit 3 years ago
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 theextra_inputwould 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_keybehavior 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