[tor-dev] Safe Alternative Uses of Onion Service Keys

[George Kadianakis]

Matthew Finkel <sysrqb at 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:
>
>  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?
>

In which way would we use LH and RH directly in EdDSA?

>  2) 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.

>  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?
>

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.

>
>  4) 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.

>  5) 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! :)