change default branch - regression in prime_is_prime

[sjaeckel]

For now I've changed the default branch of this repo from develop to master as we're currently having too many changes that could break dependencies.

I've just tried to build libtomcrypt against latest develop and the LTC-internal diffie-hellman tests fail on develop because mp_prime_is_prime() seems to behave differently.

[minad]

Why does it matter what the default branch is?

API-wise there shouldn't be an issue with the develop branch as soon as one starts to use the non-deprecated APIs. Did you port ltc to the new API?

If there is an issue with mp_prime_is_prime, it is a regression and we should check what the problem is and add a regression test. At first we should probably just do a git bisect to find the problematic commit. It is probable that the issue was introduced during the simplifications I applied.

[sjaeckel]

Why does it matter what the default branch is?

Because that's the one that is checked out after an initial clone and too many users don't care on which version they are as long as "it works"^TM.

API-wise there shouldn't be an issue with the develop branch as soon as one starts to use the non-deprecated APIs. Did you port ltc to the new API?

Yes, libtom/libtomcrypt#526

If there is an issue with mp_prime_is_prime, it is a regression and we should check what the problem is and add a regression test. At first we should probably just do a git bisect to find the problematic commit. It is probable that the issue was introduced during the simplifications I applied.

Yes. I'm currently busy with something else, but later I'll get back to that.

[sjaeckel]

9edd185f66ba92b1061aefa05c7925e68ffe18b5 is the first bad commit
commit 9edd185f66ba92b1061aefa05c7925e68ffe18b5
Author: czurnieden <czurnieden@gmx.de>
Date:   Fri Oct 4 17:41:09 2019 +0200

    Addition of fast division (recursive divrem only)

ping @czurnieden :-)
#370 seems to be the culprit

[minad]

I am relieved ;) Hopefully @czurnieden comes up with a fix soon :)

[czurnieden]

Slashdot's MOTD today: "In every non-trivial program there is at least one bug." ;-)

@sjaeckel I don't use LTC and would need a bit of time to get familiar with it, so my humble question: you don't have, just by chance, a fraction that fails at hand?

I was testing a new algorithm for Newton division a couple of days ago (works better but the cut-off is still at around 50k of 60-bit limbs) and my test checks against school and recursive (all need to deliver the same result). I don't know exactly how much input I tested but it could easily go into the million. (also in various N/D ratios from 100:5 to 100:95 in steps of 5).
So what effing edgecase is it?
*sigh*

[czurnieden]

@sjaeckel @minad
Mmh…I think I did something wrong here while trying to recreate it.

I tried to act as a typical user who doesn't like to think a lot and tends to C&P from the READMEs:

czurnieden ~/GITHUB/libtomcrypt O (develop)$ git fetch origin develop
remote: Enumerating objects: 448, done.
remote: Counting objects: 100% (448/448), done.
remote: Compressing objects: 100% (25/25), done.
remote: Total 912 (delta 434), reused 432 (delta 423), pack-reused 464
Receiving objects: 100% (912/912), 281.20 KiB | 1006.00 KiB/s, done.
Resolving deltas: 100% (696/696), completed with 155 local objects.
From https://github.com/libtom/libtomcrypt
 * branch              develop    -> FETCH_HEAD
   01c455c3..0c30412a  develop    -> origin/develop
czurnieden ~/GITHUB/libtomcrypt O (develop)$ git merge FETCH_HEAD
Updating 01c455c3..0c30412a
Fast-forward
 .ci/build.sh                                               |  16 ++
...
 create mode 100644 tests/bcrypt_test.c
 create mode 100644 tests/ed25519_test.c
 create mode 100644 tests/x25519_test.
czurnieden ~/GITHUB/libtomcrypt O (develop)$ make CFLAGS="-DUSE_LTM -DLTM_DESC" EXTRALIBS="-ltommath" test
   * cc src/ciphers/aes/aes.o
   * cc src/ciphers/aes/aes_enc.o
...
   * cc src/math/ltm_desc.o
src/math/ltm_desc.c: In function ‘isprime’:
src/math/ltm_desc.c:453:51: warning: passing argument 3 of ‘mp_prime_is_prime’ from incompatible pointer type [-Wincompatible-pointer-types]
    err = mpi_to_ltc_error(mp_prime_is_prime(a, b, c));
                                                   ^
In file included from src/math/ltm_desc.c:15:0:
/usr/local/include/tommath.h:542:8: note: expected ‘_Bool *’ but argument is of type ‘int *’
 mp_err mp_prime_is_prime(const mp_int *a, int t, bool *result) MP_WUR;
        ^~~~~~~~~~~~~~~~~
src/math/ltm_desc.c:454:16: error: ‘MP_YES’ undeclared (first use in this function); did you mean ‘MP_MEM’?
    *c = (*c == MP_YES) ? LTC_MP_YES : LTC_MP_NO;
                ^~~~~~
                MP_MEM
src/math/ltm_desc.c:454:16: note: each undeclared identifier is reported only once for each function it appears in
makefile:56: recipe for target 'src/math/ltm_desc.o' failed
make: *** [src/math/ltm_desc.o] Error 1

LTM is current develop, installed as a shared lib. LTM wasn't installed before on this (I tend work from the workbenches directly).

czurnieden ~/GITHUB/libtommath O (develop)$ git fetch upstream develop
From https://github.com/libtom/libtommath
 * branch            develop    -> FETCH_HEAD
czurnieden ~/GITHUB/libtommath O (develop)$ sudo make -f makefile.shared install
...
czurnieden ~/GITHUB/libtommath O (develop)$  diff /usr/local/include/tommath.h /home/czurnieden/GITHUB/libtommath/tommath.h
czurnieden ~/GITHUB/libtommath O (develop)$

It seems as if something went wrong in compiling LTM?
Or is it just me?

[sjaeckel]

I just skimmed over it and it looked fine besides that you should do a git checkout latest-ltm in libtomcrypt, the branch of libtom/libtomcrypt#526

make -j9 all EXTRALIBS="../libtommath/libtommath.a " CFLAGS="-DUSE_LTM -DLTM_DESC -I../libtommath" && ./test dh is the commandline I use to build&run the LTC tests

I also quickly patched libtomcrypt/tests/dh_test.c

$ git diff -U1
diff --git a/tests/dh_test.c b/tests/dh_test.c
index b259031..06125fb 100644
--- a/tests/dh_test.c
+++ b/tests/dh_test.c
@@ -30,2 +30,3 @@ static int _prime_test(void)
          err = CRYPT_FAIL_TESTVECTOR;
+         ndraw(p, "p");
          goto done;
@@ -40,2 +41,3 @@ static int _prime_test(void)
          err = CRYPT_FAIL_TESTVECTOR;
+         ndraw(tmp, "(p-1)/2");
          goto done;

to draw the failing number and I got:

p: 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200CBBE117577A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D788719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA993B4EA988D8FDDC186FFB7DC90A6C08F4DF435C93402849236C3FAB4D27C7026C1D4DCB2602646DEC9751E763DBA37BDF8FF9406AD9E530EE5DB382F413001AEB06A53ED9027D831179727B0865A8918DA3EDBEBCF9B14ED44CE6CBACED4BB1BDB7F1447E6CC254B332051512BD7AF426FB8F401378CD2BF5983CA01C64B92ECF032EA15D1721D03F482D7CE6E74FEF6D55E702F46980C82B5A84031900B1C9E59E7C97FBEC7E8F323A97A7E36CC88BE0F1D45B7FF585AC54BD407B22B4154AACC8F6D7EBF48E1D814CC5ED20F8037E0A79715EEF29BE32806A1D58BB7C5DA76F550AA3D8A1FBFF0EB19CCB1A313D55CDA56C9EC2EF29632387FE8D76E3C0468043E8F663F4860EE12BF2D5B0B7474D6E694F91E6DBE115974A3926F12FEE5E438777CB6A932DF8CD8BEC4D073B931BA3BC832B68D9DD300741FA7BF8AFC47ED2576F6936BA424663AAB639C5AE4F5683423B4742BF1C978238F16CBE39D652DE3FDB8BEFC848AD922222E04A4037C0713EB57A81A23F0C73473FC646CEA306B4BCBC8862F8385DDFA9D4B7FA2C087E879683303ED5BDD3A062B3CF5B3A278A66D2A13F83F44F82DDF310EE074AB6A364597E899A0255DC164F31CC50846851DF9AB48195DED7EA1B1D510BD7EE74D73FAF36BC31ECFA268359046F4EB879F924009438B481C6CD7889A002ED5EE382BC9190DA6FC026E479558E4475677E9AA9E3050E2765694DFC81F56E880B96E7160C980DD98EDD3DFFFFFFFFFFFFFFFFF

which is the 8192-bit MODP Group 18 - https://tools.ietf.org/html/rfc3526#section-7

HTH & sorry that I didn't include the details immediately!

[czurnieden]

[…]besides that you should do a[…]

Ah, so it was just me ;-)

HTH & sorry that I didn't include the details immediately!

Nuh, don't worry, was a quick one in isprime in ltm_desc.c to get it to repeat the error.
Oh, my…
Mmh…there are a lot of ones at the start and the end of that number.

[czurnieden]

Yepp, it was definitely me. See #462

[sjaeckel]

okay, the regression is fixed, thanks @czurnieden

should we revert the default branch to develop?

IMO yes, so I did it already, but you're free to give arguments against that and having the default point to master

[minad]

Default to develop please!