Skip to content

Instantly share code, notes, and snippets.

@itzmeanjan

itzmeanjan/saber_kem_kat.patch

Last active October 20, 2023 16:31
Show Gist options
  • Save itzmeanjan/e499eba2b8c42f150a795d9e1c3c5dea to your computer and use it in GitHub Desktop.
Save itzmeanjan/e499eba2b8c42f150a795d9e1c3c5dea to your computer and use it in GitHub Desktop.
Download ZIP
Git Patch for Generating Known Answer Tests ( KATs ) from Saber Reference Implementation
Raw
saber_kem_kat.patch
diff --git a/Reference_Implementation_KEM/Makefile b/Reference_Implementation_KEM/Makefile
index 7608e07..adfda63 100644
--- a/Reference_Implementation_KEM/Makefile
+++ b/Reference_Implementation_KEM/Makefile
@@ -14,13 +14,13 @@ SOURCES = pack_unpack.c poly.c fips202.c verify.c cbd.c SABER_indcpa.c kem.c
HEADERS = SABER_params.h pack_unpack.h poly.h rng.h fips202.h verify.h cbd.h SABER_indcpa.h
test/test_kex: $(SOURCES) $(HEADERS) rng.o test/test_kex.c
- $(CC) $(CFLAGS) -o $@ $(SOURCES) rng.o test/test_kex.c -lcrypto
+ $(CC) $(CFLAGS) -o $@ -DSABER_L=$(SABER_L) $(SOURCES) rng.o test/test_kex.c -lcrypto
test/PQCgenKAT_kem: $(SOURCES) $(HEADERS) rng.o test/PQCgenKAT_kem.c
- $(CC) $(NISTFLAGS) -o $@ $(SOURCES) rng.o test/PQCgenKAT_kem.c -lcrypto
+ $(CC) $(NISTFLAGS) -o $@ -DSABER_L=$(SABER_L) $(SOURCES) rng.o test/PQCgenKAT_kem.c -lcrypto
test/kem: $(SOURCES) $(HEADERS) rng.o test/kem.c
- $(CC) $(CFLAGS) -o $@ $(SOURCES) rng.o test/kem.c -lcrypto
+ $(CC) $(CFLAGS) -o $@ -DSABER_L=$(SABER_L) $(SOURCES) rng.o test/kem.c -lcrypto
rng.o: rng.c
$(CC) $(NISTFLAGS) -c rng.c -lcrypto -o $@
diff --git a/Reference_Implementation_KEM/SABER_indcpa.c b/Reference_Implementation_KEM/SABER_indcpa.c
index ef51b3a..0237c57 100644
--- a/Reference_Implementation_KEM/SABER_indcpa.c
+++ b/Reference_Implementation_KEM/SABER_indcpa.c
@@ -7,6 +7,7 @@
#include "rng.h"
#include "fips202.h"
#include "SABER_params.h"
+#include "hex_print.h"
#define h1 (1 << (SABER_EQ - SABER_EP - 1))
#define h2 ((1 << (SABER_EP - 2)) - (1 << (SABER_EP - SABER_ET - 1)) + (1 << (SABER_EQ - SABER_EP - 1)))
@@ -22,9 +23,16 @@ void indcpa_kem_keypair(uint8_t pk[SABER_INDCPA_PUBLICKEYBYTES], uint8_t sk[SABE
int i, j;
randombytes(seed_A, SABER_SEEDBYTES);
+
+ printf("seedA = ");
+ to_hex(seed_A, SABER_SEEDBYTES);
+
shake128(seed_A, SABER_SEEDBYTES, seed_A, SABER_SEEDBYTES); // for not revealing system RNG state
randombytes(seed_s, SABER_NOISE_SEEDBYTES);
+ printf("seedS = ");
+ to_hex(seed_s, SABER_NOISE_SEEDBYTES);
+
GenMatrix(A, seed_A);
GenSecret(s, seed_s);
MatrixVectorMul(A, s, b, 1);
diff --git a/Reference_Implementation_KEM/SABER_params.h b/Reference_Implementation_KEM/SABER_params.h
index e6674ae..c963d47 100644
--- a/Reference_Implementation_KEM/SABER_params.h
+++ b/Reference_Implementation_KEM/SABER_params.h
@@ -3,7 +3,7 @@
/* Change this for different security strengths */
// #define SABER_L 2 /* LightSaber */
-#define SABER_L 3 /* Saber */
+// #define SABER_L 3 /* Saber */
// #define SABER_L 4 /* FireSaber */
/* Don't change anything below this line */
diff --git a/Reference_Implementation_KEM/hex_print.h b/Reference_Implementation_KEM/hex_print.h
new file mode 100644
index 0000000..a9928ba
--- /dev/null
+++ b/Reference_Implementation_KEM/hex_print.h
@@ -0,0 +1,9 @@
+#include <stdio.h>
+#include <stdint.h>
+
+inline void to_hex(const uint8_t *const bytes, const size_t blen) {
+ for(size_t i = 0; i < blen; i++) {
+ printf("%02x", bytes[i]);
+ }
+ printf("\n");
+}
diff --git a/Reference_Implementation_KEM/kem.c b/Reference_Implementation_KEM/kem.c
index 7f319b5..3564232 100644
--- a/Reference_Implementation_KEM/kem.c
+++ b/Reference_Implementation_KEM/kem.c
@@ -7,6 +7,7 @@
#include "verify.h"
#include "rng.h"
#include "fips202.h"
+#include "hex_print.h"
int crypto_kem_keypair(unsigned char *pk, unsigned char *sk)
@@ -21,6 +22,14 @@ int crypto_kem_keypair(unsigned char *pk, unsigned char *sk)
randombytes(sk + SABER_SECRETKEYBYTES - SABER_KEYBYTES, SABER_KEYBYTES); // Remaining part of sk contains a pseudo-random number.
// This is output when check in crypto_kem_dec() fails.
+
+ printf("z = ");
+ to_hex(sk + SABER_SECRETKEYBYTES - SABER_KEYBYTES, SABER_KEYBYTES);
+ printf("pkey = ");
+ to_hex(pk, SABER_PUBLICKEYBYTES);
+ printf("skey = ");
+ to_hex(sk, SABER_SECRETKEYBYTES);
+
return (0);
}
@@ -32,6 +41,9 @@ int crypto_kem_enc(unsigned char *c, unsigned char *k, const unsigned char *pk)
randombytes(buf, 32);
+ printf("m = ");
+ to_hex(buf, 32);
+
sha3_256(buf, buf, 32); // BUF[0:31] <-- random message (will be used as the key for client) Note: hash doesnot release system RNG output
sha3_256(buf + 32, pk, SABER_INDCPA_PUBLICKEYBYTES); // BUF[32:63] <-- Hash(public key); Multitarget countermeasure for coins + contributory KEM
@@ -45,6 +57,12 @@ int crypto_kem_enc(unsigned char *c, unsigned char *k, const unsigned char *pk)
sha3_256(k, kr, 64); // hash concatenation of pre-k and h(c) to k
+ printf("ctxt = ");
+ to_hex(c, SABER_BYTES_CCA_DEC);
+ printf("ss = ");
+ to_hex(k, 32);
+ printf("\n");
+
return (0);
}
diff --git a/Variants/uSaber-90s/ref/Makefile b/Variants/uSaber-90s/ref/Makefile
index 9afe806..d9034ca 100644
--- a/Variants/uSaber-90s/ref/Makefile
+++ b/Variants/uSaber-90s/ref/Makefile
@@ -16,13 +16,13 @@ HEADERS = SABER_params.h pack_unpack.h poly.h rng.h verify.h cbd.h SABER_indcpa.
fips202.h aes256ctr.h sha2.h symmetric.h
test/test_kex: $(SOURCES) $(HEADERS) rng.o test/test_kex.c
- $(CC) $(CFLAGS) -o $@ $(SOURCES) rng.o test/test_kex.c -lcrypto
+ $(CC) $(CFLAGS) -o $@ -DSABER_L=$(SABER_L) $(SOURCES) rng.o test/test_kex.c -lcrypto
test/PQCgenKAT_kem: $(SOURCES) $(HEADERS) rng.o test/PQCgenKAT_kem.c
- $(CC) $(NISTFLAGS) -o $@ $(SOURCES) rng.o test/PQCgenKAT_kem.c -lcrypto
+ $(CC) $(NISTFLAGS) -o $@ -DSABER_L=$(SABER_L) $(SOURCES) rng.o test/PQCgenKAT_kem.c -lcrypto
test/kem: $(SOURCES) $(HEADERS) rng.o test/kem.c
- $(CC) $(CFLAGS) -o $@ $(SOURCES) rng.o test/kem.c -lcrypto
+ $(CC) $(CFLAGS) -o $@ -DSABER_L=$(SABER_L) $(SOURCES) rng.o test/kem.c -lcrypto
rng.o: rng.c
$(CC) $(NISTFLAGS) -c rng.c -lcrypto -o $@
@@ -43,4 +43,4 @@ clean:
-$(RM) -rf test/kem
-$(RM) -rf test/PQCgenKAT_kem
-$(RM) -f *.req
- -$(RM) -f *.rsp
\ No newline at end of file
+ -$(RM) -f *.rsp
diff --git a/Variants/uSaber-90s/ref/SABER_indcpa.c b/Variants/uSaber-90s/ref/SABER_indcpa.c
index fd69c91..e2bc83e 100644
--- a/Variants/uSaber-90s/ref/SABER_indcpa.c
+++ b/Variants/uSaber-90s/ref/SABER_indcpa.c
@@ -8,6 +8,7 @@
#include "fips202.h"
#include "SABER_params.h"
#include "symmetric.h"
+#include "hex_print.h"
/*-----------------------------------------------------------------------------------
This routine generates a=[Matrix K x K] of 256-coefficient polynomials
@@ -28,9 +29,16 @@ void indcpa_kem_keypair(uint8_t pk[SABER_INDCPA_PUBLICKEYBYTES], uint8_t sk[SABE
uint8_t seed_s[SABER_NOISE_SEEDBYTES];
randombytes(seed_A, SABER_SEEDBYTES);
+
+ printf("seedA = ");
+ to_hex(seed_A, SABER_SEEDBYTES);
+
prf(seed_A, SABER_SEEDBYTES, seed_A, SABER_SEEDBYTES); // for not revealing system RNG state
randombytes(seed_s, SABER_NOISE_SEEDBYTES);
+ printf("seedS = ");
+ to_hex(seed_s, SABER_NOISE_SEEDBYTES);
+
GenMatrix(A, seed_A);
GenSecret(s, seed_s);
MatrixVectorMul(A, s, b, 1);
diff --git a/Variants/uSaber-90s/ref/SABER_params.h b/Variants/uSaber-90s/ref/SABER_params.h
index 96a7773..b67b2da 100644
--- a/Variants/uSaber-90s/ref/SABER_params.h
+++ b/Variants/uSaber-90s/ref/SABER_params.h
@@ -3,7 +3,7 @@
/* Change this for different security strengths */
// #define SABER_L 2 /* LightSaber */
-#define SABER_L 3 /* Saber */
+// #define SABER_L 3 /* Saber */
// #define SABER_L 4 /* FireSaber */
/* Uncomment this to enable uSaber */
diff --git a/Variants/uSaber-90s/ref/hex_print.h b/Variants/uSaber-90s/ref/hex_print.h
new file mode 100644
index 0000000..a9928ba
--- /dev/null
+++ b/Variants/uSaber-90s/ref/hex_print.h
@@ -0,0 +1,9 @@
+#include <stdio.h>
+#include <stdint.h>
+
+inline void to_hex(const uint8_t *const bytes, const size_t blen) {
+ for(size_t i = 0; i < blen; i++) {
+ printf("%02x", bytes[i]);
+ }
+ printf("\n");
+}
diff --git a/Variants/uSaber-90s/ref/kem.c b/Variants/uSaber-90s/ref/kem.c
index 3b12ff4..79a8922 100644
--- a/Variants/uSaber-90s/ref/kem.c
+++ b/Variants/uSaber-90s/ref/kem.c
@@ -8,6 +8,7 @@
#include "rng.h"
#include "fips202.h"
#include "symmetric.h"
+#include "hex_print.h"
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
@@ -22,6 +23,13 @@ int crypto_kem_keypair(unsigned char *pk, unsigned char *sk)
hash_h(sk + SABER_SECRETKEYBYTES - 64, pk, SABER_INDCPA_PUBLICKEYBYTES); // Then hash(pk) is appended.
randombytes(sk + SABER_SECRETKEYBYTES - SABER_KEYBYTES, SABER_KEYBYTES); // Remaining part of sk contains a pseudo-random number.
+
+ printf("z = ");
+ to_hex(sk + SABER_SECRETKEYBYTES - SABER_KEYBYTES, SABER_KEYBYTES);
+ printf("pkey = ");
+ to_hex(pk, SABER_PUBLICKEYBYTES);
+ printf("skey = ");
+ to_hex(sk, SABER_SECRETKEYBYTES);
// This is output when check in crypto_kem_dec() fails.
return (0);
}
@@ -34,6 +42,9 @@ int crypto_kem_enc(unsigned char *c, unsigned char *k, const unsigned char *pk)
randombytes(buf, 32);
+ printf("m = ");
+ to_hex(buf, 32);
+
hash_h(buf, buf, 32); // BUF[0:31] <-- random message (will be used as the key for client) Note: hash doesnot release system RNG output
hash_h(buf + 32, pk, SABER_INDCPA_PUBLICKEYBYTES); // BUF[32:63] <-- Hash(public key); Multitarget countermeasure for coins + contributory KEM
@@ -47,6 +58,12 @@ int crypto_kem_enc(unsigned char *c, unsigned char *k, const unsigned char *pk)
hash_h(k, kr, 64); // hash concatenation of pre-k and h(c) to k
+ printf("ctxt = ");
+ to_hex(c, SABER_BYTES_CCA_DEC);
+ printf("ss = ");
+ to_hex(k, 32);
+ printf("\n");
+
return (0);
}
@itzmeanjan
Copy link
Author

itzmeanjan commented Jul 31, 2023 •
edited
Loading

Overview

Following instructions can be executed for generating known answer tests (KATs) for LightSaber, Saber, FireSaber, uLightSaber, uSaber and uFireSaber KEM. These KAT files are supposed to be used in my header-only C++ library implementation of Saber ( more @ https://github.com/itzmeanjan/saber.git ) for ensuring its functional correctness and conformance to the specification.

Note
Corresponding Saber KEM specification that you need to look at side-by-side lives @ https://www.esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround3.pdf. For more information regarding Saber, following their website @ https://www.esat.kuleuven.be/cosic/pqcrypto/saber.

Steps

  • Clone repository holding Saber KEM reference implementation (by Saber authors).
git clone https://github.com/KULeuven-COSIC/SABER.git
  • Pin repository to specific commit.
git checkout f7f39e4db2f3e22a21e1dd635e0601caae2b4510
  • Clone this gist.
git clone https://gist.github.com/e499eba2b8c42f150a795d9e1c3c5dea.git
  • Copy git patch file named saber_kem_kat.patch into directory SABER.
cp e499eba2b8c42f150a795d9e1c3c5dea/saber_kem_kat.patch SABER/
  • Issue following command for applying the git patch.
git apply saber_kem_kat.patch
git status # See files changed
git diff   # See changes
  • Now compile and execute KAT file generation program.
pushd SABER/Reference_Implementation_KEM

# For LightSaber
SABER_L=2 make all
./test/PQCgenKAT_kem | tee lightsaber.kat
make clean

# For Saber
SABER_L=3 make all
./test/PQCgenKAT_kem | tee saber.kat
make clean

# For FireSaber
SABER_L=4 make all
./test/PQCgenKAT_kem | tee firesaber.kat
make clean

popd
pushd SABER/Variants

# For uLightSaber
pushd uSaber-90s/ref
SABER_L=2 make all
popd
./uSaber-90s/ref/test/PQCgenKAT_kem | tee uLightsaber.kat
pushd uSaber-90s/ref
make clean

# For uSaber
SABER_L=3 make all
popd
./uSaber-90s/ref/test/PQCgenKAT_kem | tee uSaber.kat
pushd uSaber-90s/ref
make clean

# For uFireSaber
SABER_L=4 make all
popd
./uSaber-90s/ref/test/PQCgenKAT_kem | tee uFiresaber.kat
pushd uSaber-90s/ref
make clean

popd
popd
  • Three KAT files must have following SHA256 checksum.
$ find . -iname '*saber.kat' | xargs sha256sum
601e4c8b3606a7d5da62e1425f5a8e74424bd34c7d807195fe9146beb7763d9a  ./Variants/uLightsaber.kat
3b37d3df2bcef4457e61a396d1305c5d15735062e971bcc4ad239dfc9a038dd3  ./Variants/uSaber.kat
84a069fc1a5644b26b3fee3b866ebe0bad77585d8500fb9c4a9b670048c68f9b  ./Variants/uFiresaber.kat
87d698b576b4a819fe85921d52897715463b6fd5aa06000c6577f38de5a79b41  ./Reference_Implementation_KEM/firesaber.kat
2b0f013fcd166ef9ca802d2db0c1aa08822f068a3419bbabb74bfe42019aca44  ./Reference_Implementation_KEM/lightsaber.kat
27e83a4e88929b42074f1dc84f8cfb2ab3694c32083f71e35a5ec54a2d134939  ./Reference_Implementation_KEM/saber.kat

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