Ed25519-based semi-private keys

semiprivate.md

Semiprivate Keys

🚨 DANGER: INSECURE! 🚨

This may have seemed like a great idea in 2013, but the repeated "set/clear bits", a.k.a. clamping phases at each level of the hierarchy slowly subtract key strength.

Don't use this as described. Check out Ristretto.

Original text

Semi-private keys are an expansion of the traditional idea of asymmetric keys, which have a public/private keypair, to N keys which can each represent a different capability level. In the degenerate case, a semi-private key system has 3 different types of keys. These are, to use the Tahoe terminology:

• writecap: can publish new ciphertexts
• readcap: can read/authenticate ciphertexts
• verifycap: can authenticate ciphertexts

One of the goals of Tahoe is to keep the capability tokens for each of these short. Tahoe goes to pretty extreme lengths to do this, like symmetrically encrypting an RSA key and storing it along with a file.

I definitely applaud what they've done there and also believe that short capabilities are more useful. The real goal of a semi-private key system is to produce short capability tokens which are more convenient for users to distribute (potentially in non-digital forms)

The problem is Tahoe's description of semi-private keys is intended for DSA, however I would like to implement semi-private keys for use with NaCl. NaCl uses elliptic curve cryptography, so the implementation is slightly different.

This is, as best I understand it, how to implement it in terms of NaCl:

Constants:

• P = NaCl base point (standard group element)
• l = Order(P)

Functions:

• H(): SHA512 truncated to 256-bits + set/clear bits

Variables:

• k = random Ed25519 seed
• x = H(k)
• Q = x*P (semiprivate key)
• y = H(Q) mod l
• z = x*y mod l (computed Ed25519 private scalar)
• R = y*Q (Ed25519 public key)

Test:

assert(R == z*P)

Figure 1: Semiprivate Key Generation

Figure 2: Ed25519 (unmodified)

Credits

Semiprivate keys were originally Zooko's idea. The basic idea is described in section 6.1 of the Tahoe-LAFS paper.

SAGE code courtesy Samuel Neves

semiprivate.sage

import hashlib
 
p = 2^255 - 19;
E = EllipticCurve(GF(p), [0,486662,0,1,0]);
P = E.lift_x(9);
l = P.order();
 
x = ZZ.random_element(l);
Q = x*P;
y = int(hashlib.sha512(str(Q)).hexdigest(), 16) % l;
z = x*y % l;
R = y*Q;
assert(R == z*P)

libsodium issue here: jedisct1/libsodium#236 (comment)

As mention, the Sage code seems to be the x25519 (Montgomery) curve, not the ed25519 curve. Anyone that managed to represent the ed25519 curve in Sage. Sage seems to mandate curve creation in the long Weierstrass equation. So how to represent ed25519 (Edwards curve) is certainly not obvious to me.