--- Log opened Thu Apr 25 00:00:11 2013
--- Day changed Thu Apr 25 2013
00:00 < petertodd> heh, as inflammatory as it was I kinda liked jdillons point about how he trusts Mike with all the coins on his android wallet
00:01 <@gmaxwell> Yea, esp since android has silent push updates.
00:01 <@gmaxwell> You guys see the ozcoin  /  strongcoin drama?
00:02 < petertodd> also interesting to consider how the strongcoin 'coin movement' would be trivial to do on an off-chain tx system, yet at the same time with fraud proofs implemented doing so could be suicide (absent the still present client software vulnerabilities)
00:03 < petertodd> strongcoin got away with it, to the extent they have anyway, because humans are in the fraud detection loop
00:03 < petertodd> a regulatory issue too: "Um, you see if I return the funds this source code is going to declare me a fraudster and my clients will instantly stop using my service..."
00:04 < petertodd> same issue with Bitcoin fundementally, but more likely to be a problem in practice "yeah, you see, I can't change my mining pool to prevent those stolen funds from being moved"
00:06 < amiller> how to know if you're an illegally operating MSB tip #103125: you're capable of detect and returning someone's stolen funds...
00:07 < petertodd> lol
00:08 < petertodd> "This isn't a MSB! Why fraudproofs/trusted-hardware/closed source software/The FSM stop that!"
00:10 <@gmaxwell> :)
00:11 <@gmaxwell> I hope at least some people were getting my points about building systems where _no one_ gets put in the awkward position of having to decide to protect a theif.
00:12 < amiller> i'm interested in more ideas/examples of how to encourage things-that-will-eventually-fail to fail immediately and obviously
00:12 < petertodd> gmaxwell: I'd suggest actually saying that directly...
00:12 <@gmaxwell> I thought I did!
00:12 < petertodd> I got it, I doubt even 10% of the audience did.
00:36 <@gmaxwell> " It would have been wrong of us to demand that the operator of a service turn down a well substantiated request in a case like this, it would make them a villain to the kind and honest people their decision harmed. We shouldn't create a world where people have to make choices like that."
00:37 < warren> gmaxwell: so the strongcoin guy detected the thief then modified the .js to take it?  That wasn't entirely clear on the thread.
00:40 < warren> It's amazing to me that the thief would be so dumb to use a traceable wallet at all.
00:41 <@gmaxwell> I mean, being a thief suggests a prior probablity that you are not someone who makes excellent life choices.
00:42 <@gmaxwell> warren: yea, my understanding was that he just modified the script to have if(this_is_such_and_such)sendallfunds(overhere);
00:42 < warren> that's scary.
00:43 < warren> I haven't checked if my blockchain wallet as Chrome extension has been silently updating itself
00:43 <@gmaxwell> It's the expected and obvious outcome and it's what I've spent the last year trying to convince people exists on these sites.
00:43 <@gmaxwell> ...
00:43 <@gmaxwell> warren: the extension only makes sure that the site matches the github, or at least thats how it used to work.
00:43 < warren> I've been meaning to switch away from it for weeks for that reason, and also the ability to brute force attack a wallet.  I strongly suspect someone downloaded all the encrypted wallets.
00:44 <@gmaxwell> yea, a lot of compromises lately and people claiming they had fairly strong keys.
00:44 < warren> I think there were two or three different blockchain wallet attacks
00:44 <@gmaxwell> there might be a vulnerability that let people bulk download the encrypted wallets. (perhaps some xss)
00:45 <@gmaxwell> (er, CSRF really)
00:45 < warren> 1) XSS or java browser exploits from clicking links on btc-e trollchat.  2) Android wallet malware and blockchain's android wallet being far less secure.  3) Weak passphrases and brute force cracking of all encrypted wallets that were downloaded.
00:46 <@gmaxwell> fwiw, I do all my webbrowsing in a seperate VM. Security is just too hard.
00:46 < warren> gmaxwell: reportedly someone is 95% through writing another js client-side encrypted wallet.  he intends on open sourcing it.
00:46 < warren> yeah
00:46 <@gmaxwell> ::Sigh:: sounds like another instawallet waiting to happen. :P
00:46 < warren> sadly there seems to be something wrong with kvm.  It's wayyyy slower than a few months ago.
00:46 <@gmaxwell> People are really too easily convinces that JS wallets are completely secure.
00:47 <@gmaxwell> weird. Working fine for me.
00:47 < warren> not sure what's going on
00:47 <@gmaxwell> s/convinces/convinced/
00:48 < warren> He's writing it for Litecoin, but will launch it for both
00:48 < warren> Litecoin idiot factor is a bit higher ... and MtGox confirmed today that they will launch Litecoin real soon.  https://mtgox.com/pdf/20130424_ddos_statement_and_faq.pdf
00:48 <@gmaxwell> why doesn't he just take the blockchain.info code?
00:49 < warren> not sure, it has no copyright or license notices, suggesting it is on github only to allow auditing?
00:49 < warren> Litecoin remains unmaintained.  I really want to work on it but too busy.  I volunteered to help the professor finish her book before the June 1st deadline.
00:49 <@gmaxwell> oh, hm. I thought it was liberally licensed, I got yelled at by piuk for calling it propritary.
00:49 < warren> oh?
00:50 <@gmaxwell> as far as litecoin goes... ... tell mtgox that they want to pay you to work on it, and perhaps then you could justify some more time?
00:50 <@gmaxwell> if they're trading it .. and litecoin goes explody it could turn out quite bad for them.
00:50 < warren> I seriously doubt they would pay me.
00:51 < warren> well, it could go explody even if maintained
00:51 <@gmaxwell> sure, more likely to if unmaintained.
00:51 <@gmaxwell> I mean, other altcoins have had enormous rewrite attacks in order to exploit exchanges.
00:51 <@gmaxwell> and those exchanges are no longer in business anymore.
00:52 < warren> Litecoin remains vulnerable to the BDB lock limit self-consistency issue now.
00:53 < warren> gmaxwell: how is your relationship with mtgox?  could you suggest this?
00:53 < amiller> oh wow litecoin is being added to mtgox?
00:53 < warren> amiller: yes.  seems premature and risky to me.
00:53 < amiller> i actually did *not* suspect an altcoin would catch on... like this...
00:53 < amiller> crazy times
00:54 <@gmaxwell> magicaltux was saying it was a joke a few weeks ago. I suspect it was a joke and then it got a positive response from someone relevent.
00:54 < warren> I'm not invested in Litecoin.  I'm interested in developing it because 1) they're hurting for devs 2) I want to prove anti-spam policies that Bitcoin seems unwilling to adopt.
00:55 <@gmaxwell> A friend that has some of my old gpus is mining litecoin, ... he went through three pools before finding one that wasn't just robbing him blind.
00:56 <@gmaxwell> (I suspect his anti-samdar is not very finely tuned!)
00:56 < warren> There are honest litecoin pools.  Trouble is they get killed by DDoS often.
00:56 < warren> p2pool is the most reliable way to mine it.
00:57 <@gmaxwell> yea, I think he was on one that got dos killed first, and then switched to something else that just never paid him at all... and then another one which was giving him about 10% of what he should have been getting... and then one that went offline with positive balances.
00:57 < warren> Trouble with p2pool though is the dust + litecoin's super high fees.  I tried to convince forrest to reduce the number of shares in the next p2pool hardfork as the current dust size is unusably small.  He isn't budging.
00:58 <@gmaxwell> people can turn up their share difficulty if they're prefer to not get dust.
00:59 < warren> My maximum 100% efficiency dust size is too small.
00:59 < warren> I had to abuse 7 10KB free tx's to combine a thousand of them yesterday.
00:59 < warren> (maybe not a thousand, a few hundred, dunno)
01:00 <@gmaxwell> huh? changing you share difficulty shouldn't have anything to do with your efficiency!
01:01 < warren> What difficulty factor are you suggesting?
01:01 < warren> 5x less often?
01:02 <@gmaxwell> however much makes it so you don't get paid in every block
01:03 < warren> It allows a maximum of 10x
01:03 < warren> which isn't high enough to do that
01:03 <@gmaxwell> ah, well that seems like an issue.
01:03 <@gmaxwell> it should be claimed not on the up side but on the down side.. e.g. it shouldn't get you set it to more than 1/50th of a block or something.
01:04 < warren> It really isn't clear why Litecoin has such exchange value.  There's NO VENDORS.
01:05 <@gmaxwell> it's speculation
01:05 <@gmaxwell> duh
01:05 < warren> were you serious about asking mtgox to sponsor dev?
01:05 < warren> Not a weekend bounty, like payouts every 3 months as long as progress is made.
01:05 <@gmaxwell> I was, I have no clue if they'll do it— if they're not already doing it they're morons... given that they're morons, ::shrugs::
01:07 < warren> I'm 60% convinced the hash is a risk.
01:07 <@gmaxwell> know of any online namecoin wallets that support importing private keys? I have some nmc to rid myself of and don't really feel like starting up a namecoin node....
01:07 < warren> It seems implausible that someone would invest money to destroy it though.  They could just extract outsized profits.
01:08 < warren> nope
01:08 < warren> heading to class, bbl
01:54 < petertodd> re: litecoin a silkroad clone started up recently that denominates in litecoin by default
01:55 < amiller> https://gist.github.com/amiller/cf9af3fbc23a629d3084 i summarized my above points about fees and contention here
01:58 < petertodd> Hmm... one odd thing about coinbase tx's is they can-not have non-generation inputs. If you allowed that, and made them an exception to the usual rule that you can-not spend a coinbase, your equilibrium creating behavior can be done, paying part of the fee to the next miner, and yet still avoid the mess of a re-org canceling coinbases.
01:59 < petertodd> The fee you give to the next miner would basically be an anyone-can-spend output from the coinbase tx.
01:59 < amiller> righteous
02:00 < petertodd> yup
02:00 < petertodd> but it's late here, night
02:00 <@gmaxwell> or you do what I suggested before— make uncollected fees spill forward and you avoid all the weird maturity restrictions
02:01 < petertodd> gmaxwell: makes proofs that the block is correct potentially unbounded in size
02:01 < amiller> no you'd just have everyone keep a counter in their state
02:02 < petertodd> hmm, yeah, I'll think on that, but later
02:06 <@gmaxwell> petertodd: nah, doesn't, you just make the payforward accumulator part of the header.
04:39 < warren> gmaxwell: coblee is concerned about taking donations/sponsorship to help dev because that may create expectations or implied liability
04:40 <@gmaxwell> hah.
04:40 < warren> I personally would want work on this, to setup a non-profit and a legal structure that states clearly the project's goals (safety, security, anti-spam) but disclaims liability.
04:41 <@gmaxwell> if someone wants to find implied liability ... the fact that someone took donations or didn't isn't going to matter.
04:41 < warren> TRC dev really fucked up.  I doubt anyone will sue there.
04:42 < sipa> trc?
04:42 < warren> sipa: another alt coin, sha256-based.  They had ~4-5 mandatory version upgrades over a week because their bad design was destroyed repeatedly by a single avalon
04:42 < sipa> ha
04:42 < warren> sipa: TRC's "innovation" was super fast difficulty changes
04:43 < warren> It broke in a different way with longer 30 block intervals
04:43 <@gmaxwell> it's not even the first time someone has made that innovation with the same consequences!
04:43 <@gmaxwell> solidcoin 1.0 failed that way.
04:43 < warren> Attempt #4 made it far worse!
04:44 <@gmaxwell> yea, well I called that (or was that #3?) with ten seconds of code review…
04:44 < warren> They added a testnet-like difficulty reduction if there were no blocks in the last 10 minutes.
04:44 <@gmaxwell> yea, that was the one I called. :P
04:44 < warren> I pointed it out first, and you agreed. =)
04:44 < warren> Shortly thereafter, someone did the time traveling attack.
04:45 < warren> during these attacks, btc-e added  TRC to their exchange, and they were wondering why nobody was trading
04:45 < warren> great due dilligence folks
04:45 < warren> That was a huge opportunity to rob the exchange
04:45 <@gmaxwell> You knew before I told you there about the reseting difficulty attack?
04:45 < warren> yes
04:45 <@gmaxwell> cool. someone else paying attention.
04:45 <@gmaxwell> oh well, in any case, Lolcust is back around so you can expect more really super awesome altcoins.
04:45 < warren> I remembered seeing it in the testnet code while I was studying litecoin.
04:47 < warren> If I had time, I'd like to release a tool that forks Bitcoin, mass string replace, generates a new genesis, makes deterministic builds and uploads to a new git.
04:47 < warren> Then those fools can make a 100 new coins.
04:47 < warren> Then *maybe* people will realize how stupid it is.
04:48 < warren> gmaxwell: Can you help me approach MtGox on that idea?
04:49 <@gmaxwell> I suggested that idea in #bitcoin-mining with an added twist: you should make the cgi charge a nomial fee (in btc), and partner with a large pool, with merged mining, so that instead of premining them the creator can just recieve the pools worth of mining.
04:49 <@gmaxwell> warren: making 100 new coins?
04:49 < warren> no
04:49 < warren> sponsor dev of their new coin to reduce their financial risk
04:49 < warren> because there's literally no reference client devs
04:50 <@gmaxwell> Well, I can— however, magical tux doesn't talk to me too much, and the last time he talked to me— it seems like he outright lied to me. So...
04:51 < warren> gmaxwell: oh, you mean make it super easy for the creator to pre-mine?
04:51 <@gmaxwell> nah, not pre-mine— but to have a large amount of hashpower on the coin right from the start which the creator is getting paid for.
04:51 <@gmaxwell> a slightly more equatible premine that also provides some security.
04:52 < warren> huh.
04:52 < warren> which would be the aux?
04:52 <@gmaxwell> it would be the aux. It'd be merged mined against bitcoin (or litecoin, I suppose if you wanted)
04:53 < warren> are any of the merge mining methods reliable now?
04:53 < warren> such that it won't slow down the main coin
04:54 < warren> gmaxwell: well, I suppose an introduction might help.  This seems like a good idea for both parties.
04:54 <@gmaxwell> luke's code is— and I assume doublec's too— considering both have basically merged mined everything mergminable.  Luke stopped mming namecoin recently mostly because the daemon itself was crapping out.
04:54 < warren> doublec?  what pool did he write?
04:55 <@gmaxwell> http://mmpool.bitparking.com/pool
04:55 < warren> hmm, no source I guess
04:56 <@gmaxwell> no, but it wouldn't be useful to you, you don't have a big installed base of bitcoin hashpower
04:56 <@gmaxwell> my suggestion was to partner with someone who already did.
04:56 <@gmaxwell> luke was all for the idea— can't stop the altcoin folly directly, so make it more obvious with infinite worthless altcoins.
04:57 <@gmaxwell> I sometimes joke about gmaxwellcoin ... but then everbuddy could have their own altcoin, for the low low price of 0.5 BTC!
04:58 < warren> On a more serious note, how do you feel about a blockchain-based solution to reward full verifying nodes?
04:58 <@gmaxwell> blockchain-based? huh?
04:58 <@gmaxwell> I like puppies and apple pie.
04:59 < warren> OK, I haven't thought this through yet, just wondering if its possible to have a POW that proves you have all the tx's and you are relaying.
05:00 <@gmaxwell> amiller proposed to use queries against a committed utxo set as a memory hard function as the system POW.
05:01 < warren> who would do the query?
05:01 <@gmaxwell> and it seems like a generally reasonable idea to me, though I have some skepticism that the result will actually be hardware thats good at validation: if there is _any_ way to make it faster by cheating people will.
05:02 <@gmaxwell> warren: you'd query to mine. e.g. H(header||nonce) forms a random sequence which you use to query the UTXO set.. then you hash up the result append that to the header.. and hash that to see if you've met difficulty
05:03 < warren> and if you met difficulty, what do you get?
05:03 <@gmaxwell> a block
05:04 < warren> This is a secondary blockchain to somehow reward full nodes?
05:05 < warren> hmm
05:06 <@gmaxwell> ...
05:06 <@gmaxwell> Amiller's suggestion is to make it _the_ proof of work.
05:06 < warren> oh
05:06 <@gmaxwell> In order to align the interests of the network.
05:07 <@gmaxwell> If you just want a full node lottery— get pay2ip reenabled and probe nodes and then randomly pay them if they've been good. reasonably hard to fake if you pay them proportional to their throughput.
05:07 < warren> how about ... for each BTC block round, the highest difficulty from valid proof of uxto set from all nodes gets <reward> which is set aside in the next BTC block?
05:08 < warren> with some limitations to prevent ballot stuff
05:08 < warren> stuffing
05:09 <@gmaxwell> uh.
05:10 <@gmaxwell> well good luck with that.
05:11 < warren> what?  not technically possible?
05:13 < warren> Oh.  Not highest.  More like a lottery where the winning number is derived from the next block.
05:17 < warren> I don't have this fully thought through.  I'll think more about this.
05:18 <@gmaxwell> I don't see how I don't just enter that lottery unpteem billion times per second. Or how you're going to convince the network to take awards away from miners. (amillers stuff seems obviously enough not-for-bitcoin— but if you're going to be all hardforky about it might as well go full amiller time)
05:19 < warren> The hard part is to prevent folks from making many artificial nodes on many IP's they control. yes.
05:21 < warren> I think the lottery could be limited by having random peers check then sign if they pass certain rules.
05:22 < warren> best we can do is limit by public IP, and maybe also only one per subnet randomly chosen.
05:25 < warren> gmaxwell: Divert a really tiny portion of fees to the full node lottery.  Since running a node is much cheaper than running a miner, even a tiny lottery reward would be sufficient to encourage many more relays.
--- Log closed Thu Apr 25 07:21:17 2013
--- Log opened Thu Apr 25 07:21:34 2013
10:43 < warren> There are aspects of this I haven't figured out yet, and a major drawback of it being decentralized might be lots of extra tx's per round.
10:47 < warren> gmaxwell: Oh, another aspect of the p2pool dust problem: The litecoin users began taking matters into their own hands by forking p2pool, cutting forrest out entirely.  There are at least two other p2pool instances in litecoin now.
10:50 < warren> "<gmaxwell> [23:07:25] If you just want a full node lottery— get pay2ip reenabled and probe nodes and then randomly pay them if they've been good. reasonably hard to fake if you pay them proportional to their throughput."
10:51 < warren> I'm afraid this will create perverse incentives to intercept traffic
10:51 < warren> (yes, we talked about this before)
--- Log closed Thu Apr 25 11:29:38 2013
--- Log opened Thu Apr 25 11:28:19 2013
--- Log closed Thu Apr 25 11:28:29 2013
--- Log opened Thu Apr 25 11:29:04 2013
15:09 < HM2> cryptography is a fascinating field
15:09 < HM2> obvious ideas can sneak up on you
15:10 < HM2> i'm reading a paper on permutations over arbitrary domains. e.g. using a key to remap the numbers from 0 to 1 million to a permutation
15:11 < HM2> simplest algorithm: use a symmetric cipher to encrypt all the numbers, sort the ciphertext, replace each number with it's ordinal index
15:11 < HM2> such an obvious idea
15:12 < sipa> it will also never be a true random shuffle :p
15:13 < HM2> why so?
15:14 < sipa> your keyspace sie would need to be a integral multiple of the number of permutations ((=n!, with n the number of elements)
15:15 < HM2> Hmm?
15:16 < HM2> Your domain needs to be smaller than the block ciphers
15:16 < HM2> it doesn't matter if you're encrypting 4 digit pins with a 128bit cipher though, it's still going to result in 10000 unique 128bit ciphertexts?
15:16 < sipa> not just smaller, an integral divisor of it
15:17 < sipa> (and that's a necessary requirements, not a sufficient one)
15:17 < HM2> How?
15:18 < HM2> http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf
15:18 < HM2> method 1, page 6
15:19 < sipa> i didn't say it would be insecure
15:19 < sipa> just that it can't be a true random shuffle
15:19 < HM2> how do you define true random?
15:19 < HM2> it's obviously pseudorandom
15:20 < HM2> but are you saying it'll be biased?
15:21 < sipa> yes
15:21 < HM2> I'm confused about the integer multiple bit, because the actual value and length of the ciphertext is irrelevant, you only care about ordering within the block ciphers domain
15:21 < sipa> not every permutations will have the same probability
15:22 < HM2> Hmm perhaps, but you don't actually have to use a symmetric cipher either
15:22 < sipa> irrelevant
15:22 < HM2> How is generating 10000 SHA-1s going to be biased?
15:23 < HM2> for instance, say your arbitrary domain was over [0,1]
15:23 < HM2> basically you're generating SHA(key,1) and SHA(key,2) and comparing which is the greater
15:23 < sipa> ok
15:23 < HM2> you're saying there's going to be a bias of ordering?
15:23 < sipa> say we're sorting [0,1,2]
15:24 < HM2> no just mapping 0 -> 0 or 1 and 1->other one
15:24 < sipa> and we use SHA(key,n) & 0xF
15:24 < HM2> woah
15:24 < sipa> instead of the full SHA
15:24 < HM2> & 0xF?
15:24 < HM2> no
15:24 < sipa> just to prove my point
15:24 < sipa> it's equally valid for larger keys
15:25 < HM2> hmmm
15:25 < sipa> so you have 8 possible outcomes, ignoring the key
15:25 < HM2> yes
15:25 < sipa> and they have to be distributed over 6 possible permutations
15:25 < sipa> wait, i'm wrong
15:25 < HM2> 8x7x6 permutations
15:26 < HM2> erm
15:26 < HM2> (8x7x6)/(3x2)
15:26 < sipa> yes, and this just happens to be possible :p
15:26 < HM2> lol
15:27 < sipa> the point is that if the input to your algorithm (the key) has not a multiple of the possible resulting permutations, there will always be permutations that are more likely then others
15:27 < sipa> that doesn't mean these are easy to find, or that it's insecure
15:27 < HM2> hmm
15:28 < HM2> I still don't really see that. If you encrypt 10000 distinct values with a symmetric cipher you're going to end up with 10000 distinct ciphertexts, the distribution of those ciphertexts should be pseudorandom
15:29 < sipa> you see it as a function that takes as input a key, and returns a permutation
15:30 < sipa> each key is equally likely as input
15:30 < HM2> this is why i tried to boil it down to a very limited domain
15:30 < HM2> [0,1]
15:30 < sipa> HM2: and i'm not talking about pseudorandom or not
15:30 < sipa> in fact, if it's pseudorandom it can never be a perfect shuffle
15:31 < sipa> as no variance in the output probabilities is incredible unlikely
15:31 < HM2> SHA(key,0) should be < than SHA(key,1) ~50% of the time. so how can ordering those outputs not be a good pseudorandom shuffle?
15:31 < sipa> i am NOT talking about pseudorandom or not!
15:31 < HM2> ok
15:32 < sipa> i'm saying that not every permutation will be equally likely
15:32 < HM2> but a shuffle is a permutation
15:32 < sipa> yes
15:32 < HM2> well the paper says nowt about it
15:32 < sipa> sure
15:33 < sipa> it also doesn't matter if you keys are large enough
15:33 < sipa> which is the case in cryptographic applications anyway
15:33 < sipa> but when people try to make a random shuffle based on just some rand() function, this argument can be used to show that their shuffle is biased
15:34 < HM2> oh sure, shuffling is hard, but i still don't see your multiple problem
15:34 < sipa> if your function has N input possibilities, and M output possibilities
15:35 < sipa> then some outputs will be more likely than others
15:35 < sipa> unless N is a multiple of M
15:35 < HM2> but that's not the case
15:35 < sipa> i mean, if there are 4 inputs and 3 outputs, one output will be the result of 2 inputs, while the others will be the result of 1
15:35 < HM2> right agreed
15:36 < HM2> but you're doing this
15:36 < HM2> [encrypt(K,0), encrypt(K,1), encrypt(K,2),encrypt(K,3)]
15:37 < HM2> sorting the results
15:37 < HM2> it doesn't matter if they're 8 bits long or 1024 bits long
15:37 < HM2> relative to one another they're still randomly ordered
15:37 < sipa> for 8 bits the bias should be detectable
15:37 < sipa> iterate over all 256 input keys, see which output permutations you end up with
15:38 < sipa> and you'll see some are definitely more likely than others
15:38 < HM2> ah sure
15:38 < HM2> but you're talking about biases within the block cipher
15:38 < sipa> no
15:38 < sipa> even if that encrypt function has a perfectly uniform output distribution
15:39 < HM2> OK, so you should be able to replace it with a perfect number generator
15:39 < sipa> because there are 256 inputs, and 24 outputs
15:39 < HM2> let's do it with a perfect RNG that produces 4 different 8 bit numbers
15:40 < sipa> ok
15:40 < HM2> 201, 72, 3, 29
15:40 < sipa> now you've changed the function to take a 256^4 input, though
15:40 < sipa> which will still be biased but much much less so
15:40 < HM2> huh?
15:40 < sipa> you consume 4 8-bit numbers from your environment now
15:40 < HM2> what is the "input"?
15:41 < sipa> the random data you consume is the input now
15:41 < HM2> well we're moddling a block cipher as a RNG
15:41 < HM2> assuming the cipher is perfect
15:41 < sipa> doesn't matter
15:41 < sipa> the specific cipher is known
15:41 < sipa> so you cannot assume independence between the outputs
15:42 < sipa> you look at the set of all functions with 8-bit outputs, and pick one of them in advance
15:42 < sipa> and you know which one this is
15:42 < HM2> I'm still trying to nail down where you think this algorithm is flawed
15:42 < sipa> ok
15:43 < sipa> write me a program that produces a random permutation of [0,1,2,3]
15:43 < HM2> ergh
15:44 < sipa> but it only uses 8 bits of randomness
15:44 < sipa> so you get to call rand() % 256 once
15:44 < sipa> and that's it
15:44 < HM2> i never said you use 8 bits of randomness
15:44 < sipa> the key is 8 bits
15:45 < sipa> 21:37:18 < HM2> it doesn't matter if they're 8 bits long or 1024 bits long
15:45 < HM2> the block size, not the key size
15:46 < sipa> ooooh
15:46 < sipa> that changes things :)
15:46 < HM2> for instance, if you're using SHA-1
15:46 < HM2> you could put the works of shakespeare through it
15:46 < sipa> sure sure
15:46 < HM2> but you're producing 4 x 160 bit numbers
15:46 < HM2> then ordering them
15:46 < sipa> yes, but that's all irrelevant
15:46 < sipa> the question is what the size of your key is
15:47 < HM2> i see
15:47 < sipa> well, not irrelevant of course
15:47 < sipa> but it's not the problem
15:48 < HM2> so what has to be an integer multiple?
15:48 < HM2> the key size or the hash/ciphertext size?
15:49 < sipa> the number of possibilities of the key has to be a multiple of the number of potential outcome permutations
15:49 < HM2> hmm
15:49 < sipa> but i'm not in any way talking about secure or not
15:50 < sipa> random functions are always biased a bit, that doesn't mean they're distinguishable from random
15:51 < sipa> where this does matter is if someone wants to write a function to produce a random permutation of some list
15:51 < HM2> well that's exactly what we're doing
15:51 < sipa> and they do so by assigning a 16-bit (independent) random number with each element
15:51 < sipa> and then sorting the random numbers
15:51 < HM2> sure
15:51 < HM2> that's basically it
15:51 < sipa> and returning the elements in that order
15:51 < warren> sipa: oh hey, just curious how your secp256k1 is going?
15:52 < HM2> I don't see how that produces a bias
15:52 < sipa> HM2: because you're taking 2^(16*N) data as input
15:53 < sipa> and those inputs cannot be possibly evenly divided over N! potential outputs
15:53 < sipa> warren: quite good, but slow :)
15:53 < sipa> (progress is slow, not performance :p)
15:54 < sipa> HM2: in case you use some cryptographic-strength randomizing function in between, you're fine, the bias will be impossible to detect
15:54 < sipa> but if you use small random numbers, the bias may be detectable
15:54 < HM2> the number of inputs isn't 2^(16*N). If you assign 1 value from a 16 bit field to the number 0 then 1 can only be picked from field of 2^16 - 1 values
15:54 < sipa> i did say "independent random number"
15:55 < HM2> right, but that isn't the algorithm this paper is using
15:55 < HM2> it's using a block cipher which means it isn't 2^(N*16) possible mappings
15:55 < sipa> right
15:55 < sipa> but now you've moved the problem to the key
15:56 < HM2> If you have a field of size F and a block size of size N then you have N! / (N - F)! possible mappings
15:57 < HM2> I think?
15:57 < sipa> i'm going to stop discussing; i think you think i mean something i'm not :)
15:58 < sipa> and it's pointless anyway
15:58 < HM2> aww cmon
15:59 < sipa> i shouldn't have brought it up here, it is not a problem in this context
16:01 < HM2> you're assigning 16 bit numbers to [0...4] then you have (2**16)! / (2**16 - 5)! possible mappings afaict, your argument for a bias seems to be that that isn't divisible by 5! but I don't see that that's a problem
16:01 < HM2> although...actually it is divisible by 5!
16:02 < sipa> your keyspace size isn't
16:02 < sipa> if it is many times larger, that doesn't matter
16:03 < HM2> right, 2^16 isn't
16:04 < HM2> but i believe the number of mappings divided by the number of output permutations is always an integer
16:05 < HM2> i'll accept that the inner function will always be imperfect but can't see what the flaw you mention
16:05 < HM2> but i'll stop on about it now anyway, it's an interesting paper
16:05 < sipa> true!
16:06 < HM2> http://www.wolframalpha.com/input/?i=%28%282**n%29%21+%2F+%282**n+-+x%29%21%29+%2F+x%21
16:07 < HM2> ^ i think this shows it'll always be an integer as long as 2^n > x
16:07 < HM2> but i'm not sure
16:09 < sipa> HM2: sure, if you take a uniformly random permutation function from 2^N -> 2^N, apply it to the numbers 0..I, and then sort these numbers, you get a uniformly random permutation
16:09 < sipa> but the point is picking a uniformly random permutation function
16:09 < sipa> if you use a cryptographic primitive there, it will be indistinguishable from one
16:09 < HM2> I don't dispute that
16:10 < sipa> but it won't be one
16:12 < HM2> But i don't think there's an integer multiple requirement on the cipher block size vs the arbitrary domain you want
16:12 < HM2> if that was the case, this entire paper would be useless
16:12 < HM2> the point is to produce a pseudorandom permutation of say, 1 to 10^16 for generating card numbers or such
16:13 < HM2> if you need a cipher that has a multiple of 10^16 as the block size, then you mauy as well start from scratch and use that
16:13 < HM2> it'd be a chicken and egg problem
16:13 < HM2> but maybe you're right, it might be a risk
16:13 < HM2> perhaps the paper only means to imply "good enough" with good primitives
16:15 < sipa> I HAVE NEVER CLAIMED THERE WAS A RISK
16:15 < sipa> that's why i apologize for bringing it up
16:15 < sipa> i just said it's not a perfect shuffle
16:15 <@gmaxwell> he's only saying that the permutations are not equalprobable. This is not ideal. It many not matter in any given application.
16:16 < HM2> sorry sipa, i didn't mean to get things heated
16:16 < sipa> no, i'm sorry!
16:16 <@gmaxwell> sipa: I went through the same thing a week ago with someone (HM2?) on random number selection for some fool lottery.
16:16 < HM2> not me?
16:17 < HM2> unless I've forgotten
16:17 <@gmaxwell> In that case they wanted to generate uniform random 'winners' for the lottery with H()%users.
16:17 < HM2> definitely not me
16:17 <@gmaxwell> in any case, it also ended in tears.
16:18 < HM2> A modulus would definitely cause issues with sizes that weren't factors
16:18 <@gmaxwell> where I basically made the same point sipa made, and they responded like you did here. And then I set their dog on fire.
16:19 < HM2> but this method just maps 2 arbitrary sets and uses the mapping to select a permutation of one set. if the # of mappings mod the number of permutations is 0, then there should be no bias from that alone
16:19 <@gmaxwell> HM2: it's the same issue, but its easier to see where the non-uniformity from % shows up without having to enumerate all the possible keys first.
16:19 < sipa> HM2: absolutely true, but not the point i was making :)
16:19 < HM2> sipa: but i think it's always the case that there's an integer ratio
16:20 < sipa> HM2: yes
16:20 < sipa> that's correct
16:20 < sipa> 22:09:10 < sipa> HM2: sure, if you take a uniformly random permutation function from 2^N -> 2^N, apply it to the numbers 0..I, and  then sort these numbers, you get a uniformly random permutation
16:20 < HM2> hmm
16:20 < sipa> HM2: put otherwise, you have the set S of _all_ function 2^N -> 2^N
16:20 < sipa> you pick one uniformly random from that set
16:21 < sipa> apply that function to the numbers 0..I
16:21 < sipa> sort these numbers
16:21 < HM2> right, yeah I'm sory of with you now
16:21 < sipa> and return the list of 0..I sorted according to that function
16:21 < HM2> *sort
16:21 < sipa> then yes, you have a perfect shuffle
16:22 < sipa> sorry, the set of all permutations 2^N -> 2^N
16:22 < sipa> i don't think it holds for the set of all functions, as may get collisions
16:23 < sipa> and that is what the method in that paper approximates
16:23 < HM2> right, but you don't get collisions in a symmetric block cipher, otherwise they're pretty useless.
16:23 < sipa> indeed
16:23 < sipa> instead of picking a random permution, you pick a random key and use that with a block cipher
16:23 < HM2> right
16:23 < sipa> that will not give you a random permutation, but it will be indistinguishable from one
16:23 < sipa> which is what matters for security
16:23 < HM2> right
16:24 < HM2> it's the "integer multiple" thing that threw me here
16:24 < sipa> well, that's the point
16:24 < HM2> because that's not true, even in the papers own example
16:24 < sipa> that is the reason why it can't be a random permutation
16:24 < sipa> because you started off with a biased set of functions to choose from
16:26 < sipa> just to be clear: i'm not talking about applying the permutation (=block cipher) to the numbers and then sorting
16:26 < sipa> that is absolutely perfect
16:26 < HM2> anyway, this algorithm also sucks because you need O(n) memory and to perform O(n) block cipher encrypt operations
16:26 < sipa> it's the fact that a block cipher with a random key is NOT a random permutation
16:26 < HM2> the paper discusses 2 other algorithms, which I think I best not mention lol
16:27 < HM2> thanks for discussing it with me anyway sipa
16:27 < HM2> you always make me think
16:27 < sipa> :)
16:30 < HM2> On a lighter note, I'm not sure if the FPE wikipedia page has been copied from this paper
16:31 < HM2> Seems to have the same structure
16:31 < HM2> Hopefully not the other way around
17:04 < HM2> chilling for a while now sipa i see some more of your points
17:06 < HM2> a lot of the problem is just the insane amount of entropy in a random shuffle
17:08 < HM2> the old phrase about there being more permutations in a deck of cards than there are atoms in the universe
18:32 < HM2> It seems the Thorp shuffle variant of Feistel ciphering has been proven fairly secure with block ciphers (under standard assumptions) for small domain encryption
18:33 < HM2> It's very intuitive and easy to visualise as well
18:42 < HM2> it reminds me a lot of double-and-add in EC point multiplication
18:42 < HM2> the thorp shuffle that is
18:55 <@gmaxwell> Thorp shuffle sounds like a butterfly network.
18:56 <@gmaxwell> I don't see how it can give uniform permutations in a small (e.g. log N) number of steps though.
18:56 <@gmaxwell> Is there a proof that it does?
18:57 < sipa> link?
18:58 <@gmaxwell> I'm probably looking at the thing that hm2 is looking at: www.cs.ucdavis.edu/~rogaway/papers/thorp.pdf
19:00 <@gmaxwell> (And it sounds like a butterfly network— the kind of topology you use for logN implementations of sorting networks and FFTs)
19:26 < HM2> yeah that's it gmaxwell
19:32 < HM2> I'll have to relookup butterfly networks
19:34 < HM2> Feistel Ciphering looks like it can be applied to elliptic curves. So presumably you could permutate aG to bG using a key, k, and use the same key on the private key (bidirectionally)
19:35 < HM2> I'm not sure how that'd ever be useful though
19:35 < HM2> (one of the papers mentioned EC domains, i'm not just musing)
19:38 < HM2> I guess that's kind of what the hierarchical wallet proposal does, the chain code being the key
19:38 < HM2> except you can only go one way
19:39 < HM2> you can't go from a child public key to a parent key if you know the chaincode
19:40 < HM2> well, unless someone was saying the other day, your permutate all 'i'
19:40 < HM2> so i guess it's more or less the same
19:47 < HM2> the nice properties of ECs seem to make any applications of permutating points kinda pointless
23:37 < amiller> i really like cache oblivious data structures
23:37 < amiller> they all look like fractals
23:38 < amiller> http://www.cs.au.dk/~gerth/papers/alcomft-tr-02-136.pdf
23:38 < amiller> funnel heap is my favourite
--- Log closed Fri Apr 26 00:00:42 2013