commit 5a79d67a45454ab5b7413478702acb93dfa867e2 Author: Nick Mathewson <nickm@torproject.org> Date: Wed Aug 12 14:39:43 2015 -0400 Start writing/copying/adding a bunch of stuff about ed25519 keys --- cert-spec.txt | 134 +++++++++++++++++++++ dir-spec.txt | 143 +++++++++++++++++++++-- proposals/228-cross-certification-onionkeys.txt | 2 +- tor-spec.txt | 28 ++++- 4 files changed, 296 insertions(+), 11 deletions(-) diff --git a/cert-spec.txt b/cert-spec.txt new file mode 100644 index 0000000..c54fd86 --- /dev/null +++ b/cert-spec.txt @@ -0,0 +1,134 @@ + Ed25519 certificates in Tor + +1. Scope and Preliminaries + + This document describes a certificate format that Tor uses for + its Ed25519 internal certificates. It is not the only + certificate format that Tor uses. For the certificates that + authorities use for their signing keys, see dir-spec.txt. + Additionally, Tor uses TLS, which depends on X.509 certificates; + see tor-spec.txt for details. + + The certificates in this document were first introduced in + proposal 220, and were first supported by Tor in Tor version + 0.2.7.2-alpha. + +1.1. Signing + + All signatures here, unless otherwise specified, are computed + using an Ed25519 key. + + In order to future-proof the format, before signing anything, the + signed document is prefixed with a personalization string, which + will be different in each case. + +2. Document formats + +2.1. Certificates + + When generating a signing key, we also generate a certificate for it. + Unlike the certificates for authorities' signing keys, these + certificates need to be sent around frequently, in significant + numbers. So we'll choose a compact representation. + + VERSION [1 Byte] + CERT_TYPE [1 Byte] + EXPIRATION_DATE [4 Bytes] + CERT_KEY_TYPE [1 byte] + CERTIFIED_KEY [32 Bytes] + N_EXTENSIONS [1 byte] + EXTENSIONS [N_EXTENSIONS times] + SIGNATURE [64 Bytes] + + The "VERSION" field holds the value [01]. The "CERT_TYPE" field + holds a value depending on the type of certificate. (See appendix + A.1.) The CERTIFIED_KEY field is an Ed25519 public key if + CERT_KEY_TYPE is [01], or a SHA256 hash of some other key type + depending on the value of CERT_KEY_TYPE. The EXPIRATION_DATE is a + date, given in HOURS since the epoch, after which this + certificate isn't valid. (A four-byte field here will work fine + until 10136 A.D.) + + The EXTENSIONS field contains zero or more extensions, each of + the format: + + ExtLength [2 bytes] + ExtType [1 byte] + ExtFlags [1 byte] + ExtData [Length bytes] + + The meaning of the ExtData field in an extension is type-dependent. + + The ExtFlags field holds flags; this flag is currently defined: + + 1 -- AFFECTS_VALIDATION. If this flag is present, then the + extension affects whether the certificate is valid; clients + must not accept the certificate as valid unless they + understand the extension. + + It is an error for an extension to be truncated; such a + certificate is invalid. + + Before processing any certificate, parties SHOULD know which + identity key it is supposed to be signed by, and then check the + signature. The signature is formed by signing the first N-64 + bytes of the certificate prefixed with the string "Tor node + signing key certificate v1". + +2.2. Basic extensions + +2.2.1. Signed-with-ed25519-key extension [type 04] + + In several places, it's desirable to bundle the key signing a + certificate along with the certificate. We do so with this + extension. + + ExtLength = 32 + ExtData = + An ed25519 key [32 bytes] + + When this extension is present, it MUST match the key used to + sign the certificate. + +A.1. List of certificate types + + The values marked with asterisks are not types corresponding to + the certificate format of section 2.1. Instead, they are + reserved for RSA-signed certificates to avoid conflicts between + the certificate type enumeration of the CERTS cell and the + certificate type enumeration of in our Ed25519 certificates. + + + **[00],[01],[02],[03] - Reserved to avoid conflict with types used + in CERTS cells. + + [04] - signing a signing key with an identity key (Section 2.5) + + [05] - TLS link certificate signed with ed25519 signing key + (Section 4.2) + + [06] - Ed25519 authentication key signed with ed25519 signing key + (Section 4.2) + + **[07] - reserved for RSA identity cross-certification (Section 4.2) + + [0A] - ntor onion key cross-certifying ntor identity key + +A.2. List of extension types + + [01] - signed-with-ed25519-key (section 2.2.1) + +A.3. List of signature prefixes + + We describe various documents as being signed with a prefix. Here + are those prefixes: + + "Tor node signing key certificate v1" (section 2.1) + "Tor router descriptor signature v1" (see dir-spec.txt) + +A.4. List of certified key types + + [01] ed25519 key + [02] SHA256 hash of an RSA key + [03] SHA256 hash of an X.509 certificate + diff --git a/dir-spec.txt b/dir-spec.txt index 7bba929..e78d30d 100644 --- a/dir-spec.txt +++ b/dir-spec.txt @@ -317,6 +317,10 @@ VoteSeconds and DistSeconds MUST each be at least 20 seconds; FU-VA and VU-FU MUST each be at least 5 minutes. +1.4. Terminology and preliminaries + + + 2. Router operation and formats 2.1. Uploading server descriptors and extra-info documents @@ -378,6 +382,28 @@ authorities MAY reject any descriptor with both DirPort and ORPort of 0.) + "identity-ed25519" NL "-----BEGIN ED25519 CERT-----" NL certificate + "-----END ED25519 CERT-----" NL + + [At most once, in second or first position in document] + + The certificate is a base64-encoded Ed25519 certificate (see + cert-spec.txt) terminating =s removed. When this element is + present, it MUST appear as the first or second element in + the router descriptor. + + The certificate has CERT_TYPE of [04]. It must include a + signed-with-ed25519-key extension (see cert-spec.txt, + section 2.2.1), so that we can extract the master identity key. + + "master-key-ed25519" SP MasterKey NL + + [At most once] + + Contains the base-64 encoded ed25519 master key as a single + argument. If it is present, it MUST match the identity key + in the identity-ed25519 entry. + "bandwidth" bandwidth-avg bandwidth-burst bandwidth-observed NL [Exactly once] @@ -446,21 +472,59 @@ structure, encoded in base64, and wrapped in "-----BEGIN RSA PUBLIC KEY-----" and "-----END RSA PUBLIC KEY-----". + "onion-key-crosscert" NL a RSA signature in PEM format. + + [At most once, required when identity-25519 is present] + + This element contains an RSA signature, generated using the + onion-key, of the following: + + A SHA1 hash of the identity key [20 bytes] + The Ed25519 identity key [32 bytes] + + If there is no ed25519 identity key, or if in some future version + there is no RSA identity key, the corresponding field must be + zero-filled. + + Parties verifying this signature MUST allow additional data + beyond the 52 bytes listed above. + + This signature proves that the party creating the descriptor + had control over the secret key corresponding to the + onion-key. + "ntor-onion-key" base-64-encoded-key [At most once] - A public key used for the ntor circuit extended handshake. It's the - standard encoding of the OR's curve25519 public key, encoded in base - 64. The trailing = sign may be omitted from the base64 encoding. The - key MUST be accepted for at least 1 week after any new key is - published in a subsequent descriptor. + A curve25519 public key used for the ntor circuit extended + handshake. It's the standard encoding of the OR's curve25519 + public key, encoded in base 64. The trailing = sign may be + omitted from the base64 encoding. The key MUST be accepted + for at least 1 week after any new key is published in a + subsequent descriptor. + + "ntor-onion-key-crosscert" SP Bit NL + "-----BEGIN ED25519 CERT-----" NL certificate + "-----END ED25519 CERT-----" NL + + [At most once, required when identity-25519 is present] + + A signature created with the ntor-onion-key, using the + certificate format documented in cert-spec.txt, with type + [0a]. The signed key here is the master identity key. + + Bit must be "0" or "1". It indicates the sign of the ed25519 + public key corresponding to the ntor onion key. + + To compute the ed25519 public key corresponding to a + curve25519 key, see appendix C. "signing-key" NL a public key in PEM format [Exactly once] - The OR's long-term identity key. It MUST be 1024 bits. + The OR's long-term RSA identity key. It MUST be 1024 bits. The encoding is as for "onion-key" above. @@ -483,7 +547,26 @@ An exit-policy summary as specified in sections 3.4.1 and 3.8.2, summarizing the router's rules for connecting to IPv6 addresses. A missing - "ipv6-policy" line is equivalent to "ipv6-policy reject 1-65535". + "ipv6-policy" line is equivalent to "ipv6-policy reject + 1-65535". + + "router-sig-ed25519" SP Signature NL + + [At most once] + + When an identity-ed25519 element is present, there must also + be a "router-sig-ed25519" element. It MUST be the + next-to-last element in the descriptor, appearing immediately + before the RSA signature. It MUST contain an ed25519 + signature of a SHA256 digest of the entire document, from the + first character up to and including the first space after the + "router-sig-ed25519" string, prefixed with the string "Tor + router descriptor signature v1". Its format is: + + The signature is encoded in Base64 with terminating =s remove. + + The signing key in the identity-ed25519 certificate MUST + be the one used to sign the document. "router-signature" NL Signature NL @@ -626,6 +709,9 @@ Fingerprint is encoded in hex (using upper-case letters), with no spaces. + "identity-ed25519" + [As in router descriptors] + "published" YYYY-MM-DD HH:MM:SS NL [Exactly once.] @@ -1006,6 +1092,9 @@ Pluggable transports are only relevant to bridges, but these entries can appear in non-bridge relays as well. + "router-sig-ed25519" + [As in router descriptors] + "router-signature" NL Signature NL [At end, exactly once.] @@ -1263,6 +1352,19 @@ (Only included when generating microdescriptors for consensus-method 18 or later.) + "id" SP "ed25519" SP base64-encoded-ed25519-identity NL + + [At most once] + + The node's master Ed25519 identity key, base64 encoded, + without trailing =s. + + Implementations MUST ignore "id" lines with unrecognized + key-types in place of "rsa1024" or "ed25519" + + (Only included when generating microdescriptors for + consensus-method 21 or later.) + (Note that with microdescriptors, clients do not learn the identity of their routers: they only learn a hash of the identity key. This is all they need to confirm the actual identity key when doing a TLS handshake, @@ -1814,6 +1916,10 @@ this algorithm. "digest" is the base64 encoding of the hash of the router's microdescriptor with trailing =s omitted. + "id" SP "ed25519" SP ed25519-identity NL + "id" SP "ed25519" SP "none" NL + [vote only, at most once] + The footer section is delineated in all votes and consensuses supporting consensus method 9 and above with the following: @@ -2253,6 +2359,8 @@ "18" -- Adds 'id' to microdescriptors. "19" -- Adds "package" lines to consensuses "20" -- Adds GuardFraction information to microdescriptors. + "21" -- Adds Ed25519 keys to microdescriptors and to voting + algorithm. Before generating a consensus, an authority must decide which consensus method to use. To do this, it looks for the highest version number @@ -3165,3 +3273,24 @@ B. General-use HTTP URLs [XXX Add new URLs for microdescriptors, consensus flavors, and microdescriptor consensus. -KL] +C. Converting a curve25519 public key to an ed25519 public key + + Given a curve25519 x-coordinate (u), we can get the y coordinate + of the ed25519 key using + + y = (u-1)/(u+1) + + and then we can apply the usual ed25519 point decompression + algorithm to find the x coordinate of the ed25519 point to check + signatures with. + + Note that we need the sign of the X coordinate to do this + operation; otherwise, we'll have two possible X coordinates that + might have correspond to the key. Therefore, we need the 'sign' + of the X coordinate, as used by the ed25519 key expansion + algorithm. + + To get the sign, the easiest way is to take the same private key, + feed it to the ed25519 public key generation algorithm, and see + what the sign is. + diff --git a/proposals/228-cross-certification-onionkeys.txt b/proposals/228-cross-certification-onionkeys.txt index b3b401c..09ec33b 100644 --- a/proposals/228-cross-certification-onionkeys.txt +++ b/proposals/228-cross-certification-onionkeys.txt @@ -132,7 +132,7 @@ A. Converting a curve25519 public key to an ed25519 public key y = (u-1)/(u+1) - and then we can apply the usual ed25519 point decomporession + and then we can apply the usual ed25519 point decompression algorithm to find the x coordinate of the ed25519 point to check signatures with. diff --git a/tor-spec.txt b/tor-spec.txt index 27c933d..ee0e511 100644 --- a/tor-spec.txt +++ b/tor-spec.txt @@ -142,9 +142,11 @@ see tor-design.pdf. Every Tor relay has multiple public/private keypairs: + These are 1024-bit RSA keys: + - A long-term signing-only "Identity key" used to sign documents and certificates, and used to establish relay identity. - - A medium-term "Onion key" used to decrypt onion skins when accepting + - A medium-term TAP "Onion key" used to decrypt onion skins when accepting circuit extend attempts. (See 5.1.) Old keys MUST be accepted for at least one week after they are no longer advertised. Because of this, relays MUST retain old keys for a while after they're rotated. @@ -152,8 +154,28 @@ see tor-design.pdf. Tor implementations MAY rotate this key as often as they like, and SHOULD rotate this key at least once a day. - Tor relays are also identified by "nicknames"; these are specified in - dir-spec.txt. + This is Curve25519 key: + + - A medium-term ntor "Onion key" used to handle onion key handshakes when + accepting incoming circuit extend requests. As with TAP onion keys, + old ntor keys MUST be accepted for at least one week after they are no + longer advertised. Because of this, relays MUST retain old keys for a + while after they're rotated. + + These are Ed25519 keys: + + - A long-term "master identity" key. This key never + changes; it is used only to sign the "signing" key below. It may be + kept offline. + - A medium-term "signing" key. This key is signed by the master identity + key, and must be kept online. A new one should be generated + periodically. + - A short-term "link authentication" key. Not yet used. + + The RSA identity key and Ed25519 master identity key together identify a + router uniquely. Once a router has used an Ed25519 master identity key + together with a given RSA identity key, neither of those keys may ever be + used with a different key. 2. Connections