00:55:27dooglus_:dooglus_ is now known as Guest21566
00:57:12Guest21566:dht are inherently slow, i wonder how maidsafe can promise fast internet with their dht
00:59:28gmaxwell:I promise free 1lb gold bars to everyone who says gmaxwell is grand!
01:00:08gwillen:Señor gmaxwell es muy grande!
01:01:07Luke-Jr:gmaxwell is grand!
01:01:24gmaxwell:(this was a joke in response to Guest21566; all gold bars that I know of are propritary in any case… :P )
01:01:57nsh-:* nsh- leverages gmaxwell-promise-backed derivatives
01:02:19sipa:* sipa integrates those
01:02:39gwillen:* gwillen takes out CDSes on gmaxwell's gold-bar debt
01:03:36Guest21566:oh my god ripple is getting traction
01:03:54gmaxwell:haha
01:04:58Guest21566:ripple is doing it the right way
01:05:15Guest21566:compare to open transactions which idk what they are doing or thinking.
01:05:31Guest21566:very shady company
01:06:56kanzure:no ban hammers?
01:08:30Guest21566:kanzure are you developing any bitcoin related projects?
01:15:07andytoshi:kanzure: there are no banhammers here except for overt six-year-old style trolling
01:15:45andytoshi:which is unfortunate, but new people would probably not get a chance to learn otherwise ;)
01:29:53woah:Can't tell if bs or not: http://www.otonomos.com/
01:32:33Adohgg:Adohgg is now known as cholobear
02:28:46cholobear:cholobear is now known as adohgg
02:50:08berndj-blackout:berndj-blackout is now known as berndj
03:22:50fanquake:fanquake has left #bitcoin-wizards
06:00:49petertodd:gmaxwell sucks (do I get a -1lb gold bar now?)
06:01:21kanzure:petertodd: i just lost a few hours not believing your warning in https://github.com/petertodd/python-bitcoinlib/blob/master/examples/spend-p2sh-txout.py
06:01:31kanzure:petertodd: in the future i will be more trusting of your asserts i guess
06:01:45kanzure:(python3/python2 differences)
06:02:25petertodd:kanzure: haha
06:02:32kanzure:(pm)
06:02:45petertodd:I'm one of those programmers whose bought into the Python3 upgrade :)
08:05:16kornbluth.freenode.net:topic is: This channel is not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
08:05:16kornbluth.freenode.net:Users on #bitcoin-wizards: andy-logbot arubi wallet42 Guyver2 artifexd iang nuke1989 jtimon go1111111 coinheavy ericp4 koshii SDCDev [7] kmels contrapumpkin jchp spinza Logicwax c0rw1n_ melvster roconnor kanzure altoz puszl Brizo wiretapped nanotube espes__ Starduster justanotheruser andytoshi Guest72851 x48 samson_ gavinandresen MoALTz mortale Ress atgreen hashtag hollandais mkarrer rfreeman_w Adlai so zibbo Transisto drawingthesun emsid jrayhawk Hunger- irc88_
08:05:16kornbluth.freenode.net:Users on #bitcoin-wizards: devrandom nsh lnovy pi07r Emcy dansmith_btc epscy tacotime comboy Graftec grandmaster2 LarsLarsen arowser OneFixt Meeh jgarzik Fistful_of_coins BlueMatt Sangheili dgenr8 NikolaiToryzin tromp__ tromp ebfull wizkid057 a5m0 digitalmagus8 HaltingState prepost Grishnakh iddo starsoccer midnightmagic adohgg jaekwon berndj gribble Graet kinlo zenojis [Derek] Dyaheon pigeons lianj_ UukGoblin optimator BrainOverfl0w wumpus Apocalyptic poggy rs0
08:05:16kornbluth.freenode.net:Users on #bitcoin-wizards: jcorgan_ Iriez mr_burdell fluffypony K1773R bbrittain SomeoneWeird forrestv livegnik Anduck amiller Nightwolf Keefe Krellan BigBitz [\\\] Taek42 warren asoltys waxwing EasyAt sl01 Luke-Jr sipa coryfields [d__d] bobke nsh- pajarillo crescendo HM phantomcircuit gmaxwell DoctorBTC harrow roasbeef mmozeiko Eliel CodeShark throughnothing Guest47516 Alanius nickler_ ryan-c gwillen otoburb smooth helo Guest50253 abc56889 lechuga_ TD-Linux catcow
08:05:16kornbluth.freenode.net:Users on #bitcoin-wizards: danneu LaptopZZ burcin petertodd phedny @ChanServ
11:04:09nsh-:andytoshi, is the alts.pdf on wpsoftware the lastest draft?
11:19:57Luke-Jr:nsh-: likely
11:20:08nsh-:k
11:51:47maaku:maaku is now known as Guest94970
12:32:55andytoshi:nsh-: yes
12:34:24nsh-:ty
13:24:39andytoshi:gmaxwell: (all this modulo me actually working through the detailed security argument) so, we can get N-of-M with BRS ... when specifying each output, also specify either the bitmask or merkle paths which describe the additive N-of-N that you are doing (this is visible so verifiers can check the threshold is met)
13:24:54andytoshi:the key image, rather than being the image of all N keys added together, is the image of all M keys added together
13:25:03andytoshi:so you cannot double-spend by using different subsets of keys
13:26:01andytoshi:note that you can specify a different N for every output you include in the ring ... though i think for privacy you'd pretty much need them to be the same, the stats seem really complicated otherwise and i don't think you can communicate no information
13:27:03andytoshi:(in fact, rather than using the image of all M keys, we could even use a MAST root, but i can't see how this is useful..)
13:29:02andytoshi:oh, i guess it lets you have a script without enabling double-spending, and still use ringsigs for the case when your script demands a signature input. but doesn't let you blind the script
13:29:07gmaxwell:MAST doesn't help for BRS, I think— for plausability everyone must know the data in tree, so you get no data hiding savings. but the non-tree verifier addition approach should work equally.
13:48:50andytoshi:if we have weights, is that equivalent in expressivity to having boolean functions?
13:52:31gmaxwell:I think it is, but with a huge catch; the magnitude of the weights are exponential in the number of bits you're mapping over, in the worst case.
13:52:48andytoshi:i buy that
13:53:28andytoshi:i feel like we are very close to getting atomic chain swaps (and i think this implies coinswap) within BRS
13:55:12andytoshi:as i mentioned last night we can get almost-hash-commitments with tree-based N-of-M by having 2-of-2 with keys that are negatives of each other, then anyone can forge sigs once they know the pks (which are initially hidden behind a merkle root but will be exposed on first spend)
13:55:54andytoshi:this is "almost" because you can't demonstrate to anyone that this is actually a hash-commit prior to revealing the preimage
13:56:52gmaxwell:(if you didn't buy the weights comment, I would have pointed out there is a counting argument)
13:57:45andytoshi:it just seems intuitively right, if i've got a proposition p and i do A || p, seems like the weight on A would need to overwhelm the weights of p
14:02:12andytoshi:overwhelm the minimum sum of weights guaranteed to satisfy p*
14:03:09andytoshi:then there is some "no perfect compression" intuition that you usually can't compact this minimum sum past the "every additional symbol makes you double the total weights in play"
14:03:27andytoshi:which maybe is your counting argument
14:06:07gmaxwell:hm. actually plain linear weights with a threshold can't quite be universal. Go construct xor.
14:07:42andytoshi:ah, yes, you're right, only AND and OR ... this is true of ABE as well, the way they solved it was to "add NOT" by doubling the set of attributes, "{a, b, c, not a, not b, not c}" and promising never to use "a and not a" :)
14:07:55andytoshi:but in our case there is no "not key" we can use
14:08:14gmaxwell:basically the criteria amounts to linear seperability, if you imagine the satisfactions in 2^n space, you can get a linear threshold if you can fit a cutting hyperplane that precisely seperates.
14:08:51andytoshi:that's a good intuition
14:09:26gmaxwell:andytoshi: the counting argument was just that there are 2^2^n boolean functions over n inputs. so this suggested to me that the worst case weights would have be large.
14:11:35andytoshi:for hash-commit maybe there is something like, if you do 2-of-2 with keys P and 2P, then the structure of the ringsig causes the private key to be revealed when spent, but is safe before even if the pubkeys are known
14:12:59andytoshi:that doesn't work, but there's a lot of design space to explore here... note also that you can do OOB nizks of equality of discrete logs (this is roughly what the ringsigs are made of in the first place!)
14:13:55maaku:maaku is now known as Guest20473
14:14:06andytoshi:or maybe, just add a consensus rule that if you do 2-of-2 with keys P and 2P, your nonces all have to be 1 :P
14:15:52gmaxwell:okay, so polynomal thresholds of order <= n are universal... which is kinda ugly.
14:16:29andytoshi:n == # of keys
14:16:32andytoshi:?
14:16:54gmaxwell:yea.
14:17:26gmaxwell:(I mean the worst case is order = n, so an exponential blowup in the number of required weights)
14:19:01gmaxwell:I suppose I shouldn't be surprised, considering that e.g. for 256 bit hash H() does H(x)==y is not something you're going to compute with just a couple multiplies. :)
14:37:18gmaxwell:andytoshi: hmm.. though for checksig we don't want arbitary bool functions... in that it's okay for you to turn additional 1s to zeros until you get the right answer. in this case, I think an exact test (not a threshold) may be universal but I'm not sure.
14:39:07andytoshi:oh, good point
14:39:38andytoshi:i don't have a usecase in mind beyond A || (B && C), which can easily be done with weights, was just curious..
14:53:05gmaxwell:(A0 && A1 && A2 && ...) || (B0 && B1 && B2 && ...) is a fun pattern.
15:04:38nsh-:what are you guys talking about now? i'm lost
15:05:01nsh-:there's a way of computing b*coin ring (threshold) signatures using bitmasks?
15:09:48gmaxwell:nsh-: sort of two parallel but related things.
15:11:20gmaxwell:I presented a (kind of obvious) way to get a fairly efficient non-interactive N of M threshold signature out of schnorr signatures, which have a non-interactive N of N threshold signature.
15:11:43nsh-:* nsh- nods
15:12:17gmaxwell:andytoshi also determined that the same N of N scheme that works for schnorr works for the bytecoin ring signature.
15:12:37nsh-:oh, cool
15:12:45gmaxwell:and he also figured out how to make the N of M transform work without breaking the BRS.
15:12:50nsh-:so, transitively.... right
15:12:54nsh-:nice
15:13:35gmaxwell:He's trying to figure out how to do a coinswap which requires a A || (B&&C) with some special conditions.
15:13:57gmaxwell:You can get an A||(B&&C) out of a linear weighed threshold scheme.
15:14:35nsh-:A B C represent possible inputs?
15:14:52nsh-:no, signatures
15:15:28gmaxwell:yes, pubkeys/signatures... so thats a boolean expression, instead we can replace it with A*Wa + B*Wb + C*Wc >= T and set the weights to 2, 1, 1 and the threshold to 2.
15:15:59maaku:maaku is now known as Guest48704
15:16:25nsh-:hmmm
15:16:37gmaxwell:so e.g. a minor extension to a threshold scheme to have weights greatly increases the space of expressable functions.
15:17:01nsh-:* nsh- nods
15:17:13nsh-:interesting to see how these would map onto contractual/game/transactional situations
15:17:42gmaxwell:andytoshi asked if it was univeral. E.g. can you express any predicate with just the weights.
15:18:32gmaxwell:The answer is no, e.g. you cannot express xor that way. Though you can generalize it to be universal, but you may need a whole lot of weights.
15:18:57nsh-:what property of the algebra prevents the XOR logic?
15:20:12gmaxwell:for n bit input you can imagine a n dimensional space where an all the inputs are points.
15:20:35gmaxwell:The threshold scheme can be seen as defining a cutting hyperplane that seperates the points into pass/fail.
15:20:49nsh-:* nsh- nods
15:21:07gmaxwell:in the xor case, the points are colinear and there is no cutting plane that seperates them.
15:21:56nsh-:oh
15:22:07gmaxwell:for two inputs you can imagine making a decision table and drawing a line through it.
15:22:40gmaxwell:amusingly, you _can_ get a NAND that way, so a stack of linear thresholds is universal... but a single one is not.
15:23:10nsh-:. o O { i wonder if there's a 'deep' relationship between universality and geometric degeneracy and reversibility (destruction of information) }
15:24:58gmaxwell:though for predicates on signatures; we don't actually care about arbritary boolean expressions.
15:25:50nsh-:* nsh- nods
15:25:59gmaxwell:e.g. you'd never want A xor B .. because the signer can always omit some keys, so A xor B is really the same as A OR B.
15:27:11gmaxwell:and the space of these uhhh boolean sufficiency functions is much smaller than all boolean functions.
15:27:22gmaxwell:so maybe linear weights really are general for them, I dunno.
15:28:09nsh-:shades of heuristica...
15:29:21gmaxwell:pieter and I have been talking about a new checksig operator, with the goal of being schnorr based and supporting efficient non-interactive thresholds (or, at least, more efficent than checkmultisig). Linear weights are an obvious improvement to support, as they're very useful and easy. But are they universal for the kinds of functions we want? Is there some minor enhancement that makes them universal?
15:32:21gmaxwell:e.g. for two input functions having the additional two quadraic weights is universal... but thats kinda dumb since there are only 16 possible boolean functions on 2 inputs to begin with. (several of them being stupid; there are only two interesting sufficiency-functions the and and the or case)
15:32:41nsh-:* nsh- nods
15:33:08gmaxwell:presumably there is some proper name for what I'm calling sufficiency-functions and if I figure it out I'll find there is literature on it.
15:35:10nsh-:is there a way to taxonomise the 'kinds of functions we want'?
15:49:05andytoshi:one sec, i'll check the ABE paper because they have the same class of functions (and iirc they had a name..)
15:49:52andytoshi:"monotone span program"
15:50:54andytoshi:that's not quite right, a MSP is something different but the class of computable functions supported by MSP is the same as that for LSSS, which is the same as that for threshold gates
15:53:59andytoshi:s/computable/efficiently computable/
15:56:50andytoshi:the "monotone" is because as gmaxwell says, anyone can change 1's to 0's, so if you have an accepting input for some program P, you've also got an accepting input for any program that accepts subsets of P's inputs
16:03:09andytoshi:gmaxwell: schnorr n-of-n is not quite noninteractive, you have to agree on the nonce sum beforehand ... so half a round of interaction
16:04:55andytoshi:what we care about more is that the resulting sig looks identical for all n (including n = 1), and if you add the pubkeys beforehand it'll be indistinguishable from the single-signer case
16:06:58gmaxwell:andytoshi: yea, I mean no signing time interaction is required, just setup interaction.
17:21:32gmaxwell:http://en.wikipedia.org/wiki/Dedekind_number
17:26:35ahmed_ZzZz:ahmed_ZzZz is now known as ahmed_
17:32:05gmaxwell:Interesting that there are 56130437228687557907788 monotone boolean functions for n=8... well alas, seems unlikely that we'll find a compact and reasonably simple optimal encoding for them.
17:39:12sipa:gmaxwell: why restrict to monotone ones?
17:39:30sipa:right... we don't care about "but that guy is not allowed to sign!"
17:45:54andytoshi:gmaxwell: oh, i realized that my N-of-M transform is not as simple as i thought earlier
17:45:57nsh-:hmm, https://en.wikipedia.org/wiki/Antichain is interesting
17:46:53andytoshi:key image in BRS is xH(xG), i had observed that you can replace xG with the sum of all M pks, but there is still that pesky first `x` which is the sum of only N keys
17:47:22nsh-:gmaxwell, sure 56130437228687557907788 isn't n=9 ?
17:47:30nsh-:oh, maybe not "Even the empty set has two antichains in its power set: one containing a single set (the empty set itself) and one containing no sets.
17:47:36sipa:nsh-: n=9 isn't even known
17:47:44nsh-:* nsh- nods
17:47:45andytoshi:but this is fine, you can just do SSSS where each signing key is actually a shamir secret share, and validators can compute the corresponding pubkey
17:48:12andytoshi:so the result is xH(xG) where both x's are a shared secret amongst the M signers, and will be the same no matter which M of N are chosen
17:48:20sipa:andytoshi: hmm, the signing nonce needs to be known to all signers? isn't this a problem?
17:48:31andytoshi:sipa: no, that's not the case
17:48:40nsh-:it isn't?
17:49:14andytoshi:sipa: like in additive schnorr you sum up k_i - x_iM, and nobody can separate the individual k_i's or x_i's
17:49:53andytoshi:sipa: i'm saying, now instead of x_i you use sum_{m,n} (x_i - n)/(m - n) which gives you a shamir secret share
17:50:05andytoshi:but nothing secret has become public or vice-versa
17:50:48nsh-:but all parties still have to agree on a nonce sum, no?
17:51:10andytoshi:nsh-: yes, but that's fine, they have nonces q_i, and agree on a sum of q_iG's
17:51:23andytoshi:s/q_i/k_i/ sorry, i'm crossing notations here
17:51:39sipa:ah, right
17:53:29nsh-:gmaxwell, this is the geometrical representation of the sufficiency cutting hyperplanes(surfaces)? https://en.wikipedia.org/wiki/Abstract_simplicial_complex
17:53:54nsh-:(dedekind numbers count them)
17:54:25nsh-:or is that a coincidence, hmm
17:54:44andytoshi:i doubt it's a coincidence..
17:55:32andytoshi:if you rotate a simplicial complex of dimension n so that n faces are the coordinate planes, then the remaining face will be the "cutting hyperplane" that gmaxwell referred to
17:55:36andytoshi:(i think)
17:55:41andytoshi:that gives an exact correspondence
17:57:58nsh-:interesting
17:58:28andytoshi:n faces will be the "coordinate hyperplanes" rather which are oriented along every axis but one :P
17:58:35andytoshi:it's hard to visualize
17:59:17andytoshi:but eg for a 2-simplex (triangle) you have one along x axis (all except y) one along y axis (all except x). for a 3-simplex (pyramid) you have one on xy plane (all except z), etc
18:00:00nsh-:* nsh- nods
18:04:24andytoshi:above i said sum_{m,n} (x_i - n)/(m - n) ... what i meant was x_n prod_{i≠n} (x - n)/(i - n) evaluated at 0. (not that this affects anything, but i ought to be correct :))
18:18:47andytoshi:actually i think this secret-sharing thing is more general ... lets you do N-of-M additive schnorr which looks like 1-of-1 (so only one pk is published)
18:18:53andytoshi:i will run through the algebra, seems too good to be true..
18:19:40andytoshi:gmaxwell: can you post your sage worksheet with all the secp256k1 params? (i will put it on bitcoin.ninja if you don't)
18:25:07gmaxwell:n of m additive schnoor which looks like 1 of 1 is a known thing, but the constructions I knew about required signing time full roundtrip interaction which is really burdensom (imagine three people have offline wallets and are doing a 3 of 5)
18:25:19gmaxwell:er schnorr.
18:27:07andytoshi:interesting
18:27:14andytoshi:i'm pretty sure i've written down a noninteractive one
18:28:40andytoshi:why can't all M parties generate key x, nonce k, publish (i, x_iG, k_iG) (where i is their index, I assume they can order themselves somehow)
18:29:09andytoshi:then you do lagrange interpolation to generate (key, nonce) (xG, kG) from any N of these..
18:29:38andytoshi:all signers do a schnorr sig with x_i of h = H(m||kG), then do lagrange interpolation on the sigs themselves to get s = x - kh
18:29:41andytoshi:and (s, h) is the sig
18:30:16gmaxwell:andytoshi: is my sage worksheet at a url already or did I pastebin it to you?
18:30:31andytoshi:iirc you posted a url here at some point
18:30:34andytoshi:i'll look for it
18:36:46gmaxwell:I found it, doesn't seem to be online, I'll put it online.
18:37:48andytoshi:oh, and should i submit the CN whitepaper to bitcoin.ninja?
18:37:53andytoshi:i have a wpsoftware.net hosted copy..
18:45:40gmaxwell:andytoshi: https://github.com/TheBlueMatt/bitcoinninja/pull/5
18:46:00andytoshi:thx, i'll play with this, if it works maybe you and i and nsh- will do a 2-of-3
19:19:35SDCDev:* SDCDev takes off his robe and wizard hat
19:25:30andytoshi:oh, i'm being an idiot, what i'm doing is not SSSS (SSSS requires a dealer)
19:27:30andytoshi:also crap, this means i don't have a brs-compatible N-of-M
19:27:41gmaxwell:oh ha.
19:27:57gmaxwell:I was a bit confused as to how you were doing this but expected you to enlighten later.
19:28:31gmaxwell:Obviously a dealer needing form is totally useless around here. (I'm not sure why so many academic papers waste their time on models like that…)
19:28:56andytoshi:yeah, very irritating
19:29:08andytoshi:there was a non-dealer-using paper recently that used obfuscation :P
19:32:38Gnosis:how do you all feel about smart pointers in C++ (specifically boost::shared_ptr)?
19:33:48andytoshi:so, fwiw we can "salvage" the N-of-M scheme by having all potential signers interactively precompute the key image. this is bad ofc because ideally nobody should know it except the actual signers
19:37:42andytoshi:plus it's a pretty gross computation, and they might have to do a separate computation for all N-choose-M signersets
19:39:57gmaxwell:Gnosis: They're useful? not sure what you're looking for... they're a part of C++ as of C++11. I generally prefer unique_ptr whenever possible over just slathering things with the refcounting version.
19:40:50sipa:Gnosis: offtopic here, imho
19:41:12Gnosis:I ask because they seem useful to me too, yet they are nearly absent from Bitcoin source
19:41:20Gnosis:sipa: okay, noted
19:41:45sipa:Gnosis: if you're talkig about bitcoin development, see #bitcoin-dev
19:43:10gmaxwell:Gnosis: I don't think there is much use for shared_ptr in bitcoin core; the memory managment patterns are well defined enough that they aren't needed.
19:43:46gmaxwell:(usually once you go down the refcounting route you can no longer reason about the worst case resource usage)
19:51:56nsh-:(why's that?)
19:52:14sipa:please, #bitcoin-dev
19:52:24nsh-:((soz))
19:56:14Gnosis:gmaxwell: ah, got it. Thanks!
20:34:48HobGoblin:HobGoblin is now known as Guest94465
20:44:07SDC:SDC is now known as SDCDev
20:47:03jbenet_:jbenet_ is now known as jbenet
21:48:51DougieBot5000_:DougieBot5000_ is now known as DougieBot5000
21:49:26warren_2:warren_2 is now known as warren
22:50:30phantomcircuit:https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=762923#10
22:50:33phantomcircuit:we have a winner!
22:53:15gwillen:the bash script export feature is going to have to go
22:53:22gwillen:that will be the final resolution
22:53:30nsh-:bash maintainer isn't keen on the idea
22:53:37nsh-:there's already a patch that makes it a compile-time option
22:53:56gwillen:bash maintainer is going to get steamrolled
22:54:03gwillen:so far two patches and two failures
22:54:17nsh-:remains to be resolved. there's a memory corruption in the offing since the last patch though, so i guess he's going to be overruled on the matter
22:54:22gwillen:yep
22:54:42nsh-:i have some sympathy for this view though: http://paste.lisp.org/display/143864
22:54:45gwillen:the feature could be made safer by prefixing the vars
22:55:00nsh-:tl;dr -- it's a problem with shells being used outside of spec, partly because there is no spec
22:55:03gwillen:mah
22:55:06gwillen:er, meh
22:55:19gwillen:no spec for shells, no spec for anything
22:55:27nsh-:* nsh- smiles
22:55:50gwillen:that doesn't mean you can't call it a bug if it does something nobody wanted it to do, not even the author
22:56:18gwillen:(typing on phone keyboard, typing speed limited :-)
22:56:21gmaxwell:anything passing network input to a @#$@ shell (or anything like a shell) is pretty nuts to begin with.
22:56:29gwillen:ehhhhhh
22:56:43gwillen:we have been doing this for yeeeeeears
22:56:51gwillen:lots if things in unix are shell scripts
22:56:56gmaxwell:(this was one of the reasons I cited against the foo notify stuff in bitcoind, though at least there is very very narrowly confined)
22:57:04gmaxwell:Yes, doesn't mean it isn't nuts.
22:57:07gwillen:shrug
22:57:40gwillen:you only get to say it's nuts if you could have predicted it was nuts _before_ it got exploited :-P
22:57:45gmaxwell:it's certantly not the first time we've had env var loading attacks.
22:58:08gwillen:hmm, I mean I'm sure we had to learn abour PATH the jard way
22:58:10gwillen:hard*
22:58:26gwillen:perhaps that should have been our warning sign
22:58:27gmaxwell:path, ldpreload, termios,
22:59:05gmaxwell:there have been a half dozen vectors where you take something that normally doesn't get network input and give it network input via an obscure channel half the people don't know about and evil happens.
22:59:13gwillen:but the security boundary as long as I have understood it has been implicitly "no user control over env var names"
22:59:26gwillen:which bash violated here on its end
23:01:06nsh-:i think the main issues is a lack of robustness that's (relatively-)inherently traded off against power of shells scripting in association with network events and linux probably should be evolving to a position of more security through architectural design than judicious administration
23:01:25nsh-:there are more things to administer these days than judicious people
23:01:38gwillen:nod
23:01:51gwillen:this was not an administration isse though
23:01:54gmaxwell:hm? * is passing data to bash in enviroment variables and bash is doing things the caller didn't expect. The problem is pasing data in enviroment variables and thinking you can whitelist your way to safty.
23:02:17gwillen:lots of standard components pass untrusted data in env vars by design
23:02:25gwillen:this is not a configuration issue
23:02:46gwillen:and the idea that you will ever keep all untrusted data out of env vars is not realistic
23:02:50nsh-:but that design is a historical legacy and requires a continuity of the culture that remembers these norms of sanitization
23:02:50gmaxwell:gwillen: yes and every one of them has been exploitable multiple times in the past.
23:02:59nsh-:and clearly that's fallen by the wayside
23:03:24gwillen:you will never ever get all untrusted data out of env vars, though
23:03:25phantomcircuit:gwillen, the issue has nothing to do with bash
23:03:29gwillen:not in a million years
23:03:48phantomcircuit:environment variables should not contain remote unsanitized user input
23:04:05gwillen:the cgi standard, which yes is antiquated, _requires_ putting user input in env vars
23:04:19gwillen:do you expect those legacy apps to just go away?
23:04:22phantomcircuit:gwillen, so then consider cgi to be insecure by design
23:04:23gmaxwell:gwillen: whats more fun is that the env is passed onto every subprocess; which means that it's not just bash's security behavior you have to worry about but everything it calls, including potentially a lot of other things that also were never written with untrusted input in mind.
23:05:24gmaxwell:yes, cgi does. But cgi is old and has long been home to many secuity issues; it's also a trivial fork bomb in most configurations.
23:05:46nsh-:it's a shame we can't lay out the entire landscape of possible execution flows of the programs on a device and be able to see at a glance which streams of information are user/network controlled -- systemwise taint analysis
23:06:11nsh-:i guess that's towards the impossible side of ambitious
23:06:26gmaxwell:tagged memory can do this (e.g. valgrind uninit checking) but its expensive and less useful than you'd think.
23:06:36phantomcircuit:^ that
23:06:38nsh-:why less useful?
23:06:43gmaxwell:there are papers on doing this, language extensions.
23:06:58phantomcircuit:gmaxwell, iirc there are actually commercial versions that work slightly better... but which are insanely expensive
23:07:19gmaxwell:nsh-: taint tends to flow everywhere... valgrind does a ton of work to suppress irrelevant results... e.g. it tracks the taint around but only tells you when it changes control flow.
23:07:30nsh-:* nsh- nods
23:07:54gwillen:it feels to me like you are trying to draw a security boundary in a place it does not naturally want to go
23:08:09gwillen:which is going to fail, which will give results no better than leaving it alone, and potentially worse
23:08:24gwillen:there are an infinite number of apps that pass data in environment variables
23:08:30gwillen:and a very large number that pass untrusted data there
23:08:33gwillen:and you can't control all of them
23:08:48gmaxwell:gwillen: otherwise it's the whole system. _you do not know_ what j-random-program-never-designed-for-network-input is going to do based on the enviroment.
23:09:00phantomcircuit:gwillen, there are actually very few which pass untrusted user input in environment variables
23:09:31phantomcircuit:cgi and weird uses of ssh being the only two i can think of at this point
23:09:52gwillen:it's not a small number, phantomcircuit
23:09:53phantomcircuit:(dhcpcd no longer passes unsanitized values using environment variables)
23:09:59gwillen:both major dhcp clients do it
23:10:04gwillen:okay, one major dhcp client does it
23:10:09phantomcircuit:gwillen, not for very long they dont
23:10:12gwillen:all djb software does it
23:10:16gwillen:and I'm sure some people will laugh at that, but.
23:10:26phantomcircuit:gwillen, then all djb software is insecure by design
23:10:26gwillen:openvpn does it
23:10:37gwillen:and we don't even know the beginning of the list
23:10:46gwillen:I guarantee that for every piece of software mentioned, there are 10 more we don't know about
23:10:52gwillen:and you will never ever find them all
23:10:57gmaxwell:I agree lots of things do it. I've specifically avoided doing it in the past simply because it was impossible to figure out if it was secure or not.
23:11:00phantomcircuit:gwillen, it's a widespread security anti-pattern
23:11:11phantomcircuit:that does not mean that the root issue is bash
23:11:12gwillen:I don't disagree that it's worth avoiding
23:11:21gwillen:but security by looking very angry at how stupid peole are is not a strategy
23:11:30phantomcircuit:indeed it's so widespread that i can basically guarantee that there are other things with the same "issue" that bash has
23:11:31gmaxwell:hm? I never said anyone was stupid.
23:11:40phantomcircuit:gmaxwell, to be fair i did
23:12:18gmaxwell:They're not stupid. This is impossibly hard. Which is why you don't want to use things like env variables, because it's impossible to make progress on the question "what code touches this potentially malicious input".
23:12:26gwillen:you can theorize about how many apps do X or Y, but in practice we have lots of examples of apps that put user input in env vars, and exactly one contemporary example of an app that accidentally executes their contents
23:12:37gwillen:I agree that maybe we should stop doing the former
23:13:00gwillen:but it's a lot easier to stop executing the contents of env vars than to stop giving them user-controlled contents
23:13:12gmaxwell:"Why not both?"
23:13:14gwillen:sure, do both
23:13:23gwillen:but the latter is going tobbe a long hard slog
23:13:27nsh-:* nsh- rings the consensus bell
23:13:30gwillen:and it's going to take the better part of a decade, I supect, to root it all out
23:13:36gwillen:and even then it won't be complete
23:13:43gwillen:you're going to have CGI users into the next century probably :-P
23:14:03gmaxwell:anything that does this is a trivally DOS vulnerable in any case; so obviously we need more DOS attacks. :)
23:14:18gwillen:that seems unlikely to me
23:14:26gwillen:it's trivial to control the length of user input
23:14:30gwillen:it's a lot hard to control the contents
23:14:31phantomcircuit:gmaxwell, well yes that was my point, it's obviously very very difficult to verify correctness with env vars.... so using them to pass user input is a bit daft
23:14:34gmaxwell:"I fork a shell based on a user request" is pretty awful.
23:14:51gwillen:that's a strawman and you know it :-P
23:15:00gwillen:dhclient/dhcpcd do not fork shells based on remote input
23:15:02gmaxwell:phantomcircuit: well, it was more obvious 20 years ago before the last N other env var surprises.
23:15:04gwillen:but they still pass remote input in variables
23:15:05phantomcircuit:i had always though openvpn was only passing well structure stuff to those scripts
23:15:14gwillen:yes, well-structured stuff
23:15:19gwillen:like the rdns of the remote host! :-P
23:15:23gwillen:guess who controls that?
23:15:24phantomcircuit:and find it hilarious that anybody considers cgi to be secure for production use at all
23:15:31gwillen:you will never ever ever get this all scrubbed
23:15:55gwillen:honestly, here's what I'd suggest if you want clean environments
23:16:05gwillen:have the kernel scrub the environment at every exec
23:16:08gwillen:with a whitelist
23:16:12gwillen:unless requested otherwise by a flag
23:16:28phantomcircuit:gwillen, the rdns of the remote host should only contain valid domain names
23:16:31phantomcircuit:which should be safe
23:16:50gwillen:gmaxwell: see what I mean? :-P
23:16:55phantomcircuit:that it's not indicates something is broken
23:16:59gwillen:you will be arguing with software authors about what's unsafe user input until the next century
23:17:50gmaxwell:phantomcircuit: even if it's not valid in DNS you can encode lots of crazy stuff and get it through.
23:18:42phantomcircuit:gmaxwell, right... but the value should be filtered by openvpn if it's not a valid dns name
23:18:56gmaxwell:maybe
23:19:18gwillen:so now we can agree that user input can't go in environment variables
23:19:22gwillen:we just can't agree on what user input is :-P
23:20:01gwillen:(Sorry I keep dropping off, my internet conection is shit)
23:21:47phantomcircuit:gwillen, in general user input -- even sanitized -- should not go into environment variables
23:22:03gwillen:phantomcircuit: you keep saying that but you want to put rdns into envrionment variables! :-P
23:22:06gwillen:that's sanitized user input!
23:22:07phantomcircuit:but the idea that unsanitized user input is going into them is just ridiculous
23:22:18gwillen:and not necessarily even sanitized very well!
23:22:28phantomcircuit:gwillen, no im saying i thought it was sanitized... not smart... but not nearly as stupid
23:22:31gwillen:I don't know if the protocol will stop me from returning "() {" in a dns label
23:22:34gwillen:but I bet you it won't!
23:22:44gwillen:at least not if I'm your local cache
23:22:50gwillen:maybe if I'm out on the internet somewhere
23:22:56phantomcircuit:gwillen, dns wont prevent that but openvpn should not be passing that
23:24:37phantomcircuit:gwillen, afaict the vast majority of modern linux systems aren't actually vulnerable to dhclient doing stupid things
23:24:50phantomcircuit:because they call a networkmanager binary which doesn't call anything else
23:25:15gwillen:my understanding is that networkmanager is not vulnerable, yes
23:33:32gmaxwell:ah, funny, even the monotone boolean functions are redundant for sane signing policies... in that they include functions that don't-care about some of the inputs.
23:39:29sipa:gmaxwell: would that make a significant difference?
23:41:05sipa:gmaxwell: i expect monotone_but_cares_about_all(n) = monotone(n) - n*monotone(n-1) or something
23:41:47sipa:ah, no
23:42:00sipa:monotone_but_cares_about_all(n) = monotone(n) - n*monotone_but_cares_about_all(n-1)
23:42:52sipa:mbcaa(1) = 1
23:43:46gmaxwell:not really significant indeed. just I thought that monotone booleans mapped 1:1 to possibly sensible policies, but not quite.
23:44:26sipa:mbcaa(2) = 2
23:51:09gmaxwell:mbcaa(3) = 9 (got tired of waiting and just counted them in my head!)
23:51:32sipa:yeah, i was trying to find a formula, but it doesn't seem quite right
23:52:01gmaxwell:4 is too much to count or I'd just plug 1,2,9,x into OEIS and probably get the formula out. :)
23:52:26gmaxwell:9 is quite a bit fewer than 20.
23:52:32sipa:uhu
23:55:22kanzure:oh what is OEIS?
23:55:41gmaxwell:online encyclopedia of integer sequences.
23:55:51kanzure:oh
23:56:22gmaxwell:my favorite use for it is when I have some problem where I can solve some consecutive values but don't see a closed form formula ... oeis knows it surprisingly often.
23:56:25kanzure:i would have guessed a competitor to eureqa (symbolic regression tool thing)
23:56:58gmaxwell:(and usually the result is some psycho thing from a totally unexpected field of analytic geometry or chess moves or something; but whatever)
23:57:11andytoshi:s/or/and/g
23:57:43kanzure:ouch looks like they took down all the open source versions of eureqa
23:58:41kanzure:http://web.archive.org/web/20120615103204/http://creativemachines.cornell.edu/eureqa
23:59:31kanzure:oh. it wasn't open source..