Re: [Taler] Technical questions for backup/sync (was: UI considerations for backup & sync)

[Christian Grothoff]

On 5/26/20 9:28 PM, Torsten Grote wrote:
> On 2020-05-25 17:28, Christian Grothoff wrote:
>> I think we can have both: a single master key and the crypto-visibility:
> 
> Thanks! Now things get interesting :)
> 
> I'll add some questions below to be sure I understand things. Maybe it
> also helps others to understand your proposal better.
> 
>> Let the master key be M (symmetric!), and each device "x \in X" has a
>> device key Dx.  M is shared across all devices. M is used to derive an
>> account key "A := f(M)" for the sync process (asymmetric, for
>> signatures).
> 
> Is f() deterministic, so each device arrives at the same A?

Yes.

>> Then store at the sync service:
>>
>>   S_A(  E_M(X, { Ex, DH(Ex,Dx,K) }_{x\inX} || E_K(S) (|| J)+) )
> 
> Not sure I fully understand this syntax. Looks like a mix of latex,
> concatenation and regular expressions.

|| == concatenation
E  == symmetric encryption
E_K== symmetric encryption with key K
S_A== signing with key A, returning including the
      entire body + signature
(...)+ == ENBF-style: optional, possibly multiple
     (I guess I should have used * instead of +)
{foo(x)}_{x\in X} -- foo(x) for all
     elements x in the set X.

>> (Note that S_A is required by the Sync protocol, to detect an authorized
>> party making a change.)
> 
> What is S_A? A signature made over everything stored separately?

Yes. Needed by sync so we know this is an authorized update, as sync
updates are destructive.

> The next layer seems to be wrapped in E_M which is encryption with the
> symmetric M?

Yes.

> In there is S encrypted with K that you get out of DH(), right?

Yes. I guess I was a bit brief here: the K in E_K is not directly the
result of the DH (as we have many DHs), but provided encrypted with the
DH (as we have one K).  Like with GnuPG e-mails going to multiple
people: the E-mail body is encrypted symmetrically with one key K, and
the header includes K encrypted for each recipient.

>> With this, we know:
>> - only devices in the device group (incl. Anastasis) can do the
>>   DH to find the current K
>> - the Sync service still learns nothing, not even the set of
>>   devices, only 'A' is exposed as it must be
> 
> How is A exposed? It seems to appear only in a signature made with it.

The private key is deterministically derived from M. The public key is
used by sync as the identifier of the account.

> Ah it is implicitly used to locate the backup blob at the service
> provider, right?

The sync provider stores all backups under the public key that was used
to verify the signature on the backup.

>> - to add a device via QR code, we now need an additional
>>   interaction: basically we teach the new device 'M' first
>>   (via QR code), and then we need another interaction where
>>   an existing device adds Dx to the device list.
> 
> Dx is the new device's key and without that being added into the DH()
> computation, the new device can't use its private key to decrypt K, right?

Right.

> So when *removing* a device from the group, its Dx is dropped and thus
> it can't decrypt K and E_K anymore even though having knowledge of M, A
> and where the backups get stored. So it gets effectively included and
> can only monitor the size of the backup changing over time.

Yes, which I consider pretty useless.

> The process of adding a new device with this scheme still isn't
> completely clear to me. It seems the new device needs to learn M and the
> domain+path of the backup service(s?) it should use.
> Then the adding device needs to learn X and Dx of the new device. So
> each device needs to scan one code, right?

The adding device learns Dx via 'J'. As J is not encrypted with K, the
joining device can append its own data there. So the adding device can
learn Dx (and add x to X) by syncing after the joining device updated
the backup (without having been able to actually read the backup
contents yet).

> Also, how does this scheme work if I just want to use it with a single
> device as a backup service without Anastasis? Looks like this wouldn't
> be possible anymore, because there's nobody left to upload a new blog
> with my new device key included, right?

You would need to write down M and Dx for your single device x.

> Could there be another "fake" device for offline backups? It seems the
> to-be stored secret would need M and all Dx, so rather a lot to scribble
> it down on paper. Even worse to stay useful, the offline backup secret
> would change with each device that gets added, right?

Good idea, we could generate an initial root secret, "R", and then say
M=H1(R) and D0 = H2(R).  Given "R", one can then compute the D0 device
key for the backup, and the master key. And R could be just 256 bits.
However, we then must not store R, and thus really could only show this
once at the beginning, and not later again.  If the user looses R, we
could of course have an expensive process to migrate to a new M, but
that would change A and the user would have to re-pay for sync.

Or, we first show "R", and if the user looses it, we remove D0 from X
and show a 512-bit secret with M and a fresh D9.

>> Devices that are already in the group see the 'J', prompt the user to
>> approve the new device. If the user rejects, they remove J (kicking the
>> new device out). If the user approves, they add Dn to the X set, upload
>> the result and now the new device can download the state S for the first
>> time.
> 
> I am a bit worried about the UX of that process. But I guess as syncing
> state is very slow anyway it wouldn't matter anymore if also it takes
> quite some time for the initial state to show up.

Why should syncing be slow? Unless the wallet state is huge (bad, we
should try to avoid that -- for example by expanding RMS's proposal for
forgettable contract state to include product preview images!), I would
hope that neither bandwidth nor crypto nor CRDT-based merging makes this
take more than a few hundred milliseconds.

> Another concern I had was about devices disagreeing about the current
> set of devices X and Dx, but I guess since X is included in the blob
> that everybody can decrypt, there can be a mechanism for them to arrive
> at a consensus, even if they've missed J for example. 

Right, they see the updated X, which should be enough to be "informed".

> So in that case
> the worst that can happen is that some devices can't decrypt uploads by
> some other devices temporarily, but due to CRDTs would converge on a
> single state eventually. Correct?

They should always be able to decrypt once they have been joined, as
their Dx key is in the set. So I don't think there is even an issue here
with a 'temporary' downtime.  The only situation where one cannot yet
decrypt is if one has the M to post a (J)oin request, but has not yet
been approved by the adding device.

Happy hacking!

Christian

signature.asc
Description: OpenPGP digital signature