[EC]DSA "semi-private"/intermediate keys

[warner]

For Tahoe, we've discussed the creation of DSA "semi-private" keys, in which
there would be multiple steps between the signing key and the verifying key,
so we can hash the intermediate steps and use them to control access to
various things.

See here for a proposed API to this functionality:

​http://allmydata.org/pipermail/tahoe-dev/2008-October/000828.html

[zooko]

fix typo in original description

[warner]

API proposal

[warner]

There's been a lot of discussion about semi-private keys on
​http://allmydata.org/trac/tahoe/ticket/217 , which is the feature in Tahoe
that we hope to implement by using semi-private keys. I'm trying to drag the
discussion about non-Tahoe things back here, to the pycryptopp ticket.

The proposal so far:

privkey=x (uniformly chosen from [1..n-1])
semiprivkey = g^x
y = H(g^x), truncated to fit [1..n-1], "re-roll" if necessary
signingkey = x*y
verifyingkey = g^(x*y)

Where the holder of the privkey can derive everything, the holder of the
semiprivkey can derive the verifying key, and the holder of the verifying key
can't derive anything else.

Now, Zooko responded to one concern by adding the "re-roll if necessary"
clause: since the group size "n" is never equal to a power of two, a
uniformly-distributed hash function needs some massaging to use it to obtain
a uniformly-distributed number in the range [1..n-1]. You could
truncate it to some 2^m such that m <= n-1, but that leaves a lot
of the range uncovered. You could truncate it to 2^(m+1) and take the
result mod n, but that double-covers a lot of the range. The best (only?) way
to get a uniform distribution is to truncate it to slightly larger than the
[1..n-1] range, but then have a process to "re-roll" if you luck out
and hit that edge case. For us, that would mean something like:

def make_y(x, n):
    i = 0
    while True:
        h = sha256("%s-%s" % (g**x, i)).digest()
        num = truncate_and_integerify(h, ceil(log2(n)))
        if 1 <= num <= n-1:
            return num
        i += 1

But! I don't think that's what Shawn was concerned about. Instead (and Shawn,
please correct me if I'm wrong), I think he was concerned with the fact that
"y" will not have nearly the same range as x does. It's basically another
form of the "birthday paradox". There is a one-to-one mapping from x to
g^x, but there is a many-to-one mapping from our truncated-hash y
function (even without the re-roll clause).

I wrote up a little program to exercise this. Hashing 65536 (2^16)
consecutive strings and then truncating them into a 16-bit value only
produces about 41500 unique values. Doing the same with 2^18 18-bit
strings results in about 165000 unique values out of the 262144 possible
ones. A 20-bit run gives 663k unique values out of 1048k possible.

So I think that Shawn's concern is that the range of "y" is reduced (perhaps
by 1.0 or 0.5 bits), and therefore the range of the x*y signing key
will be reduced, weakening the security of the system.

[swillden]

Replying to warner:

So I think that Shawn's concern is that the range of "y" is reduced (perhaps
by 1.0 or 0.5 bits), and therefore the range of the x*y signing key
will be reduced, weakening the security of the system.

My concern is that x*y mod q is not uniformly distributed, even if x and y are uniformly distributed. I think, though that I may be incorrectly assuming the product is modulo q, since I don't see that in the paper. If the signing key is x*y, not x*y mod q, then my whole analysis was misguided.

[davidsarah]

Replying to swillden:

My concern is that x*y mod q is not uniformly distributed, even if x and y are uniformly distributed.

This was discussed in ​on tahoe-dev but should be recorded here:

ECDSA can work on elliptic curves over either GF(p) or GF(2^m) [or GF(p^m) but I don't think that's a standardised option]. When the curve is over GF(p), ECDSA is specified to use a prime subgroup, say of order q. Ordinary DSA also uses a prime subgroup of order q.

For any prime q and any x in [2, q-1], the function that maps y to xy mod q, for y in [1, q-1], is a permutation. Therefore, except for the special cases of x = 1 or y = 1 which should have negligable probability, multiplying by a random [EC]DSA private key should yield another random [EC]DSA private key. So there should be no problem with the uniformity of private keys in this scheme, provided that only curves over GF(p) are used in the case of ECDSA.

Note that this only addresses the specific concern that Shawn had; public key crypto is difficult to analyse and there could be other attacks.

[warner]

Cool, so if I understand you correctly, then in my example above, "y" won't
have the full range, but that won't matter, because both signingkey and
verifyingkey *will* have the full range (signingkey because the
x*y step is a permutation of x, and verifyingkey because
generators-raised-to-a-power is also a permutation).

Of course, some of the range specifications I used must be corrected: "x"
should be uniformly chosen from 2..q-1 instead of 1..q-1 .

Great! Ship it! :)