sshccp.c

   1 /*
   2  * ChaCha20-Poly1305 Implementation for SSH-2
   3  *
   4  * Protocol spec:
   5  *  http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/usr.bin/ssh/PROTOCOL.chacha20poly1305?rev=1.2&content-type=text/x-cvsweb-markup
   6  *
   7  * ChaCha20 spec:
   8  *  http://cr.yp.to/chacha/chacha-20080128.pdf
   9  *
  10  * Salsa20 spec:
  11  *  http://cr.yp.to/snuffle/spec.pdf
  12  *
  13  * Poly1305-AES spec:
  14  *  http://cr.yp.to/mac/poly1305-20050329.pdf
  15  *
  16  * The nonce for the Poly1305 is the second part of the key output
  17  * from the first round of ChaCha20. This removes the AES requirement.
  18  * This is undocumented!
  19  *
  20  * This has an intricate link between the cipher and the MAC. The
  21  * keying of both is done in by the cipher and setting of the IV is
  22  * done by the MAC. One cannot operate without the other. The
  23  * configuration of the ssh2_cipher structure ensures that the MAC is
  24  * set (and others ignored) if this cipher is chosen.
  25  *
  26  * This cipher also encrypts the length using a different
  27  * instantiation of the cipher using a different key and IV made from
  28  * the sequence number which is passed in addition when calling
  29  * encrypt/decrypt on it.
  30  */
  31
  32 #include "ssh.h"
  33 #include "sshbn.h"
  34
  35 #ifndef INLINE
  36 #define INLINE
  37 #endif
  38
  39 /* ChaCha20 implementation, only supporting 256-bit keys */
  40
  41 /* State for each ChaCha20 instance */
  42 struct chacha20 {
  43     /* Current context, usually with the count incremented
  44      * 0-3 are the static constant
  45      * 4-11 are the key
  46      * 12-13 are the counter
  47      * 14-15 are the IV */
  48     uint32 state[16];
  49     /* The output of the state above ready to xor */
  50     unsigned char current[64];
  51     /* The index of the above currently used to allow a true streaming cipher */
  52     int currentIndex;
  53 };
  54
  55 static INLINE void chacha20_round(struct chacha20 *ctx)
  56 {
  57     int i;
  58     uint32 copy[16];
  59
  60     /* Take a copy */
  61     memcpy(copy, ctx->state, sizeof(copy));
  62
  63     /* A circular rotation for a 32bit number */
  64 #define rotl(x, shift) x = ((x << shift) | (x >> (32 - shift)))
  65
  66     /* What to do for each quarter round operation */
  67 #define qrop(a, b, c, d)                        \
  68     copy[a] += copy[b];                         \
  69     copy[c] ^= copy[a];                         \
  70     rotl(copy[c], d)
  71
  72     /* A quarter round */
  73 #define quarter(a, b, c, d)                     \
  74     qrop(a, b, d, 16);                          \
  75     qrop(c, d, b, 12);                          \
  76     qrop(a, b, d, 8);                           \
  77     qrop(c, d, b, 7)
  78
  79     /* Do 20 rounds, in pairs because every other is different */
  80     for (i = 0; i < 20; i += 2) {
  81         /* A round */
  82         quarter(0, 4, 8, 12);
  83         quarter(1, 5, 9, 13);
  84         quarter(2, 6, 10, 14);
  85         quarter(3, 7, 11, 15);
  86         /* Another slightly different round */
  87         quarter(0, 5, 10, 15);
  88         quarter(1, 6, 11, 12);
  89         quarter(2, 7, 8, 13);
  90         quarter(3, 4, 9, 14);
  91     }
  92
  93     /* Dump the macros, don't need them littering */
  94 #undef rotl
  95 #undef qrop
  96 #undef quarter
  97
  98     /* Add the initial state */
  99     for (i = 0; i < 16; ++i) {
 100         copy[i] += ctx->state[i];
 101     }
 102
 103     /* Update the content of the xor buffer */
 104     for (i = 0; i < 16; ++i) {
 105         ctx->current[i * 4 + 0] = copy[i] >> 0;
 106         ctx->current[i * 4 + 1] = copy[i] >> 8;
 107         ctx->current[i * 4 + 2] = copy[i] >> 16;
 108         ctx->current[i * 4 + 3] = copy[i] >> 24;
 109     }
 110     /* State full, reset pointer to beginning */
 111     ctx->currentIndex = 0;
 112     smemclr(copy, sizeof(copy));
 113
 114     /* Increment round counter */
 115     ++ctx->state[12];
 116     /* Check for overflow, not done in one line so the 32 bits are chopped by the type */
 117     if (!(uint32)(ctx->state[12])) {
 118         ++ctx->state[13];
 119     }
 120 }
 121
 122 /* Initialise context with 256bit key */
 123 static void chacha20_key(struct chacha20 *ctx, const unsigned char *key)
 124 {
 125     static const char constant[16] = "expand 32-byte k";
 126
 127     /* Add the fixed string to the start of the state */
 128     ctx->state[0] = GET_32BIT_LSB_FIRST(constant + 0);
 129     ctx->state[1] = GET_32BIT_LSB_FIRST(constant + 4);
 130     ctx->state[2] = GET_32BIT_LSB_FIRST(constant + 8);
 131     ctx->state[3] = GET_32BIT_LSB_FIRST(constant + 12);
 132
 133     /* Add the key */
 134     ctx->state[4]  = GET_32BIT_LSB_FIRST(key + 0);
 135     ctx->state[5]  = GET_32BIT_LSB_FIRST(key + 4);
 136     ctx->state[6]  = GET_32BIT_LSB_FIRST(key + 8);
 137     ctx->state[7]  = GET_32BIT_LSB_FIRST(key + 12);
 138     ctx->state[8]  = GET_32BIT_LSB_FIRST(key + 16);
 139     ctx->state[9]  = GET_32BIT_LSB_FIRST(key + 20);
 140     ctx->state[10] = GET_32BIT_LSB_FIRST(key + 24);
 141     ctx->state[11] = GET_32BIT_LSB_FIRST(key + 28);
 142
 143     /* New key, dump context */
 144     ctx->currentIndex = 64;
 145 }
 146
 147 static void chacha20_iv(struct chacha20 *ctx, const unsigned char *iv)
 148 {
 149     ctx->state[12] = 0;
 150     ctx->state[13] = 0;
 151     ctx->state[14] = GET_32BIT_MSB_FIRST(iv);
 152     ctx->state[15] = GET_32BIT_MSB_FIRST(iv + 4);
 153
 154     /* New IV, dump context */
 155     ctx->currentIndex = 64;
 156 }
 157
 158 static void chacha20_encrypt(struct chacha20 *ctx, unsigned char *blk, int len)
 159 {
 160     while (len) {
 161         /* If we don't have any state left, then cycle to the next */
 162         if (ctx->currentIndex >= 64) {
 163             chacha20_round(ctx);
 164         }
 165
 166         /* Do the xor while there's some state left and some plaintext left */
 167         while (ctx->currentIndex < 64 && len) {
 168             *blk++ ^= ctx->current[ctx->currentIndex++];
 169             --len;
 170         }
 171     }
 172 }
 173
 174 /* Decrypt is encrypt... It's xor against a PRNG... */
 175 static INLINE void chacha20_decrypt(struct chacha20 *ctx,
 176                                     unsigned char *blk, int len)
 177 {
 178     chacha20_encrypt(ctx, blk, len);
 179 }
 180
 181 /* Poly1305 implementation (no AES, nonce is not encrypted) */
 182
 183 #define NWORDS ((130 + BIGNUM_INT_BITS-1) / BIGNUM_INT_BITS)
 184 typedef struct bigval {
 185     BignumInt w[NWORDS];
 186 } bigval;
 187
 188 static void bigval_clear(bigval *r)
 189 {
 190     int i;
 191     for (i = 0; i < NWORDS; i++)
 192         r->w[i] = 0;
 193 }
 194
 195 static void bigval_import_le(bigval *r, const void *vdata, int len)
 196 {
 197     const unsigned char *data = (const unsigned char *)vdata;
 198     int i;
 199     bigval_clear(r);
 200     for (i = 0; i < len; i++)
 201         r->w[i / BIGNUM_INT_BYTES] |=
 202             (BignumInt)data[i] << (8 * (i % BIGNUM_INT_BYTES));
 203 }
 204
 205 static void bigval_export_le(const bigval *r, void *vdata, int len)
 206 {
 207     unsigned char *data = (unsigned char *)vdata;
 208     int i;
 209     for (i = 0; i < len; i++)
 210         data[i] = r->w[i / BIGNUM_INT_BYTES] >> (8 * (i % BIGNUM_INT_BYTES));
 211 }
 212
 213 /*
 214  * Core functions to do arithmetic mod p = 2^130-5. The whole
 215  * collection of these, up to and including the surrounding #if, are
 216  * generated automatically for various sizes of BignumInt by
 217  * contrib/make1305.py.
 218  */
 219
 220 #if BIGNUM_INT_BITS == 16
 221
 222 static void bigval_add(bigval *r, const bigval *a, const bigval *b)
 223 {
 224     BignumInt v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14;
 225     BignumInt v15, v16, v17, v18, v19, v20, v21, v22, v23, v24, v25, v26;
 226     BignumCarry carry;
 227
 228     v0 = a->w[0];
 229     v1 = a->w[1];
 230     v2 = a->w[2];
 231     v3 = a->w[3];
 232     v4 = a->w[4];
 233     v5 = a->w[5];
 234     v6 = a->w[6];
 235     v7 = a->w[7];
 236     v8 = a->w[8];
 237     v9 = b->w[0];
 238     v10 = b->w[1];
 239     v11 = b->w[2];
 240     v12 = b->w[3];
 241     v13 = b->w[4];
 242     v14 = b->w[5];
 243     v15 = b->w[6];
 244     v16 = b->w[7];
 245     v17 = b->w[8];
 246     BignumADC(v18, carry, v0, v9, 0);
 247     BignumADC(v19, carry, v1, v10, carry);
 248     BignumADC(v20, carry, v2, v11, carry);
 249     BignumADC(v21, carry, v3, v12, carry);
 250     BignumADC(v22, carry, v4, v13, carry);
 251     BignumADC(v23, carry, v5, v14, carry);
 252     BignumADC(v24, carry, v6, v15, carry);
 253     BignumADC(v25, carry, v7, v16, carry);
 254     v26 = v8 + v17 + carry;
 255     r->w[0] = v18;
 256     r->w[1] = v19;
 257     r->w[2] = v20;
 258     r->w[3] = v21;
 259     r->w[4] = v22;
 260     r->w[5] = v23;
 261     r->w[6] = v24;
 262     r->w[7] = v25;
 263     r->w[8] = v26;
 264 }
 265
 266 static void bigval_mul_mod_p(bigval *r, const bigval *a, const bigval *b)
 267 {
 268     BignumInt v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14;
 269     BignumInt v15, v16, v17, v18, v19, v20, v21, v22, v23, v24, v25, v26, v27;
 270     BignumInt v28, v29, v30, v31, v32, v33, v34, v35, v36, v37, v38, v39, v40;
 271     BignumInt v41, v42, v43, v44, v45, v46, v47, v48, v49, v50, v51, v52, v53;
 272     BignumInt v54, v55, v56, v57, v58, v59, v60, v61, v62, v63, v64, v65, v66;
 273     BignumInt v67, v68, v69, v70, v71, v72, v73, v74, v75, v76, v77, v78, v79;
 274     BignumInt v80, v81, v82, v83, v84, v85, v86, v87, v88, v89, v90, v91, v92;
 275     BignumInt v93, v94, v95, v96, v97, v98, v99, v100, v101, v102, v103, v104;
 276     BignumInt v105, v106, v107, v108, v109, v110, v111, v112, v113, v114;
 277     BignumInt v115, v116, v117, v118, v119, v120, v121, v122, v123, v124;
 278     BignumInt v125, v126, v127, v128, v129, v130, v131, v132, v133, v134;
 279     BignumInt v135, v136, v137, v138, v139, v140, v141, v142, v143, v144;
 280     BignumInt v145, v146, v147, v148, v149, v150, v151, v152, v153, v154;
 281     BignumInt v155, v156, v157, v158, v159, v160, v161, v162, v163, v164;
 282     BignumInt v165, v166, v167, v168, v169, v170, v171, v172, v173, v174;
 283     BignumInt v175, v176, v177, v178, v180, v181, v182, v183, v184, v185;
 284     BignumInt v186, v187, v188, v189, v190, v191, v192, v193, v194, v195;
 285     BignumInt v196, v197, v198, v199, v200, v201, v202, v203, v204, v205;
 286     BignumInt v206, v207, v208, v210, v212, v213, v214, v215, v216, v217;
 287     BignumInt v218, v219, v220, v221, v222, v223, v224, v225, v226, v227;
 288     BignumInt v228, v229;
 289     BignumCarry carry;
 290
 291     v0 = a->w[0];
 292     v1 = a->w[1];
 293     v2 = a->w[2];
 294     v3 = a->w[3];
 295     v4 = a->w[4];
 296     v5 = a->w[5];
 297     v6 = a->w[6];
 298     v7 = a->w[7];
 299     v8 = a->w[8];
 300     v9 = b->w[0];
 301     v10 = b->w[1];
 302     v11 = b->w[2];
 303     v12 = b->w[3];
 304     v13 = b->w[4];
 305     v14 = b->w[5];
 306     v15 = b->w[6];
 307     v16 = b->w[7];
 308     v17 = b->w[8];
 309     BignumMUL(v19, v18, v0, v9);
 310     BignumMULADD(v21, v20, v0, v10, v19);
 311     BignumMULADD(v23, v22, v0, v11, v21);
 312     BignumMULADD(v25, v24, v0, v12, v23);
 313     BignumMULADD(v27, v26, v0, v13, v25);
 314     BignumMULADD(v29, v28, v0, v14, v27);
 315     BignumMULADD(v31, v30, v0, v15, v29);
 316     BignumMULADD(v33, v32, v0, v16, v31);
 317     BignumMULADD(v35, v34, v0, v17, v33);
 318     BignumMULADD(v37, v36, v1, v9, v20);
 319     BignumMULADD2(v39, v38, v1, v10, v22, v37);
 320     BignumMULADD2(v41, v40, v1, v11, v24, v39);
 321     BignumMULADD2(v43, v42, v1, v12, v26, v41);
 322     BignumMULADD2(v45, v44, v1, v13, v28, v43);
 323     BignumMULADD2(v47, v46, v1, v14, v30, v45);
 324     BignumMULADD2(v49, v48, v1, v15, v32, v47);
 325     BignumMULADD2(v51, v50, v1, v16, v34, v49);
 326     BignumMULADD2(v53, v52, v1, v17, v35, v51);
 327     BignumMULADD(v55, v54, v2, v9, v38);
 328     BignumMULADD2(v57, v56, v2, v10, v40, v55);
 329     BignumMULADD2(v59, v58, v2, v11, v42, v57);
 330     BignumMULADD2(v61, v60, v2, v12, v44, v59);
 331     BignumMULADD2(v63, v62, v2, v13, v46, v61);
 332     BignumMULADD2(v65, v64, v2, v14, v48, v63);
 333     BignumMULADD2(v67, v66, v2, v15, v50, v65);
 334     BignumMULADD2(v69, v68, v2, v16, v52, v67);
 335     BignumMULADD2(v71, v70, v2, v17, v53, v69);
 336     BignumMULADD(v73, v72, v3, v9, v56);
 337     BignumMULADD2(v75, v74, v3, v10, v58, v73);
 338     BignumMULADD2(v77, v76, v3, v11, v60, v75);
 339     BignumMULADD2(v79, v78, v3, v12, v62, v77);
 340     BignumMULADD2(v81, v80, v3, v13, v64, v79);
 341     BignumMULADD2(v83, v82, v3, v14, v66, v81);
 342     BignumMULADD2(v85, v84, v3, v15, v68, v83);
 343     BignumMULADD2(v87, v86, v3, v16, v70, v85);
 344     BignumMULADD2(v89, v88, v3, v17, v71, v87);
 345     BignumMULADD(v91, v90, v4, v9, v74);
 346     BignumMULADD2(v93, v92, v4, v10, v76, v91);
 347     BignumMULADD2(v95, v94, v4, v11, v78, v93);
 348     BignumMULADD2(v97, v96, v4, v12, v80, v95);
 349     BignumMULADD2(v99, v98, v4, v13, v82, v97);
 350     BignumMULADD2(v101, v100, v4, v14, v84, v99);
 351     BignumMULADD2(v103, v102, v4, v15, v86, v101);
 352     BignumMULADD2(v105, v104, v4, v16, v88, v103);
 353     BignumMULADD2(v107, v106, v4, v17, v89, v105);
 354     BignumMULADD(v109, v108, v5, v9, v92);
 355     BignumMULADD2(v111, v110, v5, v10, v94, v109);
 356     BignumMULADD2(v113, v112, v5, v11, v96, v111);
 357     BignumMULADD2(v115, v114, v5, v12, v98, v113);
 358     BignumMULADD2(v117, v116, v5, v13, v100, v115);
 359     BignumMULADD2(v119, v118, v5, v14, v102, v117);
 360     BignumMULADD2(v121, v120, v5, v15, v104, v119);
 361     BignumMULADD2(v123, v122, v5, v16, v106, v121);
 362     BignumMULADD2(v125, v124, v5, v17, v107, v123);
 363     BignumMULADD(v127, v126, v6, v9, v110);
 364     BignumMULADD2(v129, v128, v6, v10, v112, v127);
 365     BignumMULADD2(v131, v130, v6, v11, v114, v129);
 366     BignumMULADD2(v133, v132, v6, v12, v116, v131);
 367     BignumMULADD2(v135, v134, v6, v13, v118, v133);
 368     BignumMULADD2(v137, v136, v6, v14, v120, v135);
 369     BignumMULADD2(v139, v138, v6, v15, v122, v137);
 370     BignumMULADD2(v141, v140, v6, v16, v124, v139);
 371     BignumMULADD2(v143, v142, v6, v17, v125, v141);
 372     BignumMULADD(v145, v144, v7, v9, v128);
 373     BignumMULADD2(v147, v146, v7, v10, v130, v145);
 374     BignumMULADD2(v149, v148, v7, v11, v132, v147);
 375     BignumMULADD2(v151, v150, v7, v12, v134, v149);
 376     BignumMULADD2(v153, v152, v7, v13, v136, v151);
 377     BignumMULADD2(v155, v154, v7, v14, v138, v153);
 378     BignumMULADD2(v157, v156, v7, v15, v140, v155);
 379     BignumMULADD2(v159, v158, v7, v16, v142, v157);
 380     BignumMULADD2(v161, v160, v7, v17, v143, v159);
 381     BignumMULADD(v163, v162, v8, v9, v146);
 382     BignumMULADD2(v165, v164, v8, v10, v148, v163);
 383     BignumMULADD2(v167, v166, v8, v11, v150, v165);
 384     BignumMULADD2(v169, v168, v8, v12, v152, v167);
 385     BignumMULADD2(v171, v170, v8, v13, v154, v169);
 386     BignumMULADD2(v173, v172, v8, v14, v156, v171);
 387     BignumMULADD2(v175, v174, v8, v15, v158, v173);
 388     BignumMULADD2(v177, v176, v8, v16, v160, v175);
 389     v178 = v8 * v17 + v161 + v177;
 390     v180 = (v162) & ((((BignumInt)1) << 2)-1);
 391     v181 = ((v162) >> 2) | ((v164) << 14);
 392     v182 = ((v164) >> 2) | ((v166) << 14);
 393     v183 = ((v166) >> 2) | ((v168) << 14);
 394     v184 = ((v168) >> 2) | ((v170) << 14);
 395     v185 = ((v170) >> 2) | ((v172) << 14);
 396     v186 = ((v172) >> 2) | ((v174) << 14);
 397     v187 = ((v174) >> 2) | ((v176) << 14);
 398     v188 = ((v176) >> 2) | ((v178) << 14);
 399     v189 = (v178) >> 2;
 400     v190 = (v189) & ((((BignumInt)1) << 2)-1);
 401     v191 = (v178) >> 4;
 402     BignumMUL(v193, v192, 5, v181);
 403     BignumMULADD(v195, v194, 5, v182, v193);
 404     BignumMULADD(v197, v196, 5, v183, v195);
 405     BignumMULADD(v199, v198, 5, v184, v197);
 406     BignumMULADD(v201, v200, 5, v185, v199);
 407     BignumMULADD(v203, v202, 5, v186, v201);
 408     BignumMULADD(v205, v204, 5, v187, v203);
 409     BignumMULADD(v207, v206, 5, v188, v205);
 410     v208 = 5 * v190 + v207;
 411     v210 = 25 * v191;
 412     BignumADC(v212, carry, v18, v192, 0);
 413     BignumADC(v213, carry, v36, v194, carry);
 414     BignumADC(v214, carry, v54, v196, carry);
 415     BignumADC(v215, carry, v72, v198, carry);
 416     BignumADC(v216, carry, v90, v200, carry);
 417     BignumADC(v217, carry, v108, v202, carry);
 418     BignumADC(v218, carry, v126, v204, carry);
 419     BignumADC(v219, carry, v144, v206, carry);
 420     v220 = v180 + v208 + carry;
 421     BignumADC(v221, carry, v212, v210, 0);
 422     BignumADC(v222, carry, v213, 0, carry);
 423     BignumADC(v223, carry, v214, 0, carry);
 424     BignumADC(v224, carry, v215, 0, carry);
 425     BignumADC(v225, carry, v216, 0, carry);
 426     BignumADC(v226, carry, v217, 0, carry);
 427     BignumADC(v227, carry, v218, 0, carry);
 428     BignumADC(v228, carry, v219, 0, carry);
 429     v229 = v220 + 0 + carry;
 430     r->w[0] = v221;
 431     r->w[1] = v222;
 432     r->w[2] = v223;
 433     r->w[3] = v224;
 434     r->w[4] = v225;
 435     r->w[5] = v226;
 436     r->w[6] = v227;
 437     r->w[7] = v228;
 438     r->w[8] = v229;
 439 }
 440
 441 static void bigval_final_reduce(bigval *n)
 442 {
 443     BignumInt v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v12, v13, v14, v15;
 444     BignumInt v16, v17, v18, v19, v20, v21, v22, v24, v25, v26, v27, v28, v29;
 445     BignumInt v30, v31, v32, v33;
 446     BignumCarry carry;
 447
 448     v0 = n->w[0];
 449     v1 = n->w[1];
 450     v2 = n->w[2];
 451     v3 = n->w[3];
 452     v4 = n->w[4];
 453     v5 = n->w[5];
 454     v6 = n->w[6];
 455     v7 = n->w[7];
 456     v8 = n->w[8];
 457     v9 = (v8) >> 2;
 458     v10 = 5 * v9;
 459     BignumADC(v12, carry, v0, v10, 0);
 460     (void)v12;
 461     BignumADC(v13, carry, v1, 0, carry);
 462     (void)v13;
 463     BignumADC(v14, carry, v2, 0, carry);
 464     (void)v14;
 465     BignumADC(v15, carry, v3, 0, carry);
 466     (void)v15;
 467     BignumADC(v16, carry, v4, 0, carry);
 468     (void)v16;
 469     BignumADC(v17, carry, v5, 0, carry);
 470     (void)v17;
 471     BignumADC(v18, carry, v6, 0, carry);
 472     (void)v18;
 473     BignumADC(v19, carry, v7, 0, carry);
 474     (void)v19;
 475     v20 = v8 + 0 + carry;
 476     v21 = (v20) >> 2;
 477     v22 = 5 * v21;
 478     BignumADC(v24, carry, v0, v22, 0);
 479     BignumADC(v25, carry, v1, 0, carry);
 480     BignumADC(v26, carry, v2, 0, carry);
 481     BignumADC(v27, carry, v3, 0, carry);
 482     BignumADC(v28, carry, v4, 0, carry);
 483     BignumADC(v29, carry, v5, 0, carry);
 484     BignumADC(v30, carry, v6, 0, carry);
 485     BignumADC(v31, carry, v7, 0, carry);
 486     v32 = v8 + 0 + carry;
 487     v33 = (v32) & ((((BignumInt)1) << 2)-1);
 488     n->w[0] = v24;
 489     n->w[1] = v25;
 490     n->w[2] = v26;
 491     n->w[3] = v27;
 492     n->w[4] = v28;
 493     n->w[5] = v29;
 494     n->w[6] = v30;
 495     n->w[7] = v31;
 496     n->w[8] = v33;
 497 }
 498
 499 #elif BIGNUM_INT_BITS == 32
 500
 501 static void bigval_add(bigval *r, const bigval *a, const bigval *b)
 502 {
 503     BignumInt v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14;
 504     BignumCarry carry;
 505
 506     v0 = a->w[0];
 507     v1 = a->w[1];
 508     v2 = a->w[2];
 509     v3 = a->w[3];
 510     v4 = a->w[4];
 511     v5 = b->w[0];
 512     v6 = b->w[1];
 513     v7 = b->w[2];
 514     v8 = b->w[3];
 515     v9 = b->w[4];
 516     BignumADC(v10, carry, v0, v5, 0);
 517     BignumADC(v11, carry, v1, v6, carry);
 518     BignumADC(v12, carry, v2, v7, carry);
 519     BignumADC(v13, carry, v3, v8, carry);
 520     v14 = v4 + v9 + carry;
 521     r->w[0] = v10;
 522     r->w[1] = v11;
 523     r->w[2] = v12;
 524     r->w[3] = v13;
 525     r->w[4] = v14;
 526 }
 527
 528 static void bigval_mul_mod_p(bigval *r, const bigval *a, const bigval *b)
 529 {
 530     BignumInt v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14;
 531     BignumInt v15, v16, v17, v18, v19, v20, v21, v22, v23, v24, v25, v26, v27;
 532     BignumInt v28, v29, v30, v31, v32, v33, v34, v35, v36, v37, v38, v39, v40;
 533     BignumInt v41, v42, v43, v44, v45, v46, v47, v48, v49, v50, v51, v52, v53;
 534     BignumInt v54, v55, v56, v57, v58, v60, v61, v62, v63, v64, v65, v66, v67;
 535     BignumInt v68, v69, v70, v71, v72, v73, v74, v75, v76, v78, v80, v81, v82;
 536     BignumInt v83, v84, v85, v86, v87, v88, v89;
 537     BignumCarry carry;
 538
 539     v0 = a->w[0];
 540     v1 = a->w[1];
 541     v2 = a->w[2];
 542     v3 = a->w[3];
 543     v4 = a->w[4];
 544     v5 = b->w[0];
 545     v6 = b->w[1];
 546     v7 = b->w[2];
 547     v8 = b->w[3];
 548     v9 = b->w[4];
 549     BignumMUL(v11, v10, v0, v5);
 550     BignumMULADD(v13, v12, v0, v6, v11);
 551     BignumMULADD(v15, v14, v0, v7, v13);
 552     BignumMULADD(v17, v16, v0, v8, v15);
 553     BignumMULADD(v19, v18, v0, v9, v17);
 554     BignumMULADD(v21, v20, v1, v5, v12);
 555     BignumMULADD2(v23, v22, v1, v6, v14, v21);
 556     BignumMULADD2(v25, v24, v1, v7, v16, v23);
 557     BignumMULADD2(v27, v26, v1, v8, v18, v25);
 558     BignumMULADD2(v29, v28, v1, v9, v19, v27);
 559     BignumMULADD(v31, v30, v2, v5, v22);
 560     BignumMULADD2(v33, v32, v2, v6, v24, v31);
 561     BignumMULADD2(v35, v34, v2, v7, v26, v33);
 562     BignumMULADD2(v37, v36, v2, v8, v28, v35);
 563     BignumMULADD2(v39, v38, v2, v9, v29, v37);
 564     BignumMULADD(v41, v40, v3, v5, v32);
 565     BignumMULADD2(v43, v42, v3, v6, v34, v41);
 566     BignumMULADD2(v45, v44, v3, v7, v36, v43);
 567     BignumMULADD2(v47, v46, v3, v8, v38, v45);
 568     BignumMULADD2(v49, v48, v3, v9, v39, v47);
 569     BignumMULADD(v51, v50, v4, v5, v42);
 570     BignumMULADD2(v53, v52, v4, v6, v44, v51);
 571     BignumMULADD2(v55, v54, v4, v7, v46, v53);
 572     BignumMULADD2(v57, v56, v4, v8, v48, v55);
 573     v58 = v4 * v9 + v49 + v57;
 574     v60 = (v50) & ((((BignumInt)1) << 2)-1);
 575     v61 = ((v50) >> 2) | ((v52) << 30);
 576     v62 = ((v52) >> 2) | ((v54) << 30);
 577     v63 = ((v54) >> 2) | ((v56) << 30);
 578     v64 = ((v56) >> 2) | ((v58) << 30);
 579     v65 = (v58) >> 2;
 580     v66 = (v65) & ((((BignumInt)1) << 2)-1);
 581     v67 = (v58) >> 4;
 582     BignumMUL(v69, v68, 5, v61);
 583     BignumMULADD(v71, v70, 5, v62, v69);
 584     BignumMULADD(v73, v72, 5, v63, v71);
 585     BignumMULADD(v75, v74, 5, v64, v73);
 586     v76 = 5 * v66 + v75;
 587     v78 = 25 * v67;
 588     BignumADC(v80, carry, v10, v68, 0);
 589     BignumADC(v81, carry, v20, v70, carry);
 590     BignumADC(v82, carry, v30, v72, carry);
 591     BignumADC(v83, carry, v40, v74, carry);
 592     v84 = v60 + v76 + carry;
 593     BignumADC(v85, carry, v80, v78, 0);
 594     BignumADC(v86, carry, v81, 0, carry);
 595     BignumADC(v87, carry, v82, 0, carry);
 596     BignumADC(v88, carry, v83, 0, carry);
 597     v89 = v84 + 0 + carry;
 598     r->w[0] = v85;
 599     r->w[1] = v86;
 600     r->w[2] = v87;
 601     r->w[3] = v88;
 602     r->w[4] = v89;
 603 }
 604
 605 static void bigval_final_reduce(bigval *n)
 606 {
 607     BignumInt v0, v1, v2, v3, v4, v5, v6, v8, v9, v10, v11, v12, v13, v14;
 608     BignumInt v16, v17, v18, v19, v20, v21;
 609     BignumCarry carry;
 610
 611     v0 = n->w[0];
 612     v1 = n->w[1];
 613     v2 = n->w[2];
 614     v3 = n->w[3];
 615     v4 = n->w[4];
 616     v5 = (v4) >> 2;
 617     v6 = 5 * v5;
 618     BignumADC(v8, carry, v0, v6, 0);
 619     (void)v8;
 620     BignumADC(v9, carry, v1, 0, carry);
 621     (void)v9;
 622     BignumADC(v10, carry, v2, 0, carry);
 623     (void)v10;
 624     BignumADC(v11, carry, v3, 0, carry);
 625     (void)v11;
 626     v12 = v4 + 0 + carry;
 627     v13 = (v12) >> 2;
 628     v14 = 5 * v13;
 629     BignumADC(v16, carry, v0, v14, 0);
 630     BignumADC(v17, carry, v1, 0, carry);
 631     BignumADC(v18, carry, v2, 0, carry);
 632     BignumADC(v19, carry, v3, 0, carry);
 633     v20 = v4 + 0 + carry;
 634     v21 = (v20) & ((((BignumInt)1) << 2)-1);
 635     n->w[0] = v16;
 636     n->w[1] = v17;
 637     n->w[2] = v18;
 638     n->w[3] = v19;
 639     n->w[4] = v21;
 640 }
 641
 642 #elif BIGNUM_INT_BITS == 64
 643
 644 static void bigval_add(bigval *r, const bigval *a, const bigval *b)
 645 {
 646     BignumInt v0, v1, v2, v3, v4, v5, v6, v7, v8;
 647     BignumCarry carry;
 648
 649     v0 = a->w[0];
 650     v1 = a->w[1];
 651     v2 = a->w[2];
 652     v3 = b->w[0];
 653     v4 = b->w[1];
 654     v5 = b->w[2];
 655     BignumADC(v6, carry, v0, v3, 0);
 656     BignumADC(v7, carry, v1, v4, carry);
 657     v8 = v2 + v5 + carry;
 658     r->w[0] = v6;
 659     r->w[1] = v7;
 660     r->w[2] = v8;
 661 }
 662
 663 static void bigval_mul_mod_p(bigval *r, const bigval *a, const bigval *b)
 664 {
 665     BignumInt v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14;
 666     BignumInt v15, v16, v17, v18, v19, v20, v21, v22, v24, v25, v26, v27, v28;
 667     BignumInt v29, v30, v31, v32, v33, v34, v36, v38, v39, v40, v41, v42, v43;
 668     BignumCarry carry;
 669
 670     v0 = a->w[0];
 671     v1 = a->w[1];
 672     v2 = a->w[2];
 673     v3 = b->w[0];
 674     v4 = b->w[1];
 675     v5 = b->w[2];
 676     BignumMUL(v7, v6, v0, v3);
 677     BignumMULADD(v9, v8, v0, v4, v7);
 678     BignumMULADD(v11, v10, v0, v5, v9);
 679     BignumMULADD(v13, v12, v1, v3, v8);
 680     BignumMULADD2(v15, v14, v1, v4, v10, v13);
 681     BignumMULADD2(v17, v16, v1, v5, v11, v15);
 682     BignumMULADD(v19, v18, v2, v3, v14);
 683     BignumMULADD2(v21, v20, v2, v4, v16, v19);
 684     v22 = v2 * v5 + v17 + v21;
 685     v24 = (v18) & ((((BignumInt)1) << 2)-1);
 686     v25 = ((v18) >> 2) | ((v20) << 62);
 687     v26 = ((v20) >> 2) | ((v22) << 62);
 688     v27 = (v22) >> 2;
 689     v28 = (v27) & ((((BignumInt)1) << 2)-1);
 690     v29 = (v22) >> 4;
 691     BignumMUL(v31, v30, 5, v25);
 692     BignumMULADD(v33, v32, 5, v26, v31);
 693     v34 = 5 * v28 + v33;
 694     v36 = 25 * v29;
 695     BignumADC(v38, carry, v6, v30, 0);
 696     BignumADC(v39, carry, v12, v32, carry);
 697     v40 = v24 + v34 + carry;
 698     BignumADC(v41, carry, v38, v36, 0);
 699     BignumADC(v42, carry, v39, 0, carry);
 700     v43 = v40 + 0 + carry;
 701     r->w[0] = v41;
 702     r->w[1] = v42;
 703     r->w[2] = v43;
 704 }
 705
 706 static void bigval_final_reduce(bigval *n)
 707 {
 708     BignumInt v0, v1, v2, v3, v4, v6, v7, v8, v9, v10, v12, v13, v14, v15;
 709     BignumCarry carry;
 710
 711     v0 = n->w[0];
 712     v1 = n->w[1];
 713     v2 = n->w[2];
 714     v3 = (v2) >> 2;
 715     v4 = 5 * v3;
 716     BignumADC(v6, carry, v0, v4, 0);
 717     (void)v6;
 718     BignumADC(v7, carry, v1, 0, carry);
 719     (void)v7;
 720     v8 = v2 + 0 + carry;
 721     v9 = (v8) >> 2;
 722     v10 = 5 * v9;
 723     BignumADC(v12, carry, v0, v10, 0);
 724     BignumADC(v13, carry, v1, 0, carry);
 725     v14 = v2 + 0 + carry;
 726     v15 = (v14) & ((((BignumInt)1) << 2)-1);
 727     n->w[0] = v12;
 728     n->w[1] = v13;
 729     n->w[2] = v15;
 730 }
 731
 732 #else
 733 #error Add another bit count to contrib/make1305.py and rerun it
 734 #endif
 735
 736 struct poly1305 {
 737     unsigned char nonce[16];
 738     bigval r;
 739     bigval h;
 740
 741     /* Buffer in case we get less that a multiple of 16 bytes */
 742     unsigned char buffer[16];
 743     int bufferIndex;
 744 };
 745
 746 static void poly1305_init(struct poly1305 *ctx)
 747 {
 748     memset(ctx->nonce, 0, 16);
 749     ctx->bufferIndex = 0;
 750     bigval_clear(&ctx->h);
 751 }
 752
 753 /* Takes a 256 bit key */
 754 static void poly1305_key(struct poly1305 *ctx, const unsigned char *key)
 755 {
 756     unsigned char key_copy[16];
 757     memcpy(key_copy, key, 16);
 758
 759     /* Key the MAC itself
 760      * bytes 4, 8, 12 and 16 are required to have their top four bits clear */
 761     key_copy[3] &= 0x0f;
 762     key_copy[7] &= 0x0f;
 763     key_copy[11] &= 0x0f;
 764     key_copy[15] &= 0x0f;
 765     /* bytes 5, 9 and 13 are required to have their bottom two bits clear */
 766     key_copy[4] &= 0xfc;
 767     key_copy[8] &= 0xfc;
 768     key_copy[12] &= 0xfc;
 769     bigval_import_le(&ctx->r, key_copy, 16);
 770     smemclr(key_copy, sizeof(key_copy));
 771
 772     /* Use second 128 bits are the nonce */
 773     memcpy(ctx->nonce, key+16, 16);
 774 }
 775
 776 /* Feed up to 16 bytes (should only be less for the last chunk) */
 777 static void poly1305_feed_chunk(struct poly1305 *ctx,
 778                                 const unsigned char *chunk, int len)
 779 {
 780     bigval c;
 781     bigval_import_le(&c, chunk, len);
 782     c.w[len / BIGNUM_INT_BYTES] |=
 783         (BignumInt)1 << (8 * (len % BIGNUM_INT_BYTES));
 784     bigval_add(&c, &c, &ctx->h);
 785     bigval_mul_mod_p(&ctx->h, &c, &ctx->r);
 786 }
 787
 788 static void poly1305_feed(struct poly1305 *ctx,
 789                           const unsigned char *buf, int len)
 790 {
 791     /* Check for stuff left in the buffer from last time */
 792     if (ctx->bufferIndex) {
 793         /* Try to fill up to 16 */
 794         while (ctx->bufferIndex < 16 && len) {
 795             ctx->buffer[ctx->bufferIndex++] = *buf++;
 796             --len;
 797         }
 798         if (ctx->bufferIndex == 16) {
 799             poly1305_feed_chunk(ctx, ctx->buffer, 16);
 800             ctx->bufferIndex = 0;
 801         }
 802     }
 803
 804     /* Process 16 byte whole chunks */
 805     while (len >= 16) {
 806         poly1305_feed_chunk(ctx, buf, 16);
 807         len -= 16;
 808         buf += 16;
 809     }
 810
 811     /* Cache stuff that's left over */
 812     if (len) {
 813         memcpy(ctx->buffer, buf, len);
 814         ctx->bufferIndex = len;
 815     }
 816 }
 817
 818 /* Finalise and populate buffer with 16 byte with MAC */
 819 static void poly1305_finalise(struct poly1305 *ctx, unsigned char *mac)
 820 {
 821     bigval tmp;
 822
 823     if (ctx->bufferIndex) {
 824         poly1305_feed_chunk(ctx, ctx->buffer, ctx->bufferIndex);
 825     }
 826
 827     bigval_import_le(&tmp, ctx->nonce, 16);
 828     bigval_final_reduce(&ctx->h);
 829     bigval_add(&tmp, &tmp, &ctx->h);
 830     bigval_export_le(&tmp, mac, 16);
 831 }
 832
 833 /* SSH-2 wrapper */
 834
 835 struct ccp_context {
 836     struct chacha20 a_cipher; /* Used for length */
 837     struct chacha20 b_cipher; /* Used for content */
 838
 839     /* Cache of the first 4 bytes because they are the sequence number */
 840     /* Kept in 8 bytes with the top as zero to allow easy passing to setiv */
 841     int mac_initialised; /* Where we have got to in filling mac_iv */
 842     unsigned char mac_iv[8];
 843
 844     struct poly1305 mac;
 845 };
 846
 847 static void *poly_make_context(void *ctx)
 848 {
 849     return ctx;
 850 }
 851
 852 static void poly_free_context(void *ctx)
 853 {
 854     /* Not allocated, just forwarded, no need to free */
 855 }
 856
 857 static void poly_setkey(void *ctx, unsigned char *key)
 858 {
 859     /* Uses the same context as ChaCha20, so ignore */
 860 }
 861
 862 static void poly_start(void *handle)
 863 {
 864     struct ccp_context *ctx = (struct ccp_context *)handle;
 865
 866     ctx->mac_initialised = 0;
 867     memset(ctx->mac_iv, 0, 8);
 868     poly1305_init(&ctx->mac);
 869 }
 870
 871 static void poly_bytes(void *handle, unsigned char const *blk, int len)
 872 {
 873     struct ccp_context *ctx = (struct ccp_context *)handle;
 874
 875     /* First 4 bytes are the IV */
 876     while (ctx->mac_initialised < 4 && len) {
 877         ctx->mac_iv[7 - ctx->mac_initialised] = *blk++;
 878         ++ctx->mac_initialised;
 879         --len;
 880     }
 881
 882     /* Initialise the IV if needed */
 883     if (ctx->mac_initialised == 4) {
 884         chacha20_iv(&ctx->b_cipher, ctx->mac_iv);
 885         ++ctx->mac_initialised;  /* Don't do it again */
 886
 887         /* Do first rotation */
 888         chacha20_round(&ctx->b_cipher);
 889
 890         /* Set the poly key */
 891         poly1305_key(&ctx->mac, ctx->b_cipher.current);
 892
 893         /* Set the first round as used */
 894         ctx->b_cipher.currentIndex = 64;
 895     }
 896
 897     /* Update the MAC with anything left */
 898     if (len) {
 899         poly1305_feed(&ctx->mac, blk, len);
 900     }
 901 }
 902
 903 static void poly_genresult(void *handle, unsigned char *blk)
 904 {
 905     struct ccp_context *ctx = (struct ccp_context *)handle;
 906     poly1305_finalise(&ctx->mac, blk);
 907 }
 908
 909 static int poly_verresult(void *handle, unsigned char const *blk)
 910 {
 911     struct ccp_context *ctx = (struct ccp_context *)handle;
 912     int res;
 913     unsigned char mac[16];
 914     poly1305_finalise(&ctx->mac, mac);
 915     res = smemeq(blk, mac, 16);
 916     return res;
 917 }
 918
 919 /* The generic poly operation used before generate and verify */
 920 static void poly_op(void *handle, unsigned char *blk, int len, unsigned long seq)
 921 {
 922     unsigned char iv[4];
 923     poly_start(handle);
 924     PUT_32BIT_MSB_FIRST(iv, seq);
 925     /* poly_bytes expects the first 4 bytes to be the IV */
 926     poly_bytes(handle, iv, 4);
 927     smemclr(iv, sizeof(iv));
 928     poly_bytes(handle, blk, len);
 929 }
 930
 931 static void poly_generate(void *handle, unsigned char *blk, int len, unsigned long seq)
 932 {
 933     poly_op(handle, blk, len, seq);
 934     poly_genresult(handle, blk+len);
 935 }
 936
 937 static int poly_verify(void *handle, unsigned char *blk, int len, unsigned long seq)
 938 {
 939     poly_op(handle, blk, len, seq);
 940     return poly_verresult(handle, blk+len);
 941 }
 942
 943 static const struct ssh_mac ssh2_poly1305 = {
 944     poly_make_context, poly_free_context,
 945     poly_setkey,
 946
 947     /* whole-packet operations */
 948     poly_generate, poly_verify,
 949
 950     /* partial-packet operations */
 951     poly_start, poly_bytes, poly_genresult, poly_verresult,
 952
 953     "", "", /* Not selectable individually, just part of ChaCha20-Poly1305 */
 954     16, 0, "Poly1305"
 955 };
 956
 957 static void *ccp_make_context(void)
 958 {
 959     struct ccp_context *ctx = snew(struct ccp_context);
 960     if (ctx) {
 961         poly1305_init(&ctx->mac);
 962     }
 963     return ctx;
 964 }
 965
 966 static void ccp_free_context(void *vctx)
 967 {
 968     struct ccp_context *ctx = (struct ccp_context *)vctx;
 969     smemclr(&ctx->a_cipher, sizeof(ctx->a_cipher));
 970     smemclr(&ctx->b_cipher, sizeof(ctx->b_cipher));
 971     smemclr(&ctx->mac, sizeof(ctx->mac));
 972     sfree(ctx);
 973 }
 974
 975 static void ccp_iv(void *vctx, unsigned char *iv)
 976 {
 977     /* struct ccp_context *ctx = (struct ccp_context *)vctx; */
 978     /* IV is set based on the sequence number */
 979 }
 980
 981 static void ccp_key(void *vctx, unsigned char *key)
 982 {
 983     struct ccp_context *ctx = (struct ccp_context *)vctx;
 984     /* Initialise the a_cipher (for decrypting lengths) with the first 256 bits */
 985     chacha20_key(&ctx->a_cipher, key + 32);
 986     /* Initialise the b_cipher (for content and MAC) with the second 256 bits */
 987     chacha20_key(&ctx->b_cipher, key);
 988 }
 989
 990 static void ccp_encrypt(void *vctx, unsigned char *blk, int len)
 991 {
 992     struct ccp_context *ctx = (struct ccp_context *)vctx;
 993     chacha20_encrypt(&ctx->b_cipher, blk, len);
 994 }
 995
 996 static void ccp_decrypt(void *vctx, unsigned char *blk, int len)
 997 {
 998     struct ccp_context *ctx = (struct ccp_context *)vctx;
 999     chacha20_decrypt(&ctx->b_cipher, blk, len);
1000 }
1001
1002 static void ccp_length_op(struct ccp_context *ctx, unsigned char *blk, int len,
1003                           unsigned long seq)
1004 {
1005     unsigned char iv[8];
1006     /*
1007      * According to RFC 4253 (section 6.4), the packet sequence number wraps
1008      * at 2^32, so its 32 high-order bits will always be zero.
1009      */
1010     PUT_32BIT_LSB_FIRST(iv, 0);
1011     PUT_32BIT_LSB_FIRST(iv + 4, seq);
1012     chacha20_iv(&ctx->a_cipher, iv);
1013     chacha20_iv(&ctx->b_cipher, iv);
1014     /* Reset content block count to 1, as the first is the key for Poly1305 */
1015     ++ctx->b_cipher.state[12];
1016     smemclr(iv, sizeof(iv));
1017 }
1018
1019 static void ccp_encrypt_length(void *vctx, unsigned char *blk, int len,
1020                                unsigned long seq)
1021 {
1022     struct ccp_context *ctx = (struct ccp_context *)vctx;
1023     ccp_length_op(ctx, blk, len, seq);
1024     chacha20_encrypt(&ctx->a_cipher, blk, len);
1025 }
1026
1027 static void ccp_decrypt_length(void *vctx, unsigned char *blk, int len,
1028                                unsigned long seq)
1029 {
1030     struct ccp_context *ctx = (struct ccp_context *)vctx;
1031     ccp_length_op(ctx, blk, len, seq);
1032     chacha20_decrypt(&ctx->a_cipher, blk, len);
1033 }
1034
1035 static const struct ssh2_cipher ssh2_chacha20_poly1305 = {
1036
1037     ccp_make_context,
1038     ccp_free_context,
1039     ccp_iv,
1040     ccp_key,
1041     ccp_encrypt,
1042     ccp_decrypt,
1043     ccp_encrypt_length,
1044     ccp_decrypt_length,
1045
1046     "chacha20-poly1305@openssh.com",
1047     1, 512, 64, SSH_CIPHER_SEPARATE_LENGTH, "ChaCha20",
1048
1049     &ssh2_poly1305
1050 };
1051
1052 static const struct ssh2_cipher *const ccp_list[] = {
1053     &ssh2_chacha20_poly1305
1054 };
1055
1056 const struct ssh2_ciphers ssh2_ccp = {
1057     sizeof(ccp_list) / sizeof(*ccp_list),
1058     ccp_list
1059 };