Falcon source files (reference implementation)


falcon.h

    1 /*
    2  * Public API for Falcon.
    3  *
    4  * ==========================(LICENSE BEGIN)============================
    5  *
    6  * Copyright (c) 2017  Falcon Project
    7  *
    8  * Permission is hereby granted, free of charge, to any person obtaining
    9  * a copy of this software and associated documentation files (the
   10  * "Software"), to deal in the Software without restriction, including
   11  * without limitation the rights to use, copy, modify, merge, publish,
   12  * distribute, sublicense, and/or sell copies of the Software, and to
   13  * permit persons to whom the Software is furnished to do so, subject to
   14  * the following conditions:
   15  *
   16  * The above copyright notice and this permission notice shall be
   17  * included in all copies or substantial portions of the Software.
   18  *
   19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   20  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
   21  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
   22  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
   23  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
   24  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
   25  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
   26  *
   27  * ===========================(LICENSE END)=============================
   28  *
   29  * @author   Thomas Pornin <thomas.pornin@nccgroup.trust>
   30  */
   31 
   32 #ifndef FALCON_H__
   33 #define FALCON_H__
   34 
   35 #include <stddef.h>
   36 #include <stdint.h>
   37 
   38 #ifdef __cplusplus
   39 extern "C" {
   40 #endif
   41 
   42 /* ==================================================================== */
   43 /*
   44  * Small vector compression.
   45  *
   46  * Signatures and private keys contain small vectors. They are optionally
   47  * compressed. Several compression algorithms are defined.
   48  */
   49 
   50 /* No compression. */
   51 #define FALCON_COMP_NONE      0
   52 
   53 /* Compression with static codes (approximation of Huffman codes). */
   54 #define FALCON_COMP_STATIC    1
   55 
   56 /* ==================================================================== */
   57 /*
   58  * Signature verifier.
   59  *
   60  * An opaque falcon_vrfy context structure must be allocated with
   61  * falcon_vrfy_new(). That context must be ultimately released with
   62  * falcon_vrfy_free().
   63  *
   64  * The public key is set with falcon_vrfy_set_public_key(). The public
   65  * key must be set at some point before calling falcon_vrfy_verify(),
   66  * but part or all of the signed message may be injected before setting
   67  * the public key. Several successive signature verifications can be
   68  * performed with the same context; the public key is preserved, unless
   69  * changed explicitly.
   70  *
   71  * To start a new verification, call falcon_vrfy_start(). Then inject
   72  * the signed message data with zero, one or more calls to
   73  * falcon_vrfy_update(). Finally, falcon_vrfy_verify() checks the
   74  * signature against the injected message and the set public key.
   75  *
   76  * Falcon signatures include an explicit nonce element, which must be
   77  * provided as parameter to falcon_vrfy_start(). The nonce should be
   78  * generated randomly by the signer.
   79  */
   80 
   81 /*
   82  * Signature verifier context.
   83  */
   84 typedef struct falcon_vrfy_ falcon_vrfy;
   85 
   86 /*
   87  * Allocate a new falcon_vrfy structure. It will have to be released later
   88  * on with falcon_vrfy_free().
   89  *
   90  * This function returns NULL on memory allocation failure.
   91  */
   92 falcon_vrfy *falcon_vrfy_new(void);
   93 
   94 /*
   95  * Release a falcon_vrfy structure and all corresponding resources. This
   96  * function may be called at any time, cancelling the currently ongoing
   97  * signature verification. If 'fv' is NULL, then this function does
   98  * nothing.
   99  */
  100 void falcon_vrfy_free(falcon_vrfy *fv);
  101 
  102 /*
  103  * Set the public key against which signatures are to be verified.
  104  * The encoded public key is provided as pointer 'pkey', with encoded
  105  * length 'len' bytes.
  106  *
  107  * Returned value is 1 on success, 0 on error (invalid public key encoding).
  108  */
  109 int falcon_vrfy_set_public_key(falcon_vrfy *fv,
  110         const void *pkey, size_t len);
  111 
  112 /*
  113  * Reset the hashing mechanism for a new message. The 'r' value is the
  114  * random nonce which was used when generating the signature; it has
  115  * length 'rlen' bytes.
  116  */
  117 void falcon_vrfy_start(falcon_vrfy *fv, const void *r, size_t rlen);
  118 
  119 /*
  120  * Inject some message bytes. These bytes are added to the current message
  121  * to verify. The message bytes are pointed to by 'data' and have length
  122  * 'len' (in bytes). If 'len' is 0, then this call does nothing.
  123  */
  124 void falcon_vrfy_update(falcon_vrfy *fv, const void *data, size_t len);
  125 
  126 /*
  127  * Verify the provided signature against the currently injected message and
  128  * public key. The signature is in 'sig', of length 'len' bytes.
  129  *
  130  * Returned value is:
  131  *   1   signature is valid
  132  *   0   signature does not match the message + public key
  133  *  -1   signature decoding error (invalid / wrong modulus or degree)
  134  *  -2   public key was not set
  135  */
  136 int falcon_vrfy_verify(falcon_vrfy *fv, const void *sig, size_t len);
  137 
  138 /* ==================================================================== */
  139 /*
  140  * Signature generator.
  141  *
  142  * An opaque falcon_sign context structure must be allocated with
  143  * falcon_sign_new(). That context must be ultimately released with
  144  * falcon_sign_free().
  145  *
  146  * The private key is set with falcon_sign_set_private_key(). The public
  147  * key must be set at some point before calling falcon_sign_generate(),
  148  * but part or all of the signed message may be injected before setting
  149  * the private key. Several successive signature generations can be
  150  * performed with the same context; the private key is preserved, unless
  151  * changed explicitly.
  152  *
  153  * To start a new signature generation, call falcon_sign_start(). Then
  154  * inject the signed message data with zero, one or more calls to
  155  * falcon_sign_update(). Finally, falcon_sign_verify() checks the
  156  * signature against the injected message and the set public key.
  157  *
  158  * Falcon signatures include an explicit nonce element. Normally, the
  159  * signature generator produces it as a sequence of 40 random bytes;
  160  * this is done in falcon_sign_start(). Alternatively,
  161  * falcon_sign_start_external_nonce() can be called instead of
  162  * falcon_sign_start(), to provide the nonce explicitly. In that case,
  163  * the caller is responsible for nonce generation. Nonces shall be
  164  * generated with a cryptographically strong RNG.
  165  */
  166 
  167 /*
  168  * Signature generation context.
  169  */
  170 typedef struct falcon_sign_ falcon_sign;
  171 
  172 /*
  173  * Allocate a new falcon_sign structure. It will have to be released later
  174  * on with falcon_sign_free().
  175  *
  176  * This function returns NULL on memory allocation failure.
  177  */
  178 falcon_sign *falcon_sign_new(void);
  179 
  180 /*
  181  * Release a falcon_sign structure and all corresponding resources. This
  182  * function may be called at any time, cancelling the currently ongoing
  183  * signature generation. If 'fs' is NULL, then this function does
  184  * nothing.
  185  */
  186 void falcon_sign_free(falcon_sign *fs);
  187 
  188 /*
  189  * Set the random seed for signature generation. If this function is called,
  190  * then the internal RNG used for this specific signature will be seeded
  191  * with the provided value.
  192  *
  193  * If 'replace' is non-zero, then the provided seed _replaces_ any other
  194  * seed currently set in the RNG. This can be used for test purposes, to
  195  * ensure reproducible behaviour. Otherwise, the provided seed is added
  196  * to the internal pool, which will also use the system RNG.
  197  *
  198  * When falcon_sign_start() is called, the following happens:
  199  *
  200  *  - If falcon_sign_set_seed() was called with a non-zero 'replace'
  201  *    parameter, then that value is used as seed, along with all seeds
  202  *    injected with subsequent falcon_sign_set_seed() with a zero
  203  *    'replace'.
  204  *
  205  *  - Otherwise, the system RNG is used to obtain fresh randomness. If
  206  *    the system RNG fails, then a failure is reported and the engine
  207  *    is not started. If the system RNG succeeds, then the fresh randomness
  208  *    is added to all seeds provided with falcon_sign_set_seed() calls.
  209  */
  210 void falcon_sign_set_seed(falcon_sign *fs,
  211         const void *seed, size_t len, int replace);
  212 
  213 /*
  214  * Set the private key for signature generation. The encoded private key
  215  * is provided as pointer 'skey', with encoded length 'len' bytes.
  216  *
  217  * Returned value is 1 on success, 0 on error (invalid private key encoding
  218  * or memory allocation failure).
  219  */
  220 int falcon_sign_set_private_key(falcon_sign *fs,
  221         const void *skey, size_t len);
  222 
  223 /*
  224  * Reset the hashing mechanism for a new message. The "r" value shall
  225  * point to a 40-byte buffer, which is filled with a newly-generated
  226  * random nonce for this signature. That nonce value shall be conveyed
  227  * to verifiers along with the signature (it is required for proper
  228  * verification).
  229  *
  230  * Returned value is 1 on success, 0 on error. An error may be reported
  231  * if no system RNG could be successfully used to produce the nonce.
  232  */
  233 int falcon_sign_start(falcon_sign *fs, void *r /* 40 bytes */);
  234 
  235 /*
  236  * Reset the hashing mechanism for a new message. The provided nonce 'r'
  237  * (of length 'rlen' bytes) is used for computing the signature, and
  238  * shall be used by verifiers to verify the signature. The caller is
  239  * responsible for proper nonce generation: for security, that nonce
  240  * shall be produced with a cryptographically strong RNG and have
  241  * sufficient length to be unpredictable (40 bytes are recommended).
  242  */
  243 void falcon_sign_start_external_nonce(falcon_sign *fs,
  244         const void *r, size_t rlen);
  245 
  246 /*
  247  * Inject some message bytes. These bytes are added to the current message
  248  * to sign. The message bytes are pointed to by 'data' and have length
  249  * 'len' (in bytes). If 'len' is 0, then this call does nothing.
  250  */
  251 void falcon_sign_update(falcon_sign *fs, const void *data, size_t len);
  252 
  253 /*
  254  * Produce the signature. The signature being a short vector, it can
  255  * optionally be compressed; the compression algorithm to use is set
  256  * in the 'comp' parameter, and shall be one of the FALCON_COMP_*
  257  * constants.
  258  *
  259  * Returned value is the signature length, in bytes.
  260  *
  261  * On error, 0 is returned. Error conditions include the following:
  262  *
  263  *  - Private key was not set.
  264  *  - The system RNG could not be located, or failed.
  265  *  - The signature length would exceed the output buffer length (sig_max_len).
  266  *
  267  * If the private key has degree N, then an uncompressed signature
  268  * (FALCON_COMP_NONE) has length exactly 2*N+1 bytes. With Huffman
  269  * compression, the signature is shorter with overwhelming probability,
  270  * but its exact length may vary. Degree N is normally 512 or 1024,
  271  * depending on key parameters.
  272  */
  273 size_t falcon_sign_generate(falcon_sign *fs,
  274         void *sig, size_t sig_max_len, int comp);
  275 
  276 /* ==================================================================== */
  277 /*
  278  * Key generator.
  279  *
  280  * Key pair generation uses an allocated context. That context keeps
  281  * track of the internal PRNG (this allows external seeding for
  282  * reproducible key generation) and contains some tables that can be
  283  * reused for producing several key pairs.
  284  */
  285 
  286 /*
  287  * Key generation context.
  288  */
  289 typedef struct falcon_keygen_ falcon_keygen;
  290 
  291 /*
  292  * Create a new falcon key generation context.
  293  *
  294  * In the binary case (ternary = 0), the 'logn' parameter is the base-2
  295  * logarithm of the degree; it must be between 1 and 10 (normal Falcon
  296  * parameters use logn = 9 or 10; lower values are for reduced test-only
  297  * versions).
  298  *
  299  * In the ternary case (ternary = 1), the 'logn' parameter is the base-2
  300  * logarithm of 2/3rd of the degree (e.g. logn is 9 for degree 768). In
  301  * that case, 'logn' must lie between 2 and 9 (normal value is 9, lower
  302  * values are for reduced test-only versions).
  303  *
  304  * Returned value is the new context, or NULL on error. Errors include
  305  * out-of-range parameters, and memory allocation errors.
  306  */
  307 falcon_keygen *falcon_keygen_new(unsigned logn, int ternary);
  308 
  309 /*
  310  * Release a previously allocated key generation context, and all
  311  * corresponding resources. If 'fk' is NULL then this function does
  312  * nothing.
  313  */
  314 void falcon_keygen_free(falcon_keygen *fk);
  315 
  316 /*
  317  * Get the maximum encoded size (in bytes) of a private key that can be
  318  * generated with the provided context. When using no compression
  319  * (FALCON_COMP_NONE), this is the exact size; with compression,
  320  * private key will be shorter.
  321  */
  322 size_t falcon_keygen_max_privkey_size(falcon_keygen *fk);
  323 
  324 /*
  325  * Get the maximum encoded size (in bytes) of a public key that can be
  326  * generated with the provided context. Since public keys are uncompressed,
  327  * the returned size is always exact.
  328  */
  329 size_t falcon_keygen_max_pubkey_size(falcon_keygen *fk);
  330 
  331 /*
  332  * Set the random seed for key pair generation. If this function is called,
  333  * then the internal RNG used for this specific signature will be seeded
  334  * with the provided value.
  335  *
  336  * If 'replace' is non-zero, then the provided seed _replaces_ any other
  337  * seed currently set in the RNG. This can be used for test purposes, to
  338  * ensure reproducible behaviour. Otherwise, the provided seed is added
  339  * to the internal pool, which will also use the system RNG.
  340  *
  341  * When falcon_keygen_make() is called, the following happens:
  342  *
  343  *  - If falcon_keygen_set_seed() was called with a non-zero 'replace'
  344  *    parameter, then that value is used as seed, along with all seeds
  345  *    injected with subsequent falcon_keygen_set_seed() with a zero
  346  *    'replace'.
  347  *
  348  *  - Otherwise, the system RNG is used to obtain fresh randomness. If
  349  *    the system RNG fails, then a failure is reported and the engine
  350  *    is not started. If the system RNG succeeds, then the fresh randomness
  351  *    is added to all seeds provided with falcon_keygen_set_seed() calls.
  352  */
  353 void falcon_keygen_set_seed(falcon_keygen *fk,
  354         const void *seed, size_t len, int replace);
  355 
  356 /*
  357  * Generate a new key pair.
  358  *
  359  * The private key is written in 'privkey', using the compression algorithm
  360  * specified by 'comp'. The public key is written in 'pubkey'.
  361  *
  362  * The '*privkey_len' and '*pubkey_len' must initially be set to the
  363  * maximum lengths of the corresponding buffers; on output, they are
  364  * modified to characterize the actual private and public key lengths.
  365  *
  366  * Returned value is 1 on success, 0 on error. An error is reported in the
  367  * following cases:
  368  *
  369  *  - The system RNG failed to provide appropriate seeding.
  370  *
  371  *  - Some memory allocation failed.
  372  *
  373  *  - A new key pair could be internally produced, but could not be encoded
  374  *    because one of the output buffers is too small.
  375  */
  376 int falcon_keygen_make(falcon_keygen *fk, int comp,
  377         void *privkey, size_t *privkey_len,
  378         void *pubkey, size_t *pubkey_len);
  379 
  380 /* ==================================================================== */
  381 
  382 #ifdef __cplusplus
  383 }
  384 #endif
  385 
  386 #endif