use of signatures in secure datastructures

signatures.md

Camlistore is a simple secure datastructure, but it uses signatures in a way that exposes it to implicit trust. camlistore uses one way hashes to link json objects to make immutable datastructures, this is completely fine. But camlistore also uses signatures to make mutable datastructures, but this isn't done in a completely safe way.

To make a mutable datastructure a camlistore user creates a permanode this is just a json object with some entropy in it, and a pointer to the owner (the key who will sign updates). Then, the permanode owner can create claims (which are just signed json objects, that point back at the permanode) with which add or remove attributes from the permanode (things like set a key, or remove a key, add tags, or add something to a set)

Since claims are signed, it's infeasible for an attacker to forge a claim. However, since there is no way to know whether you posses the entire set of claims for that permanode it's entirely possible for a Man In The Middle to manipulate the meaning of the permanode by "forgetting" certain claims. If the owner makes a claim that some key is X, but then another claiming another key is Y, and an attacker could benefit from Y but not X, then that attacker could replicate the claim with Y but not X. Although attackers cannot feasibly forge claims, they can leave claims out.

This problem can be partially resolved by linking the claims into a chain, so that each claim points to the previous claim (ordering claims per owner). Now, if a MITM drops an old claim, that will be detected. However, it's still possible for it drop a new claim.

Nodes can never be sure if they have the latest claims, but they can be sure about what they do have. The best way to avoid this is to replicate through multilpe paths - via a gossip protocol. As long as some honest nodes have the new claim, then they will pass it on one way or another. A MITM cannot fool another node unless it controls all the communication paths to that node.

secure-scuttlebutt uses both pointers to the previous message (messages in ssb are equalivant to claims in camlistore) and a counter on each message. messages thus form a signly linked list.

Your analysis looks right on this. If, barring a keypair compromise, the only MITM attack on an SSB stream is to truncate the stream, then you don't have to worry about consensus either. One honest pathway is enough to thwart the truncate-attack.

Applications ought to be made aware of that vector. Data-freshness can't be assumed, either due to network failure or the truncate-attack. So long as you don't build using freshness/timeliness as an assumption, it should only be an inconvenience.

The mutable KV dictionary object should be a core message type!

I have been building that kv thing (although it's actually a path -> value thing, and you can also link into other people's paths - enough to build a package manager)

I think there are some situations where we actually want the truncate attack. Say someone is harassing me, and I want to block them. I could ask my friends not to relay my information to them, and they would shun that node, pretending that I have just stopped publishing messages. This is essentially a coordinated truncate attack, performed by honest node against a malicious node.

I think it's being able to block a harasser is more important than being able to guarantee freshness.

I have been building that kv thing (although it's actually a path -> value thing, and you can also link into other people's paths - enough to build a package manager)

Ah yeah, I like that idea. Integrating that with attachments would give you the little distributed FS.

I think it's being able to block a harasser is more important than being able to guarantee freshness.

Yeah, I wouldn't want to try to "solve freshness" -- I think that's a matter of physics anyway. You just can't expect freshness naively. For instance, an algorithm which "requires a confirmation message to be published within 5 minutes" might be a bad idea in some case. Anyway, I'm not saying anything that's not obvious.

Oh now that we are discussing it, there is a way you could do it, well not prove freshness, but a way to come up with a number that represents the probability of being in sync.

https://cassandra-shawn.googlecode.com/files/The%20Phi%20Accrual%20Failure%20Detector.pdf

tl;dr based on the frequency of messages from a given node, estimate the probability that another messages has been created by a given time. for example, if a node posts messages daily and you havn't received a new message in a day, then it's 50% chance that a new message exists - after two days it's 75% (or whatever...)

Ah yeah, interesting idea with the failure detector. Again, I'm not sure a truncate attack bothers me that much, but there may be a use-case for this. It may be good for automatically detecting failures in the network for nodes which are not in direct contact (>1 hop away). If the node detects a drop-off in messages from another node, it can begin to query around, and maybe discover that the path relied on a pubkey that was just revoked, for instance.