RC2 - TFM & timing troubles in DSA

[karel-m]

I have built the library via:

make -f makefile.unix CFLAGS="-Wall -Wextra -Werror -DUSE_TFM -DTFM_DESC -DLTC_SOURCE -Isrc/headers -I../tomsfastmath/src/headers" EXTRALIBS=../tomsfastmath/libtfm.a all

When I try to run ./timing it never ends:

./timing
Clock Skew: 0


Key Schedule Time Trials for the Symmetric Ciphers:
(Times are cycles per key)
.......................
skipjack            : Schedule at     53
noekeon             : Schedule at     55
xtea                : Schedule at    234

...

RSA-2048 make_key    took       429383933 cycles
RSA-2048 encrypt_key took          240743 cycles
RSA-2048 decrypt_key took         5404849 cycles
RSA-2048 sign_hash took           5475974 cycles
RSA-2048 verify_hash took          210872 cycles


DSA-(160, 768) make_key    took        78803816 cycles
DSA-(160, 1024) make_key    took       246325338 cycles
DSA-(192, 1536) make_key    took       660878002 cycles
DSA-(224, 2048) make_key    took      2238445835 cycles
!!!!!!! here it stays for hours just consuming CPU !!!!!!!

It seems to got stuck somewhere in DSA-(256, 4096) make_key

TFM version:

commit 81530c207da8b3a43867da14df7d79d2cdf96978
Date:   Wed Jun 14 17:17:30 2017 +0200

I have not experienced this sort of troubles with LTM - here are LTM results from the same machine:

DSA-(160, 768) make_key    took       364152277 cycles
DSA-(160, 1024) make_key    took       743838300 cycles
DSA-(192, 1536) make_key    took      1703609029 cycles
DSA-(224, 2048) make_key    took     13534636760 cycles
DSA-(256, 4096) make_key    took    117063959249 cycles

[buggywhip]

On 7Aug, 2017, at 7:27 AM, karel-m ***@***.***> wrote: When I try to run ./timing it never ends:

...

DSA-(192, 1536) make_key took 660878002 cycles DSA-(224, 2048) make_key took 2238445835 cycles !!!!!!! here it stays for hours just consuming CPU !!!!!!! It seems to got stuck somewhere in DSA-(256, 4096) make_key

Confirmed. I just aborted my run of "DSA-(256, 4096) make key" after well over 3 hours (3.5GHz i5). It too was LTC/TFM.

[buggywhip]

I'd like to suggest , in the interest of our brethren running Raspberry Pi and other smaller machines, that we disable/delete the timing test for DSA-4098 make key. ...and perhaps some of the other longer running tests. I doubt they will have the patience to wait; I know I don't. Besides, some of these stochastic timings are [relatively] meaningless anyway.

...or perhaps add an optional ./timing commandline switch to cancel pk tests when they exceed some number of wall-clock seconds, eg: -limitsecs 60

[karel-m]

The problem is:

dsa_generate_pqg(&yarrow_prng, find_prng("yarrow"), 32, 512, &key)

[karel-m]

It seems that at this line: https://github.com/libtom/libtomcrypt/blob/release/1.18.0/src/pk/dsa/dsa_generate_pqg.c#L164 mp_prime_is_prime(p, mr_tests_p, &res) is always returning not a prime (for mr_tests_p=64).

And because we loop via:

for(found_p=0; !found_p;) {
   ...
}

we do it for ever. We should perhaps utilize PK_MAX_RETRIES here.

[buggywhip]

On 7Aug, 2017, at 11:55 AM, karel-m ***@***.***> wrote: It seems that at this line: https://github.com/libtom/libtomcrypt/blob/release/1.18.0/src/pk/dsa/dsa_generate_pqg.c#L164 <https://github.com/libtom/libtomcrypt/blob/release/1.18.0/src/pk/dsa/dsa_generate_pqg.c#L164> mp_prime_is_prime(p, mr_tests_p, &res) is always returning not a prime (for mr_tests_p=64). And because we loop via: for(found_p=0; !found_p;) { ... } we do it for ever. We should perhaps utilize PK_MAX_RETRIES here.

If the [consistent?] failure was when running with TFM and not with LTM, why the focus on this loop in dsa_generate_pqg? I'm going to rerun several times as this is a stochastic process to get some indication of repeatability.

[sjaeckel]

this reminds me of https://github.com/libtom/libtomcrypt/blob/release/1.18.0/src/headers/tomcrypt_custom.h#L385

[buggywhip]

On 7Aug, 2017, at 12:15 PM, Larry Bugbee ***@***.***> wrote: If the [consistent?] failure was when running with TFM and not with LTM, why the focus on this loop in dsa_generate_pqg? I'm going to rerun several times as this is a stochastic process to get some indication of repeatability.

I fired up 4 processes maxing out my cores, and after letting each run for 10-12 minutes, they all hang at DSA-4096. That's 5 out of 5. I'm of the opinion this is deterministic and has to do with TFM. Yarrow? ...not so much. Definitely not LTM.

[buggywhip]

I vaguely recall seeing somewhere a TFM limit on the size of numbers and 4096 might be exceeding that. Dunno, but at this point it is just a feeling.

[sjaeckel]

Got it!

... and yep, it makes sense...

build tfm with CFLAGS="-DFP_MAX_SIZE=10000" make
build ltc with make -j9 all timing CFLAGS="-DFP_MAX_SIZE=10000 -DUSE_TFM -DTFM_DESC -I../tomsfastmath/src/headers" EXTRALIBS="../tomsfastmath/libtfm.a"

tfm in its default config can only do 2048x2048 multiplications...

[karel-m]

this reminds me of https://github.com/libtom/libtomcrypt/blob/release/1.18.0/src/headers/tomcrypt_custom.h#L385

Yes, /* tfm has a problem in fp_isprime for larger key sizes */ seems like somebody already dealt with similar issue.

Anyway, as mentioned above it is TFM problem so not a 1.18 blocker.

[buggywhip]

For now I'd drop the DSA-4096 timing test in timing.c.

[sjaeckel]

we definitely should work on libtom/tomsfastmath#10

[sjaeckel]

diff --git a/demos/timing.c b/demos/timing.c
index 670d2f7..0c6b543 100644
--- a/demos/timing.c
+++ b/demos/timing.c
@@ -659,3 +659,5 @@ static const struct {
 { 28, 256 },
-{ 32, 512 }
+#ifndef TFM_DESC
+{ 32, 512 },
+#endif
 };

fine like that?

[karel-m]

fine like that?

👍

[sjaeckel]

alternatively we could double the default tfm size :>