01:09:40Taek:Is 56 bits enough? The Bitcoin network does 2^67 hashes every block. Someone with 1% of that hashing power can crack a 56 bit password minute. It's stronger if you use multiple iterations, which might be enough for the average person
01:09:57Taek:It's not something that I would trust more than a few thousand dollars to though
01:10:36Taek:*56 bit password every minute
01:11:38Luke-Jr:Taek: mining chips can't crack passwords in any case
01:11:51maaku:maybe you remember two passwords?
01:13:02Taek:How hard would it be to manufacture a password cracking sha2 ASIC given that bitcoin mining asics exist? I legitimately don't know.
01:14:47phantomcircuit:Luke-Jr, very very specific passwords
01:14:48phantomcircuit:heh
01:15:14phantomcircuit:Taek, it costs >3m to do a 28nm asic
01:15:22phantomcircuit:the question isn't how hard, but how expensive
01:17:18Taek:that's convincingly expensive to me. I remember that you can skip the final 3 rounds of sha2 when doing Bitcoin mining, something I imagine most of the ASICs do. Wouldn't that make it essentially useless for passwords though, even if they did the same double hashing as Bitcoin?
01:18:07Luke-Jr:Taek: nah, the host CPU can do the full hash over for good guesses
01:19:08Taek:oh that makes sense
01:20:39phantomcircuit:Taek, you could repurpose bitcoin miners to brute force passwords which are hashed with sha256d which start with 32bits of leading zeros and which are a fixed 64 byte length
01:23:17kanzure:"given that bitcoin mining asics exist" has nothing to do with it, i would say just as easy as before.
01:23:44kanzure:and of course, not all asics require 28nm or $3M
01:24:14phantomcircuit:kanzure, sure for a couple hundred grand you can do 180nm
01:24:57kanzure:there was at least one company offering $3k per run but you'd get like half a wafer and >200nm feature sizes
01:25:11kanzure:but they would also do packaging for you and stuff.
01:25:13phantomcircuit:i've actually considered getting a 180nm fpga with static components to accelerate common hash algorithms to mess wtih altcoins
01:25:32phantomcircuit:kanzure, shared wafer lots
01:25:37phantomcircuit:those can take a long long time
01:25:43kanzure:oh, how long?
01:25:48phantomcircuit:indefinite
01:25:53kanzure:what?
01:25:56phantomcircuit:they wait to have enough people to do a full lot
01:26:08phantomcircuit:so you could be waiting foreve
01:26:09phantomcircuit:r
01:26:42kanzure:weird, i would have guessed there's more demand for partial wafer lots etc and they would fill up fast
01:27:20kanzure:i should put together a verilog or vhdl library of bitcoin stuff. hrm.
01:29:05phantomcircuit:kanzure, they do tend to fill up relatively quickly
01:29:10phantomcircuit:so it's mostly not an issue
01:29:22kanzure:meh? https://github.com/progranism/Open-Source-FPGA-Bitcoin-Miner/tree/master/src
01:29:52phantomcircuit:but it's still going to add some delay to a process that already takes minimum 45 days and average 60
01:52:10maaku:maaku is now known as Guest20595
01:58:01Guest20595:Guest20595 is now known as maaku
02:15:10justanotheruser:justanotheruser is now known as senpai-san
02:16:14senpai-san:senpai-san is now known as justanotheruser
02:56:12maaku:maaku is now known as Guest15747
03:26:03Guest15747:Guest15747 is now known as maaku
03:55:40zooko`:zooko` is now known as zooko
04:50:21maaku:maaku is now known as Guest14231
05:44:52kanzure:leaderless byzantine paxos http://research.microsoft.com/en-us/um/people/lamport/pubs/disc-leaderless-web.pdf
05:46:49Taek:long ass paper
05:47:19kanzure:brevity is the soul of not wasting my time, etc
05:49:17Taek:I actually really like reading Lamport. I find he gets the point across better than most writers.
06:43:38wyager:wyager has left #bitcoin-wizards
06:50:22fanquake:fanquake has left #bitcoin-wizards
08:05:14card.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:14card.freenode.net:Users on #bitcoin-wizards: andy-logbot ebfull Guyver2 profreid Adlai pen d4de^^ MoALTz__ mortale Dr-G TheSeven rdponticelli aburan28 c0rw1n_ RoboTeddy drawingthesun DoctorBTC p15 vmatekole Graftec Luke-Jr zenojis justanotheruser zwischenzug2 jtimon devrandom spinza copumpkin DougieBot5000 Max_H3adr00m EasyAt wizkid057 gavinandresen NewLiberty eristisk gribble go1111111 nuke1989 MRL-Relay artilectinc shesek epscy rfreeman_w wiretapped altoz koshii HaltingState Aquent Emcy
08:05:14card.freenode.net:Users on #bitcoin-wizards: hollandais tromp_ dansmith_btc2 super3 Guest29578 nanotube Starduster burcin SDCDev Meeh LarsLarsen samson_ pi07r optimator_ stonecoldpat wumpus Grishnakh mmozeiko jgarzik Nightwolf grubles berndj forrestv asoltys [d__d] livegnik reick nsh Dyaheon Sangheili Fistful_of_coins myeagleflies SomeoneWeird Krellan CryptOprah emsid harrow throughnothing abc56889 lechuga_ phedny @ChanServ fluffypony mr_burdell Apocalyptic kinlo midnightmagic starsoccer so
08:05:14card.freenode.net:Users on #bitcoin-wizards: ahmed_ Gnosis Keefe pajarillo roasbeef ryan-c otoburb helo [Tristan] TD-Linux catcow danneu UukGoblin poggy coryfields kgk btc_ crescendo amiller Eliel zibbo_ jbenet mappum yoleaux firepacket jrayhawk_ Hunger-- Muis Kretchfoop weex bbrittain tromp michagogo artifexd sl01 @gwillen Graet BlueMatt smooth CodeShark digitalmagus BrainOverfl0w espes__ waxwing BigBitz petertodd bobke andytoshi a5m0 heath kumavis phantomcircuit K1773R Alanius hguux
08:05:14card.freenode.net:Users on #bitcoin-wizards: dgenr8 lnovy LaptopZZ_ _2539 kanzure Taek gmaxwell sipa pigeons [\\\] coryfields_ Logicwax warren arowser HM Anduck NikolaiToryzin comboy [Derek] Iriez
12:14:48Pan0ram1x:Pan0ram1x is now known as Guest21768
17:02:21kanzure:hmm andrychowicz/dziembowski are also looking towards the rational cryptography approach, http://eprint.iacr.org/2014/796.pdf
17:03:04kanzure:"In his paper Bahack shows than an adversary can discard a block on any depth with a probability 1 regardless of his computational power if he is willing to wait long enough."
17:10:55kanzure:a little off-topic, http://blanu.net/curious_yellow.html "The primary strategy behind the Warhol superworm is to pre-scan the network for vulnerable targets. When the worm is launched it already has a large list of targets with a known method for infection and can therefore quickly infect an initial seed population. One thing which the Warhol paper mentions is that better results might be achieved via a coordinated worm in which various ...
17:11:01kanzure:... instances of the worm on different computers communicate with each other in order to optimize infection. The Warhol paper states, however, that no coordinated worm has ever been created. This paper proposes the first design for a worm which utilizes efficient communication between worm instances for an optimal infection strategy."
17:22:02wumpus:one drawback (from the worm's perspective) of that would be that other software could pretend that they're worm instances, and thus confuse and disrupt the worm's strategy
17:34:17amiller:kanzure, weird, that andrychowicz/dziembowski paper has basically exactly the same results and model as what i just submitted to eurocrypt.
17:34:34amiller:(neither of which has anything to do with rational crypto though)
17:34:47kanzure:oh, they mention it, that's all i meant
17:48:11kanzure:wumpus: worms would be authenticated i think
18:02:41andytoshi:i'd bet you could pull a key out of a worm if it had one
18:05:22kanzure:part of that page/article explains something about protecting an infected node because obv. it was just vulnerable to your own worm
18:10:56fenn:fenn has left #bitcoin-wizards
18:33:20myeagleflies:myeagleflies has left #bitcoin-wizards
19:19:52gmaxwell:kanzure: this is that approach that assumes hashpower (for the defenders and attackers) increases exponentially forever, and only obtains a non-negligible probablity in the limit and not over any remotely sane timeframe (like 1000 years)?
19:21:04kanzure:that's what i assumed when i saw it referenced, but i haven't confirmed
19:28:58gmaxwell:If so, it's something that I found intellectually very interesting, but it seemed to be of no pratical interest itself.
19:31:54kanzure:agreed, i'm more surprised that someone has already bothered to work out the exact scenario or w/e
19:35:10amiller:it's totally false that that attack has a negligible probability over a finite time frame
19:38:24c0rw1n_:c0rw1n_ is now known as c0rw1n
19:40:01amiller:(it's not even clear here what you would want "negligible" to mean here, because the attack does not involve hash collisions so there's no security parameter, and the strength of the attacker is denoted by a hashpower fraction p rather than some poly(k) function)
19:41:30amiller:"Her chances of succeeding are about ∆·p / (t−2015)"
19:41:52amiller:p is the attacker's strength (as a fraction of the honest rest of the network)
19:41:55gmaxwell:amiller: yes. this is attacker has 0.0001% of the hashpower forever, and the hashpower goes up exponentially forever (physically impossible). What I mean by negligible was that I ran numbers for some things assuming e.g. 1000 years and still ended up with success probablities under 1/2^128.
19:43:06amiller:okay the expression for the success probability in a finite time is for constant hashpower, no assumptoin about it going up
19:43:28gmaxwell:it's quite surprising and curious that they go up over time, but didn't seem to be consequential in any real sense. (Since external processes will effortless reject a 1 year rewrite, much less a 1000 year one; so ... why bother trying?)
19:43:36amiller:they only bring up increasing hashpower in the last paragraph, it's not required for the finite time probability
19:43:37gmaxwell:Okay then this is a different argument than the one I'm aware of.
19:44:44amiller:the paper presents the attack in sort of increasing complexity as it models more of the practical countermeasures bitcoin has for this
19:45:54amiller:to understand the basic attack, suppose the attacker can set choose an arbitrarily high difficulty for bocks he mines
19:47:01amiller:also suppose he has 10% of the hashpower, that he wants to rewind history to a point 1 month ago (from the time that the attack starts), and he wants to succeed at this by 1 month from now.
19:47:26amiller:on average it takes the adversary 20 months to build a chain with 2 months of work, regardless of the difficulty, right?
19:48:38amiller:but to succeed at this attack he has to find a *single* 2 month block in only 1 month, which is in like 5% of the expected amount of time
19:49:59amiller:he has roughly a 1/20 chance of attack success.
19:50:48amiller:1-poisson.cdf(0,0.05) = ~0.049
19:51:31amiller:(that's the probability of finding at least 1 block in 0.05 of the mean time to find a block)
19:51:35gmaxwell:I follow that. Yep. So how does this bridge to Bitcoin? The paper I read before on the diff ramping attack still required exp hashrate growth because the fixed retargeting windows meant the network still made progress.
19:52:16gmaxwell:(and so it needed the growth so the attacker could wipe out his past losses with constant probablity no matter how far behind he'd fallen)
19:52:44amiller:yes they introduce that (goofy) assumption so they can claim a finite "mean time to success"
19:53:08amiller:if that assumption isn't in place, the average amount of time to successfully revert to a fixed point in history is infinite... however the median time is finite
19:53:19amiller:meaning there's a finite time where the attack succeeds with probaility 50%
19:55:43gmaxwell:(the paper I'm thinking actually uses it to prove p=1 in the limit, ... but its not useful :) )
19:56:12amiller:yeah we're talking about the same paper i think... http://arxiv.org/pdf/1312.7013.pdf
19:57:25gmaxwell:yep. K.
19:59:20kanzure:is there anything in the current bitcoind that rejects a 1 year rewrite, other than existing checkpoints?
20:01:05amiller:okay so because the difficulty by a factor of 4 each time, the attacker has to spend a lot more time just to increase the difficulty enough. But still the attacker has a probability of success in a finite time interval that's basically proportional to his hashpower, and the finite amount of time he's willing to try for
20:01:19amiller:even with the network having constant hashpwoer.
20:05:01gmaxwell:(well not 'each time' he has to mine 2016 blocks at the current difficulty, this is part of how I can't see that it ever reaches 50% success probablity, since there is progress enforced by the difficulty changing)
20:06:38amiller:if the 10% attacker starts today, he can create a fork with increased difficulty at the tip every 20 weeks (yes, admittedly that's already pretty impractical!)... let's say he spends a year and does this twice
20:07:31amiller:er... that's still not good, he's a year behind, and the 16x difficulty only lets him clear less than a year with a single block.
20:08:17amiller:how about he spends 60 weeks (a year and two months) but now he has a fork with 64x difficulty, which lets him clear 2 years in a single lucky block
20:10:18amiller:so, he spends an average of 1 year grinding on his fork to increase the difficulty to 64x, then he spends 1 year hoping to get a lucky block at that difficulty.... which again he can succeed at with probability 1/20 or so
20:10:25gmaxwell:there are around 52k blocks in a year, so you need a diff of roughly 100k higher to clear two years in a single lucky block.
20:10:49amiller:oh, crap yeah i messed up with 2 weeks instead of 10 minutes sheesh
20:11:53gmaxwell:bbiaf
20:18:40amiller:hmmm right i calculated that wrong anyway...
20:24:24amiller:okay i think you're right here, so it takes an attacker with constant hashpower something like 4^k time (also with very low variance) to increase the difficulty by 4^k... ok i'd have to work that out more
20:28:03amiller:maybe this is more fun with like a 49% attacker that doesn't fall that much behind.
20:29:50amiller:bbl
21:08:02Taek:The attacker in the DRA needs to find 2016 blocks at a given difficulty to push the difficulty up 4x
21:08:20Taek:Each time the attacker does this, it will take E(4x) longer than the last time
21:08:38Taek:which means the dominant term is the current 2016 blocks
21:09:11Taek:So the attacker only needs to get lucky on one set of 2016 blocks to be able to make up for all of the lost time
21:09:53Taek:Meaning the attacker can just keep driving the difficulty up and starting over
21:10:30Taek:In the meantime, the honest network is producing an exponential number of blocks with regards to the attackers re-rolls
21:11:33Taek:But getting lucky over the space of 2016 blocks seems very unlikely
21:12:40Taek:and has the attacker investing an exponential amount of time per retry
21:15:35Taek:Assuming the attacker has 40% total hashing power, remaining network has 60% (attacker is 2/3 strength of remaining network)
21:17:19Taek:The attacker needs to create 1008 blocks to catch up with his work from the previous tries, and 1008/3 blocks to catch up from being 1/3 less powerful
21:19:26Taek:So if the attacker can make 2016 blocks in the amount of time where you'd expect to see ~650, then the attacker succeeds in getting ahead
21:19:53Taek:So at 40% strength, the attacker just needs to raise the difficulty until he can create 2016 blocks in the space where you'd expect to see 650
21:33:06Taek:using a poisson distribution (perhaps incorrectly), I'm getting a 10^-400 chance of success per retry
21:33:21Taek:needing to spend an approximate eternity, even at 40% hashing power
22:03:20amiller:i still think that's not the right way to look at it
22:03:30amiller:suppose the attacker doesn't want to rewrite a particular point in history
22:03:51amiller:but just wants to pull off a history revision attack that's X blocks long (from whatever the front of the main chain is when the attack succeeds)
22:05:08amiller:the point is the attacker can put in exactly the expected amount of work to increase the difficulty, and then has to get lucky on only the blocks after that
22:07:19Taek:Right how *how* lucky is important
22:07:33Taek:the longer the attacker takes to increase the difficulty, the luckier they have to get
22:07:50Taek:and each time they don't get lucky, they have that much more work to do catchup with
22:08:14Taek:*but how lucky
22:09:04Taek:so you have to keep driving up the difficulty as you fail to get lucky or you just fall behind from your unlucky attempts
22:16:30amiller:if you want to rewind history to a fixed date, then it gets more and more unlikely because you fall behind yeah
22:17:18amiller:but if you want to make *some* rewinding attack that rewinds T amount of history, then your probability of success each time you make a finite attempt is nonnegligible in T
22:20:13Taek:ok that makes sense. But then each time you have to start over in pushing the difficulty up?
22:20:38Taek:And all the mining from a failed attempt just goes to waste? (you can't get a reward?)
22:32:23amiller:Taek, yeah absolutely.
22:32:24amiller:it's still a pretty crappy and unrealistic attack, but it's not "negligible" in one way you'd want it to be
22:32:25amiller:i think the blck ramping cap is a pretty good defense.
23:15:55midnightmagic:
23:21:28andytoshi: