Feb 2, 2022
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. Questions
Did you review the PR?
Concept ACK, approach ACK, tested ACK, or
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
--enable-module-schnorrsig arguments to
Why do the examples demonstrate how to obtain randomness? Is this a good
What are the recommendations for obtaining randomness on the supported
Do the examples correctly follow these recommendations?
Can you follow the examples? Is it clear how they should be generalized to a
Is there anything missing in the examples (e.g.
return value check, setting secrets to 0, etc…)?
Are the comments in the examples helpful?
Are the comments sufficient (e.g. ECDSA takes message hash, not message)?
Is it a good idea to retry (in a loop) operations that could only fail with
negligible probability (see
Is the build system correctly adjusted for the examples? Are examples
disabled by default? Does the
configure output show whether examples are
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.
What role do they play in the API?
What does it mean for a context to be “initialized for signing” and/or
“initialized for verification”?
What is the probability that
fails given a uniformly random input byte string?
Can you give an example for a 33-byte string that results in failure when
ask the user to generate a uniformly random nonce and pass it in?
What does it mean for a public key to be “X-only”? Why does the Schnorr
example (unlike ECDSA) use “X-only” keys?
takes a 32-byte message. What are two ways to use the API to sign longer
Can you give an example for a 32-byte string that results in failure when
What messages are actually exchanged (across the network) during an
execution of the
do? How does that protect against side-channel attacks?
What does the
auxiliary_rand argument to
How could an eavesdropping attacker detect whether two parties are engaging
in an ECDH protocol?
1 17:00 <glozow> #startmeeting
3 17:00 <Kaizen_Kintsugi_> Learning time!
5 17:00 <nickler> hello hello
7 17:00 <robot-dreams> hello
8 17:00 <Kaizen_Kintsugi_> I am excited for this one!
12 17:00 <michaelfolkson> hi
14 17:00 <real_or_random> hi
18 17:00 — engraving waves
20 17:01 <OliverOffing> hi!
21 17:01 <michaelfolkson> Lots of Jonas Brothers fans here I see
22 17:01 <Kaizen_Kintsugi_> lots of people here today
28 17:01 <Kaizen_Kintsugi_> damn
29 17:01 <mninja> hi all, first time, happy to be here :)
30 17:01 <glozow> shoutout to real_or_random, elichai2, nickler, jesseposner_, robot-dreams, thanks for being here
32 17:01 <glozow> and thanks nickler for being our host today, passing it onto you :)
35 17:02 <glozow> oh and sipa, sorry!
37 17: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.
38 17: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
39 17:02 <nickler> Q1: did everyone get a chance to have a look at the PR? How about a quick y/n from everyone
45 17:02 <emzy> y (tested)
48 17:02 <Kaizen_Kintsugi_> y
49 17:02 <michaelfolkson> y
53 17:03 <bitcoin1o1> y (tested on Mac)
55 17:03 <svav> yes i read the notes
57 17:03 <nickler> That's quite a lot of people , thanks everyone for showing interest in libsecp dev
58 17: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.
59 17:04 <svav> How long has libsecp been in existence?
61 17:04 <nickler> Question 1: Can you compile and run the example? Any troubles
62 17:04 <sipa> Started as a hobby project of mine in 2013.
63 17:05 <glozow> y, no troubles
64 17:05 <robot-dreams> y, compiles and runs fine
65 17: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. :-)
66 17:06 <larryruane> I was able to build the `ecdsa_example` binary, but should there be other example binaries (ecdh, schnorr)?
67 17:06 <nickler> Also important to check, does the printed output make sense? Correct exit code? etc
68 17:06 <glozow> ./configure --enable-examples --enable-module-ecdh --enable-experimental --enable-module-schnorrsig for anyone wanting to do it rn
69 17:06 <emzy> y, no troubles, worked.
70 17:06 <theStack_> y, examples compiled and ran fine on OpenBSD 7.0... after setting the right configure flags :)
71 17:06 <stickies-v> y, ran smoothly - although I was slightly surprised the builds were in root and not in ./examples/,
72 17:06 <elichai2> theStack_: Good to hear they work properly on OpenBSD :)
74 17:07 <jesseposner_> larryruane: the other examples require additional flags to be set (i.e. experimental, ecdh, echnorrsig)
75 17:07 <glozow> larryruane: there should be schnorr_example and ecdh_example in root
76 17: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
77 17:07 <larryruane> also I ran `./configure CFLAGS='-O0 -g' --enable-examples ...` so I could explore with the debugger
78 17:07 <michaelfolkson> elichai2: You want someone on Windows right? :)
79 17:08 <larryruane> glozow: thanks, now I have them
80 17:08 <jnewbery> stickies-v: I was also surprised that they binaries were built in the root directory
81 17:08 <glozow> i was also able to use gdb with the examples without modifying flags
82 17:08 <nickler> jnewbery: stickies-v: good point. not great if the root dir gets DOS'd
83 17:09 <siv2r[m]> glozow: libsecp by default set the `-g` flag during the build
84 17:09 <nickler> But ok, seems like no major troubles, good!
85 17:09 <emzy> If i'm right "make check" also runs the examples.
86 17:10 <nickler> correct, it should emzy
87 17: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
88 17:10 <bitcoin1o1> y, on mac, no problem
89 17:10 <larryruane> I love how fast everything builds (relative to bitcoin core)!
90 17:10 <theStack_> larryruane: heh, i thought the same w.r.t. compilation speed
91 17:10 <glozow> robot-dreams: ah thanks
92 17:10 <emzy> yes I got a "PASS: schnorr_example ....." from make check
93 17: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
94 17:11 <nickler> glozow: when should the host move to the next question? :D
95 17:11 <glozow> nickler: whenever they want
96 17:11 <glozow> now's probably good
97 17:11 <nickler> 3. Question 1: Can you compile and run the example? Any troubles
99 17:12 <nickler> 3. Why do the examples demonstrate how to obtain randomness? Is this a good idea?
100 17:13 <nickler> You may have seen that the examples also show how to obtain randomness from OS.
101 17:13 <nickler> But instead we could just expect a random byte string to come from *somewhere*
102 17: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
103 17:13 <michaelfolkson> Assuming the demonstration is solid yes it is a good idea. Otherwise users may obtain imperfect sources of randomness
104 17:13 <svav> Is it because generating true randomness is rather difficult?
105 17: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)
106 17:14 <nickler> I don't think it's answered in the PR history, but often the problem with crypto implementation _is_ obtaining randomness
107 17: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
108 17:14 <jimmysong> Q: Is it normal to get this warning when I configure? "configure: WARNING: unrecognized options: --enable-examples"
109 17:14 <theStack_> definitely a good idea, as without proper randomness there are some attacks possible
110 17:14 <nickler> So without that, the examples would be much less helpful
111 17:15 <larryruane> jimmysong: i did not get that warning
112 17:15 <nickler> stickies-v: often it comes down to finding the right RNG (for your OS)
113 17:15 <jnewbery> jimmysong: perhaps you need to run autogen.sh again?
114 17:15 <jimmysong> ok, let me try that
115 17:15 <larryruane> i ran `./configure CFLAGS='-O0 -g' SECP_CFLAGS='-O0 -g' --enable-examples --enable-module-ecdh --enable-experimental --enable-module-schnorrsig`
116 17:15 <jesseposner_> it's critical to get good randomness, and it's not obvious how to do it properly, and it is platform dependent
117 17:15 <emzy> jimmysong: also had no warning.
118 17:15 <engraving> nice phrasing glozow +1
119 17: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
120 17:16 <real_or_random> an interesting question is: how large is the burden of maintaining these methods? OSes change
121 17:16 <jimmysong> jnewbery: that was it. warning is now gone
122 17:17 <nickler> real_or_random: yes! that's the "Is this a good idea?" part of above question
123 17:17 <svav> In ecdh.c what does "Randomizing the context is recommended to protect against side-channel leakage" mean?
124 17: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
125 17:17 <michaelfolkson> real_or_random: How often do the sources of randomness change though? Surely extremely infrequently
126 17: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
127 17: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
128 17: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
129 17:18 <nickler> this ^
130 17:18 <michaelfolkson> I guess it depends what they use. if trivial changes to the OS could impact how the randomness is generated
131 17:19 <michaelfolkson> But that sounds like a flaw of the OS
132 17:19 <real_or_random> ok yes, but that will be a stupid change on the OS side
133 17: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?
134 17:19 <nickler> michaelfolkson: the problem is also that the OS' manpages are sometimes very confusing
136 17:20 <theStack_> jimmysong: i guess partly because the library doesn't know what a good entropy source is?
137 17:20 <elichai2> michaelfolkson: and that some functions that are now OK are not ok in old versions of the OS (e.g. `arc4random`)
138 17:20 <real_or_random> (where I argue we should have a creation function that takes randomness as input)
139 17: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?
141 17:21 <real_or_random> lightlike: yes, it has. that's the reason why secp256k1 does not have a randomness generation function
142 17:21 <michaelfolkson> elichai2: So secp requires newer versions of those particular OSes?
143 17:21 <michaelfolkson> Warnings?
144 17:21 <nickler> Q4 and Q5 are very relevant for reviewing the PR.
145 17:21 <nickler> What are the recommendations for obtaining randomness on the supported operating systems? Do the examples correctly follow these recommendations?
146 17: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
147 17: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)
148 17: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?
149 17: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)
150 17:23 <larryruane> I think it's good that the library doesn't generate randomness (internally)
151 17: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?
152 17:23 <stickies-v> It looks like fill_random only partially follows recommendations, in that it doesn't implement the suggested fallbacks?
153 17: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)
154 17:24 <engraving> Why should the Core repo house the randomness algos? Is that the ideal location?
157 17:25 <larryruane> stickies-v: well the fallbacks are determined at code-writing time (not at runtime), right?
158 17:25 <jimmysong> real_or_random: okay, that's good to know. I'll be adding that...
159 17:25 <sipa> jimmysong: Roughly, more blinding is better. How much is very hard to quantify.
160 17:25 <nickler> stickies-v: what do you mean exactly?
161 17:25 <sipa> Note that randomization is only needed for side-channel resistance.
162 17:26 <real_or_random> jesseposner: I think the Core method collects entropy from a lot of sources and is pretty sophisticated
164 17:26 <real_or_random> jesseposner: maybe it's a good idea to refer to it at least, not sure
165 17: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.
166 17:27 <jimmysong> sipa: got it. you can never be too paranoid.
167 17: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?
168 17: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)?
169 17: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
170 17:28 <stickies-v> I'm not suggesting anything - that's just how I interpreted the documentation
171 17:28 <larryruane> stickies-v: hmm, well you can't determine if `getrandom(2)` is available at runtime, right? that's compile-time
172 17:28 <sipa> Yeah, it'd need #ifdef's etc.
173 17:28 <sipa> Or configure mechanisms to determine what exists etc.
174 17:29 <siv2r[m]> Is there any specific reason why getrandom() is used for Linux whereas getentropy() is used for macOS? availability issues?
175 17:29 <siv2r[m]> The GNU C library manual says this:
176 17:29 <siv2r[m]> Most applications should use getentropy. The getrandom function is intended for low-level applications which need additional control over blocking behavior.
181 17: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 :)
182 17:30 <jesseposner> dhruv: Thanks!
183 17: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)
184 17:31 <sipa> siv2r: That's certainly good to know. I don't think I was aware getentropy even existed in linux/glibc
185 17:31 <michaelfolkson> ccccccvkvigvgnibjgfgclrnklbuigknldjtjvvdehin
186 17:31 <nickler> bless you
187 17:31 <sipa> Are you ok, michaelfolkson?
188 17:31 <michaelfolkson> Oops sorry unintended entropy
189 17:32 <robot-dreams> He is just demonstrating the proper way to generate entropy
192 17:32 <nickler> Time to move to the actual examples?
193 17:32 <nickler> 6. Can you follow the examples? Is it clear how they should be generalized to a production system?
195 17: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).
196 17:32 <emzy> sipa: a clasic.
197 17:32 <larryruane> I do remember quite a while ago, moving the mouse around to generate entropy .... I'm glad that's been improved upon!
198 17:33 <engraving> TrueCrypt did that I believe
199 17:33 <dhruv> jesseposner: yeah. makes it hard to generalize/document for other library users.
200 17: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
204 17:33 <michaelfolkson> larryruane: Bitaddress too for generating seed
205 17: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)
206 17: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
207 17:34 <robot-dreams> glozow: Interesting to see the `memory_cleanse` call / implementation in the bitcoin core version
208 17: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
209 17:36 <siv2r[m]> elichai2: sure, I have also mentioned this on GitHub, just in case
210 17: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?
212 17:37 <glozow> scary to think that the memset could be optimized out 😱
213 17:38 <leffw> Hi, I'm new here!
214 17:38 <glozow> leffw: welcome!
215 17: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
216 17:38 <michaelfolkson> You don't want to move all hash functions to libsecp from Core presumably
217 17:38 <jimmysong> michaelfolkson: from the PR, I think it's to reduce dependencies? specifically a hashing library.
218 17:38 <b10c> agree that the examples are clear
219 17:38 <robot-dreams> It also seems Core and libsecp both have separate implementations of SHA256
220 17:38 <real_or_random> glozow: yes, and even more scary that we don't have a proper "cleanse" function in secp currently ^^
221 17:39 <real_or_random> (there's an open PR that I should update)
222 17: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
223 17:39 <theStack_> (sorry for late reply)
224 17: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.
225 17:40 <nickler> Which is very related to question 7:
226 17:40 <nickler> Is there anything missing in the examples (e.g. context_randomize, ec_seckey_verify, return value check, setting secrets to 0, etc…)?
227 17:41 <engraving> glozow what does it mean for "memset to be optimized out"?
228 17:41 <larryruane> engraving: if the compiler can determine that a variable isn't being read after a write, it can discard the write
229 17:41 <michaelfolkson> Is the idea that examples will show you *all* the "safe" uses? Or just to get you started using libsecp?
230 17: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"
231 17:42 <nickler> theStack_: I mean arc4 just sounds too scary to be used really...
233 17: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: https://godbolt.org/z/WeMfon6jh
234 17:42 <engraving> ohhhh compiler optimization -- I didn't realize.
235 17:42 <elichai2> engraving: if you want to look for more information on this, this optimization is called "dead store elimination"
236 17: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
237 17:43 <nickler> jnewbery: yup, do you know if Core does the same for ECDSA?
239 17:44 <sipa> jnewbery: Bitcoin Core also does that, since recently.
240 17:44 <real_or_random> jesseposner: there's no sha256 in the public API
241 17: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
243 17:44 <jesseposner> real_or_random: ah
244 17:44 <nickler> theStack_: haha
245 17:44 <sipa> ha, a backronym
246 17:45 <theStack_> TIL from the man pages :D
247 17:45 <real_or_random> jesseposner: we should add new ECDSA signing function that hashes the message
248 17:45 <larryruane> glozow: and that's probably not a performance-critical path, since we don't sign stuff that often, right?
249 17:45 <sipa> real_or_random: Once, or twice?
250 17:45 <engraving> thanks real_or_random Familiar with compilers breaking code's operating assumptions +1, grabbed this talk right before the link -- thanks!
251 17:45 <sipa> (Bitcoin's use of ECDSA uses double-SHA256)
252 17:45 <real_or_random> sipa: we should add it once :P
253 17:46 <sipa> real_or_random: Then my question is: for whom?
254 17:46 <Kaizen_Kintsugi_> noob question: what is exaclty this context? it looks like it is doing something to allocate memory?
255 17:46 <real_or_random> yeah, indeed, I don't know
256 17: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
257 17:46 <Kaizen_Kintsugi_> as in secp256k1_context
258 17:47 <siv2r[m]> nickler: the verification step happens for ECDSA too on the core
260 17: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.
261 17: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?
262 17:47 <nickler> siv2r[m]: thx
263 17:47 <Kaizen_Kintsugi_> sipa: thanks
264 17: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.
265 17:48 <Kaizen_Kintsugi_> randomization state = nonce that people refer to above?
266 17:48 <robot-dreams> Slightly different from the nonce
267 17:48 <Kaizen_Kintsugi_> ah
268 17:49 <glozow> sipa: so would `secp256k1_ecmult_gen_context`have precomputed multiplication tables?
269 17:50 <robot-dreams> The "randomization state" is a way to scramble your arithmetic operations to protect against side channel attacks that larryruane referenced
270 17:50 <sipa> The randomization state is for side-channel protection. It isn't observable/
271 17:50 <sipa> It helps blind intermediary values that are used, which are eventually cancelled out at the end.
272 17: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)
273 17:50 <Kaizen_Kintsugi_> crazy. Damn I have a lot to learn
274 17:51 <real_or_random> now `secp256k1_ecmult_gen_context`only holds the blinding data sipa is talking about
275 17:51 <glozow> real_or_random: i see, thanks
277 17:51 <sipa> is the table
278 17:51 <sipa> for signing
279 17:51 <sipa> verification has an even bigger one
281 17:52 <jimmysong> sipa: the precomputation is essentially some multiple of G, correct?
282 17: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
283 17: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)
284 17:53 <sipa> jimmysong: That's correct, but kind of vacuously so... literally every point is a multiple of G ;)
285 17:54 <sipa> But indeed, they are lots of specific precomputed multiples of G.
286 17:54 <nickler> jesseposner: correct, with emphasis on negligible. So nothing will happen if you forget to seckey_verify for randomly generated keys
287 17: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...).
289 17:55 <Kaizen_Kintsugi_> sipa: omg yes
290 17:55 <glozow> jesseposner: nickler: ooh can we do Q3 in further questions?
291 17: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
292 17:55 <robot-dreams> sipa: I'd be very interested in ecmult session(s), can also host if no one else wants to
293 17:55 <jimmysong> the optimizations with the 8-bit words thing is insane
294 17:56 <nickler> glozow: ok!
295 17:56 <nickler> What is the probability that ec_seckey_verify fails given a uniformly random input byte string?
296 17:56 <robot-dreams> An intermediate interesting question IMO is, "what would cause it to fail"
297 17: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
298 17: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?
299 17:57 <glozow> nickler: i got an answer but i'm not sure if it's right
300 17:57 <glozow> it's = Probability(key > secp256k1 order) yes?
301 17:57 <glozow> and order is FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
302 17:57 <glozow> does that mean the chance is (0xFF - 0xEB) / 2^33 ?
303 17: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)
304 17: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
305 17:57 <siv2r[m]> This comes around 1/2^128. This does not seem small when compared with 1/2^256
306 17:57 <sipa> 2^-128 is our security target.
307 17:58 <glozow> oh it's 1/2^128?
308 17:58 <sipa> Anything below that is considered infeasible.
309 17:58 <robot-dreams> glozow: Your reasoning looks reasonable but the calculated chance looks kind of large
310 17:58 <sipa> With ~2^128 operations, an attacker can compute the private key to a given public key already.
311 17:58 <stickies-v> the key also isn't allowed to be 0 iirc?
312 17:58 <real_or_random> extra question: what's the number of particles in the universe?
313 17:58 <nickler> stickies-v: correct
314 17:59 <elichai2> real_or_random: *observable universe ;)
315 18:00 <nickler> I think around 1/2^128 is a sufficiently close answer
316 18:00 <nickler> Ok, we're out of time, but I think we touched on the remaining questions
317 18:00 <siv2r[m]> oh, so this security target (2^-128) will become smaller and smaller as tech advances?
318 18:00 <Kaizen_Kintsugi_> Thanks nickler!
319 18:00 — glozow cries in exponential
320 18:01 <nickler> (or they're about build systems which isn't terribly exciting :D)
321 18:01 <sipa> The cryptography that Bitcoin uses assumes a 2^128 security level.
322 18:01 <Kaizen_Kintsugi_> This was a busy one wow
323 18:01 <jules23> 2^265 atoms in observable universe?
324 18:01 <nickler> thanks everyone for participating.
325 18:01 <theStack_> thanks for hosting nickler!
326 18:01 <glozow> thanks nickler!
327 18:01 <sipa> Which is assumed to be infeasible for attackers for the forseeable - but not unlimited - future.
328 18:01 <emzy> Thank you nickler, glozow, real_or_random, elichai2, nickler, jesseposner_, robot-dreams, sipa and all.
329 18:01 <bitcoin1o1> thanks, nickler
331 18:01 <Kaizen_Kintsugi_> jules: its a lot smaller
332 18:01 <effexzi> Thanks!
334 18: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.
335 18:01 <stickies-v> thank you for hosting nickler and elichai2 for the PR!
336 18:01 <jnewbery> thanks nickler! That was fascinating
337 18:01 <svav> Thanks all
338 18:01 <nickler> If you have any questions feel free to stop by #secp256k1
339 18:01 <jesseposner> Thanks!
340 18:01 <tarun> thank you nickler
341 18:01 <larryruane> thanks nickler and everyone else!!
342 18:02 <siv2r[m]> Thanks everyone!
343 18:02 <nickler> I have to go now, bye!
344 18:02 <michaelfolkson> Thanks nickler!
346 18:02 <jules23> Kaizen_Kintsugi_ : quick look up on wolframalpha
347 18:02 <elichai2> Thanks nickler!
348 18:02 <robot-dreams> Thanks nickler!
350 18:02 <jules23> thanks
351 18:02 <Kaizen_Kintsugi_> oh thx for the correction
352 18:02 <glozow> #endmeeting
354 18: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
355 18: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 :)
356 18:04 <engraving> thank you so much elichai2
359 18:05 <glozow> next week is CPFP fee-bumping in packages
360 18: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.
361 18:06 <robot-dreams> michaelfolkson: You mean you didn't cut out 2048 little pieces of paper and draw them out of a hat?
363 18:06 <engraving> sipa blinding of what specifically?
364 18:06 <sipa> engraving: introducing randomness into the algorithm early on in a way that gets cancelled out at the end
365 18:07 <michaelfolkson> Maybe Jimmy's book will have a Schnorr and MuSig section one day :)
367 18:08 — engraving twists a towel, untwists a towel
368 18: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.
369 18:08 <engraving> yeah
370 18: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
371 18:11 <michaelfolkson> And obviously entropy generator beware. Don't want anyone losing funds. Unbiased dice are fine though
372 18:12 <sipa> Because it is very cool, I need to mention Von Neumann debiasing here.
373 18:12 <engraving> yeah
374 18:12 <engraving> was just about to say that
375 18:12 <sipa> You can produce perfectly unbiased entropy using biased dice/coins.
376 18:12 <engraving> assuming the bias remains between flips
377 18:13 <sipa> Right, it assumes that every coin toss / die roll is an independent sample from the same distribution.