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_with_sha512(private_bliss_public_key_t *this,
  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 = { data_hash_buf, sizeof(data_hash_buf) };
  72         hasher_t *hasher;
  73         bliss_fft_t *fft;
  74         bliss_signature_t *sig;
  75         bool success = FALSE;
  76
  77         /* Create data hash */
  78         hasher = lib->crypto->create_hasher(lib->crypto, HASH_SHA512);
  79         if (!hasher )
  80         {
  81                 return FALSE;
  82         }
  83         if (!hasher->get_hash(hasher, data, data_hash_buf))
  84         {
  85                 hasher->destroy(hasher);
  86                 return FALSE;
  87         }
  88
  89         sig = bliss_signature_create_from_data(this->set, signature);
  90         if (!sig)
  91         {
  92                 hasher->destroy(hasher);
  93                 return FALSE;
  94         }
  95         sig->get_parameters(sig, &z1, &z2d, &c_indices);
  96
  97         if (!bliss_utils_check_norms(this->set, z1, z2d))
  98         {
  99                 hasher->destroy(hasher);
 100                 sig->destroy(sig);
 101                 return FALSE;
 102         }
 103
 104         /* Initialize a couple of needed variables */
 105         n  = this->set->n;
 106         q  = this->set->q;
 107         p  = this->set->p;
 108         q2 = 2 * q;
 109         az  = malloc(n * sizeof(uint32_t));
 110         u   = malloc(n * sizeof(int32_t));
 111         ud  = malloc(n * sizeof(int16_t));
 112         indices   = malloc(this->set->kappa * sizeof(uint16_t));
 113
 114         for (i = 0; i < n; i++)
 115         {
 116                 az[i] = z1[i] < 0 ? q + z1[i] : z1[i];
 117         }
 118         fft = bliss_fft_create(this->set->fft_params);
 119         fft->transform(fft, az, az, FALSE);
 120
 121         for (i = 0; i < n; i++)
 122         {
 123                 az[i] = (this->A[i] * az[i]) % q;
 124         }
 125         fft->transform(fft, az, az, TRUE);
 126
 127         for (i = 0; i < n; i++)
 128         {
 129                 u[i] = (2 * this->set->q2_inv * az[i]) % q2;
 130         }
 131
 132         for (i = 0; i < this->set->kappa; i++)
 133         {
 134                 u[c_indices[i]] = (u[c_indices[i]] + q * this->set->q2_inv) % q2;
 135         }
 136         bliss_utils_round_and_drop(this->set, u, ud);
 137
 138         for (i = 0; i < n; i++)
 139         {
 140                 ud[i] += z2d[i];
 141                 if (ud[i] < 0)
 142                 {
 143                         ud[i] += p;
 144                 }
 145                 else if (ud[i] >= p)
 146                 {
 147                         ud[i] -= p;
 148                 }
 149         }
 150
 151         /* Detailed debugging information */
 152         DBG3(DBG_LIB, "  i    u[i]  ud[i] z2d[i]");
 153         for (i = 0; i < n; i++)
 154         {
 155                 DBG3(DBG_LIB, "%3d  %6d   %4d  %4d", i, u[i], ud[i], z2d[i]);
 156         }
 157
 158         if (!bliss_utils_generate_c(hasher, data_hash, ud, n, this->set->kappa,
 159                                                                 indices))
 160         {
 161                 goto end;
 162         }
 163
 164         for (i = 0; i < this->set->kappa; i++)
 165         {
 166                 if (indices[i] != c_indices[i])
 167                 {
 168                         DBG1(DBG_LIB, "signature verification failed");
 169                         goto end;
 170                 }
 171         }
 172         success = TRUE;
 173
 174 end:
 175         /* cleanup */
 176         hasher->destroy(hasher);
 177         sig->destroy(sig);
 178         fft->destroy(fft);
 179         free(az);
 180         free(u);
 181         free(ud);
 182         free(indices);
 183
 184         return success;
 185 }
 186
 187 METHOD(public_key_t, verify, bool,
 188         private_bliss_public_key_t *this, signature_scheme_t scheme,
 189         chunk_t data, chunk_t signature)
 190 {
 191         switch (scheme)
 192         {
 193                 case SIGN_BLISS_WITH_SHA512:
 194                         return verify_bliss_with_sha512(this, data, signature);
 195                 default:
 196                         DBG1(DBG_LIB, "signature scheme %N not supported by BLISS",
 197                                  signature_scheme_names, scheme);
 198                         return FALSE;
 199         }
 200 }
 201
 202 METHOD(public_key_t, encrypt_, bool,
 203         private_bliss_public_key_t *this, encryption_scheme_t scheme,
 204         chunk_t plain, chunk_t *crypto)
 205 {
 206         DBG1(DBG_LIB, "encryption scheme %N not supported",
 207                                    encryption_scheme_names, scheme);
 208         return FALSE;
 209 }
 210
 211 METHOD(public_key_t, get_keysize, int,
 212         private_bliss_public_key_t *this)
 213 {
 214         return this->set->strength;
 215 }
 216
 217 METHOD(public_key_t, get_encoding, bool,
 218         private_bliss_public_key_t *this, cred_encoding_type_t type,
 219         chunk_t *encoding)
 220 {
 221         bool success = TRUE;
 222
 223         *encoding = bliss_public_key_info_encode(this->set->oid, this->A, this->set);
 224
 225         if (type != PUBKEY_SPKI_ASN1_DER)
 226         {
 227                 chunk_t asn1_encoding = *encoding;
 228
 229                 success = lib->encoding->encode(lib->encoding, type,
 230                                                 NULL, encoding, CRED_PART_BLISS_PUB_ASN1_DER,
 231                                                 asn1_encoding, CRED_PART_END);
 232                 chunk_clear(&asn1_encoding);
 233         }
 234         return success;
 235 }
 236
 237 METHOD(public_key_t, get_fingerprint, bool,
 238         private_bliss_public_key_t *this, cred_encoding_type_t type, chunk_t *fp)
 239 {
 240         bool success;
 241
 242         if (lib->encoding->get_cache(lib->encoding, type, this, fp))
 243         {
 244                 return TRUE;
 245         }
 246         success = bliss_public_key_fingerprint(this->set->oid, this->A,
 247                                                                                    this->set, type, fp);
 248         if (success)
 249         {
 250                 lib->encoding->cache(lib->encoding, type, this, *fp);
 251         }
 252         return success;
 253 }
 254
 255 METHOD(public_key_t, get_ref, public_key_t*,
 256         private_bliss_public_key_t *this)
 257 {
 258         ref_get(&this->ref);
 259         return &this->public.key;
 260 }
 261
 262 METHOD(public_key_t, destroy, void,
 263         private_bliss_public_key_t *this)
 264 {
 265         if (ref_put(&this->ref))
 266         {
 267                 lib->encoding->clear_cache(lib->encoding, this);
 268                 free(this->A);
 269                 free(this);
 270         }
 271 }
 272
 273 /**
 274  * ASN.1 definition of a BLISS public key
 275  */
 276 static const asn1Object_t pubkeyObjects[] = {
 277         { 0, "subjectPublicKeyInfo",ASN1_SEQUENCE,              ASN1_OBJ  }, /*  0 */
 278         { 1,   "algorithm",                     ASN1_EOC,                       ASN1_RAW  }, /*  1 */
 279         { 1,   "subjectPublicKey",      ASN1_BIT_STRING,        ASN1_BODY }, /*  2 */
 280         { 0, "exit",                            ASN1_EOC,                       ASN1_EXIT }
 281 };
 282 #define BLISS_SUBJECT_PUBLIC_KEY_ALGORITHM      1
 283 #define BLISS_SUBJECT_PUBLIC_KEY                        2
 284
 285 /**
 286  * See header.
 287  */
 288 bliss_public_key_t *bliss_public_key_load(key_type_t type, va_list args)
 289 {
 290         private_bliss_public_key_t *this;
 291         chunk_t blob = chunk_empty, object, param;
 292         asn1_parser_t *parser;
 293         bool success = FALSE;
 294         int objectID, oid;
 295
 296         while (TRUE)
 297         {
 298                 switch (va_arg(args, builder_part_t))
 299                 {
 300                         case BUILD_BLOB_ASN1_DER:
 301                                 blob = va_arg(args, chunk_t);
 302                                 continue;
 303                         case BUILD_END:
 304                                 break;
 305                         default:
 306                                 return NULL;
 307                 }
 308                 break;
 309         }
 310
 311         if (blob.len == 0)
 312         {
 313                 return NULL;
 314         }
 315
 316         INIT(this,
 317                 .public = {
 318                         .key = {
 319                                 .get_type = _get_type,
 320                                 .verify = _verify,
 321                                 .encrypt = _encrypt_,
 322                                 .equals = public_key_equals,
 323                                 .get_keysize = _get_keysize,
 324                                 .get_fingerprint = _get_fingerprint,
 325                                 .has_fingerprint = public_key_has_fingerprint,
 326                                 .get_encoding = _get_encoding,
 327                                 .get_ref = _get_ref,
 328                                 .destroy = _destroy,
 329                         },
 330                 },
 331                 .ref = 1,
 332         );
 333
 334         parser = asn1_parser_create(pubkeyObjects, blob);
 335
 336         while (parser->iterate(parser, &objectID, &object))
 337         {
 338                 switch (objectID)
 339                 {
 340                         case BLISS_SUBJECT_PUBLIC_KEY_ALGORITHM:
 341                         {
 342                                 oid = asn1_parse_algorithmIdentifier(object,
 343                                                                 parser->get_level(parser)+1, &param);
 344                                 if (oid != OID_BLISS_PUBLICKEY)
 345                                 {
 346                                         goto end;
 347                                 }
 348                                 if (!asn1_parse_simple_object(&param, ASN1_OID,
 349                                                                 parser->get_level(parser)+3, "blissKeyType"))
 350                                 {
 351                                         goto end;
 352                                 }
 353                                 oid = asn1_known_oid(param);
 354                                 if (oid == OID_UNKNOWN)
 355                                 {
 356                                         goto end;
 357                                 }
 358                                 this->set = bliss_param_set_get_by_oid(oid);
 359                                 if (this->set == NULL)
 360                                 {
 361                                         goto end;
 362                                 }
 363                                 break;
 364                         }
 365                         case BLISS_SUBJECT_PUBLIC_KEY:
 366                                 if (!bliss_public_key_from_asn1(object, this->set, &this->A))
 367                                 {
 368                                         goto end;
 369                                 }
 370                                 break;
 371                 }
 372         }
 373         success = parser->success(parser);
 374
 375 end:
 376         parser->destroy(parser);
 377         if (!success)
 378         {
 379                 destroy(this);
 380                 return NULL;
 381         }
 382
 383         return &this->public;
 384 }
 385
 386 /**
 387  * See header.
 388  */
 389 bool bliss_public_key_from_asn1(chunk_t object, bliss_param_set_t *set,
 390                                                                 uint32_t **pubkey)
 391 {
 392         bliss_bitpacker_t *packer;
 393         uint32_t coefficient;
 394         uint16_t needed_bits;
 395         int i;
 396
 397         /* skip initial bit string octet defining unused bits */
 398         object = chunk_skip(object, 1);
 399
 400         needed_bits = set->n * set->q_bits;
 401
 402         if (8 * object.len < needed_bits)
 403         {
 404                 return FALSE;
 405         }
 406         *pubkey = malloc(set->n * sizeof(uint32_t));
 407
 408         packer = bliss_bitpacker_create_from_data(object);
 409
 410         for (i = 0; i < set->n; i++)
 411         {
 412                 packer->read_bits(packer, &coefficient, set->q_bits);
 413                 if (coefficient >= set->q)
 414                 {
 415                         packer->destroy(packer);
 416                         return FALSE;
 417                 }
 418                 (*pubkey)[i] = coefficient;
 419         }
 420         packer->destroy(packer);
 421
 422         return TRUE;
 423 }
 424
 425 /**
 426  * See header.
 427  */
 428 chunk_t bliss_public_key_encode(uint32_t *pubkey, bliss_param_set_t *set)
 429 {
 430         bliss_bitpacker_t *packer;
 431         chunk_t encoding;
 432         int i;
 433
 434         packer = bliss_bitpacker_create(set->n * set->q_bits);
 435
 436         for (i = 0; i < set->n; i++)
 437         {
 438                 packer->write_bits(packer, pubkey[i], set->q_bits);
 439         }
 440         encoding = packer->extract_buf(packer);
 441         packer->destroy(packer);
 442
 443         return encoding;
 444 }
 445
 446 /**
 447  * See header.
 448  */
 449 chunk_t bliss_public_key_info_encode(int oid, uint32_t *pubkey,
 450                                                                          bliss_param_set_t *set)
 451 {
 452         chunk_t encoding, pubkey_encoding;
 453
 454         pubkey_encoding = bliss_public_key_encode(pubkey, set);
 455
 456         encoding = asn1_wrap(ASN1_SEQUENCE, "mm",
 457                                         asn1_wrap(ASN1_SEQUENCE, "mm",
 458                                                 asn1_build_known_oid(OID_BLISS_PUBLICKEY),
 459                                                 asn1_build_known_oid(oid)),
 460                                         asn1_bitstring("m", pubkey_encoding));
 461
 462         return encoding;
 463 }
 464
 465 /**
 466  * See header.
 467  */
 468 bool bliss_public_key_fingerprint(int oid, uint32_t *pubkey,
 469                                                                   bliss_param_set_t *set,
 470                                                                   cred_encoding_type_t type, chunk_t *fp)
 471 {
 472         hasher_t *hasher;
 473         chunk_t key;
 474
 475         switch (type)
 476         {
 477                 case KEYID_PUBKEY_SHA1:
 478                         key = bliss_public_key_encode(pubkey, set);
 479                         break;
 480                 case KEYID_PUBKEY_INFO_SHA1:
 481                         key = bliss_public_key_info_encode(oid, pubkey, set);
 482                         break;
 483                 default:
 484                         return FALSE;
 485         }
 486
 487         hasher = lib->crypto->create_hasher(lib->crypto, HASH_SHA1);
 488         if (!hasher || !hasher->allocate_hash(hasher, key, fp))
 489         {
 490                 DBG1(DBG_LIB, "SHA1 hash algorithm not supported, fingerprinting failed");
 491                 DESTROY_IF(hasher);
 492                 free(key.ptr);
 493
 494                 return FALSE;
 495         }
 496         hasher->destroy(hasher);
 497         free(key.ptr);
 498
 499         return TRUE;
 500 }
 501