security review of dark-crystal

forked from Dev Diary 02.11.2018 / Coconut Death

I started by doing a quick search for known vulnerabilities, found some vulnerabilities in SSS described on this page and also this paper: how not to share a secret (I didn't bother to try understand all the math, just using it for hints)

1. small metadata leak: length of the secret is revealed (solution: pad the secret)
2. possible for participant to return the wrong share, which means the correct secret is not recovered.
3. If the secret isn't very strong, like "password", it may be possible to confirm a guess just using a single share.
4. If two different shares have some relation (such as one being a known multiple of the other) then the other secret can be derived from the first.

Note: the last two are partly me reading between the lines of that paper, which I quickly skimmed. I'm not staking my reputation on those being true, by the following suggestions I have will cover this just in case they are true. Better safe than sorry.

dark-crystal is a key building block for ssb applications, and I believe, usable security applications in general. We want it to be rock solid, so that it does exactly what it says on the tin and you do not have to understand internal details in order to use it safely. This last point is extremely important and I'd be disapointed if any ssb crypto did not have this property.

Most of the above problems can be fixed using a layer of symmetric crypto. As I suggested in the forked-from-thread sharing a random key, and using that to symmetrically encrypt the actual secret. too-long secrets is currently a problem, but encrypting the secret symmetrically does not have much overhead - 16 additional bytes for the mac + the secret size, and the size of the share will always be the same.

key = randomBytes(32)
shares = createShares(key, N, threashold).map(function (share) {
  //give each share a different encryption, also makes it not obvious two shares are for the
  //same secret. it's okay to use the same key again if the nonce is different, so we use
  //the hash of the share.
  return share + secretbox(secret, key, hash(share))
})

Metadata - problem 1, this is not really a very big problem, regular ssb messages private messages don't hide the length. if you wanted could instead have the encrypted secret be between the true size and twice that size. secretbox([secret.length, secret, randomBytes(secret.length*random())

The library used left-pads the secret to be shared with ascii zeros then "1" then the secret,
so that it's possible to distinguish between padding and secret. Since it's padded with zeros,
this protects against metadata (1) but not against 3 (confirming a guess at bad secret) since it doesn't increase the entropy. It would be much better to pad with random data.

But, we should first consider 3, and 4 - problems where mathematical properties of the secret leaks through. problems like this are typical of number theory based cryptography. 3 (weak secret) is easily fixed by sharing a known strong secret (one the system has generated, not one the user has provided). This also prevents 4 (interaction between mathematically related secrets)

One problem that dark-crystal currently has, is that it does not store the current quorum size, which means when reconstructing the secret you need some way to detect whether you've got it. this is mentioned in "possible enhancements" section of the library. Using libsodium's secretbox solves this problem, because a mac is attached to the secret, so it either returns the plaintext or fails.

Based on my current understanding of secret sharing (this morning's work) that may mitigate problem 3 (note: in a security context "mitigate" means reduce a risk or make a problem less bad, remediate means remove the problem entirely). meaning if you have a k/N secret, and 1 peer returns the wrong secret, it won't open with k/N, but if you get another honest share (now you have k+1 shares) you can just try k times, excluding each share until you successfully decrypt.

Remembering the secret has two parts - the shamir share, and the symmetric part. As long as one peer returns the correct symmetric part, you will be able to decrypt that. As long as you have k/N shamir shares. For any k, trying to combine every k-1 ... 1 possibilities will not be a scalability problem because the order of the shares does not matter.

Okay, I'm gonna look at the paper on authenticated sharing and see if that is better...

update: shamir secret sharing is post quantum that's good news, and I now suspect that 3 (weak password) probably isn't a problem.

Hmm, the paper I read how-not-to-share-a-secret.pdf is actually about a different scheme to shamir's, that seems to allow sharing multiple sets of secrets at once.

reading Detection and identification of cheaters in (t,n) secret sharing scheme detection-of-cheaters-in-sss.pdf

outlines 3 attacks/problems

1. a peer returns an incorrect share by accident (for example, because of a bug)
2. malicious peers generating incorrect shares, but without having the chance to see any honest shares first.
3. as in 2, except attackers have the chance to see what honest peers reveal first.

3 is obviously a lower bar (thus easier to attack than 2) and is also more relevant to dark-crystal.

Hmm, okay I don't fully understand this paper (too many cryptic math symbols) but they claim they detect cheating in O(1) and detect who the cheat is in O(j!) (I think j is the number of cheaters). j factorial is pretty big, but okay since j is small. It's the same as my suggestion would be though. (I need to look at this more though)

revoking trust - deleting shares

in my research, I also encountered the idea of renewed shares. This allows you to remove someone from the set of shares. I strongly recommend that dark-crystal adds this to the roadmap.

Trust is not a permanent state - I think it is important that if you can give trust you can also take it back easily. For example - say you share something with your partner - but then go through a difficult breakup - maybe you'd want your security to not depend on them anymore. Another example - one of your shares looses their device -- possibly stolen. Now a potential attacker has one share.

Solution: update the rest of the shares (any maybe add a new peer). If the peers delete then gets hold of one of the new shares, well it cannot be combined with any of the old shares! So the attacker has to acquire a quorum of shares before anyone suspects anything.

The neat thing here when you revoke trust in a share, that share holder doesn't have to do anything. Instead, the share holders you still trust replace the share, and that is enough!

Since ssb is on the record, we can't directly delete shares - but we can if we encrypt them to an ephemeral key.

Something like this:

Alice sends a request to Bob, "hi Bob, can you look after a secret share for me?"
Bob replies "yes, encrypt it to this ephemeral public key bob_e". Bob's stores this key on disk, for now.
Alice also generates an ephemeral key, alice_e and encrypts the share, sending bob alice_e.public, secretbox(share_bob, alice_e*bob_e) then deletes alice_e's private key. (note: alice sends the public key she used to bob, he'll need that to decrypt the share)

Later, she wants to update the share - she sends a message to bob: "please delete that share" and bob deletes his ephemeral key. Now bob can't decrypt that share anymore! So if an attacker gets a hold of bob's device, they won't have that share either.

If bob sent an array of ephemeral keys, then alice could update the share that many times without having to do another round trip.

PS. you'd better also look into how to securely delete files. I think this might depend on the underlying storage architecture sometimes. Or it might be as easy as just writing 0's over the file.

@bobhaugen if you have questions not directly security related, please fork the thread - but this one I'll answer here because it is short: because protecting keys is hard and dark-crystal makes it easier. Especially since it's targeting itself at diverse people.

Thanks @Dominic I'm gonna brew on all your points.

I agree hugely that revoking trust / deleting shares is a big plus, its one of the first things that people point out as a 'pitfall' of Dark Crystal, is that you cannot revoke trust. Lives change, people change. So finding a solution to this is definitely a high prority for us.

Later, she wants to update the share - she sends a message to bob: "please delete that share" and bob deletes his ephemeral key. Now bob can't decrypt that share anymore! So if an attacker gets a hold of bob's device, they won't have that share either.

The implication in this scenario is that if say Bob does lose his device, if he were to regain access to his identity under the Coconut Death scenario 1, the ephemeral key is no longer available (since it was stored locally on Bob's old device), Bob can no longer decrypt the share, thus effectively invalidating Bob's share for Alice's secret. Technically speaking (rather than human), Alice no longer trusts Bob since he lost his identity so Alice can no longer regain this share from Bob. Would it be possible in this scenario for Alice to basically then say, okay, you've got your identity back, I trust you again, I'll send you a new share. Some SSS implementations allow for adding a new share, though under what conditions I cannot recall right now, but I think you might have to have access to at least one already existing share, possibly the quorum.

Thank you @dominic. Will be digesting. Very enlivening and encouraging to wake up to such a generous gift of time and attention :) Here's some pizza:

@bobhaugen if I had to guess an answer I'd say it is one way of resolving one of the standard plays from web2.0 - password recovery. (amongst other things).

@Kieran to create another share you need to have the secret. The secret is a curvy line defined by K points. If you know any K points on the line, you can draw the line, if you know the shape of the line you can pick another random point on it. Yeah, so to update the line you do actually need to hold the secret. If you backup the secret and forget it locally, then you can't do that.

If you really wanted to not hold the secret locally, I think you could create future shares that are held locally, but encrypted to curve25519 keys that your friends hold. You can't decrypt them, you need your friends to do that... but you'd just have your friends hold them one at a time. Hmm, I think there is still more investigation to do here.

Hmm, I guess to regenerate a secret you can request it back, then regenerate it?

If the idea is to keep the secrets off the permanent log, when your peers return the secret, they ought to encrypt it to a ephemeral key that you provide, so you can recover the secret, but if someone compromises your devices at a later point, they cannot recover the secret from looking at the private messages.

I think the next step should be to go through the DC protocol step by step and analyze what happens if a device is compromised at particular times.

RE: padding the secret

Padding the secret
This is a great idea to make content ambiguous. Particular kind of keys have a characteristic length which gives away more than we need to. I would suggest we add padding so that shards are just under maximum SSB message length.

rather than pad to the max we could add in a randomizer so that we can shave some bytes off. If this becomes a successful pattern within this cyperhspace we'll be glad over time for those shaved off bytes, whilst acheiving the same content ambiguity.

@dan-hassan @peg if you pad to the max it will look obviously like a #dark-crystal message - because what else consistently creates maximum size private messages? you want it to look like it could have been anything so create random sized messages, ideally, without changing the average message size in a statistically detectable way.

notes: how a secret is sharded and returned

A primary peer creates shard messages for all holders. each shard message is encrypted to the holder and the primary,
but then the shard inside of that is again encrypted only to the holder. This means the primary forgets the shards.
You can decrypt the outer (and so see who you sent shards too) but not regain the shard.

following key compromise, compromiser knowns who holds shards (this may be considered necessary...)

When you request the shards back, a private request is sent to each holder. They then decrypt the shard from the previous message, and then send it back. https://github.com/blockades/scuttle-dark-crystal/blob/master/recover/async/reply.js#L61-L62

{
  root, branch, accept: true,
  body: decrypted_shard,
  recps: [primary, holder]
}

The shard is decrypted and sent back to the primary. the holder does not forget the shard. future key compromise of a qorum of holders can recover the secret

But worse: the shards are now on permanent logs encrypted to the primary - so after recovery, future compromise of the holder can recover the secret. However, key compromise before recovery does not reveal the secret, but after recovery it does.

It seems unfortunate that dark-crystal goes to a special effort to avoid logging the shards, but then looses that property after recovery. In particular, for backing up a cryptocurrency private key, it would be better not to have that private key on the log.

mitigation: with current design, a dark-crystal user should move all funds from the recovered wallet to a new address after recovery. However, this is not obvious and they'll probably forget.

remediation: internal forward-secrecy as suggested above for revoking trust would also fix this problem.

("mitigation" and "remediation" are auditing terms - mitigation is what users can currently do to reduce or avoid the problem, "remediation" is how the problem can be fixed by a change to the system)

@peg that's great! yes I can trust @keks to make a suggestion like that. my only addition then is to also use such a scheme for sending the shards to begin with, so that you can revoke shards (i.e. holders are able to choose to forget a shard)

I'm wondering if it makes sense to have such a forward secrecy within an encrypted thread mechanism, as a generic pattern that is useful for other ssb applications? It would mean you could use ssb to transfer a small secret and then forget it - although the metadata (that you told them a secret) wouldn't be forward secret. Can anyone think of another application that might benefit from this?

@peg also to put the commenters suggestion to use 32 byte checksums in perspective - bitcoin mining can generate 64 bit (8 byte) partial collisions, but that costs thousands of dollars to generate, and each additional bit doubles that cost. There are plenty of trustworthy systems that use 16 byte (128 bits). 128 bits of security is considered the standard. I normally don't truncate hashes, I just suggested this over using sha1. My earlier suggestion to use libsodium secretbox also implies a 16 bit mac, although not inside the share, and wouldn't require altering a primitive. (I'm confidant the difference here is just a matter of taste though)

Peg, it is so excellent I have SSB'd

Security Considerations for Shamirs Secret Sharing

really enjoying reading about this. I love to idea of ephemeral shard returns.
I think we could definitely make an ssb-module which handles ephemeral keys

I didn't understand how the revokable shares / shards idea works, have started a thread for that here : %2qEtYbJ...