choose+implement EC-DSA KDF: deterministic generation of private key from small seed

[zooko]

Generate an ECDSA private key -- in a 192-bit GF(p) curve -- from a 96-bit secret seed. Do it fast.

[zooko]

Wei Dai pointed out to me on the Crypto++ mailing list that any algorithm which satisfies the stream cipher interface can be used as a deterministic PRNG, so probably we should use AES-CTR-128bit for that part (in the current ECDSA code I use Tiger-192 hash function).

[zooko]

Oh by the way, this is a potentially dangerous optimization which has not been published in peer-reviewed cryptographic literature as far as I know. I can't see how it could really be weak, considering that if you did require and carry around a full ECDSA 192-bit private key (as opposed to a 96-bit secret seed which is used to deterministically generate the ECDSA 192-bit private key), then where did you get that 192-bit private key in the first place? I'll tell you where you got it -- you got it by using a PRNG on a secret seed (such as /dev/urandom or /dev/random). Therefore, carrying around and using the full key can't really be more secure than carrying around and using the secret seed.

Still, we should really search the crypto literature for discussion of this or publish a paper making claims and subject it to peer review or file a patent on it just to get people riled up so they'll pay attention to us and tell us if I'm wrong about this.

Here is the historical record of my slowly discovering this idea with the help of others:

​http://allmydata.org/trac/tahoe/ticket/217 # DSA-based mutable files -- small URLs, fast file creation

[zooko]

The patch attached to #3 does this, but that patch doesn't work.

[zooko]

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

---

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;
}

[zooko]

I propose to use HKDF with SHA-2-512d-truncated-to-256 as the extractor and SHA-2-256d as the expander:

​http://allmydata.org/pipermail/tahoe-dev/2009-August/002598.html

[warner]

That sounds good. Although, after reading quickly through the paper, I'm still not sure why we need the expander, if SHA-2-512d will give us 512 bits of quality entropy, and we don't have any curves larger than 512 bits. Does it take more than K bits to construct a private key for a K-bit curve?

But, their arguments seem sound, and going with a respected standard wins in my book.
Your proposal sounds fine to me.

[warner]

Oh, also, why truncate the extractor output? Can't the expander step handle a 512bit-long input string?

[warner]

I'm starting to write code for this. So far I've got the existing (Tiger-based) KDF pulled out into a separate function, with a debug hook in place to let us call the KDF function (alone) from unit tests. The plan is to invoke the KDF function with some different seeds, and compare the result (the private exponent) against the same algorithm implemented in python code.

To actually do that would require exposing SHA512 to python, however.

Is it important to use "-d" on both extractor and expander? I have to figure out how to implement the double-hash in C++.

Also, are you still happy with using Tiger as the actual message-digest hash? (i.e. using Tiger as the second template parameter argument). I don't know how/if to change that, for consistency, to SHA256 or whatever.

[warner]

updating the ticket name to reflect the work that remains

[zooko]

I have a few questions about HKDF and how it could be used for our purposes. Fortunately the authors of it are trying to get it standardized and they asked for feedback on a mailing list that I'm subscribed to, so I took the opportunity to ask them:

​http://www.ietf.org/mail-archive/web/cfrg/current/msg02651.html
​http://www.ietf.org/mail-archive/web/cfrg/current/msg02652.html

[zooko]

The next step is to figure out if HKDF-Poly1305 or HKDF-VMAC is as secure as HKDF-HMAC. The author of HKDF -- Hugo Krawczyk -- is also one of the authors of HMAC, and while he is a world expert on the topic of KDFs, his interest in this discussion seems to be limited to advocating HMAC:

​http://www.ietf.org/mail-archive/web/cfrg/current/msg02699.html

I have a lot of reservations about using HKDF-HMAC-SHA256 when as far as I can currently tell HKDF-Poly1305-XSalsa20 would be stronger (and more long-lived) and faster:

​http://www.ietf.org/mail-archive/web/cfrg/current/msg02687.html

Note especially Prof. Bernstein's remarks (posted years ago):

​http://www.ietf.org/mail-archive/web/cfrg/current/msg01167.html

"HMAC, etc. are examples of the Wegman-Carter framework. They use
SHA with a secret IV as the hash function---conjectured to have low
differential probabilities---and SHA with another secret IV as the
encryption function---conjecturally a PRF.

These aren't particularly good Wegman-Carter examples. We have _faster_
hash functions that are _proven_ to have low differential probabilities.
For example, Poly1305 has low differential probabilities and is much
faster than SHA, so it's much better than SHA as the hash function in a
Wegman-Carter MAC."

[zooko]

If we're going to use HKDF-Poly1305-XSalsa20 (my current preference), then we also #33 (implement Poly1305 or VMAC), #15 (XSalsa20).

[warner]

We chatted on IRC the other week about what the next step should be. Deciding
upon and implementing the KDF seems like the best one. Testing the KDF is a
challenge. Here's my current favorite approach.

• the C function (in ecdsamodule.cpp) to construct an ECDSA signing key should take a longint argument named exponent=, and raise a ValueError (or maybe TypeError) if its numeric value is outside the acceptable range (I think this is 1..q-2, where "q" is the size of the prime subgroup, but I may be wrong).
• the C module should also export a constant, next to the constructor function, which allows Python code to learn what "q" is.
• pycryptopp must also expose Poly1305 and/or XSalsa20, or whatever hash function we plan to use for the KDF.
• the Python module should provide an ECDSASigningKey class, whose constructor takes an argument named seed=, which accepts a variable length string.
  • internally, this constructor should call a python function named KDF, which takes the seed and "q", and invokes whatever hash functions, expansions, modulus computations, and try-try-again loops as necessary until it comes up with an exponent in the correct range. Then it should call the C-based constructor.
  • we might like to say that omitting seed= causes the python code to use os.urandom(ceil(log2(q)))) as a seed.

This moves the KDF logic out of C and into Python, where we can test it more
easily.

If we get concerned about speed, we could implement the KDF logic in C as
well, but retain exponent= as an option (callers would either pass
exponent= or seed= but not both), and then have tests which
assert equality of keys generated with the C seed= argument against
keys generated with exponent=python.KDF(seed), to confirm that the
C-based KDF code behaves the same way as the sample Python implementation.

As to choice of KDF (specifically the "turn N random bits into a suitable
random secret exponent" sort of derivation function), I think the four basic
variants we discussed (ignoring choice of hash function) were:

• 1 (try-try-again): guess=HASH(seed+counter), truncate to ceil(log2(q)) bits, test against limit, if out of bounds then increment counter and try again
• 2 (bigmodulo): expand the seed to perhaps 2*log2(q) bits, reduce it modulo the limit, done. (actually it'd be more like e=1+(largesecret%(q-3)) or something)
• 3 (truncate): expand the seed to floor(log2(q)) bits, done.
• 4 (bigmodulo-and-try-try-again): expand the seed to 2*log2(q) bits, if that is larger than q*int(guess/q) (i.e. in the "tail"), try again, else reduce modulo q and return

The try-try-again choices (1 and 4) have the unfortunate property that,
depending upon how close the group size is to a power of two, they might be
very hard to test (if q=2128-9 then the chances of triggering the loop are
negligible, so writing a test to exercise that code would be hard). The
opposite extreme is occasional cases of looping a large number of times (if
q=2128+9 then nearly half of the 129-bit keys would be out-of range,
causing a loop, and although the average number of loops should be two, the
exponential distribution of loop counts means that sometimes you'll get 10 or
100 or 1000 loops).

The other choices (2 and 3) have the unfortunate property that there will be
some amount of bias in the resulting key, although at least David-Sarah
believes that the 2-bigmodulo variant can reduce the bias down to a
negligible size (less than a bit). 2-bigmodulo needs an efficient bigint
modulo operation, which is probably not a big deal in the C code (and
certainly not a problem up at the Python level). 3-truncate has up to one bit
of bias, reducing a 128-bit key to more like a 127-bit key, but is
super-simple and super-fast.

[zooko]

Fortunately the Brainpool elliptic curve that we'd like to use--brainpoolP256r1--has a group size of 76884956397045344220809746629001649092737531784414529538755519063063536359079, which is a mere 60% of the next power of two: 115792089237316195423570985008687907853269984665640564039457584007913129639936 . So it would be easy to test the looping behavior.

[zooko]

Replying to warner:

I'm starting to write code for this. So far I've got the existing (Tiger-based) KDF pulled out into a separate function, with a debug hook in place to let us call the KDF function (alone) from unit tests. The plan is to invoke the KDF function with some different seeds, and compare the result (the private exponent) against the same algorithm implemented in python code.

Do you still have the code for this? I would like it.

[warner]

half-finished patch to extract Tiger-based KDF into separate function for testing

[zooko]

This is superceded by Ed25519. Yay!