safecoin collusion resistance

[Dan Jasek]

From what I understand:

Safecoins are protected by a set of rules that specify how a safecoin record can be modifed (for example, only the current owner can perform a transaction by changing the owner of the coin).

The vault nodes that store each duplicated copy of the safecoin record will not change the record in a way that violates the rules.

Neighboring nodes will monitor the vault node and will ensure the vault node itself does not try to change the record.

If an attacker controlled a majority of the vault nodes for a given safecoin record, and the attacker controlled all of the neighbor monitoring nodes, would they be able to modify the record and steal the coin?  In practice, how many colluding nodes would this require?

I understand there is an additional safeguard in that it is not possible for an attacker to choose what data its node will store or which nodes are its neighbors.  However, there will be a large number of safecoin records scattered throughout the network.  Has anyone calculated what percentage of the network an attacker would need to control before they would have a high probability of controlling the nodes required to steal a random safecoin?

[David Irvine]

On Sat, Apr 26, 2014 at 8:34 PM, Dan Jasek <d...@jasek.org> wrote:

If an attacker controlled a majority of the vault nodes for a given safecoin record, and the attacker controlled all of the neighbor monitoring nodes, would they be able to modify the record and steal the coin?  In practice, how many colluding nodes would this require?

This is something we have to document better, the number of nodes for such an attack are several orders of magnitude of the total network size in tests. Fraser was running a test of a 3 chain consensus on a 100,000 network and had tried with an attack of 26 or 260 million nodes (I cannot remember, but we stopped the test after about three weeks)· 

We will be running many simulations of this attack, with a group of 2 we did manage to get an attack in a small network but not in a large network (million nodes).  As the network grows this attack becomes more difficult. 

You are right it would be to steal a safecoin, it would be pretty expensive, but we need to keep poking about these consensus groups a little more yet. 

--

David Irvine

maidsafe.net 
twitter: @metaquestions

blog:  http://metaquestions.me

[Fraser Hutchison]

On 26/04/2014 20:39, David Irvine wrote:

On Sat, Apr 26, 2014 at 8:34 PM, Dan Jasek <d...@jasek.org> wrote:

If an attacker controlled a majority of the vault nodes for a given safecoin record, and the attacker controlled all of the neighbor monitoring nodes, would they be able to modify the record and steal the coin?  In practice, how many colluding nodes would this require?

This is something we have to document better, the number of nodes for such an attack are several orders of magnitude of the total network size in tests. Fraser was running a test of a 3 chain consensus on a 100,000 network and had tried with an attack of 26 or 260 million nodes (I cannot remember, but we stopped the test after about three weeks)·

Actually, it wasn't so much an attack of that number of nodes, it was more checking addresses given an attack was under way.  The attacker had only about 8-10% of all the nodes.  I can't remember the rest of the figures off the top of my head - I think I maybe kept them on my work PC, but I'm not sure.

Current plans would require at least 5 groups to be colluding to steal a coin (and to collude, each group would require 3 nodes out of the group of 4 to be malicious), but as David mentioned, we have a few different implementation options here, so those numbers may change.

Cheers,
Fraser.

[Dan Jasek]

I ran some numbers to try to get my head around the feasibility of this attack.  I used Sagemath to calculate the probabilities.  The workspace is attached.

Due to my lack of complete understanding of the safecoin structure, I made some assumptions that may not be accurate.  I hope they are close enough to get in the ballpark:

There are 4.2 billion potential coins, and many fewer nodes in the network.  So, I assume every node on the network has (partial) authority over at least one coin.

I assume the distribution of nodes and the grouping of nodes within the network is completely random.

I start by choosing a single colluding node as the focus of the attack and calculate the probability that colluding nodes are in the correct place to steal a coin assigned to this node.

From here, I assume the target node's group must be controlled, and 4 other specific groups must be controlled as well.  The groups required are entirely based on the target node and are not affected by the status of any other nodes within the network.

Each of the nodes within the relevant groups is randomly chosen to be colluding or not.  For a hit, all 5 groups need at least 3 colluding nodes as members.

For the network described above, to get a 50% chance of controlling a specific single group, would require 61% of the network.  In order to get an 80% chance, you would need control over 78.5% of the network.

In the below graph:

x-axis is the percent of colluding nodes within the network.

y-axis is the odds that any specific group within the network is under control.

When expanding to all 5 groups, it requires 83% for a 50% chance, and 90% of the network for an 80% chance.

Odds of stealing from a specific node against percent of network under control:

Interestingly, groups of size 4  provides maximum resistance against an attack of this type (when requiring a simple majority to control the group).

The size of the network has very little affect on these results.

These are the odds when attempting to steal coins on a specific node, but the attacker would have the opportunity to try the attack against any of his colluding nodes.  The chance of success of this attack against any node in the network will be considerably higher.  I attempted to calculate this as well.  Unfortunately, the results did not make much sense.  I believe the issue is how I am allocating colluding vs trustworthy nodes.  I assumed the distribution is random.  In the real network, there are correlations between the groups.  Groups are allocated based on nearest neighbor calculations, so nearby groups will have shared members.  I don't think this error has a great affect on the above calculations as I expect the 5 nodes involved in a single attack will tend to be logically distant.  As I apply the calculation across the entire network, the error will compound and skew the results.

At this point, I have reached the limit of my probability theory, and my free time.  If I find some time in the future, I will look into building a Monte Carlo simulation using a more accurate network model.

[trak...@gmail.com]

Interesting numbers, but I assume this is about double spending (through collusion with the owner), rather than stealing? To outright steal a (unspent) coin, you would still need the owner's private key, I believe.

I am sure this is clear for everyone on this list already, but I thought it was worth highlighting.

[trak...@gmail.com]

To comment on the actual numbers, it would suggest a higher level of security than proof of work on bitcoin (or other blockchain technologies).

With PoW, I understand that 51% is sufficient to attract/dictate which transactions are added to the blockchain. Less than 51% can still lead to a bad node causing disruption too.

Thanks for taking the time to generate this!

[Benjamin Bollen]

Very nice work.  It already shows you need a larger portion of the total network (compared to bitcoin) to have a chance at controlling a few safecoins.  Comparing to bitcoin you need only 51% of the network to control all of the network with near certainty.

Concerning the private key of the current/previous owner, what prevents an attacker from overwriting the coin with his own signatures for previous and current owner of the coin?  Im just a bit slow in understanding here.

--
You received this message because you are subscribed to the Google Groups "MaidSafe-Development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to maidsafe-develop...@googlegroups.com.
To post to this group, send email to maidsafe-d...@googlegroups.com.
Visit this group at http://groups.google.com/group/maidsafe-development.
To view this discussion on the web, visit https://groups.google.com/d/msgid/maidsafe-development/17674ebd-91d8-4630-86f5-427f37187236%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
<2014-04-28-194647.sagews>

[David Irvine]

On Wed, Apr 30, 2014 at 8:48 AM, Benjamin Bollen <benjami...@gmail.com> wrote:

Concerning the private key of the current/previous owner, what prevents an attacker from overwriting the coin with his own signatures for previous and current owner of the coin?  Im just a bit slow in understanding here.

You are right a new coin could just be created. This is the attack here. The ability to create a coin if you can also create the mining proof (which is a big proof of work in this case). 

Fantastic start on this for sure. We will try and expand on it, Grieg, if you are listening, perhaps we can take this amazing start further.  

--

David Irvine

Secure email and chat: dir...@unseen.is

[Dan Jasek]

On Wednesday, April 30, 2014 1:48:08 AM UTC-6, Benjamin Bollen wrote:

Very nice work.  It already shows you need a larger portion of the total network (compared to bitcoin) to have a chance at controlling a few safecoins.  Comparing to bitcoin you need only 51% of the network to control all of the network with near certainty.

These results are not enough to make any comparisons to bitcoin.  This shows how much control of the network would be required to attack specific set of coins.  The analysis needs to be expanded to the entire network of coins before we can make any conclusive statements.

 

Concerning the private key of the current/previous owner, what prevents an attacker from overwriting the coin with his own signatures for previous and current owner of the coin?  Im just a bit slow in understanding here.

This is the way I understand it.  If an attacker can successful perform this attack, they will be able to overwrite the owner field on the coins and effectively steal them.  They may also be able to create new coins with IDs within the address space that they control.  That will take more work, however.

The saving grace is that the attacker can only affect coins stored on the nodes that they happen to control.  They won't be able to target specific accounts or coins, and they won't have free reign over the network.  A bitcoin 51% style attack where the attacker can re-write history and accept/deny transactions is not possible with safecoin.  Being able to steal random coins within the network is still a pretty bad situation.

[Dan Jasek]

I've got an idea for a solution to the collusion attack.  I'm just spit-balling here, not a fully thought out idea:

What if the entire history of a coin is stored within the network.  Every time a coin is updated, the previous version is encrypted with the new version's hash and stored on the network with proof the owner approved the new version.  You could only find the elements that make up the history by starting with the current coin, the node holding the historical version wouldn't even know that is what it had.

An attacker could overwrite a coin with a brand new coin, but only if they could generate a proof of farming for it.  Even if they did, the correct owner could keep a copy of the real coin and possibly re-claim it from the network.  The older a coin is, the more secure it becomes.  An attacker might get lucky and be able to overwrite one or two historical versions, but they will never be able to practically do this past 3 or 4 transactions.

The network could have a good chance of detecting an attack as well.  Every node checks a coin as it is passed though the routing layer.  If it has a cache of the coin, it checks to ensure the cached coin is a valid ancestor to the current coin.  If not, it throws up an alert and the network attempts to repair the coin.  This could be done efficiently with bloom filters.

In this scenario, a vandal might be able to gain control of a historical version and delete it.  However, this would take a massive amount of resources and would not provide any profit, just cause chaos for the network.

This would be a serious expansion of storage space required for safecoin.  Maybe a paring scheme could be found to drop the history past what is required for security.

It would also make anonymity a bit more of a challenge.  However, as safecoins are stored as coins instead of as accounts, I think it will be much easier to anonymize compared to bitcoin.

[arkana....@gmail.com]

> An attacker could overwrite a coin with a brand new coin, but only if they could generate a proof of farming for it.

They could also just delete the coins they control out of spite.

I have an unrelated question regarding the chain of groups required to update a coin. Assuming a chain User > Pmid Managers > (maybe more groups) >Data manager > Vaults Storing The Token, it seems to me that an attacker can bypass most of the chain instead of taking over each of the group. If the attacker has 3 nodes that store the same coin, then they don't need the Data Managers to know where the data is stored. They just need their Pmid Managers to sign a fake proof of mining. So as far as I can see, an attacker only needs to take over two groups, which considerably weakens the security of the chain, compared to the results of the simulations presented above.

I think this could be fixed easily by attaching to the token the signatures of each of the vaults involved in the chain (I don't think this is what is specified in the current whitepaper). Then, if someone comes up with a different version of the token than the one that is currently stored, we can compare their signatures. The vaults that signed both will be penalized, and we can compare the addresses of the others to see which set is closer to the target addresses.

[David Irvine]

On Tue, May 6, 2014 at 7:31 PM, Jelmer Cnossen <j.cn...@gmail.com> wrote:

Nice simulations. I'm unfamiliar with the current amount of unit tests in the maidsafe codebase, but would it be an idea to add simulations like these into some sort of testing framework? 

If small tweaks to behaviour can already change the security of the network, it seems important to automate testing it. It would certainly help to convince people of the security of maidsafe.

Agreed, we have thousands of tests and working on coverage now as well. It is pretty high and we have some critical tests. It would be nice to somehow wrangle in security simulation tests as you mention. I am not sure simulations, but yes something that guarantees fundamental rules are being followed would be nice (i.e. we have some deterministic tests in common that if they fail the alarms go off as a core algorithm is producing different test vector results). 

Not easy by any means though, bit that does not mean we should shy away from it. We need to give some thought to this one. Such tests would probably require sizeable test networks to check though and that is a fairly large test rig, maybe we could instead have a qa roll out process that created temp sacrificial nodes on willing computers to run some large scale tests. It is something we have discussed a lot, decentralised systems are murder to test though. It's like testing a brain, but yes it is an important point.

--

David Irvine

[Dan Jasek]

The calculations are based on a small number of data points (group size, groups required, etc).  There is not much value in adding them to the unit tests.

However, the next step in this analysis would be Monte Carlo simulations.  This would incorporate the algorithms used to choose the groups used in coin verification.  If the code used in the actual application was abstracted in the correct way, the simulation could use the same code as the application.  Tests could be devised to run the simulations with updated code and verify certain security metrics are maintained.

Monte Carlo simulations are very slow (measured in hours, if we are lucky), so this would probably not belong in the main unit test suite, more likely as a secondary process during release QA.

As far as I can tell, none of the safecoin code has been released yet, so I don't know if this would be feasible or valuable at this point.

[Mark Hughes]

SAFE Distributed Computing facility would be perfect for running Monte Carlo simulations would it not? 

Let the network test itself once it's up! 

Mark

--

My Services & Blog:

http://theWebalyst.com 

Sent from mobile - apols for autoccorrrct & brevit ;-)

--

You received this message because you are subscribed to the Google Groups "MaidSafe-Development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to maidsafe-develop...@googlegroups.com.
To post to this group, send email to maidsafe-d...@googlegroups.com.
Visit this group at http://groups.google.com/group/maidsafe-development.

To view this discussion on the web, visit https://groups.google.com/d/msgid/maidsafe-development/5571443b-15d0-4ae8-a18e-52cb5aab22bb%40googlegroups.com.