Key Encapsulation Mechanism exploration for Identity Based derivation. (No warranty) #Kyber #KEM #X25519

ib-kem.go

// MIT License
//
// Copyright (c) 2020 Thibault Normand
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

package main

import (
	"bytes"
	"crypto/rand"
	"crypto/sha256"
	"encoding/base64"
	"encoding/binary"
	"fmt"
	"io"
	"os"
	"time"

	"github.com/cloudflare/circl/kem/schemes"
	"golang.org/x/crypto/blake2b"
	"golang.org/x/crypto/curve25519"
	"golang.org/x/crypto/hkdf"
	"golang.org/x/crypto/nacl/box"
)

// General
//  * No digital signature (not yet) => delegated to message payload.
//  * Time limited identity and data expiration by design.
//
// Actor(s):
// - Alice is an external (out of trust boundary) client who need to send data to Bob.
//  * No initial crypto material exchange should be done.
//  * Master Public Key and Kyber group should be retrieved from a public endpoint
//  * No authentication for Alice.
// - Bob is an internal client who will receive the data sent by Alice
//  * Encryption key retrieval is subject to authorization
//  * Bob is identified, authenticated and authorized to PKG
// - PKG is an internal service
//  * Provide shared encryption key from received message if consumer is authorized and identity is not expired.
//  * Control access to master private key and encryption key retrieval by authenticated consumers.

// Encryption could be delegated to AES256 / CHACHA20.

func main() {
	// -------------------------------------------------------------------------
	// PKG (Private Key Generator)
	// Initialize master keypair.
	mPk, mSk, err := box.GenerateKey(bytes.NewReader([]byte("0000-deterministic-buffer-for-tests")))
	if err != nil {
		panic(err)
	}

	// Set Kyber768 for KEM
	kem := schemes.ByName("kyber768")

	// -------------------------------------------------------------------------
	// Alice

	// Generate a deterministic identity
	ts := time.Now().AddDate(0, 0, 7)
	recipientID, err := deriveIdentity("bob@example.com", ts)
	if err != nil {
		panic(err)
	}

	// Generate ephemeral keypair
	ephPub, ephPriv, err := box.GenerateKey(rand.Reader)
	if err != nil {
		panic(err)
	}

	// ECDH for MasterKey binding
	pkgSecret, err := curve25519.X25519(ephPriv[:], mPk[:])
	if err != nil {
		panic(err)
	}

	// Generate a 64 bytes array used as seed for KEM key generation.
	// This sedd will be bound to master public key via ECDH.
	recipientSeed, err := packSeed(pkgSecret, mPk[:], ephPub[:], recipientID, kem.SeedSize())
	if err != nil {
		panic(err)
	}

	// Create kyber keys from seed
	pk, _ := kem.DeriveKey(recipientSeed)

	// Encapsulate public key and generate shared secret.
	ct, ss, err := kem.Encapsulate(pk)
	if err != nil {
		panic(err)
	}

	fmt.Fprintf(os.Stdout, "A> EncapsulatedPublicKem: %s\n", base64.RawURLEncoding.EncodeToString(ct))
	fmt.Fprintf(os.Stdout, "A> SharedSecret: %s\n", base64.RawURLEncoding.EncodeToString(ss))

	// Send to bob
	fmt.Fprintf(os.Stdout, "A> Send to Bob [ts || EphPub || ct || enc(Msg, sharedSecret)]\n")

	// -------------------------------------------------------------------------
	// Bob
	fmt.Fprintln(os.Stdout)

	fmt.Fprintf(os.Stdout, "B> Extract ts, EphPub, ct\n")

	fmt.Fprintf(os.Stdout, "B> Send to PKG (id:bob@example.com, ts:%d, ct:%s, ephPub:%s)\n", ts.Unix(), base64.RawURLEncoding.EncodeToString(ct), base64.RawURLEncoding.EncodeToString(ephPub[:]))

	// -------------------------------------------------------------------------
	// PKG
	fmt.Fprintln(os.Stdout)

	{
		// Validate timestamp.
		// Derive identity from authentication information
		bobID, err := deriveIdentity("bob@example.com", ts)
		if err != nil {
			panic(err)
		}

		// ECDH for MasterKey binding
		pkgSecret, err := curve25519.X25519(mSk[:], ephPub[:])
		if err != nil {
			panic(err)
		}

		// Generate seed
		bobSeed, err := packSeed(pkgSecret, mPk[:], ephPub[:], bobID, kem.SeedSize())
		if err != nil {
			panic(err)
		}

		// Create kyber keys from seed
		_, bobSk := kem.DeriveKey(bobSeed)
		fmt.Fprintf(os.Stdout, "PKG> Derive Bob identity\n")

		// Decapsulate
		sharedSecret, err := kem.Decapsulate(bobSk, ct)
		if err != nil {
			panic(err)
		}

		fmt.Fprintf(os.Stdout, "PKG> Reply to Bob (Session Key): %s\n", base64.RawURLEncoding.EncodeToString(sharedSecret))
	}

	// -------------------------------------------------------------------------
	// Bob
	fmt.Fprintln(os.Stdout)

	fmt.Fprintf(os.Stdout, "B> Decrypt data\n")

}

// -----------------------------------------------------------------------------

func deriveIdentity(name string, expiresOn time.Time) ([]byte, error) {
	// Prepare protected identity
	ts := make([]byte, 8)
	binary.BigEndian.PutUint64(ts, uint64(expiresOn.Unix()))

	// Prepare buffer to derive
	var buf bytes.Buffer
	buf.WriteString(name)   // Recipient string
	buf.Write([]byte{0x00}) // Always add null byte after ascii string
	buf.Write(ts)           // Encoded expiration

	// Initialize hash function to bind recipient and timestamp. (64 Bytes)
	hID, err := blake2b.New512([]byte("harp identity derivation"))
	if err != nil {
		return nil, fmt.Errorf("unable to initialize salt: %w", err)
	}
	if _, err := hID.Write(buf.Bytes()); err != nil {
		return nil, fmt.Errorf("unable to update identity hash state: %w", err)
	}

	// Return determistic identifier
	return hID.Sum(nil), nil
}

func packSeed(sharedSecret, masterPublicKey, ephemeralPublicKey, id []byte, seedSize int) ([]byte, error) {
	// Bind all public informations
	var salt bytes.Buffer
	salt.Write(id)                    // Identity
	salt.Write(masterPublicKey)       // Master Public Key
	salt.Write(ephemeralPublicKey[:]) // Ephemeral Public Key

	// Apply hkdf
	dk := hkdf.New(sha256.New, sharedSecret, salt.Bytes(), []byte("harp:v1:identity:seed"))
	seed := make([]byte, seedSize)
	if _, err := io.ReadFull(dk, seed); err != nil {
		return nil, fmt.Errorf("unable to generate seed: %w", err)
	}

	// Return seed
	return seed, nil
}

output.txt

A> EncapsulatedPublicKem: FwKSHeyKk_IMkOOwZChlZdEumTW7Oib-Y189sDy8qJmveRFEAGOcRzAWwih4b4RLTOjI7Pt_Ctv97Gr5-nn6KgRtAzUr2iPILZ8M1o9bi3X18DSF-iWbZsKj8n6RLT-cXartqZzD50bOefqexCDr0jgrneVaXELN9aoNU9KqnKLYSsqlxmfUOhq40w14UhRhR9KDuWsyzac5Pm-yuOkBcGt_vbbcO2cqOXrGVjxzH2fO8YZ8DRE_7eNxKc-ZcM0ESyxCOwnVOovpQFQusT5gI-6dJh07nAnNzEilyMqtm9COf37jMYllJpUe4AEt4qV1mSZ22gxIHQZBpw6vSzp0bYkpJauJlTSCv1CBXpcUzbRPF4xR8Sh59huskIf2wHR087zQvuJHQgTLvS40WI-y1ETDjs1tVBae0VeT0E5WlOJTIS0gmed9xaF9Rrw836qKGW93O6pxa8PbugUJXDoS7vIxP8LuUSmXG91cgy64sRjApJV4cqiUNUPG02IawtXTiZ1AjwLAE3L_qABT5FoXyjAtunQmWc1Hw2DYiQ49JHZViWf3eobouPFwdlY4AJgdsQbzbrxMmp20SkDh8MHZgDuBiEbCX-sFDZdwfu040GaWafnBRCMNOoXkIxTd4qTEVYqcZBvT6jWQt9sSD6X9DHSbPxorZnFFT21sq3lThG6uSIEhfaZT4mRM3YtzbWutuye5eaN_v-zHYSzQ_mAOSatTJ8Ci5Cb1sgP_OJZ_IFhbzLaQzk8Ytm8Gf17J0eOEs4sbidfVaDlk2La7f110RHUoRHiVuMO8S7EPtbyF5zqrq3YDcW8v5lEMUHucTr--jsmW1mv8M2xE4WtLFXN7pOGSZ3yf07co-YN52P05-gH3b7Jd0dzKf6j9R6OFYwPSJrubRYJ5Nq5ztC-hthiymH_G3qeV2tKqFU38AvXBDlCwMr1kVEQkoiL6ExBADagLSzEfIp9zEK5DHJ9xqPqIAjwpeBJ1czLloFyWhGhITAs5ALxqJCflPPfmp4AfDSqOyfttFg55nFhOTa6k9EWk_kiFgJWpdaxKq5OrDztRkwpgERMB4ULk_IVOqyRC1gHoatvac78I9DA0NtFP4rLCOIjjMnDDZ8SLXZebFRiDwEm0VV0plU39gvvUIyi2hRa0V1YrVW6t0gfVeLZsjSS_rrJh2fJ2TX4yK6tE3ONAByzNfRWes8LHOPyIJIqJMlamW_5q665DJt44XNzTyCYUpkE1S_u-e9jGWUfkJMJSrRrDrXsUMAtG82nP_AzAxeE46HeDQOA1uOCBN_a1W1J4XeDpn8W-AFho2hIL0T6Mj1D6ouiQNtJOY2bx4OwbCR3TSK4UUoAVKfLxSlJ_iVJafHEWMeSUt9Kj0YslyWaNaQimQ5p0lzxZy_AVDv0_7kDIkwkAaDaidK3vapjMdiuv0L2UjlaNZ40qnoA8Rrz8HxE
A> SessionKey: 6YaJaZMjMUZ7ZKYhzayF9d-i-MxvDgrS5v3sHE7UQVk
A> Send to Bob [ts || EphPub || ct || enc(Msg, sessionKey)]

B> Extract ts, EphPub, ct
B> Send to PKG (id:bob@example.com, ts:1606121729, ct:FwKSHeyKk_IMkOOwZChlZdEumTW7Oib-Y189sDy8qJmveRFEAGOcRzAWwih4b4RLTOjI7Pt_Ctv97Gr5-nn6KgRtAzUr2iPILZ8M1o9bi3X18DSF-iWbZsKj8n6RLT-cXartqZzD50bOefqexCDr0jgrneVaXELN9aoNU9KqnKLYSsqlxmfUOhq40w14UhRhR9KDuWsyzac5Pm-yuOkBcGt_vbbcO2cqOXrGVjxzH2fO8YZ8DRE_7eNxKc-ZcM0ESyxCOwnVOovpQFQusT5gI-6dJh07nAnNzEilyMqtm9COf37jMYllJpUe4AEt4qV1mSZ22gxIHQZBpw6vSzp0bYkpJauJlTSCv1CBXpcUzbRPF4xR8Sh59huskIf2wHR087zQvuJHQgTLvS40WI-y1ETDjs1tVBae0VeT0E5WlOJTIS0gmed9xaF9Rrw836qKGW93O6pxa8PbugUJXDoS7vIxP8LuUSmXG91cgy64sRjApJV4cqiUNUPG02IawtXTiZ1AjwLAE3L_qABT5FoXyjAtunQmWc1Hw2DYiQ49JHZViWf3eobouPFwdlY4AJgdsQbzbrxMmp20SkDh8MHZgDuBiEbCX-sFDZdwfu040GaWafnBRCMNOoXkIxTd4qTEVYqcZBvT6jWQt9sSD6X9DHSbPxorZnFFT21sq3lThG6uSIEhfaZT4mRM3YtzbWutuye5eaN_v-zHYSzQ_mAOSatTJ8Ci5Cb1sgP_OJZ_IFhbzLaQzk8Ytm8Gf17J0eOEs4sbidfVaDlk2La7f110RHUoRHiVuMO8S7EPtbyF5zqrq3YDcW8v5lEMUHucTr--jsmW1mv8M2xE4WtLFXN7pOGSZ3yf07co-YN52P05-gH3b7Jd0dzKf6j9R6OFYwPSJrubRYJ5Nq5ztC-hthiymH_G3qeV2tKqFU38AvXBDlCwMr1kVEQkoiL6ExBADagLSzEfIp9zEK5DHJ9xqPqIAjwpeBJ1czLloFyWhGhITAs5ALxqJCflPPfmp4AfDSqOyfttFg55nFhOTa6k9EWk_kiFgJWpdaxKq5OrDztRkwpgERMB4ULk_IVOqyRC1gHoatvac78I9DA0NtFP4rLCOIjjMnDDZ8SLXZebFRiDwEm0VV0plU39gvvUIyi2hRa0V1YrVW6t0gfVeLZsjSS_rrJh2fJ2TX4yK6tE3ONAByzNfRWes8LHOPyIJIqJMlamW_5q665DJt44XNzTyCYUpkE1S_u-e9jGWUfkJMJSrRrDrXsUMAtG82nP_AzAxeE46HeDQOA1uOCBN_a1W1J4XeDpn8W-AFho2hIL0T6Mj1D6ouiQNtJOY2bx4OwbCR3TSK4UUoAVKfLxSlJ_iVJafHEWMeSUt9Kj0YslyWaNaQimQ5p0lzxZy_AVDv0_7kDIkwkAaDaidK3vapjMdiuv0L2UjlaNZ40qnoA8Rrz8HxE, ephPub:eXcrzMpIeO7TIn4JHkD4Vdi7U82jPdarW_oJCgWUl00)

PKG> Derive Bob identity
PKG> Reply to Bob (Session Key): 6YaJaZMjMUZ7ZKYhzayF9d-i-MxvDgrS5v3sHE7UQVk

B> Decrypt data