Wrong! Wrong! Wrong! Building A Truly Citizen Focused World Where You Own Your Data
Wrong! Wrong! Wrong! Building A Truly Citizen Focused World Where You Own Your Data
In the future, Cyber Security professionals will truly laugh when they look back at the things that we have done over the past 40 years. They will exist in a distributed world and one which will respect the rights of privacy and consent. The Wild West of Data, where anyone could do anything they wanted with personal data, will have gone, and the rights of privacy and consent will be fully respected.
Our blind over centralisation of our data infrastructures and resources will also be gone, and be replaced by a truly distributed infrastructure which respects the ownership and the access rights for every single data element.
For us, now, we continue to do things that are plainly wrong, just because it is the way that we have always done things since the start of the Internet. We are basically fixing the leaks in our dam as we go, and never really fixing it. And we educate in the same old way we have done for over 40 years, without caring that we need to build a better world. Our currently security problems are caused mainly because we have built an infrastructure which is severely flawed.
Why? Because we often don’t want to change something that is working. That has always been our attitude to networks and the Internet. If it’s working, just leave it, as we’ll break it! But it’s broken, and it needs fixed.
So why are we still hashing and salting passwords? What a crazy system for storing something so sensitive. With the Cloud and GPU crackers, the challenge is then just a matter to having enough computing resource to find the match. With crackers now working at rates of terahashes per second, and where even long-term encryption keys can be broken, we have a major problem that we are not solving.
The world is changing for the better, though. Blockchain methods allow for the rights of citizens to be respected through code, and not through a cumbersome legal system, which benefits those in power and who have wealth. Protocols that we have lived with for years, such as TLS 1.2 and WPA-2, are not being pushed into the 21st Century, and in the ageing-out of their flawed ways. TLS 1.3 and WPA-3 are just an acknowledgement that the world has moved on from the 1980s, and we need to improve, otherwise our existing Internet will unravel itself as it falls to match its expectations of building new worlds.
A demo of the method — Fiat-Shamir — I will show here is defined here. I have tried to simply the technique in order to demonstrate the key principles involved.
What’s the problem?
So let’s define the problem we want to solve. Basically, can I prove my password, that me and my Cloud service provider have agreed, but for me not to actually tell them what it is? Most of the time, though, I have to give my service provider my password, and then they hash it, and check against the hash that they have. We have thus become sheep, where we blindly fall down the same trap, again and again.
And so we have Peggy (the Prover) sending her password to Victor (the Verifier), and who will take the salt we have on the password, and then take Peggy’s password, and compute a hashed value for it. If the hashed value is the same as the hash stored on his system, then Victor has verified Peggy. How can something so simple lead to billions of passwords being released?
What a crazy system! Peggy is forced to give away her password every time, and Victor now has stored the salt with the hashed value, so that Eve can come along and try lots of possible passwords for Peggy, and then discover her password. Eve might then go and try other systems that Peggy uses, and crack them. Victor might not even know that Eve is doing this, as she can take all the hashed password off-line, and she can continually try possible passwords.
It is complete rubbish, and not fit for a world where Peggy is the true owner of her data and identity, and that Victor has no rights to know her sensitive information (like her password)! It is a system which worked in the 1980s, when we had computers that ran with clock speeds of 16MHz and which had 16MBs of memory, but doesn’t work in a modern era building with the computation power of The Cloud. The hard problem of cracking hashes in the 1980s, is certainly not so difficult in a era of almost endless computing power.
Enter Fiat-Shamir
What we need is a way that Peggy can generate her own password, and then register something with Victor so that he can generate a challenge to her to prove that she still knows it. This sounds, oh so simple, but we blindly still go down the same route of giving away our passwords for the systems that we build. For this we need Zero Knowledge Proofs (ZKPs), and we make sure that the registration process done in a way that has high levels of trust.
Now Peggy can generate an initial registration value, and which Victor can store. We will make sure that it is almost impossible to ever determine her original password from the registration value we use. Now, when Peggy wants to log in to Victor’s system, he sends her a random challenge, and she must produce the right answer to show that she still knows her password. If she return the right answer, Victor lets her log in. Every time Peggy wants to log in Victor sends her a different challenge to solve.
There are many ways to solve the problem, but one of the most widely used methods is the “non-interactive random oracle access” for zero-knowledge proofs. It is defined as the Fiat-Shamir heuristic [1]. It uses discrete logarithms to create a difficult puzzle for Eve, and an easy one for Peggy to prove, and for Victor to verify. Eve, with her array of GPU crackers, will have an extremely large electricity bill if we make the puzzle so difficult that she’ll be have to consume masses of computing power, just to solve one element of the puzzle.
Now let’s start. First Victor and Peggy agree on a generator value (g) and a prime number (p).
1. First Peggy decides on her password (pass), and generates a hash of it, and then converts this to an integer value (x).
x = Hash(pass)
y=gˣ
and to make things more difficult and to allow us to create the puzzle we need to pick a prime number (p) and make the operation:
y=gˣ (mod p)
Peggy sends Victor the value of y, and he stores it. In code this looks like:
x = int(hashlib.md5(pass).hexdigest()[:8], 16) % n
y= g**x % n
2. Now Peggy wants to log on, so she send generates a new random number and sends Victor has value of t:
t=gᵛ
3. Victor thens sends her a challenge ( c ) and which is a random value that he has not used before.
4. Peggy generates another random value (v), and now takes the c value, and computes:
r=v−c×t
She then sends Victor the value of r that she has computed.
5. He then computes:
val=gʳ×yᶜ
and checks if the result equals t equals val, and if they are the same, Peggy has proven her identity, and Eve is left scratching her head.
Note that the operations are conducted with (mod p) and it works because of the magic is logarithms:
gʳ×yᶜ = g^{v-cx}×(gˣ)ᶜ = g^{v-cx}×(gˣᶜ) = gᵛ
For a password reset, Peggy just contacts Victor and does some multi-factor authentication that she did when she registered her secret, and then registers a new secret.
Coding
So what does the coding look like? We we can simply with this:
import sys
import random
import hashlib
n=997
text="Hello"
g= 3
print "Password:\t",text
x = int(hashlib.md5(text).hexdigest()[:8], 16) % n
y= pow(g,x,n)
t = pow(g,v,n)
r = (v - c * x)
Result = ( pow(g,r,n) * pow(y,c,n)) % n
print '======Agreed parameters============'
print 'P=',n,'\t(Prime number)'
print 'G=',g,'\t(Generator)'
print '======The secret=================='
print 'x=',x,'\t(Alice\'s secret)'
print '======Random values==============='
print 'c=',c,'\t(Bob\'s random value)'
print 'v=',v,'\t(Alice\'s random value)'
print '======Shared value==============='
print 'g^x mod P=\t',y
print 'r=\t\t',r
print '=========Resuts==================='
print 't=g**v % n =\t\t',t
print '( (g**r) * (y**c) )=\t',Result
if (t==Result):
print 'Alice has proven she knows password'
else:
print 'Alice has not proven she knows x'
But now we have a problem. What happens if r=v−c×t is negative, as we will get g to the power of a negative number, and which is not possible in a world of integer values. Well for this we introduce the inverse mod, and where we compute the inverse mod of r:
if (r<0):
Result = ( inverse_of(pow(g,-r,n),n) * pow(y,c,n)) % n
else:
Result = ( pow(g,r,n) * pow(y,c,n)) % n
and we use the extended euclidean algorithm to determine this. We just need something to find out a value of g to use, and we are now good to go:
else:
import sys
import random
import hashlib
n=997
text="Hello"
g= 3
def extended_euclidean_algorithm(a, b):
"""
Returns a three-tuple (gcd, x, y) such that
a * x + b * y == gcd, where gcd is the greatest
common divisor of a and b.
This function implements the extended Euclidean
algorithm and runs in O(log b) in the worst case.
"""
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = b, a
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
return old_r, old_s, old_t
def inverse_of(n, p):
"""
Returns the multiplicative inverse of
n modulo p.
This function returns an integer m such that
(n * m) % p == 1.
"""
gcd, x, y = extended_euclidean_algorithm(n, p)
assert (n * x + p * y) % p == gcd
if gcd != 1:
# Either n is 0, or p is not a prime number.
raise ValueError(
'{} has no multiplicative inverse '
'modulo {}'.format(n, p))
else:
return x % p
def pickg(p):
for x in range (1,p):
rand = x
exp=1
next = rand % p
while (next <> 1 ):
next = (next*rand) % p
exp = exp+1
if (exp==p-1):
return rand
v = random.randint(1,n)
c = random.randint(1,n)
print "Password:\t",text
x = int(hashlib.md5(text).hexdigest()[:8], 16) % n
g=pickg(n)
y= pow(g,x,n)
t = pow(g,v,n)
r = (v - c * x)
if (r<0):
Result = ( inverse_of(pow(g,-r,n),n) * pow(y,c,n)) % n
else:
Result = ( pow(g,r,n) * pow(y,c,n)) % n
print '======Agreed parameters============'
print 'P=',n,'\t(Prime number)'
print 'G=',g,'\t(Generator)'
print '======The secret=================='
print 'x=',x,'\t(Alice\'s secret)'
print '======Random values==============='
print 'c=',c,'\t(Bob\'s random value)'
print 'v=',v,'\t(Alice\'s random value)'
print '======Shared value==============='
print 'g^x mod P=\t',y
print 'r=\t\t',r
print '=========Resuts==================='
print 't=g**v % n =\t\t',t
print '( (g**r) * (y**c) )=\t',Result
if (t==Result):
print 'Alice has proven she knows password'
else:
print 'Alice has not proven she knows x'
You are try here (and with a prime number of 997 and a g value of 7), but a sample run is:
Password: hello
======Agreed parameters============
P= 997 (Prime number)
G= 7 (Generator)
======The secret==================
x= 149 (Alice's secret)
======Random values===============
c= 4 (Bob's random value)
v= 150 (Alice's random value)
======Shared value===============
g^x mod P= 116
r= -446
=========Resuts===================
t=g**v % n = 812
( (g**r) * (y**c) )= 812
Alice has proven she knows password
A demo of the method I will show here is defined here. I have tried to simply the technique in order to demonstrate the key principles involved.
Conclusions
And that is it. Eve does not have the computing power to work out Peggy’s password, and Victor doesn’t know it either. That is a world that puts Peggy at the centre, and pushes Victor to the edge.
We need to move to a world where we respect citizen’s rights to privacy, and a core part of this is to allow them to preserve the data that they do not want known. For passwords, we still live in the 1980s, and we blindly build systems which give away a great deal of our most sensitive information. For Victor and Eve, that is fine, but, increasingly our world should be build for Peggy, and not Victor or Eve.
Go build a world for Peggy, and leave Eve with a massive electricity bill. For Victor, those who will change their ways, will benefit most from the new world that we are building. And for those Victor’s who stay the same, they will go the way of the dinosaurs. A new era begins …