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
ddustin has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
DeanGuss has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 259 seconds]
booyah_ has quit [Read error: Connection reset by peer]
booyah_ has joined #bitcoin-wizards
booyah_ has quit [Read error: Connection reset by peer]
booyah_ has joined #bitcoin-wizards
DeanGuss has quit [Ping timeout: 256 seconds]
thomasan_ has joined #bitcoin-wizards
<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
tromp has joined #bitcoin-wizards
thomasan_ has quit [Remote host closed the connection]
thomasan_ has joined #bitcoin-wizards
<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"
tromp has quit [Ping timeout: 244 seconds]
<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)
booyah_ is now known as booyah
ddustin has quit [Remote host closed the connection]
thomasan_ has quit [Ping timeout: 264 seconds]
<sipa>
but because of those unconventional choices, harder to integrate into other things
<sipa>
booyah: how is bitcoin a user?
ddustin has joined #bitcoin-wizards
<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
<sipa>
but then impose a burden on wallet implementations etc to make sure they get bip32 etc right
<gmaxwell>
which, publish schemes for bip32 have been broken and insecure because even people thinking carefully manage to get it wrong.
<gmaxwell>
it's just a hazard.
<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.
thomasan_ has joined #bitcoin-wizards
pinheadmz has quit [Quit: pinheadmz]
<booyah>
gmaxwell: ensuring that DH private key k is (k%8)==0 is trivial, are there other pitfals?
<sipa>
booyah: but it's not just DH
<sipa>
this is a test, and transformation, you need to take into account in every EC operation you do in any protocol
mn3monic has quit [Ping timeout: 250 seconds]
<sipa>
like, go look at the bugs monero had
davec has quit [Ping timeout: 268 seconds]
mn3monic has joined #bitcoin-wizards
thomasan_ has quit [Ping timeout: 250 seconds]
<sipa>
booyah: for DH, it's relatively simple - for signatures too, if you take certain things into account
<sipa>
but for anything else the burden is thinking through exactly what to take into account
davec has joined #bitcoin-wizards
<booyah>
ok so that fact with k%8 makes it harder to build more clever ideas on top of that curve?
<sipa>
yup
<booyah>
this site makes assertion that secp256k1 is "not safe" in few categories, while ed25519 is according to them - https://safecurves.cr.yp.to/
<sipa>
the site is also created by the authors of ed25519 :)
<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>
of course
<booyah>
they refused to update it?
<sipa>
their only claim is that the naive implementation is less likely to be constant time in secp256k1
<sipa>
it's not about any specific implementation
<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
<sipa>
but there are other types of pitfalls that apply when implementing ed25519
<gmaxwell>
or even the same, ones.
<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.
<gmaxwell>
and no amount of different tradeoffs can make an implementer competent.
<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?
<sipa>
booyah: it's pure C89 if you want
ddustin has quit [Remote host closed the connection]
<sipa>
booyah: the asm optimizations are optional
<booyah>
sipa: the version free of timing attacks etc is C89?
<gmaxwell>
of course.
<sipa>
yes
<booyah>
hmm how it assures that compiler will not make some parts not constant time
<sipa>
by making reasonable assumptions about compiler intelligence... and manual verification
<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.
<gmaxwell>
Though thats a pretty obscure example.
<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)
IGHOR has joined #bitcoin-wizards
<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>
different use cases require different priorities
<booyah>
gmaxwell: need to pick a lib tho
<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.
<sipa>
ha
<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>
for DH ed25519 isn't used but the related 'curve25519' is used.
thomasan_ has joined #bitcoin-wizards
<gmaxwell>
And curve25519 allows for a particularly elegant DH implementation.
<booyah>
gmaxwell: isn't x25519 different construct but same mathemathical curve
<sipa>
ed25519 and curve25519 are different, but isomorphic curves
<gmaxwell>
booyah: it's an isomorphic curve, the coordinates are different.
<sipa>
i'm not sure about x25519
<gmaxwell>
So you can't reuse the same code.
<booyah>
ok. and secp256k1 for DH?
<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.
thomasan_ has quit [Remote host closed the connection]
<booyah>
do you know if performance in DH is also basically the same for both?
<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>
Though not by a huge margin, also performance depends a lot on implementation tradeoffs.
<gmaxwell>
e.g. how much memory, how much code written in asm, etc.
<gmaxwell>
of course there is another axis to consider, many parties are now recommending using curves larger thatn 256 bits...
<booyah>
hmm really? are 256's in danger on classical computers?
<sipa>
see curve448 for example
<gmaxwell>
Not as far as anyone knows.
<booyah>
does bitcoin considers?
<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>
in bitcoin the tradeoffs are pretty darn atypical.
<booyah>
what_if.jpg that was the reason for idea of segwit2x
<gmaxwell>
doesn't make sense, since of course no one proposed such a thing.
<booyah>
:)
<booyah>
speaking of QC, how about NTru signatures? or them + normal secp ones. they are small..
<gmaxwell>
they're not small.. key plus signature are about the size of a winternitz hash based signature.
<gmaxwell>
(about 2kb)
<gmaxwell>
(also not clear which ntru scheme you mean, the earlier signature algo was broken...)
AaronvanW has quit [Ping timeout: 244 seconds]
<booyah>
I though they fixed it, with the exception that it shouldn't be reused too many times
thomasan_ has quit [Remote host closed the connection]
<JackH>
do we know what BIP is being enforced on the network at the moment?
<JackH>
if its even a BIP
thomasan_ has joined #bitcoin-wizards
DeanGuss has quit [Ping timeout: 256 seconds]
<sipa>
JackH: no
AaronvanW has quit [Ping timeout: 268 seconds]
thomasan_ has quit [Remote host closed the connection]
thomasan_ has joined #bitcoin-wizards
thomasan_ has quit [Remote host closed the connection]
thomasan_ has joined #bitcoin-wizards
<JackH>
maybe its yet another BIP to enforce another BIP like last time :D
thomasan_ has quit [Ping timeout: 252 seconds]
thomasan_ has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
<booyah>
a general question, if it's ok here - why are EC point operations (add, mul) defined this way, why they have this results?
<sipa>
"because it works" (tm)
<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>
the only thing that matters is the group structure
<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?
AaronvanW has quit [Ping timeout: 250 seconds]
<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
<booyah>
(though some particullary bad rules might result in for example lessen security etc)
<sipa>
oh this has nothing to do with security
<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>
it doesn't matter what that group actually is
thomasan_ has quit [Remote host closed the connection]
<sipa>
(and the fact that DL is hard in some groups is an assumption, not something we can derive)
thomasan_ has joined #bitcoin-wizards
<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
<booyah>
are there any evidences for DL being hard, besides that no one yet had any idea for it?
<sipa>
it's not just nobody has any idea
<nsh>
the absence of a break
<sipa>
there are plenty of ideas, and in some cases, breaks that apply to DL
<sipa>
but we pick the security parameter (size of the group) high enough that none of these are feasible
thomasan_ has quit [Remote host closed the connection]
<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
thomasan_ has joined #bitcoin-wizards
<booyah>
sipa: you mean, as in normal DSA/RSA ?
<sipa>
yes, DSA
<sipa>
RSA is based on a completely different assumption
<sipa>
(not discrete logarithm based)
<sipa>
so there is no equivalent of RSA applied to EC groups, for example
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
<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?
<waxwing>
heh "EC curves" .. i did one of those.
thomasan_ has quit [Remote host closed the connection]
<sipa>
error correction curves? :p
<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" :)
<waxwing>
RH?
<sipa>
RH?
<waxwing>
riemann hypothesis
Murch has quit [Quit: Snoozing.]
<sipa>
well as far as groups go, it feels like EC groups are the most erratic ones
<sipa>
(where erratic means lack of structure, i guess)
<sipa>
as the best solving algorithm for DL on them does not use any EC properties, just generic group operations
<sipa>
(apart from some constant factors)
<waxwing>
right, no factorization i guess is the reason?
<waxwing>
anyway not having some nonexistence result (of some cheaty- fast algo) seems a bit suboptimal.
son0p has joined #bitcoin-wizards
thomasan_ has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
thomasan_ has quit [Remote host closed the connection]
AaronvanW has quit [Ping timeout: 250 seconds]
thomasan_ has joined #bitcoin-wizards
elichai2 has joined #bitcoin-wizards
spinza has quit [Quit: Coyote finally caught up with me...]
thomasan_ has quit [Remote host closed the connection]
thomasan_ has joined #bitcoin-wizards
nephyrin has quit [Ping timeout: 268 seconds]
* nsh
smiles
thomasan_ has quit [Remote host closed the connection]
thomasan_ has joined #bitcoin-wizards
nephyrin has joined #bitcoin-wizards
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
thomasan_ has quit [Remote host closed the connection]
spinza has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
shesek`` has joined #bitcoin-wizards
michaels_ has quit [Remote host closed the connection]
Noldorin has joined #bitcoin-wizards
thomasan_ has joined #bitcoin-wizards
michaels_ has joined #bitcoin-wizards
thomasan_ has quit [Remote host closed the connection]
michaels_ has quit [Ping timeout: 246 seconds]
stiell has quit [Ping timeout: 245 seconds]
son0p has quit [Remote host closed the connection]