Skip to content

Instantly share code, notes, and snippets.

@itzmeanjan
Last active September 12, 2023 18:47
Show Gist options
  • Save itzmeanjan/38d506a69073bdeb0933245401f42186 to your computer and use it in GitHub Desktop.
Save itzmeanjan/38d506a69073bdeb0933245401f42186 to your computer and use it in GitHub Desktop.
Git Patch for generating Known Answer Tests ( KATs ) from FrodoKEM Reference Implementation
diff --git a/FrodoKEM/python3/frodokem.py b/FrodoKEM/python3/frodokem.py
index 731cb0e..c701108 100644
--- a/FrodoKEM/python3/frodokem.py
+++ b/FrodoKEM/python3/frodokem.py
@@ -4,6 +4,7 @@
import bitstring
import math
+import sys
import secrets
import struct
import warnings
@@ -454,7 +455,7 @@ class FrodoKEM(object):
A[i][j] = c_i[j] % self.q
return A
- def kem_keygen(self):
+ def kem_keygen(self, fh = sys.stdout):
"""Generate a public key / secret key pair (FrodoKEM specification,
Algorithm 12)"""
# 1. Choose uniformly random seeds s || seedSE || z
@@ -463,6 +464,11 @@ class FrodoKEM(object):
s = bytes(s_seedSE_z[0:self.len_s_bytes])
seedSE = bytes(s_seedSE_z[self.len_s_bytes : self.len_s_bytes + self.len_seedSE_bytes])
z = bytes(s_seedSE_z[self.len_s_bytes + self.len_seedSE_bytes : self.len_s_bytes + self.len_seedSE_bytes + self.len_z_bytes])
+
+ print(f's = {s.hex()}', file=fh)
+ print(f'seedSE = {seedSE.hex()}', file=fh)
+ print(f'z = {z.hex()}', file=fh)
+
# 2. Generate pseudorandom seed seedA = SHAKE(z, len_seedA) (length in bits)
seedA = self.shake(z, self.len_seedA_bytes)
self.__print_intermediate_value("seedA", seedA)
@@ -500,9 +506,13 @@ class FrodoKEM(object):
sk.append(pkh)
sk = sk.bytes
assert len(sk) == self.len_sk_bytes
+
+ print(f'pkey = {pk.hex()}', file=fh)
+ print(f'skey = {sk.hex()}', file=fh)
+
return (pk, sk)
- def kem_encaps(self, pk):
+ def kem_encaps(self, pk, fh = sys.stdout):
"""Encapsulate against a public key to create a ciphertext and shared secret
(FrodoKEM specification, Algorithm 13)"""
# Parse pk = seedA || b
@@ -513,6 +523,10 @@ class FrodoKEM(object):
mu_salt = self.randombytes(self.len_mu_bytes + self.len_salt_bytes)
mu = mu_salt[0:self.len_mu_bytes]
salt = mu_salt[self.len_mu_bytes:self.len_mu_bytes + self.len_salt_bytes]
+
+ print(f'μ = {mu.hex()}', file=fh)
+ print(f'salt = {salt.hex()}', file=fh)
+
self.__print_intermediate_value("mu", mu)
self.__print_intermediate_value("salt", salt)
# 2. pkh = SHAKE(pk, len_pkh)
@@ -563,6 +577,11 @@ class FrodoKEM(object):
ct = c1 + c2 + salt
assert len(ct) == self.len_ct_bytes
assert len(ss) == self.len_ss_bytes
+
+ print(f'ct = {ct.hex()}', file=fh)
+ print(f'ss = {ss.hex()}', file=fh)
+ print('', file=fh)
+
return (ct, ss)
def kem_decaps(self, sk, ct):
@@ -660,3 +679,36 @@ class FrodoKEM(object):
ss = self.shake(c1 + c2 + salt + kbar, self.len_ss_bytes)
assert len(ss) == self.len_ss_bytes
return ss
+
+if __name__ == '__main__':
+ KNOWN_ANSWER_TEST_COUNT = 64
+
+ with open('FrodoKEM640_KAT.txt', 'w') as fh:
+ frodo640_shake = FrodoKEM("FrodoKEM-640-SHAKE")
+ for _ in range(KNOWN_ANSWER_TEST_COUNT):
+ (pk, sk) = frodo640_shake.kem_keygen(fh)
+ (ct, ss0) = frodo640_shake.kem_encaps(pk, fh)
+ ss1 = frodo640_shake.kem_decaps(sk, ct)
+
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM640-SHAKE"
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-640-SHAKE, written to FrodoKEM640_KAT.txt')
+
+ with open('FrodoKEM976_KAT.txt', 'w') as fh:
+ frodo976_shake = FrodoKEM("FrodoKEM-976-SHAKE")
+ for _ in range(KNOWN_ANSWER_TEST_COUNT):
+ (pk, sk) = frodo976_shake.kem_keygen(fh)
+ (ct, ss0) = frodo976_shake.kem_encaps(pk, fh)
+ ss1 = frodo976_shake.kem_decaps(sk, ct)
+
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM976-SHAKE"
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-976-SHAKE, written to FrodoKEM976_KAT.txt')
+
+ with open('FrodoKEM1344_KAT.txt', 'w') as fh:
+ frodo1344_shake = FrodoKEM("FrodoKEM-1344-SHAKE")
+ for _ in range(KNOWN_ANSWER_TEST_COUNT):
+ (pk, sk) = frodo1344_shake.kem_keygen(fh)
+ (ct, ss0) = frodo1344_shake.kem_encaps(pk, fh)
+ ss1 = frodo1344_shake.kem_decaps(sk, ct)
+
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM1344-SHAKE"
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-1344-SHAKE, written to FrodoKEM1344_KAT.txt')
diff --git a/eFrodoKEM/python3/efrodokem.py b/eFrodoKEM/python3/efrodokem.py
index 07156b2..64b988c 100644
--- a/eFrodoKEM/python3/efrodokem.py
+++ b/eFrodoKEM/python3/efrodokem.py
@@ -4,6 +4,7 @@
import bitstring
import math
+import sys
import secrets
import struct
import warnings
@@ -448,7 +449,7 @@ class FrodoKEM(object):
A[i][j] = c_i[j] % self.q
return A
- def kem_keygen(self):
+ def kem_keygen(self, fh = sys.stdout):
"""Generate a public key / secret key pair (FrodoKEM specification,
Algorithm 12)"""
# 1. Choose uniformly random seeds s || seedSE || z
@@ -457,6 +458,11 @@ class FrodoKEM(object):
s = bytes(s_seedSE_z[0:self.len_s_bytes])
seedSE = bytes(s_seedSE_z[self.len_s_bytes : self.len_s_bytes + self.len_seedSE_bytes])
z = bytes(s_seedSE_z[self.len_s_bytes + self.len_seedSE_bytes : self.len_s_bytes + self.len_seedSE_bytes + self.len_z_bytes])
+
+ print(f's = {s.hex()}', file=fh)
+ print(f'seedSE = {seedSE.hex()}', file=fh)
+ print(f'z = {z.hex()}', file=fh)
+
# 2. Generate pseudorandom seed seedA = SHAKE(z, len_seedA) (length in bits)
seedA = self.shake(z, self.len_seedA_bytes)
self.__print_intermediate_value("seedA", seedA)
@@ -494,9 +500,13 @@ class FrodoKEM(object):
sk.append(pkh)
sk = sk.bytes
assert len(sk) == self.len_sk_bytes
+
+ print(f'pkey = {pk.hex()}', file=fh)
+ print(f'skey = {sk.hex()}', file=fh)
+
return (pk, sk)
- def kem_encaps(self, pk):
+ def kem_encaps(self, pk, fh = sys.stdout):
"""Encapsulate against a public key to create a ciphertext and shared secret
(FrodoKEM specification, Algorithm 13)"""
# Parse pk = seedA || b
@@ -505,6 +515,9 @@ class FrodoKEM(object):
b = pk[self.len_seedA_bytes:]
# 1. Choose a uniformly random key mu in {0,1}^len_mu (length in bits)
mu = self.randombytes(self.len_mu_bytes)
+
+ print(f'μ = {mu.hex()}', file=fh)
+
self.__print_intermediate_value("mu", mu)
# 2. pkh = SHAKE(pk, len_pkh)
pkh = self.shake(pk, self.len_pkh_bytes)
@@ -554,6 +567,11 @@ class FrodoKEM(object):
ct = c1 + c2
assert len(ct) == self.len_ct_bytes
assert len(ss) == self.len_ss_bytes
+
+ print(f'ct = {ct.hex()}', file=fh)
+ print(f'ss = {ss.hex()}', file=fh)
+ print('', file=fh)
+
return (ct, ss)
def kem_decaps(self, sk, ct):
@@ -648,3 +666,36 @@ class FrodoKEM(object):
ss = self.shake(c1 + c2 + kbar, self.len_ss_bytes)
assert len(ss) == self.len_ss_bytes
return ss
+
+if __name__ == '__main__':
+ KNOWN_ANSWER_TEST_COUNT = 64
+
+ with open('eFrodoKEM640_KAT.txt', 'w') as fh:
+ frodo640_shake = FrodoKEM("FrodoKEM-640-SHAKE")
+ for _ in range(KNOWN_ANSWER_TEST_COUNT):
+ (pk, sk) = frodo640_shake.kem_keygen(fh)
+ (ct, ss0) = frodo640_shake.kem_encaps(pk, fh)
+ ss1 = frodo640_shake.kem_decaps(sk, ct)
+
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM640-SHAKE"
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-640-SHAKE, written to eFrodoKEM640_KAT.txt')
+
+ with open('eFrodoKEM976_KAT.txt', 'w') as fh:
+ frodo976_shake = FrodoKEM("FrodoKEM-976-SHAKE")
+ for _ in range(KNOWN_ANSWER_TEST_COUNT):
+ (pk, sk) = frodo976_shake.kem_keygen(fh)
+ (ct, ss0) = frodo976_shake.kem_encaps(pk, fh)
+ ss1 = frodo976_shake.kem_decaps(sk, ct)
+
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM976-SHAKE"
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-976-SHAKE, written to eFrodoKEM976_KAT.txt')
+
+ with open('eFrodoKEM1344_KAT.txt', 'w') as fh:
+ frodo1344_shake = FrodoKEM("FrodoKEM-1344-SHAKE")
+ for _ in range(KNOWN_ANSWER_TEST_COUNT):
+ (pk, sk) = frodo1344_shake.kem_keygen(fh)
+ (ct, ss0) = frodo1344_shake.kem_encaps(pk, fh)
+ ss1 = frodo1344_shake.kem_decaps(sk, ct)
+
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM1344-SHAKE"
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-1344-SHAKE, written to eFrodoKEM1344_KAT.txt')
@itzmeanjan
Copy link
Author

itzmeanjan commented May 19, 2023

Overview

You can follow below steps for generating known answer tests (KATs) for {e}FrodoKEM-{640, 976, 1344} ( with SHAKE128 for generation of matrix A ), which can be used with my C++ library implementation of FrodoKEM ( more @ https://github.com/itzmeanjan/frodokem ) for ensuring its functional correctness and conformance with the specification.

Note Corresponding FrodoKEM specification that you need to look at side by side lives @ https://frodokem.org/files/FrodoKEM-standard_proposal-20230314.pdf.

Steps

  • Clone the repository holding FrodoKEM reference implementation.
git clone https://github.com/microsoft/PQCrypto-LWEKE.git
  • Pin repository to specific commit.
git checkout a2f9dec8917ccc3464b3378d46b140fa7353320d
  • Clone/ download ( and unzip ) this gist.
  • Copy git patch file frodokem_kat.patch into directory PQCrypto-LWEKE.
  • Issue following command for applying the git patch.
git apply frodokem_kat.patch
git status # see files changed (optional)
git diff   # see changes (optional)
  • Create python virtual environment and install dependencies.
python3 -m venv . # more @ https://docs.python.org/3/library/venv.html
source bin/activate

# notice change in SHELL prompt
# now inside virtual environment

pip install bitstring
pip install cryptography
  • Run scripts for generating KATs.
python FrodoKEM/python3/frodokem.py
python eFrodoKEM/python3/efrodokem.py

deactivate
# just left virtual environment
# notice change in SHELL prompt
  • Generated KAT files should look like.
$ find . -name '*KAT.txt'

./FrodoKEM1344_KAT.txt
./FrodoKEM640_KAT.txt
./eFrodoKEM1344_KAT.txt
./eFrodoKEM640_KAT.txt
./FrodoKEM976_KAT.txt
./eFrodoKEM976_KAT.txt

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment