[tahoe-dev] [pycryptopp] #2: deterministic generation of private key from small seed

[pycryptopp]

#2: deterministic generation of private key from small seed
------------------------+---------------------------------------------------
Reporter:  zooko        |           Owner:  zooko
    Type:  enhancement  |          Status:  new  
Priority:  major        |         Version:  0.4.0
Keywords:               |   Launchpad_bug:       
------------------------+---------------------------------------------------
Changes (by zooko):

 * cc: tahoe-dev@… (added)


Comment:

 I posted to the cryptopp-users mailing list asking for feedback about my
 current approach:

 http://groups.google.com/group/cryptopp-users/msg/01a2620f684a70bd

 -------
 I am about to implement "deterministic generation of private key from
 small seed" [1] for Tahoe, so I need to come up with a function that takes
 an input of 96 bits and produces a 192-bit ECDSA private key.  I'm going
 to have to support this functon forever (approximately) for backwards-
 compatibility reasons.  I would really like the next release of Tahoe to
 be compatible with older Crypto++ versions.  Also I would really like for
 this function to be as simple and clear as possible so that I can easily
 explain to other people how to implement it compatibly.

 My current code to do this is below (and I've earlier posted it to this
 list: [2]), but I'm not entirely satisfied with it because it seems rather
 ad-hoc.  One of my earlier notes on this subject to this list, [2], says
 that I experimented with using X917RNG with a customization of Salsa20 to
 pretend that it has a block size of 32.

 So, I ask everyone, what is the simplest efficient way to take a secret
 96-bit input, and produce an output between [1, n) such that

 a) if you know the 96-bit secret and use this algorithm, you always get
 the same output, and
 b) if you don't know the 96-bit secret, you can't learn anything about the
 output

 Unless I, or someone, can think of a problem with this way to do it, or
 can propose a better way to do it, then I guess I'm going to proceed with
 this and then I'll be committed to maintaining it for a while.

 Regards,

 Zooko

 [1] http://allmydata.org/trac/pycryptopp/ticket/2 # deterministic
 generation of private key from small seed
 [2] http://groups.google.com/group/cryptopp-
 users/browse_thread/thread/f30427601a5884f6
 [3] http://groups.google.com/group/cryptopp-users/msg/c1041e508c8d8705

 ------- begin appended code
 static const char* TAG_AND_SALT = "102:pycryptopp v0.5.3 key derivation
 algorithm using Tiger hash to generate ECDSA 192-bit secret exponents," \
     "16:H1yGNvUONoc0FD1d,";
 static const size_t TAG_AND_SALT_len = 127;

 static int
 SigningKey___init__(PyObject* self, PyObject* args, PyObject* kwdict) {
     static const char *kwlist[] = { "seed", NULL };
     const char* seed;
     int seedlen;
     if (!PyArg_ParseTupleAndKeywords(args, kwdict,
 "t#:SigningKey___init__", const_cast<char**>(kwlist), &seed, &seedlen)) {
         return -1;
     }

     if (seedlen != 12) {
         PyErr_Format(ecdsa_error, "Precondition violation: seed is
 required to be of length 12, but it was %d", seedlen);
         return -1;
     }

     OID curve;
     Integer grouporderm1;
     byte privexpbytes[24] = {0};
     Integer privexponentm1;
     privexponentm1.Decode(privexpbytes, sizeof(privexpbytes)); assert
 (priveexponentm1 == 0); // just checking..

     curve = ASN1::secp192r1();
     grouporderm1 = DL_GroupParameters_EC<ECP>(curve).GetGroupOrder() - 1;
     Tiger t;

     t.Update(reinterpret_cast<const byte*>(TAG_AND_SALT),
 TAG_AND_SALT_len);
     t.Update(reinterpret_cast<const byte*>(seed), seedlen);
     t.TruncatedFinal(privexpbytes, Tiger::DIGESTSIZE);
     privexponentm1.Decode(privexpbytes, sizeof(privexpbytes));
     while (privexponentm1 >= grouporderm1) {
         Tiger t2;
         t2.Update(reinterpret_cast<const byte*>(TAG_AND_SALT),
 TAG_AND_SALT_len);
         t2.Update(privexpbytes, sizeof(privexpbytes));
         t2.TruncatedFinal(privexpbytes, Tiger::DIGESTSIZE);
         privexponentm1.Decode(privexpbytes, sizeof(privexpbytes));
     }

     SigningKey* mself = reinterpret_cast<SigningKey*>(self);
     mself->k.AccessKey().Initialize(curve, privexponentm1+1);

     return 0;
 }

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