Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support deeper ed25519 functionality (that can do key blinding) #5068

Closed
asn-d6 opened this issue Nov 18, 2019 · 7 comments
Closed

Support deeper ed25519 functionality (that can do key blinding) #5068

asn-d6 opened this issue Nov 18, 2019 · 7 comments

Comments

@asn-d6
Copy link

@asn-d6 asn-d6 commented Nov 18, 2019

Hello cryptography people!

This is a request for deeper ed25519 support in the Python hazmat crypto lib. The goal is to be able to implement key blinding primitives like the ones used by v3 Tor onion services (also see here for relevant proof). The same techniques AFAIK are used to do hierarchically derived deterministic wallets in various cryptocurrency schemes.


In particular the missing functionality is:

  • Support the (a, RH) private key format as described by Brian Warner, which allows us to blind the privkey scalar a' = blind(a) and still compute a signature with a' which is not possible with the (k, A) private key format that hazmat uses.
  • Support additional ed25519 primitives like:
    • Ability to do scalar multiplication on the 25519 curve
    • Ability to decode and encode points on the curve
    • Ability to check if a point is on the curve

For now, in our Python code we are using djb's super slow ed25519 implementation (which exposes the required primitives), plus the required key blinding code and then we wrap it with a fragile type-ducked key layer that emulates a hazmat key. All in all it's not so much fun particularly since it's incredibly slow.

For comparison in our core C code, we are using the ed25519 donna code, slightly modded to support our blind key primitives and the custom key format.


If the Hazmat lib is not designed to do such low level operations, it would be great if you could suggest alternative approaches for what we are trying to do.

Thanks!

@reaperhulk

This comment has been minimized.

Copy link
Member

@reaperhulk reaperhulk commented Nov 20, 2019

Hmm, this is a tricky problem because we expose the interfaces that OpenSSL supports. Low level ed25519 math isn't available so these sorts of things aren't really possible at the moment. This may be a candidate for discussion on the OpenSSL side to see what APIs are necessary to enable this use case.

@atagar

This comment has been minimized.

Copy link

@atagar atagar commented Nov 20, 2019

Thanks Paul! Possibly a dumb question on my part (asn's a cryptographer, I'm not) but does the cryptography module surface any replacement for slow_ed25519.py's scalarmult?

That function dominates the runtime (~2 seconds per blinding), so if we could replace just that bit it could remediate our performance issues even if the code isn't the prettiest.

@reaperhulk

This comment has been minimized.

Copy link
Member

@reaperhulk reaperhulk commented Nov 20, 2019

We could expose EC_POINT_mul which would allow ed25519 scalar multiplication. Do you have some sample code using slow_ed25519 that I could use to do some basic benchmarks just to see what options are available? I can test binding EC_POINT_mul and doing the math + the faster ed25519 Python impl PyCA played with ~6 years ago https://github.com/pyca/ed25519/blob/master/ed25519.py

@atagar

This comment has been minimized.

Copy link

@atagar atagar commented Nov 21, 2019

Thanks Paul! Here's a standalone demo...

% wget https://www.atagar.com/transfer/cryptography_ticket_5068/slow_ed25519_py -O slow_ed25519.py
% wget https://www.atagar.com/transfer/cryptography_ticket_5068/demo_py -O demo.py

% python --version
Python 2.7.12

% python demo.py 
d912092e392973aca3d8bece3838262b862fca53a627460cb1c3018102224bb60ecb159b030ea4dfb1ff21601eb7c812652303915cf56312915aae58ef7b0105 <= expected signature
d912092e392973aca3d8bece3838262b862fca53a627460cb1c3018102224bb60ecb159b030ea4dfb1ff21601eb7c812652303915cf56312915aae58ef7b0105 <= calculated ed25519 signature

% python3 --version
Python 3.5.2

% python3 demo.py 
b'd912092e392973aca3d8bece3838262b862fca53a627460cb1c3018102224bb60ecb159b030ea4dfb1ff21601eb7c812652303915cf56312915aae58ef7b0105' <= expected signature
b'd912092e392973aca3d8bece3838262b862fca53a627460cb1c3018102224bb60ecb159b030ea4dfb1ff21601eb7c812652303915cf56312915aae58ef7b0105' <= calculated ed25519 signature

PS. slow_ed25519.py is adapted from here. If you'd suggest using something else we're all ears. :)

@reaperhulk

This comment has been minimized.

Copy link
Member

@reaperhulk reaperhulk commented Nov 21, 2019

Okay, so on my system (using Python 3.7) your demo takes:

real	0m1.753s
user	0m1.617s
sys	0m0.053s

Using https://github.com/pyca/ed25519/blob/master/ed25519.py (which is just an optimized version of djb's original Python) that drops to:

real	0m0.198s
user	0m0.168s
sys	0m0.026s

Almost 10x faster 😄

Unfortunately EC_POINT_mul actually doesn't work with ed25519 by default (the ed25519 and X25519 NIDs won't return an EC_GROUP when calling EC_GROUP_new_by_curve_name). This is probably because the EC APIs don't fit ed25519/x25519 very well, but it's unfortunate for our purposes. There may be a way to do this still using the more generic functions (e.g. EC_GROUP_new(EC_GFp_simple_method());) but I'll have to look at that later.

torproject-pusher pushed a commit to torproject/stem that referenced this issue Nov 22, 2019
Thanks to Paul ed25519 blinding is now fully two orders of magnitude faster!

  pyca/cryptography#5068

Replaced slow_ed25519.py with an optimized implementation from...

  https://github.com/pyca/ed25519/

This changes the runtime of test_blinding as follows:

  Python 2.7: 2.25s => 20 ms
  Python 3.5: 1.83s => 19 ms
@atagar

This comment has been minimized.

Copy link

@atagar atagar commented Nov 22, 2019

Wonderful, thank you Paul! Swapped us over and actually, we're seeing fully two orders of magnitude improvement...

  • Python 2.7: 2.25s => 20 ms
  • Python 3.5: 1.83s => 19 ms

From our side we're delighted to resolve this ticket if you'd like, or leave it open to track cryptography module support for blinding. Up to you. Once again, thanks for all the help!

@reaperhulk

This comment has been minimized.

Copy link
Member

@reaperhulk reaperhulk commented Nov 25, 2019

Okay I think we'll close this for now then. If and when OpenSSL makes this more accessible we may expose more -- otherwise PyNaCl supports these operations right now.

@reaperhulk reaperhulk closed this Nov 25, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.