When we’ve first released Secure Comparator to use in our Themis crypto library and started talking about novel authentication concepts, we’ve encountered a few common misconceptions and plenty of magical thinking about Zero-Knowledge Proofs as a phenomenon. In this post, we’ll talk about some of them, tie ZKP authentication to traditional security models, and help you gain a better understanding of how authentication, in general, should work.
Understanding authentication and Zero-Knowledge Proof Protocols
What is authentication, anyway?
Note: If you know (or think that you know) what authentication is, you can skip the next few paragraphs. Else — behold the power of Captain Obvious.
In secret-based authentication, parties agree that a secret (S) represents the public identity of a prover (P). When P wants to prove he/she actually is P, all he/she needs to do is to supply S as his/her secret to the second party – verifier (V). Whatever the authentication method is, general methodology is the same:
The prover sends his/her identity (P) and a secret (S(P)) (for example, login/password pair).
The verifier tries to match S(P) with the records in the credential database.
For any secret-based authentication, it is important that the parties have a pre-shared secret.
Problems with secret-based authentication techniques
Interception. The only way to prove that you know a secret to the remote party is to transmit either the secret or its derivatives (hashes are frequently used for that purpose). Both the secret or its derivative data can be stolen through intercepting the traffic between the parties in one way or another and then used to impersonate P, knowing their secret S or any derivative of this secret.
Authentication database leakage. To compare secrets, V has to carry a database of secrets of remote provers matched to their identities. By stealing that database, the attacker can pretend hto be P holding S to this party and any other, which have the same S.
Solutions to these problems?
Secret interception can be prevented by:
Public-key based authentication: safe method, based on asymmetric cryptography. Requires parties to exchange public keys (which you can’t easily dictate over the phone or write down on a post-it note on your desktop), requires key management (key revocation, a chain of trust, etc.).
Securing transport layer: encrypting traffic means you either need to have the pre-shared secret key or have the public key-based system, so restrictions mentioned above apply.
Zero-Knowledge Proof: does not require the key exchange, does not leak password. Allows to derive temporary keys for secret key transport encryption after authentication itself. The only drawback is that ZKP is computationally expensive.
Secret leakage can be prevented through:
Protecting authentication database: Limit the database access and encrypt the secret storage with some external secret. Ultimately, this will deter an unprepared attacker with insufficient privileges.
Indirect secret storage: To complicate the life of an attacker, the Verifier can avoid storing the secret itself, but store one-time reproducible derivative of the secret instead (i.e. salted cryptographic hash value). On each authentication session, the Prover has to reproduce this derivative from secret and present it to the Verifier.
Also, any secret-key authentication is frequently reinforced by OTP and other MFA techniques.
So why exactly Zero Knowledge Proof is better for authentication?
Imagine that the Verifier is actually an attacker! Or that the Verifier is replaced by an attacker. It could even happen locally; that’s how banking-oriented malware frequently works.
With traditional techniques, there’s not much you can do. If the Prover authenticates with fraudulent Verifier once, in most cases it’s enough for this fraudulent Verifier to pretend he/she is the Prover to any third party as he/she now knows that Secret.
This is the largest advantage: no amount of data emitted by the Prover under Zero-Knowledge Proof protocol is sufficient to re-run the Zero-Knowledge Proof protocol or to reconstruct the Secret.
Themis is an easy-to-use crypto library that provides interactive ZKP protocol for authentication and comparing secrets.
Zero-Knowledge Proof Protocols in simple words
ZKP enables two parties to check (verify) if they share the same secret (for example, find out if they have the same password for their respective accounts), without exposing it. As a byproduct, some Zero-Knowledge Protocols enable you to derive shared secrets (one or many) in the process.
How Zero-Knowledge Proof Protocol actually works?
Over the time, cryptographers invented few smart ways to explain ZKP to “normal people”:
Ignat Korchagin’s SMP explanation (by the way, Ignat is contributing a lot to Cossack Labs cryptographic research and his research is behind our ZKP implementation Secure Comparator).
Matthew Green’s Zero-Knowledge Proofs: An illustrated primer.
Bennet Yee’s Explanation of Zero-Knowledge Proofs.
The classic "Cave example" explanation of Zero-Knowledge Proof.
And our own take on explaining Zero-Knowledge Protocol — Explain Like I’m 5: Zero Knowledge Proof (with Halloween-themed illustrations).
Using Zero-Knowledge Proof Protocol
ZKP in practice: how can I use it for my own tasks?
ZKP is not some abra-cadabra magical technique which could allow building trust without having the parties to exchange the secrets. ZKP is a good reinforcement of the existing authentication patterns:
You still need to share a secret to be able to verify it.
You still need a public identifier to match to the secret.
It’s only the security guarantees of the process that change.
In the most general form, you use ZKP to verify secrets in hostile environments, architecturally it’s just another implementation of authentication.
However, some features of ZKP proofs could use a few novel security tricks.
Need assistance with ZKP or zk-SNARKs? Consult with our cryptographic engineers.
Zero-Knowledge Proof Protocols in practice: some applications
Login/password authentication
The most obvious application is login/password authentication, where you exchange login in an open (or easily decipherable) form and then perform ZKP to prove that you know the password and that the server knows it, too.
Request by ID
Another useful technique is authenticating requests to sensitive data. A good example is Name/SSN pair. A bank that is asking the Credit Rating authority for a credit rating score via SSN is directly exposing the fact that this SSN is bank’s client and it is letting the Credit Rating authority create a record out of nothing (solely out of the fact that the person behind the SSN contacted the bank). However, a name is a very broad identifier, which does not objectively point at one person.
Let’s say, you (as a bank) is a Verifier and the Credit Rating authority is a Prover. You send the public requisite (name) to the Verifier and initiate a ZKP over SSN. The Verifier allocates a list of SSNs that match this name and performs a ZKP on each.
This way, the protocol only succeeds if the Credit Rating authority has some record(s) matching to the desired SSN and exposing the SSN to authority grants meaningful benefits to the Verifier.
There are more sophisticated schemes (in terms of storage), where both parties hold the secrets they use and their derivatives as identifiers for these secrets. Such schemes pay off in situations where there is only one identifier — and its leakage already is a problem.
Repeated authentication: paranoid mode on
To enforce the proper behaviour in risky protocols (like signing transactions in online banking), we need to verify the honesty of both parties (because we don’t know where the attacker might hit).
To do that, we can authenticate each step of the protocol with secret S and sensitive data from the previous step. This way we keep a trust chain from the very beginning of the protocol (the first value can be any derived key) and do not rely on temporary trust tokens like session keys.
Secure Comparator
At Cossack Labs, we’ve developed our own ZKP implementation, "Secure Comparator". Take a look at it in Themis, our security services library. It’s quite useful as an illustration of what ZKP is and how it can be used in your infrastructure.
Summary
The summary is as simple as it gets: ZKP protocols are not magic. But by understanding how they work, you can add some "magical" (as in "magically effective") reinforcements to your security architectures.
They allow:
authentication over an untrusted communication channel
authentication with an untrusted / unidentified remote party
key derivation based on this secret exchange (sometimes).
ZKP protocols still require the secret to be pre-shared. More importantly, they still require the authentication to be a part of the security system, not a magical feature to scare the hackers away.
2018 UPD: This article is just as valid as on the day it was published, yet Themis and Secure Comparator have significantly evolved. If you're looking for new ideas, this is the right place. If you're looking to implement security, apply for our Customer Success Program. If you're looking for ready-made solutions, consider looking into Themis, Acra, or Hermes.
