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
michaelsdunn1 has quit [Ping timeout: 244 seconds]
thrmo_ is now known as thermostat
arubi has quit [Ping timeout: 256 seconds]
<roasbeef>
waxwing: more efficient t-of-n variants have also been published recently, main gain imo is you get the existing anon set, as we've seen with segwit the major consumer facing cos are suuuper slow w/ up take of new things, schnorr arguably is more invasive since signing+verification changes
michaelfolkson has joined #bitcoin-wizards
<waxwing>
roasbeef, and even if that wasn't true, we should advertise that it is, so that nobody knows for sure whether it's being used.
<waxwing>
more seriously though, all good points, but i'd have to wonder about the paillier part, it's a certain counterargument i guess.
thermostat is now known as thrmo
arubi has joined #bitcoin-wizards
michaelfolkson has quit [Quit: Sleep mode]
Krellan has quit [Ping timeout: 252 seconds]
tromp has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
michaelsdunn1 has joined #bitcoin-wizards
michaelsdunn1 has quit [Changing host]
michaelsdunn1 has joined #bitcoin-wizards
detoo has quit [Ping timeout: 250 seconds]
Krellan has joined #bitcoin-wizards
Murch has quit [Quit: Snoozing.]
arubi has quit [Remote host closed the connection]
arubi has joined #bitcoin-wizards
michaelsdunn1 has quit [Remote host closed the connection]
michaelsdunn1 has joined #bitcoin-wizards
Dizzle has joined #bitcoin-wizards
detoo has joined #bitcoin-wizards
michaelsdunn1 has quit [Remote host closed the connection]
michaelsdunn1 has joined #bitcoin-wizards
michaelsdunn1 has quit [Remote host closed the connection]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
instagibbs has quit [Ping timeout: 260 seconds]
AaronvanW has quit [Ping timeout: 264 seconds]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 272 seconds]
instagibbs has joined #bitcoin-wizards
Belkaar has quit [Ping timeout: 272 seconds]
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
Belkaar has joined #bitcoin-wizards
Hunger- has quit [Ping timeout: 252 seconds]
shesek has quit [Read error: No route to host]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
instagibbs has quit [Ping timeout: 252 seconds]
instagibbs has joined #bitcoin-wizards
instagibbs has quit [Quit: ZNC 1.6.3+deb1 - http://znc.in]
Krellan has quit [Remote host closed the connection]
son0p has quit [Quit: Lost terminal]
davec has quit [Quit: leaving]
rh0nj has quit [Remote host closed the connection]
rh0nj has joined #bitcoin-wizards
thomasan_ has joined #bitcoin-wizards
lukedashjr has joined #bitcoin-wizards
luke-jr has quit [Ping timeout: 252 seconds]
luke-jr has joined #bitcoin-wizards
lukedashjr has quit [Ping timeout: 268 seconds]
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
helo has quit [Remote host closed the connection]
vtnerd has quit [Ping timeout: 252 seconds]
vtnerd has joined #bitcoin-wizards
thomasan_ has quit [Ping timeout: 260 seconds]
Dizzle has quit [Remote host closed the connection]
Dizzle has joined #bitcoin-wizards
Dizzle has quit [Ping timeout: 250 seconds]
Dizzle_ has joined #bitcoin-wizards
Dizzle_ is now known as Dizzle
Dizzle has quit [Quit: Leaving...]
mn3monic has quit [Excess Flood]
mn3monic has joined #bitcoin-wizards
fabianfabian has joined #bitcoin-wizards
setpill has joined #bitcoin-wizards
laptop__ has quit [Ping timeout: 240 seconds]
tromp has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
davec has joined #bitcoin-wizards
morcos has quit [Remote host closed the connection]
morcos has joined #bitcoin-wizards
lukedashjr has joined #bitcoin-wizards
luke-jr has quit [Ping timeout: 244 seconds]
lukedashjr is now known as luke-jr
luke-jr has quit [Excess Flood]
luke-jr has joined #bitcoin-wizards
michaelfolkson has joined #bitcoin-wizards
michaelfolkson has quit [Client Quit]
spinza has quit [Quit: Coyote finally caught up with me...]
Hunger- has joined #bitcoin-wizards
spinza has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
copumpkin has quit [Read error: Connection reset by peer]
booyah_ has joined #bitcoin-wizards
drexl_ has joined #bitcoin-wizards
maaku has quit [Remote host closed the connection]
tromp_ has joined #bitcoin-wizards
booyah has quit [Read error: Connection reset by peer]
maaku has joined #bitcoin-wizards
drexl has quit [Read error: Connection reset by peer]
spinza has quit [Quit: Coyote finally caught up with me...]
spinza has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
spinza has quit [Quit: Coyote finally caught up with me...]
Murch has joined #bitcoin-wizards
setpill has quit [Ping timeout: 264 seconds]
spinza has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
kallewoof has quit [Remote host closed the connection]
Chris_Stewart_5 has joined #bitcoin-wizards
JackH has quit [Ping timeout: 260 seconds]
thrmo has quit [Remote host closed the connection]
JackH has joined #bitcoin-wizards
fabianfabian has joined #bitcoin-wizards
rh0nj has quit [Remote host closed the connection]
rh0nj has joined #bitcoin-wizards
thomasan_ has joined #bitcoin-wizards
thomasan_ has quit [Ping timeout: 250 seconds]
Chris_Stewart_5 has quit [Ping timeout: 252 seconds]
lukedashjr has joined #bitcoin-wizards
luke-jr has quit [Ping timeout: 245 seconds]
lukedashjr is now known as luke-jr
shesek has quit [Read error: No route to host]
shesek has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
nuncanada has joined #bitcoin-wizards
nuncanada has quit [Remote host closed the connection]
nuncanada has joined #bitcoin-wizards
brianhoffman has quit [Quit: brianhoffman]
brianhoffman has joined #bitcoin-wizards
instagibbs has joined #bitcoin-wizards
michaelsdunn1 has joined #bitcoin-wizards
michaelsdunn1 has quit [Changing host]
michaelsdunn1 has joined #bitcoin-wizards
Murch has quit [Quit: Snoozing.]
Murch has joined #bitcoin-wizards
Murch has quit [Client Quit]
Zenton has quit [Ping timeout: 246 seconds]
thomasan_ has joined #bitcoin-wizards
thomasan_ has quit [Ping timeout: 252 seconds]
JackH has quit [Quit: Leaving]
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
Krellan has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 246 seconds]
<dgenr8>
given a pubkey, how difficult is it to find a valid signature for a 256-bit message if you don't care what the message is?
<andytoshi>
do you care that it's a hash with a known preimage?
<andytoshi>
with schnorr it's impossible and i think this can be proven .. with ECDSA i also think it's impossible but i wouldn't bet money on that
<sipa>
i think it's easy to prove that's impossible in idealized ECDSA (where you treat extracting the X coordinate of a point as a RO)
<andytoshi>
oh, hm, maybe.. all i know is there is no "message recovery" analogous to "pubkey recovery"
<sipa>
you'd need to find (s, k, m) such that s*k = m + H(k*G)*P, given P
<sipa>
ah, no, not necessarily
<sipa>
you'd need to find (s, R, m) such that s*R = m + H(R)*P
<dgenr8>
andytoshi: no, the idea is that someone may claim it's the hash of an unknown preimage. the question is how much does weight the signature have
<sipa>
andytoshi: i think you can use the forking lemma to extract the private key even if the 2 signatures are for different messages with the same R
<sipa>
(and R has to be chosen first as it's the input to a hash function in idealized ECDSA)
<andytoshi>
yeah that sounds right
<andytoshi>
though like, if m = 0 then you can do it
<andytoshi>
so there's still something about m you have to express in your proof
<sipa>
if m=0 then it's even easier for the extractor
<sipa>
oh, wait
<andytoshi>
then your proof doesn't work, because it's trivial irl to produce such 'forgeries' :)
<sipa>
right
Chris_Stewart_5 has joined #bitcoin-wizards
AaronvanW has quit [Remote host closed the connection]
Krellan has quit [Remote host closed the connection]
AaronvanW has joined #bitcoin-wizards
tromp_ has quit [Ping timeout: 260 seconds]
rh0nj has quit [Remote host closed the connection]
<dgenr8>
this account claims to have signed a hash with the key to coinbase 9
<dgenr8>
do I understand correctly that this is trivial by choosing message=0?
<nsh>
the first thing to check is that it's not a recycled signature or m=0 aye
<dgenr8>
he he he
shesek has quit [Read error: Connection reset by peer]
tromp has joined #bitcoin-wizards
Zenton has joined #bitcoin-wizards
<waxwing>
it always amuses me to think that, to make a transferrable signature, you have to take an identification protocol (here Schnorr's), and make it non-interactive (fiat-shamir), but then if you want to use your signature protocol to prove identity, you have to put back the interactivity you took out :)
shesek has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
wizkid057 has quit [Ping timeout: 252 seconds]
<gmaxwell>
andytoshi: it's trivially possible to just go find a pretexting signature and publish it though, like scamtoshi did.
Zenton has quit [Read error: Connection reset by peer]
Zenton has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
shesek has quit [Read error: No route to host]
shesek has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
wpaulino has quit [Changing host]
wpaulino has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
laurentmt has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
shesek has quit [Read error: Connection reset by peer]
Chris_Stewart_5 has quit [Ping timeout: 252 seconds]
shesek has joined #bitcoin-wizards
enemabandit has joined #bitcoin-wizards
drolmer has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
nickstum has joined #bitcoin-wizards
shesek has quit [Read error: No route to host]
nickstum has left #bitcoin-wizards [#bitcoin-wizards]
shesek has joined #bitcoin-wizards
opdenkamp has quit [Ping timeout: 252 seconds]
shesek has quit [Read error: Connection reset by peer]
opdenkamp has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has quit [Read error: No route to host]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
thomasan_ has joined #bitcoin-wizards
satwo has joined #bitcoin-wizards
shesek has quit [Read error: No route to host]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
shesek has quit [Read error: No route to host]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
thomasan_ has quit [Ping timeout: 250 seconds]
shesek has quit [Read error: Connection reset by peer]
Krellan has joined #bitcoin-wizards
spinza has quit [Quit: Coyote finally caught up with me...]
_Sam-- has joined #bitcoin-wizards
spinza has joined #bitcoin-wizards
douglas_ has quit [Ping timeout: 252 seconds]
laurentmt has quit [Read error: Connection reset by peer]
AaronvanW has quit [Remote host closed the connection]
Chris_Stewart_5 has quit [Ping timeout: 268 seconds]
AaronvanW has joined #bitcoin-wizards
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
AaronvanW has quit [Remote host closed the connection]
AaronvanW has joined #bitcoin-wizards
michaelsdunn1 has quit [Remote host closed the connection]
AaronvanW has quit [Remote host closed the connection]
rh0nj has quit [Remote host closed the connection]
<andytoshi>
dgenr8: o.O so, gmaxwell showed me the example you posted (which appears to have been taken down) and i think this is actually a novel way to produce a fake ECDSA signature on a "hash" which is some forced 256-bit value
rh0nj has joined #bitcoin-wizards
<arubi>
andytoshi, did you see that r == -s in both signatures?
<andytoshi>
arubi: yeah, gmax pointed that out to me. it's important to the forgery
<arubi>
so I still can't figure out how to do that
<andytoshi>
the key observation is that s = -r in these signatures ... so the verification equation sR = mG + rP can be rewritten as s(R + P) = mG
<arubi>
right
<andytoshi>
so ... pick R so that R + P = cG, for some `c` that you know
<andytoshi>
then set m = c*s
<andytoshi>
so, R is forced by c, then r is forced by R, and s is forced by r... so you can't control this quantity
AaronvanW has joined #bitcoin-wizards
<arubi>
sorry I've been away for too long, I'm trying to follow this :)
<andytoshi>
heh, it's the kinda thing that's super annoying to follow on IRC
<belcher>
thanks for the explanation andytoshi
<andytoshi>
cuz it's a bunch of ascii-fied equations in a horizontal line of english text
AaronvanW has quit [Ping timeout: 240 seconds]
<arubi>
got it. thanks andytoshi. that's a really neat trick
shesek has joined #bitcoin-wizards
<arubi>
waxwing you probably will be interested too ^ :)
<andytoshi>
interestingly, the forger did not have to be so clumsy .. i wonder if s/he wanted to be noticed by using s = -r like that, because it gave a critical hint to how it was done
<nsh>
was it not required to have s = -r?
<andytoshi>
so, there's a simple variant where you make s be some multiple of -r
<drexl>
he uploaded 3 so far and then took them down
<drexl>
all have r = -s
<andytoshi>
and if you don't reveal the multiple they'll look uncorrelated
<belcher>
maybe his next tweet will do that if he's in here watching
* nsh
smiles
<gmaxwell>
They took it down instantly when I mentioned it in bitcoin-forks
<gmaxwell>
maybe coincidence.
<sipa>
you can generalize it
<sipa>
choose R = c*G + a*P, and then s = R.x/a, and m = c*R.x/a
<andytoshi>
oh, nice, that's super simple
<sipa>
which is indistinguighable from random valid signatures
<andytoshi>
and you can see why you can't control s, R or m very well
<sipa>
this attack doesn't apply to Schnorr, as m is under a hash
douglas_ has joined #bitcoin-wizards
<andytoshi>
you can solve for both `c` and `a` here ... in the twitter thing clearly `a = 1`, but `c` looks like it's just some big random number, it's not especially small or anything interesting
<andytoshi>
or ascii
<sipa>
a=-1 actually
<andytoshi>
eh, right
shesek has quit [Read error: Connection reset by peer]
shesek has joined #bitcoin-wizards
<sipa>
you can also recover a,s from the signature; a = R.x/s, c = m/s
<sipa>
eh, a and c
<sipa>
right, of course - that's the ECDSA verification equation
<andytoshi>
yeah .. a little disappointing, i was hoping there'd be something that e.g. only the actual key owner could recover
<andytoshi>
but i think i'd tried "ecdsa as encryption" some years ago and never got something that worked
<sipa>
andytoshi: that would be in contradiction with being able to use them for forgeries :p
<andytoshi>
heh, yeah, i guess so
shesek has quit [Read error: Connection reset by peer]
opdenkamp has quit [Quit: ZNC 1.6.5+deb1+deb9u1 - http://znc.in]
shesek has joined #bitcoin-wizards
Murch has joined #bitcoin-wizards
<uiuc-slack>
<smk7> If i understand correctly, the problem is because m = H(message) in ECDSA and that it could be fixed by making m = H(message || R) .
booyah_ is now known as booyah
<sipa>
smk7: well, not really - the above lets you 'forge' a signature if the attacker can choose m
<sipa>
but m in the writeup above is H(message)
<uiuc-slack>
<smk7> Ignore it. I realize the point of this entire thing was signatures are meaningless unless I provide message.
<sipa>
So the result is not technically an ECDSA signature without knowing the preimage of m