[messaging] Giving new devices access to old messages

[Trevor Perrin]

On Mon, May 11, 2015 at 1:12 AM, David Leon Gil <coruus at gmail.com> wrote:
>>> > On 19/04/2015 01:22, Trevor Perrin wrote:
>>> [...]
>>> >>  A read-cap contains a symmetric encryption key for an
>>> >> encrypted file and a secure hash of its ciphertext, so it has all the
>>> >> data needed to retrieve and decrypt an authentic copy of the file.
>
> The idea of storing a key of trees is not particularly novel. A
> somewhat better way of doing it is to store a tree with a branching
> factor of (storage_page_size / (key_size + sizeof(uintptr_t))).
>
> Does anyone have a decent citation? (RR, perhaps?)

I cited Tahoe, which introduced the term "read-cap":

https://gnunet.org/sites/default/files/lafs.pdf

I agree this is straightforward.  It's just two basic ideas:
 - clients passing around a (symmetric key, hash) that decrypts and
authenticates some server-stored file
 - recursively storing (symmetric key, hash) "read-caps" inside
server-stored files to construct directory trees, so that giving
someone a single read-cap recursively grants access to a larger number
of files

Tahoe explains this well and has a nice term for it.  If there are
earlier/better examples I'd like to see them.


> And, to reiterate a point which I have made previously: It is
> extremely important to ensure that stored messages cannot be
> correlated with the messages sent on the wire between sender and
> recipient. This requires that messages be re-encrypted for storage.

Whether that's "extremely important" seems debateable:

1) Re-encrypting and re-uploading every received message to your
server would be a significant bandwidth cost

2) Paying this cost might not achieve the benefit you mention.  If I
upload archived messages immediately after downloading incoming
messages, the server will have a good idea how the archived messages
correlate to incoming messages.  This is true even if the archived
messages are re-encrypted.

I instead suggested deriving read-caps such that clients could
"archive" incoming messages by simply leaving them on the server.
This could be done if messages in transit are encrypted and
integrity-protected based on a single symmetric key and a hash-based
MAC (e.g. by deriving cipher and HMAC keys as a one-way function of
the symmetric key).  Then the symmetric key and MAC can be interpreted
as a read-cap.

Clients would probably still upload encrypted "directory files"
periodically, so that they could provision read-caps for directories
to new clients, instead of provisioning read-caps for all messages.
So clients would be uploading a read-cap for every archived message,
eventually.  But this should still be a savings over re-encrypting /
uploading message contents.

So I still think that's a practical approach for an email-like protocol.


>> On Sun, Apr 19, 2015 at 10:37 AM, Trevor Perrin <trevp at trevp.net> wrote:
>>> Example:  Alice sends you a message, you later share the
>>> message-decryption key to a new device.  But spyware on Alice's
>>> machine was stealing her keys!  Your service provider could use the
>>> stolen message key to rewrite Alice's message.  This is prevented if
>>> you give the new device a secure hash of the message alongside the
>>> key.
>
> This threat model would make sense if a provider
>
> (1) allowed users to rewrite stored messages at arbitrary times,
> (2) but did not allow them to rewrite the hashes.
>
> Is there some reason that this would be a useful service to provide?

Regarding (1), the provider might be part of the attack.  That's not a
"useful service", it's the threat model.

Regarding (2), the provider can't rewrite the hashes if they are
provisioned from old clients to new clients.  I was explaining why it
was important to provision hashes between clients, and not just
decryption keys.


Trevor