Created bliss_bitpacker class to encode BLISS signatures
authorAndreas Steffen <andreas.steffen@strongswan.org>
Thu, 27 Nov 2014 07:52:24 +0000 (08:52 +0100)
committerAndreas Steffen <andreas.steffen@strongswan.org>
Sat, 29 Nov 2014 13:51:17 +0000 (14:51 +0100)
src/libstrongswan/plugins/bliss/Makefile.am
src/libstrongswan/plugins/bliss/bliss_bitpacker.c [new file with mode: 0644]
src/libstrongswan/plugins/bliss/bliss_bitpacker.h [new file with mode: 0644]
src/libstrongswan/plugins/bliss/bliss_param_set.c
src/libstrongswan/plugins/bliss/bliss_param_set.h
src/libstrongswan/plugins/bliss/bliss_signature.c
src/libstrongswan/plugins/bliss/bliss_tests.h
src/libstrongswan/plugins/bliss/suites/test_bliss_bitpacker.c [new file with mode: 0644]

index b88964d..d2010de 100644 (file)
@@ -18,6 +18,7 @@ libstrongswan_bliss_la_SOURCES = \
        bliss_public_key.h bliss_public_key.c \
        bliss_signature.h bliss_signature.c \
        bliss_utils.h bliss_utils.c \
+       bliss_bitpacker.h bliss_bitpacker.c \
        bliss_fft.h bliss_fft.c \
        bliss_fft_params.h bliss_fft_params.c \
        bliss_sampler.h bliss_sampler.c
@@ -30,6 +31,7 @@ check_PROGRAMS = $(TESTS)
 
 bliss_tests_SOURCES = \
        suites/test_bliss_fft.c \
+       suites/test_bliss_bitpacker.c \
        suites/test_bliss_sign.c \
        bliss_fft_params.c \
        bliss_fft.c \
@@ -39,6 +41,7 @@ bliss_tests_SOURCES = \
        bliss_sampler.c \
        bliss_signature.c \
        bliss_utils.c \
+       bliss_bitpacker.c \
        bliss_tests.h bliss_tests.c
 
 bliss_tests_CFLAGS = \
diff --git a/src/libstrongswan/plugins/bliss/bliss_bitpacker.c b/src/libstrongswan/plugins/bliss/bliss_bitpacker.c
new file mode 100644 (file)
index 0000000..6bd480f
--- /dev/null
@@ -0,0 +1,203 @@
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY;https://www.hsr.ch/HSR-intern-Anmeldung.4409.0.html?&no_cache=1 without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * for more details.
+ */
+
+#include "bliss_bitpacker.h"
+
+typedef struct private_bliss_bitpacker_t private_bliss_bitpacker_t;
+
+/**
+ * Private data structure for bliss_bitpacker_t object
+ */
+struct private_bliss_bitpacker_t {
+       /**
+        * Public interface.
+        */
+       bliss_bitpacker_t public;
+
+       /**
+        * Current number of bits written to buffer
+        */
+       size_t bits;
+
+       /**
+        * Bit buffer for up to 16 bits
+        */
+       uint16_t bits_buf;
+
+       /**
+        * Bits left in the bit buffer
+        */
+       size_t bits_left;
+
+       /**
+        * Buffer
+        */
+       chunk_t buf;
+
+       /**
+        * Read/Write pointer into buffer
+        */
+       chunk_t pos;
+
+};
+
+METHOD(bliss_bitpacker_t, get_bits, size_t,
+       private_bliss_bitpacker_t *this)
+{
+       return this->bits;
+}
+
+METHOD(bliss_bitpacker_t, write_bits, bool,
+       private_bliss_bitpacker_t *this, uint16_t value, size_t bits)
+{
+       if (bits > 16)
+       {
+               return FALSE;
+       }
+       this->bits += bits;
+       value &= (1 << bits) - 1;
+
+       while (TRUE)
+       {
+               if (bits <= this->bits_left)
+               {
+                       this->bits_buf |= value << (this->bits_left - bits);
+                       this->bits_left -= bits;
+                       return TRUE;
+               }
+
+               this->bits_buf |= value >> (bits - this->bits_left);
+               value &= (1 << (bits - this->bits_left)) - 1;
+               bits -= this->bits_left;
+
+               if (this->pos.len < 4)
+               {
+                       return FALSE;
+               }
+               htoun16(this->pos.ptr, this->bits_buf);
+               this->pos = chunk_skip(this->pos, 2);
+               this->bits_buf = 0;
+               this->bits_left = 16;
+       }
+}
+
+METHOD(bliss_bitpacker_t, read_bits, bool,
+       private_bliss_bitpacker_t *this, uint16_t *value, size_t bits)
+{
+       if (bits > 16)
+       {
+               return FALSE;
+       }
+       *value = 0;
+
+       while (TRUE)
+       {
+               if (this->bits_left == 0)
+               {
+                       if (this->pos.len < 2)
+                       {
+                               return FALSE;
+                       }
+                       this->bits_buf = untoh16(this->pos.ptr);
+                       this->pos = chunk_skip(this->pos, 2);
+                       this->bits_left = 16;
+               }
+               if (bits <= this->bits_left)
+               {
+                       *value |= this->bits_buf >> (this->bits_left - bits);
+                       this->bits_buf &= (1 << (this->bits_left - bits)) - 1;
+                       this->bits_left -= bits;
+
+                       return TRUE;
+               }
+               *value |= this->bits_buf << (bits - this->bits_left);
+               bits -= this->bits_left;
+               this->bits_left = 0;
+       }
+}
+
+METHOD(bliss_bitpacker_t, extract_buf, chunk_t,
+       private_bliss_bitpacker_t *this)
+{
+       chunk_t buf;
+
+       htoun16(this->pos.ptr, this->bits_buf);
+       this->pos.len -= 2;
+       buf = this->buf;
+       buf.len = this->buf.len - this->pos.len - this->bits_left/8;
+       this->buf = this->pos = chunk_empty;
+
+       return buf;
+}
+
+METHOD(bliss_bitpacker_t, destroy, void,
+       private_bliss_bitpacker_t *this)
+{
+       free(this->buf.ptr);
+       free(this);
+}
+
+/**
+ * See header.
+ */
+bliss_bitpacker_t *bliss_bitpacker_create(size_t max_bits)
+{
+       private_bliss_bitpacker_t *this;
+
+       INIT(this,
+               .public = {
+                       .get_bits = _get_bits,
+                       .write_bits = _write_bits,
+                       .read_bits = _read_bits,
+                       .extract_buf = _extract_buf,
+                       .destroy = _destroy,
+               },
+               .bits_left = 16,
+               .buf = chunk_alloc(round_up(max_bits, 16)/8),
+       );
+
+       this->pos = this->buf;
+
+       return &this->public;
+}
+
+/**
+ * See header.
+ */
+bliss_bitpacker_t *bliss_bitpacker_create_from_data(chunk_t data)
+{
+       private_bliss_bitpacker_t *this;
+
+       INIT(this,
+               .public = {
+                       .get_bits = _get_bits,
+                       .write_bits = _write_bits,
+                       .read_bits = _read_bits,
+                       .extract_buf = _extract_buf,
+                       .destroy = _destroy,
+               },
+               .bits = 8 * data.len,
+               .buf = chunk_alloc(round_up(data.len, 2)),
+       );
+
+       memcpy(this->buf.ptr, data.ptr, data.len);
+       if (this->buf.len > data.len)
+       {
+               *(this->buf.ptr + data.len) = 0x00;
+       }
+       this->pos = this->buf;
+
+       return &this->public;
+}
diff --git a/src/libstrongswan/plugins/bliss/bliss_bitpacker.h b/src/libstrongswan/plugins/bliss/bliss_bitpacker.h
new file mode 100644 (file)
index 0000000..76accc2
--- /dev/null
@@ -0,0 +1,85 @@
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * for more details.
+ */
+
+/**
+ * @defgroup bliss_bitpacker bliss_bitpacker
+ * @{ @ingroup bliss_p
+ */
+
+#ifndef BLISS_BITPACKER_H_
+#define BLISS_BITPACKER_H_
+
+#include <library.h>
+
+typedef struct bliss_bitpacker_t bliss_bitpacker_t;
+
+/**
+ * Reads and writes a variable number of bits in packed format
+ * from and to an octet buffer
+ */
+struct bliss_bitpacker_t {
+
+       /**
+        * Get the number of bits written into buffer
+        *
+        * @result                      Number of bits written
+        */
+       size_t (*get_bits)(bliss_bitpacker_t *this);
+
+       /**
+        * Get the prime modulus of the Number Theoretic Transform
+        *
+        * @param value         Value to be written
+        * @param bits          Number of bits to be written
+        * @result                      TRUE if value could be written into buffer
+        */
+       bool (*write_bits)(bliss_bitpacker_t *this, uint16_t value, size_t bits);
+
+
+       /**
+        * Get the prime modulus of the Number Theoretic Transform
+        *
+        * @param value         Value returned
+        * @param bits          Number of bits to be read
+        * @result                      TRUE if value could be read from buffer
+        */
+       bool (*read_bits)(bliss_bitpacker_t *this, uint16_t *value, size_t bits);
+
+       /**
+        * Detach the internal octet buffer and return it
+        */
+       chunk_t (*extract_buf)(bliss_bitpacker_t *this);
+
+       /**
+        * Destroy bliss_bitpacker_t object
+        */
+       void (*destroy)(bliss_bitpacker_t *this);
+};
+
+/**
+ * Create a bliss_bitpacker_t object for writing
+ *
+ * @param bits                 Total number of bits to be stored 
+ */
+bliss_bitpacker_t* bliss_bitpacker_create(size_t max_bits);
+
+/**
+ * Create a bliss_bitpacker_t object for reading
+ *
+ * @param data                 Packed array of bits 
+ */
+bliss_bitpacker_t* bliss_bitpacker_create_from_data(chunk_t data);
+
+#endif /** BLISS_BITPACKER_H_ @}*/
index 4623b5a..2fde669 100644 (file)
@@ -136,10 +136,11 @@ static bliss_param_set_t bliss_param_sets[] = {
                .c = c_bliss_i,
                .c_cols = 16,
                .c_rows = 21,
+               .z1_bits = 12,
                .d = 10,
                .p = 24,
                .M = 46539,
-               .B_inf = 2100,
+               .B_inf = 2047, /* reduced from 2100 due to 12 bit z1 encoding */
                .B_l2 = 12872 * 12872
       },
 
@@ -162,6 +163,7 @@ static bliss_param_set_t bliss_param_sets[] = {
                .c = c_bliss_iii,
                .c_cols = 16,
                .c_rows = 21,
+               .z1_bits = 12,
                .d = 9,
                .p = 48,
                .M = 128113,
@@ -188,6 +190,7 @@ static bliss_param_set_t bliss_param_sets[] = {
                .c = c_bliss_iv,
                .c_cols = 16,
                .c_rows = 22,
+               .z1_bits = 12,
                .d = 8,
                .p = 96,
                .M = 244186,
index 8c850c3..305d3a1 100644 (file)
@@ -131,7 +131,12 @@ struct bliss_param_set_t {
        size_t c_rows;
 
        /**
-        * Number of bits to be dropped after rounding
+        * Number of bits in z1
+        */
+       uint16_t z1_bits;
+
+       /**
+        * Number of z2 bits to be dropped after rounding
         */
        uint16_t d;
 
index ff0e47b..4d575c1 100644 (file)
@@ -14,6 +14,7 @@
  */
 
 #include "bliss_signature.h"
+#include "bliss_bitpacker.h"
 
 
 typedef struct private_bliss_signature_t private_bliss_signature_t;
@@ -47,44 +48,41 @@ struct private_bliss_signature_t {
         */
        uint16_t *c_indices;
 
-       /**
-        * Compressed encoding of BLISS signature
-        */
-       chunk_t encoding;
-
 };
 
 METHOD(bliss_signature_t, get_encoding, chunk_t,
        private_bliss_signature_t *this)
 {
-       if (this->encoding.len == 0)
+       bliss_bitpacker_t *packer;
+       uint16_t z2d_bits;
+       chunk_t encoding;
+       int i;
+
+       z2d_bits = this->set->z1_bits - this->set->d;
+
+       packer = bliss_bitpacker_create(this->set->n * this->set->z1_bits +
+                                                                       this->set->n * z2d_bits +
+                                                                       this->set->kappa * this->set->n_bits);
+
+       for (i = 0; i < this->set->n; i++)
        {
-               uint8_t *pos;
-               int i;
-
-               this->encoding = chunk_alloc(this->set->kappa * sizeof(uint16_t) +
-                                                                        this->set->n * sizeof(int16_t) +
-                                                                        this->set->n * sizeof(int8_t)),
-               pos = this->encoding.ptr;
-
-               for (i = 0; i < this->set->kappa; i++)
-               {
-                       htoun16(pos, this->c_indices[i]);
-                       pos += 2;
-               }
-               for (i = 0; i < this->set->n; i++)
-               {
-                       htoun16(pos, (uint16_t)this->z1[i]);
-                       pos += 2;
-               }
-               for (i = 0; i < this->set->n; i++)
-               {
-                       *pos++ = (uint8_t)this->z2d[i];
-               }
-               DBG2(DBG_LIB, "generated BLISS signature (%u bytes)", 
-                                          this->encoding.len);
+               packer->write_bits(packer, this->z1[i], this->set->z1_bits);
        }
-       return chunk_clone(this->encoding);
+       for (i = 0; i < this->set->n; i++)
+       {
+               packer->write_bits(packer, this->z2d[i], z2d_bits);
+       }
+       for (i = 0; i < this->set->kappa; i++)
+       {
+               packer->write_bits(packer, this->c_indices[i], this->set->n_bits);
+       }
+       encoding = packer->extract_buf(packer);
+
+       DBG2(DBG_LIB, "generated BLISS signature (%u bits encoded in %u bytes)",
+                                  packer->get_bits(packer), encoding.len);
+       packer->destroy(packer);
+
+       return encoding;
 }
 
 METHOD(bliss_signature_t, get_parameters, void,
@@ -102,7 +100,6 @@ METHOD(bliss_signature_t, destroy, void,
        free(this->z1);
        free(this->z2d);
        free(this->c_indices);
-       free(this->encoding.ptr);
        free(this);
 }
 
@@ -135,11 +132,16 @@ bliss_signature_t *bliss_signature_create_from_data(bliss_param_set_t *set,
                                                                                                        chunk_t encoding)
 {
        private_bliss_signature_t *this;
-       uint8_t *pos;
+       bliss_bitpacker_t *packer;
+       uint32_t z1_sign, z1_mask;
+       uint16_t z2d_sign, z2d_mask, value, z1_bits, z2d_bits;
        int i;
 
-       if (encoding.len != set->kappa * sizeof(uint16_t) +
-                                               set->n * sizeof(int16_t) + set->n * sizeof(int8_t))
+       z1_bits  = set->z1_bits;
+       z2d_bits = set->z1_bits - set->d;
+
+       if (8 * encoding.len < set->n * set->z1_bits + set->n * z2d_bits +
+                                                  set->kappa * set->n_bits)
        {
                DBG1(DBG_LIB, "incorrect BLISS signature size");
                return NULL;
@@ -155,25 +157,33 @@ bliss_signature_t *bliss_signature_create_from_data(bliss_param_set_t *set,
                .z1  = malloc(set->n * sizeof(int32_t)),
                .z2d = malloc(set->n * sizeof(int16_t)),
                .c_indices = malloc(set->n * sizeof(uint16_t)),
-               .encoding = chunk_clone(encoding),
        );
 
-       pos = encoding.ptr;
+       packer = bliss_bitpacker_create_from_data(encoding);
 
-       for (i = 0; i < set->kappa; i++)
+       z1_sign =   1 << (z1_bits - 1);
+       z1_mask = ((1 << (32 - z1_bits)) - 1) << z1_bits;
+
+       for (i = 0; i < set->n; i++)
        {
-               this->c_indices[i] = untoh16(pos);
-               pos += 2;
+               packer->read_bits(packer, &value, z1_bits);
+               this->z1[i] = value & z1_sign ? value | z1_mask : value;
        }
+
+       z2d_sign =   1 << (z2d_bits - 1);
+       z2d_mask = ((1 << (16 - z2d_bits)) - 1) << z2d_bits;
+
        for (i = 0; i < set->n; i++)
        {
-               this->z1[i] = (int16_t)untoh16(pos);
-               pos += 2;
+               packer->read_bits(packer, &value, z2d_bits);
+               this->z2d[i] = value & z2d_sign ? value | z2d_mask : value;
        }
-       for (i = 0; i < set->n; i++)
+       for (i = 0; i < set->kappa; i++)
        {
-               this->z2d[i] = (int8_t)(*pos++);
+               packer->read_bits(packer, &value, set->n_bits);
+               this->c_indices[i] = value;
        }
+       packer->destroy(packer);
 
        return &this->public;
 }
index d808bcf..d857b3a 100644 (file)
@@ -14,5 +14,6 @@
  */
 
 TEST_SUITE(bliss_fft_suite_create)
+TEST_SUITE(bliss_bitpacker_suite_create)
 TEST_SUITE(bliss_sign_suite_create)
 
diff --git a/src/libstrongswan/plugins/bliss/suites/test_bliss_bitpacker.c b/src/libstrongswan/plugins/bliss/suites/test_bliss_bitpacker.c
new file mode 100644 (file)
index 0000000..ad885e8
--- /dev/null
@@ -0,0 +1,108 @@
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * for more details.
+ */
+
+#include "test_suite.h"
+
+#include <bliss_bitpacker.h>
+
+static uint16_t bits[] = { 0, 1, 2, 3, 4, 7, 1, 14, 2, 29, 3, 28, 67};
+
+static chunk_t packed_bits = chunk_from_chars(0x6e, 0x71, 0xe1, 0x74,
+                                                                                         0x37, 0x21, 0x80);
+
+START_TEST(test_bliss_sign_bitpacker_write)
+{
+       chunk_t buf;
+       bliss_bitpacker_t *packer;
+       int i;
+
+       packer = bliss_bitpacker_create(49);
+
+       ck_assert(!packer->write_bits(packer, 0, 17));
+
+       for (i = 0; i < countof(bits); i++)
+       {
+               ck_assert(packer->write_bits(packer, bits[i], 1 + i/2));
+       }
+       buf = packer->extract_buf(packer);
+       ck_assert_int_eq(packer->get_bits(packer), 49);
+       ck_assert_chunk_eq(buf, packed_bits);
+
+       packer->destroy(packer);
+       free(buf.ptr);
+}
+END_TEST
+
+START_TEST(test_bliss_sign_bitpacker_read)
+{
+       uint16_t value;
+       bliss_bitpacker_t *packer;
+       int i;
+
+       packer = bliss_bitpacker_create_from_data(packed_bits);
+
+       ck_assert(!packer->read_bits(packer, &value, 17));
+
+       for (i = 0; i < countof(bits); i++)
+       {
+               ck_assert(packer->read_bits(packer, &value, 1 + i/2));
+               ck_assert_int_eq(value, bits[i]);
+       }
+       ck_assert(!packer->read_bits(packer, &value, 16));
+
+       packer->destroy(packer);
+}
+END_TEST
+
+START_TEST(test_bliss_sign_bitpacker_fail)
+{
+       bliss_bitpacker_t *packer;
+       uint16_t value;
+
+       packer = bliss_bitpacker_create(16);
+       ck_assert(!packer->write_bits(packer, 0, 17));
+       ck_assert( packer->write_bits(packer, 0x7f01, 15));
+       ck_assert(!packer->write_bits(packer, 3,  2));
+       packer->destroy(packer);
+
+       packer = bliss_bitpacker_create_from_data(chunk_from_chars(0x7f, 0x01));
+       ck_assert(!packer->read_bits(packer, &value, 17));
+       ck_assert( packer->read_bits(packer, &value, 15));
+       ck_assert(!packer->read_bits(packer, &value,  2));
+       packer->destroy(packer);
+}
+END_TEST
+
+Suite *bliss_bitpacker_suite_create()
+{
+       Suite *s;
+       TCase *tc;
+
+       s = suite_create("bliss_bitpacker");
+
+       tc = tcase_create("bitpacker_write");
+       tcase_add_test(tc, test_bliss_sign_bitpacker_write);
+       suite_add_tcase(s, tc);
+
+       tc = tcase_create("bitpacker_read");
+       tcase_add_test(tc, test_bliss_sign_bitpacker_read);
+       suite_add_tcase(s, tc);
+
+       tc = tcase_create("bitpacker_fail");
+       tcase_add_test(tc, test_bliss_sign_bitpacker_fail);
+       suite_add_tcase(s, tc);
+
+       return s;
+}