src/libstrongswan/plugins/bliss/bliss_public_key.c

   1 /*
   2  * Copyright (C) 2014 Andreas Steffen
   3  * HSR Hochschule fuer Technik Rapperswil
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; either version 2 of the License, or (at your
   8  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * for more details.
  14  */
  15
  16 #include "bliss_public_key.h"
  17 #include "bliss_signature.h"
  18 #include "bliss_bitpacker.h"
  19 #include "bliss_fft.h"
  20 #include "bliss_utils.h"
  21
  22 #include <asn1/asn1.h>
  23 #include <asn1/asn1_parser.h>
  24 #include <asn1/oid.h>
  25
  26 typedef struct private_bliss_public_key_t private_bliss_public_key_t;
  27
  28 /**
  29  * Private data structure with signing context.
  30  */
  31 struct private_bliss_public_key_t {
  32         /**
  33          * Public interface for this signer.
  34          */
  35         bliss_public_key_t public;
  36
  37         /**
  38          * BLISS signature parameter set
  39          */
  40         bliss_param_set_t *set;
  41
  42         /**
  43          * NTT of BLISS public key a (coefficients of polynomial (2g + 1)/f)
  44          */
  45         uint32_t *A;
  46
  47         /**
  48          * reference counter
  49          */
  50         refcount_t ref;
  51 };
  52
  53 METHOD(public_key_t, get_type, key_type_t,
  54         private_bliss_public_key_t *this)
  55 {
  56         return KEY_BLISS;
  57 }
  58
  59 /**
  60  * Verify a BLISS signature based on a SHA-512 hash
  61  */
  62 static bool verify_bliss(private_bliss_public_key_t *this, hash_algorithm_t alg,
  63                                                  chunk_t data, chunk_t signature)
  64 {
  65         int i, n;
  66         int32_t *z1, *u;
  67         int16_t *ud, *z2d;
  68         uint16_t q, q2, p, *c_indices, *indices;
  69         uint32_t *az;
  70         uint8_t data_hash_buf[HASH_SIZE_SHA512];
  71         chunk_t data_hash;
  72         hasher_t *hasher;
  73         hash_algorithm_t oracle_alg;
  74         bliss_fft_t *fft;
  75         bliss_signature_t *sig;
  76         bool success = FALSE;
  77
  78         /* Create data hash using configurable hash algorithm */
  79         hasher = lib->crypto->create_hasher(lib->crypto, alg);
  80         if (!hasher )
  81         {
  82                 return FALSE;
  83         }
  84         data_hash = chunk_create(data_hash_buf, hasher->get_hash_size(hasher));
  85
  86         if (!hasher->get_hash(hasher, data, data_hash_buf))
  87         {
  88                 hasher->destroy(hasher);
  89                 return FALSE;
  90         }
  91         hasher->destroy(hasher);
  92
  93         sig = bliss_signature_create_from_data(this->set, signature);
  94         if (!sig)
  95         {
  96                 return FALSE;
  97         }
  98         sig->get_parameters(sig, &z1, &z2d, &c_indices);
  99
 100         if (!bliss_utils_check_norms(this->set, z1, z2d))
 101         {
 102                 sig->destroy(sig);
 103                 return FALSE;
 104         }
 105
 106         /* MGF1 hash algorithm to be used for random oracle */
 107         oracle_alg = HASH_SHA512;
 108
 109         /* Initialize a couple of needed variables */
 110         n  = this->set->n;
 111         q  = this->set->q;
 112         p  = this->set->p;
 113         q2 = 2 * q;
 114         az  = malloc(n * sizeof(uint32_t));
 115         u   = malloc(n * sizeof(int32_t));
 116         ud  = malloc(n * sizeof(int16_t));
 117         indices   = malloc(this->set->kappa * sizeof(uint16_t));
 118
 119         for (i = 0; i < n; i++)
 120         {
 121                 az[i] = z1[i] < 0 ? q + z1[i] : z1[i];
 122         }
 123         fft = bliss_fft_create(this->set->fft_params);
 124         fft->transform(fft, az, az, FALSE);
 125
 126         for (i = 0; i < n; i++)
 127         {
 128                 az[i] = (this->A[i] * az[i]) % q;
 129         }
 130         fft->transform(fft, az, az, TRUE);
 131
 132         for (i = 0; i < n; i++)
 133         {
 134                 u[i] = (2 * this->set->q2_inv * az[i]) % q2;
 135         }
 136
 137         for (i = 0; i < this->set->kappa; i++)
 138         {
 139                 u[c_indices[i]] = (u[c_indices[i]] + q * this->set->q2_inv) % q2;
 140         }
 141         bliss_utils_round_and_drop(this->set, u, ud);
 142
 143         for (i = 0; i < n; i++)
 144         {
 145                 ud[i] += z2d[i];
 146                 if (ud[i] < 0)
 147                 {
 148                         ud[i] += p;
 149                 }
 150                 else if (ud[i] >= p)
 151                 {
 152                         ud[i] -= p;
 153                 }
 154         }
 155
 156         /* Detailed debugging information */
 157         DBG3(DBG_LIB, "  i    u[i]  ud[i] z2d[i]");
 158         for (i = 0; i < n; i++)
 159         {
 160                 DBG3(DBG_LIB, "%3d  %6d   %4d  %4d", i, u[i], ud[i], z2d[i]);
 161         }
 162
 163         if (!bliss_utils_generate_c(oracle_alg, data_hash, ud, this->set, indices))
 164         {
 165                 goto end;
 166         }
 167
 168         for (i = 0; i < this->set->kappa; i++)
 169         {
 170                 if (indices[i] != c_indices[i])
 171                 {
 172                         DBG1(DBG_LIB, "signature verification failed");
 173                         goto end;
 174                 }
 175         }
 176         success = TRUE;
 177
 178 end:
 179         /* cleanup */
 180         sig->destroy(sig);
 181         fft->destroy(fft);
 182         free(az);
 183         free(u);
 184         free(ud);
 185         free(indices);
 186
 187         return success;
 188 }
 189
 190 METHOD(public_key_t, verify, bool,
 191         private_bliss_public_key_t *this, signature_scheme_t scheme,
 192         chunk_t data, chunk_t signature)
 193 {
 194         switch (scheme)
 195         {
 196                 case SIGN_BLISS_WITH_SHA256:
 197                         return verify_bliss(this, HASH_SHA256, data, signature);
 198                 case SIGN_BLISS_WITH_SHA384:
 199                         return verify_bliss(this, HASH_SHA384, data, signature);
 200                 case SIGN_BLISS_WITH_SHA512:
 201                         return verify_bliss(this, HASH_SHA512, data, signature);
 202                 default:
 203                         DBG1(DBG_LIB, "signature scheme %N not supported by BLISS",
 204                                  signature_scheme_names, scheme);
 205                         return FALSE;
 206         }
 207 }
 208
 209 METHOD(public_key_t, encrypt_, bool,
 210         private_bliss_public_key_t *this, encryption_scheme_t scheme,
 211         chunk_t plain, chunk_t *crypto)
 212 {
 213         DBG1(DBG_LIB, "encryption scheme %N not supported",
 214                                    encryption_scheme_names, scheme);
 215         return FALSE;
 216 }
 217
 218 METHOD(public_key_t, get_keysize, int,
 219         private_bliss_public_key_t *this)
 220 {
 221         return this->set->strength;
 222 }
 223
 224 METHOD(public_key_t, get_encoding, bool,
 225         private_bliss_public_key_t *this, cred_encoding_type_t type,
 226         chunk_t *encoding)
 227 {
 228         bool success = TRUE;
 229
 230         *encoding = bliss_public_key_info_encode(this->set->oid, this->A, this->set);
 231
 232         if (type != PUBKEY_SPKI_ASN1_DER)
 233         {
 234                 chunk_t asn1_encoding = *encoding;
 235
 236                 success = lib->encoding->encode(lib->encoding, type,
 237                                                 NULL, encoding, CRED_PART_BLISS_PUB_ASN1_DER,
 238                                                 asn1_encoding, CRED_PART_END);
 239                 chunk_clear(&asn1_encoding);
 240         }
 241         return success;
 242 }
 243
 244 METHOD(public_key_t, get_fingerprint, bool,
 245         private_bliss_public_key_t *this, cred_encoding_type_t type, chunk_t *fp)
 246 {
 247         bool success;
 248
 249         if (lib->encoding->get_cache(lib->encoding, type, this, fp))
 250         {
 251                 return TRUE;
 252         }
 253         success = bliss_public_key_fingerprint(this->set->oid, this->A,
 254                                                                                    this->set, type, fp);
 255         if (success)
 256         {
 257                 lib->encoding->cache(lib->encoding, type, this, *fp);
 258         }
 259         return success;
 260 }
 261
 262 METHOD(public_key_t, get_ref, public_key_t*,
 263         private_bliss_public_key_t *this)
 264 {
 265         ref_get(&this->ref);
 266         return &this->public.key;
 267 }
 268
 269 METHOD(public_key_t, destroy, void,
 270         private_bliss_public_key_t *this)
 271 {
 272         if (ref_put(&this->ref))
 273         {
 274                 lib->encoding->clear_cache(lib->encoding, this);
 275                 free(this->A);
 276                 free(this);
 277         }
 278 }
 279
 280 /**
 281  * ASN.1 definition of a BLISS public key
 282  */
 283 static const asn1Object_t pubkeyObjects[] = {
 284         { 0, "subjectPublicKeyInfo",ASN1_SEQUENCE,              ASN1_OBJ  }, /*  0 */
 285         { 1,   "algorithm",                     ASN1_EOC,                       ASN1_RAW  }, /*  1 */
 286         { 1,   "subjectPublicKey",      ASN1_BIT_STRING,        ASN1_BODY }, /*  2 */
 287         { 0, "exit",                            ASN1_EOC,                       ASN1_EXIT }
 288 };
 289 #define BLISS_SUBJECT_PUBLIC_KEY_ALGORITHM      1
 290 #define BLISS_SUBJECT_PUBLIC_KEY                        2
 291
 292 /**
 293  * See header.
 294  */
 295 bliss_public_key_t *bliss_public_key_load(key_type_t type, va_list args)
 296 {
 297         private_bliss_public_key_t *this;
 298         chunk_t blob = chunk_empty, object, param;
 299         asn1_parser_t *parser;
 300         bool success = FALSE;
 301         int objectID, oid;
 302
 303         while (TRUE)
 304         {
 305                 switch (va_arg(args, builder_part_t))
 306                 {
 307                         case BUILD_BLOB_ASN1_DER:
 308                                 blob = va_arg(args, chunk_t);
 309                                 continue;
 310                         case BUILD_END:
 311                                 break;
 312                         default:
 313                                 return NULL;
 314                 }
 315                 break;
 316         }
 317
 318         if (blob.len == 0)
 319         {
 320                 return NULL;
 321         }
 322
 323         INIT(this,
 324                 .public = {
 325                         .key = {
 326                                 .get_type = _get_type,
 327                                 .verify = _verify,
 328                                 .encrypt = _encrypt_,
 329                                 .equals = public_key_equals,
 330                                 .get_keysize = _get_keysize,
 331                                 .get_fingerprint = _get_fingerprint,
 332                                 .has_fingerprint = public_key_has_fingerprint,
 333                                 .get_encoding = _get_encoding,
 334                                 .get_ref = _get_ref,
 335                                 .destroy = _destroy,
 336                         },
 337                 },
 338                 .ref = 1,
 339         );
 340
 341         parser = asn1_parser_create(pubkeyObjects, blob);
 342
 343         while (parser->iterate(parser, &objectID, &object))
 344         {
 345                 switch (objectID)
 346                 {
 347                         case BLISS_SUBJECT_PUBLIC_KEY_ALGORITHM:
 348                         {
 349                                 oid = asn1_parse_algorithmIdentifier(object,
 350                                                                 parser->get_level(parser)+1, &param);
 351                                 if (oid != OID_BLISS_PUBLICKEY)
 352                                 {
 353                                         goto end;
 354                                 }
 355                                 if (!asn1_parse_simple_object(&param, ASN1_OID,
 356                                                                 parser->get_level(parser)+3, "blissKeyType"))
 357                                 {
 358                                         goto end;
 359                                 }
 360                                 oid = asn1_known_oid(param);
 361                                 if (oid == OID_UNKNOWN)
 362                                 {
 363                                         goto end;
 364                                 }
 365                                 this->set = bliss_param_set_get_by_oid(oid);
 366                                 if (this->set == NULL)
 367                                 {
 368                                         goto end;
 369                                 }
 370                                 break;
 371                         }
 372                         case BLISS_SUBJECT_PUBLIC_KEY:
 373                                 if (!bliss_public_key_from_asn1(object, this->set, &this->A))
 374                                 {
 375                                         goto end;
 376                                 }
 377                                 break;
 378                 }
 379         }
 380         success = parser->success(parser);
 381
 382 end:
 383         parser->destroy(parser);
 384         if (!success)
 385         {
 386                 destroy(this);
 387                 return NULL;
 388         }
 389
 390         return &this->public;
 391 }
 392
 393 /**
 394  * See header.
 395  */
 396 bool bliss_public_key_from_asn1(chunk_t object, bliss_param_set_t *set,
 397                                                                 uint32_t **pubkey)
 398 {
 399         bliss_bitpacker_t *packer;
 400         uint32_t coefficient;
 401         uint16_t needed_bits;
 402         int i;
 403
 404         /* skip initial bit string octet defining unused bits */
 405         object = chunk_skip(object, 1);
 406
 407         needed_bits = set->n * set->q_bits;
 408
 409         if (8 * object.len < needed_bits)
 410         {
 411                 return FALSE;
 412         }
 413         *pubkey = malloc(set->n * sizeof(uint32_t));
 414
 415         packer = bliss_bitpacker_create_from_data(object);
 416
 417         for (i = 0; i < set->n; i++)
 418         {
 419                 packer->read_bits(packer, &coefficient, set->q_bits);
 420                 if (coefficient >= set->q)
 421                 {
 422                         packer->destroy(packer);
 423                         return FALSE;
 424                 }
 425                 (*pubkey)[i] = coefficient;
 426         }
 427         packer->destroy(packer);
 428
 429         return TRUE;
 430 }
 431
 432 /**
 433  * See header.
 434  */
 435 chunk_t bliss_public_key_encode(uint32_t *pubkey, bliss_param_set_t *set)
 436 {
 437         bliss_bitpacker_t *packer;
 438         chunk_t encoding;
 439         int i;
 440
 441         packer = bliss_bitpacker_create(set->n * set->q_bits);
 442
 443         for (i = 0; i < set->n; i++)
 444         {
 445                 packer->write_bits(packer, pubkey[i], set->q_bits);
 446         }
 447         encoding = packer->extract_buf(packer);
 448         packer->destroy(packer);
 449
 450         return encoding;
 451 }
 452
 453 /**
 454  * See header.
 455  */
 456 chunk_t bliss_public_key_info_encode(int oid, uint32_t *pubkey,
 457                                                                          bliss_param_set_t *set)
 458 {
 459         chunk_t encoding, pubkey_encoding;
 460
 461         pubkey_encoding = bliss_public_key_encode(pubkey, set);
 462
 463         encoding = asn1_wrap(ASN1_SEQUENCE, "mm",
 464                                         asn1_wrap(ASN1_SEQUENCE, "mm",
 465                                                 asn1_build_known_oid(OID_BLISS_PUBLICKEY),
 466                                                 asn1_build_known_oid(oid)),
 467                                         asn1_bitstring("m", pubkey_encoding));
 468
 469         return encoding;
 470 }
 471
 472 /**
 473  * See header.
 474  */
 475 bool bliss_public_key_fingerprint(int oid, uint32_t *pubkey,
 476                                                                   bliss_param_set_t *set,
 477                                                                   cred_encoding_type_t type, chunk_t *fp)
 478 {
 479         hasher_t *hasher;
 480         chunk_t key;
 481
 482         switch (type)
 483         {
 484                 case KEYID_PUBKEY_SHA1:
 485                         key = bliss_public_key_encode(pubkey, set);
 486                         break;
 487                 case KEYID_PUBKEY_INFO_SHA1:
 488                         key = bliss_public_key_info_encode(oid, pubkey, set);
 489                         break;
 490                 default:
 491                         return FALSE;
 492         }
 493
 494         hasher = lib->crypto->create_hasher(lib->crypto, HASH_SHA1);
 495         if (!hasher || !hasher->allocate_hash(hasher, key, fp))
 496         {
 497                 DBG1(DBG_LIB, "SHA1 hash algorithm not supported, fingerprinting failed");
 498                 DESTROY_IF(hasher);
 499                 free(key.ptr);
 500
 501                 return FALSE;
 502         }
 503         hasher->destroy(hasher);
 504         free(key.ptr);
 505
 506         return TRUE;
 507 }
 508