[messaging] KCI in X3DH

[Natanael]

Den 18 jan. 2018 12:10 skrev "Katriel Cohn-Gordon" <me at katriel.co.uk>:


*KCI *For the KCI attack described by Kobeissi et al [
https://doi.org/10.1109/EuroSP.2017.38] you only need to compromise one key
(Bob's medium term signed prekey). If I know that key, I can impersonate
anybody to Bob by making up a fake ephemeral key for Alice. Then I can
compute 1 because I know Alice's ephemeral, 2 because I know Bob's
medium-term, and 3 because I know Alice's ephemeral. I can't compute 4.


I assume that having Alice sign her ephemeral key breaks deniability for
her? That the construction expects only the receiver to have signed medium
term keys?

I'm can't say I know enough to say for sure, but doesn't DH(static a,
static b) also partially hurt deniability? One big difference between OTR
and Signal / 3DH is denying that you ever have had contact. In the case of
a compromise of a static key, then the pre-existence of this value #4
proves at least that either a or b at minimum considered starting a
conversation with the other... Right? Without it, *anybody* can forge a
full conversation transcript between any two parties. You can't however
forge #4 as an outsider to somebody who knows the key.

To show to Bob that you're Alice you will need to do something with your
private key which he can verify, but the proof must be tied to Bob and the
conversation somehow. And yet for deniability you need to deny your private
key was involved. As far as I can see, you need the construction for the
the proof to still rely on "provenance" of the proof as 3DH itself does,
which requires interaction of some form. This is most easily done IMHO by
challenging somebody to decrypt a message.

I can only really imagine one (partially OTR inspired) scheme, a
challenge-response scheme, here's my suggested implementation;

Bob generates a secret random nonce, unique for this conversation. He
appends a value derived from the ratchet seed hash(1, 2, 3), and encrypts
this with Alice's static public key. Alice decrypts, checks for that
ratchet value, and replies with the nonce.

This is deniable because anybody can construct a transcript in which they
send such a challenge and makes it look like the recipient responds with
your challenge string, you can't *prove* with the transcript that it was
Alice who revealed her knowledge of the nonce.

---

As a side note, deniability still don't really hold up to ACTIVE attacks in
which one side is compromised and targeting the other (at minimum this
would support a claim that Alice and Bob did communicate, useful tactic for
example if one denied it in court).

There's too many alternative ways to implement your side of the key
exchange such that you can show you (probably) didn't forge the response.
Silently using threshold keys, which are held by multiple parties, being
one. Or even implementing your entries side of the protocol over MPC.
Adding interactive timing measurement d demanding more latency might be the
only plausible countermeasure.


*Bad RNG*


It doesn't hurt to mix the system provided entropy with your own private
key, deterministic ECC signatures does it already. A sufficiently bad
system RNG might repeat values, so a naive mix don't protect you against
all attacks. Then you want your own internal CSPRNG with its own seed. The
fast key erasure construction seems nice, seeding that with every source of
entropy you've got available should work fine (Java secure random, and your
keys).

I'm not sure how plausible this scenario is though. In what case would the
system RNG first be safe, but then become the only part broken enough to be
exploitable? Perhaps after a system update, perhaps after loading your
backup onto a new phone. Perhaps your phone only used its poorly built
HWRNG to seed the OS RNG and now it broke. Unlikely though.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20180119/ae122976/attachment.html>