Zero Knowledge Protocols without magic

When we’ve first released Secure Comparator and started to talk about novel authentication concepts, we’ve encountered 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 understand better how authentication, in general, should work. 

Understanding authentication and ZKP

What is authentication, anyway? 

The power of Captain Obvious shall unfold in the next paragraphs, so skip them if you know what authentication is (or at least think so). 

Authentication is the act of confirming the truth of an attribute of a single piece of data (a datum) claimed true by an entity. In contrast with identification which refers to the act of stating or otherwise indicating a claim purportedly attesting to a person or thing's identity, authentication is the process of actually confirming that identity. (wikipedia

In secret-based authentication, parties agree that secret (S) represents the public identity of prover (P). Then, when P wants to prove he actually is P, all he needs to do is to supply S as his secret to the second party – verifier (V). Whatever the authentication method is, general methodology is the same: 

  1. Prover sends his identity (P) and secret (S(P)) (for example, login/password pair). 
  2. Verifier tries to match S(P) with its records in the credential database. 

For any secret-based authentication, it is important that parties have the pre-shared secret. 

Problems with secret-based authentication techniques

Interception. The only way to prove to the remote party that you know a secret is to transmit either the secret, or it’s derivatives (hashes are frequently used for that purpose). Both the secret itself or derivative data can be stolen by intercepting traffic between parties in one way or another, then used to present someone else as P, knowing their secret S or any derivative. 

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 he’s a P holding S to this party and any other, which have the same S. 

Solutions to these problems?

Secret interception can be prevented by: 

  1. 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.). 
  2. 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.
  3. 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 by: 

  1. Protecting authentication database: just limit database access and encrypt the secret storage with some external secret. Ultimately, this will prevent an unprepared attacker with insufficient privileges. 
  2. Indirect secret storage: To complicate matters for attacker more, the Verifier can avoid storing the secret itself, but rather store one-time reproducible derivative of the secret (for example, salted cryptographic hash value). On each authentication session, the Prover has to reproduce this derivative from secret and present it to 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?

Now imagine that Verifier is actually an attacker! Or, 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 Prover authenticates with fraudulent Verifier once, in most cases it’s enough for this fraudulent Verifier to pretend he’s Prover to any third parties knowing that Secret. 

This is the biggest advantage: no amount of data emitted by Prover under Zero Knowledge Proof protocol is sufficient to re-run Zero Knowledge Proof protocol, or reconstruct the secret itself.

Zero Knowledge Proof in simple words

ZKP enables two parties to verify whether they share the same secret (for example, a password for username), without exposing it. As a byproduct, some Zero Knowledge Protocols enable you to derive shared secrets (one or many) in the process. 

How ZKP actually works? 

Over the time, cryptographers invented few smart ways to explain ZKP to “normal people”. Instead of trying to repeat them, we’d like to invite you to sip a bit of their knowledge:

Using ZKP

ZKP in practice: what does this mean for my applied task? 

ZKP is not super-magical technique, which will allow parties to build trust without exchanging secrets. ZKP is a good reinforcement to 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 secret. 
  • It’s only the security guarantees of the process which 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 beg for novel security tricks:

ZKP in practice: some applications

Login/password authentication

The most obvious application is login/password authentication, where you exchange login in open (or easily decipherable) form, and then perform ZKP to prove that you know the password and server knows it too.

Request by ID 

Another useful technique is authenticating requests to sensitive data. A good example is Name/SSN pair. Bank, Asking Credit Rating authority for credit rating via SSN is directly exposing the fact that this SSN is bank’s client and letting Credit Rating authority create a record out of nothing (out of the fact that person behind SSN contacted the bank). However, a name is a very broad identifier, which does not bijectively point at one person.

Let’s say you (as a bank) is Verifier and Credit Rating authority is a Prover. You send the Verifier public requisite (name) and initiate ZKP over SSN. Verifier allocates a list of SSNs that correspond to this name and performs ZKP on each one. 

This way, the protocol will succeed only if Credit Rating authority has any record on desired SSN and exposing SSN to authority gives meaningful benefit for Verifier.

There are more sophisticated (storage-wise) schemes, where both parties hold secrets they use and their derivatives as identifiers for these secrets. Such schemes pay off in situations where there is only one identifier - and it’s leakage already is a problem.

Repeated authentication: paranoid mode on

To enforce proper behaviour during 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 keeping trust chain from the very beginning of the protocol (first value can be any derived key) and 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 infrastructures.

Summary

The summary is as simple as it gets: ZKP protocols are not magic. However, by understanding how they work, you can achieve magical reinforcements to your security architectures.

They allow: 

  • authentication over untrusted communication channel
  • authentication with untrusted / unidentified remote party
  • (sometimes) key derivation based on this secret exchange. 

They still require the secret to be pre-shared, and, more importantly, they still require authentication to be a part of the security system, not a magical feature to scare hackers away.

Copyright © 2014-2017 Cossack Labs Limited
Cossack Labs is a privately-held British company with a team of data security experts based in Kyiv, Ukraine.