[tahoe-dev] [pycryptopp] #13: DSA "semi-private"/intermediate keys

[pycryptopp]

#13: DSA "semi-private"/intermediate keys
------------------------+---------------------------------------------------
Reporter:  warner       |           Owner:       
    Type:  enhancement  |          Status:  new  
Priority:  major        |         Version:  0.5.1
Keywords:               |   Launchpad_bug:       
------------------------+---------------------------------------------------

Comment(by 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.

-- 
Ticket URL: <http://allmydata.org/trac/pycryptopp/ticket/13#comment:2>
pycryptopp <http://allmydata.org/trac/pycryptopp>
Python bindings for the Crypto++ library