--- Log opened Sat Jul 31 00:00:24 2021
02:43 -!- belcher_ is now known as belcher
08:34 -!- waxwing_ is now known as waxwing
08:34 -!- waxwing [~waxwing@193.29.57.116] has quit [Changing host]
08:34 -!- waxwing [~waxwing@user/waxwing] has joined #secp256k1
12:51 < gmaxwell> https://www.reddit.com/r/Bitcoin/comments/ovcz5v/ysk_there_are_weak_keys_in_secp256k1_elliptic/ dumb thread on reddit about a dumb publication, but in case you see it.
12:51 < gmaxwell> I wish the pressures in academia weren't such that people were pressured to use nonsense to promote their work.
12:52 < gmaxwell> What the linked paper points out is that if a user picks private keys in a tiny range that the attacker is targeting, ... the attacker can crack their private keys.  But this has no relevance to the security of the scheme, since it's cryptographically unlikely for the user to select a key that the attacker is targeting.
12:53 < sipa> (just reading now) they justify it by saying the software could be backdoored to undetectably construct/use such keys
12:53 < sipa> but that's equally silly; if the attacker has such power they can do much more interesting things
12:53 < gmaxwell> Worse, if you did want to trick users into picking keys in small targeted ranges the *best* way to do that would be to convince them that they need to use some complicated non-uniform key selection.
12:54 < gmaxwell> So, essentally the paper itself creates the vulnerablity it's addressing! -- see the reddit description, suggesting 'avoiding' 'weak keys'.
12:55 < gmaxwell> There is a useful point-- pick curves with safe prime orders to avoid small multiplicative subgroups in N ... sure, why not, if you have free choice of parameters.
12:56 < gmaxwell> But it doesn't actually change the discrete log security to fail to do so.
13:09 -!- roconnor [~roconnor@host-184-164-31-32.dyn.295.ca] has joined #secp256k1
13:09 < roconnor> what are these subgroups that the reddit comments are quoting about?
13:11 < gmaxwell> Multiplication in the field of private keys.
13:11 < gmaxwell> like your private key is x mod N.
13:12 < gmaxwell> some values have lower multiplicative order than others, because the multiplictive group is order N-1 which isn't prime.
13:13 < roconnor> So the claim would be that you've reduced the effective entropy of the hashing in Schnoor because you multiply your private key by the message hash, and that subgroup could be small?
13:15 < roconnor> 2^6 * 3 * 149 * 631 * 107361793816595537 * 174723607534414371449 * 341948486974166000522343609283189
13:15 < gmaxwell> This paper is exlusively about DL security of your public key. The idea is that an attacker tricks you into selecting keys which are members of a low multiplicative order subgroup (presumably by showing you this paper to convince you that there are weak keys you need to avoid...).  Then once you've selected one of the attacker's chosen bad keys, he can find it.
13:17 < gmaxwell> Of course, thats no less true than if the attacker convinces you to use keys e.g. in the range [x,y], where sqrt(y-x) is sufficiently small.
13:18 < gmaxwell> I suppose the author might defend their work pointing out that you might be smart enough to avoid using a small range, but not smart enough to insist on uniform generation.  It just seems very circular to me, the paper is being used to justify avoiding 'weak keys', but that's exactly how I'd trick someone into using a weak key.
13:18 < roconnor> Oh ... where does that leave my "attack" where you find a message hash collision modulo 149 and transport the signature on one message to another if ... um ... you convince the target to pick a secret key of multiplicative order 149 ... ... This seems just as hard as finding the DL.
13:18 < roconnor> which I suppose the security proof shows.
13:20 < gmaxwell> Yeah.  It's basically a fancy version of saying  ... an attacker might be watching for key 239842934823948294829238239482 so you should skip that one.
13:28 < roconnor> I wonder how many known pubkeys are in any non-trivial subgroup.
13:52 < sipa> so how does the DL search actually work, if you know they are in this subgroup?
13:55 < gmaxwell> You have some points in the group with a known DL,  and you multiply your target point over and over again with a constant in the subgroup until it collides with one of your known points.
13:57 < gmaxwell> (er, well technically you'd multiply both, of course)
13:57 < gmaxwell> it's the same complexity as a known range of the same size.
14:00 < sipa> right
14:10 < gmaxwell> (and likely slower in a real implementation because you can't just add as your update operation, you have to multiply by a element of the group)
14:12 < roconnor> The supposed advantage is that you can easily filter for pubkeys that fall into these non-trivial subgroups.
14:12 < sipa> how?
14:13 < roconnor> ummm...  I thought it was a scalar mutiply ...
14:13 < roconnor> But now I see that ... of course ... we don't have full homomorphism.
14:13 < roconnor> so I guess you cannot even do that.
14:14 < roconnor> Okay, this is pretty stupid.
14:19 < sipa> ?
14:20 < roconnor> I though you could test a pubkey to see if the secert key is part of one of these multiplicative subgroups.
14:20 < roconnor> But the homomorphism between the elliptic curve and F_n is only on the additive subgroup, not the multiplicative subgroup.
14:21 < roconnor> which suggests that you cannot test the pubkey for this attribute of the secret key.
14:21 < sipa> he main power of our methods thus occurs when
14:21 < sipa> the secret key lies in a small subgroup of F∗
14:21 < sipa> p, allow-
14:21 < sipa> ing one to detect whether a given private key is weak.
14:21 < sipa> In most cases the probability that a randomly-selected
14:21 < sipa> key is weak in this sense is very low. 
14:22 < roconnor> so you can test pubkey?
14:23 < roconnor> I mean, I did get that the probablily of pubkey being in such a subgroup is extrodinalry low to begin with.
14:24 < roconnor> So I though the deal would be at least that there would be a rapid test of the pubkey.
14:24 < roconnor> But I don't see how that is even possible.
14:25 < roconnor> and without a rapid test of the pubkey, then, as noted above, this is no different than guessing the secret key might be in small range.
14:29 < gmaxwell> You can't raise points to powers, if you could then you could check the group membership by raising it to the order's power.
14:30 < sipa> that sounds like a contradiction to me?
14:31 < sipa> oh, i missed your sentence
14:31 < sipa> yes, exactly
14:31 < roconnor> not only that, but if you could raise points to powers we'd have full homomorphism and things would be ... awesome?
14:32 < roconnor> I guess you would need to be able to mulitply points.
14:32 < gmaxwell> roconnor: notice the text says you can detected if a PRIVATE KEY is in a group with low mul order. Not a public key.
14:32 < roconnor> which would imply raising points to powers.
14:33 < sipa> given an oracle that can square points (w.r.t a fixed generator), can you break CDH?
14:33 < roconnor> gmaxwell: I see that now.  So stupid.
14:33 < gmaxwell> if you look down at the summary they basically repeat the sentimate: That this is like an attacker who puts your key in a range, EXCEPT you can't check for that because you don't know the attacker's range.
14:34 < gmaxwell> But they might as well have written a paper about detecting attackers that put keys in the range [H("Greg is AWESOME"),H("Greg is AWESOME")+2^128].
14:35 < gmaxwell> Which is why I was saying that I think the only thing this paper accomplishes is creating a pretext to ship vulnerable code. E.g. code that "avoids" weak keys by making sure your key is weak.
14:35 < sipa> roconnor: if you want to compute A*B/G (= abG), and have a P->P^2/G oracle f, you can compute A*B/G as (f(A+B)-f(A)-f(B))/2
14:35 < sipa> thus, if you have an exponentiation oracle, you can implement a multiplication oracle
15:49 < roconnor> nice.
17:13 -!- belcher_ [~belcher@user/belcher] has joined #secp256k1
17:17 -!- belcher [~belcher@user/belcher] has quit [Ping timeout: 256 seconds]
19:23 -!- roconnor [~roconnor@host-184-164-31-32.dyn.295.ca] has quit [Quit: Konversation terminated!]
--- Log closed Sun Aug 01 00:00:25 2021