Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: knightmb on August 02, 2010, 08:44:34 PM



Title: Trojan Time Machine Chain
Post by: knightmb on August 02, 2010, 08:44:34 PM
I've been running some experiments with some isolated BitCoin clients to test for bugs or security issues. So far so good, haven't found anything worthy of discussion here, but I did come across a thought experiment, I figured I would put it out for discussion.

I understand how the core of BitCoin prevents cheating, basically you take the network combined CPU power to generate a chain that rely on math principles to prevent someone from trying to cheat due to that person needing more *corrupt* CPU power than *honest* CPU power out on the network making a direct attack against the block chain too expensive or difficult.

Has anyone thought about what happen if instead of attacking the block chain or math principles that build via CPU time and instead attacked the time itself as a way to produce a *corrupt* chain that could be fitted into the existing clients without needing to defeat all the CPU time it took to produce it? Instead of trying to throw as much CPU power at building a corrupt chain, you instead focus on cheating time to build a corrupt chain?

Would an attack like that really be something to worry about?


Title: Re: Trojan Time Machine Chain
Post by: FreeMoney on August 02, 2010, 11:26:42 PM
I don't quite understand. Do you mean preparing some chain ahead of time then feeding in a bunch of blocks when you get a valid block?

I doubt that's what you mean since the basic idea is that you can't work ahead because you need the hash from the previous block to start working ahead.

How do you cheat time?


Title: Re: Trojan Time Machine Chain
Post by: knightmb on August 03, 2010, 01:10:34 AM
I don't quite understand. Do you mean preparing some chain ahead of time then feeding in a bunch of blocks when you get a valid block?

I doubt that's what you mean since the basic idea is that you can't work ahead because you need the hash from the previous block to start working ahead.

How do you cheat time?
It would be a very slow attack, but basically you grow a block chain with a small private network that is actually churning out blocks every 10 minutes (clients tweaked to go it exactly so there is never a change in difficulty) then after a lot of time (months), you'll have a organic chain that will eventually catch up with the real one and surpass it since the real chain flux around on block creation.

What you are doing is cheating the time within the real block chain to eventually surpass it with a chain that always has perfect expansion. It follows the rules of the protocol and thus when finally introduced to the clients would appear to be a perfectly valid chain from start to finish, except you would literally have 99% of all the bitcoins from your private network under your control.


Title: Re: Trojan Time Machine Chain
Post by: Red on August 03, 2010, 04:55:08 AM
That is a very interesting attack vector!

I was thinking about that longest chain wins bit for a while, however, I presumed (didn't read the code) that there was some memory in the network outside of the "block tree" itself.

For example, I presumed that if at block 7000 everyone calculated the difficulty and the consensus was 250 then this would somehow be remembered as a permanent checkpoint. However, if each fork in the block chain is evaluated in its own relative terms then the vector you suggest seems potentially viable.

It would seem even more viable during two week periods where the main network is decreasing in CPU power. On average the network would be generating less than one block every 10 minutes. Towards the end of the two week period it seems possible that you could substitute your now longer chain for the shorter main one. Thereby erasing any number of transactions that you wanted.

If their is no memory across difficulty reset points, the substitution effect is magnified.



Title: Re: Trojan Time Machine Chain
Post by: knightmb on August 03, 2010, 05:16:14 AM
After testing this all day, this might be a real *theoretical* attack vector.

But I'm not an alarmist, this is what it would take for it to work.

Currently, everyone's client is trying to maintain a "1 block per 10 minutes" average and adjust the difficulty up and down based on how quickly blocks are being generated. The reason the attack *might* be possible is due to the fluctuation in block generation. Basically, it's chaos theory in action and this can be exploited.

Example:
Here are some recent block generation stats
Code:
  756 seconds to find block 71953
  1485 seconds to find block 71952
   252 seconds to find block 71951
   592 seconds to find block 71950
   226 seconds to find block 71949
   310 seconds to find block 71948
Average = 10.08 minutes per block

What my *corrupt* network will be doing is producing a perfect 10 block per minute chain, eventually (months) it will catch up with the real block chain and have a perfect start to finish block chain that is longer than the current block chain being used by all clients. I then take these *corrupt* clients and fuse them into the public network where they have a chain that is significantly longer than what is out there, but the math is perfect from block 1 to the end and by default all the clients will accept this chain, and then they spread it to the next and next, and just like a virus, this new block chain wipes out everyone.

The key part is, as controlling the original PCs that made all those blocks, you end up controlling all the BTC in the system.

This is a very slow attack and instead of attacking with brute force of thousands of servers, you "kill softly" with only a few PCs maintaining a perfect block cadence production over time.

Thus an attack on *time* instead of CPU via chaos. The Trojan is the few PC that are growing the new corrupt network replacement.

I'm going to check the current block chain to see if such an attack is likely, I'll report back my further findings.

In the mean time, I'm not going to panic, I don't expect anyone else to either.


Title: Re: Trojan Time Machine Chain
Post by: Red on August 03, 2010, 06:02:47 AM
Interesting! Are you considering going all the way back to the genesis block?

I was presuming you would just wipe out recent transactions. That would require a shorter effort.

If I had to guess, I would say it would be hard (not impossible) to go all the way back to genesis. The reason I think so is the increasing amount of CPU power over time. Every time the difficulty increases, it is because blocks are generating faster on average than 1 per 10 min. There have been many difficulty increases, so therefore I'm guessing that on average since the launch of the system, blocks have been generated faster than 1 per 10 min. If you are trying to fix your rate at 1 per 10 minutes, it would seem you could never catch up.

Doh! I forgot you can fake time itself! That was the whole point of your title! You can generate blocks as fast as you want from your new genesis block! All you have to do is synchronize your network's fake clocks and fake transactions! You could probably wipe the whole list in days if you tried!

Woot! Nice attack!

Do the nodes not keep the alternate forks incase someone wants to extend them in a chunk later?


Title: Re: Trojan Time Machine Chain
Post by: Anonymous on August 03, 2010, 06:05:46 AM
 :o  that is clever.Is there a way to verify that the current block chain has been generated for an agreed time period?Say it took 1 year to get to the current block length  and your competing block chain only took 2 months?



Title: Re: Trojan Time Machine Chain
Post by: knightmb on August 03, 2010, 06:06:34 AM
Interesting! Are you considering going all the way back to the genesis block?

I was presuming you would just wipe out recent transactions. That would require a shorter effort.

If I had to guess, I would say it would be hard (not impossible) to go all the way back to genesis. The reason I think so is the increasing amount of CPU power over time. Every time the difficulty increases, it is because blocks are generating faster on average than 1 per 10 min. There have been many difficulty increases, so therefore I'm guessing that on average since the launch of the system, blocks have been generated faster than 1 per 10 min. If you are trying to fix your rate at 1 per 10 minutes, it would seem you could never catch up.

Doh! I forgot you can fake time itself! That was the whole point of your title! You can generate blocks as fast as you want from your new genesis block! All you have to do is synchronize your network's fake clocks and fake transactions! You could probably wipe the whole list in days if you tried!

Woot! Nice attack!

Do the nodes not keep the alternate forks incase someone wants to extend them in a chunk later?

I'm not sure, I'm guessing no; if my experiment was any indication since the "real" network wiped out the "fake" network once they synced up.

Think of like this, what would happen if you went back in time a few months with your client the way it is now and connected it to the network? Would everyone not see your client as "the longest chain, most up to date" and sync off of that?


Title: Re: Trojan Time Machine Chain
Post by: knightmb on August 03, 2010, 06:08:59 AM
:o  that is clever.Is there a way to verify that the current block chain has been generated for an agreed time period?Say it took 1 year to get to the current block length  and your competing block chain only took 2 months?

I think there was a post a while back that said the block chain was locked to say example:65,000 blocks in the new release client, but I haven't been able to find that post and didn't find anything in the source that suggested it.

That would be a way to defeat this reverse time attack up to the point of the block snapshot.


Title: Re: Trojan Time Machine Chain
Post by: theymos on August 03, 2010, 06:09:42 AM
It seems that broadcasting your version of block 70,000 or whatever would immediately trigger Reorganize(), which would delete it and make all later blocks invalid. (Assuming I have all the blocks.)

You couldn't modify blocks before ones that are locked in, in any case. (Lockin is at line 1362 of main.cpp.)


Title: Re: Trojan Time Machine Chain
Post by: ArtForz on August 03, 2010, 06:23:47 AM
Won't work.
A block can't have a timestamp earlier than the genesis block.
The hash of the genesis block is hardcoded, so you can't replace that.
Mainline will reject any block more than 2 hours into the future at the time it receives it.
So if your block timestamps are spaced exactly 600 sec apart to stay at 1.0 difficulty, you'll be "too far into the future" long before your block chain is anywhere near as long as the real one.


Title: Re: Trojan Time Machine Chain
Post by: knightmb on August 03, 2010, 06:36:15 AM
It seems that broadcasting your version of block 70,000 or whatever would immediately trigger Reorganize(), which would delete it and make all later blocks invalid. (Assuming I have all the blocks.)

You couldn't modify blocks before ones that are locked in, in any case. (Lockin is at line 1362 of main.cpp.)
That's what I was looking for. It's locked along the way with hard-coded hash values, that makes this vector of attack null.

Glad someone already figured this out long ago and locked it in the code.

It was a fun exercise in code review at least.  ;)


Title: Re: Trojan Time Machine Chain
Post by: Red on August 03, 2010, 07:08:45 AM
That's what I was looking for. It's locked along the way with hard-coded hash values, that makes this vector of attack null.

Just because I'm lazy and don't have the code on this machine...

You're saying the hash recorded independently by each node outside the block chain?
Where is the check-point hash stored and how often?


Title: Re: Trojan Time Machine Chain
Post by: Ground Loop on August 03, 2010, 07:09:25 AM
If I remember right, the "lock in" of checkpoints is a relatively new thing in the client.


Title: Re: Trojan Time Machine Chain
Post by: FreeMoney on August 03, 2010, 07:33:02 AM
Why can't you start working from the lockin? Ah, because you don't get the difficult set back to 1 that way.


Title: Re: Trojan Time Machine Chain
Post by: knightmb on August 03, 2010, 08:13:56 AM
That's what I was looking for. It's locked along the way with hard-coded hash values, that makes this vector of attack null.

Just because I'm lazy and don't have the code on this machine...

You're saying the hash recorded independently by each node outside the block chain?
Where is the check-point hash stored and how often?
It's located in the code like this. Basically, a block is picked (in this case, the last one was 70567) and the client checks against that point forward. So if you attempt to modify the chain along the way (as what I was doing) at some point, it wouldn't match up properly and the current clients would reject it as fake.

The only attack would be to generate from the last snap-shop, but with the difficulty so high from that point, CPU time becomes too expensive.
Code:
    // Check that the block chain matches the known block chain up to a checkpoint
    if (pindexPrev->nHeight+1 == 11111 && hash != uint256("0x0000000069e244f73d78e8fd29ba2fd2ed618bd6fa2ee92559f542fdb26e7c1d"))
        return error("AcceptBlock() : rejected by checkpoint lockin at 11111");
    if (pindexPrev->nHeight+1 == 33333 && hash != uint256("0x000000002dd5588a74784eaa7ab0507a18ad16a236e7b1ce69f00d7ddfb5d0a6"))
        return error("AcceptBlock() : rejected by checkpoint lockin at 33333");
    if (pindexPrev->nHeight+1 == 68555 && hash != uint256("0x00000000001e1b4903550a0b96e9a9405c8a95f387162e4944e8d9fbe501cd6a"))
        return error("AcceptBlock() : rejected by checkpoint lockin at 68555");
    if (pindexPrev->nHeight+1 == 70567 && hash != uint256("0x00000000006a49b14bcf27462068f1264c961f11fa2e0eddd2be0791e1d4124a"))
        return error("AcceptBlock() : rejected by checkpoint lockin at 70567");


Title: Re: Trojan Time Machine Chain
Post by: knightmb on August 03, 2010, 08:15:23 AM
Why can't you start working from the lockin? Ah, because you don't get the difficult set back to 1 that way.
Exactly, you start at 244 for example and a few machines won't ever generate enough blocks to overtake the correct chain since it's being powered by thousands of clients now.


Title: Re: Trojan Time Machine Chain
Post by: theymos on August 03, 2010, 08:32:38 AM
Just because I'm lazy and don't have the code on this machine...

You're saying the hash recorded independently by each node outside the block chain?
Where is the check-point hash stored and how often?

Satoshi includes the hash of a recent block in the code every once in a while. It's not done by each node. Right now, all blocks up to 70,567 are protected from modification.

This isn't to prevent any particular attack, but just as a "safety net" that will allow most transactions to be preserved in any possible case. Even without the checkpoints, you would never get ahead of the real chain with this attack.

Edit: I added this attack to the wiki's weaknesses (http://www.bitcoin.org/wiki/doku.php?id=weaknesses) article.


Title: Re: Trojan Time Machine Chain
Post by: Red on August 03, 2010, 02:08:44 PM
Thanks guys! Sorry to be lazy!


Title: Re: Trojan Time Machine Chain
Post by: Olipro on August 03, 2010, 02:26:55 PM
I'm not quite sure how this attack can work because it has the following pre-requisites:

1) that you can generate blocks faster than the rest of the network

2) that you can do so without being subject to the same target modification rules

As I see it, assuming you have so much processing power that you can outpace the network, when you are doing your block generation, you will still have to adjust the target using the same algorithm or when you start posting your blocks to the network, they're going to get rejected because you weren't obeying the target value rules, therefore, I don't see how you could actually permit yourself to generate blocks more cheaply by not announcing them.


Title: Re: Trojan Time Machine Chain
Post by: knightmb on August 03, 2010, 02:33:04 PM
I'm not quite sure how this attack can work because it has the following pre-requisites:

1) that you can generate blocks faster than the rest of the network

2) that you can do so without being subject to the same target modification rules

As I see it, assuming you have so much processing power that you can outpace the network, when you are doing your block generation, you will still have to adjust the target using the same algorithm or when you start posting your blocks to the network, they're going to get rejected because you weren't obeying the target value rules, therefore, I don't see how you could actually permit yourself to generate blocks more cheaply by not announcing them.
Connect two PC together with the -connect=XXX.XXX.XXX.XXX command line to both machines with a fresh install, and both will start generating blocks from the genesis block and start building up the network again. Get enough PC going, you'll be able to keep the 1 per 10 minutes generation up to a constant level since the difficulty will always be a 1.000

After a while, you would have a perfect block chain from to finish in which those two PCs own all the coin and with the constant generation rate, overtake the flux rates that are seen out in the public network (where one block takes 8,000 seconds to find sometimes, your little network is doing a constant block every 300 seconds, eventually it would catch up and surpass the real chain)


Title: Re: Trojan Time Machine Chain
Post by: ArtForz on August 03, 2010, 03:12:29 PM
Looks like "best block chain" does not simply mean "longest chain of blocks" but "highest sum of difficulty".
check main.cpp CBlock::AddToBlockIndex
Code:
pindexNew->bnChainWork = (pindexNew->pprev ? pindexNew->pprev->bnChainWork : 0) + pindexNew->GetBlockWork()
...
if (pindexNew->bnChainWork > bnBestChainWork)
...
now, what does GetBlockWork() do?
main.h
Code:
    CBigNum GetBlockWork() const
    {
        return (CBigNum(1)<<256) / (CBigNum().SetCompact(nBits)+1);
    }
So a single block of the real chain at 200 difficulty is "worth" 200 blocks of your 1.0 chain...


Title: Re: Trojan Time Machine Chain
Post by: Olipro on August 03, 2010, 03:37:32 PM
I'm not quite sure how this attack can work because it has the following pre-requisites:

1) that you can generate blocks faster than the rest of the network

2) that you can do so without being subject to the same target modification rules

As I see it, assuming you have so much processing power that you can outpace the network, when you are doing your block generation, you will still have to adjust the target using the same algorithm or when you start posting your blocks to the network, they're going to get rejected because you weren't obeying the target value rules, therefore, I don't see how you could actually permit yourself to generate blocks more cheaply by not announcing them.
Connect two PC together with the -connect=XXX.XXX.XXX.XXX command line to both machines with a fresh install, and both will start generating blocks from the genesis block and start building up the network again. Get enough PC going, you'll be able to keep the 1 per 10 minutes generation up to a constant level since the difficulty will always be a 1.000

After a while, you would have a perfect block chain from to finish in which those two PCs own all the coin and with the constant generation rate, overtake the flux rates that are seen out in the public network (where one block takes 8,000 seconds to find sometimes, your little network is doing a constant block every 300 seconds, eventually it would catch up and surpass the real chain)

precisely, and the hashes you generate are going to be completely invalid because the target your systems are aiming for will be higher than the one the network requires.


Title: Re: Trojan Time Machine Chain
Post by: knightmb on August 03, 2010, 03:43:15 PM
Looks like "best block chain" does not simply mean "longest chain of blocks" but "highest sum of difficulty".
check main.cpp CBlock::AddToBlockIndex
Code:
pindexNew->bnChainWork = (pindexNew->pprev ? pindexNew->pprev->bnChainWork : 0) + pindexNew->GetBlockWork()
...
if (pindexNew->bnChainWork > bnBestChainWork)
...
now, what does GetBlockWork() do?
main.h
Code:
    CBigNum GetBlockWork() const
    {
        return (CBigNum(1)<<256) / (CBigNum().SetCompact(nBits)+1);
    }
So a single block of the real chain at 200 difficulty is "worth" 200 blocks of your 1.0 chain...
Cool, actually a double-wham to the attack then because it's worth is better defined by how much CPU time it took to create it, thanks for pointing that out.