Hello everyone,
Onion service version two (v2) key pairs were used for more purposes than simply facilitating the establishment of rendezvous circuits, in particular third-party applications used this key in numerous ways. Similarly, version three (v3) onion service keys are being re-used in similar (and new) ways. However, the (re)use of v3 long-term keys is not obviously safe in all situations. How should (and should not) these keys be used, such that the security of the onion service is preserved?
I'll briefly summarize v3 keys (for those who don't want to read through the spec), and then I'll sketch two alternative use cases along with a straw man proposal. The long-term v3 identity keys are ed25519 keys (see [0] for a nice write up of ed25519, in general). The generated key material is serialized externally (outside of tor) in two (similar) formats: written on-disk [2] and from the control port [3].
The secret (private) key is the (64-byte) SHA-512 digest of a 32-byte seed value. The 64-byte digest is the "expanded form". The seed is thrown away. The public key is obtained by taking the first 32 bytes of that SHA-512 hash, clamping some of the bits, and performing a scalar multiplication with the (fixed) base point. This key is the onion service long-term identity key.
Creating and verifying a signature using the above keys (respectively) follow standard EdDSA. However, (at this time) Tor does not use these keys directly for signing messages. All messages are signed using an ephemeral ed25519 key, and that ephemeral key is certified by a blinded ed25519 key derived from the long-term key pair. The blinded keys are computed using a specified blinding scheme [4]. All messages signed using the ephemeral key are prefixed with a context-specific string. In summary, long-term keys are used for deriving a short-term blinded key, and that short-term blinded key is used for certifying an ephemeral signing key.
For computing the blinded key, the first 32 bytes of the long-term secret key (LH) are multiplied with a blinding factor (h*a mod l), see the specification for the value of **h** [4]. This becomes LH' (LH-prime). The second 32 bytes of the secret key (RH) are concatenated with a string prefix and then the SHA3-256 digest is computed of the concatenated string. The first 32 bytes of the resulting digest become RH' (RH-prime). LH' and RH' are used as regular ed25519 secret keys for signing and verifying messages following EdDSA.
Tor's EdDSA signature is "R|S", R concatenated with S (the message is not included in the signature).
The safest usage of the long-term keys for alternative purposes I see appears to be by deriving a (fixed/deterministic) blinded key pair using the same scheme that Tor uses, and signing/verification simply follow the same process as Tor, except the derived keys need not rotate periodically (is this true?). The derived key should be used for certifying a freshly generated ed25519 key, which is used in the application protocol. For example, if I want to use a key for code signing such that it is bound to my onion service key, then I could derive a certifying key by following Tor's derivation scheme, by substituting:
BLIND_STRING = "Derive temporary signing key" | INT_1(0) N = "key-blind" | INT_8(period-number) | INT_8(period_length)
with
BLIND_STRING = "Derive code signing key" | INT_1(0) N = "code-sigining-key-blind" | "v0" | "YYYY-MM-DD" | INT_8(validity_period)
for computing the blinding factor. Where "v0" is a version tag. YYYY-MM-DD is an arbitrary date, but it can be used for rotating signing keys in the future. INT_8(validity_period) may be used for specifying the number of days after YYYY-MM-DD at which time previously unverified signatures using this key should be considered invalid (where INT_8(0) could indicate "never expire").
And substituting
RH_BLIND_STRING = "Derive temporary signing key hash input"
with
RH_BLIND_STRING = "Derive code signing key hash input"
for computing RH'.
A signature must include "v0" and the values used in "YYYY-MM-DD" and INT_8(validity_period), such that the client can derive the correct blinded public key for verification when starting from the long-term identity key. The signature should be over a certification of an independently generated ed25519 key pair. This new key pair (along with the certification) can be used for providing message integrity within the application's protocol. If, instead, the derived key is used directly for signing, and the application needs the keys online for signing messages, then this risks the security of the long-term key, as well. The blinding scheme allows for (partially) recovering the long-term secret key from the derived secret key.
Another example use case comes from Jeremy Rand where the onion service key is used in a root CA certificate, and a leaf certificate (signed by the CA cert) is used by the application.
Following from the previous example, (most likely) the CA certificate should not be signed directly using the onion service's long-term secret key. However, a derived key could be used in the CA certificate and the leaf cert could contain an ephemeral key (in exactly the same way that tor certifies ephemeral keys using the derived blinded signing key). This idea appears to be a concrete design of how the above (abstract) key certification could be implemented, and it could be a format that tor natively supports.
The above process seems like a lot to ask from application developers. Can we make it easier for them?
Open questions:
1) Going back to the long-term secret key, can LH and RH be used directly in EdDSA without reducing the security and unlinkability of the blinded keys?
2) Should other use cases of the long-term keys only derive distinct (blinded) keys, instead of using the long-term keys directly?
3) If other use cases should only use derived keys, then is there an alternative derivation scheme for when unlinkability between derived keys is not needed (without reducing the security properties of the onion service blinded keys), and is allowing linkability useful/worthwhile?
4) Is the above example derivation scheme safe if different applications tweak the above prefix strings in similar ways?
5) Should Tor simply derive one blinded key that can be used by all alternative applications? Is that safe?
I'd like to thank Nick Mathewson and David Goulet for their comments on an earlier version of this mail.
Thanks, Matt
[0] https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/ [1] https://gitweb.torproject.org/torspec.git/tree/rend-spec-v3.txt#n2267 [2] A tagged value: "== ed25519v1-secret: type0 =="\0\0\0 | (64-byte SHA-512 hash of the seed) [3] https://gitweb.torproject.org/torspec.git/tree/control-spec.txt#n1746 [4] https://gitweb.torproject.org/torspec.git/tree/rend-spec-v3.txt#n2267
On 2020/07/29 05:15, Matthew Finkel wrote:
[ ... snip ... ]
A signature must include "v0" and the values used in "YYYY-MM-DD" and INT_8(validity_period), such that the client can derive the correct blinded public key for verification when starting from the long-term identity key. The signature should be over a certification of an independently generated ed25519 key pair. This new key pair (along with the certification) can be used for providing message integrity within the application's protocol. If, instead, the derived key is used directly for signing, and the application needs the keys online for signing messages, then this risks the security of the long-term key, as well. The blinding scheme allows for (partially) recovering the long-term secret key from the derived secret key.
This is super useful, Matt! Thanks for writing all of this down.
Another example use case comes from Jeremy Rand where the onion service key is used in a root CA certificate, and a leaf certificate (signed by the CA cert) is used by the application.
This idea stemmed from a conversation between David, George, and me a little while after the Stockholm meeting last summer. The implementation of the tool for generating the various x509 files (the x509 CA and the signed x509 certificates) is available from
https://gitlab.torproject.org/ahf/onion-x509
For people who are unaware of what this tool is doing, I can flesh it out here:
Tor uses an ed25519 secret key format that is incompatible with the ed25519 secret key encoding found in x509, and we cannot just convert the .onion identity ed25519 key to a PEM file and make, for example, a web server use it directly. This also seems to be what Matt is recommending against. As seen in Matt's [0], the signatures and public keys are all using the same encoding, however.
In ordinary TLS, where the server sends the certificate chain, we don't keep ANY of our CA's secret keys online (since we hopefully don't have access to them under normal circumstances). Thus, we only need the secret and public key of our leaf certificate to be available for our TLS service to do signatures as part of the TLS protocol. We can therefore generate an "Onion CA" from Tor's .onion identity secret key, but never have to move any secret key with it into our TLS service deployments.
Once we have generated this "Onion CA", which is identified by the onion identity public key, we use the onion-x509 tool to issue leaf certificates that are signed by the "Onion CA." By configuring our TLS service to use the Onion CA and our ed25519 leaf key pair, and its x509 certificate (signed by the Onion CA), the client will be able to verify if the certificate is "valid" just based on the Onion address itself.
I think the stateless nature of this system is pretty cool. I don't believe that moving to blinded keys blocks anything for it to work, which means I think Jeremy and I should probably coordinate to do that instead of the direct use of the onion identity key pair as the tool does today.
Of course, the modifications to the browser are the terrifying part of all of this as such changes touch some scary code paths in how TLS certificates are validated. Still, if this can work, it would make x509 certificates very easily accessible for Onion service operators.
If Jeremy gets the demo to work in Tor Browser and it all looks promising, we should also spend a bit of time rewriting the Go tool to C and bundle it with the Tor codebase.
Following from the previous example, (most likely) the CA certificate should not be signed directly using the onion service's long-term secret key. However, a derived key could be used in the CA certificate and the leaf cert could contain an ephemeral key (in exactly the same way that tor certifies ephemeral keys using the derived blinded signing key). This idea appears to be a concrete design of how the above (abstract) key certification could be implemented, and it could be a format that tor natively supports.
From what I can tell, it should be possible for us to update the
onion-x509 tool to use the blinded key instead.
Exciting stuff!
All the best, Alex.
Matthew Finkel sysrqb@torproject.org writes:
Hello everyone,
Hello hello!
These are all good questions and they become more and more important as the onionspace grows and more use cases appear.
<snip>
For computing the blinded key, the first 32 bytes of the long-term secret key (LH) are multiplied with a blinding factor (h*a mod l), see the specification for the value of **h** [4]. This becomes LH' (LH-prime). The second 32 bytes of the secret key (RH) are concatenated with a string prefix and then the SHA3-256 digest is computed of the concatenated string. The first 32 bytes of the resulting digest become RH' (RH-prime). LH' and RH' are used as regular ed25519 secret keys for signing and verifying messages following EdDSA.
Hmm, not sure about this last sentence. Are you implying that LH' and RH' are two different secret keys? Because I don't think that's the case. LH' and RH' are components of the final public/private keypair.
Tor's EdDSA signature is "R|S", R concatenated with S (the message is not included in the signature).
The above process seems like a lot to ask from application developers. Can we make it easier for them?
Yes I totally agree that this procedure is too much to ask from application developers.
Open questions:
- Going back to the long-term secret key, can LH and RH be used directly in EdDSA without reducing the security and unlinkability of the blinded keys?
In which way would we use LH and RH directly in EdDSA?
- Should other use cases of the long-term keys only derive distinct (blinded) keys, instead of using the long-term keys directly?
I think that's the most important question. That is, what can we safely do with the long-term keys (given that they are also used for this key blinding procedure)?
My intuition is that it's safe to use the long-term keys to sign other things directly, because the blinding factor of the key blinding procedure does not contain any attacker-controlled input. However, this is just an intuition from a non-cryptographer and hence we need a proper security proof, especially given the various complexities of the whole system (e.g. clamping: https://lists.torproject.org/pipermail/tor-dev/2017-April/012204.html), and especially if we want to do more complicated things than just signing (like use those keys for x25519 or something).
In some way I think that exploring this problem is the first step before deciding to use derived keys, since as you said having to use derived keys will complicate things a lot for application developers.
- If other use cases should only use derived keys, then is there an alternative derivation scheme for when unlinkability between derived keys is not needed (without reducing the security properties of the onion service blinded keys), and is allowing linkability useful/worthwhile?
Hm, if linkability between derived keys is _desired_, then perhaps you could generate subsequent derived keys by iterating on top of previous derived keys, instead of iterating on top of the long-term key like HSv3 does. This way you can prove relations between derived public keys without leaking the long-term key.
In any case, IANAC so a security proof is what we need here.
- Is the above example derivation scheme safe if different applications tweak the above prefix strings in similar ways?
Again my intuition says that it should be OK, since tweaking the BLIND_STRING tweaks the blind factor 'h': h = H(BLIND_STRING | A | s | B | N)
And because the blind factor is the output of a hash function, tweaking the BLIND_STRING is not any different from using a blind factor with a different time period value: N = "key-blind" | INT_8(period-number) | INT_8(period_length)
In any case, IANAC so a security proof is what we need here.
- Should Tor simply derive one blinded key that can be used by all alternative applications? Is that safe?
If we assume that derived keys are as safe as long-term keys, then that should be fine, as it is safe for many applications to use the same long-term ed25519 key, assuming that they don't do anything silly with it (like converting between ed25519 and x25519 and exposing a DH oracle that might generate valid signatures for the attacker).
In any case, IANAC so a security proof is what we need here.
---
Hope that was useful. It's as far as I can get here without spending days on it and without going into dangerous waters.
I've seen more and more interest about hierarchical key derivation lately, and it seems like our design is one of the popular ones (and probably the oldest), but there are more these days: https://mailarchive.ietf.org/arch/msg/cfrg/qDJKIMRctVvYuZBYBcACLLeS7hM/ https://forum.web3.foundation/t/key-recovery-attack-on-bip32-ed25519/44 https://github.com/satoshilabs/slips/blob/master/slip-0010.md
In general, I'd be interested in participating in a standarization and security analysis process where we clarify what application-developers can and cannot do with our scheme.
Cheers! :)
On Thu, Jul 30, 2020 at 01:18:33PM +0300, George Kadianakis wrote:
Matthew Finkel sysrqb@torproject.org writes:
Hello everyone,
Hello hello!
These are all good questions and they become more and more important as the onionspace grows and more use cases appear.
<snip>
For computing the blinded key, the first 32 bytes of the long-term secret key (LH) are multiplied with a blinding factor (h*a mod l), see the specification for the value of **h** [4]. This becomes LH' (LH-prime). The second 32 bytes of the secret key (RH) are concatenated with a string prefix and then the SHA3-256 digest is computed of the concatenated string. The first 32 bytes of the resulting digest become RH' (RH-prime). LH' and RH' are used as regular ed25519 secret keys for signing and verifying messages following EdDSA.
Hmm, not sure about this last sentence. Are you implying that LH' and RH' are two different secret keys? Because I don't think that's the case. LH' and RH' are components of the final public/private keypair.
Yes, but no, your description of them as "components of" the keypair seems more correct than mine. My goal was simply to imply that both LH' and RH' are secret values and they are used as secret inputs into the signing procedure, and I wanted to make it clear that the blinding procedure begins with a valid ed25519 secret key and derives a valid ed25519 secret key in the same format as the original (specifically a LH value and a RH value).
Hopefully this clarification doesn't make it more confusing/wrong.
On Wed, Jul 29, 2020 at 1:15 AM Matthew Finkel sysrqb@torproject.org wrote:
Hello everyone,
Hi, Matt!
There's a part of this that I'm still trying to figure out:
The safest usage of the long-term keys for alternative purposes I see appears to be by deriving a (fixed/deterministic) blinded key pair using the same scheme that Tor uses, and signing/verification simply follow the same process as Tor, except the derived keys need not rotate periodically (is this true?). The derived key should be used for certifying a freshly generated ed25519 key, which is used in the application protocol. For example, if I want to use a key for code signing such that it is bound to my onion service key, then I could derive a certifying key by following Tor's derivation scheme, by substituting:
BLIND_STRING = "Derive temporary signing key" | INT_1(0) N = "key-blind" | INT_8(period-number) | INT_8(period_length)
with
BLIND_STRING = "Derive code signing key" | INT_1(0) N = "code-sigining-key-blind" | "v0" | "YYYY-MM-DD" | INT_8(validity_period)
In the case of v3 onion services, 'period-number' comes from the current time, and 'period-length' comes from the consensus, so it's easy for the client to know what parameters to use when deriving the key.
But how is the party that relies on the derived key supposed to know what values were used for "YYYY-MM-DD" and "validity period" in this case? It seems like those two values would need to be shipped along with the key, which could make for logistical issues.
I guess in the case of an X.509 certificate, we could use the validAfter and validUntil fields to set the parameters -- though it's a little weird to have to look at _just_ those fields to see what the signing key is supposed to be.
Maybe, for an X.509 cert, we could have
N = "x509 onion key derivation" | H(unsigned-certificate)
where `unsigned-certificate` is a DER-encoded TBSCertificate (the part of the certificate that's signed). That way, we get a separate blinded key for each certificate.
[...]
The above process seems like a lot to ask from application developers. Can we make it easier for them?
Open questions:
- Going back to the long-term secret key, can LH and RH be used directly in EdDSA without reducing the security and unlinkability of the blinded keys?
From a practical point of view: Forcing the signer to keep LH and RH
online reduces the security of the protocol IMO; the current protocol is designed so that the onion service doesn't need to keep its long-term identity key online.
Also note that if we care about keeping the primary identity key offline, LH' and RH' shouldn't be used directly! Although it is not possible to derive a long-term public key from a blinded public key, it IS possible to derive a long-term _private_ key from a blined private key. That's why in the v3 onion service system, blinded private keys aren't kept for any longer than needed in order to certify a short-term randomly generated signing key.
- Should other use cases of the long-term keys only derive distinct (blinded) keys, instead of using the long-term keys directly?
IMO yes.
If other use cases should only use derived keys, then is there an alternative derivation scheme for when unlinkability between derived keys is not needed (without reducing the security properties of the onion service blinded keys), and is allowing linkability useful/worthwhile?
Is the above example derivation scheme safe if different applications tweak the above prefix strings in similar ways?
Should Tor simply derive one blinded key that can be used by all alternative applications? Is that safe?
Yes, but only if that key will never ever need to rotate.
Here's a suggestion -- what if we come up with a single profile for this kind of key derivation, to be used in X.509. Along with it, we could have a nice small library that can generate and verify the "root" certificates (the ones signed by a blinded key).
What important parts of the application space would be left unaddressed by that?
but it's trivial to verify the certificate if you know what the
On Mon, Aug 10, 2020 at 9:00 AM Nick Mathewson nickm@freehaven.net wrote:
On Wed, Jul 29, 2020 at 1:15 AM Matthew Finkel sysrqb@torproject.org wrote:
Hello everyone,
Hi, Matt!
There's a part of this that I'm still trying to figure out:
The safest usage of the long-term keys for alternative purposes I see appears to be by deriving a (fixed/deterministic) blinded key pair using the same scheme that Tor uses, and signing/verification simply follow the same process as Tor, except the derived keys need not rotate periodically (is this true?). The derived key should be used for certifying a freshly generated ed25519 key, which is used in the application protocol. For example, if I want to use a key for code signing such that it is bound to my onion service key, then I could derive a certifying key by following Tor's derivation scheme, by substituting:
BLIND_STRING = "Derive temporary signing key" | INT_1(0) N = "key-blind" | INT_8(period-number) | INT_8(period_length)
with
BLIND_STRING = "Derive code signing key" | INT_1(0) N = "code-sigining-key-blind" | "v0" | "YYYY-MM-DD" | INT_8(validity_period)
In the case of v3 onion services, 'period-number' comes from the current time, and 'period-length' comes from the consensus, so it's easy for the client to know what parameters to use when deriving the key.
But how is the party that relies on the derived key supposed to know what values were used for "YYYY-MM-DD" and "validity period" in this case? It seems like those two values would need to be shipped along with the key, which could make for logistical issues.
I guess in the case of an X.509 certificate, we could use the validAfter and validUntil fields to set the parameters -- though it's a little weird to have to look at _just_ those fields to see what the signing key is supposed to be.
Maybe, for an X.509 cert, we could have
N = "x509 onion key derivation" | H(unsigned-certificate)
where `unsigned-certificate` is a DER-encoded TBSCertificate (the part of the certificate that's signed). That way, we get a separate blinded key for each certificate.
[...]
The above process seems like a lot to ask from application developers. Can we make it easier for them?
Open questions:
- Going back to the long-term secret key, can LH and RH be used directly in EdDSA without reducing the security and unlinkability of the blinded keys?
From a practical point of view: Forcing the signer to keep LH and RH online reduces the security of the protocol IMO; the current protocol is designed so that the onion service doesn't need to keep its long-term identity key online.
Also note that if we care about keeping the primary identity key offline, LH' and RH' shouldn't be used directly! Although it is not possible to derive a long-term public key from a blinded public key, it IS possible to derive a long-term _private_ key from a blined private key. That's why in the v3 onion service system, blinded private keys aren't kept for any longer than needed in order to certify a short-term randomly generated signing key.
- Should other use cases of the long-term keys only derive distinct (blinded) keys, instead of using the long-term keys directly?
IMO yes.
If other use cases should only use derived keys, then is there an alternative derivation scheme for when unlinkability between derived keys is not needed (without reducing the security properties of the onion service blinded keys), and is allowing linkability useful/worthwhile?
Is the above example derivation scheme safe if different applications tweak the above prefix strings in similar ways?
Should Tor simply derive one blinded key that can be used by all alternative applications? Is that safe?
Yes, but only if that key will never ever need to rotate.
Here's a suggestion -- what if we come up with a single profile for this kind of key derivation, to be used in X.509. Along with it, we could have a nice small library that can generate and verify the "root" certificates (the ones signed by a blinded key).
What important parts of the application space would be left unaddressed by that?
Like, here's the API I'm envisioning, in pseudocode.
On the service side, you would have a function that takes the primary keypair for an onion service, and an unsigned X.509 certificate, and produces a signed certificate:
X509Cert create_cert(PrimaryKeypair, UnsignedCertificate);
then later on, an application that knows the public key for an onion service could check one of these certificates by getting the public key as follows:
PublicKey get_public_key_to_check_cert(X509Cert, PrimaryPublicKey pub);
and then the application would just call the regular X509 verification functions.
.....
Of course, maybe we'd want to stick the blinded signing key in the certificate, so that you could verify the certificate without knowing its identity key? If so we'd need a different API to create the cert, but we could still make it work.
On Mon, Aug 10, 2020 at 09:00:32AM -0400, Nick Mathewson wrote:
On Wed, Jul 29, 2020 at 1:15 AM Matthew Finkel sysrqb@torproject.org wrote:
Hello everyone,
Hi, Matt!
There's a part of this that I'm still trying to figure out:
The safest usage of the long-term keys for alternative purposes I see appears to be by deriving a (fixed/deterministic) blinded key pair using the same scheme that Tor uses, and signing/verification simply follow the same process as Tor, except the derived keys need not rotate periodically (is this true?). The derived key should be used for certifying a freshly generated ed25519 key, which is used in the application protocol. For example, if I want to use a key for code signing such that it is bound to my onion service key, then I could derive a certifying key by following Tor's derivation scheme, by substituting:
BLIND_STRING = "Derive temporary signing key" | INT_1(0) N = "key-blind" | INT_8(period-number) | INT_8(period_length)
with
BLIND_STRING = "Derive code signing key" | INT_1(0) N = "code-sigining-key-blind" | "v0" | "YYYY-MM-DD" | INT_8(validity_period)
In the case of v3 onion services, 'period-number' comes from the current time, and 'period-length' comes from the consensus, so it's easy for the client to know what parameters to use when deriving the key.
But how is the party that relies on the derived key supposed to know what values were used for "YYYY-MM-DD" and "validity period" in this case? It seems like those two values would need to be shipped along with the key, which could make for logistical issues.
I was imagining "just serialize it in the public key". The public key would grow by a few more characters, but not too much. In this case, we'd probably want a defined (extensible) structure for the public key rather than each application defining their own arbitrary format, but I didn't get that far in thinking about it.
-
Alexander Færøy -
George Kadianakis -
Matthew Finkel -
Nick Mathewson