Libsecp256k1 #748 Add usage examples (math and cryptography)

Host: jonasnick  -  PR author: elichai


  • libsecp256k1 is the library that Bitcoin Core uses for low-level cryptographic operations such as signing and verification.

  • This PR adds usage examples for several common use cases: ECDSA signatures, Schnorr signatures, and (elliptic curve) Diffie-Hellman key exchange. There are no existing usage examples in the library.

  • The examples are intended to clarify the API by supplementing the documentation in the various header files.


  1. Did you review the PR? Concept ACK, approach ACK, tested ACK, or NACK?

  2. Can you compile and run the example? Note that the examples are not compiled by default. Therefore, you must run ./configure with the --enable-examples arguments. Moreover, the ECDH and Schnorr signature examples are only compiled if the modules are enabled, which is done by providing the --enable-module-ecdh and --enable-experimental --enable-module-schnorrsig arguments to ./configure.

  3. Why do the examples demonstrate how to obtain randomness? Is this a good idea?

  4. What are the recommendations for obtaining randomness on the supported operating systems?

  5. Do the examples correctly follow these recommendations?

  6. Can you follow the examples? Is it clear how they should be generalized to a production system?

  7. Is there anything missing in the examples (e.g. context_randomize, ec_seckey_verify, return value check, setting secrets to 0, etc…)?

  8. Are the comments in the examples helpful?

  9. Are the comments sufficient (e.g. ECDSA takes message hash, not message)?

  10. Is it a good idea to retry (in a loop) operations that could only fail with negligible probability (see this comment for context)?

  11. Is the build system correctly adjusted for the examples? Are examples disabled by default? Does the configure output show whether examples are enabled?

Further Questions

These questions are intended to guide deeper exploration of libsecp256k1. We may not have time to cover them in the review session, but they can help with above questions.

  1. What’s a secp256k1_context? What role do they play in the API?

  2. What does it mean for a context to be “initialized for signing” and/or “initialized for verification”?

  3. What is the probability that ec_seckey_verify fails given a uniformly random input byte string?

  4. Can you give an example for a 33-byte string that results in failure when given to ec_pubkey_parse?

  5. Why doesn’t secp256k1_schnorrsig_sign ask the user to generate a uniformly random nonce and pass it in?

  6. What does it mean for a public key to be “X-only”? Why does the Schnorr example (unlike ECDSA) use “X-only” keys?

  7. secp256k1_schnorrsig_sign takes a 32-byte message. What are two ways to use the API to sign longer messages?

  8. Can you give an example for a 32-byte string that results in failure when given to xonly_pubkey_parse?

  9. What messages are actually exchanged (across the network) during an execution of the ECDH protocol?

  10. What does “randomizing” a secp256k1_context do? How does that protect against side-channel attacks?

  11. What does the auxiliary_rand argument to secp256k1_schnorrsig_sign do?

  12. How could an eavesdropping attacker detect whether two parties are engaging in an ECDH protocol?

Meeting Log

  117:00 <glozow> #startmeeting
  217:00 <stickies-v> hi!
  317:00 <Kaizen_Kintsugi_> Learning time!
  417:00 <jimmysong> hi
  517:00 <nickler> hello hello
  617:00 <bitcoin1o1> hi
  717:00 <robot-dreams> hello
  817:00 <Kaizen_Kintsugi_> I am excited for this one!
  917:00 <jesseposner_> hi
 1017:00 <theStack_> hi
 1117:00 <MarcoFalke> hi
 1217:00 <michaelfolkson> hi
 1317:00 <elichai2> Hi
 1417:00 <real_or_random> hi
 1517:00 <effexzi> Hi
 1617:00 <svav> Hi All
 1717:00 <kalpa> hi
 1817:00 — engraving waves
 1917:00 <glozow> Hello welcome to a special edition of PR review club! we're looking at a libsecp PR today
 2017:01 <OliverOffing> hi!
 2117:01 <michaelfolkson> Lots of Jonas Brothers fans here I see
 2217:01 <Kaizen_Kintsugi_> lots of people here today
 2317:01 <brunoerg> hi
 2417:01 <ziggie> hi
 2517:01 <emzy> hi
 2617:01 <siv2r[m]> hi
 2717:01 <Clint65> howdy
 2817:01 <Kaizen_Kintsugi_> damn
 2917:01 <mninja> hi all, first time, happy to be here :)
 3017:01 <glozow> shoutout to real_or_random, elichai2, nickler, jesseposner_, robot-dreams, thanks for being here
 3117:01 <lightlike> hi
 3217:01 <glozow> and thanks nickler for being our host today, passing it onto you :)
 3317:01 <sipa> hi
 3417:02 <willcl_ark> hi
 3517:02 <glozow> oh and sipa, sorry!
 3617:02 <jnewbery> hi
 3717:02 <nickler> Ok, I volunteered to be the host this session, but this is my first time doing this so please let me know if this session is not going in the right direction.
 3817:02 <nickler> I was also reminded to mention that you don’t need to wait for the host to ask a specific question — you can just jump in at any point
 3917:02 <nickler> Q1: did everyone get a chance to have a look at the PR? How about a quick y/n from everyone
 4017:02 <MarcoFalke> n
 4117:02 <glozow> y
 4217:02 <jimmysong> y
 4317:02 <stickies-v> y
 4417:02 <effexzi> N
 4517:02 <emzy> y (tested)
 4617:02 <Praveen> N
 4717:02 <theStack_> y
 4817:02 <Kaizen_Kintsugi_> y
 4917:02 <michaelfolkson> y
 5017:02 <jnewbery> y
 5117:03 <robot-dreams> y
 5217:03 <jesseposner_> y
 5317:03 <bitcoin1o1> y (tested on Mac)
 5417:03 <larryruane> hi
 5517:03 <svav> yes i read the notes
 5617:03 <Clint65> n
 5717:03 <nickler> That's quite a lot of people , thanks everyone for showing interest in libsecp dev
 5817:04 <nickler> Perhaps you've noticed that we split the questions into two: 1) questions that are directly relevant to reviewing the PR 2) "further" questions that may help exploration of libsecp concepts We'll start with the first set of questions. Let's see how far we come.
 5917:04 <svav> How long has libsecp been in existence?
 6017:04 <siv2r[m]> y
 6117:04 <nickler> Question 1: Can you compile and run the example? Any troubles
 6217:04 <sipa> Started as a hobby project of mine in 2013.
 6317:05 <glozow> y, no troubles
 6417:05 <robot-dreams> y, compiles and runs fine
 6517:05 <jesseposner_> I was able to compile and run all the examples. At least once I read the docs and figured out all the configure flags I had to set. :-)
 6617:06 <larryruane> I was able to build the `ecdsa_example` binary, but should there be other example binaries (ecdh, schnorr)?
 6717:06 <nickler> Also important to check, does the printed output make sense? Correct exit code? etc
 6817:06 <glozow> ./configure --enable-examples --enable-module-ecdh --enable-experimental --enable-module-schnorrsig for anyone wanting to do it rn
 6917:06 <emzy> y, no troubles, worked.
 7017:06 <theStack_> y, examples compiled and ran fine on OpenBSD 7.0... after setting the right configure flags :)
 7117:06 <stickies-v> y, ran smoothly - although I was slightly surprised the builds were in root and not in ./examples/,
 7217:06 <elichai2> theStack_: Good to hear they work properly on OpenBSD :)
 7317:06 <b10c> hi
 7417:07 <jesseposner_> larryruane: the other examples require additional flags to be set (i.e. experimental, ecdh, echnorrsig)
 7517:07 <glozow> larryruane: there should be schnorr_example and ecdh_example in root
 7617:07 <nickler> larryruane: there's a suggested update to the README in the PR that would make it more clear that the modules need to be enabled
 7717:07 <larryruane> also I ran `./configure CFLAGS='-O0 -g' --enable-examples ...` so I could explore with the debugger
 7817:07 <michaelfolkson> elichai2: You want someone on Windows right? :)
 7917:08 <larryruane> glozow: thanks, now I have them
 8017:08 <jnewbery> stickies-v: I was also surprised that they binaries were built in the root directory
 8117:08 <glozow> i was also able to use gdb with the examples without modifying flags
 8217:08 <nickler> jnewbery: stickies-v: good point. not great if the root dir gets DOS'd
 8317:09 <siv2r[m]> glozow: libsecp by default set the `-g` flag during the build
 8417:09 <nickler> But ok, seems like no major troubles, good!
 8517:09 <emzy> If i'm right "make check" also runs the examples.
 8617:10 <nickler> correct, it should emzy
 8717:10 <robot-dreams> glozow: I was able to debug as well, but I did get `ecdh_example was compiled with optimization - stepping may behave oddly; variables may not be available.` so I think larryruane's `CLAGS='-O0'` is still helpful
 8817:10 <bitcoin1o1> y, on mac, no problem
 8917:10 <larryruane> I love how fast everything builds (relative to bitcoin core)!
 9017:10 <theStack_> larryruane: heh, i thought the same w.r.t. compilation speed
 9117:10 <glozow> robot-dreams: ah thanks
 9217:10 <emzy> yes I got a "PASS: schnorr_example ....." from make check
 9317:11 <real_or_random> robot-dreams: but then you need CFLAGS='-O0 -g'. We only have -g in our *default* CFLAGS but if the user sets CFLAGS they have the last word
 9417:11 <nickler> glozow: when should the host move to the next question? :D
 9517:11 <glozow> nickler: whenever they want
 9617:11 <glozow> now's probably good
 9717:11 <nickler> 3. Question 1: Can you compile and run the example? Any troubles
 9817:11 <nickler> wait
 9917:12 <nickler> 3. Why do the examples demonstrate how to obtain randomness? Is this a good idea?
10017:13 <nickler> You may have seen that the examples also show how to obtain randomness from OS.
10117:13 <nickler> But instead we could just expect a random byte string to come from *somewhere*
10217:13 <larryruane> Doesn't the library enable the user to provide the randomness? (Not built into the library) ... hence it's good to show the user the best ways to do it
10317:13 <michaelfolkson> Assuming the demonstration is solid yes it is a good idea. Otherwise users may obtain imperfect sources of randomness
10417:13 <svav> Is it because generating true randomness is rather difficult?
10517:14 <stickies-v> if e.g. nonce generation is not truly random, it can be trivial for an attacker to derive your private key. A lot of RNGs are not truly random, because of bad implementation or because of different requirements (e.g. speed > security)
10617:14 <nickler> I don't think it's answered in the PR history, but often the problem with crypto implementation _is_ obtaining randomness
10717:14 <glozow> security of these schemes relies on the assumption that keys, nonces, salts, etc. are secret and/or uniformly distributed, so it makes sense to call attention to it
10817:14 <jimmysong> Q: Is it normal to get this warning when I configure? "configure: WARNING: unrecognized options: --enable-examples"
10917:14 <theStack_> definitely a good idea, as without proper randomness there are some attacks possible
11017:14 <nickler> So without that, the examples would be much less helpful
11117:15 <larryruane> jimmysong: i did not get that warning
11217:15 <nickler> stickies-v: often it comes down to finding the right RNG (for your OS)
11317:15 <jnewbery> jimmysong: perhaps you need to run again?
11417:15 <jimmysong> ok, let me try that
11517:15 <larryruane> i ran `./configure CFLAGS='-O0 -g' SECP_CFLAGS='-O0 -g' --enable-examples --enable-module-ecdh --enable-experimental --enable-module-schnorrsig`
11617:15 <jesseposner_> it's critical to get good randomness, and it's not obvious how to do it properly, and it is platform dependent
11717:15 <emzy> jimmysong: also had no warning.
11817:15 <engraving> nice phrasing glozow +1
11917:15 <siv2r[m]> a good PRNG is required to avoid cryptographic attack ig. Ex: if schnorrsig use a LCG random generator we can derive the private key since, the nonces will be linearly related
12017:16 <real_or_random> an interesting question is: how large is the burden of maintaining these methods? OSes change
12117:16 <jimmysong> jnewbery: that was it. warning is now gone
12217:17 <nickler> real_or_random: yes! that's the "Is this a good idea?" part of above question
12317:17 <svav> In ecdh.c what does "Randomizing the context is recommended to protect against side-channel leakage" mean?
12417:17 <glozow> The recommendation can become outdated if a vulnerability is found, the library is no longer maintained, etc. so it's nice that there's a warning message there
12517:17 <michaelfolkson> real_or_random: How often do the sources of randomness change though? Surely extremely infrequently
12617:17 <nickler> svav: that's not specific to ecdh but also in the other files. you can read more about it in include/secp256k1.h
12717:18 <jnewbery> perhaps that comment at the top of the file should actually be split up and put inline inside the fill_random() function, so if the OSs change or another is added, there's only one place that needs to be changed
12817:18 <real_or_random> michaelfolkson: yeah, it's hopefully much better now... it took quite some time in linux for example to provide a good API
12917:18 <nickler> this ^
13017:18 <michaelfolkson> I guess it depends what they use. if trivial changes to the OS could impact how the randomness is generated
13117:19 <michaelfolkson> But that sounds like a flaw of the OS
13217:19 <real_or_random> ok yes, but that will be a stupid change on the OS side
13317:19 <jimmysong> so question about the context randomization, how come it's a separate call instead of it being done for you as part of the context creation?
13417:19 <nickler> michaelfolkson: the problem is also that the OS' manpages are sometimes very confusing
13517:19 <real_or_random> jimmysong: that's a good question. there's some discussion in
13617:20 <theStack_> jimmysong: i guess partly because the library doesn't know what a good entropy source is?
13717:20 <elichai2> michaelfolkson: and that some functions that are now OK are not ok in old versions of the OS (e.g. `arc4random`)
13817:20 <real_or_random> (where I argue we should have a creation function that takes randomness as input)
13917:20 <lightlike> doesn't bitcoin core have some more elaborate algorithm for gathering entropy/randomess than just using the OS syscall, combining randomness from multiple sources?
14017:21 <sipa> yes
14117:21 <real_or_random> lightlike: yes, it has. that's the reason why secp256k1 does not have a randomness generation function
14217:21 <michaelfolkson> elichai2: So secp requires newer versions of those particular OSes?
14317:21 <michaelfolkson> Warnings?
14417:21 <nickler> Q4 and Q5 are very relevant for reviewing the PR.
14517:21 <nickler> What are the recommendations for obtaining randomness on the supported operating systems? Do the examples correctly follow these recommendations?
14617:22 <real_or_random> it's a litte strange: for bitcoin core as the main user of secp26k1, it does not matter. core has its functions and they work. the examples are intended for other users
14717:22 <real_or_random> (the strange part is that this is a crypto library which is "bring your own randomness" and this is the part where a lot of people screw up)
14817:23 <jesseposner> but if core has a superior method, should that method be documented so other users of the library can follow a similar pattern?
14917:23 <elichai2> michaelfolkson: Notice that secp currently doesn't generate randomness anywhere, it expects the user to provide random strings. This is just in the examples. (but it could be argued that libsecp should maintain a "getrandom" function)
15017:23 <larryruane> I think it's good that the library doesn't generate randomness (internally)
15117:23 <jimmysong> real_or_random: so trying to clear up something from the discussion. Are we supposed to call the context_randomize function before each new signing?
15217:23 <stickies-v> It looks like fill_random only partially follows recommendations, in that it doesn't implement the suggested fallbacks?
15317:24 <real_or_random> jimmysong: yes, it will make signing more secure by adding side-channel protection. (though that does not mean that signing is insecure if you don't do it)
15417:24 <engraving> Why should the Core repo house the randomness algos? Is that the ideal location?
15517:24 <theStack_> as for obtaining randomness on OpenBSD, i think arc4random(3) should be preferred over getentropy(2), at least that's what the man pages suggest (see also
15617:25 <glozow> Q4 relevant code is here i think the examples use the `fill_random` function which is defined using preprocessor directives, depending on the operating system
15717:25 <larryruane> stickies-v: well the fallbacks are determined at code-writing time (not at runtime), right?
15817:25 <jimmysong> real_or_random: okay, that's good to know. I'll be adding that...
15917:25 <sipa> jimmysong: Roughly, more blinding is better. How much is very hard to quantify.
16017:25 <nickler> stickies-v: what do you mean exactly?
16117:25 <sipa> Note that randomization is only needed for side-channel resistance.
16217:26 <real_or_random> jesseposner: I think the Core method collects entropy from a lot of sources and is pretty sophisticated
16317:26 <nickler> theStack_: did you see this comment?
16417:26 <real_or_random> jesseposner: maybe it's a good idea to refer to it at least, not sure
16517:27 <jesseposner> real_or_random: makes sense. I'm not familiar with the Core method so not sure how practical it is for other users to implement.
16617:27 <jimmysong> sipa: got it. you can never be too paranoid.
16717:27 <stickies-v> larryruane nickler the inline documentation in fill_random states that "/* If `getrandom(2)` is not available you should fallback to /dev/urandom */", but then it doesn't actually fallback?
16817:27 <robot-dreams> stickies-v: Are you suggesting that `fill_random` should also try to read from `/dev/urandom` (or whatever the OS-specific fallback is)?
16917:27 <elichai2> stickies-v: you're right. `random.h` only contains "best practice" random generation. it doesn't contain any fallbacks for older machines, as that will require a lot more effort
17017:28 <stickies-v> I'm not suggesting anything - that's just how I interpreted the documentation
17117:28 <larryruane> stickies-v: hmm, well you can't determine if `getrandom(2)` is available at runtime, right? that's compile-time
17217:28 <sipa> Yeah, it'd need #ifdef's etc.
17317:28 <sipa> Or configure mechanisms to determine what exists etc.
17417:29 <siv2r[m]> Is there any specific reason why getrandom() is used for Linux whereas getentropy() is used for macOS? availability issues?
17517:29 <siv2r[m]> The GNU C library manual says this:
17617:29 <siv2r[m]> Most applications should use getentropy. The getrandom function is intended for low-level applications which need additional control over blocking behavior.
17717:29 <siv2r[m]>
17817:29 <larryruane> here's a good article on side-channel attacks
17917:29 <sipa> Here is Bitcoin Core's code for getting randomness from the OS:
18017:29 <dhruv> jesseposner: Here's an example of core harvesting entropy from an inbound p2p message
18117:30 <elichai2> stickies-v: At the top of `random.h` it states that the file only contains best practices. But it's probably not clear enough, so please comment a suggestion :)
18217:30 <jesseposner> dhruv: Thanks!
18317:30 <real_or_random> one issue with these man pages is that sometimes they're wrong, too. for example the linux manpage was suggesting /dev/random over /dev/urandom for a while (fixed now)
18417:31 <sipa> siv2r: That's certainly good to know. I don't think I was aware getentropy even existed in linux/glibc
18517:31 <michaelfolkson> ccccccvkvigvgnibjgfgclrnklbuigknldjtjvvdehin
18617:31 <nickler> bless you
18717:31 <sipa> Are you ok, michaelfolkson?
18817:31 <michaelfolkson> Oops sorry unintended entropy
18917:32 <robot-dreams> He is just demonstrating the proper way to generate entropy
19017:32 <kalpa> lol
19117:32 <jaonoctus> oof
19217:32 <nickler> Time to move to the actual examples?
19317:32 <nickler> 6. Can you follow the examples? Is it clear how they should be generalized to a production system?
19417:32 <sipa>
19517:32 <jesseposner> dhruv: That's a good example of entropy sources that wouldn't necessarily be applicable to other applications (the time and checksum of a p2p message).
19617:32 <emzy> sipa: a clasic.
19717:32 <larryruane> I do remember quite a while ago, moving the mouse around to generate entropy .... I'm glad that's been improved upon!
19817:33 <engraving> TrueCrypt did that I believe
19917:33 <dhruv> jesseposner: yeah. makes it hard to generalize/document for other library users.
20017:33 <glozow> for this question it was really fun to look at src/key.cpp and src/pubkey.cpp and compare with the usage in bitcoin core
20117:33 <glozow> e.g. `CKey::SignSchnorr`
20217:33 <glozow> and `CKey::Sign`
20317:33 <jimmysong> larryruane: still does that
20417:33 <michaelfolkson> larryruane: Bitaddress too for generating seed
20517:34 <stickies-v> nickler yeah I found the examples very straightforward to follow (disclaimer - only did ecdsa.h but they all seem very similarly structured)
20617:34 <elichai2> siv2r[m]: I think there's a reason I didn't use getentropy but I can't remember it (been almost 2 years haha), I'll recheck later and respond to your comment
20717:34 <robot-dreams> glozow: Interesting to see the `memory_cleanse` call / implementation in the bitcoin core version
20817:36 <robot-dreams> nickler: The examples seem quite clear to me; they don't include (1) hashing the message or (2) exchanging public keys over a network (ECDH) but I think those are straightforward for a reader to infer from context
20917:36 <siv2r[m]> elichai2: sure, I have also mentioned this on GitHub, just in case
21017:36 <michaelfolkson> I think was discussed before we started but why don't they include hashing the message? Replication of code between Core and libsecp?
21117:37 <glozow> robot-dreams: indeed!
21217:37 <glozow> scary to think that the memset could be optimized out 😱
21317:38 <leffw> Hi, I'm new here!
21417:38 <glozow> leffw: welcome!
21517:38 <robot-dreams> michaelfolkson: I'm guessing it's because we don't want to (1) take a dependency on a cryptography library, or (2) add a SHA256 implementation to the example code
21617:38 <michaelfolkson> You don't want to move all hash functions to libsecp from Core presumably
21717:38 <jimmysong> michaelfolkson: from the PR, I think it's to reduce dependencies? specifically a hashing library.
21817:38 <b10c> agree that the examples are clear
21917:38 <robot-dreams> It also seems Core and libsecp both have separate implementations of SHA256
22017:38 <real_or_random> glozow: yes, and even more scary that we don't have a proper "cleanse" function in secp currently ^^
22117:39 <real_or_random> (there's an open PR that I should update)
22217:39 <theStack_> nickler: (re: arc4random vs getentropy on OpenBSD) yes i did. I'd rather assume that the mentioned projects are not following best practices. OTOH i don't think getentropy() is wrong either
22317:39 <theStack_> (sorry for late reply)
22417:39 <nickler> compared to the Core code it seems like the Schnorr examples do not specifically mention that the sig should be verified before giving it to the verifier.
22517:40 <nickler> Which is very related to question 7:
22617:40 <nickler> Is there anything missing in the examples (e.g. context_randomize, ec_seckey_verify, return value check, setting secrets to 0, etc…)?
22717:41 <engraving> glozow what does it mean for "memset to be optimized out"?
22817:41 <larryruane> engraving: if the compiler can determine that a variable isn't being read after a write, it can discard the write
22917:41 <michaelfolkson> Is the idea that examples will show you *all* the "safe" uses? Or just to get you started using libsecp?
23017:41 <glozow> engraving: i imagine that a compiler says "oh, you're setting this memory to 0 and then forgetting about it, there's no need to set it to 0"
23117:42 <nickler> theStack_: I mean arc4 just sounds too scary to be used really...
23217:42 <jnewbery> nickler: good point about verifying the signature after signing. There's a recommendation in BIP340 to do that:
23317:42 <robot-dreams> engraving: here's a specific example where it gets optimized out. Note that in the assembly version, there is no `memset` call:
23417:42 <engraving> ohhhh compiler optimization -- I didn't realize.
23517:42 <elichai2> engraving: if you want to look for more information on this, this optimization is called "dead store elimination"
23617:43 <jesseposner> calling secp256k1_sha256 from within the ecdsa example could be useful for documentation purposes, and it would also help emphasize the hashing requirement which can be a footgun
23717:43 <nickler> jnewbery: yup, do you know if Core does the same for ECDSA?
23817:43 <real_or_random> engraving:
23917:44 <sipa> jnewbery: Bitcoin Core also does that, since recently.
24017:44 <real_or_random> jesseposner: there's no sha256 in the public API
24117:44 <theStack_> nickler: i think RC4 hasn't been used internally since OpenBSD 5.5. Nowadays arc4random doesn't have anything to do with RC4 anymore, it's a mnemonic for "A Replacement Call For Random" :D
24217:44 <glozow> yeah
24317:44 <jesseposner> real_or_random: ah
24417:44 <nickler> theStack_: haha
24517:44 <sipa> ha, a backronym
24617:45 <theStack_> TIL from the man pages :D
24717:45 <real_or_random> jesseposner: we should add new ECDSA signing function that hashes the message
24817:45 <larryruane> glozow: and that's probably not a performance-critical path, since we don't sign stuff that often, right?
24917:45 <sipa> real_or_random: Once, or twice?
25017:45 <engraving> thanks real_or_random Familiar with compilers breaking code's operating assumptions +1, grabbed this talk right before the link -- thanks!
25117:45 <sipa> (Bitcoin's use of ECDSA uses double-SHA256)
25217:45 <real_or_random> sipa: we should add it once :P
25317:46 <sipa> real_or_random: Then my question is: for whom?
25417:46 <Kaizen_Kintsugi_> noob question: what is exaclty this context? it looks like it is doing something to allocate memory?
25517:46 <real_or_random> yeah, indeed, I don't know
25617:46 <glozow> larryruane: i imagine it's more important to sanity-check that your signature is correct than try to save time. and yeah we don't sign nearly as often as we verify
25717:46 <Kaizen_Kintsugi_> as in secp256k1_context
25817:47 <siv2r[m]> nickler: the verification step happens for ECDSA too on the core
25917:47 <siv2r[m]>
26017:47 <sipa> Kaizen_Kintsugi_: It used to hold a lot of precomputed tables to accelerate signing/verification, but since recently all those tables are now built-in to the binary at compile time.
26117:47 <nickler> Ok perhaps a few sub questions: 1) what can happen if you don't check return value? 2) don't call seckey_verify 3) forget context_randomize?
26217:47 <nickler> siv2r[m]: thx
26317:47 <Kaizen_Kintsugi_> sipa: thanks
26417:47 <sipa> So right now the context doesn't hold that much anymore; it holds randomization state as well as callbacks for errors, if you want to use that feature.
26517:48 <Kaizen_Kintsugi_> randomization state = nonce that people refer to above?
26617:48 <robot-dreams> Slightly different from the nonce
26717:48 <Kaizen_Kintsugi_> ah
26817:49 <glozow> sipa: so would `secp256k1_ecmult_gen_context`have precomputed multiplication tables?
26917:50 <robot-dreams> The "randomization state" is a way to scramble your arithmetic operations to protect against side channel attacks that larryruane referenced
27017:50 <sipa> The randomization state is for side-channel protection. It isn't observable/
27117:50 <sipa> It helps blind intermediary values that are used, which are eventually cancelled out at the end.
27217:50 <real_or_random> glozow: until recently, this struct had tables, yes and they would be created on context creation. now the tables are precomputed at build time (or actually in the repo)
27317:50 <Kaizen_Kintsugi_> crazy. Damn I have a lot to learn
27417:51 <real_or_random> now `secp256k1_ecmult_gen_context`only holds the blinding data sipa is talking about
27517:51 <glozow> real_or_random: i see, thanks
27617:51 <sipa>
27717:51 <sipa> is the table
27817:51 <sipa> for signing
27917:51 <sipa> verification has an even bigger one
28017:52 <sipa>
28117:52 <jimmysong> sipa: the precomputation is essentially some multiple of G, correct?
28217:53 <glozow> was looking for those multiplication tables and couldn't find them. thought i'd see some magic like the minisketch linear transformation tables
28317:53 <jesseposner> nickler: if you don't call seckey_verify, then you risk, with negligible probability, that the secret key is invalid because not all 256 bit numbers are valid secp256k1 keys (because valid secret keys are limited to scalars within the cyclical subgroup of the generator)
28417:53 <sipa> jimmysong: That's correct, but kind of vacuously so... literally every point is a multiple of G ;)
28517:54 <sipa> But indeed, they are lots of specific precomputed multiples of G.
28617:54 <nickler> jesseposner: correct, with emphasis on negligible. So nothing will happen if you forget to seckey_verify for randomly generated keys
28717:54 <sipa> If people are interested in what EC multiplication algorithms are actually used, we should do a separate review club on that (or probably several...).
28817:55 <jules23> +1
28917:55 <Kaizen_Kintsugi_> sipa: omg yes
29017:55 <glozow> jesseposner: nickler: ooh can we do Q3 in further questions?
29117:55 <nickler> and the answer to sub-question 2) above is perhaps obvious, you won't actually verify a signature in the worst case, ouch
29217:55 <robot-dreams> sipa: I'd be very interested in ecmult session(s), can also host if no one else wants to
29317:55 <jimmysong> the optimizations with the 8-bit words thing is insane
29417:56 <nickler> glozow: ok!
29517:56 <nickler> What is the probability that ec_seckey_verify fails given a uniformly random input byte string?
29617:56 <robot-dreams> An intermediate interesting question IMO is, "what would cause it to fail"
29717:56 <engraving> a bit off topic so ignore if need be: are we aware of active attempts of side channel attacks or are the precautions merely cause we know they have/can be done and so our implementations must use anti-side channel designs
29817:56 <theStack_> i noticed that on the schnorr example, seckey_verify is not called. i guess this is just to save an extra call, since keypair_create checks whether the private key is valid anyways?
29917:57 <glozow> nickler: i got an answer but i'm not sure if it's right
30017:57 <glozow> it's = Probability(key > secp256k1 order) yes?
30117:57 <glozow> and order is FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
30217:57 <glozow> does that mean the chance is (0xFF - 0xEB) / 2^33 ?
30317:57 <robot-dreams> engraving: I'm also curious about this question, e.g. what's a canonical scenario people have in mind when thinking about side channel (e.g. maybe a hardware wallet running secp256k1 code, an attacker stole it)
30417:57 <siv2r[m]> jesseposner: nickler: in what order is this neglible probablity in? I tried calculating it like (p-n)/2^256. Here, p = field size and n = group order
30517:57 <siv2r[m]> This comes around 1/2^128. This does not seem small when compared with 1/2^256
30617:57 <sipa> 2^-128 is our security target.
30717:58 <glozow> oh it's 1/2^128?
30817:58 <sipa> Anything below that is considered infeasible.
30917:58 <robot-dreams> glozow: Your reasoning looks reasonable but the calculated chance looks kind of large
31017:58 <sipa> With ~2^128 operations, an attacker can compute the private key to a given public key already.
31117:58 <stickies-v> the key also isn't allowed to be 0 iirc?
31217:58 <real_or_random> extra question: what's the number of particles in the universe?
31317:58 <nickler> stickies-v: correct
31417:59 <elichai2> real_or_random: *observable universe ;)
31518:00 <nickler> I think around 1/2^128 is a sufficiently close answer
31618:00 <nickler> Ok, we're out of time, but I think we touched on the remaining questions
31718:00 <siv2r[m]> oh, so this security target (2^-128) will become smaller and smaller as tech advances?
31818:00 <Kaizen_Kintsugi_> Thanks nickler!
31918:00 — glozow cries in exponential
32018:01 <nickler> (or they're about build systems which isn't terribly exciting :D)
32118:01 <sipa> The cryptography that Bitcoin uses assumes a 2^128 security level.
32218:01 <Kaizen_Kintsugi_> This was a busy one wow
32318:01 <jules23> 2^265 atoms  in observable universe?
32418:01 <nickler> thanks everyone for participating.
32518:01 <theStack_> thanks for hosting nickler!
32618:01 <glozow> thanks nickler!
32718:01 <sipa> Which is assumed to be infeasible for attackers for the forseeable - but not unlimited - future.
32818:01 <emzy> Thank you nickler, glozow, real_or_random, elichai2, nickler, jesseposner_, robot-dreams, sipa and all.
32918:01 <bitcoin1o1> thanks, nickler
33018:01 <nickler> If you have more appetite for examples, we have a musig example here:
33118:01 <Kaizen_Kintsugi_> jules: its a lot smaller
33218:01 <effexzi> Thanks!
33318:01 <ziggie> thanks
33418:01 <nickler> Of course, the libsecp repo has many more open PRs! Some of them only require a bit of context to review. If you enjoyed today's session perhaps that's something for you.
33518:01 <stickies-v> thank you for hosting nickler and elichai2 for the PR!
33618:01 <jnewbery> thanks nickler! That was fascinating
33718:01 <svav> Thanks all
33818:01 <nickler> If you have any questions feel free to stop by #secp256k1
33918:01 <jesseposner> Thanks!
34018:01 <tarun> thank you nickler
34118:01 <larryruane> thanks nickler and everyone else!!
34218:02 <siv2r[m]> Thanks everyone!
34318:02 <nickler> I have to go now, bye!
34418:02 <michaelfolkson> Thanks nickler!
34518:02 <b10c> Thanks!
34618:02 <jules23> Kaizen_Kintsugi_ : quick look up on wolframalpha
34718:02 <elichai2> Thanks nickler!
34818:02 <robot-dreams> Thanks nickler!
34918:02 <docallag> ty
35018:02 <jules23> thanks
35118:02 <Kaizen_Kintsugi_> oh thx for the correction
35218:02 <glozow> #endmeeting
35318:03 <engraving> robot-dreams are some interesting side channel attacks
35418:04 <engraving> obviously attackers aren't going to telegraph they're about to attack you but thought I'd float the question if anyone had seen any interesting attacks
35518:04 <elichai2> Please feel free to reask any question that wasn't unanswered (there were so many observations and questions it was hard to follow haha) in the PR itself, in #secp256k1 or in private if you prefer :)
35618:04 <engraving> thank you so much elichai2
35718:04 <glozow> very lively chat today, hope to see some of you again! please take a look at the upcoming meetings:
35818:05 <michaelfolkson> A couple more shills. This tweet thread was great on different ways of generating entropy
35918:05 <glozow> next week is CPFP fee-bumping in packages
36018:05 <sipa> engraving: So libsecp256k1 (on major platforms) should be completely free of timing attacks (all operations on secret data are constant time, have memory accesses and code paths that do not depend on secrets). For things like power leaks we rely on blinding.
36118:06 <robot-dreams> michaelfolkson: You mean you didn't cut out 2048 little pieces of paper and draw them out of a hat?
36218:06 <michaelfolkson> Plus jimmysong's book Programming Bitcoin is great if you need to learn from scratch about ECDSA signing etc
36318:06 <engraving> sipa blinding of what specifically?
36418:06 <sipa> engraving: introducing randomness into the algorithm early on in a way that gets cancelled out at the end
36518:07 <michaelfolkson> Maybe Jimmy's book will have a Schnorr and MuSig section one day :)
36618:08 <jesseposner> +1 to Jimmy's book. Also, this blog series is good for an elliptic curve crypto intro:
36718:08 — engraving twists a towel, untwists a towel
36818:08 <sipa> I shouldn't say we rely on blinding. libsecp256k1 (or probably, any pure-software system) cannot guarantee any protection against DPA or things like that, because who knows what an attacker can do if they can observe intermediary values in your CPU. Still, we use blinding for some best-effort to make it harder.
36918:08 <engraving> yeah
37018:09 <michaelfolkson> robot-dreams: I haven't used radioactive decay unfortunately. The Coldcard dice look cool. My entropy generation has been decidedly vanilla thus far
37118:11 <michaelfolkson> And obviously entropy generator beware. Don't want anyone losing funds. Unbiased dice are fine though
37218:12 <sipa> Because it is very cool, I need to mention Von Neumann debiasing here.
37318:12 <engraving> yeah
37418:12 <engraving> was just about to say that
37518:12 <sipa> You can produce perfectly unbiased entropy using biased dice/coins.
37618:12 <engraving> assuming the bias remains between flips
37718:13 <sipa> Right, it assumes that every coin toss / die roll is an independent sample from the same distribution.