[Pqc-forum] API for PQC algorithms
Moody, Dustin (Fed)
Let us know of any suggestions. Thanks,
Dustin Moody
NIST
PQC - API notes
Most of the API information is derived from the eBATS: ECRYPT Benchmarking of Asymmetric Systems (https://bench.cr.yp.to/ebats.html). This has been done to facilitate benchmarking algorithm performance. Please look at the eBATS page for more information on how to submit an algorithm for performance benchmarking. There are two sets of API calls listed for each primitive. The first set is the API call directly from the eBATS page, or something very similar for the Key Encapsulation Mechanism section. The second set of calls is for testing purposes. The calls extend the eBATS calls for functions that utilize randomness by providing a pointer to specify a randomness string. This will allow algorithms that utilize randomness to be able to provide reproducible results. For example, this will allow testing of KAT files and other sample values.
Public-key Signatures
See https://bench.cr.yp.to/call-sign.html for more information on Public-key Signature API and performance testing.
The first thing to do is to create a file called api.h. This file contains the following four lines (with the sizes set to the appropriate values):
#define CRYPTO_SECRETKEYBYTES 256
#define CRYPTO_PUBLICKEYBYTES 85
#define CRYPTO_BYTES 128
#define CRYPTO_RANDOMBYTES 64
indicating that your software uses a 256-byte (2048-bit) secret key, an 85-byte (680-bit) public key, at most 128 bytes of overhead in a signed message compared to the original message, and 64 bytes of random input.
Then create a file called sign.c with the following function calls:
eBATS calls
Generates a keypair - pk is the public key and sk is the secret key.
int crypto_sign_keypair(
unsigned char *pk,
unsigned char *sk
)
Sign a message: sm is the signed message, m is the original message, and sk is the secret key.
int crypto_sign(
unsigned char *sm, unsigned long long *smlen,
const unsigned char *m, unsigned long long mlen,
const unsigned char *sk
)
Verify a message signature: m is the original message, sm is the signed message, pk is the public key.
int crypto_sign_open(
const unsigned char *m, unsigned long long *mlen,
const unsigned char *sm, unsigned long long smlen,
const unsigned char *pk
)
KAT calls
int crypto_sign_keypair_KAT(
unsigned char *pk,
unsigned char *sk,
const unsigned char *randomness
)
int crypto_sign_KAT(
unsigned char *sm, unsigned long long *smlen,
const unsigned char *m, unsigned long long mlen,
const unsigned char *sk,
const unsigned char *randomness
)
Public-key Encryption
See https://bench.cr.yp.to/call-encrypt.html for more information on Public-key Encryption API and performance testing.
The first thing to do is to create a file called api.h. This file contains the following four lines (with the sizes set to the appropriate values):
#define CRYPTO_SECRETKEYBYTES 256
#define CRYPTO_PUBLICKEYBYTES 64
#define CRYPTO_BYTES 48
#define CRYPTO_RANDOMBYTES 64
indicating that your software uses a 256-byte (2048-bit) secret key, a 64-byte (512-bit) public key, at most 48 bytes of overhead in an encrypted message compared to the original message, and 64 bytes of random input.
Then create a file called encrypt.c with the following function calls:
eBATS calls
Generates a keypair - pk is the public key and sk is the secret key.
int crypto_encrypt_keypair(
unsigned char *pk,
unsigned char *sk
)
Encrypt a plaintext: c is the ciphertext, m is the plaintext, and pk is the public key.
int crypto_encrypt(
unsigned char *c, unsigned long long *clen,
const unsigned char *m, unsigned long long mlen,
const unsigned char *pk
)
Decrypt a ciphertext: m is the plaintext, c is the ciphertext, and sk is the secret key.
int crypto_encrypt_open(
unsigned char *m, unsigned long long *mlen,
const unsigned char *c, unsigned long long clen,
const unsigned char *sk
)
KAT calls
int crypto_encrypt_keypair_KAT(
unsigned char *pk,
unsigned char *sk,
const unsigned char *randomness
)
int crypto_encrypt_KAT(
unsigned char *c, unsigned long long *clen,
const unsigned char *m, unsigned long long mlen,
const unsigned char *pk,
const unsigned char *randomness
)
Key Encapsulation Mechanism (KEM)
The calls in the eBATS specification do not meet the calls specified in the call for algorithms. However, attempts were made to match the specifications for the other algorithms.
The first thing to do is to create a file called api.h. This file contains the following four lines (with the sizes set to the appropriate values):
#define CRYPTO_SECRETKEYBYTES 192
#define CRYPTO_PUBLICKEYBYTES 64
#define CRYPTO_BYTES 64
#define CRYPTO_CIPHERTEXTBYTES 128
#define CRYPTO_RANDOMBYTES 64
indicating that your software uses a 192-byte (1536-bit) secret key, a 64-byte (512-bit) public key, a 64-byte (512-bit) shared secret, at most a 128-byte (1024-bit) ciphertext, and 64 bytes of random input.
Then create a file called kem.c with the following function calls:
eBATS-like calls
Generates a keypair - pk is the public key and sk is the secret key.
int crypto_kem_keygenerate(
unsigned char *pk,
unsigned char *sk
)
Encapsulate - pk is the public key, ct is a key encapsulation message (ciphertext), ss is the shared secret.
int crypto_kem_encapsulate(
const unsigned char *pk,
unsigned char *ct,
unsigned char *ss
)
Decapsulate - ct is a key encapsulation message (ciphertext), sk is the private key, ss is the shared secret
int crypto_kem_decapsulate(
const unsigned char *ct,
const unsigned char *sk,
unsigned char *ss
)
KAT calls
int crypto_kem_keygenerate(
unsigned char *pk,
unsigned char *sk,
const unsigned char *randomness
)
int crypto_kem_encapsulate(
const unsigned char *pk,
unsigned char *ct,
unsigned char *ss,
const unsigned char *randomness
)
Danilo Gligoroski
Danilo Gligoroski
D. J. Bernstein
* Key generation should be crypto_kem_keypair(pk,sk) by analogy to
the other functions in SUPERCOP generating public and secret keys:
crypto_encrypt_keypair, crypto_sign_keypair, and crypto_dh_keypair.
* Encryption should put ct,ss before pk: outputs are always before
inputs in SUPERCOP (and NaCl). Having ct before ss is good: it fits
the keypair pattern of public output before secret output.
* Decryption should similarly put ss before ct,sk. Again having ct
before sk is good, as in (e.g.) crypto_dh; more broadly, secret
keys as inputs are always at the end.
* It's common in the literature to abbreviate encapsulation (or
encapsulate) as encaps or encap or enc. The shortest version, enc,
has the virtue of reducing distraction for people who are thinking
"encrypt" and who aren't already steeped in the relatively obscure
"encapsulate" terminology. Similarly I'd suggest dec.
Regarding KATs (not just for crypto_kem), I'd suggest scrapping the
extra API calls (and the RANDOMBYTES definition) and instead telling
implementors to use randombytes() to generate randomness. This has at
least four advantages:
* It's already supported and used by SUPERCOP for generating KATs
(and also works in NaCl to read /dev/urandom).
* It avoids a profusion of extra function calls.
* It avoids having to pass an RNG argument around through all the
subroutines that need (or might need) the RNG.
* The implementor doesn't have to bother calculating a maximum number
of random bytes needed (or a maximum reasonable number for the
common case that there's no limit).
I'm not aware of any advantages of having an extra RNG argument. It's
sometimes useful to analyze a randomized algorithm _semantically_ as a
deterministic algorithm applied to a separate string-of-random-bits
input, and there is a fringe argument that any other _syntax_ for
algorithms should be disallowed, but this argument is ignored by
approximately 100% of algorithm designers and programmers.
---Dan
Markku-Juhani Olavi Saarinen
Dan's comments on the API make sense to me. Most style guides suggest
destination variables on the left -- this is also the convention used
in C library functions such as memcpy() and memset().
Perhaps the document should be little bit more clear on the C dialect
required. I can only see a vague reference to "ANSI C". This is often
understood to mean ISO C90, since that was the dialect used in the 2nd
"ANSI" edition of K&R's C book. This is still the interpretation of
gcc's -ansi flag with -Wpedantic. Strictly speaking C90 does not
support "long long" types, so this would be incompatible with the API
itself. It also lacks things like new style (//) comments and 64-bit
types altogether.
Most major C codebases (such as the BSD and Linux kernels) have since
migrated to ISO C99. Since 64-bit implementations are relevant here,
style guides suggest using the types given in stdint.h; especially
uint8_t, uint32_t, and uint64_t. For byte array lengths most prefer to
see size_t from stddef.h. These all are standard C99 features.
The document further suggests that "optimized implementation targeting
64-bit Intel processors" should also be written in "ANSI C".
Experience has shown that many post-quantum algorithms significantly
benefit from vector instructions, like the 256-bit AVX2 instruction
set which is now widely available on the x86_64/amd64 target. With
some Lattice schemes the speedup (of NTT operations) may be up to an
order of magnitude and this has indeed affected the design of these
algorithms. Such vector types are of course unavailable in any
standard C dialect.
I've had good experiences on using C intrinsics for this purpose and I
would definitely like to see them allowed for Intel-targeted optimized
reference code. These extensions to C are defined by Intel and have a
certain technical standard status as they are supported by multiple
compilers. See
https://software.intel.com/sites/landingpage/IntrinsicsGuide/
Code written with these intrinsics is still reasonably readable for
people who understand C (but not necessarily Assembler). But most
importantly the code is in C files and the same vectorized code can
usually be compiled with Microsoft, Apple (LLVM), and GCC. The
resulting code may have significantly differing performance
characteristics with different compilers, but that is an another
matter.
Cheers,
- markku
Dr. Markku-Juhani O. Saarinen <mjos at iki.fi>
> _______________________________________________
> pqc-forum mailing list
> pqc-...@list.nist.gov
> (_internal_name)s
>
Markku-Juhani Olavi Saarinen
Since someone will probably bring this up: Yes, uint64_t is only
available in the standard if the architecture supports it, and no,
Linus has not embraced *all* C99 features, nor has really anyone. But
using things like uint64_t and size_t rather than making your own
typedefs is definitely recommended.
Cheers,
- markku
Dr. Markku-Juhani O. Saarinen <mjos at iki.fi>
D. J. Bernstein
for writing crypto code, whether the goal is clarity or performance. But
the big picture is even worse: _none_ of the C standards are adequate.
For example:
* Vector instructions are so important for performance on big CPUs
(including smartphone CPUs) that it would be crazy to prohibit
those instructions in performance comparisons. But, as Markku
notes, the C standards don't provide vector instructions.
(Occasionally a compiler will figure out on its own how to
vectorize something, but this is extremely fragile.)
* The C standards provide very few guarantees regarding the
availability of integer types of particular widths. C99 does
provide standard names uint8_t, uint32_t, uint64_t, but, as Markku
noted later, strictly conforming C99 code can't assume that those
types exist. There isn't even a guarantee that "unsigned char" is
{0,1,...,255}.
* http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1637.pdf includes
many examples of how poorly thought through the C standards are.
The coup de grace is a proof that it's actually _impossible_ to
write a strictly conforming program.
Requiring programs to be conforming (rather than strictly conforming) is
pointless: it doesn't guarantee the portability that these standards are
supposed to be ensuring. The logical implications between
(1) strictly conforming (defined by the standard)
(2) works with a conforming compiler (defined by that compiler)
(3) conforming (defined by the standard)
are supposed to be 1=>2 and 2=>3, with no guarantee of 3=>2 or 2=>1.
What we actually need is the code to work on particular platforms; 3
isn't enough for this, and 1 is unreachable in theory and in practice.
Concretely, should a submission be kicked out of the competition because
the reference code doesn't work on a 32-bit big-endian MIPS chip? Or
because some language lawyer points out a way that the code _could_ be
miscompiled by some compiler? Or because the optimized code saves time
using some CPU features that that other submitters haven't used?
The C standards also provide many features that are shown by experience
to be unnecessarily error-prone. I'd put size_t in this category: often
people do arithmetic on sizes, and experience shows that very often the
difference between "long long" and size_t is the difference between this
code always working and sometimes failing on 32-bit platforms. This is
why SUPERCOP always uses "long long" for sizes. (An automatically
resized integer would work even more often, but would raise questions of
memory allocation and library support.)
I think NIST should simply specify some common CPU microarchitecture,
say Haswell, and some free compiler, say gcc-4.8.4 -O3 -march=native
-mtune=native -fomit-frame-pointer, with the caveat that performance in
other environments can be quite different. For SUPERCOP we try many
implementations on many machines with many compiler options, see what
works, and take the fastest on each machine.
Incidentally, SUPERCOP also provides #include "crypto_uint32.h" for an
unsigned 32-bit integer type crypto_uint32, and similarly for all of
{uint,int}{8,16,32,64}. Of course submissions to SUPERCOP are allowed
to, and do, assume that unsigned char is an 8-bit type.
---Dan