1 files changed, 104 insertions, 0 deletions
diff --git a/spec/rend-spec/keyblinding-scheme.md b/spec/rend-spec/keyblinding-scheme.md
new file mode 100644
index 0000000..b69a578
--- /dev/null
+++ b/spec/rend-spec/keyblinding-scheme.md
@@ -0,0 +1,104 @@
+<a id="rend-spec-v3.txt-A"></a>
+
+# Appendix A: Signature scheme with key blinding {#KEYBLIND}
+
+<a id="rend-spec-v3.txt-A.1"></a>
+
+## Key derivation overview {#overview}
+
+As described in \[IMD:DIST\] and \[SUBCRED\] above, we require a "key
+blinding" system that works (roughly) as follows:
+
+There is a master keypair (sk, pk).
+
+```text
+        Given the keypair and a nonce n, there is a derivation function
+        that gives a new blinded keypair (sk_n, pk_n).  This keypair can
+        be used for signing.
+
+        Given only the public key and the nonce, there is a function
+        that gives pk_n.
+
+        Without knowing pk, it is not possible to derive pk_n; without
+        knowing sk, it is not possible to derive sk_n.
+
+        It's possible to check that a signature was made with sk_n while
+        knowing only pk_n.
+
+        Someone who sees a large number of blinded public keys and
+        signatures made using those public keys can't tell which
+        signatures and which blinded keys were derived from the same
+        master keypair.
+
+        You can't forge signatures.
+
+        [TODO: Insert a more rigorous definition and better references.]
+```
+
+<a id="rend-spec-v3.txt-A.2"></a>
+
+## Tor's key derivation scheme {#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\]:
+
+```text
+      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:
+
+```text
+           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'.
+
+```text
+  (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.