When Peggy Met Victor: It’s Goodbye to an Old World of Hashed Passwords and Hello to Zero Knowledge…

People in the future will look back on the way we created our digital world and smile.

When Peggy Met Victor: It’s Goodbye to an Old World of Hashed Passwords and Hello to Zero Knowledge Proofs

People in the future will look back on the way we created our digital world and smile.

“They cared more about sustaining flawed systems than they did about proper privacy”

For them they might say …

“Ha, ha … they took a password and put it through a one-way function and which just scrambled it … and then the found that it could be easily cracked … so they added some salt, but they … wait for it … put the salt beside scrambled value … and then they found that this could be cracked … so they slowed the whole process down … and then they …”,

And

“Ah, they actually gave away all their information freely to however wanted it, and their passwords were sent over the network, and where administrators could see them. And a crack of a key would reveal the rest of their encryption keys. What a crazy, mixed-up world they had. No wonder they had some many data breaches”.

And they will ask “Why didn’t cyber security professionals do anything about it?”.

I appreciate that if we were to use proper random values for our passwords, we would be relatively safe, as the entropy would be high, but we don’t, as we are humans. Some will say that multi-factor systems are on the way, but even with them we need to find ways to pass elements of our identity in a way that does not actually reveal the core data. If so, we leak our identity every time we prove ourselves.

But a new world is evolving. With the phasing out of WPA-2, and its flawed hashing method of protecting keys, we see a new world evolving, and it is one that properly protects data by proving both ends of a connection. WPA-3 thus brings the Dragonfly method and which allows two sides to prove that they know a secret (the password) without actually having to send it [here], and where even a breach on a single key does not compromise all the other keys (forward secrecy).

So let’s peek inside some ZKP and see how the magic happens. I walk through John Napier’s Tower every working day, so I’m a big fan of logarithms, and it’s to discrete logarithms that we often turn for our ZPK. In this article I will outline the Schnorr Identification scheme and which is used in the Non-interactive ZPF method [here]:

The Schnorr identification scheme

The Schnorr identification scheme was defined in 1991 [1] and supports a zero knowledge proof method. It uses discrete logarithms. The prover (Peggy) has a proving public key of (g,X) where g is a generator, and X=gˣ(mod N). x is the secret value that the prover (Peggy) must prove. After Peggy generates her public proving key, she will then be challenged by Victor to produce the correct result. In the following we define a secret value (x), a generator (g) and a modulus value (N).

Method in detail

With Schnorr identification, Peggy (the prover) has a proving public key of (N,g,X) and a proving secret key of (N,x). N is a prime number for the modulus operation, and x is the secret, and where:

X←gˣ (mod N)

On the registration of the secret, Peggy generates a random value (y), and then computes Y:

Y←gʸ (mod N)

This value is sent to Victor (who is the verifier). Victor then generates a random value (c ) and sends this to Peggy. This is a challenge to Peggy to produce the correct result. Peggy then computes:

z←(y+xc)(mod N)

He then sends this to Victor in order to prove that he knows x. Victor then computes two values:

val1=YXᶜ (mod N)

val2=gᶻ(modN)

If the values are the same (val1≡val2), Peggy has proven that she knows x.

This works because:

YXᶜ=gʸg(ˣ)^c=g^{y+cx}

gᶻ=g^{y+cx}

In a formal definition (taken from this paper) [2], the method is:

The following codes it in a simple form:

import random
import sys
N=89
g=3

x = random.randint(1,97)
X = pow(g,x) % N
y = random.randint(1,97)
Y = pow(g,y) % N
print "Peggy (the Prover) generates these values:"
print "x(secret)=\t",x
print "N=\t\t",N
print "X=\t\t",X
print "\nPeggy generates a random value (y):"
print "y=",y
print "\nPeggy computes Y = g^y (mod N) and passes to Victor:"
print "Y=",Y
print "\nVictor generates a random value (c) and passes to Peggy:"
c = random.randint(1,97)
print "c=",c
print "\nPeggy calculates z = y.x^c (mod N) and send to Victor (the Verifier):"
z = (y + c * x)  
print "z=",z
print "\nVictor now computes val=g^z (mod N) and (Y X^c (mod N)) and determines if they are the same\n"
val1= pow(g,z) % N
val2= (Y * (X**c))  % N
print "val1=\t",val1,
print " val2=\t",val2
if (val1==val2):
	print "Peggy has proven that he knows x"
else:
	print "Failure to prove"

We can determine the possible values of g from [here]. And here is a same run:

Peggy (the Prover) generates these values:
x(secret)= 3
N=  97 , g= 5
X=  28
Peggy generates a random value (y):
y= 54
Peggy computes Y = g^y (mod N) and passes to Victor:
Y= 89
Victor generates a random value (c) and passes to Peggy:
c= 77
Peggy calculates z = y.x^c (mod N) and send to Victor:
z= 285
Victor now computes val=g^z (mod N) and (Y X^c (mod N)) and determines if they are the same
val1= 52  val2= 52
Peggy has proven that he knows x

Conclusions

Hashed passwords are a flawed system, and an intruder just has to build up a database with the mappings between possible passwords and the hashed values. We added salt into this, but stored the salt beside the salted hash password, so again and intruder could take the salt and rebuild the hashed password list. So we slowed the whole process down in order to make it costly for the intruder, but as the cost of GPUs fall and in creating ASICs, the barrier drops by the day.

Why don’t we just give up using a flawed system and do it properly?

Postscript

If you are interested, I have lots more examples of ZPF here:

  • Zero-knowledge Proof: Proving age with hash chains. Age. Proving someones age, without revealing their age.
  • Zero-knowledge proof (discrete logs). ZKP. Outlines zero-knowledge proof.
  • Zero-knowledge proof (zkSnark — Hidden Homomorphic). ZKP. Outlines zero-knowledge proof.
  • Zero-knowledge proof (zkSnark — Blind evaluation problem). ZKP. Outlines zero-knowledge proof.
  • Zero-knowledge proof (Fiat-Shamir). ZKP. Outlines zero-knowledge proof.
  • Zero-knowledge proof (Feige-Fiat-Shamir). ZKP. Outlines zero-knowledge proof using the Feige-Fiat-Shamir method.
  • Zero-knowledge proof (non-interactive random oracle access). ZKP. Non-interactive random oracle access for the Fiat-Shamir heuristic.
  • Zero-knowledge proof (GQ). GQ. Outlines zero-knowledge proof with Guillou-Quisquater (GQ) identification scheme.
  • Zero-knowledge proof (Schnorr). Schnorr. Outlines zero-knowledge proof with Schnorr identification scheme.
  • Zero-knowledge proof (Graphs). ZKP. Outlines zero-knowledge proof using graphing methods.
  • Fair coin flip. ZKP. Outlines how a fair coin flip can be created, without a trusted verifier.
  • Voting with Paillier crypto system. ZKP. Outlines voting with Paillier crypto system.
  • Oblivious transfer. OT. Oblivious transfer.
  • Scrambled circuits. Scrambled. Scrambled circuits — SFE.
  • Millionaire’s Problem . Mill. Yao’s Millionaire Problem.
  • A Fair and Open Election. Election. Outline of a Fair and Open Election process.
  • Diffie-Hellman with Zero-knowledge proof. Diffie. Example of ZKP with Diffie-Hellman key exchange.
  • Dragonfly (used in WPA-3). Dragonfly. The Dragonfly protocol is used in WPA-3.

References

[1] . C. P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161–174, 1991. [paper]

[2] Bellare, M., & Palacio, A. (2002, August). GQ and Schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks. In Annual International Cryptology Conference (pp. 162–177). Springer, Berlin, Heidelberg. [paper]