Support Post-Quantum Cryptography #2915
Description
With the hypothetical threat of quantum computing and its capability to break existing asymmetric encryption schemes various secure chat applications have been adding post-quantum resistance to their key exchange to potentially mitigate this threat. In addition, due to the so-called harvest now, decrypt later attack, the sooner such resistance is added the better to prevent stored messages from being easily decrypted in the future if quantum computing ever becomes a real threat.
As such I think Tox, being a secure chat application, should look into implementing some sort of post-quantum KEM to its key exchange to have its security more competitive with other alternatives and to give users more confidence in the confidentiality of messages going forwards.
For reference, here's a few writeups done by other secure chat protocols/services implementing this protection:
While I myself am not a cryptography expert (let alone in post-quantum cryptography), based on the SimpleX blog post about their implementation the Streamlined NTRU Prime (or something similar) KEM is probably the best option for a project like Tox. Unlike Kyber (ML-KEM as NIST calls it) which Daniel Bernstein has raised concerns about (see here for a blog post about the dubious calculations the NIST used to evaluate it and here for a comparison of various KEMs) it seems like a more robust option, plus avoids any potential patent threats which might be undesirable for an open source project.
The main concern I could see with implementing something like this is that such KEMs are something on the order of a kilobyte rather than the much smaller 32 byte Curve25519 keys in use now which will increase the key exchange's network usage. I am also not sure about the implications of how this would interact with the Tox ID since if you had to share some huge 1 KB string with someone through an existing trusted channel to protect against a quantum MITM that probably wouldn't work very well. Based on Signal's explanation of their PQXDH protocol here though there doesn't actually seem to be a good solution to preventing a MITM attack with a quantum adversary currently (unless I am reading it wrong). As that document says:
Authentication in PQXDH is not quantum-secure. In the presence of an active quantum adversary, the parties receive no cryptographic guarantees as to who they are communicating with. Post-quantum secure deniable mutual authentication is an open research problem which we hope to address with a future revision of this protocol.
With that in mind perhaps the focus could be just preventing the harvest now, decrypt later attacks by adding a KEM to the key exchange and dealing with active attacks like that at some point in the future when it becomes more of a threat.
Another potential concern I could see would be how this would interact with older Tox clients. I assume there's some sort of protocol versioning though in the Tox protocol that could be used to negotiate which encryption protocol can be used, though there'd probably need to be a way via the API to actually query if post-quantum encryption is in use or not (or an option to only allow that) so clients can indicate that information to prevent protocol downgrade attacks.
Again I am not an expert in this sort of stuff, so feel free to criticize this proposal or point out anything I missed.