<div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Oct 8, 2014 at 2:58 AM, Trevor Perrin <span dir="ltr"><<a href="mailto:trevp@trevp.net" target="_blank">trevp@trevp.net</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Suppose that each day the key directory constructs a "Sparse Merkle<br>
tree" [1] that maps usernames to the user's identity public key(s) for<br>
the previous 24 hours.  The "signed tree head" (STH) is a signed hash<br>
of the sparse Merkle tree root and the previous day's STH.<br></blockquote><div><br></div><div>Like the idea. Actually I think it's even better than your post suggests.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Users could gossip the latest STH by including it in their encrypted<br>
messages to each other.  Users would request proofs from the directory<br>
that STHs are consistent, and that identity keys are consistent with<br>
STHs.<br></blockquote><div><br></div><div>What would you check "consistency" with? I think the log can just publish signature(Merkle root of entire current data structure, epoch #) every epoch. Maybe the epoch is 1 day but this is a trade-off. The tree can change arbitrarily every epoch and that's okay. You still need gossip to check that they don't sign two trees in the same epic, but otherwise consistency is basically available "for free."</div><div><br></div><div>Users can request proofs on demand that their desired key material is correctly included every day at the hash of their username. Your software can automate this. Each proof would be 1 signature plus 256*256 bits of Merkle proof (perhaps less if we can drop collision resistance in the hash, which may be safe but haven't thought it through. Plus a signature. Less than 10kB total (maybe down to just a few kB).</div><div><br></div><div>Your software can ping you if your data ever changes in a way it didn't expect. If you go offline, you can catch up (though you won't detect the attack until later obviously). Basically this is like monitoring except you can do it yourself locally. You could have an offline monitor check for you as well. The key point is that checking for N users takes work linear in N with no overhead from tracking the whole structure like you have in some other systems.</div><div><br></div><div>So I think this has some cool advantages.</div><div><br>Further comments:</div><div><br></div><div>1) Self-enforcing security</div><div><br></div><div><div>Digging into the Crypto Bag Of Tricks there's an interesting and potentially stronger approach: tagged one-time signatures [1]. With this approach, if the server ever signs two Merkle roots for the same epoch #, you can use the two signatures to re-construct their private key. You still need gossip to discover this, but this is a big disincentive to the server ever cheating.<br><br></div><div>Perhaps this is a bad idea-it's a big loaded gun and the system will collapse spectacularly if the log screws up. Maybe we want the flexibility for a misbehaving log to explain itself publicly and be forgiven, or maybe we explicitly want a Sword of Damocles over their head to avoid them being able to do so.</div></div><div><br></div><div>2) Key Directory vs. Short-lived certificates</div><div><br></div><div>Two approaches are possible for privacy: in one version, the log functions as a key directory and will respond to anonymous queries for a given username. In this case you have to deal with DoS and people trying to brute-force to find usernames. Maybe privacy goes down.</div><div><br></div><div>Alternately, it can function as a type of "certificate authority". Your "certificate" is the proof that your cert is included in a specific epoch. You can give this to anybody else (size < 10kB) and they can check that this really is the key for the username you just claimed. The log would only give this proof to the user themselves (perhaps authenticated however they authenticate changes to that user's log entry), after which you can give your proof to whomever you want through other channels. Privacy seems higher here, though everybody has to download a new cert every epoch so the epoch probably need to be longer and revocation is worse. Which leads to the net point.</div><div><br></div><div>3) Dealing with immediate issuance</div><div><br></div><div>In the simple approach, you can't add new data to the log until the next epoch. Maybe we can drive this down to a matter of minutes (and users will accept data from a slightly out-of-date epoch). At some point the cost of downloading your proofs at every epoch becomes prohibitive, which probably means that you can't immediately download the chat app, make a new username, and start talking. That might be the "fatal flaw" in practice. One approach is issuing SCTs to use before inclusion but that seems to pull in a lot of complexity. You might also have some side data structure for newly issued certs, though that seems to invite MITM attack by inserting things there. Or maybe there's a really elegant extension of the tree with things changing at different epochs to be discovered.</div><div><br></div><div>Seems worth exploring further to me.</div><div><br></div><div>Joe</div><div><br></div><div>[1] <a href="http://link.springer.com/chapter/10.1007%2F978-3-642-36362-7_20" target="_blank">http://link.springer.com/chapter/10.1007%2F978-3-642-36362-7_20</a> (apologies, couldn't find a non-paywalled link)</div><div> </div></div></div></div>