open-quantum-safe / liboqs Goto Github PK

I looked around for this code but can't seem to find it. Is it available online somewhere or do we need to get it from the authors?

How about changing Alice and Bob to Server and Client in the public API? I find the names a bit confusing, as I always need to double-check which one plays which role.

We need at least two macOS in Travis, otherwise we cannot catch bugs like #127 (current macOS install all dependencies to run the full project)

@tlepoint, could I ask you to edit the main README.md to add the appropriate reference for Kyber, as well as create an algorithm data sheet similar to the existing ones?

Need to clarify the licencing issues here. Linking against GPL code might not be ok:

https://www.gnu.org/licenses/old-licenses/gpl-2.0-faq.en.html#LinkingWithGPL

I've been told that the reported speed of the McBits implementation in liboqs is significantly slower than reported by the author. I'll try to find out what is going on and see if I can fix it. I'll keep track of my findings in this issue thread.

Now that we have autoconf it would be good if we could make configure-time options combined with preprocessor macros to enable or disable each algorithm.

There are a bunch of compiler warnings now being thrown when building after the autotools merge. @smashra can you take a look at them?

• Please make it so that the build fails when there are compiler warnings.
• Please fix the compiler warnings.

Currently the API for KEX makes it a bit difficult to implement a KEM transform like Fujisaki-Okamoto generically. This is because the message is generated randomly inside each implementation.

It could just be done on a per algorithm basis. This might be the best bet since we are concerned about benchmarking. In that case which of the current algorithms do we want to focus on?

One solution (to do it generically) that would involve a somewhat major architectural change is to implement a generic interface to asymmetric encryption then implement KEX in terms of that for the algorithms it applies to. The transform can then take a generic asymmetric encryption represented by a struct and return a new generic asymmetric encryption that is wrapped with for example Fujisaki-Okamoto.

I think #47 can be merged soon. I commented on a few issues in that pull request. If anyone else has comments that could be helpful.

Which config file is meant to be updated for Travis to succeed.
I see .travis.yml on my local disk.

Noticed while stats-testing the kex_rlwe_vscrypto code, where the algorithm returns a key whose length is not a whole number of bytes. If "true" key length is actually 8n+r bits (0<r<8) then kex_rlwe_vscrypto returns key_len = n+1, causing last byte to lose entropy.

Changing the liboqs API (for the whole of liboqs) so key_len is in bits, not bytes, would address this issue (for any algorithm) and is probably more mathematically correct in general than sticking with bytes. Downside would be coding complexity.

(edited to make clear this is a proposed liboqs API change, not just a kex_rlwe_vscrypto change)

make -j does not work probably because of concurrency.

[...]
clang -cc1as: error: unable to open output file 'objs/kex_sidh_cln16/fp_x64_asm.o': 'No such file or directory'
make: *** [objs/kex_sidh_cln16/fp_x64_asm.o] Error 1
make: *** Waiting for unfinished jobs....
[...]

Kyber has non-namespaced global symbols (see list below) and some of these conflict with Picnic (see @smashra's comment on pull request #120). These are not being caught by Travis due to issue #130.

Once #130 is fixed, these will need to be namespaced or made static.

0000000000000070 T barrett_reduce
0000000000000140 T bitrev_vector
00000000000002d0 T cbd
0000000000000100 T cmov
0000000000000090 T freeze
0000000000000fa0 T gen_matrix
0000000000001ad0 T indcpa_dec
00000000000014f0 T indcpa_enc
0000000000001140 T indcpa_keypair
0000000000000050 T montgomery_reduce
0000000000000190 T mul_coefficients
00000000000001d0 T ntt
0000000000000900 T poly_add
0000000000000380 T poly_compress
0000000000000470 T poly_decompress
0000000000000690 T poly_frombytes
0000000000000980 T poly_frommsg
00000000000007b0 T poly_getnoise
0000000000000870 T poly_invntt
0000000000000820 T poly_ntt
0000000000000940 T poly_sub
0000000000000570 T poly_tobytes
00000000000009d0 T poly_tomsg
0000000000000f40 T polyvec_add
0000000000000a60 T polyvec_compress
0000000000000bb0 T polyvec_decompress
0000000000000db0 T polyvec_frombytes
0000000000000e20 T polyvec_invntt
0000000000000df0 T polyvec_ntt
0000000000000e50 T polyvec_pointwise_acc
0000000000000d70 T polyvec_tobytes
00000000000000c0 T verify

NTRUEncrypt code is now in public domain, so we wouldn't have license issues in directly including it in the project: https://github.com/NTRUOpenSourceProject/NTRUEncrypt/blob/master/LICENSE

We should be zeroing memory that is used to store secret data in our free functions. It turns out that it is pretty difficult to do this in a way that is portable and guaranteed not to be optimized away. We could do something a bit ugly as show below (from libsodium):

#ifdef HAVE_WEAK_SYMBOLS
__attribute__ ((weak)) void
_sodium_memzero_as_a_weak_symbol_to_prevent_lto(void * const pnt, const size_t len)
{
    unsigned char *pnt_ = (unsigned char *) pnt;;
    size_t         i = (size_t) 0U;

    while (i < len) {
        pnt_[i++] = 0U;
    }
}
#endif

void
sodium_memzero(void * const pnt, const size_t len)
{
#ifdef _WIN32
    SecureZeroMemory(pnt, len);
#elif defined(HAVE_MEMSET_S)
    if (len > 0U && memset_s(pnt, (rsize_t) len, 0, (rsize_t) len) != 0) {
        abort(); /* LCOV_EXCL_LINE */
    }
#elif defined(HAVE_EXPLICIT_BZERO)
    explicit_bzero(pnt, len);
#elif HAVE_WEAK_SYMBOLS
    _sodium_memzero_as_a_weak_symbol_to_prevent_lto(pnt, len);
#else
    volatile unsigned char *volatile pnt_ =
        (volatile unsigned char * volatile) pnt;
    size_t i = (size_t) 0U;

    while (i < len) {
        pnt_[i++] = 0U;
    }
#endif
}

The functions return boolean values (1 on success, 0 on failure). However, I feel that an error code would be more appropriate (0 on success, -1 on failure).

In particular, it can keep the code of the caller cleaner. Consider the following:

if (alice_0(...)) {
  // send message, wait for reply
  if (alice_1(...)) {
    // do something with shared secret
  } else {
    // error handling alice_1
  }
} else {
  // error handling alice_0
}

vs.

if (alice_0(...)) {
  // error handling alice_0
}
// send message, wait for reply
if (alice_1(...)) {
  // error handling alice_1
}
// do something with shared secret

I prefer the latter as it doesn't trail off to the right and keeps the error handling close to the function that raised the error.

Now that NTRU is built-in, should we enable it by default?

@smashra When I do make on macOS (with clang), I get the following warnings

newhope.c:52:13: warning: unused function 'keygen' [-Wunused-function]
static void keygen(unsigned char *send, poly *sk, OQS_RAND *rand) {
            ^
newhope.c:72:13: warning: unused function 'sharedb' [-Wunused-function]
static void sharedb(unsigned char *sharedkey, unsigned char *send, const unsigned char *received, OQS_RAND *rand) {
            ^
newhope.c:104:13: warning: unused function 'shareda' [-Wunused-function]
static void shareda(unsigned char *sharedkey, const poly *sk, const unsigned char *received) {
            ^
3 warnings generated.

and

poly.c:89:13: warning: unused function 'poly_frombytes' [-Wunused-function]
static void poly_frombytes(poly *r, const unsigned char *a) {
            ^
poly.c:99:13: warning: unused function 'poly_tobytes' [-Wunused-function]
static void poly_tobytes(unsigned char *r, const poly *p) {
            ^
poly.c:139:13: warning: unused function 'poly_uniform' [-Wunused-function]
static void poly_uniform(poly *a, const unsigned char *seed) {
            ^
poly.c:164:13: warning: unused function 'poly_getnoise' [-Wunused-function]
static void poly_getnoise(poly *r, OQS_RAND *rand) {
            ^
poly.c:189:13: warning: unused function 'poly_pointwise' [-Wunused-function]
static void poly_pointwise(poly *r, const poly *a, const poly *b) {
            ^
poly.c:198:13: warning: unused function 'poly_add' [-Wunused-function]
static void poly_add(poly *r, const poly *a, const poly *b) {
            ^
poly.c:205:13: warning: unused function 'poly_ntt' [-Wunused-function]
static void poly_ntt(poly *r) {
            ^
poly.c:210:13: warning: unused function 'poly_invntt' [-Wunused-function]
static void poly_invntt(poly *r) {
            ^
poly.c:277:13: warning: unused function 'helprec' [-Wunused-function]
static void helprec(poly *c, const poly *v, OQS_RAND *oqs_rand) {
            ^
poly.c:307:13: warning: unused function 'rec' [-Wunused-function]
static void rec(unsigned char *key, const poly *v, const poly *c) {
            ^
10 warnings generated.

On my macOS, ./configure --enable-mcbits doesn't find libsodium, despite it having been installed with brew install libsodium. Can you add a --with-mcbits-dir similar to the --with-openssl-dir and --with-gmp-dir options?

seed not used in lwe_frodo; check to make sure other kex methods are done properly.

I'm getting an error compiling the master branch on Mac Sierra 10.12.4. There are three unused functions, and the -Wunused-function flag causes the compiler to create a warning, which is then treated as an error.

libtool: compile: gcc -DHAVE_CONFIG_H -I. -I../.. -I../../include -I. -g -std=gnu11 -Wno-unused-function -Werror -Wpedantic -Wall -Wextra -DCONSTANT_TIME -DAES_ENABLE_NI -g -O2 -MT libnewhope_la-newhope.lo -MD -MP -MF .deps/libnewhope_la-newhope.Tpo -c newhope.c -o libnewhope_la-newhope.o
newhope.c:53:13: error: unused function 'keygen' [-Werror,-Wunused-function]
static void keygen(unsigned char *send, poly *sk, OQS_RAND *rand) {
^
newhope.c:73:13: error: unused function 'sharedb' [-Werror,-Wunused-function]
static void sharedb(unsigned char *sharedkey, unsigned char *send,
^
newhope.c:106:13: error: unused function 'shareda' [-Werror,-Wunused-function]
static void shareda(unsigned char *sharedkey, const poly *sk,
^
3 errors generated.
make[2]: *** [libnewhope_la-newhope.lo] Error 1
make[1]: *** [all-recursive] Error 1
make: *** [all] Error 2

I was thinking of creating a test sub folder to put all the test files there.
For now we have:

src/kex/test_kex.c
src/rand/test_rand.c

Test functions are returning 1 for success and 0 for failure.
When for e.g.
make test
is run it shows failure because it expects 0 for success.

Running valgrind over text_kex currently returns this error (among other similar errors):

==21169== Invalid read of size 8
==21169==    at 0x41442E: oqs_sidh_cln16_fpcopy751 (fpx.c:38)
==21169==    by 0x41387D: oqs_sidh_cln16_ladder_3_pt (ec_isogeny.c:345)
==21169==    by 0x40C196: oqs_sidh_cln16_SecretAgreement_B (sidh_kex.c:352)
==21169==    by 0x40A20D: OQS_KEX_sidh_cln16_bob (kex_sidh_cln16.c:116)
==21169==    by 0x401E42: kex_test_correctness (test_kex.c:81)
==21169==    by 0x400E48: kex_test_correctness_wrapper (test_kex.c:152)
==21169==    by 0x400E48: main (test_kex.c:289)
==21169==  Address 0x5bff880 is 0 bytes after a block of size 48 alloc'd
==21169==    at 0x4C2BC0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21169==    by 0x40A1AA: OQS_KEX_sidh_cln16_bob (kex_sidh_cln16.c:100)
==21169==    by 0x401E42: kex_test_correctness (test_kex.c:81)
==21169==    by 0x400E48: kex_test_correctness_wrapper (test_kex.c:152)
==21169==    by 0x400E48: main (test_kex.c:289)

I investigated the problem and noticed the following:

A block of 48 bytes is malloc'd here, then passed here, then passed here (as the forth parameter), finally it is passed here.

In the function:

oqs_sidh_cln16_fpcopy751(oqs_sidh_cln16_felm_t a, oqs_sidh_cln16_felm_t c)

It is treated as if it has type oqs_sidh_cln16_felm_t which is defined:

typedef digit_t oqs_sidh_cln16_felm_t[NWORDS_FIELD];.

Looking at this section it seems that the type should be of size 96 bytes (4 * 24 or 8 * 12).

Is the original memory allocation here incorrect?

In light of #53, I think it would be interesting to switch from astyle to clang-format. Clang-format is both a library and a stand-alone tool aiming at automatically reformatting C sources files, and continus to be developed while astyle has not been updated since December 2014.

Need to have new build system which can support building multiple architectures.

Hi,
I am currently writing a cryptography library in C++: https://github.com/Steppenwolfe65/CEX
and I wonder if I can get your opinions on a couple of things.
You have collected a number of RingLWE implementations (thanks for that), but do you have a preference for one implementation over another?
Are there functions or features of these implementations that you would like to see combined in an ideal implementation? The library I am writing is targeting application developers, so multi-threading and SIMD parallelization are high priority, is one version better suited for this than the others?
I think the most important criteria though is, do you feel one version is more secure than the others, this includes upwardly flexible parameter sets, and the application of attack vector counter-measures like constant time functions.
I looked at Supersingular Isogeny a few years ago, but could only find the one 'cython' implementation on git.. it's an interesting idea, and could be made quite fast, but I wonder if it has had enough study. The same goes for the McBits version of McEliece.. but again, I would be really interested to know what you think about this..
Anyways, thanks so much for all this great work, it is certain to make my job a lot easier.

Regards,
John

We don't need all the keys printed out in the travis test logs.

When I try to compile on mac (where openssl is not automatically available), I get

Making all in src/sig_picnic_msr
  CC       libpicnicmsr_la-LowMC.lo
LowMC.c:30:10: fatal error: 'openssl/sha.h' file not found
#include <openssl/sha.h>
         ^
1 error generated.
make[2]: *** [libpicnicmsr_la-LowMC.lo] Error 1
make[1]: *** [all-recursive] Error 1
make: *** [all] Error 2

Questions:

• Where is the PR with the merge with LowMC?
• Can we only enable LowMC is openssl is enabled?
• Why hasn't it been caught by Travis?

I suggest the FFT to be decoupled from kex_rlwe_bcns15 (and even from the name "rlwe") itself, as it could be used in implementations of different primitives (several kex, signatures, encryption, etc.).

https://scan.coverity.com/travis_ci

Building with --enable-ntru fails on my macOS. More specifically, the liboqs build completes, but then trying to run ./test_kex fails with the following error:

dyld: Library not loaded: /usr/local/lib/libntruencrypt.0.dylib
  Referenced from: /Users/dstebila/Desktop/liboqs/./test_kex
  Reason: image not found

Can you change the build process so it statically links in libntruencrypt.a at compile time rather than dynamically linking in libntruencrypt.dylib at runtime?

Originally commented by @tlepoint

Why do we have a fail on macOS not caught by Travis?

./test_kex
dyld: Library not loaded: /usr/local/lib/libntruencrypt.0.dylib
  Referenced from: /Users/travis/build/open-quantum-safe/liboqs/./test_kex
  Reason: image not found
make: *** [test] Trace/BPT trap: 5

Before autotools merge, these was a nice Makefile output. @smashra, could we add

m4_ifdef([AM_SILENT_RULES], [AM_SILENT_RULES([yes])])

to configure.ac?

@smashra When I run

make distclean

I get the following errors

Makefile:743: src/crypto/aes/.deps/test_aes-test_aes.Po: No such file or directory
Makefile:744: src/crypto/rand/.deps/test_rand-test_rand.Po: No such file or directory
Makefile:745: src/kex/.deps/test_kex-test_kex.Po: No such file or directory
make[1]: *** No rule to make target `src/kex/.deps/test_kex-test_kex.Po'.  Stop.
make: *** [distclean-recursive] Error 1

I would suggest that

make

only builds the library, and that

make check

(introduced in #11) builds and runs the tests. What do you think?

Hi Alex, I was thinking that it might be good to have a PRNG that is based on the new AES-NI code that you've added, since that might be faster for large amounts of PRNG expansion than the existing ChaCha20 code when AES-NI is available. Would you have a chance to try that out?

Can we rename the various ./configure options to match our naming scheme?

• --enable-mcbits => --enable-kex-code-mcbits
• --enable-ntru => --enable-kex-ntru
• --enable-sidhiqc => --enable-kex-sidh-iqc-ref

None of the algorithms appear to actually use this and it made it slightly irritating to wrap in C++.

My suggestion would be simply to drop this parameter, which would make the API marginally simpler to understand

Because libm4ri-dev does not exist, introduced in 3aaa26aacee5e332a517f2de6436fe1c665e0785

@smashra It is important to only do PR and to not directly commit to master, otherwise we do not catch this.
@dstebila: is it possible to forbid commits to master and force to go through PR?

perhaps i didn't configure liboqs with the correct options, but my makefile links a bunch of the headers into include/oqs, but they're soft links and thus useless when naively copying them into some place more useful (like /usr/local/include/oqs). also, not all the headers are present, so not all functionality of liboqs is exposed...

perhaps there's a better solution, have automake take care of copying all the header files into /usr/local/include when doing the make install:
http://stackoverflow.com/questions/32148172/move-all-header-files-to-usr-local-include-target
this option seems appropriate, as it wouldn't require any extra steps on the end users part to start working with the library in another C/C++ project.

here are the changes to the Makefile.am which do this, but you may want to add/modify. (note that it puts it in /usr/local/include/liboqs, though, there should be a way to do it in include/oqs if desired.)

pkginclude_HEADERS = src/common/common.h \
                     src/crypto/aes/aes.h \
                     src/crypto/sha3/sha3.h \
                     src/kex/kex.h \
                     src/crypto/rand/rand.h \
                     src/crypto/rand_urandom_chacha20/rand_urandom_chacha20.h \
                     src/crypto/rand_urandom_aesctr/rand_urandom_aesctr.h \
                     src/kex_rlwe_newhope/kex_rlwe_newhope.h \
                     src/kex_rlwe_msrln16/kex_rlwe_msrln16.h \
                     src/kex_lwe_frodo/kex_lwe_frodo.h \
                     src/kex_rlwe_bcns15/kex_rlwe_bcns15.h \
                     src/kex_sidh_cln16/kex_sidh_cln16.h

if USE_MCBITS
pkginclude_HEADERS += src/kex_code_mcbits/kex_code_mcbits.h
endif
if USE_NTRU
pkginclude_HEADERS += src/kex_ntru/kex_ntru.h
endif
if USE_SIDH_IQC
pkginclude_HEADERS += src/kex_sidh_iqc_ref/kex_sidh_iqc_ref.h
endif

Some things in liboqs use standard cryptographic algorithms. We should eventually have a common mechanism for these, either (a) our own API and collected implementations, or (b) linking against an existing library, e.g. OpenSSL or libnacl.

Algorithms needed:

• ChaCha20: in rand_urandom_chacha20
• AES-128 or AES-256: in kex_lwe_frodo branch
• SHAKE/SHA-3: in kex_rlwe_newhope

I was talking with Dan Bernstein at Real World Crypto, and he had some suggestions about our KEX API, some of which carry forward into the design of a signature API.

Some of his comments (my wording) were:

1. the API should not require malloc's (in other words, callers pass in byte arrays of appropriate size, rather than the callee allocating it)
2. make the API as close to Supercop / NIST as possible to make it easier for people to submit
3. having the OQS_KEX or OQS_SIGN data structure is an extra hurdle for people wanting to submit
4. avoid passing the OQS_KEX or OQS_SIGN data structures down multiple levels of the stack
5. every input should be byte strings (i.e., don't use void * for private keys)
6. don't pass a random number generator down, instead rely on a global random number generator function like random_bytes
7. don't have functions representing "families of schemes" parameterized by different values, instead have each function correspond to one scheme

My opinions:

1. okay
2. okay
3. I would like to have the OQS_KEX or OQS_SIGN data structure for a few reasons: still maintaining a generic high level API that is parameterized by the scheme, and to include metadata such as key sizes and security levels
4. okay
5. For ephemeral/passive key exchange where the private key is only used once, I think void * is okay, but for schemes with long-term keys, each scheme would have to provide an explicit serialization/deserialization that the caller has to make use of; so I think for signatures byte strings is simpler (and matches Supercop / NIST)
6. It's not clear to me how to do transforms based on determinism for KEMs if you don't pass an RNG down. But then again it's also not clear to me how to do such transforms even if you do pass an RNG down. Thoughts?
7. Probably would simplify the API.

https://www.codacy.com (C is a community supported language)

We should add the software of the KEM based on NTRU by Hülsing, Rijneveld, Schanck, and Schwabe. To appear at CHES 2017.

In addition to #128, current travis builds that are flagged as passing output what is below, and therefore should fail.

Code contains the following non-namespaced global symbols; see https://github.com/open-quantum-safe/liboqs/wiki/Coding-conventions for function naming conventions.
00000000000000c0 T allocateProof
0000000000000060 T allocateRandomTape
0000000000000130 T allocateSignature
0000000000000190 T allocateUnruhPermutations
0000000000000000 T allocateView
00000000000003b0 T cleanup_EVP
0000000000000520 T Commit
0000000000002450 T computeRoundKey
0000000000001460 T computeRoundKey2
0000000000000f50 T deserializeSignature
0000000000000110 T freeProof
00000000000000a0 T freeRandomTape
0000000000000160 T freeSignature
00000000000001c0 T freeUnruhPermutations
0000000000000040 T freeView
0000000000000660 T G
00000000000005c0 T generateAesIv
00000000000002b0 T getAllRandomness
0000000000000230 T getBit
00000000000001e0 T getBitFromWordArray
00000000000008b0 T getChallenge
0000000000000280 T getRandom32
0000000000000950 T H3
0000000000000390 T init_EVP
0000000000002320 T mpc_AND
00000000000011c0 T mpc_AND_verify
0000000000002660 T mpc_LowMC
0000000000002250 T mpc_multiplyWithKeyMatrix
0000000000001390 T mpc_multiplyWithKeyMatrix2
0000000000002130 T mpc_multiplyWithMatrix
0000000000001280 T mpc_multiplyWithMatrix2
0000000000002460 T mpc_substitution
0000000000001470 T mpc_substitution2
00000000000003e0 T mpc_xor
00000000000004e0 T mpc_xor2
0000000000000480 T mpc_xor4_2
0000000000000420 T mpc_xor4_3
0000000000000290 T numBytes
00000000000008f0 T print_hex
0000000000000bd0 T prove
0000000000002890 T random_bytes_default_openssl
0000000000002850 T runMPC
0000000000000d30 T serializeSignature
0000000000000250 T setBit
0000000000000200 T setBitInWordArray
0000000000000850 T setChallenge
00000000000028b0 T sign
0000000000001aa0 T verify
0000000000001680 T verifyLowMC
0000000000001840 T verifyProof
0000000000000620 T freeLookupTables
0000000000000610 T freeRoundConstants
0000000000000650 T LowMCEnc
0000000000000230 T readLookupTables
0000000000000130 T readRoundConstants
0000000000000000 T get_transform
0000000000000040 T picnic_get_param_name
00000000000001e0 T picnic_init
0000000000000290 T picnic_keygen
0000000000000060 T picnicParamsToLowMCParams
0000000000000b70 T picnic_read_private_key
0000000000000a90 T picnic_read_public_key
0000000000000250 T picnic_shutdown
0000000000000530 T picnic_sign
0000000000000760 T picnic_signature_size
0000000000000bf0 T picnic_validate_keypair
0000000000000830 T picnic_verify
0000000000000b00 T picnic_write_private_key
0000000000000a20 T picnic_write_public_key

Hi Dr. Stebila,

I asked my question/possible bug in the code here initially to see maybe if I am wrong or not. There at crypto.stackexchange they suggested the new repository might have the issue fixed but it is not. It would be great if you could look at my question and see if I am missing a point or not. In the question, there is a link to SageMath code to verify my claim.

Thank you,
Amir