#331 closed defect (wontfix)

add DSA to pycryptopp - serialize pubkeys with less fluff

Reported by: zooko Owned by: zooko
Priority: critical Milestone: eventually
Component: code-mutable Version: 0.8.0
Keywords: ecdsa pycryptopp performance forward-compatibility Cc: warner
Launchpad Bug:

Description

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

Attachments (1)

size-tests.patch (36.5 KB) - added by warner at 2008-06-17T03:08:16Z.
additional tests, including a failing "serialized verifying key is too fluffy" test

Download all attachments as: .zip

Change History (34)

comment:1 Changed at 2008-03-05T21:40:03Z by zooko

  • Status changed from new to assigned

comment:2 Changed at 2008-03-08T01:29:54Z by zooko

  • Resolution set to fixed
  • Status changed from assigned to closed

done

comment:3 Changed at 2008-03-08T01:42:49Z by zooko

  • Resolution fixed deleted
  • Status changed from closed to reopened

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.

comment:4 Changed at 2008-03-08T04:14:30Z by zooko

  • Milestone changed from 0.9.0 (Allmydata 3.0 final) to undecided

comment:5 Changed at 2008-03-13T17:06:07Z by zooko

  • Milestone changed from undecided to 0.9.0 (Allmydata 3.0 final)

comment:6 Changed at 2008-03-13T17:51:58Z by zooko

  • Milestone changed from 0.9.0 (Allmydata 3.0 final) to 0.10.0

comment:7 Changed at 2008-05-06T23:37:18Z by 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.

comment:8 Changed at 2008-05-29T22:31:15Z by warner

  • Milestone changed from 1.1.0 to 1.2.0

comment:9 Changed at 2008-06-17T02:03:03Z by 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

comment:10 Changed at 2008-06-17T03:06:35Z by 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

Changed at 2008-06-17T03:08:16Z by warner

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

comment:11 Changed at 2008-06-17T03:09:35Z by warner

  • Summary changed from add DSA to pycryptopp to add DSA to pycryptopp - serialize pubkeys with less fluff

comment:12 Changed at 2008-08-27T02:24:37Z by warner

  • Priority changed from major to critical

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.

comment:13 Changed at 2008-08-27T16:59:14Z by 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.

comment:14 Changed at 2008-08-27T18:56:07Z by 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.

comment:15 Changed at 2008-08-27T20:01:19Z by zooko

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

comment:16 Changed at 2008-09-02T19:05:17Z by warner

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

comment:17 Changed at 2008-09-02T21:44:34Z by 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.

comment:18 Changed at 2008-09-03T01:04:30Z by warner

ok, it's a deal. thanks!

comment:19 Changed at 2008-09-17T01:57:04Z by 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.

comment:20 Changed at 2008-09-17T06:27:16Z by 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!

comment:21 Changed at 2008-09-17T17:21:29Z by 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.

comment:22 Changed at 2008-09-17T18:14:25Z by 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).

comment:23 Changed at 2008-09-17T18:38:31Z by 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.

comment:24 Changed at 2008-09-18T04:25:37Z by 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.

comment:25 Changed at 2008-10-07T02:07:03Z by 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.

comment:26 Changed at 2009-02-04T00:24:25Z by zooko

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

comment:27 Changed at 2009-06-19T18:49:46Z by 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!

comment:28 Changed at 2009-06-30T17:50:19Z by zooko

  • Milestone changed from 1.5.0 to 1.6.0

comment:29 Changed at 2009-08-20T17:53:59Z by warner

  • Component changed from code to code-mutable

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?

comment:30 Changed at 2009-12-13T05:32:56Z by zooko

  • Milestone changed from 1.6.0 to eventually

comment:31 Changed at 2010-01-07T00:24:55Z by davidsarah

  • Keywords ecdsa pycryptopp performance added

comment:32 Changed at 2010-01-07T00:25:11Z by davidsarah

  • Keywords forward-compatibility added

comment:33 Changed at 2012-01-09T15:42:31Z by zooko

  • Resolution set to wontfix
  • Status changed from reopened to closed

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

Note: See TracTickets for help on using tickets.