cpace.go

// Copyright 2020 Google LLC
//
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file or at
// https://developers.google.com/open-source/licenses/bsd

// Package cpace implements the CPace password authenticated key exchange (PAKE)
// instantiated with the ristretto255 group.
//
// PAKEs allow two peers to establish a shared secret key if they agree on a
// password or similar low-entropy value, without letting eavesdropping or
// machine-in-the-middle attackers make multiple attempts at guessing the
// password value. CPace is a balanced PAKE, meaning that both peers need to
// know the password plaintext.
//
// This implementation is loosely based on draft-haase-cpace-01.
package cpace

import (
	"crypto/hmac"
	"crypto/rand"
	"crypto/sha256"
	"errors"

	"github.com/gtank/ristretto255"
	"golang.org/x/crypto/cryptobyte"
	"golang.org/x/crypto/hkdf"
)

// ContextInfo captures the additional connection information that the two peers
// need to agree on for the key to be the same.
type ContextInfo struct {
	idA, idB string
	ad       []byte
}

// NewContextInfo returns a ContextInfo for use with Start or Exchange.
//
// idA represents the identity of the party that uses Start, idB of the party
// that uses Exchange. Identities could be MAC addresses, or IPs and ports.
//
// ad is any additional context the two parties share, and can be nil. Examples
// of values that could be included in ad to protect against protocol downgrade
// and mismatch attacks are the name and transcript of the higher level
// protocol, including any negotiation inputs that led to the use of this PAKE.
func NewContextInfo(idA, idB string, ad []byte) *ContextInfo {
	return &ContextInfo{
		idA: idA, idB: idB, ad: ad,
	}
}

func (c *ContextInfo) validate() error {
	switch {
	case c == nil:
		return errors.New("cpace: ContextInfo can't be nil")
	case len(c.idA) >= 1<<16:
		return errors.New("cpace: idA too long")
	case len(c.idB) >= 1<<16:
		return errors.New("cpace: idB too long")
	case len(c.ad) >= 1<<16:
		return errors.New("cpace: additional data too long")
	default:
		return nil
	}
}

const label = "cpace-r255"

func (c *ContextInfo) serialize() []byte {
	b := &cryptobyte.Builder{}
	for _, in := range [][]byte{
		[]byte(label), []byte(c.idA), []byte(c.idB), c.ad,
	} {
		b.AddUint16LengthPrefixed(func(b *cryptobyte.Builder) {
			b.AddBytes(in)
		})
	}
	return b.BytesOrPanic()
}

func secretGenerator(password string, salt []byte, c *ContextInfo) *ristretto255.Element {
	h := hkdf.New(sha256.New, []byte(password), salt, c.serialize())
	b := make([]byte, 64)
	h.Read(b)
	return ristretto255.NewElement().FromUniformBytes(b)
}

func randomScalar() (*ristretto255.Scalar, error) {
	b := make([]byte, 64)
	if _, err := rand.Read(b); err != nil {
		return nil, err
	}
	return ristretto255.NewScalar().FromUniformBytes(b), nil
}

// State is a PAKE session in progress, where the initiating party is waiting
// for the peer response.
type State struct {
	transcript []byte
	secret     *ristretto255.Scalar
}

// Start initiates a new PAKE exchange authenticated by password. msgA should be
// sent to the peer, to be processed by Exchange, and s used to process the
// peer's response.
func Start(password string, c *ContextInfo) (msgA []byte, s *State, err error) {
	if err := c.validate(); err != nil {
		return nil, nil, err
	}

	s = &State{}

	salt := make([]byte, 16, 16+32)
	if _, err := rand.Read(salt); err != nil {
		return nil, nil, err
	}

	s.secret, err = randomScalar()
	if err != nil {
		return nil, nil, err
	}

	A := secretGenerator(password, salt, c)
	A.ScalarMult(s.secret, A)

	msgA = A.Encode(salt)

	s.transcript = make([]byte, 16+32, 16+32+32)
	copy(s.transcript, msgA)

	return msgA, s, nil
}

var identity = ristretto255.NewElement()

func deriveKey(peerElement, transcript []byte, secret *ristretto255.Scalar) ([]byte, error) {
	K := ristretto255.NewElement()
	if err := K.Decode(peerElement); err != nil {
		return nil, errors.New("cpace: invalid peer message")
	}
	K.ScalarMult(secret, K)

	// draft-haase-cpace-01 requires checking for the identity element at this
	// stage, but also overloads the identity as the output for invalid peer
	// points (for curves where that check is necessary like P-256) and for
	// degenerate scalar multiplications (for curves with cofactors). In a safe
	// prime order group with an error-checking decode function such as
	// ristretto255, this should not be necessary, as the transcript hash
	// guarantees contributory behavior, but it's cheap so we do it anyway.
	if K.Equal(identity) == 1 {
		return nil, errors.New("cpace: invalid peer message")
	}

	h := hmac.New(sha256.New, transcript)
	h.Write(K.Encode(nil))
	return h.Sum(nil), nil
}

// Finish processes the peer's response, generated by Exchange, and returns the
// shared secret key.
//
// If the two peers agree on the password and ContextInfo, they will derive the
// same key. Note that an error is NOT returned otherwise: the two peers will
// simply derive different keys.
//
// The returned key is suitable to be passed to hkdf.Expand.
func (s *State) Finish(msgB []byte) (key []byte, err error) {
	if len(msgB) != 32 {
		return nil, errors.New("cpace: invalid peer message")
	}

	transcript := append(s.transcript, msgB...)
	return deriveKey(msgB, transcript, s.secret)
}

// Exchange executes a PAKE exchange authenticated by password, processing msgA
// generated by a peer with Start, and returns the shared secret key and msgB.
// msgB should be sent to the peer, to be processed by (*State).Finish.
//
// If the two peers agree on the password and ContextInfo, they will derive the
// same key. Note that an error is NOT returned otherwise: the two peers will
// simply derive different keys.
//
// The returned key is suitable to be passed to hkdf.Expand.
func Exchange(password string, c *ContextInfo, msgA []byte) (msgB, key []byte, err error) {
	if err := c.validate(); err != nil {
		return nil, nil, err
	}

	if len(msgA) != 16+32 {
		return nil, nil, errors.New("cpace: invalid peer message")
	}
	salt := msgA[:16]
	encodedA := msgA[16:]

	secret, err := randomScalar()
	if err != nil {
		return nil, nil, err
	}

	x := secretGenerator(password, salt, c)
	x.ScalarMult(secret, x)

	msgB = make([]byte, 0, 32)
	msgB = x.Encode(msgB)

	transcript := make([]byte, 0, 16+32+32)
	transcript = append(transcript, msgA...)
	transcript = append(transcript, msgB...)

	key, err = deriveKey(encodedA, transcript, secret)
	if err != nil {
		return nil, nil, err
	}

	return msgB, key, nil
}