Falcon source files (reference implementation)


falcon-enc.c

    1 /*
    2  * Encoding/decoding of keys and signatures.
    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 #include "internal.h"
   33 
   34 /*
   35  * Encoding rules
   36  * ==============
   37  *
   38  * In this description we number bits left-to-right, starting at 0. In
   39  * an octet (a "byte"), there are eight bits, the most significant being
   40  * leftmost (i.e. bit 0 here).
   41  *
   42  *
   43  * Ring elements, q = 12289
   44  * ------------------------
   45  *
   46  * A point coordinate is an integer between 0 and 12288 (inclusive), which
   47  * is encoded as a 14-bit sequence, again numbered 0 to 13, 0 being most
   48  * significant.
   49  *
   50  * An arbitrary point (e.g. public key H) is a sequence of values modulo
   51  * q. These are encoded in due order as sequences of 14 bits. These are
   52  * then concatenated, then split over bytes in left-to-right order. For
   53  * instance, if the first two coordinates are 11911 (10111010000111 in
   54  * binary) and 3446 (00110101110110 in binary), then the bit sequence
   55  * will be:
   56  *
   57  *   10111010000111 00110101110110 ...
   58  *
   59  * which gets resplit into eight-bit chunks as:
   60  *
   61  *   10111010 00011100 11010111 0110...
   62  *
   63  * so the three first bytes of the encoding will have values 186, 28
   64  * and 215, in that order.
   65  *
   66  * If the total bit length is not a multiple of 8, then extra padding
   67  * bits are added to complete the final bytes. These padding bits MUST
   68  * have value 0.
   69  *
   70  *
   71  * Ring elements, q = 18433
   72  * ------------------------
   73  *
   74  * For the ternary case, modulus q is 18433. Encoding is similar to
   75  * the case q = 12289, except that each value uses 15 bits instead
   76  * of 14.
   77  *
   78  * Also, array length is 1.5*2^logn in that case.
   79  *
   80  *
   81  * Small vectors
   82  * -------------
   83  *
   84  * "Small vectors" are private keys and signatures. They consist in
   85  * _signed_ integers with values close to 0. They are encoded into bytes
   86  * with a static code that approximates Huffman codes.
   87  */
   88 
   89 /* see falcon-internal.h */
   90 size_t
   91 falcon_encode_12289(void *out, size_t max_out_len,
   92         const uint16_t *x, unsigned logn)
   93 {
   94         unsigned char *buf;
   95         size_t n, u;
   96         uint32_t acc;
   97         int acc_len;
   98 
   99         n = (size_t)1 << logn;
  100         buf = out;
  101         u = 0;
  102         acc = 0;
  103         acc_len = 0;
  104         while (n > 0) {
  105                 acc = (acc << 14) | (*x ++);
  106                 n --;
  107                 acc_len += 14;
  108                 while (acc_len >= 8) {
  109                         acc_len -= 8;
  110                         if (out != NULL) {
  111                                 if (u >= max_out_len) {
  112                                         return 0;
  113                                 }
  114                                 buf[u] = (unsigned char)(acc >> acc_len);
  115                         }
  116                         u ++;
  117                         acc &= (1U << acc_len) - 1U;
  118                 }
  119         }
  120         if (acc_len > 0) {
  121                 if (out != NULL) {
  122                         if (u >= max_out_len) {
  123                                 return 0;
  124                         }
  125                         buf[u] = (unsigned char)(acc << (8 - acc_len));
  126                 }
  127                 u ++;
  128         }
  129         return u;
  130 }
  131 
  132 /* see falcon-internal.h */
  133 size_t
  134 falcon_decode_12289(uint16_t *x, unsigned logn, const void *data, size_t len)
  135 {
  136         const unsigned char *buf;
  137         size_t n, u;
  138         uint32_t acc;
  139         int acc_len;
  140 
  141         n = (size_t)1 << logn;
  142         buf = data;
  143         u = 0;
  144         acc = 0;
  145         acc_len = 0;
  146         while (n > 0) {
  147                 if (u >= len) {
  148                         return 0;
  149                 }
  150                 acc = (acc << 8) | buf[u ++];
  151                 acc_len += 8;
  152                 if (acc_len >= 14) {
  153                         uint32_t w;
  154 
  155                         acc_len -= 14;
  156                         w = acc >> acc_len;
  157                         if (w >= 12289) {
  158                                 return 0;
  159                         }
  160                         *x ++ = (uint16_t)w;
  161                         n --;
  162                         acc &= (1U << acc_len) - 1U;
  163                 }
  164         }
  165         if (acc != 0) {
  166                 return 0;
  167         }
  168         return len;
  169 }
  170 
  171 /* see falcon-internal.h */
  172 size_t
  173 falcon_encode_18433(void *out, size_t max_out_len,
  174         const uint16_t *x, unsigned logn)
  175 {
  176         unsigned char *buf;
  177         size_t n, u;
  178         uint32_t acc;
  179         int acc_len;
  180 
  181         n = (size_t)3 << (logn - 1);
  182         buf = out;
  183         u = 0;
  184         acc = 0;
  185         acc_len = 0;
  186         while (n > 0) {
  187                 acc = (acc << 15) | (*x ++);
  188                 n --;
  189                 acc_len += 15;
  190                 while (acc_len >= 8) {
  191                         acc_len -= 8;
  192                         if (out != NULL) {
  193                                 if (u >= max_out_len) {
  194                                         return 0;
  195                                 }
  196                                 buf[u] = (unsigned char)(acc >> acc_len);
  197                         }
  198                         u ++;
  199                         acc &= (1U << acc_len) - 1U;
  200                 }
  201         }
  202         if (acc_len > 0) {
  203                 if (out != NULL) {
  204                         if (u >= max_out_len) {
  205                                 return 0;
  206                         }
  207                         buf[u] = (unsigned char)(acc << (8 - acc_len));
  208                 }
  209                 u ++;
  210         }
  211         return u;
  212 }
  213 
  214 /* see falcon-internal.h */
  215 size_t
  216 falcon_decode_18433(uint16_t *x, unsigned logn, const void *data, size_t len)
  217 {
  218         const unsigned char *buf;
  219         size_t n, u;
  220         uint32_t acc;
  221         int acc_len;
  222 
  223         n = (size_t)3 << (logn - 1);
  224         buf = data;
  225         u = 0;
  226         acc = 0;
  227         acc_len = 0;
  228         while (n > 0) {
  229                 if (u >= len) {
  230                         return 0;
  231                 }
  232                 acc = (acc << 8) | buf[u ++];
  233                 acc_len += 8;
  234                 if (acc_len >= 15) {
  235                         uint32_t w;
  236 
  237                         acc_len -= 15;
  238                         w = acc >> acc_len;
  239                         if (w >= 18433) {
  240                                 return 0;
  241                         }
  242                         *x ++ = (uint16_t)w;
  243                         n --;
  244                         acc &= (1U << acc_len) - 1U;
  245                 }
  246         }
  247         if (acc != 0) {
  248                 return 0;
  249         }
  250         return len;
  251 }
  252 
  253 /*
  254  * Encoding of a small vector, no compression, 16 bits per value.
  255  */
  256 static size_t
  257 compress_none(void *out, size_t max_out_len,
  258         unsigned q, const int16_t *x, unsigned logn)
  259 {
  260         size_t len, u;
  261         unsigned char *buf;
  262 
  263         if (q == 12289) {
  264                 len = (size_t)2 << logn;
  265         } else {
  266                 len = (size_t)3 << logn;
  267         }
  268         if (out == NULL) {
  269                 return len;
  270         }
  271         if (max_out_len < len) {
  272                 return 0;
  273         }
  274         buf = out;
  275         for (u = 0; u < len; u += 2) {
  276                 unsigned w;
  277 
  278                 w = *x ++;
  279                 buf[u + 0] = (unsigned char)(w >> 8);
  280                 buf[u + 1] = (unsigned char)w;
  281         }
  282         return len;
  283 }
  284 
  285 /*
  286  * Encoding of a small vector, using (sort-of) Huffman codes.
  287  */
  288 static size_t
  289 compress_static(void *out, size_t max_out_len,
  290         unsigned q, const int16_t *x, unsigned logn)
  291 {
  292         unsigned char *buf;
  293         size_t n, u;
  294         unsigned acc, mask;
  295         int acc_len, j;
  296 
  297         /*
  298          * Let x be a value to encode. We first encode its sign as 1 bit
  299          * (1 = negative, 0 = positive), and replace x with |x|.
  300          * The low j bits are encoded as-is in the stream (number j depends
  301          * on the modulus q); then we follow with x/(2^j) bits of value 0,
  302          * and a final bit of value 1.
  303          *
  304          * We use j = 7 for q = 12289, j = 8 for q = 18433.
  305          */
  306 
  307         if (q == 12289) {
  308                 n = (size_t)1 << logn;
  309                 j = 7;
  310         } else {
  311                 n = (size_t)3 << (logn - 1);
  312                 j = 8;
  313         }
  314         mask = (1U << j) - 1U;
  315         buf = out;
  316         u = 0;
  317         acc = 0;
  318         acc_len = 0;
  319         while (n > 0) {
  320                 int w;
  321                 unsigned lo;
  322                 int ne;
  323 
  324                 w = *x ++;
  325                 n --;
  326 
  327                 /*
  328                  * First part: 1 bit for sign, and then the 7 low bits of
  329                  * the absolute value of the integer.
  330                  */
  331                 if (w < 0) {
  332                         w = -w;
  333                         lo = 1U << j;
  334                 } else {
  335                         lo = 0;
  336                 }
  337                 lo |= w & mask;
  338                 ne = w >> j;
  339                 acc = (acc << (j + 1)) | lo;
  340                 acc_len += j + 1;
  341                 while (acc_len >= 8) {
  342                         acc_len -= 8;
  343                         if (buf != NULL) {
  344                                 if (u >= max_out_len) {
  345                                         return 0;
  346                                 }
  347                                 buf[u] = (unsigned char)(acc >> acc_len);
  348                         }
  349                         u ++;
  350                 }
  351 
  352                 /*
  353                  * Second part: 'ne' bits of value 0, and one bit of value 1.
  354                  */
  355                 while (ne -- >= 0) {
  356                         acc <<= 1;
  357                         acc += ((unsigned)ne >> 15) & 1;
  358                         if (++ acc_len == 8) {
  359                                 if (buf != NULL) {
  360                                         if (u >= max_out_len) {
  361                                                 return 0;
  362                                         }
  363                                         buf[u] = (unsigned char)acc;
  364                                 }
  365                                 u ++;
  366                                 acc_len = 0;
  367                         }
  368                 }
  369         }
  370         if (acc_len > 0) {
  371                 if (buf != NULL) {
  372                         if (u >= max_out_len) {
  373                                 return 0;
  374                         }
  375                         buf[u] = (unsigned char)(acc << (8 - acc_len));
  376                 }
  377                 u ++;
  378         }
  379         return u;
  380 }
  381 
  382 /* see falcon-internal.h */
  383 size_t
  384 falcon_encode_small(void *out, size_t max_out_len,
  385         int comp, unsigned q, const int16_t *x, unsigned logn)
  386 {
  387         switch (comp) {
  388         case FALCON_COMP_NONE:
  389                 return compress_none(out, max_out_len, q, x, logn);
  390         case FALCON_COMP_STATIC:
  391                 return compress_static(out, max_out_len, q, x, logn);
  392         default:
  393                 return 0;
  394         }
  395 }
  396 
  397 /*
  398  * Decoding of a small vector, no compression.
  399  */
  400 static size_t
  401 uncompress_none(int16_t *x, unsigned logn,
  402         unsigned q, const void *data, size_t len)
  403 {
  404         size_t n, u;
  405         const unsigned char *buf;
  406         uint32_t hq, tq;
  407 
  408         if (q == 12289) {
  409                 n = (size_t)1 << logn;
  410         } else {
  411                 n = (size_t)3 << (logn - 1);
  412         }
  413         if (len < (n << 1)) {
  414                 return 0;
  415         }
  416 
  417         /*
  418          * hq = floor(q/2)
  419          * tq = ceil(3q/2)
  420          * (Remember that q is odd).
  421          */
  422         hq = q >> 1;
  423         tq = hq + q + 1;
  424 
  425         buf = data;
  426         for (u = 0; u < n; u ++) {
  427                 uint32_t w;
  428                 long y;
  429 
  430                 /*
  431                  * Decode the value as a 32-bit signed value (held in an
  432                  * unsigned integer).
  433                  */
  434                 w = ((uint32_t)buf[(u << 1) + 0] << 8)
  435                         | (uint32_t)buf[(u << 1) + 1];
  436                 w |= -(w & 0x8000);
  437 
  438                 /*
  439                  * Add q. The result must be greater than q/2, and lower
  440                  * than 3q/2.
  441                  */
  442                 w += q;
  443                 if (!(((hq - w) & (w - tq)) >> 31)) {
  444                         return 0;
  445                 }
  446 
  447                 /*
  448                  * Assemble the signed value in a 'long'. Thanks to the
  449                  * verifications above, we know that the result will fit
  450                  * in an int16_t, so the cast is valid.
  451                  */
  452                 y = (long)w - (long)q;
  453                 x[u] = (int16_t)y;
  454         }
  455         return n << 1;
  456 }
  457 
  458 /*
  459  * Decoding of a small vector, compressed with fixed (sort-of) Huffman codes.
  460  */
  461 static size_t
  462 uncompress_static(int16_t *x, unsigned logn,
  463         unsigned q, const void *data, size_t len)
  464 {
  465         const unsigned char *buf;
  466         size_t n, u, v;
  467         unsigned db, mask;
  468         unsigned db_len, j;
  469 
  470         if (q == 12289) {
  471                 n = (size_t)1 << logn;
  472                 j = 7;
  473         } else {
  474                 n = (size_t)3 << (logn - 1);
  475                 j = 8;
  476         }
  477         mask = (1U << j) - 1U;
  478         buf = data;
  479         u = 0;
  480         v = 0;
  481         db = 0;
  482         db_len = 0;
  483         for (;;) {
  484                 unsigned sign;
  485                 unsigned lo;
  486                 unsigned ne;
  487 
  488                 /*
  489                  * Read next byte(s) for the sign bit and the low j bits
  490                  * of the absolute value of the next integer.
  491                  */
  492                 while (db_len <= j) {
  493                         if (v >= len) {
  494                                 return 0;
  495                         }
  496                         db = (db << 8) + buf[v ++];
  497                         db_len += 8;
  498                 }
  499                 sign = (db >> (db_len - 1)) & 1;
  500                 db_len -= j + 1;
  501                 lo = (db >> db_len) & mask;
  502 
  503                 /*
  504                  * Read subsequent bits until next '1' (inclusive).
  505                  */
  506                 for (ne = 0;; ne ++) {
  507                         unsigned bit;
  508 
  509                         if (db_len == 0) {
  510                                 if (v >= len) {
  511                                         return 0;
  512                                 }
  513                                 db = buf[v ++];
  514                                 db_len = 8;
  515                         }
  516                         db_len --;
  517                         bit = (db >> db_len) & 1;
  518                         if (bit) {
  519                                 break;
  520                         }
  521                 }
  522 
  523                 /*
  524                  * Write value.
  525                  */
  526                 if (ne > 255) {
  527                         return 0;
  528                 }
  529                 lo += (ne << j);
  530                 if (sign) {
  531                         x[u] = -(int16_t)lo;
  532                 } else {
  533                         x[u] = (int16_t)lo;
  534                 }
  535                 if (++ u >= n) {
  536                         /*
  537                          * Check that the remaining bits are all zero.
  538                          */
  539                         if ((db & ((1U << db_len) - 1U)) != 0) {
  540                                 return 0;
  541                         }
  542                         return v;
  543                 }
  544         }
  545 }
  546 
  547 /* see falcon-internal.h */
  548 size_t
  549 falcon_decode_small(int16_t *x, unsigned logn,
  550         int comp, unsigned q, const void *data, size_t len)
  551 {
  552         switch (comp) {
  553         case FALCON_COMP_NONE:
  554                 return uncompress_none(x, logn, q, data, len);
  555         case FALCON_COMP_STATIC:
  556                 return uncompress_static(x, logn, q, data, len);
  557         default:
  558                 return 0;
  559         }
  560 }
  561 
  562 /* see falcon-internal.h */
  563 void
  564 falcon_hash_to_point(shake_context *sc, unsigned q, uint16_t *x, unsigned logn)
  565 {
  566         /*
  567          * TODO: make a constant-time version of this process, in case
  568          * the signed data is confidential. We could generate twice as
  569          * many values as necessary, then move proper values into place
  570          * with logn passes that perform conditional swaps.
  571          */
  572 
  573         size_t n;
  574         uint32_t lim;
  575 
  576         if (q == 12289) {
  577                 n = (size_t)1 << logn;
  578         } else {
  579                 n = (size_t)3 << (logn - 1);
  580         }
  581         lim = (uint32_t)65536 - ((uint32_t)65536 % q);
  582         while (n > 0) {
  583                 unsigned char buf[2];
  584                 uint32_t w;
  585 
  586                 shake_extract(sc, buf, sizeof buf);
  587                 w = (buf[0] << 8) | buf[1];
  588                 if (w < lim) {
  589                         *x ++ = (uint16_t)(w % q);
  590                         n --;
  591                 }
  592         }
  593 }
  594 
  595 /* see falcon-internal.h */
  596 int
  597 falcon_is_short(const int16_t *s1, const int16_t *s2,
  598         unsigned logn, unsigned ter)
  599 {
  600         if (ter) {
  601                 /*
  602                  * In the ternary case, we must compute the norm in
  603                  * the FFT embedding. Fortunately, this can be done
  604                  * without computing the FFT.
  605                  */
  606                 size_t n, hn, u;
  607                 int64_t s;
  608 
  609                 n = (size_t)3 << (logn - 1);
  610                 hn = n >> 1;
  611                 s = 0;
  612                 for (u = 0; u < n; u ++) {
  613                         int32_t z;
  614 
  615                         z = s1[u];
  616                         s += z * z;
  617                         z = s2[u];
  618                         s += z * z;
  619                 }
  620                 for (u = 0; u < hn; u ++) {
  621                         s += (int32_t)s1[u] * (int32_t)s1[u + hn];
  622                         s += (int32_t)s2[u] * (int32_t)s2[u + hn];
  623                 }
  624 
  625                 /*
  626                  * If the norm is v, then we computed (v^2)/N (in s).
  627                  */
  628 
  629                 /*
  630                  * Acceptance bound on the embedding norm is:
  631                  *   b = 1.2*1.32*2*N*sqrt(q/sqrt(2))
  632                  *
  633                  * Since we computed (v^2)/N, we must compare it with:
  634                  *   (b^2)/N = ((1.2*1.32*2)^2/sqrt(2))*q*N
  635                  *           = (3*(1.2*1.32*2)^2/sqrt(2))*q*2^(logn-1)
  636                  *
  637                  * We use 100464491 = floor((b^2)/N) when N = 768, and
  638                  * scale it down for lower dimensions.
  639                  */
  640                 return s < (int64_t)((uint32_t)100464491 >> (9 - logn));
  641         } else {
  642                 /*
  643                  * In the binary case, we use the l2-norm. Code below
  644                  * uses only 32-bit operations to compute the square
  645                  * of the norm with saturation to 2^32-1 if the value
  646                  * exceeds 2^31-1.
  647                  */
  648                 size_t n, u;
  649                 uint32_t s, ng;
  650 
  651                 n = (size_t)1 << logn;
  652                 s = 0;
  653                 ng = 0;
  654                 for (u = 0; u < n; u ++) {
  655                         int32_t z;
  656 
  657                         z = s1[u];
  658                         s += (uint32_t)(z * z);
  659                         ng |= s;
  660                         z = s2[u];
  661                         s += (uint32_t)(z * z);
  662                         ng |= s;
  663                 }
  664                 s |= -(ng >> 31);
  665 
  666                 /*
  667                  * Acceptance bound on the l2-norm is:
  668                  *   1.2*1.55*sqrt(q)*sqrt(2*N)
  669                  * Value 7085 is floor((1.2^2)*(1.55^2)*2*1024).
  670                  */
  671                 return s < (((uint32_t)7085 * (uint32_t)12289) >> (10 - logn));
  672         }
  673 }