Libtomcrypt armv8 aarch64 troubles

[demonguy]

Thanks for creating such elegant crypt library. It's just the thing that i want.
But i found some difficult on transplanting it. I have a hardware which only have 512 KB memory to use.
And the only two functions i need are "rsa_import" "and rsa_decrypt". So i just include "rsa_decrypt_key.c" and "rsa_import.c", and then whenever i found "undefined references", i will include corresponding source file.

Finally it passes compiling, but i found the final library is 900KB, libtommatch is already 700KB. Is there any chance for me to shrink it? And how can i do it?

[karel-m]

You approach is basically what I would do.

• here is my quick&dirty attempt https://github.com/karel-m/libtomcrypt-subset
• the final binary of rsa_import+rsa_decrypt_key demo is 100-150KB (32bit Windows EXE)
• you can save more space by switching from rsa_import to rsa_import_radix (you can exclude all ASN.1 code)

[demonguy]

So you didn't include any libtommatch source files?
I have to download libtommath and all include in. Why you can ignore them?

crypto/libtommath/bn_mp_neg.c
crypto/libtommath/bn_mp_copy.c
crypto/libtommath/bn_mp_set_int.c
crypto/libtommath/bn_mp_get_int.c
crypto/libtommath/bn_mp_cmp.c
crypto/libtommath/bn_mp_cmp_d.c
crypto/libtommath/bn_mp_count_bits.c
crypto/libtommath/bn_mp_cnt_lsb.c
crypto/libtommath/bn_mp_2expt.c
crypto/libtommath/bn_mp_read_radix.c
crypto/libtommath/bn_mp_toradix.c
crypto/libtommath/bn_mp_add.c
crypto/libtommath/bn_mp_add_d.c
crypto/libtommath/bn_mp_sub.c
crypto/libtommath/bn_mp_sub_d.c
crypto/libtommath/bn_mp_mul.c
crypto/libtommath/bn_mp_mul_d.c
crypto/libtommath/bn_mp_sqr.c
crypto/libtommath/bn_mp_div.c
crypto/libtommath/bn_mp_div_2.c
crypto/libtommath/bn_mp_mod_d.c
crypto/libtommath/bn_mp_gcd.c
crypto/libtommath/bn_mp_lcm.c
crypto/libtommath/bn_mp_mulmod.c
crypto/libtommath/bn_mp_sqrmod.c
crypto/libtommath/bn_mp_invmod.c
crypto/libtommath/bn_mp_exptmod.c
crypto/libtommath/bn_mp_prime_is_prime.c
crypto/libtommath/bn_mp_unsigned_bin_size.c
crypto/libtommath/bn_mp_to_unsigned_bin.c
crypto/libtommath/bn_mp_montgomery_setup.c
crypto/libtommath/bn_mp_read_unsigned_bin.c
crypto/libtommath/bn_mp_montgomery_calc_normalization.c
crypto/libtommath/bn_mp_montgomery_reduce.c
crypto/libtommath/bn_mp_grow.c
crypto/libtommath/bn_mp_zero.c
crypto/libtommath/bn_mp_mul_2d.c
crypto/libtommath/bn_mp_clamp.c
crypto/libtommath/bn_mp_init_copy.c
crypto/libtommath/bn_mp_div_d.c
crypto/libtommath/bn_mp_toom_mul.c
crypto/libtommath/bn_mp_karatsuba_mul.c
crypto/libtommath/bn_mp_toom_sqr.c
crypto/libtommath/bn_mp_karatsuba_sqr.c
crypto/libtommath/bn_mp_init_size.c
crypto/libtommath/bn_mp_lshd.c
crypto/libtommath/bn_mp_rshd.c
crypto/libtommath/bn_mp_exch.c
crypto/libtommath/bn_mp_div_2d.c
crypto/libtommath/bn_mp_abs.c
crypto/libtommath/bn_mp_init_multi.c
crypto/libtommath/bn_mp_cmp_mag.c
crypto/libtommath/bn_mp_clear_multi.c
crypto/libtommath/bn_mp_mod.c
crypto/libtommath/bn_mp_invmod_slow.c
crypto/libtommath/bn_mp_reduce_is_2k_l.c
crypto/libtommath/bn_mp_dr_is_modulus.c
crypto/libtommath/bn_mp_reduce_is_2k.c
crypto/libtommath/bn_mp_exptmod_fast.c
crypto/libtommath/bn_mp_prime_is_divisible.c
crypto/libtommath/bn_mp_set.c
crypto/libtommath/bn_mp_prime_miller_rabin.c
crypto/libtommath/bn_mp_mul_2.c
crypto/libtommath/bn_mp_div_3.c
crypto/libtommath/bn_mp_mod_2d.c
crypto/libtommath/bn_mp_dr_setup.c
crypto/libtommath/bn_mp_reduce_2k_setup.c
crypto/libtommath/bn_mp_reduce_2k.c
crypto/libtommath/bn_mp_dr_reduce.c
crypto/libtommath/bn_mp_radix_smap.c
crypto/libtommath/bn_s_mp_add.c
crypto/libtommath/bn_s_mp_mul_digs.c
crypto/libtommath/bn_s_mp_sqr.c
crypto/libtommath/bn_s_mp_exptmod.c
crypto/libtommath/bn_s_mp_sub.c
crypto/libtommath/bn_fast_s_mp_mul_digs.c
crypto/libtommath/bn_fast_s_mp_sqr.c
crypto/libtommath/bn_fast_mp_invmod.c
crypto/libtommath/bn_fast_mp_montgomery_reduce.c
crypto/libtommath/bn_mp_reduce_2k_setup_l.c
crypto/libtommath/bn_mp_reduce_setup.c
crypto/libtommath/bn_mp_reduce_2k_l.c
crypto/libtommath/bn_mp_reduce.c
crypto/libtommath/bn_reverse.c
crypto/libtommath/bn_s_mp_mul_high_digs.c
crypto/libtommath/bn_prime_tab.c
crypto/libtommath/bncore.c
crypto/libtommath/bn_fast_s_mp_mul_high_digs.c

[karel-m]

I did, it is in ltm subdir https://github.com/karel-m/libtomcrypt-subset/tree/master/ltm

The libtomcrypt (a subset) is in ltc subdir and the makefile first creates liballinone.a library containing both and after that you can link your code with this library via -L. -lallinone compiler/linker options

[demonguy]

i found rsa_import return 7, which is CRYPT_INVALID_PACKET. But i'm using the exactly same private_rsa array of libtomcrypt-subset/main.c.

And it is where return INVALID_PACKET. Do you have any clue?
/* now it should be SEQUENCE { INTEGER, INTEGER } */ if ((err = der_decode_sequence_multi(tmpbuf, t, LTC_ASN1_INTEGER, 1UL, key->N, LTC_ASN1_INTEGER, 1UL, key->e, LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) {

By the way. how much memory does rsa_import and rsa_decrypt_key need? After code size and stack, i only have 128KB heap for malloc. Is it enough?

[demonguy]

now i use rsa_import_radix rather than rsa_import
import status is 0 now. but rsa_decrypt_key_ex status is still invalid.
Here is how i call it. rsa_decrypt_key_ex(a, sizeof(a), temp_buffer, &plain_text_len , NULL, 0, 0, LTC_PKCS_1_V1_5, &stat, &key);

a is the contents of sig.bin. Signature that i generate by using such command openssl rsautl -sign -pkcs -in message.bin -out sig.bin. And i suppose temp_buffer should be contents of message.bin.
Did i do anything wrong?

And what argument should i pass to padding if i sign it with -raw option(which mean no padding.). I didn't see any macro like LTC_PADDING_NO, is it zero?

[demonguy]

I found that even i do exactly what libtomcrypt-subset/main.c do, it's still invalid. rsa_import is invalid, and even i use rsa_import_radix, then rsa_decrypt_key is invalid.

[sjaeckel]

regarding the integration of ltm you could also just use pre_gen/mpi.c, so you only have 1 file which also helps with the library size IIRC (you probably should update it (call make pre_gen) before using it)

[rofl0r]

if your binary is 900 KB, you're doing something wrong. i've written an ircbot using wolfSSL for ssl connection, and the entire binary when static linked against musl libc is ~140 KB with heavy size optimization settings (-Os -g0 -s -flto ...). this is just to give you a rough idea, but doing TLS connections, parsing certificates, etc, is far more complex than basic RSA usage. karel-m's libtomcrypt-subset gives me a binary size of 80KB (static linked).

~/libtomcrypt-subset[master*]$ make CFLAGS="-fdata-sections -ffunction-sections -Os -g0 -s -fno-unwind-tables -fno-asynchronous-unwind-tables -Wa,--noexecstack -static" -j2
cc -fdata-sections -ffunction-sections -Os -g0 -s -fno-unwind-tables -fno-asynchronous-unwind-tables -Wa,--noexecstack -static main.c -o main -DUSE_LTM -DLTM_DESC -Iltc/headers -Iltm -L. -lallinone
~/libtomcrypt-subset[master*]$ la main
-rwxr-xr-x    1 rofl     rofl         81176 Mar  5 14:30 main

[demonguy]

Thanks for helping me. I will try to figure out where is wrong. @karel-m it's really a wonderful library

[demonguy]

After debugging, i found where is going wrong. Exactly same key array and data array runs well on linux PC but fail on my ARM board. So i add debug log and found rsa_exptmod return CRYPT_PK_INVALID_SIZE. So i use mp_toradix to print key->N and tmp, and here is the value.

As you can see, all the big numbers are truncated. Why would this happen?

PC:

key->N:B7FBCDE320B827E34F0D13C40EC5C8ABBC13F0288D9A7C16731ED3E5D4C2D7798804FDF3938BE1FA0868DAE6788F30B5530679BFCFE00661238D8E9FC32588C676F964A575F4438CCC97EF2D4476C3655BD5DA7E50AABFDB998D3235181D9A1EDCBCF49F866DDF6BF2856318EDC49BDF151BD2ED7B438945029A3A73755682D0B0669915FA3317DD7D57D06F51A34921460BA7CF3CD83CB7B5F62195DBBE4E5BA876BB41D3DC3D29C07317A190D205853C6A081D1807E7FCC271C1EA811B105D855C2DF1608ED5E6393EE7739F8B04E271652D68D37BC9D975E614BCC71E77E1E051BA9E51EE9D3E55E1A5BA05FCF18620E96F4A5B21717239165BA135FB5041
tmp: A096921682891FA4AAD7099120BE1CA15788E6E3C383F98EAD2CCD4D78AABB4EC38D2AA9170AC988A5201AF6298155A487CD6CA4A42B22019FD5ACDB5DDE313943953C3EEB646B994C121F48D63E18745C1D56562619CE023009D1BDA4AF18CC592F2684BBCA6D909B402E7EFDF8B8C9C9D3F8AD9FCD25A098269944D023F25095B82823F623B403F315FA1F76769E0D6F9C3FC4938E0CFF25D48053E3450CF547B4449BC313765EFFD2BF30BBE7C15F17F7357401FB4EDAE92B97BF005ED50AAD412AE38EB5F60CB69E502D5883F370AE456F48821393BC73FD1BAAEA7AA030BCFEA5051F271A1712109EA8D519D156DF50D25A86C54DF0334805F62800254E

My Board:

key->N:DC49BDF151BD2ED7B438945029A3A73755682D0B0669915FA3317DD7D57D06F51A34921460BA7CF3CD83CB7B5F62195DBBE4E5BA876BB41D3DC3D29C07317A190D205853C6A081D1807E7FCC271C1EA811B105D855C2DF1608ED5E6393EE7739F8B04E271652D68D37BC9D975E614BCC71E77E1E051BA9E51EE9D3E55E1A5BA05FCF18620E96F4A5B21717239165BA135FB5041
tmp:2E7EFDF8B8C9C9D3F8AD9FCD25A098269944D023F25095B82823F623B403F315FA1F76769E0D6F9C3FC4938E0CFF25D48053E3450CF547B4449BC313765EFFD2BF30BBE7C15F17F7357401FB4EDAE92B97BF005ED50AAD412AE38EB5F60CB69E502D5883F370AE456F48821393BC73FD1BAAEA7AA030BCFEA5051F271A1712109EA8D519D156DF50D25A86C54DF0334805F62800254E

[karel-m]

Could you try to replace tomcrypt_cfg.h with this one:

https://github.com/libtom/libtomcrypt/blob/fix/109-alternative-approach/src/headers/tomcrypt_cfg.h

As for your board it is ARM/32bit right?

[rofl0r]

one gotcha of the ARM ABI is that it defaults to unsigned char, which is quite exceptional and breaks many assumptions. you can see if that's the issue by using -fsigned-char in your CFLAGS, which fixes the issue.

[demonguy]

It's armv8 aarch64. Neither tomcrypt_cfg.h nor fsigned-char helps.
After some debug in mp_read_unsigned_bin, i found argument b already have intact data.(I do this by print them one by one).
Going to take deep research on what happened next.
By the way i'm using clang, not gcc

I'will update what i found in late comment

BTW, @karel-m Could give me some hints why you give me a tomcrypt_cfg.h? What do you suspect?

[karel-m]

If you compile the library (libtomcrypt + libtommath) with -Wall -Wextra do you see any warnings? (if yes, please post them here)

[demonguy]

On X86_X64, DIGIT_BIT is defined as 60, however on my arm64 board it is 28.
I'm not familiar with big number handling, so i just change DIGIT_BIT to 28 on my PC, and compare a->used between PC and my board when mp_read_unsigned_bin reading exact same number.

when reading this one
A096921682891FA4AAD7099120BE1CA15788E6E3C383F98EAD2CCD4D78AABB4EC38D2AA9170AC988A5201AF6298155A487CD6CA4A42B22019FD5ACDB5DDE313943953C3EEB646B994C121F48D63E18745C1D56562619CE023009D1BDA4AF18CC592F2684BBCA6D909B402E7EFDF8B8C9C9D3F8AD9FCD25A098269944D023F25095B82823F623B403F315FA1F76769E0D6F9C3FC4938E0CFF25D48053E3450CF547B4449BC313765EFFD2BF30BBE7C15F17F7357401FB4EDAE92B97BF005ED50AAD412AE38EB5F60CB69E502D5883F370AE456F48821393BC73FD1BAAEA7AA030BCFEA5051F271A1712109EA8D519D156DF50D25A86C54DF0334805F62800254E

PC a->used is 74, while my arm board shows it is 43. Both of them have DIGIT_BIT as 28

[karel-m]

Try to patch tommath.h and rebuild the whole stuff

- #if defined(__x86_64__)
+ #if defined(__x86_64__) || defined(__aarch64__)

[rofl0r]

another case of broken CPP assumptions ...
that's what you get for trying to catch each possible arch, os, libc, compiler combination using preprocessor hacks instead of testing for properties like configure scripts do.

[demonguy]

Well, no warnings at all because i always set -Werror -Wall -Wextra. So warning will be treated as error and break the build.

As for patch tommath.h, i got bunch of undefined reference to __udivti3
It seems that clang can't find it's own 128 bits integer division symbol. I'm going to search how to solve it.

Information for references:

Target: arm-none-linux-gnueabi Thread model: posix Repository: (git://git-hexagon.quicinc.com/llvm/clang-mainline.git a3aa5516ce435f5dfed7f24f4eafab07a76b55c7) (llvm/llvm-mainline.git 7d3cf63ab0a75ac41a9fc3758dd57e60728efc1f) Snapdragon LLVM ARM Compiler 3.5.2

[karel-m]

In QEMU + Debian/ARM64 I am not able to reproduce the failure neither with gcc nor with clang (QEMU started with -machine virt -cpu cortex-a57)

$ cat /etc/os-release
PRETTY_NAME="Debian GNU/Linux 8 (jessie)"
NAME="Debian GNU/Linux"
VERSION_ID="8"
VERSION="8 (jessie)"
ID=debian
HOME_URL="http://www.debian.org/"
SUPPORT_URL="http://www.debian.org/support"
BUG_REPORT_URL="https://bugs.debian.org/"

$ uname -a
Linux debian 3.16.0-4-arm64 #1 SMP Debian 3.16.39-1+deb8u1 (2017-02-22) aarch64 GNU/Linux

$ gcc --version
gcc (Debian/Linaro 4.9.2-10) 4.9.2
Copyright (C) 2014 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ clang --version
Debian clang version 3.5.0-10 (tags/RELEASE_350/final) (based on LLVM 3.5.0)
Target: aarch64-unknown-linux-gnu
Thread model: posix

I have tested my https://github.com/karel-m/libtomcrypt-subset

$ make
...
$ ./main
1/4 register_hash: success
2/4 find_hash: success
3/4 rsa_import: success
4/4 rsa_decrypt_key: success

IMO There must be something special|strange|different about your ARM board.

[demonguy]

Then would mind giving me some idea? Where can i add more debug logs to check where is going wrong?
I'm stuck on the big number truncated and don't know what should do next.

[rofl0r]

did you already try to run @karel-m 's code unaltered ? if that passes the tests, the bug is likely in your code.

[demonguy]

I print all number before mp_read_unsigned_bin return MP_OKAY
for (i = 0; i < a->used; ++i) { snprintf(tmp,1024,"%x", a->dp[i]); boot_log_message(tmp); }

Here is part of result
800254e 4805f62

Original number is
2E7EFDF8B8C9C9D3F8AD9FCD25A098269944D023F25095B82823F623B403F315FA1F76769E0D6F9C3FC4938E0CFF25D48053E3450CF547B4449BC313765EFFD2BF30BBE7C15F17F7357401FB4EDAE92B97BF005ED50AAD412AE38EB5F60CB69E502D5883F370AE456F48821393BC73FD1BAAEA7AA030BCFEA5051F271A1712109EA8D519D156DF50D25A86C54DF0334805F62800254E

As DIGIT_BIT is 28, if i understand struct mp_int correctly, a->dp[0] should store 0x2800254E rather than 800254E, which means every time it reads an unsigned long int, highest 4 bits are lost.

I'm still taking further investigation, and will feedback if i found where is wrong.

[demonguy]

Finally i worked it out. Code on my original board is messy, And standard library implementation is ridiculous.
void *realloc(void *p, size_t sz) { free(p); return malloc(sz); }
This is the cause of big number truncation. Sign!

Another thing is that, rsa_verify_hash_ex doesn't provide a method to verify message without hash. In practice. Some HSM still sign message directly without hash or add hash identifier to the message (rfc3447.txt Page 42). They just padding and sign it directly. Libtomcrypt doesn't provide a method to verify such message, i have to call ltc_mp.rsa_me and pkcs_1_v1_5_decode.

Anyway ,case closed. Thanks for helping me.!

[karel-m]

Ad realloc - do I understand correctly that this issue is outside of libtomcrypt/libtommath, right?

Ad rsa_verify_hash_ex - when using pkcs1v1.5 padding (which seems to be your case) the hash function identified by hash_idx is used only for checking proper OID in signature's ASN.1 data structure, in fact no hashing happens. The function rsa_verify_hash_ex is verifying whatever data passed via hash + hashlen params.

[demonguy]

1. Yes, realloc issue is not related to libtomcrypt.
2. My signature format is raw from HSM, it is generated by command like this openssl rsa -sign -inkey key.pem -out sig.bin. It's not wrapped by ANS.1, it's just raw signature

[sjaeckel]

Regarding 2 I've a patch that I wasn't able to test yet (I wrote the patch as some pre TLS implementations also used that format of pkcs#1v1.5)
I'll push them later so you can have a try if you'd like

[demonguy]

Thanks.

[sjaeckel]

I've pushed to feature/pkcs1ssl, feel free to try it out