add DSA to pycryptopp - serialize pubkeys with less fluff #331

New Issue

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.

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.

zooko removed the

fixed

label 2008-03-08 01:42:49 +00:00

zooko reopened this issue

2008-03-08 01:42:49 +00:00

zooko modified the milestone from 0.9.0 (Allmydata 3.0 final) to undecided

2008-03-08 04:14:30 +00:00

zooko modified the milestone from undecided to 0.9.0 (Allmydata 3.0 final)

2008-03-13 17:06:07 +00:00

warner commented

2008-05-06 23:37:18 +00:00

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.

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 modified the milestone from 1.1.0 to 1.2.0

2008-05-29 22:31:15 +00:00

warner commented

2008-06-17 02:03:03 +00:00

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

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 commented

2008-06-17 03:06:35 +00:00

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

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 commented

2008-06-17 03:08:16 +00:00

Attachment size-tests.patch (37379 bytes) added

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

**Attachment** size-tests.patch (37379 bytes) added additional tests, including a failing "serialized verifying key is too fluffy" test

size-tests.patch

36 KiB

warner changed title from ~~add DSA to pycryptopp~~ to add DSA to pycryptopp - serialize pubkeys with less fluff

2008-06-17 03:09:35 +00:00

warner commented

2008-08-27 02:24:37 +00:00

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.

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.

warner added

critical

and removed

major

labels 2008-08-27 02:24:37 +00:00

zooko commented

2008-08-27 16:59:14 +00:00

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.

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 commented

2008-08-27 18:56:07 +00:00

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 commented

2008-08-27 20:01:19 +00:00

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

warner commented

2008-09-02 19:05:17 +00:00

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

zooko commented

2008-09-02 21:44:34 +00:00

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 commented

2008-09-03 01:04:30 +00:00

ok, it's a deal. thanks!

zooko commented

2008-09-17 01:57:04 +00:00

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.

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 commented

2008-09-17 06:27:16 +00:00

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!

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 commented

2008-09-17 17:21:29 +00:00

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 commented

2008-09-17 18:14:25 +00:00

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).

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 commented

2008-09-17 18:38:31 +00:00

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.

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 commented

2008-09-18 04:25:37 +00:00

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.

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 commented

2008-10-07 02:07:03 +00:00

#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 commented

2009-02-04 00:24:25 +00:00

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

warner commented

2009-06-19 18:49:46 +00:00

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!

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!

zooko modified the milestone from 1.5.0 to 1.6.0

2009-06-30 17:50:19 +00:00

warner commented

2009-08-20 17:53:59 +00:00

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?

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?

warner added

code-mutable

and removed

code

labels 2009-08-20 17:53:59 +00:00

zooko modified the milestone from 1.6.0 to eventually

2009-12-13 05:32:56 +00:00

zooko commented

2012-01-09 15:42:31 +00:00

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

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

zooko added the