03:20 UTC

< February 2019 > Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

- Console
- #amber
- #arm-graphics
- #arm-netbook
- #bitcoin-wizards
- #bundler
- #cinch
- #coiniumserv
- #coiniumserv-dev
- #crystal-lang
- #cubieboard
- #datamapper
- #discferret
- #elliottcable
- #etnaviv
- #forth
- #glasgow
- #gridcoin
- #gridcoin-dev
- #homecmos
- #huawei-g300
- #imx6-dev
- #imx6-dongle
- #ipfs
- #jruby
- #libreelec
- #libreoffice-ru
- #lima
- #linux-amlogic
- #linux-exynos
- #linux-rockchip
- #linux-sunxi
- #lisp
- #litex
- #logarion
- #maglev-ruby
- #microrb
- #milkymist
- #mirage
- #mutant
- #nanoc
- #neo900
- #nextbsd
- #nmigen
- #ocaml
- #opal
- ##openfpga
- #panfrost
- #Paws
- #Paws.Nucleus
- #picolisp
- #ponylang
- #prjmistral
- #pypy
- #qaul.net
- #qi-hardware
- #racket
- #radxa
- #reasonml
- #rom-rb
- #rubinius
- #ruby
- #ruby-core
- #rubygems
- #rubygems-aws
- #rubygems-trust
- #ruby-lang
- #ruby-rdf
- #sandstorm
- #scopehal
- #skywater-pdk
- #slime
- #soletta
- #solvespace
- #stellar
- #stellar-dev
- #symbiflow
- #systemtap
- #teamhacksung
- #teamhacksung-support
- #tinyqma
- #trilema
- #wallaroo
- #xiki
- #xtompp
- ##yamahasynths
- #yosys
- #zig

sipa changed the topic of #bitcoin-wizards to: This channel is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja

<booyah_>
would there be any benefits for bitcoin to use ed25519 instead secp256k1? even if not enough to switch (probably not a good idea) but just to compare them

<booyah_>
gmaxwell: so the problem with cofactors in ed25519 is this one? - "Curve25519, which has a cofactor of 8. Such curves require some extra care in the protocol that uses them. For instance, when doing a Diffie-Hellman key exchange over Curve25519, the Diffie-Hellman private keys must be chosen as multiples of 8 (which is expressed as: "set the three least significant bits to zero"); this ensures that the points will be in the proper subgroup"

<sipa>
booyah_: yes, the curve has points (87.5% of them, to be exact) which do not belong to the subgroup used in cryptographic applications

<booyah_>
I assume any proper library implementing ed25519 would take care to do that, so that would be a bit harder for library creator, but not for user like bitcoin?

<sipa>
it's a rather unconventional construction as far as elliptic curve crypto goes - the designers took care to make sure all unusual parts about it were fine for the specific purpose of ECDH (for curve255) and signatures (for ed25519)

<sipa>
you could propose a softfork to introduce opcodes that do ed25519 validation in bitcoin... the cost would be introduction of a ed25519 implementation in bitcoin's consensus rules

<gmaxwell>
which, publish schemes for bip32 have been broken and insecure because even people thinking carefully manage to get it wrong.

<gmaxwell>
Which verges into kind of absurd considering that the primary marketing point for it is that its 'safer'-- but that claim just turns out to not be all that true in practice.

<gmaxwell>
Basically, there is no replacement for doing things right. ed25519 is structually somewhat safer against some kinds of misimplementation, but substantially weaker against others. In practice, I think the tradeoff has shown itself not to be a good one.

<sipa>
this is a test, and transformation, you need to take into account in every EC operation you do in any protocol

<sipa>
booyah: for DH, it's relatively simple - for signatures too, if you take certain things into account

<booyah>
this site makes assertion that secp256k1 is "not safe" in few categories, while ed25519 is according to them - https://safecurves.cr.yp.to/

<booyah>
and allaged by them problems with secp are: ECDLP/disc , ECC/ladder, ECC/complete, ECC/ind, as we see in that longer table there

<sipa>
there is nothing wrong with the properties they highlight of course - but many of them are very minor issues

<booyah>
I guess this problems, are timing attacks etc, that are fixed in current implementation of secp256k1 as used in bitcoin?

<sipa>
their only claim is that the naive implementation is less likely to be constant time in secp256k1

<sipa>
but nobody in their right mind should ever use a naive implementation for any production use anyway

<sipa>
and they're right - you need to take a bunch of pitfalls into account when implementing secp256k1

<gmaxwell>
e.g. the ed25519 implementation that you got for years when you googled python ed25519 used double and add -- grossly non-constant time.

<gmaxwell>
basically their argument is that it's easier to make a constant time implementation. But implementing it is not a question of ease, it's a question of gross incompetence or not.

<booyah>
sipa: how portable is current Bitcoin's implemenation of secp256k1? should work on any OS right? but needs asm which limits avability of cpu architectures?

<gmaxwell>
there are ed25519 implementations are not completely free of timing attacks... because timing attacks are a property of the implementation, not the curve.

<gmaxwell>
Unfortunately, there is no replacement for actually measuring the specific usage. E.g. some older arm cores the mul instruction takes a data dependant amount of time. libsecp256k1 isn't constant time on that hardware, and nor is any of the published ed25519 code that I'm aware of.

<booyah>
seems secp256k1 is quite nice then. should it be promoted to be used by other projects in place of ed25519, for projects that might plan on doing more advanced crypto?

<gmaxwell>
(also, libsecp256k1 has blinding, so even if the constant timeness failed, there is still some protection... I've not seen any ed25519 implementation do this, though they could, though its probably made more complicated by cofactor)

<booyah>
if it is in fact same/better then would be nice to have user base (always better), while seems everoune rather goes with sodium (and ed25519 there)

<gmaxwell>
booyah: maybe? projects shouldn't just be picking raw cryptographic primitives. The security depends on the whole system

<sipa>
e.g. safecurves also promotes having an elligator construction available... but that inherently requires a cofactor

<sipa>
if you don't need elligator (mapping of curve points to uniform strings), that's a pretty weird tradeoff

<gmaxwell>
sipa: well safecurves erroniously believes that there is no constant time value to point or point to value construction.

<gmaxwell>
booyah: the point I'm making is that sodium doesn't do those 'advanced' things either, so it's not like you can used that.

<booyah>
ok so for signatures (ECDSA), both curves are fine; for more complex stuff ed25519 is error prone to do right. and for DH?

<gmaxwell>
it doesn't have ring signatures of any form, multisigning, blind signing, threshold signing, PAKE of any form, or ZKPs of any form except a plain digital signature.

<gmaxwell>
It's fine. There is a different but morally similar optimization for DH for secp256k1. We don't currently bother to use it, though there is a pull request for it.

<gmaxwell>
If all you ever cared about was DH, and you don't care to use the not yet patent expired optimizations for secp256k1, I think the edge goes to curve25519.

<gmaxwell>
of course there is another axis to consider, many parties are now recommending using curves larger thatn 256 bits...

<gmaxwell>
But for most applications the computation/communications cost of a ~500 bit curve aren't a problem. And varrious parties think that larger curves will be substantially stronger against quantum computers.

<gmaxwell>
they're not small.. key plus signature are about the size of a winternitz hash based signature.

<booyah>
a general question, if it's ok here - why are EC point operations (add, mul) defined this way, why they have this results?

<booyah>
someone just told me that it has practical meaning such that A+B=C the point C represents angle equal to sum of angles of A and B. but why is that? is it that way for all additions on 2d fields?

<sipa>
someone noticed that if you pick that particular definition for "addition" on an elliptic curve, the resulting set satsify the definitions of a group

<booyah>
sipa: so it could be any rule as long as long as the defined operators obey some laws like A+B = B+A, A*O = something and so on?

<sipa>
yes, A+B must be equal to B+A, (A+B)+C must be equal to A+(B+C), there is a 0 such that A+0 and 0+A == A, and every element A has an inverse -A such that A + (-A) = 0

<sipa>
security comes from the fact that people have tried and failed to solve the discrete logarithm problem for EC groups

<sipa>
but ECDSA, Schnorr, ring signatures, bulletproofs, ... all just need a abelian prime-ordered group in which the DL problem is hard

<sipa>
with a slightly stronger assumption (namely that if you're given (P,aP,bP) you can't compute abP), you can do DH key negotiation

<sipa>
but we pick the security parameter (size of the group) high enough that none of these are feasible

<sipa>
booyah: note that the definition of EC multiplication is just repeated application of the group operation (which for EC is called point addition)

<sipa>
but for example you can also use multiplication of integers modulo certain big primes as group operation; the equivalent of EC multiplication then becomes exponentiation modulo that prime

<waxwing>
booyah, part of the reason EC curves are the way they are is that's the only way you can get a group operation out of an algebraic curve - choose two points on a cubic and there is a unique third cut through the line defined on them (except when there isn't any at all).

<waxwing>
so if groups are defined by operations on pairs of points resulting in a third point in the group (that's kinda the idea of a group), it wouldn't work e.g. with a second order equation.

<waxwing>
also on that last point, i've always wondered whether at some deeper level, assumptions like the hardness of factoring/RSA aren't somehow related to discrete log in a prime order group like that, but it's at least above my paygrade, maybe some mathematicians have theories about that?

<sipa>
waxwing: the fact that number field sieves are the best known algorithm for solving both factoring and integer DL feels like they're related on an abstract level

<waxwing>
yes i suppose. maybe that's just another way of saying "it's really goddamn random, no joke" :)

<sipa>
as the best solving algorithm for DL on them does not use any EC properties, just generic group operations