tbuktu / libntru Goto Github PK

View Code? Open in Web Editor NEW

198.0 198.0 59.0 653 KB

C Implementation of NTRUEncrypt

License: Other

Makefile 0.06% C 81.18% Perl 18.76%

libntru's People

Contributors

Stargazers

Watchers

libntru's Issues

What about the safety of particular uses of NTRU, and what about the safety of this library?

Hi!

What about the safety of particular uses of NTRU, and what about the safety of this library?

So that a non-cryptographer software developer can use this library and know he's doing it right.

For instance, Bernstein brings up examples of unsecure NTRU use for instance here https://ntruprime.cr.yp.to/ntruprime-20160511.pdf .

What about it, is there any guidance for how to use your libntru library safely?

Thanks,
Mlmikael

What about the safety of particular uses of NTRU, and what about the safety of this library?

Hi!

Running test on mac-os

I am getting segfaults with the current master branch on mac OS. Somehow the function ptr is not reference properly...

Platform:

Apple LLVM version 8.1.0 (clang-802.0.42)
Target: x86_64-apple-darwin16.6.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

Here is some debugging information:

There is a running process, kill it and restart?: [Y/n] yes
Process 25413 exited with status = 9 (0x00000009)
Process 25418 launched: './testnoham' (x86_64)
Running tests...
test_ntruprime_inv_int ✓
test_ntruprime_inv_poly ✓
testnoham was compiled with optimization - stepping may behave oddly; variables may not be available.
Process 25418 stopped

thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
frame #0: 0x000000010000495a testnoham`test_mult_int at test_poly.c:82 [opt]
79 NtruIntPoly a1 = {11, {-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1}};
80 NtruIntPoly b1 = {11, {14, 11, 26, 24, 14, 16, 30, 7, 25, 6, 19}};
81 NtruIntPoly c1;
-> 82 ntru_mult_int(&a1, &b1, &c1, 32-1);
83 NtruIntPoly c1_exp = {11, {3, 25, -10, 21, 10, 7, 6, 7, 5, 29, -7}};
84 valid &= equals_poly_mod(&c1_exp, &c1, 32);
85
(lldb) print ntru_mult_int
(uint8_t (*)(NtruIntPoly *, NtruIntPoly *, NtruIntPoly *, uint16_t)) $0 = 0x0000000000000000
(lldb) print &ntru_mult_int
(uint8_t (**)(NtruIntPoly *, NtruIntPoly *, NtruIntPoly *, uint16_t)) $1 = 0x000000010000a328
(lldb) print ntru_mult_int
(uint8_t ()(NtruIntPoly *, NtruIntPoly *, NtruIntPoly *, uint16_t)) $2 = 0x0000000000000000
(lldb) step
Process 25418 stopped
thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
frame #0: 0x0000000000000000
error: memory read failed for 0x0
(lldb) bt
thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
- frame #0: 0x0000000000000000
  frame #1: 0x000000010000497a testnohamtest_mult_int at test_poly.c:82 [opt] frame #2: 0x00000001000059b1 testnohamtest_poly at test_poly.c:313 [opt]
  frame #3: 0x00000001000044f5 testnohammain(argc=<unavailable>, argv=<unavailable>) at test.c:16 [opt] frame #4: 0x00007fffad4de235 libdyld.dylibstart + 1
  frame #5: 0x00007fffad4de235 libdyld.dylib`start + 1
  (lldb)

It is as if the function ptr are not allocated: ntru_mult_int

I know for sure, it is hitting:

#elif __SSSE3__ ntru_mult_int = &ntru_mult_int_sse; ntru_mult_tern = ntru_mult_tern_sse; ntru_to_arr = ntru_to_arr_sse; ntru_mod_mask = ntru_mod_sse;

in poly.c, however, not sure what is going on :( Any ideas?

undefined symbols

after i comipled successfully. i executed hybrid and i get an undefined symbol error: EES401EP2. what i doing wrong?

test_key() stack date currupted

char pub_arr[ntru_enc_len(params.N, params.q)]; 
...
char priv_arr[ntru_priv_len(params.df1, params.df2, params.df3)];

//change to:

char pub_arr[ntru_enc_len(params.N, params.q) + 2 * sizeof uint16_t]; // see ntru_export_pub
...
char priv_arr[ntru_priv_len(params.df1, params.df2, params.df3) + 2 * sizeof uint16_t + 1]; // see ntru_export_priv

Need to implement

can u please help how can i implement this encryption and decryption algorithm in socket programming in linux, as i want to encrypt and decrypt the messages between server and client.

Does this library implement a padding algorithm?

Hello,

Please pardon my naive question. I would like to know whether this library provides a padding algorithm.
I read this function: ntru.c:204 and this issue but I'm not sure whether I understood correctly.

If it does not implement a padding algorithm, does the encrypted output remains safe?
(I only encrypt a symmetric key as explained in the issue)

Thanks.

error: initializer element is not constant

Trying to test it out by compiling the sample code, but I get an error:

test.c:4:8: error: initializer element is not constant
 struct NtruEncParams params = NTRU_DEFAULT_PARAMS_128_BITS; /*see section "Parameter Sets" below*/
        ^
test.c:7:1: error: expected identifier or ‘(’ before ‘if’
 if (ntru_rand_init(&rand_ctx_def, &rng_def) != NTRU_SUCCESS)
 ^
test.c:10:1: error: expected identifier or ‘(’ before ‘if’
 if (ntru_gen_key_pair(&params, &kp, &rand_ctx_def) != NTRU_SUCCESS)
 ^

the sample code is

#include "ntru.h"

/* key generation */
struct NtruEncParams params = NTRU_DEFAULT_PARAMS_128_BITS; /*see section "Parameter Sets" below*/
NtruRandGen rng_def = NTRU_RNG_DEFAULT;
NtruRandContext rand_ctx_def;
if (ntru_rand_init(&rand_ctx_def, &rng_def) != NTRU_SUCCESS)
    printf("rng fail\n");
NtruEncKeyPair kp;
if (ntru_gen_key_pair(&params, &kp, &rand_ctx_def) != NTRU_SUCCESS)
    printf("keygen fail\n");

Any idea of what to do?

rare hang in both noham and ham versions

I've added a "test" that attempts to run a billion iterations of encryption followed by decryption:

https://gist.github.com/bhuff36/788646b453a1dc4abcf4ee03facda3c8

Every few iterations, it prints the remaining number of iterations.

After a while this is observed to "hang", meaning that the library gets "stuck" in one of the encryption or decryption calls, while consuming all available (single-threaded) CPU time.

This happens for both noham and ham versions.

I believe this is indicative of a bug in libntru.

The host platform I attempted to run libntru on is x86_64.

MacOS: test crashes with SegFault

MacOS 10.15.6, Xcode-11.6. Current master.

$ ./testnoham 
Running tests...
  test_ntruprime_inv_int   ✓
  test_ntruprime_inv_poly  ✓
Segmentation fault: 11

$ lldb ./testnoham
(lldb) target create "./testnoham"
Current executable set to '/Users/ur20980/src/libntru/testnoham' (x86_64).
(lldb) run
error: process exited with status -1 (Error 1)
(lldb) bt
error: invalid thread
(lldb) list
   13  	int main(int argc, char** argv) {
   14  	    printf("Running tests...\n");
   15  	    ntru_set_optimized_impl();   /* normally called by the functions in ntru.h */
   16  	    uint8_t pass = test_poly();
   17  	    pass &= test_ntruprime();
   18  	    pass &= test_ntru();
   19  	    pass &= test_idxgen();
   20  	    pass &= test_bitstring();
   21  	    pass &= test_key();
   22  	    pass &= test_hash();
(lldb) ^D
$

provide install rules

I could make a pull request, but I don't even know which headers are public.

equals_params()

I think I'm experiencing undesired behavior with tests/test_util.c on Windows XP. In equals_params(), two function pointers are being compared. The pointers are not equal when compared even if the DLL function pointer and the non-DLL function pointer refer to the same function.

Please see http://www-01.ibm.com/support/knowledgecenter/SSLTBW_1.12.0/com.ibm.zos.r12.cbcpx01/fpc.htm%23fpc.

Something unrelated. Should ntru_params_from_priv_key() copy the sparse field?

Thanks.

Plan to implement NTRUSign?

Hi!

What about API:s for making NTRU-based signatures?

It's in the Java variant currently but not here.

Thanks,
Mlmikael

Buffer overrun in ntru_to_arr_32 and ntru_to_arr_64

There is a buffer overrun in the ntru_to_arr_32() and ntru_to_arr_64() functions in poly.c. Both functions operate on the input buffer in 4-byte or 8-byte increments, but the buffer may not be a multiple of this length. For example, in test_arr() function we allocate a buffer 'a' of length 1495 and pass it to ntru_to_arr_32(), resulting in a write of 1496 bytes to this 1495 buffer.

Interestingly enough, the documentation for ntru_to_arr_32() explicitly claims that the buffer does NOT need any padding: "No extra room is needed at the end." This problem is somewhat mitigated on SSE3 builds since ntru_to_arr() which most of the library uses will call the SSE3 version, but the tests and at least ntru_export_pub() directly rely on the broken version. The SSE3 version of the function (ntru_to_arr_sse_2048()) does not have the problem (as far as I can tell).

FYI, I'm building in Microsoft Visual Studio which doesn't support C99's variable length arrays (I also have SSE3 turned off), so I changed all VLA allocations to _alloca() calls. In debug mode Visual Studio will warn of overruns on memory allocated by _alloca(), which is how I found this.

NTRU Prime implementation?

__builtin / OS X / gcc 4.2.1

The __builtin_cpu_supports function is not defined.

cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/hash.c -o src/hash.o
src/hash.c:83:9: error: use of unknown builtin '__builtin_cpu_supports' [-Wimplicit-function-declaration]
    if (__builtin_cpu_supports("ssse3") || __builtin_cpu_supports("avx2")) {

https://gcc.gnu.org/onlinedocs/gcc-4.9.2/gcc/X86-Built-in-Functions.html

Python wrapper

Would be useful for NTRUEncrypt being integrated to other projects.

Identical Code Returning NTRU_ERR_INVALID_PARAM on iOS

I have the identical code, shown below, successfully encrypting messages on macOS, yet return NTRU_ERR_INVALID_PARAMS on iOS.

struct NtruEncParams params = NTRU_DEFAULT_PARAMS_256_BITS;
struct sockaddr_in si_other;
int s = 0;
int slen = sizeof(si_other);
char buf[BUFLEN];
char contact_oid[OID_SIZE] = { '\0' };

char message[BUFLEN * 4] = { '\0' };
char contact_public_key_string[BUFLEN] = { '\0' };
uint8_t digest[DIGEST_LENGTH] = { '\0' };
uint8_t pub_arr[ntru_pub_len(&params)];
char **tokens = NULL;
NtruRandGen rng_def = NTRU_RNG_DEFAULT;
NtruRandContext rand_ctx_def;

/* Hash password with SHA256 */
ntru_sha256(password, strlen(password), digest);

db_man_get_contacts_oid(contact_db_id, contact_oid);

if (!(strlen(contact_oid) > 0))
{
    fprintf(stderr, "That contact db_id does not exist in the "\
            "database!\n\n");
    return;
}

db_man_get_contacts_public_key(contact_db_id,
                               contact_public_key_string);

tokens = str_split(contact_public_key_string, '-');

if (tokens)
{
    int i;
    for (i = 0; *(tokens + i); i++)
    {
        free(*(tokens + i));
        pub_arr[i] = atoi( *(tokens + i));
    }
    printf("\n");
    free(tokens);
    
    /* import key from uint8_t array */
    NtruEncPubKey pub;
    ntru_import_pub(pub_arr, &pub);
    
    /* encryption */
    if (ntru_rand_init(&rand_ctx_def, &rng_def) != NTRU_SUCCESS)
    {
        printf("rng fail\n");
        return;
    }
    
    printf("Enc length: %u", ntru_enc_len(&params));
    uint8_t enc[ntru_enc_len(&params)];
    int err_code = 0;
    
    if ((err_code = ntru_encrypt(usr_msg, strlen(usr_msg), &pub, &params,
                     &rand_ctx_def, enc)) != NTRU_SUCCESS)
    {
        printf("encrypt fail: %u\n", err_code);
        return;
    }

Padding and CCA concerns [question]

Hello!
Please pardon if stupid/naive question, but

should I be concerned with padding for non-hybrid encryption of (<200 bytes) plaintexts, or is the padding as implemented in this library "good enough" to take care of it ?

Plaintexts are low entropy, and distinguish-ability is a concern.

Do I understand correctly that if malleability/CCA/etc is a concern, a MAC should be used (ideally in Encrypt-then-MAC manner) in order to avoid trouble ?

FreeBSD

Please add the following to src/poly.c.

#ifdef __FreeBSD__
#include <sys/endian.h>
#endif

thoughts on the API

Maybe I'm missing something, but afais the maximum message size for ntru_encrypt() is ntru_max_msg_len(params).

I don't see a note on that in the function documentation
I think it would make sense to provide a more high-level approach for string encryption/decryption without worrying about that restriction. My current approach looks something like this:

uint8_t ntru_encrypt_str(uint8_t *msg,
        size_t msg_len,
        NtruEncPubKey *pub,
        NtruEncParams *params,
        uint8_t (*rng)(uint8_t[], uint16_t, NtruRandContext*),
        uint8_t *enc,
        size_t *enc_len)
{
    uint8_t *enc_ptr = enc;

    *enc_len = 0;

    for (size_t i = 0; i < msg_len; i += ntru_max_msg_len(params)) {
        uint8_t enc_tmp[ntru_enc_len(params)];
        uint8_t ret;

        if (i + ntru_max_msg_len(params) > msg_len)
            ret = ntru_encrypt(msg + i,
                    msg_len - i,
                    pub, params, rng, enc_tmp);
        else
            ret = ntru_encrypt(msg + i,
                    ntru_max_msg_len(params),
                    pub, params, rng, enc_tmp);

        if (ret != NTRU_SUCCESS)
            return ret;

        *enc_len += (uint64_t)ntru_enc_len(params);
        memcpy(enc_ptr, enc_tmp, ntru_enc_len(params));
        enc_ptr += ntru_enc_len(params);
    }

    return NTRU_SUCCESS;
}


uint8_t ntru_decrypt_str(uint8_t *enc,
        size_t enc_len,
        NtruEncKeyPair *kp,
        NtruEncParams *params,
        uint8_t *dec,
        size_t *dec_len)
{
    uint8_t *dec_ptr = dec;

    *dec_len = 0;

    for (size_t i = 0; i < enc_len; i += ntru_enc_len(params)) {
        uint8_t dec_tmp[ntru_max_msg_len(params)];
        uint8_t ret;
        uint16_t dec_len_tmp = 0;

        ret = ntru_decrypt(enc + i,
                kp,
                params,
                dec_tmp,
                &dec_len_tmp);

        if (ret != NTRU_SUCCESS)
            return ret;

        *dec_len += (size_t)dec_len_tmp;
        memcpy(dec_ptr, dec_tmp, dec_len_tmp);
        dec_ptr += ntru_max_msg_len(params);
    }

    return NTRU_SUCCESS;
}

Memory leak

src/ntru.c line 363 should read:

    if (rand_state != NULL)
        free(rand_state);

ntru_rand_wincrypt_init()

The hCryptProv object is not deallocated before the second return.

Question About the usage code in the readme file

I ran the usage code in the readme file of the project, but the program reported an error. Among the things I can’t understand are:

‘’‘
uint8_t enc[ntru_enc_len(&params)];

uint8_t dec[ntru_max_msg_len(&params)];
’‘’

Arrays in C language cannot be declared with variables. Is this statement wrong or is my understanding wrong?

Possible memory leak in ntru_invert()

In the following block of code if anything else than 'b' fails to be malloc()'d the function returns without freeing anything else.

int ntru_invert(NtruIntPoly *a, int q, NtruIntPoly *Fq) {
    int invertible;
    int i;
    int N = a->N;
    int k = 0;
    NtruIntPoly *b = ntru_zero_poly(N+1);
    if (!b)
        return NTRU_ERR_OUT_OF_MEMORY;
    b->coeffs[0] = 1;
    NtruIntPoly *c = ntru_zero_poly(N+1);
    if (!c)
        return NTRU_ERR_OUT_OF_MEMORY;
    NtruIntPoly *f = ntru_clone(a);
    if (!f)
        return NTRU_ERR_OUT_OF_MEMORY;
    f->coeffs[f->N] = 0;   /* index N wasn't cloned */
    f->N++;   /* add one coefficient for a total of N+1 */
    ntru_mod2(f);
    /* set g(x) = x^N − 1 */
    NtruIntPoly *g = ntru_zero_poly(N+1);
    if (!g)
        return NTRU_ERR_OUT_OF_MEMORY;
....

should be

int ntru_invert(NtruIntPoly *a, int q, NtruIntPoly *Fq) {
    int invertible;
    int i;
    int N = a->N;
    int k = 0;
    NtruIntPoly *b = ntru_zero_poly(N+1);
    if (!b)
        return NTRU_ERR_OUT_OF_MEMORY;
    b->coeffs[0] = 1;
    NtruIntPoly *c = ntru_zero_poly(N+1);
    if (!c)
    {
        free(b);
        return NTRU_ERR_OUT_OF_MEMORY;
    }
    NtruIntPoly *f = ntru_clone(a);
    if (!f)
    {
        free(b);
        free(c);
        return NTRU_ERR_OUT_OF_MEMORY;
    }
    f->coeffs[f->N] = 0;   /* index N wasn't cloned */
    f->N++;   /* add one coefficient for a total of N+1 */
    ntru_mod2(f);
    /* set g(x) = x^N − 1 */
    NtruIntPoly *g = ntru_zero_poly(N+1);
    if (!g)
    {
        free(b);
        free(c);
        free(f);
        return NTRU_ERR_OUT_OF_MEMORY;
    }
....

OS/2

Please include a Makefile.os2 file in your distribution. The process creates a DLL, however, we do not yet have a complete test execution. Credit to Elbert Pol, please.

Makefile.os2:

CC=gcc
AS=$(CC) -c
OPTFLAGS=-O2
bench: OPTFLAGS=-O3 -march=native
CFLAGS?=-g $(OPTFLAGS)
CFLAGS+=-Wall -Wextra -Wno-unused-parameter
ifeq ($(SSE), yes)
    CFLAGS+=-mssse3
endif
LIBS+=-lrt
SRCDIR=src
TESTDIR=tests
LIB_OBJS=bitstring.o encparams.o hash.o idxgen.o key.o mgf.o ntru.o poly.o rand.o arith.o sha1.o sha2.o
ifeq ($(SSE), yes)
    LIB_OBJS+=sha1-mb-x86_64.o sha256-mb-x86_64.o
endif
TEST_OBJS=test_bitstring.o test_hash.o test_idxgen.o test_key.o test_ntru.o test.o test_poly.o test_util.o
VERSION=0.3
INST_PFX=%PROGRAMFILES%
INST_LIBDIR=$(INST_PFX)\libntru
INST_INCLUDE=$(INST_PFX)\libntru\include
INST_DOCDIR=$(INST_PFX)\libntru
INST_HEADERS=ntru.h types.h key.h encparams.h hash.h rand.h err.h
PERL=c:\mingw\msys\1.0\bin\perl
PERLASM_SCHEME=coff

LIB_OBJS_PATHS=$(patsubst %,$(SRCDIR)/%,$(LIB_OBJS))
TEST_OBJS_PATHS=$(patsubst %,$(TESTDIR)/%,$(TEST_OBJS))
DIST_NAME=libntru-$(VERSION)
MAKEFILENAME=$(lastword $(MAKEFILE_LIST))

.PHONY: all lib install dist test clean distclean

all: lib

lib: $(LIB_OBJS_PATHS)
    $(CC) $(CFLAGS) $(CPPFLAGS) -shared -o libntru.dll $(LIB_OBJS_PATHS)

install: lib
    mkdir "$(DESTDIR)$(INST_PFX)"
    mkdir "$(DESTDIR)$(INST_LIBDIR)"
    mkdir "$(DESTDIR)$(INST_INCLUDE)"
    mkdir "$(DESTDIR)$(INST_DOCDIR)"
    copy libntru.dll "$(DESTDIR)$(INST_LIBDIR)"
    copy README.md "$(DESTDIR)$(INST_DOCDIR)"
    for %%h in ($(INST_HEADERS)) do \
        copy $(SRCDIR)\%%h "$(INST_INCLUDE)"

uninstall:
    rm -f "$(DESTDIR)$(INST_LIBDIR)\libntru.dll"
    rm -f "$(DESTDIR)$(INST_DOCDIR)\README.md"
    for %%h in ($(DESTDIR)$(INST_HEADERS)) do \
        rm -f "$(DESTDIR)$(INST_INCLUDE)\%%h"
    rmdir "$(DESTDIR)$(INST_INCLUDE)"
    rmdir "$(DESTDIR)$(INST_LIBDIR)"
    rmdir "$(DESTDIR)$(INST_DOCDIR)"

dist:
    rm -f $(DIST_NAME)\$(SRCDIR)\*.c
    rm -f $(DIST_NAME)\$(SRCDIR)\*.h
    rmdir $(DIST_NAME)\$(SRCDIR)
    rm -f $(DIST_NAME)\$(TESTDIR)\*.c
    rm -f $(DIST_NAME)\$(TESTDIR)\*.h
    rmdir $(DIST_NAME)\$(TESTDIR)
    rm -f /q $(DIST_NAME)\*.*
    rmdir $(DIST_NAME)
    mkdir $(DIST_NAME)
    mkdir $(DIST_NAME)\$(SRCDIR)
    mkdir $(DIST_NAME)\$(TESTDIR)
    copy Makefile $(DIST_NAME)
    copy Makefile.win $(DIST_NAME)
    copy Makefile.osx $(DIST_NAME)
    copy README.md $(DIST_NAME)
    copy LICENSE $(DIST_NAME)
    copy PATENTS $(DIST_NAME)
    copy $(SRCDIR)\*.c $(DIST_NAME)\$(SRCDIR)
    copy $(SRCDIR)\*.h $(DIST_NAME)\$(SRCDIR)
    copy $(TESTDIR)\*.c $(DIST_NAME)\$(TESTDIR)
    copy $(TESTDIR)\*.h $(DIST_NAME)\$(TESTDIR)

test:
    $(MAKE) -f $(MAKEFILENAME) testnoham
    @echo.
    @echo Testing patent-reduced build
    testnoham.exe
    $(MAKE) -f $(MAKEFILENAME) testham
    @echo.
    @echo Testing full build
    testham.exe

testham: clean lib $(TEST_OBJS_PATHS)
    @echo CFLAGS=$(CFLAGS)
    $(CC) $(CFLAGS) -o testham.exe $(TEST_OBJS_PATHS) -L. -lntru -lm

testnoham: CFLAGS += -DNTRU_AVOID_HAMMING_WT_PATENT
testnoham: clean lib $(TEST_OBJS_PATHS)
    @echo CFLAGS=$(CFLAGS)
    $(CC) $(CFLAGS) -o testnoham.exe $(TEST_OBJS_PATHS) -L. -lntru -lm

bench: lib
    $(CC) $(CFLAGS) $(CPPFLAGS) -o bench $(SRCDIR)/bench.c -L. -lntru

hybrid: lib
    $(CC) $(CFLAGS) $(CPPFLAGS) -o hybrid $(SRCDIR)/hybrid.c $(LDFLAGS) -L. -lntru -lcrypto -lgdi32

$(SRCDIR)/%.o: $(SRCDIR)/%.c
    $(CC) $(CFLAGS) $(CPPFLAGS) -c $< -o $@

$(SRCDIR)/sha1-mb-x86_64.s: $(SRCDIR)/sha1-mb-x86_64.pl; $(PERL) $(SRCDIR)/sha1-mb-x86_64.pl $(PERLASM_SCHEME) > $@
$(SRCDIR)/sha1-mb-x86_64.o: $(SRCDIR)/sha1-mb-x86_64.s
    $(AS) $(SRCDIR)/sha1-mb-x86_64.s -o $@
$(SRCDIR)/sha256-mb-x86_64.s: $(SRCDIR)/sha256-mb-x86_64.pl; $(PERL) $(SRCDIR)/sha256-mb-x86_64.pl $(PERLASM_SCHEME) > $@
$(SRCDIR)/sha256-mb-x86_64.o: $(SRCDIR)/sha256-mb-x86_64.s
    $(AS) $(SRCDIR)/sha256-mb-x86_64.s -o $@

$(TESTDIR)/%.o: tests/%.c
    $(CC) $(CFLAGS) $(CPPFLAGS) -I$(SRCDIR) -c $< -o $@

clean:
    rm -f $(SRCDIR)\*.o
    rm -f $(SRCDIR)\*.s
    rm -f $(TESTDIR)\*.o
    rm -f libntru.dll
    rm -f testham.exe
    rm -f testnoham.exe
    rm -f bench.exe
    rm -f libntru.so
    rm -f libntru.dylib
    rm -f testham
    rm -f testnoham
    rm -f bench
    rm -f hybrid
    rm -f hybrid.exe

distclean: clean
    rm -f $(DIST_NAME)\$(SRCDIR)\*.c
    rm -f $(DIST_NAME)\$(SRCDIR)\*.h
    rmdir $(DIST_NAME)\$(SRCDIR)
    rm -f $(DIST_NAME)\$(TESTDIR)\*.c
    rm -f $(DIST_NAME)\$(TESTDIR)\*.h
    rmdir $(DIST_NAME)\$(TESTDIR)
    rm -f $(DIST_NAME)\*.*
    rmdir $(DIST_NAME)
    rm -f $(DIST_NAME).zip
    rm -f $(DIST_NAME).tar.xz

src/poly.c:

#ifdef __OS2__
#include <endian.h>
#endif

NTRU_AVOID_HAMMING_WT_PATENT

NTRU's main strengths are high performance and resistance to quantum computer attacks. Its main drawback is that it is patent encumbered. The patents expire in 2021; when built with the NTRU_AVOID_HAMMING_WT_PATENT flag, libntru becomes patent-free in 2017.

Would you mind explaining/documenting what this NTRU_AVOID_HAMMING_WT_PATENT flag changes?

Thank you!

32-bit Сomputing, Windows, LLVM

Hello,

is it possible to build a 32 bit version of this library? The existing examples in the test folder are not built on Windows due to errors in the makefile. Have you tested this project on Windows? If you compile test cases through LLVM from Visual Studio, then the program crashes with an error.

Thanks!

MGF function incorect realization

//Change this in function ntru_MGF(), problem with {-1, 0, -1} conversion:
for (;;) {
        int cur = 0;

        int j;
        for (j=0; j<buf_len; j++) {
            int O = (unsigned char)buf[j];
            if (O >= 243)   /* 243 = 3^5 */
                continue;

            int ter_idx;
            for (ter_idx=0; ter_idx<4; ter_idx++) {
                int rem3 = O % 3;
                i->coeffs[cur] = rem3 - 1; 
                cur++;
                if (cur == N)
                    return;
                O = (O-rem3) / 3;
            }

            i->coeffs[cur] = O - 1;
            cur++;
            if (cur == N)
                return;
        }
//To this
const static char mm[] = {0, 1, -1}
for (;;) {
        int cur = 0;

        int j;
        for (j=0; j<buf_len; j++) {
            int O = (unsigned char)buf[j];
            if (O >= 243)   /* 243 = 3^5 */
                continue;

            int ter_idx;
            for (ter_idx=0; ter_idx<4; ter_idx++) {
                int rem3 = O % 3;
                i->coeffs[cur] = mm[rem3]; //because  -1 mod 3 = 2, 0 mod 3 = 0, 1 mod 3 = 1 
                cur++;
                if (cur == N)
                    return;
                O = (O-rem3) / 3;
            }

            i->coeffs[cur] = mm[O] ;
            cur++;
            if (cur == N)
                return;
        }

The parameter dm0 is zero for EES439EP1

In Mar 28, there is a commit which has zeroed the dm0 parameter in EES439EP1.

The same parameter is 130 in other implementations such as this java code:
https://github.com/tbuktu/ntru

Is this intentional or a bug?

0.4 does not compile if CC is set

If CC is set to gcc or clang, compilation failes with a lot of error messages:

[...]
Operator or semicolon missing before %rbp at (eval 633) line 2.
Ambiguous use of % resolved as operator % at (eval 633) line 2.
Bareword found where operator expected at (eval 634) line 2, near "%ecx     # examine counters
    cmovge"
    (Missing operator before cmovge?)
Operator or semicolon missing before %rbp at (eval 634) line 2.
Ambiguous use of % resolved as operator % at (eval 634) line 2.
Bareword found where operator expected at (eval 635) line 2, near "%ecx     # examine counters
    cmovge"
    (Missing operator before cmovge?)
Operator or semicolon missing before %rbp at (eval 635) line 2.
Ambiguous use of % resolved as operator % at (eval 635) line 2.
Bareword found where operator expected at (eval 636) line 2, near "%ecx     # examine counters
    cmovge"
    (Missing operator before cmovge?)
Operator or semicolon missing before %rbp at (eval 636) line 2.
Ambiguous use of % resolved as operator % at (eval 636) line 2.
Bareword found where operator expected at (eval 636) line 3, near "%r11         # cancel input
    vmovdqu"
    (Missing operator before vmovdqu?)
Bareword found where operator expected at (eval 636) line 4, near "%xmm6        # pull counters
    vpxor"
    (Missing operator before vpxor?)
Operator or semicolon missing before %xmm8 at (eval 636) line 4.
Ambiguous use of % resolved as operator % at (eval 636) line 4.
Bareword found where operator expected at (eval 636) line 5, near "%xmm8
    vmovdqa"
    (Missing operator before vmovdqa?)
Operator or semicolon missing before %xmm6 at (eval 636) line 5.
Ambiguous use of % resolved as operator % at (eval 636) line 5.
Bareword found where operator expected at (eval 636) line 6, near "%xmm7
    vpcmpgtd"
    (Missing operator before vpcmpgtd?)
Operator or semicolon missing before %xmm8 at (eval 636) line 6.
Ambiguous use of % resolved as operator % at (eval 636) line 6.
Bareword found where operator expected at (eval 636) line 7, near "%xmm7        # mask value
    vpaddd"
    (Missing operator before vpaddd?)
Operator or semicolon missing before %xmm7 at (eval 636) line 7.
Ambiguous use of % resolved as operator % at (eval 636) line 7.
Bareword found where operator expected at (eval 636) line 9, near "%xmm6        # counters--

    vpand"
    (Missing operator before vpand?)
Operator or semicolon missing before %xmm7 at (eval 636) line 9.
Ambiguous use of % resolved as operator % at (eval 636) line 9.
Bareword found where operator expected at (eval 636) line 10, near "%xmm10
    vpand"
    (Missing operator before vpand?)
Operator or semicolon missing before %xmm7 at (eval 636) line 10.
Ambiguous use of % resolved as operator % at (eval 636) line 10.
Bareword found where operator expected at (eval 636) line 11, near "%xmm11
    vpaddd"
    (Missing operator before vpaddd?)
Number found where operator expected at (eval 636) line 11, near "vpaddd    0x00"
    (Do you need to predeclare vpaddd?)
Bareword found where operator expected at (eval 636) line 12, near "%xmm10
    vpand"
    (Missing operator before vpand?)
Operator or semicolon missing before %xmm7 at (eval 636) line 12.
Ambiguous use of % resolved as operator % at (eval 636) line 12.
Bareword found where operator expected at (eval 636) line 13, near "%xmm12
    vpaddd"
    (Missing operator before vpaddd?)
Number found where operator expected at (eval 636) line 13, near "vpaddd    0x20"
    (Do you need to predeclare vpaddd?)
Bareword found where operator expected at (eval 636) line 14, near "%xmm11
    vpand"
    (Missing operator before vpand?)
Operator or semicolon missing before %xmm7 at (eval 636) line 14.
Ambiguous use of % resolved as operator % at (eval 636) line 14.
Bareword found where operator expected at (eval 636) line 15, near "%xmm13
    vpaddd"
    (Missing operator before vpaddd?)
Number found where operator expected at (eval 636) line 15, near "vpaddd    0x40"
    (Do you need to predeclare vpaddd?)
Bareword found where operator expected at (eval 636) line 16, near "%xmm12
    vpand"
    (Missing operator before vpand?)
Operator or semicolon missing before %xmm7 at (eval 636) line 16.
Ambiguous use of % resolved as operator % at (eval 636) line 16.
Bareword found where operator expected at (eval 636) line 17, near "%xmm14
    vpaddd"
    (Missing operator before vpaddd?)
Number found where operator expected at (eval 636) line 17, near "vpaddd    0x60"
    (Do you need to predeclare vpaddd?)
Bareword found where operator expected at (eval 636) line 18, near "%xmm13
    vpaddd"
    (Missing operator before vpaddd?)
Number found where operator expected at (eval 636) line 18, near "vpaddd    0x80"
    (Do you need to predeclare vpaddd?)
Bareword found where operator expected at (eval 636) line 19, near "%xmm14
    vmovdqu"
    (Missing operator before vmovdqu?)
Operator or semicolon missing before %xmm10 at (eval 636) line 19.
Ambiguous use of % resolved as operator % at (eval 636) line 19.
Bareword found where operator expected at (eval 636) line 20, near ")
    vmovdqu"
    (Missing operator before vmovdqu?)
Operator or semicolon missing before %xmm11 at (eval 636) line 20.
Ambiguous use of % resolved as operator % at (eval 636) line 20.
Bareword found where operator expected at (eval 636) line 21, near ")
    vmovdqu"
    (Missing operator before vmovdqu?)
Operator or semicolon missing before %xmm12 at (eval 636) line 21.
Ambiguous use of % resolved as operator % at (eval 636) line 21.
Bareword found where operator expected at (eval 636) line 22, near ")
    vmovdqu"
    (Missing operator before vmovdqu?)
Operator or semicolon missing before %xmm13 at (eval 636) line 22.
Ambiguous use of % resolved as operator % at (eval 636) line 22.
Bareword found where operator expected at (eval 636) line 23, near ")
    vmovdqu"
    (Missing operator before vmovdqu?)
Operator or semicolon missing before %xmm14 at (eval 636) line 23.
Ambiguous use of % resolved as operator % at (eval 636) line 23.
Bareword found where operator expected at (eval 636) line 25, near ")

    vmovdqu"
    (Missing operator before vmovdqu?)
Operator or semicolon missing before %xmm6 at (eval 636) line 25.
Ambiguous use of % resolved as operator % at (eval 636) line 25.
Bareword found where operator expected at (eval 636) line 26, near ")           # save counters
    vmovdqu"
    (Missing operator before vmovdqu?)
Number found where operator expected at (eval 636) line 26, near "vmovdqu   0x60"
    (Do you need to predeclare vmovdqu?)
Bareword found where operator expected at (eval 636) line 27, near "%xmm5       # pbswap_mask
    dec"
    (Missing operator before dec?)
Bareword found where operator expected at (eval 637) line 2, near "%edx
    lea"
    (Missing operator before lea?)
Number found where operator expected at (eval 637) line 2, near "lea    16"
    (Do you need to predeclare lea?)
Bareword found where operator expected at (eval 637) line 3, near "%rdi
    lea"
    (Missing operator before lea?)
Bareword found where operator expected at (eval 638) line 2, near "%rsi
    dec"
    (Missing operator before dec?)
gcc -c src/sha1-mb-x86_64.s -o src/sha1-mb-x86_64.o
src/sha1-mb-x86_64.s: Assembler messages:
src/sha1-mb-x86_64.s: Error: .size expression for sha1_multi_block_avx does not evaluate to a constant
Makefile.linux:147: recipe for target 'src/sha1-mb-x86_64.o' failed
make: *** [src/sha1-mb-x86_64.o] Error 1

Not an issue. Confused.

The function ntru_rand_tern() in src/poly.c uses at most half of rand_data in the first loop. The second loop also uses at most half of rand_data. Should if (r_idx >= rand_len) be if (r_idx >= 2 * rand_len)?

ntru_enc_len_Nq()

Why not return zero as a failure condition? The negative one is represented as 65535.

uint16_t ntru_enc_len_Nq(uint16_t N, uint16_t q) {
    /* make sure q is a power of 2 */
    if (q & (q-1))
        return -1;

    uint16_t len_bits = N * ntru_log2(q);
    uint16_t len_bytes = (len_bits+7) / 8;
    return len_bytes;
}

ntru_clone() / poly.c

Please check the results of malloc() before the memcpy().

Portate project to C90 and VC

I can send my port to VC with C90 fixes, mail me if needed

ntru_rand_device_init()

Should the function issue a close(rand_fd) if malloc() fails?

Quick patch to compile with old glibc < 2.9

--- src/poly.c.orig Sun Sep 6 12:55:00 2015
+++ src/poly.c Thu Sep 10 14:36:38 2015
@@ -19,6 +19,12 @@
#define htole32(x) (x)
#endif

+#if GLIBC <= 2 || ( GLIBC == 2 && GLIBC_MINOR < 9 )
+/* assume little endian */
+#define htole64(x) (x)
+#define htole32(x) (x)
+#endif
+
#ifdef OS2
#include <endian.h>
#endif

Errors during make

During make, errors fly all over the place:

cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/encparams.c -o src/encparams.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/hash.c -o src/hash.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/idxgen.c -o src/idxgen.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/key.c -o src/key.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/mgf.c -o src/mgf.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/ntru.c -o src/ntru.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/poly.c -o src/poly.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/rand.c -o src/rand.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/arith.c -o src/arith.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/sha1.c -o src/sha1.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/sha2.c -o src/sha2.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/nist_ctr_drbg.c -o src/nist_ctr_drbg.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -c -fPIC src/rijndael.c -o src/rijndael.o
src/rijndael.c:856:64: warning: argument 3 of type ‘const u8[16]’ {aka ‘const unsigned char[16]’} with mismatched bound [-Warray-parameter=]
  856 | rijndaelEncrypt(const u32 rk[/*4*(Nr + 1)*/], int Nr, const u8 pt[16],
      |                                                       ~~~~~~~~~^~~~~~
In file included from src/rijndael.c:33:
src/rijndael.h:55:53: note: previously declared as ‘const unsigned char[]’
   55 | void    rijndaelEncrypt(const unsigned int [], int, const unsigned char [],
      |                                                     ^~~~~~~~~~~~~~~~~~~~~~
src/rijndael.c:857:8: warning: argument 4 of type ‘u8[16]’ {aka ‘unsigned char[16]’} with mismatched bound [-Warray-parameter=]
  857 |     u8 ct[16])
      |     ~~~^~~~~~
src/rijndael.h:56:13: note: previously declared as ‘unsigned char[]’
   56 |             unsigned char []);
      |             ^~~~~~~~~~~~~~~~
CC=cc ASM="cc -c" /usr/bin/perl src/sha1-mb-x86_64.pl elf > src/sha1-mb-x86_64.s
cc -c src/sha1-mb-x86_64.s -o src/sha1-mb-x86_64.o
CC=cc ASM="cc -c" /usr/bin/perl src/sha256-mb-x86_64.pl elf > src/sha256-mb-x86_64.s
cc -c src/sha256-mb-x86_64.s -o src/sha256-mb-x86_64.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -mssse3 -c -fPIC src/hash_simd.c -o src/hash_simd.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -mssse3 -c -fPIC src/poly_ssse3.c -o src/poly_ssse3.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -mavx2 -c -fPIC src/poly_avx2.c -o src/poly_avx2.o
cc -g -Wall -Wextra -Wno-unused-parameter -DNTRU_DETECT_SIMD -O2  -shared -Wl,-soname,libntru.so -o libntru.so src/bitstring.o src/encparams.o src/hash.o src/idxgen.o src/key.o src/mgf.o src/ntru.o src/poly.o src/rand.o src/arith.o src/sha1.o src/sha2.o src/nist_ctr_drbg.o src/rijndael.o src/sha1-mb-x86_64.o src/sha256-mb-x86_64.o src/hash_simd.o src/poly_ssse3.o src/poly_avx2.o  -lrt
/usr/bin/ld: src/mgf.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:382: multiple definition of `ntru_invert'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:382: first defined here
/usr/bin/ld: src/mgf.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:316: multiple definition of `ntru_mod_mask'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:316: first defined here
/usr/bin/ld: src/mgf.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:276: multiple definition of `ntru_mult_int'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:276: first defined here
/usr/bin/ld: src/mgf.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:239: multiple definition of `ntru_to_arr'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:239: first defined here
/usr/bin/ld: src/mgf.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:138: multiple definition of `ntru_mult_tern'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:138: first defined here
/usr/bin/ld: src/ntru.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:382: multiple definition of `ntru_invert'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:382: first defined here
/usr/bin/ld: src/ntru.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:316: multiple definition of `ntru_mod_mask'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:316: first defined here
/usr/bin/ld: src/ntru.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:239: multiple definition of `ntru_to_arr'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:239: first defined here
/usr/bin/ld: src/ntru.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:276: multiple definition of `ntru_mult_int'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:276: first defined here
/usr/bin/ld: src/ntru.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:138: multiple definition of `ntru_mult_tern'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:138: first defined here
/usr/bin/ld: src/poly.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:316: multiple definition of `ntru_mod_mask'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:316: first defined here
/usr/bin/ld: src/poly.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:138: multiple definition of `ntru_mult_tern'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:138: first defined here
/usr/bin/ld: src/poly.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:276: multiple definition of `ntru_mult_int'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:276: first defined here
/usr/bin/ld: src/poly.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:239: multiple definition of `ntru_to_arr'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:239: first defined here
/usr/bin/ld: src/poly.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:382: multiple definition of `ntru_invert'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:382: first defined here
/usr/bin/ld: src/poly_ssse3.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:382: multiple definition of `ntru_invert'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:382: first defined here
/usr/bin/ld: src/poly_ssse3.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:316: multiple definition of `ntru_mod_mask'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:316: first defined here
/usr/bin/ld: src/poly_ssse3.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:276: multiple definition of `ntru_mult_int'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:276: first defined here
/usr/bin/ld: src/poly_ssse3.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:239: multiple definition of `ntru_to_arr'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:239: first defined here
/usr/bin/ld: src/poly_ssse3.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:138: multiple definition of `ntru_mult_tern'; src/key.o:/home/posydon/coding/Web Server C/libntru/src/poly.h:138: first defined here
/usr/bin/ld: warning: src/sha256-mb-x86_64.o: missing .note.GNU-stack section implies executable stack
/usr/bin/ld: NOTE: This behaviour is deprecated and will be removed in a future version of the linker
collect2: error: ld returned 1 exit status
make: *** [Makefile.linux:82: libntru.so] Error 1```

PowerPC

Please modify src/poly.c

#ifdef __GLIBC__
#if __GLIBC__ <= 2 || ( __GLIBC__ == 2 && __GLIBC_MINOR__ < 9 )
/* assume little endian */
#ifndef __powerpc__
#define htole64(x) (x)
#define htole32(x) (x)
#endif
#endif
#endif

ntru_decrypt()

I think there are some missing return statements in the function.

if (!ntru_check_rep_weight(&ci, dm0))
  {
   retcode = NTRU_ERR_DM0_VIOLATION;
   return retcode; // Exit here?
  }

Supplying improperly-encoded data to the method occasionally aborted the parent process. The error code NTRU_ERR_INVALID_ENCODING was returned.

Please review.

OS X does not have htole64().

Please apply the following changes to poly.c.

--- a/libNTRU/src/poly.c
+++ b/libNTRU/src/poly.c
@@ -8,6 +8,11 @@
#include "err.h"
#include "arith.h"

+#ifdef APPLE
+#include <libkern/OSByteOrder.h>
+#define htole64(x) OSSwapHostToLittleInt64(x)
+#endif
+
#define NTRU_SPARSE_THRESH 20

tbuktu / libntru Goto Github PK

libntru's People

Contributors

Stargazers

Watchers

Forkers

libntru's Issues

Recommend Projects

Recommend Topics

Recommend Org