[curves] pure-python Ed25519 library for review

[Brian Warner]

On 4/7/15 12:05 PM, Gregory Maxwell wrote:

> I applaud you for seeking public review; but doesn't your remark above
> mean that many people will use it, because its easy, even if their
> actual (and perhaps not completely known to them) security
> requirements demand that it not have timining sidechannels (or memory
> leaks)?

Yeah, that's totally fair. I'm torn on this point. I feel there are
plenty of applications in which a non-constant-time implementation is
safe to use, and the alternative (requiring C code) means those
applications just won't get written or deployed. For example:

* the PAKE-based file-transfer application I built this for
  (https://github.com/warner/magic-wormhole), where each "password" is
  used once, and a human must transcribe the password

* https://github.com/warner/git-lockup , which creates and verifies
  Ed25519 signatures on git commits. The signatures are created locally
  (in a post-commit hook), which the network adversary doesn't get to
  see, and the verifier doesn't have any secrets anyways.

In both applications, requiring users to install a C module requires a
compiler (especially troublesome on windows), or for us to host
pre-compiled binaries (for which we'd really want verifiable /
reproducible builds). The git-lockup application is particularly
sensitive to deployment barriers: thanks to the current pure-python
form, a downstream user of a suitably-published git repo can completely
protect themselves against subsequent (TOFU) unauthorized commits by
just doing:

 git clone XYZ
 cd XYZ
 ./setup-lockup

which installs a hook that verifies the Ed25519 signatures during 'git
fetch'. That setup command doesn't fetch any external code, doesn't
compile anything, and doesn't need to include binaries for every
conceivable platform in the source tree.

> (Especially that seems odd when also talking about SPAKE2, ... a
> complex zero knowledge password based key agreement having a timing
> leak that might even be visible on the network would be really
> unfortunate.)

To be honest, I'm not so worried about SPAKE2, because it's (again,
generally) deployed in a mode where a human has to input something for
each execution of the protocol. So it's naturally rate-limited by the
user's patience, preventing the timing-measuring attacker from getting a
significant number of samples.

I'd be more concerned about something like an automated Ed25519
certificate signer, where the attacker gets non-human-mediated access to
a signing oracle. Or an encrypted-message autoresponder that's using
Curve25519, so you can ping it a million times to accumulate the timing
data.


The big problem with these cautionary footnotes in crypto-libraries is
that they increase the chances someone will use them "off-label". Too
many such footnotes makes it almost impossible to use safely. But
sometimes I think aiming for no footnotes is a limitation too. "The
perfect is the enemy of the good" and all (which of course goes against
our instincts as security folks).

I guess I want to be able to use this library for my own projects, where
I think I can correctly evaluate the consequences of the caveats, and
steer everyone else (or everyone I think won't evaluate them correctly)
towards pynacl and other libsodium-based C bindings. FWIW, I'm not
publishing this to PyPI. But maybe I should add code to make the library
delete itself if it gets run with the wrong userid? :).

thanks,
 -Brian