add DSA to pycryptopp - serialize pubkeys with less fluff

[zooko]

This is necessary for #217 -- "DSA-based mutable files -- small URLs, fast file creation".

[zooko]

done

[zooko]

I need to actually make the new version of pycryptopp available and packaged and so forth, which I'm going to do, actually, by automating that process with buildslaves -- #281 (buildslaves for pycryptopp).

Then I'll reclose this.

[warner]

we're still waiting on no-overhead serialization: ​http://allmydata.org/trac/pycryptopp/ticket/3 , since I think we need this for DSA-based mutable files.

[warner]

Hm, I suppose the best way to make progress on this is to write up some unit tests which exactly specify the sort of DSA features we require out of pycryptopp. I suppose:

• the signing key object should have a serialize method that returns a 192-bit string
• the verification key obhect should have a serialize method that returns a 384-bit string
• those strings should be accepted by an unserialize method
• the signing key object should return a verification key object upon demand

[warner]

It looks like pycryptopp trunk (and 0.5.1) has almost everything I want, the only piece left is for serialized verifier keys to be small (I'm expecting 48 bytes, I observe 246 bytes).

I've attached a patch with some new test cases, including one that checks the size of the serialized verifier key. This test case fails.

EC-DSA-192 is nice and fast! On my workstation (fluxx):

• ecdsa.generate(): 260-310us
• signer.serialize(): 1.7-2.6us
• signer.get_verifying_key(): 2.7-3.3ms
• verifier.serialize(): 37-64us
• ecdsa.create_signing_key_from_string(signer_s): 131-300us
• ecdsa.create_verifying_key_from_string(verifier_s): 150-300us
• signer.sign(len<=1000): 2.4-2.9ms, len=1M: 15ms, len=10MB: 140ms
• verifier.verify(len<=1000): 5.7-6.7ms, len=1M: 18-33ms, len=10MB: 137ms

[warner]

additional tests, including a failing "serialized verifying key is too fluffy" test

[warner]

do we have an ETA on this? I want to look at signed-introducer-announcements, and I need the pubkey serialization scheme to be nailed down before I can finalize the certificate format.

#68, #466, #295, #467, #217, and Accounting are all blocked on this one.

[zooko]

Let's see, I have the following other things that are currently sort of ahead of this one in my queue: immutable file checking, contributing a bunch of patches or bug reports or so on to nevow, setuptools, pyflakes, etc., and writing up a proposal for the SHA-3 project. Oh, and automating the building of binaries of pycryptopp. And contributing to the project of automating darcs benchmarking and building packages.

However, I am highly motivated by this ticket -- I enjoy hacking on pycryptopp. I already have written some code for this but it isn't complete and tested.

So, um, I need to think more carefully and schedule the order of these things. Perhaps Brian and I should pair-program on immutable file checker.

[warner]

So, could you condense your decision tree down into a date that you can commit to? Two weeks from now? Four weeks? That would help me organize my own schedule.

[zooko]

Yes I can. I will so condense and commit soon.

[warner]

Any luck with this? Could you provide a meta-ETA? :)

[zooko]

How about this: if you do lots of work on release management of Tahoe v1.3.0 next week (Sept. 8-12), then I'll work on pycryptopp and it will be ready for you to use by the following Monday -- Sept. 15.

[warner]

ok, it's a deal. thanks!

[zooko]

Well, I'm sorry to say that this isn't done yet. It is mostly done, but there is a bug in my use of the Crypto++ API/memory management which makes it unusable until I debug it.

Furthermore, I think I should prioritize immutable checking and repair (#483 ?) over getting this working. So I now predict that I will have this working next Monday, the 22nd.

On the bright side, it occurs to me that you could proceed with the other tickets that you mentioned using the current ecdsa implementation in pycryptopp. The keys will be unnecessarily large, and I intend to change the API, but the basic functionality is already implemented so you might be able to go ahead and use it to implement those other features.

[warner]

True, if I put a version identifier in the container format (to indicate that this value is a "fluffy" ECDSA-192 pubkey instead of an "unfluffy" one), then I can get started with the current code. There will be less code if I don't have to support both formats, so I might stall on starting that work until you've got this ticket done.

Speaking of which, please consider adding a one-byte version prefix to the serialized form. I think that may help later versions of the code, so tahoe can just pass a string to pycryptopp.ecdsa.pubkey_from_string() and not need to know that it has a fluffy, unfluffy, or expanded other-than-192bits alternate-serialization-scheme-of-the-future -serialized pubkey.

Monday the 22nd will be fine. Thanks!

[zooko]

It seems like this versioning should be done by the higher-layer code that uses pycryptopp and not by pycryptopp. This is because putting it in pycryptopp would add a byte (or so) the serialized forms, which might be unacceptable for some users of pycryptopp (including me), and because the higher-layer code knows better about related issues, such as if there are other changes that are all versioned together (Tahoe would use different pycryptopp serialization as well as different crypto, different capability formatting, etc.), or if it no longer cares about certain old versions, etc.

[warner]

Ok, do you plan to support multiple APIs for deserializing pubkeys from various eras of pycryptopp? A higher layer can remember which serialization function it used to create the pubkey string, and it can record that in a wrapper, but we need a clear (and stable) definition of what that function means for that to be at all useful. I don't see how, say, Tahoe could manage this without something like:

 pycryptopp.publickey.ecdsa.create_verifying_key_from_string_v1()  # fluffy
 pycryptopp.publickey.ecdsa.create_verifying_key_from_string_v2()  # unfluffy q.v. #331
 pycryptopp.publickey.ecdsa.create_verifying_key_from_string_v3()  # handles 256bit also
 etc..

I can't write deployable code that uses the existing (fluffy) pubkey form if that form is going to disappear.

(incidentally, I still don't know how to get this whole versioning thing "right", but I'm starting to learn that it's important to leave some room in the parse tree space, and that it's important to make early assumptions clear so that later you can define that set of assumptions as "version 1" and build a new "version 2" on top of it).

[zooko]

No, my plan was just to tell everyone who used the current pycryptopp API that if they upgraded to the new version of pycryptopp then their ECDSA-using code would break.

Probably "everyone" in that sentence would just be you and me.

[warner]

ok, so that means I shouldn't ship (or push, really) any ECDSA-using code until you've finished with the defluffing work, because I have no way to make it forwards-compatible.

I'll refer to the current implementation of create_verifying_key_from_string() and its converse as "v0", and the implementation that you're working on as "v1". If we ever change it again in the future (say, to add support for non-192-bit keys), then I'll need you to retain the v1 code (possibly under a different function name, but preferably under the same name), and to add a new method with whatever "v2" implementation that you come up with later. Otherwise, I will have no way to make it backwards-compatible, and users will experience a "flag day" when everybody has to upgrade at the same time.

[warner]

#466 is now blocked on this one.. the #466 code is ready to be pushed into trunk, as soon as #331 is closed (with the release of a new version of pycryptopp), and some brief catch-up-to-the-new-API work is done.

[zooko]

This is urgently important to allow Brian to do other tickets.

[warner]

pycryptopp-0.5.13, released a week or two ago, added ecdsa! But then it got yanked, because the KDF (the code that interprets the random string you pass into SigningKey) is not yet in a form that Zooko feels comfortable supporting in the long run (and it's a significant compatibility issue, to make sure that generating a key from string ABC will keep generating the same key in the future).

So close!

[warner]

moving to code-mutable so I can find it more easily.

Zooko floated a KDF proposal to tahoe-dev last week, and nobody objected! That's progress, right?

[zooko]

We're abandoning implementation of ECDSA in favor of Ed25519: ​https://tahoe-lafs.org/trac/pycryptopp/ticket/75