Git Patch for generating Known Answer Tests ( KATs ) from FrodoKEM Reference Implementation

frodokem_kat.patch

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')

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