Falcon source files (reference implementation)


speed.c

    1 /*
    2  * Speed benchmark code for Falcon implementation.
    3  *
    4  * ==========================(LICENSE BEGIN)============================
    5  *
    6  * Copyright (c) 2017-2019  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.com>
   30  */
   31 
   32 #include <stdio.h>
   33 #include <stdlib.h>
   34 #include <string.h>
   35 #include <time.h>
   36 
   37 /*
   38  * This code uses only the external API.
   39  */
   40 
   41 #include "falcon.h"
   42 
   43 static void *
   44 xmalloc(size_t len)
   45 {
   46         void *buf;
   47 
   48         if (len == 0) {
   49                 return NULL;
   50         }
   51         buf = malloc(len);
   52         if (buf == NULL) {
   53                 fprintf(stderr, "memory allocation error\n");
   54                 exit(EXIT_FAILURE);
   55         }
   56         return buf;
   57 }
   58 
   59 static void
   60 xfree(void *buf)
   61 {
   62         if (buf != NULL) {
   63                 free(buf);
   64         }
   65 }
   66 
   67 /*
   68  * Benchmark function takes an opaque context and an iteration count;
   69  * it returns 0 on success, a negative error code on error.
   70  */
   71 typedef int (*bench_fun)(void *ctx, unsigned long num);
   72 
   73 /*
   74  * Returned value is the time per iteration in nanoseconds. If the
   75  * benchmark function reports an error, 0.0 is returned.
   76  */
   77 static double
   78 do_bench(bench_fun bf, void *ctx, double threshold)
   79 {
   80         unsigned long num;
   81         int r;
   82 
   83         /*
   84          * Alsways do a few blank runs to "train" the caches and branch
   85          * prediction.
   86          */
   87         r = bf(ctx, 5);
   88         if (r != 0) {
   89                 fprintf(stderr, "ERR: %d\n", r);
   90                 return 0.0;
   91         }
   92 
   93         num = 1;
   94         for (;;) {
   95                 clock_t begin, end;
   96                 double tt;
   97 
   98                 begin = clock();
   99                 r = bf(ctx, num);
  100                 end = clock();
  101                 if (r != 0) {
  102                         fprintf(stderr, "ERR: %d\n", r);
  103                         return 0.0;
  104                 }
  105                 tt = (double)(end - begin) / (double)CLOCKS_PER_SEC;
  106                 if (tt >= threshold) {
  107                         return tt * 1000000000.0 / (double)num;
  108                 }
  109 
  110                 /*
  111                  * If the function ran for less than 0.1 seconds then
  112                  * we simply double the iteration number; otherwise, we
  113                  * use the run time to try to get a "correct" number of
  114                  * iterations quickly.
  115                  */
  116                 if (tt < 0.1) {
  117                         num <<= 1;
  118                 } else {
  119                         unsigned long num2;
  120 
  121                         num2 = (unsigned long)((double)num
  122                                 * (threshold * 1.1) / tt);
  123                         if (num2 <= num) {
  124                                 num2 = num + 1;
  125                         }
  126                         num = num2;
  127                 }
  128         }
  129 }
  130 
  131 typedef struct {
  132         unsigned logn;
  133         shake256_context rng;
  134         uint8_t *tmp;
  135         size_t tmp_len;
  136         uint8_t *pk;
  137         uint8_t *sk;
  138         uint8_t *esk;
  139         uint8_t *sig;
  140         size_t sig_len;
  141         uint8_t *sigct;
  142         size_t sigct_len;
  143 } bench_context;
  144 
  145 static inline size_t
  146 maxsz(size_t a, size_t b)
  147 {
  148         return a > b ? a : b;
  149 }
  150 
  151 #define CC(x)   do { \
  152                 int ccr = (x); \
  153                 if (ccr != 0) { \
  154                         return ccr; \
  155                 } \
  156         } while (0)
  157 
  158 static int
  159 bench_keygen(void *ctx, unsigned long num)
  160 {
  161         bench_context *bc;
  162 
  163         bc = ctx;
  164         while (num -- > 0) {
  165                 CC(falcon_keygen_make(&bc->rng, bc->logn,
  166                         bc->sk, FALCON_PRIVKEY_SIZE(bc->logn),
  167                         bc->pk, FALCON_PUBKEY_SIZE(bc->logn),
  168                         bc->tmp, bc->tmp_len));
  169         }
  170         return 0;
  171 }
  172 
  173 static int
  174 bench_sign_dyn(void *ctx, unsigned long num)
  175 {
  176         bench_context *bc;
  177 
  178         bc = ctx;
  179         while (num -- > 0) {
  180                 bc->sig_len = FALCON_SIG_VARTIME_MAXSIZE(bc->logn);
  181                 CC(falcon_sign_dyn(&bc->rng,
  182                         bc->sig, &bc->sig_len,
  183                         bc->sk, FALCON_PRIVKEY_SIZE(bc->logn),
  184                         "data", 4, 0, bc->tmp, bc->tmp_len));
  185         }
  186         return 0;
  187 }
  188 
  189 static int
  190 bench_sign_dyn_ct(void *ctx, unsigned long num)
  191 {
  192         bench_context *bc;
  193 
  194         bc = ctx;
  195         while (num -- > 0) {
  196                 bc->sigct_len = FALCON_SIG_CT_SIZE(bc->logn);
  197                 CC(falcon_sign_dyn(&bc->rng,
  198                         bc->sigct, &bc->sigct_len,
  199                         bc->sk, FALCON_PRIVKEY_SIZE(bc->logn),
  200                         "data", 4, 1, bc->tmp, bc->tmp_len));
  201         }
  202         return 0;
  203 }
  204 
  205 static int
  206 bench_expand_privkey(void *ctx, unsigned long num)
  207 {
  208         bench_context *bc;
  209 
  210         bc = ctx;
  211         while (num -- > 0) {
  212                 CC(falcon_expand_privkey(
  213                         bc->esk, FALCON_EXPANDEDKEY_SIZE(bc->logn),
  214                         bc->sk, FALCON_PRIVKEY_SIZE(bc->logn),
  215                         bc->tmp, bc->tmp_len));
  216         }
  217         return 0;
  218 }
  219 
  220 static int
  221 bench_sign_tree(void *ctx, unsigned long num)
  222 {
  223         bench_context *bc;
  224 
  225         bc = ctx;
  226         while (num -- > 0) {
  227                 bc->sig_len = FALCON_SIG_VARTIME_MAXSIZE(bc->logn);
  228                 CC(falcon_sign_tree(&bc->rng,
  229                         bc->sig, &bc->sig_len,
  230                         bc->esk,
  231                         "data", 4, 0, bc->tmp, bc->tmp_len));
  232         }
  233         return 0;
  234 }
  235 
  236 static int
  237 bench_sign_tree_ct(void *ctx, unsigned long num)
  238 {
  239         bench_context *bc;
  240 
  241         bc = ctx;
  242         while (num -- > 0) {
  243                 bc->sigct_len = FALCON_SIG_CT_SIZE(bc->logn);
  244                 CC(falcon_sign_tree(&bc->rng,
  245                         bc->sigct, &bc->sigct_len,
  246                         bc->esk,
  247                         "data", 4, 1, bc->tmp, bc->tmp_len));
  248         }
  249         return 0;
  250 }
  251 
  252 static int
  253 bench_verify(void *ctx, unsigned long num)
  254 {
  255         bench_context *bc;
  256         size_t pk_len;
  257 
  258         bc = ctx;
  259         pk_len = FALCON_PUBKEY_SIZE(bc->logn);
  260         while (num -- > 0) {
  261                 CC(falcon_verify(
  262                         bc->sig, bc->sig_len,
  263                         bc->pk, pk_len,
  264                         "data", 4, bc->tmp, bc->tmp_len));
  265         }
  266         return 0;
  267 }
  268 
  269 static int
  270 bench_verify_ct(void *ctx, unsigned long num)
  271 {
  272         bench_context *bc;
  273         size_t pk_len;
  274 
  275         bc = ctx;
  276         pk_len = FALCON_PUBKEY_SIZE(bc->logn);
  277         while (num -- > 0) {
  278                 CC(falcon_verify(
  279                         bc->sigct, bc->sigct_len,
  280                         bc->pk, pk_len,
  281                         "data", 4, bc->tmp, bc->tmp_len));
  282         }
  283         return 0;
  284 }
  285 
  286 static void
  287 test_speed_falcon(unsigned logn, double threshold)
  288 {
  289         bench_context bc;
  290         size_t len;
  291 
  292         printf("%4u:", 1u << logn);
  293         fflush(stdout);
  294 
  295         bc.logn = logn;
  296         if (shake256_init_prng_from_system(&bc.rng) != 0) {
  297                 fprintf(stderr, "random seeding failed\n");
  298                 exit(EXIT_FAILURE);
  299         }
  300         len = FALCON_TMPSIZE_KEYGEN(logn);
  301         len = maxsz(len, FALCON_TMPSIZE_SIGNDYN(logn));
  302         len = maxsz(len, FALCON_TMPSIZE_SIGNTREE(logn));
  303         len = maxsz(len, FALCON_TMPSIZE_EXPANDPRIV(logn));
  304         len = maxsz(len, FALCON_TMPSIZE_VERIFY(logn));
  305         bc.tmp = xmalloc(len);
  306         bc.tmp_len = len;
  307         bc.pk = xmalloc(FALCON_PUBKEY_SIZE(logn));
  308         bc.sk = xmalloc(FALCON_PRIVKEY_SIZE(logn));
  309         bc.esk = xmalloc(FALCON_EXPANDEDKEY_SIZE(logn));
  310         bc.sig = xmalloc(FALCON_SIG_VARTIME_MAXSIZE(logn));
  311         bc.sig_len = 0;
  312         bc.sigct = xmalloc(FALCON_SIG_CT_SIZE(logn));
  313         bc.sigct_len = 0;
  314 
  315         printf(" %8.2f",
  316                 do_bench(&bench_keygen, &bc, threshold) / 1000000.0);
  317         fflush(stdout);
  318         printf(" %8.2f",
  319                 do_bench(&bench_expand_privkey, &bc, threshold) / 1000.0);
  320         fflush(stdout);
  321         printf(" %8.2f",
  322                 do_bench(&bench_sign_dyn, &bc, threshold) / 1000.0);
  323         fflush(stdout);
  324         printf(" %8.2f",
  325                 do_bench(&bench_sign_dyn_ct, &bc, threshold) / 1000.0);
  326         fflush(stdout);
  327         printf(" %8.2f",
  328                 do_bench(&bench_sign_tree, &bc, threshold) / 1000.0);
  329         fflush(stdout);
  330         printf(" %8.2f",
  331                 do_bench(&bench_sign_tree_ct, &bc, threshold) / 1000.0);
  332         fflush(stdout);
  333         printf(" %8.2f",
  334                 do_bench(&bench_verify, &bc, threshold) / 1000.0);
  335         fflush(stdout);
  336         printf(" %8.2f",
  337                 do_bench(&bench_verify_ct, &bc, threshold) / 1000.0);
  338         fflush(stdout);
  339 
  340         printf("\n");
  341         fflush(stdout);
  342 
  343         xfree(bc.tmp);
  344         xfree(bc.pk);
  345         xfree(bc.sk);
  346         xfree(bc.esk);
  347         xfree(bc.sig);
  348         xfree(bc.sigct);
  349 }
  350 
  351 int
  352 main(int argc, char *argv[])
  353 {
  354         double threshold;
  355 
  356         if (argc < 2) {
  357                 threshold = 2.0;
  358         } else if (argc == 2) {
  359                 threshold = atof(argv[1]);
  360         } else {
  361                 threshold = -1.0;
  362         }
  363         if (threshold <= 0.0 || threshold > 60.0) {
  364                 fprintf(stderr,
  365 "usage: speed [ threshold ]\n"
  366 "'threshold' is the minimum time for a bench run, in seconds (must be\n"
  367 "positive and less than 60).\n");
  368                 exit(EXIT_FAILURE);
  369         }
  370         printf("time threshold = %.4f s\n", threshold);
  371         printf("kg = keygen, ek = expand private key, sd = sign (without expanded key)\n");
  372         printf("st = sign (with expanded key), vv = verify\n");
  373         printf("sdc, stc, vvc: like sd, st and vv, but with constant-time hash-to-point\n");
  374         printf("keygen in milliseconds, other values in microseconds\n");
  375         printf("\n");
  376         printf("degree  kg(ms)   ek(us)   sd(us)  sdc(us)   st(us)  stc(us)   vv(us)  vvc(us)\n");
  377         fflush(stdout);
  378         test_speed_falcon(8, threshold);
  379         test_speed_falcon(9, threshold);
  380         test_speed_falcon(10, threshold);
  381         return 0;
  382 }