1 2013-08-10 20:36:11 <nsh> gmaxwell, is this relevant to bitcoin: http://www.daemonology.net/blog/2013-08-10-the-factoring-cryptopocalypse.html
2 2013-08-10 20:36:20 <nsh> --
3 2013-08-10 20:36:22 <nsh> e no reason to panic. If you want to switch over to using Elliptic curves, go ahead; but my earlier remarks still apply there: Because ECC is more complex than RSA, it's easier to make implementation errors and/or introduce side channels. I would add one extra caveat however: If you do decide to use ECC, do it over a prime field. While I've never been fond of ECC over small-characterstic (aka. binary) fields, this latest attack provides all the more reason t
4 2013-08-10 20:36:22 <nsh> o be cautious about them: It's the inherent "structure" which makes them scary, and the work of Joux et al. just reinforces that such structure can be exploited.
5 2013-08-10 20:36:22 <nsh> When should we worry? If there's any hint of this work being extended to apply to prime fields. The discrete logarithm problem over prime fields is very closely related to the problem of integer factorization ??? there's a long history of improvements in one translating directly to improvements in the other. (In fact, I'd say DLP over prime fields is more closely related to factoring than it is to DLP over small-characteristic fields.) In the mean time, I se
6 2013-08-10 20:36:24 <nsh> -- ibid.
7 2013-08-10 20:36:33 <gmaxwell> We do not use a characteristic two field.
8 2013-08-10 20:36:38 <gmaxwell> We use a prime field.
9 2013-08-10 20:36:41 <nsh> right
10 2013-08-10 20:36:42 <nsh> thanks
11 2013-08-10 20:36:49 <gmaxwell> This is also what saves us from most ECC patents too.
12 2013-08-10 20:36:55 <nsh> gotcha
13 2013-08-10 20:37:31 <gmaxwell> Though even that.. meh, DLP on highly composite fields (e.g. ones with many 'prime') points has been insecure for a long time. I'm not even especially worried about characteristic 2 fields.
14 2013-08-10 20:37:53 <nsh> why's that?
15 2013-08-10 20:38:08 <nsh> ACTION prepares for whooshing noises above his head
16 2013-08-10 20:38:57 <gmaxwell> Becuase none of the fast techniques are especially fast unless you have _many_ factor bases. e.g. you only get the major sub exponential times as the number of prime points tends to infinity. But we'll see.
17 2013-08-10 20:39:32 <gmaxwell> I'm more annoyed by all the applications which are not space and computation constrained (e.g. things like GPG, not bitcoin) that don't belt-and-suspenders their ECC.
18 2013-08-10 20:39:37 <gmaxwell> E.g. PGP
19 2013-08-10 20:40:13 <gmaxwell> 's ECC support is limited to, at most, using the NIST 521 bit field.
20 2013-08-10 20:41:02 <gmaxwell> Vs it could do everything using both the NIST 521 bit and a P1024 random field, and still have keys much smaller than 2048 bit RSA. I'd feel much safer with that.
21 2013-08-10 20:41:38 <gmaxwell> When you know your crypto is almost certantly sub-exponential it makes sense to be double paranoid.
22 2013-08-10 20:41:38 <nsh> what would the overhead-factor be for doing that double security?
23 2013-08-10 20:41:48 <nsh> that makes sense
24 2013-08-10 20:42:24 <nsh> ACTION muses
25 2013-08-10 20:42:29 <gmaxwell> nsh: just the time and size of the extra keys. If it used point compression adding an extra P1024 point would just add ~1024 bits to every key and encrypted message... and be perhaps 4x slower.
26 2013-08-10 20:42:48 <gmaxwell> but, for GPG, who gives a hoot? it could be 50x slower without the user noticing.
27 2013-08-10 20:43:04 <nsh> right, message composition is already orders longer than encryption
28 2013-08-10 20:43:10 <nsh> and email isn't expected to be instantaneous
29 2013-08-10 20:44:02 <sipa> it would add 2048 to signatures
30 2013-08-10 20:44:05 <nsh> so just by adding a point to the existing curve that doesn't follow the same relationship, you increase the security by that degree?
31 2013-08-10 20:44:12 <sipa> and 1024 to keys
32 2013-08-10 20:44:30 <gmaxwell> sipa: indeed.
33 2013-08-10 20:44:45 <gmaxwell> We know this is viable in any case, since 4096 bit RSA is now considered a recommended practice.
34 2013-08-10 20:44:55 <sipa> nsh: i believe gmaxwell is talking about a completely unrelated field/curve/gemerator
35 2013-08-10 20:45:22 <sipa> let's do 4096 bit ECC :p
36 2013-08-10 20:45:33 <gmaxwell> Right, I'd make it an unrelated field. That would be part of the point. It's _possible_ for there to be field specific weaknesses and precomputation attacks.
37 2013-08-10 20:45:33 <nsh> hmm, ok
38 2013-08-10 20:46:24 <gmaxwell> sipa: at some point I'd rather have more curves than a bigger one. Once the curve is big enough that you're _well_ beyond even any speculative attack, having a seperate field to close of field specific attacks/optimizations is probably better.
39 2013-08-10 20:46:57 <sipa> right, agree
40 2013-08-10 20:47:26 <sipa> and 521 bit, if unbroken, provides the sa,me security as 256-bit symmtretic crypto
41 2013-08-10 20:47:45 <sipa> so there shouldn't be any reason to go higher unless QC
42 2013-08-10 20:47:53 <gmaxwell> Or alternatively, for something like GPG I could instead suggest lattice based + ecc, except the key sizes...
43 2013-08-10 21:28:49 <phantomcircuit> gmaxwell, theoretically keysize shouldn't matter with keyservers
44 2013-08-10 21:28:58 <phantomcircuit> except well people still use shortkey ids
45 2013-08-10 21:28:59 <phantomcircuit> :/
46 2013-08-10 21:59:54 <gmaxwell> phantomcircuit: key sizes do matter, they may not matter _much_ but they still have some consequence. E.g. mailing someone needing to fetch a 4mb key (to carry its self and its signatures) would kinda suck.
47 2013-08-10 22:00:36 <gmaxwell> or if you needed 500mb of diskspace to store the keys of everyone you interacted with, or all the keys of the maintainers of your OS, etc.
48 2013-08-10 22:01:20 <Luke-Jr> ACTION coughs at bitcoin
49 2013-08-10 22:01:51 <gmaxwell> well, this is why key sizes are very important in bitcoin... but less important in GPG, though still not unimportant.
50 2013-08-10 22:32:48 <phantomcircuit> gmaxwell, im sure a lot of people would happily make that trade
51 2013-08-10 22:32:55 <phantomcircuit> but key management is still x100 more important