Our research on CONIKS began in an attempt to design a secure webmail service run by an untrusted provider. After some time, we realized that the underlying problem in designing a secure webmail service is that the existing key management and verification systems have two main drawbacks: managing and verifying key fingerprints manually is an error-prone process and impractical to automate; centralized service provider-run key servers require that users blindly trust the provider not to tamper with its users' keys. We designed CONIKS to address these two issues, and we found that the key transparency model was the most suitable key management and verification model for secure communication services of all kinds.

We hope that our research will guide the deployment of CONIKS or key transparency systems in existing and new end-to-end secure communication services, but we also believe that our research may have applications in areas other than secure communication. At the same time, many problems specific to secure messaging remain unsolved. We have outlined several of these open problems that we have encountered so far.

If you're a researcher interested in secure messaging, we encourage you to consider tackling one of these open problems, or to contribute to our list so that others may learn about problems we may not have encountered yet. Please feel free to email us or to start a discussion on our mailing list.



Why Making Johnny's Key Management Transparent is So Challenging
Marcela Melara
Freedom to Tinker
[blog post]

EthIKS: Using Ethereum to audit a CONIKS key transparency log
Joseph Bonneau


CONIKS: Bringing Key Transparency to End Users
Marcela S. Melara, Aaron Blankstein, Joseph Bonneau, Edward W. Felten, Michael J. Freedman
USENIX Security '15
[paper] [presentation]

Coniks 2.0: Publicly Verifiable Keystore with Key Changing and Verifying Capabilities
Michael Rochlin
Princeton University

Bringing Deployable Key Transparency to End Users
Marcela S. Melara, Aaron Blankstein, Joseph Bonneau, Edward W. Felten, Michael J. Freedman
Cryptology ePrint Archive


CONIKS: Preserving Secure Communication with Untrusted Identity Providers
Marcela S. Melara
Princeton University
[Master's thesis]

Open Research Problems

CONIKS has provided the first steps towards key transparency and is changing how communication service providers are thinking about key management. However, several open challenges that pose major barriers to making CONIKS truly practical for deployment remain. We identified some of these problems through discussions with major communication service providers, and summarize these findings in a blog post.
Detecting the source of an inconsistency

Auditors have no way of determining whether an inconsistency they detect was introduced by an outside attacker who compromised the key server, a system error, or a malicious employee. Currently, the only party that can be held accountable for an inconsistency is the identity provider. But identity providers don't want to lose the trust of their users because of a single malicious employee or because of an outside compromise. A high-assurance key server would minimize server bugs by using formal verification and secure hardware, but how can identity providers unambiguously prove that changes to the directory were made by a single malicious employee or caused by outside compromise?

Recovering from unintended inconsistencies

This problem is coupled with a CONIKS server's ability to detect the source of an inconsistency. Being able to prove the cause of an unintended inconsistency can help providers maintain their users' trust, but providers and users also need to return their system to a stable state after such an inconsistency has occurred.

Secure account recovery after key loss

Unlike passwords, which may be recovered when lost, there is no way to recover data encrypted for a lost key, which means a user would lose access to her account. A more user-friendly approach to account recovery, which is the current default in CONIKS, is to allow unauthorized key changes. However, this mechanism undermines users’ security since it doesn’t leave cryptographic evidence and other clients have no way of distinguishing account recovery from a compromised account. Therefore, it is crucial to develop a secure account recovery mechanism, in which it’s unambiguously clear who initiated the recovery. While key loss is also a problem in other applications such as Bitcoin wallets, we haven’t explored whether the solutions in those domains could apply to CONIKS.

Detecting false positives

False positives will cause a CONIKS client to issue warnings prompting the user about a possible attack. For example, the client will detect an unexpected key if the user adds a new device or re-installs the app to recover a lost account, as well as when the key server maliciously changes the user’s key without proper authorization. Similarly, a warning will be issued for inconsistent directory summaries, but these may stem from time synchronization problems between the server and the client, or from an attempt by a malicious key server to equivocate. It is crucial for the client to be able to distinguish between the innocuous causes for warnings and the attacks.

Effective user warnings

This problem is coupled with a CONIKS client's ability to detect false positives. Users are notorious for ignoring security warnings, so malicious CONIKS key servers may get away with attacks. Even if CONIKS clients have a mechanism for detecting false positives, how do we design a user interface that conveys clearly to users when it’s important for their security to take action on a warning?

Proactive attack prevention

By design, CONIKS detects attacks after-the-fact as inconsistencies are only detected once inconsistent signed tree roots have been published. While the detection guarantees are strong, they do leave an open window for attack, which depends on the frequency with which providers publish new STRs. Even though providers are required to publish temporary bindings whenever a client changes a key directory entry, these only serve as a non-repudiable promise by the provider to incorporate the changes in the following epoch. They don't prevent equivocation. Therefore, it is important to find a practical solution that is proactive and can mitigate the risks of key server compromise, instead of relying solely on a reactive system such as CONIKS.