In several places we do rand.Read(buf); where eventually buf will be sent to the client. I'm suggesting we additionally hash buf = H(buf) after the read. Is this a thing we should do?

See https://trac.torproject.org/projects/tor/ticket/17694

/cc @liamsi

Tor Messenger doesn't handout any identities, and it supports various protocols. In such a case, do we need to provide a way to manage identities of each protocol for the developer?

In the current implementation of CONIKS for Tor Messenger, the CONIKS server stores all the identities of all protocols in the same tree, the key of each user leaf node is formatted as username + '@' + protocol. We probably want a better way.

Or the developers could have multi CONIKS server instances, each of them corresponding to a specific protocol.

** Maybe the title of the issue is incorrect, so I'm glad if someone helps me replace it with a proper title.

Implement the Merkle prefix tree data structure following the most recent version of the CONIKS paper. CONIKS-specific tree node fields should be made general to allow for more general applications.

As @arlolra commented in #48 (comment):

it might be worth abstracting this further into interfaces which the vrf/ and sign/ packages implement, so that using the PAD with other schemes is straightforward.

It also useful to allow the developers to supply theirs own

• hash scheme #6.
• signature scheme.
• VRF

We'd like a more formal specification of this protocol. Related to #33.

What sort of availability does the server need to have? What failure modes does the client have for unreachability? We should probably share some thoughts on these things.

See #33 (comment), #33 (comment), and #72 (comment)

There seems to be a lot of repeated code used for testing (e.g. constructing a tree with 3 entries). It might be worth moving these repeated code segments into appropriate functions into a separate module?

cc @c633 @arlolra

Implement the signed tree root data structure per the most recent version of the CONIKS paper. This includes the hash chain of signed tree roots that forms the history.

See #21 (comment)
Thus, it would make sense to expose a verify() or prove() function for STRs and temporary bindings.

Particularly things like LongToBytes() should be well specified.

The discussion so far is #29 (diff).

From our email discussion:

Right now, the TB extension is very much embedded into the main data structure, but I think it would be more general (and maybe clearer?) to be able to just run coniksserver run --with-tb --with-cosi and for the server to plug in the indicated extensions at run-time.

By sending multiple lookup requests to the server it will block forever. Most probably this is because on lookup the RLocks are never released:

See #39 (comment)

There a few known differences so far:

• Hash of STR sig instead of serialized STR
• Root is an interior node and serializes as the hash its branches
• Integer epochs
• Probably more ...

My vote is for yes, but I'm not sure I have a vote.

The (test-)client command line interface should have the the following functionality:

• register a name-to-key binding
• update a name-to-key-binding
• lookup a key

And deal with all the details/edge-cases that come with that, e.g, dealing with temporary bindings etc

The cli should clarify what a real client would need to implement and what a client would need to know in advance/before doing its first request (like initial public key of the key-server, key-server's epoch duration, or "initial" STR if necessary).

For a start, we omit the possibility to alter the key-change policy (which is currently possible in the java-test client: https://github.com/coniks-sys/coniks-java/blob/master/coniks_test_client/src/main/java/org/coniks/coniks_test_client/TestClient.java#L447)

@masomel said:

I'm thinking it might be better to have a separate TB struct, because the server needs to keep track of all temporary bindings issued during a given epoch, and return a TB whenever a client makes a lookup for a name which may not be in the tree yet but which has been registered/changed.
I think the functionality of keeping track can probably be implemented in the server itself, but I think it would facilitate handling TBs if they had their own struct.

This issues would be a part of #3

Moving this discussion from #1 so it doesn't get lost.

The idea was that Get would return a MerkleNode. And then you'd have another function,

func GenerateProof(mn MerkleNode) []ProofNode {
  var proof []ProofNode
  for mn.parent !== nil {
    proof = preprend(...)
    mn = mn.parent
  }
  return proof
}

@masomel said,

I think it makes sense to separate the Get from the proof generation logic, especially if the lookup returns an EmptyNode whenever the lookup failed, as long as there is still a lookup function that returns the proof node. As we're using the Merkle tree as an authenticated dictionary, the lookups should always return the path along with the value Section 3 [1].

[1] https://dl.acm.org/citation.cfm?doid=2019599.2019602

Some form of sanitized logs will probably be useful for operating the server, at various severity levels.

... you want a different nonce per-user so that you can selectively reveal, the tree nonce is for the whole tree.

It looks to me that salt is also a tree-wide value. This needs to be changed.

@masomel can you elaborate on how you expect this to work?

Currently the server can not take registration requests from outside (only through the bot). We might want to make this behavior optional/configurable such that the server can be run without the registration bot in between:

(Discussion started here: #86 (comment))

See the discussion at #59 (diff)

My bad advice to remove it in https://github.com/coniks-sys/coniks-go/pull/1/files/1f04f1ebb6b0986505ff1b9ae6b8e1a76e78370b#r67399418

We need to make this change,

type ProofNode interface {
    Level() int
    Index() []byte
    Value() []byte
    IsEmpty() bool
-   Commitment() []byte
+   Salt() []byte
}

then the client computes the digest with Salt(), Value(), and the name it looked up.

I think ... need to go back to the paper.

Instead of having to add each new package and subpackage to our .travis.yml file manually to collect the test coverage profiles, we should use a script like https://github.com/dedis/cosi/blob/master/coveralls.sh to handle this automatically.

Profiling PAD.Update() it seems we could do better in regards to memory consumption:

update: cpu usage (update op. only): https://imagebin.ca/v/2q5DJGSE651d
update: mem usage (PAD.Update only): https://imagebin.ca/v/2q778EJzdBxd (Digest should/could be optimized)

(from #16 (comment))

Moving from libconiks-server-go repo.

For the registration protocol, the server needs to handle registration requests, insert the new name-to-key mappings into the tree, and return a temporary binding to the client.

• bots
• client
• crypto
• keyserver
• merkletree
• utils
• protocol

This should address #8 (comment)

We probably want the server to commit the timestamp to the STR, so the client's able to verify the STR was issued in the "right time".
We also want to avoid the clock synchronization issue, maybe the only thing we can trust is that the interval between 2 consecutive epochs are the same for both the client and the server.
See also #80 (comment).

A possible solution is to add an extra field TimeStamp into the Policies, and keep the EpochDeadline as the interval. This way, the client can verify the server's timestamp by checking the saved timestamp with the received timestamp.

Right now, trees are kept in memory, and we're assuming that the user will set up her own storage backend and save the tree. To improve scalability, we should provide hooks for a few popular storage backend. We may also want to provide a mechanism for serializing trees into files on disk for this purpose.

Currently, the private index is computed only using a cryptographic hash. This will also require adding a VRF key field in the STR policy.

From the CoSi paper abstract:

To protect authorities and their clients proactively from undetected exploits and misuse, we introduce CoSi, a scalable witness cosigning protocol ensuring that every authoritative statement is validated and publicly logged by a diverse group of witnesses before any client will accept it. A statement S collectively signed by W witnesses assures clients that S has been seen, and not immediately found erroneous, by those W observers. Even if S is compromised in a fashion not readily detectable by the witnesses, CoSi still guarantees S’s exposure to public scrutiny, forcing secrecy-minded attackers to risk that the compromise will soon be detected by one of the W witnesses. Because clients can verify collective signatures efficiently without communication, CoSi protects clients’ privacy, and offers the first transparency mechanism effective against persistent man-in-the-middle attackers who control a victim’s Internet access, the authority’s secret key, and several witnesses’ secret keys.

We would like to implement CoSi as a protocol extension for CONIKS; here are some benefits we've discussed via email so far:

• you can have multiple participants/parties signing off (a tree-root for instance) and get a single signature at the end. Someone who wants to verify this signature can do so as if it was a single signature, too.
• equivocation could be detected proactively (even before the tree-roots are signed)
• to forge such a signature you would need to control all co-signers instead of a single server (which would be a single point of failure).
• It would simplify the auditing protocol: for clients to be sure that they received the right “world view” they wouldn’t need to contact several auditors as all (or a threshold t of n) auditors have witnessed the same view.
• users in repressive regimes can’t be forced to used state controlled auditors (the regime might censor access to honest ones).

What would the integration look like:

The next STR would be signed by CoSi. The TBs could be a little tricky (but would need to be signed, too). Starting with a threshold of zero could mean that end-clients could ignore CoSi at the beginning.

cc @bford @liamsi @arlolra @c633

Continue the discussion at #64 (comment)

The client needs to provide a mechanism for the user to blow the whistle on the key server if any proof verification fails. Some suggested mechanisms: Post to Twitter (if account linked), post to public web page, disseminate via auditors.

Each user leaf node should be able to map multiple data entries to the key. This is particularly useful for supporting multiple app instances (e.g. on multiple devices).

This doc should detail all client-side operations, including possible attacks and countermeasures.

Protocols covered:

• Registration
• Lookup in current epoch
• Lookup in previous epoch
• Monitoring for current epoch
• Monitoring with missed epochs
• Auditing in current epoch

Should the client have some way of verifying that the index j of the different leaf (or empty node) in a proof of absence is indeed a prefix match for the index i of the key it tried to look up? Without this, a malicious provider could return a valid auth path in the tree as a proof of absence, even though i does exist in the tree, to deny service to the client.

On the other hand, returning the index i for each failed lookup may allow an attacker to slowly enumerate the entire index space.

coniks.org isn't listening on 443, is it?

Discussion started here #43 (comment) (refactor node.level to an unsigned integer value or panic/err if methods that expect a non-negative int receive a negative on; find out which approach is safer/faster/more reasonable).

Also, clarify if and how we want to deal with overflows (also in case of uint(32/64) if we go with unsigned values).

TLS seems overkill when the two processes are on the same machine. If we use sockets, we also don't need to have an open port, which needs firewall protection.

It seems https://github.com/coniks-sys/libconiks-server-go/blob/registration/coniks/internal/util.go re-implements some of the internal util functions. Should some of these functions be exposed to allow reuse?

The size of the library compiled with cgo is little large. We should have some ways to reduce its size.

See #63 (comment)

As an extension to the current STR implementation, it would be useful to allow the developer to supply her own hash scheme, and other developer-specific policies.

This question came out of #39 (comment)

To summarize the discussion:

The signing key needs to be in the policies.

I'm not sure about that. According to the paper, it's not.

In §2.1, we write: "We assume a separate PKI exists for distributing providers’ public keys, which they use to sign authenticated bindings and to transform users’ names for privacy purposes." And later on in §3.3, we write that the VRF key could be part of the policy.

However, the statement from §2.1 makes it sound like neither the signing key nor the VRF key need to be in the policy. In coniks-java, we've been using the server's TLS key for signing the tree roots, so there is at least some established way of handling the rotating the signing key.

I don't know if this is an approach that we would want to take here as well. I actually like @arlolra's suggestion to include the signing key in the policy as well if it's going to be different than the server's TLS key. I'm wondering if we could then use something like certificate transparency to manage our server keys (i.e. the signing key and the VRF key).

This will allow reuse by other libraries (e.g. CONIKS client library).

5ff85ad is an indication that we should have a test that generates a large number of key/val pairs to set and retrieve from the tree.

Currently the key-server doesn't really allow the key-material to change. At least as far as I understood: https://github.com/coniks-sys/coniks-go/blob/master/protocol/directory.go#L91-L97