Falcon source files (reference implementation)


codec.c

    1 /*
    2  * Encoding/decoding of keys and signatures.
    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 "inner.h"
   33 
   34 /* see inner.h */
   35 size_t
   36 Zf(modq_encode)(
   37         void *out, size_t max_out_len,
   38         const uint16_t *x, unsigned logn)
   39 {
   40         size_t n, out_len, u;
   41         uint8_t *buf;
   42         uint32_t acc;
   43         int acc_len;
   44 
   45         n = (size_t)1 << logn;
   46         for (u = 0; u < n; u ++) {
   47                 if (x[u] >= 12289) {
   48                         return 0;
   49                 }
   50         }
   51         out_len = ((n * 14) + 7) >> 3;
   52         if (out == NULL) {
   53                 return out_len;
   54         }
   55         if (out_len > max_out_len) {
   56                 return 0;
   57         }
   58         buf = out;
   59         acc = 0;
   60         acc_len = 0;
   61         for (u = 0; u < n; u ++) {
   62                 acc = (acc << 14) | x[u];
   63                 acc_len += 14;
   64                 while (acc_len >= 8) {
   65                         acc_len -= 8;
   66                         *buf ++ = (uint8_t)(acc >> acc_len);
   67                 }
   68         }
   69         if (acc_len > 0) {
   70                 *buf = (uint8_t)(acc << (8 - acc_len));
   71         }
   72         return out_len;
   73 }
   74 
   75 /* see inner.h */
   76 size_t
   77 Zf(modq_decode)(
   78         uint16_t *x, unsigned logn,
   79         const void *in, size_t max_in_len)
   80 {
   81         size_t n, in_len, u;
   82         const uint8_t *buf;
   83         uint32_t acc;
   84         int acc_len;
   85 
   86         n = (size_t)1 << logn;
   87         in_len = ((n * 14) + 7) >> 3;
   88         if (in_len > max_in_len) {
   89                 return 0;
   90         }
   91         buf = in;
   92         acc = 0;
   93         acc_len = 0;
   94         u = 0;
   95         while (u < n) {
   96                 acc = (acc << 8) | (*buf ++);
   97                 acc_len += 8;
   98                 if (acc_len >= 14) {
   99                         unsigned w;
  100 
  101                         acc_len -= 14;
  102                         w = (acc >> acc_len) & 0x3FFF;
  103                         if (w >= 12289) {
  104                                 return 0;
  105                         }
  106                         x[u ++] = (uint16_t)w;
  107                 }
  108         }
  109         if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) {
  110                 return 0;
  111         }
  112         return in_len;
  113 }
  114 
  115 /* see inner.h */
  116 size_t
  117 Zf(trim_i16_encode)(
  118         void *out, size_t max_out_len,
  119         const int16_t *x, unsigned logn, unsigned bits)
  120 {
  121         size_t n, u, out_len;
  122         int minv, maxv;
  123         uint8_t *buf;
  124         uint32_t acc, mask;
  125         unsigned acc_len;
  126 
  127         n = (size_t)1 << logn;
  128         maxv = (1 << (bits - 1)) - 1;
  129         minv = -maxv;
  130         for (u = 0; u < n; u ++) {
  131                 if (x[u] < minv || x[u] > maxv) {
  132                         return 0;
  133                 }
  134         }
  135         out_len = ((n * bits) + 7) >> 3;
  136         if (out == NULL) {
  137                 return out_len;
  138         }
  139         if (out_len > max_out_len) {
  140                 return 0;
  141         }
  142         buf = out;
  143         acc = 0;
  144         acc_len = 0;
  145         mask = ((uint32_t)1 << bits) - 1;
  146         for (u = 0; u < n; u ++) {
  147                 acc = (acc << bits) | ((uint16_t)x[u] & mask);
  148                 acc_len += bits;
  149                 while (acc_len >= 8) {
  150                         acc_len -= 8;
  151                         *buf ++ = (uint8_t)(acc >> acc_len);
  152                 }
  153         }
  154         if (acc_len > 0) {
  155                 *buf ++ = (uint8_t)(acc << (8 - acc_len));
  156         }
  157         return out_len;
  158 }
  159 
  160 /* see inner.h */
  161 size_t
  162 Zf(trim_i16_decode)(
  163         int16_t *x, unsigned logn, unsigned bits,
  164         const void *in, size_t max_in_len)
  165 {
  166         size_t n, in_len;
  167         const uint8_t *buf;
  168         size_t u;
  169         uint32_t acc, mask1, mask2;
  170         unsigned acc_len;
  171 
  172         n = (size_t)1 << logn;
  173         in_len = ((n * bits) + 7) >> 3;
  174         if (in_len > max_in_len) {
  175                 return 0;
  176         }
  177         buf = in;
  178         u = 0;
  179         acc = 0;
  180         acc_len = 0;
  181         mask1 = ((uint32_t)1 << bits) - 1;
  182         mask2 = (uint32_t)1 << (bits - 1);
  183         while (u < n) {
  184                 acc = (acc << 8) | *buf ++;
  185                 acc_len += 8;
  186                 while (acc_len >= bits && u < n) {
  187                         uint32_t w;
  188 
  189                         acc_len -= bits;
  190                         w = (acc >> acc_len) & mask1;
  191                         w |= -(w & mask2);
  192                         if (w == -mask2) {
  193                                 /*
  194                                  * The -2^(bits-1) value is forbidden.
  195                                  */
  196                                 return 0;
  197                         }
  198                         w |= -(w & mask2);
  199                         x[u ++] = (int16_t)*(int32_t *)&w;
  200                 }
  201         }
  202         if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) {
  203                 /*
  204                  * Extra bits in the last byte must be zero.
  205                  */
  206                 return 0;
  207         }
  208         return in_len;
  209 }
  210 
  211 /* see inner.h */
  212 size_t
  213 Zf(trim_i8_encode)(
  214         void *out, size_t max_out_len,
  215         const int8_t *x, unsigned logn, unsigned bits)
  216 {
  217         size_t n, u, out_len;
  218         int minv, maxv;
  219         uint8_t *buf;
  220         uint32_t acc, mask;
  221         unsigned acc_len;
  222 
  223         n = (size_t)1 << logn;
  224         maxv = (1 << (bits - 1)) - 1;
  225         minv = -maxv;
  226         for (u = 0; u < n; u ++) {
  227                 if (x[u] < minv || x[u] > maxv) {
  228                         return 0;
  229                 }
  230         }
  231         out_len = ((n * bits) + 7) >> 3;
  232         if (out == NULL) {
  233                 return out_len;
  234         }
  235         if (out_len > max_out_len) {
  236                 return 0;
  237         }
  238         buf = out;
  239         acc = 0;
  240         acc_len = 0;
  241         mask = ((uint32_t)1 << bits) - 1;
  242         for (u = 0; u < n; u ++) {
  243                 acc = (acc << bits) | ((uint8_t)x[u] & mask);
  244                 acc_len += bits;
  245                 while (acc_len >= 8) {
  246                         acc_len -= 8;
  247                         *buf ++ = (uint8_t)(acc >> acc_len);
  248                 }
  249         }
  250         if (acc_len > 0) {
  251                 *buf ++ = (uint8_t)(acc << (8 - acc_len));
  252         }
  253         return out_len;
  254 }
  255 
  256 /* see inner.h */
  257 size_t
  258 Zf(trim_i8_decode)(
  259         int8_t *x, unsigned logn, unsigned bits,
  260         const void *in, size_t max_in_len)
  261 {
  262         size_t n, in_len;
  263         const uint8_t *buf;
  264         size_t u;
  265         uint32_t acc, mask1, mask2;
  266         unsigned acc_len;
  267 
  268         n = (size_t)1 << logn;
  269         in_len = ((n * bits) + 7) >> 3;
  270         if (in_len > max_in_len) {
  271                 return 0;
  272         }
  273         buf = in;
  274         u = 0;
  275         acc = 0;
  276         acc_len = 0;
  277         mask1 = ((uint32_t)1 << bits) - 1;
  278         mask2 = (uint32_t)1 << (bits - 1);
  279         while (u < n) {
  280                 acc = (acc << 8) | *buf ++;
  281                 acc_len += 8;
  282                 while (acc_len >= bits && u < n) {
  283                         uint32_t w;
  284 
  285                         acc_len -= bits;
  286                         w = (acc >> acc_len) & mask1;
  287                         w |= -(w & mask2);
  288                         if (w == -mask2) {
  289                                 /*
  290                                  * The -2^(bits-1) value is forbidden.
  291                                  */
  292                                 return 0;
  293                         }
  294                         x[u ++] = (int8_t)*(int32_t *)&w;
  295                 }
  296         }
  297         if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) {
  298                 /*
  299                  * Extra bits in the last byte must be zero.
  300                  */
  301                 return 0;
  302         }
  303         return in_len;
  304 }
  305 
  306 /* see inner.h */
  307 size_t
  308 Zf(comp_encode)(
  309         void *out, size_t max_out_len,
  310         const int16_t *x, unsigned logn)
  311 {
  312         uint8_t *buf;
  313         size_t n, u, v;
  314         uint32_t acc;
  315         unsigned acc_len;
  316 
  317         n = (size_t)1 << logn;
  318         buf = out;
  319 
  320         /*
  321          * Make sure that all values are within the -2047..+2047 range.
  322          */
  323         for (u = 0; u < n; u ++) {
  324                 if (x[u] < -2047 || x[u] > +2047) {
  325                         return 0;
  326                 }
  327         }
  328 
  329         acc = 0;
  330         acc_len = 0;
  331         v = 0;
  332         for (u = 0; u < n; u ++) {
  333                 int t;
  334                 unsigned w;
  335 
  336                 /*
  337                  * Get sign and absolute value of next integer; push the
  338                  * sign bit.
  339                  */
  340                 acc <<= 1;
  341                 t = x[u];
  342                 if (t < 0) {
  343                         t = -t;
  344                         acc |= 1;
  345                 }
  346                 w = (unsigned)t;
  347 
  348                 /*
  349                  * Push the low 7 bits of the absolute value.
  350                  */
  351                 acc <<= 7;
  352                 acc |= w & 127u;
  353                 w >>= 7;
  354 
  355                 /*
  356                  * We pushed exactly 8 bits.
  357                  */
  358                 acc_len += 8;
  359 
  360                 /*
  361                  * Push as many zeros as necessary, then a one. Since the
  362                  * absolute value is at most 2047, w can only range up to
  363                  * 15 at this point, thus we will add at most 16 bits
  364                  * here. With the 8 bits above and possibly up to 7 bits
  365                  * from previous iterations, we may go up to 31 bits, which
  366                  * will fit in the accumulator, which is an uint32_t.
  367                  */
  368                 acc <<= (w + 1);
  369                 acc |= 1;
  370                 acc_len += w + 1;
  371 
  372                 /*
  373                  * Produce all full bytes.
  374                  */
  375                 while (acc_len >= 8) {
  376                         acc_len -= 8;
  377                         if (buf != NULL) {
  378                                 if (v >= max_out_len) {
  379                                         return 0;
  380                                 }
  381                                 buf[v] = (uint8_t)(acc >> acc_len);
  382                         }
  383                         v ++;
  384                 }
  385         }
  386 
  387         /*
  388          * Flush remaining bits (if any).
  389          */
  390         if (acc_len > 0) {
  391                 if (buf != NULL) {
  392                         if (v >= max_out_len) {
  393                                 return 0;
  394                         }
  395                         buf[v] = (uint8_t)(acc << (8 - acc_len));
  396                 }
  397                 v ++;
  398         }
  399 
  400         return v;
  401 }
  402 
  403 /* see inner.h */
  404 size_t
  405 Zf(comp_decode)(
  406         int16_t *x, unsigned logn,
  407         const void *in, size_t max_in_len)
  408 {
  409         const uint8_t *buf;
  410         size_t n, u, v;
  411         uint32_t acc;
  412         unsigned acc_len;
  413 
  414         n = (size_t)1 << logn;
  415         buf = in;
  416         acc = 0;
  417         acc_len = 0;
  418         v = 0;
  419         for (u = 0; u < n; u ++) {
  420                 unsigned b, s, m;
  421 
  422                 /*
  423                  * Get next eight bits: sign and low seven bits of the
  424                  * absolute value.
  425                  */
  426                 if (v >= max_in_len) {
  427                         return 0;
  428                 }
  429                 acc = (acc << 8) | (uint32_t)buf[v ++];
  430                 b = acc >> acc_len;
  431                 s = b & 128;
  432                 m = b & 127;
  433 
  434                 /*
  435                  * Get next bits until a 1 is reached.
  436                  */
  437                 for (;;) {
  438                         if (acc_len == 0) {
  439                                 if (v >= max_in_len) {
  440                                         return 0;
  441                                 }
  442                                 acc = (acc << 8) | (uint32_t)buf[v ++];
  443                                 acc_len = 8;
  444                         }
  445                         acc_len --;
  446                         if (((acc >> acc_len) & 1) != 0) {
  447                                 break;
  448                         }
  449                         m += 128;
  450                         if (m > 2047) {
  451                                 return 0;
  452                         }
  453                 }
  454                 x[u] = (int16_t)(s ? -(int)m : (int)m);
  455         }
  456         return v;
  457 }
  458 
  459 /*
  460  * Key elements and signatures are polynomials with small integer
  461  * coefficients. Here are some statistics gathered over many
  462  * generated key pairs (10000 or more for each degree):
  463  *
  464  *   log(n)     n   max(f,g)   std(f,g)   max(F,G)   std(F,G)
  465  *      1       2     129       56.31       143       60.02
  466  *      2       4     123       40.93       160       46.52
  467  *      3       8      97       28.97       159       38.01
  468  *      4      16     100       21.48       154       32.50
  469  *      5      32      71       15.41       151       29.36
  470  *      6      64      59       11.07       138       27.77
  471  *      7     128      39        7.91       144       27.00
  472  *      8     256      32        5.63       148       26.61
  473  *      9     512      22        4.00       137       26.46
  474  *     10    1024      15        2.84       146       26.41
  475  *
  476  * We want a compact storage format for private key, and, as part of
  477  * key generation, we are allowed to reject some keys which would
  478  * otherwise be fine (this does not induce any noticeable vulnerability
  479  * as long as we reject only a small proportion of possible keys).
  480  * Hence, we enforce at key generation time maximum values for the
  481  * elements of f, g, F and G, so that their encoding can be expressed
  482  * in fixed-width values. Limits have been chosen so that generated
  483  * keys are almost always within bounds, thus not impacting neither
  484  * security or performance.
  485  *
  486  * IMPORTANT: the code assumes that all coefficients of f, g, F and G
  487  * ultimately fit in the -127..+127 range. Thus, none of the elements
  488  * of max_fg_bits[] and max_FG_bits[] shall be greater than 8.
  489  */
  490 
  491 const uint8_t Zf(max_fg_bits)[] = {
  492         0, /* unused */
  493         8,
  494         8,
  495         8,
  496         8,
  497         8,
  498         7,
  499         7,
  500         6,
  501         6,
  502         5
  503 };
  504 
  505 const uint8_t Zf(max_FG_bits)[] = {
  506         0, /* unused */
  507         8,
  508         8,
  509         8,
  510         8,
  511         8,
  512         8,
  513         8,
  514         8,
  515         8,
  516         8
  517 };
  518 
  519 /*
  520  * When generating a new key pair, we can always reject keys which
  521  * feature an abnormally large coefficient. This can also be done for
  522  * signatures, albeit with some care: in case the signature process is
  523  * used in a derandomized setup (explicitly seeded with the message and
  524  * private key), we have to follow the specification faithfully, and the
  525  * specification only enforces a limit on the L2 norm of the signature
  526  * vector. The limit on the L2 norm implies that the absolute value of
  527  * a coefficient of the signature cannot be more than the following:
  528  *
  529  *   log(n)     n   max sig coeff (theoretical)
  530  *      1       2       412
  531  *      2       4       583
  532  *      3       8       824
  533  *      4      16      1166
  534  *      5      32      1649
  535  *      6      64      2332
  536  *      7     128      3299
  537  *      8     256      4665
  538  *      9     512      6598
  539  *     10    1024      9331
  540  *
  541  * However, the largest observed signature coefficients during our
  542  * experiments was 1077 (in absolute value), hence we can assume that,
  543  * with overwhelming probability, signature coefficients will fit
  544  * in -2047..2047, i.e. 12 bits.
  545  */
  546 
  547 const uint8_t Zf(max_sig_bits)[] = {
  548         0, /* unused */
  549         10,
  550         11,
  551         11,
  552         12,
  553         12,
  554         12,
  555         12,
  556         12,
  557         12,
  558         12
  559 };