Goodbye to the Creator of the Password, And Also Goodbye to Passwords?

Goodbye to the Creator of the Password, And Also Goodbye to Passwords?

Non-interactive zero-knowledge (NIZK) proofs for the equality (EQ) of discrete logarithms (DL)

In May 2019, the creator of the password — Fernando Corbato — died at the age of 93. He also worked on time-sharing methods within the Massachusetts Institute of Technology (MIT).

But why do passwords even exist in this modern digital world, and why do we still send them to companies? They are at the root of privacy and digital security, but still, we blindly pass our secrets over to companies that we don’t quite trust.

The whole concept of passwords and of password hashing is a historical thing from the past — and where there was little thought of the global Internet that we have now. Initially we one stored the password itself in a restricted place, and then we evolved to store a one-way version of the password — the hash. Unfortunately, the one-way function can be easily broken with either a dictionary attack or brute force. So then we added in salt, but the salt is stored with the hashed password so that it is not that difficult to create a dictionary attack on our password. Once discovered, we could cause many problems, especially if the user has used the same password on many different systems.

But there is a better way … Non-interactive zero-knowledge (NIZK) proofs, and where Peggy (the ‘Prover’) just has to prove that she still knows her secret. For this Victor (the ‘Verifier’) can send Peggy a challenge, and where Peggy can prove that she can provide a solution for it.

And so I’ve been reviewed some good from the Kyber Github repository, and there’s a method named DLEQ, and which implements NIZK using elliptic curve methods [demo].

Initially, Peggy creates a secret value (x) and then we create two values xG and xH, and can check that log_G(xG)==log_H(xH). Peggy first creates her secret (x) from her password (x=Hash(Password)), and then calculates xG and xH, and where G and H are base points on an elliptic curve. She passes these values to Victor.

With the challenge, Victor generates a random value (v) and computes vG and vH. Next Victor creates a challenge (c) and which is a hash of xG,xH,vG,vH:

c=H(xG,xH,vG,vH)

Peggy then responds back with:

r=v−cx

The proof this then (c,r,vG,vH). Victor then proves that Peggy still knows the secret with:

vG==rG+c(xG)

vH==rH+c(xH)

If both are equal, Peggy has proven that she still knows x. This works because:

rG+c(xG)=(v−cx)G+c(xG)=vG−cxG+cxG=vG

The following is the code [demo][taken from here]:

// Code from https://github.com/dedis/kyber
package main

import (
    "fmt"

    "go.dedis.ch/kyber"
    "go.dedis.ch/kyber/proof/dleq"
    "go.dedis.ch/kyber/suites"
    "go.dedis.ch/kyber/group/edwards25519"
    "go.dedis.ch/kyber/util/random"
    "crypto/sha256"
    "os"
    "errors"

)

var rng = random.New()

func NewDLEQProof(suite suites.Suite, G kyber.Point, H kyber.Point, x kyber.Scalar) (proof *dleq.Proof, xG kyber.Point, xH kyber.Point, err error) {
    // Encrypt base points with secret
    xG = suite.Point().Mul(x, G)
    xH = suite.Point().Mul(x, H)

    // Commitment
    v := suite.Scalar().Pick(suite.RandomStream())
    vG := suite.Point().Mul(v, G)
    vH := suite.Point().Mul(v, H)

    // Challenge
    h := suite.Hash()
    xG.MarshalTo(h)
    xH.MarshalTo(h)
    vG.MarshalTo(h)
    vH.MarshalTo(h)
    cb := h.Sum(nil)
    c := suite.Scalar().Pick(suite.XOF(cb))

    // Response
    r := suite.Scalar()
    r.Mul(x, c).Sub(v, r)

    return &dleq.Proof{c, r, vG, vH}, xG, xH, nil
}

func Verify(p *dleq.Proof, suite suites.Suite, G kyber.Point, H kyber.Point, xG kyber.Point, xH kyber.Point) error {
    rG := suite.Point().Mul(p.R, G)
    rH := suite.Point().Mul(p.R, H)
    cxG := suite.Point().Mul(p.C, xG)
    cxH := suite.Point().Mul(p.C, xH)
    a := suite.Point().Add(rG, cxG)
    b := suite.Point().Add(rH, cxH)
    if !(p.VG.Equal(a) && p.VH.Equal(b)) {
        return  errors.New("invalid proof")
    }
    return nil
}

func main() {

    suite := edwards25519.NewBlakeSHA256Ed25519()

    m:="Hello"

    argCount := len(os.Args[1:])

        if (argCount>0) {m= string(os.Args[1])}

    message := []byte(m)
    scal := sha256.Sum256(message[:])

    x := suite.Scalar().SetBytes(scal[:32])

    g := suite.Point().Pick(rng)
    h := suite.Point().Pick(rng)

    proof, xG, xH, err := NewDLEQProof(suite, g, h, x)

    if (err==nil) {
        fmt.Printf("Secret: %s\n",m) 
        fmt.Printf("x: %x\n\n",scal) 
        fmt.Printf("xG %s\nxH %s\n",xG,xH) 
 
        fmt.Printf("\nProof created\nChallenge: %s\nRandom: %s\nvG: %s\nvH: %s",proof.C,proof.R,proof.VG,proof.VH) 
    }

    rtn:=Verify(proof,suite, g, h, xG, xH)

    if (rtn==nil) { fmt.Printf("\nProven") }

}

A sample run is [demo]:

Secret: Testing 123

x: 9734aef6d3788ba985e78f7b3785dc4817e770be92a4e5e57e64a92cc9c2fc25

xG 30588dee051cd61c23543adf7ba0b02e81c510948535fc93b4162333cf2853ea
xH 2a39911a1168cddf21698ffd728b8526c62c5133826af3d9732af02bcd58f03e

Proof created
Challenge: b2f64ac7710ec266517236f4257fdae6efe86e6b5901204895298e1f187c810a
Random: 722283f5b18ec7a4929d19d2871fb43bcf533dec0f58c79ecd1bf85087010409
vG: 73805a0b082ad6cf761a01c19016eaedc8c70910b9fc9fb4ffe166d28851d4e4
vH: db33cafb98b9aa9ac24b98ac908df06f19e91374aeafdb267d9ef4f941b86f74
Proven

And there you go. In the week when we lost the creator of the password, the whole concept of the password is now being questioned.