[tor-dev] Proposal 220 (revised): Migrate server identity keys to Ed25519

Wed Mar 5 00:42:28 UTC 2014

Nick Mathewson <nickm at torproject.org> writes:

> I've revised proposal 220 based on commentary from Roger.  The biggest
> changes is tweaking all of the things called "certificates" to make
> them actually follow the same format to greatest the extent possible.
>
> To see diffs, you can use git, or browse the gitweb site at
> https://gitweb.torproject.org/torspec.git/history/HEAD:/proposals/220-ecc-id-keys.txt
>

The proposal looks good.

Below you can find some nitpicks.

>
> <snip>
>
>    The EXTENSIONS field contains zero or more extensions, each of
>    the format:
>
>          ExtLength [1 or 2 bytes]
>          ExtType   [1 or 2 bytes]
>          ExtData   [Length bytes]
>
>    The ExtLength and ExtType fields can represent values between 0
>    and 2^15-1, representing values under 128 as "0xxxxxxx" and
>    values over 128 as "1xxxxxxx yyyyyyyy".  The meaning of the
>    ExtData field in an extension is type-dependent.
>

Ugh. Do these multi-sized fields look nasty only to me?

Parsing them will not be too hard, but it definitely increases the
parsing complexity. And just to save two bytes per extension _when_
extensions are used?

I think I would personally upgrade both fields to 2 bytes. Except if
these credentials will get passed around in great numbers.

>    It is an error for an extension to be truncated; such a
>    certificate is invalid.
>
>    Before processing any certificate, parties MUST 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.
>
>    This
>

is a nickmism.

> 2.3. Revoking keys.
>
>    We also specify a revocation document for revoking a signing key or an
>    identity key.  Its format is:
>          FIXED_PREFIX    [8 Bytes]
>          VERSION         [1 Byte]
>          KEYTYPE         [1 Byte]
>          IDENTITY_KEY    [32 Bytes]
>          REVOKED_KEY     [32 Bytes]
>          PUBLISHED       [8 Bytes]
>          REV_EXTENSIONS  [variable length, up to length of revocation
>                           document minus 64 bytes]
>          SIGNATURE       [64 Bytes]
>
>    FIXED_PREFIX is "REVOKEID" or "REVOKESK". VERSION is [01]. KEYTYPE is
>    [01] for revoking a signing key or [02] for revoking an identity key.
>    REVOKED_KEY is the key being revoked; IDENTITY_KEY is the node's
>    Ed25519 identity key. PUBLISHED is the time that the document was
>    generated, in seconds since the epoch. REV_EXTENSIONS is left for a
>    future version of this document.  The SIGNATURE is generated with
>    the same key as in IDENTITY_KEY, and covers the entire revocation,
>    prefixed with "Tor key revocation v1".
>

Do we need both KEYTYPE and FIXED_PREFIX? Aren't they both used to
distinguish what type of key we are revoking?

>    Using these revocation documents is left for a later specification.
>
> <snip>
>
> 3.2. Formats
>
>    Vote and microdescriptor documents now contain an optional "id"
>    field for each routerstatus section.  Its format is:
>
>        "id" SP "ed25519" SP ed25519-identity NL
>
>    where ed25519-identity is base64-encoded, with trailing = characters
>    omitted.  In vote documents, it may be replaced by the format:
>
>        "id" SP "ed25519" SP "none" NL
>
>    which indicates that the node does not have an ed25519 identity.  (In
>    a microdescriptor, a lack of "id" line means that the node has no ed25519
>    identity.)
>
>    [XXXX Should the id entries in consensuses go into microdescriptors
>      instead? I think perhaps so. -NM]
>

Is this XXXX still valid? This section mentions microdescriptors and
not consensuses.

>    A vote or consensus document is ill-formed if it includes the same
>    ed25519 identity key twice.
>
> 3.3. Generating votes
>
>    An authority should pick which descriptor to choose for a node as
>    before, and include the ed25519 identity key for the descriptor if
>    it's present.
>
>    As a transition, before Rule 1 and Rule 2 in 3.1 are fully enforced,
>    authorities need a way to deal with the possibility that there might
>    be two nodes with the same ed25519 key but different RSA keys.  In
>    that case, it votes for the one with the most recent publication
>    date.
>
>    (The existing rules already prevent an authority from voting for two
>    servers with the same RSA identity key.)
>
> 3.4. Generating a consensus from votes
>
>    This proposal requires a new consensus vote method.  When we deploy
>    it, we'll pick the next available vote method in sequence to use for
>    this.
>
>    When the new consensus method is in use, we must choose nodes first
>    by ECC key, then by RSA key.
>
>    First, for every {ECC identity key, RSA identity key} pair listed by
>    over half of the voting authorities, list it, unless some other RSA
>    identity key digest is listed more popularly for the ECC key.  Break
>    ties in favor of low RSA digests. Treat all routerstatus entries that
>    mention this <ECC,RSA> pair as being for the same router, and all
>    routerstatus entries that mention the same RSA key with an
>    unspecified ECC key as being for the same router.
>
>    Then, for every node that has previously not been listed, perform the
>    current routerstatus algorithm: listing a node if it has been listed
>    by at least N/2 voting authorities, and treating all routerstatuses
>    containing the same identity as the same router.
>
>    In other words:
>
>      Let Entries = []
>
>      for each ECC ID listed by any voter:
>         Find the RSA key associated with that ECC ID by the most voters,
>         breaking ties in favor of low RSA keys.
>
>         If that ECC ID and RSA key ID are listed by > N/2 voting authorities:
>             Add the consensus of the routerstatus entries for those
>             voters, along with the routerstatus entry for every voter
>             that included that RSA key with no ECC key, to Entries.
>             Include the ECC ID in the consensus.
>

In this phase, all the RSA keys we are considering are tied to ECC
keys, right?

Shouldn't "along with the routerstatus entry for every voter that
included that RSA key with no ECC key" be handled by the phase below?

(I might be wrong since I'm not familiar with the voting process of Tor)

>       For each RSA key listed by any voter:
>         If that RSA key is already in Entries, skip it.
>
>         If the RSA key is listed by > N/2 voting authorities:
>             Add the consensus of the routerstatus entries for those
>             voters to Entries.  Do not include an ECC key in the
>             consensus.
>
>    [XXX Think about this even more.]
>
> 4. The link protocol

> <snip>
>
> 4.2. Link protocol changes for ECC ID keys
>
>    We add four new CertType values for use in CERTS cells:
>         4: Ed25519 signing key
>         5: Link key certificate certified by Ed25519 signing key
>         6: Ed25519 TLS authentication key certified by Ed25519 signing key
>         7: RSA cross-certificate for Ed25519 identity key
>    These correspond to types used in the CERT_TYPE field of
>    the certificates.
>
>    The content of certificate type [04] (Ed25519 signing key)
>    is as in section 2.5 above, containing an identity key and the
>    signing key, both signed by the identity key.
>
>    Certificate type [05] (Link certificate signed with Ed25519
>    signing key) contains a SHA256 digest of the X.509 link
>    certificate used on the TLS connection in its key field; it is
>    signed with the signing key.
>
>    Certificate type [06] (Ed25519 TLS authentication signed with
>    Ed25519 signing key) has the signing key used to sign the
>    AUTHENTICATE cell described later in this section.
>
>    Certificate type [07] (Cross-certification of Ed25519 identity
>    with RSA key) contains the following data:
>        ED25519_KEY                       [32 bytes]
>        EXPIRATION_DATE                   [4 bytes]
>        SIGNATURE                         [128 bytes]
>    Here, the Ed25519 identity key is signed with router's RSA
>    identity key, to indicate that authenticating with a key
>    certified by the Ed25519 key counts as certifying with RSA
>    identity key.  (The signature is computed on the SHA256 hash of
>    the non-signature parts of the certificate, prefixed with the
>    string "Tor TLS RSA/Ed25519 cross-certificate".)
>
>    (There's no reason to have a corresponding Ed25519-signed-RSA-key
>    certificate here, since we do not treat authenticating with an RSA
>    key as proving ownership of the Ed25519 identity.)
>
>    Relays with Ed25519 keys should always send these certificate types
>    in addition to their other certificate types.
>

This is another area I'm not very familiar with, but IIUC relays with
Ed25519 will need to send 7 certificates. The 3 old ones and these 4
new ones.

I guess, maybe they could skip "1: Link key certificate certified by
RSA1024 identity" since it's already covered by certificate 5, but
maybe one extra certificate is not that bad (and maybe better than
writing risky "don't require certificate 1 if ..." logic in the
authentication code).

>
> <and the proposal goes on>
>