Lamport clock can be set far into future making db progress halt

[DanielVF]

The main building block of OriginDB is an ordered log, with the ordering being handled at the protocol level.

However the current ordering by a Lamport Clock can trivially be manipulated by a malicious writer to insert entries into almost any specific location desired in the log. This breaks the rough ordering "guarantees" that the Orbit DB protocol provides.

A malicious user could also set the clock to a high value, say Math.pow(2, 54), which when adding one to in Javascript returns the same number. This would break all future entry ordering on a given database, forever.

[haadcode]

Thank you for reporting the issue @DanielVF! 👍It's great to see that you're looking into the various aspect of the protocol and making sure things work. I truly appreciate you taking the time to tinker and report the issues you find! ❤️

...can trivially be manipulated by a malicious writer to insert entries into almost any specific location desired in the log

The way the orbitdb, the log and generally eventual consistency work is that users can be in different network partitions (say, some of them are offline) but still keep working (ie. make progress from the db perspective). That in turn means that entries can have older timestamps and causal ordering than what other users "see" or know about. Which in turn means that entries can seem to be "added to history" in a way. For example, if I open a database and I'm not connected to the network and have not loaded the db previously, my first entry would also be a "genesis entry" (next pointing to null as I have no knowledge of others) and while others' databases are getting updated (say few hundred entries), upon merging my db with others', mine would be somewhere at the end of the log. This is by design and part of how diverging/converging histories are handled by the log and is not considered malicious and does not break ordering.

However, you're absolutely right that it is possible to have the clock point far to the future (either by malicious intents or per bugs) and this is something we should add a check for.

There are couple of ways we can handle this (cc @aphelionz and @shamb0t):

We can keep the clock ordering in log.values() and add checks where needed for "time skew", ie. check that the clock times are not too far apart when receiving new entries, joining logs, appending to it, etc. and either ignore or throw an error when "known clocks" and "received clocks" are too far apart. We can also consider adding some "upper limit" to the clock time.

Another way, and I think this would be the better approach, is to change the log.values() to traverse the merkle dag causal order, ie. traverse the log going from entry to its next entries as we do in the replication/loading part. This would make sure that even if there was clock skew, new entries would point to the "clock-skewed" entry allowing further progress (ie. to address the Math.pow(2, 54) case).

@aphelionz iirc you wanted to work on the "log loading" part anyways, this would be a good starting point (as they're somewhat related).

@DanielVF I wish you'd reached out to discuss the details before reporting the issue. As it stands now, the report gives an alarming impression to users and is incomplete and partially incorrect. We have guidelines for reporting security issues, but I realize now that they're not obvious in the README and are behind another repo, and this is completely our mistake. However, because these can be tricky to report, it's exactly why we have the guidelines for disclosing security issues.

[DanielVF]

I'll send any future security related issues to the security address, thanks.

You do have some very nice temporal guarantees with the DAG side of Orbit DB. However the DAG side is currently discarded for ordering purposes.

[felixSchl]

Shouldn't it be easy to validate an entry's lamport clock as it's a function of the entries' parents' clocks? Provided you validate all the way to root.

…

On Friday, November 30, 2018, Haad ***@***.***> wrote: Thank you for reporting the issue @DanielVF <https://github.com/DanielVF>! 👍It's great to see that you're looking into the various aspect of the protocol and making sure things work. I truly appreciate you taking the time to tinker and report the issues you find! ❤️ ...can trivially be manipulated by a malicious writer to insert entries into almost any specific location desired in the log The way the orbitdb, the log and generally eventual consistency work is that users can be in different network partitions (say, some of them are offline) but still keep working (ie. make progress from the db perspective). That in turn means that entries can have older timestamps and causal ordering than what other users "see" or know about. Which in turn means that entries can seem to be "added to history" in a way. For example, if I open a database and I'm not connected to the network and have not loaded the db previously, my first entry would also be a "genesis entry" ( next pointing to null as I have no knowledge of others) and while others' databases are getting updated (say few hundred entries), upon merging my db with others', mine would be somewhere at the end of the log. This is by design and part of how diverging/converging histories are handled by the log and is *not considered malicious* and *does not break ordering*. *However*, you're absolutely right that it is possible to have the clock point far *to the future* (either by malicious intents or per bugs) and this is something we should add a check for. There are couple of ways we can handle this (cc @aphelionz <https://github.com/aphelionz> and @shamb0t <https://github.com/shamb0t>): We can keep the clock ordering in log.values() and add checks where needed for "time skew", ie. check that the clock times are not too far apart when receiving new entries, joining logs, appending to it, etc. and either ignore or throw an error when "known clocks" and "received clocks" are too far apart. We can also consider adding some "upper limit" to the clock time. Another way, and I think this would be the better approach, is to change the log.values() to traverse the *merkle dag causal order*, ie. traverse the log <https://github.com/orbitdb/ipfs-log/blob/master/src/log.js#L173> going from entry to its next entries as we do in the replication/loading part. This would make sure that even if there was clock skew, new entries would point to the "clock-skewed" entry allowing further progress (ie. to address the Math.pow(2, 54) case). @aphelionz <https://github.com/aphelionz> iirc you wanted to work on the "log loading" part anyways, this would be a good starting point (as they're somewhat related). @DanielVF <https://github.com/DanielVF> I wish you'd reached out to discuss the details before reporting the issue. As it stands now, the report gives an alarming impression to users and is *incomplete* and partially *incorrect*. We have guidelines for reporting security issues <https://github.com/orbitdb/welcome/blob/master/contributing.md#security-issues>, but I realize now that they're not obvious in the README and are behind another repo, and this is completely our mistake. However, because these can be tricky to report, it's exactly why we have the guidelines for disclosing security issues. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#512 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACk_znTrPak1t1p_l3YVHnGRnif-GKqJks5u0NqZgaJpZM4Y42PC> .

[holmesworcester]

Any update on the DoS issue here? We'd like to ensure that a malicious peer can't trivially DoS every channel they can write to, in our chat app.

[holmesworcester]

Is disallowing entries with a clock value that high sufficient for protecting against this? Is this the user's own clock?

Or a shared clock such that you could set it almost this high and wait for another user to increment it past the limit?

[holmesworcester]

I discussed this with @tabcat and his thoughts were, paraphrasing:

the issue title is a bit misleading since progress wouldn't halt, but ordering may degrade with concurrent operations. since ordering is weighted causal > clock value > writer > entry hash entries could still build on each other. (So if the next message references the malicious entry it would come after.)

We've created an issue for this, just to create a test adding entries with maliciously large clock values and ensuring nothing bad happens: https://github.com/ZbayApp/nectar/issues/84

[DanielVF]

I've love to hear what you find @holmesworcester!