Reduce s2n-tls binary size

alexw91 commented 2 years ago

Problem:

Currently the size of libs2n.so is over 1 megabyte in size. This makes it difficult to use s2n in some contexts where storage size is constrained (Eg AWS SDK use cases for IoT/embedded clients). We'd like to ensure that customers don't need workarounds to avoid using s2n due to it's binary size.

Solution:

The largest functions in terms of code size in s2n currently are many of the PQ algorithms, so initial work can likely make quick progress there by removing the older rounds of algorithms, but we should begin investigating other options as well, and work towards a longer term plan for ensuring s2n-tls stays as small as possible.

Possible actions to reduce binary size:

[x] Remove older rounds of PQ algorithms
[ ] Investigate new compile time options for finer grained control of which algorithms to enable/disable
[ ] Investigate if possible to optimize Round 3 PQ algorithms for code size
[ ] Investigate/Create tooling to measure s2n binary size during Pull Requests, and warn if binary size increased significantly
[ ] Investigate enabling Link Time Optimization
[ ] Optimize the generation of Error Strings

Requirements / Acceptance Criteria:

Reduce libs2n.so binary size significantly, and have a mechanism that prevents it from slowly increasing over time again.

alexw91 commented 2 years ago

Top 50 largest functions in s2n

aweibel$ readelf -sw --wide libs2n.so | grep FUNC | grep -v UND | sort -nr -k3 | head -50
  1455: 00000000000acac0 31563 FUNC    LOCAL  DEFAULT   12 s2n_kyber_512_r3_KeccakF1600times4_FastLoop_Absorb
  1766: 00000000000a1b40 29740 FUNC    LOCAL  DEFAULT   12 s2n_kyber_512_r3_KeccakP1600times4_PermuteAll_24rounds
  1569: 00000000000b4610 16859 FUNC    LOCAL  DEFAULT   12 s2n_kyber_512_r3_KeccakP1600times4_12rounds_FastLoop_Absorb
   725: 0000000000097130 16658 FUNC    LOCAL  DEFAULT   12 crypto_hashblocks_sha512
  2352: 00000000000a8f70 15182 FUNC    LOCAL  DEFAULT   12 s2n_kyber_512_r3_KeccakP1600times4_PermuteAll_12rounds
  1063: 00000000000843a0 14147 FUNC    LOCAL  DEFAULT   12 gf2x_mod_mul_with_ctx
   724: 0000000000094400 11554 FUNC    LOCAL  DEFAULT   12 crypto_hashblocks_sha256
  2096: 000000000007dca0  5775 FUNC    LOCAL  DEFAULT   12 BIKE1_L1_R2_gf2x_mod_mul
  1565: 0000000000077bb0  5775 FUNC    LOCAL  DEFAULT   12 BIKE1_L1_R1_gf2x_mod_mul
  1478: 000000000001c770  4222 FUNC    LOCAL  DEFAULT   12 s2n_asn1_time_to_nano_since_epoch_ticks
  2321: 00000000000482a0  3713 FUNC    LOCAL  DEFAULT   12 s2n_record_writev
   941: 00000000000833d0  3498 FUNC    LOCAL  DEFAULT   12 decode
  1254: 000000000007a320  3295 FUNC    LOCAL  DEFAULT   12 BIKE1_L1_R1_decode
  1253: 0000000000080110  3183 FUNC    LOCAL  DEFAULT   12 BIKE1_L1_R2_decode
  2376: 00000000000520e0  3033 FUNC    LOCAL  DEFAULT   12 s2n_x509_validator_validate_cert_chain
   354: 0000000000074e20  2918 FUNC    GLOBAL DEFAULT   12 s2n_strerror
  2974: 0000000000074e20  2918 FUNC    GLOBAL DEFAULT   12 s2n_strerror
   268: 0000000000075990  2882 FUNC    GLOBAL DEFAULT   12 s2n_strerror_name
  2638: 0000000000075990  2882 FUNC    GLOBAL DEFAULT   12 s2n_strerror_name
   430: 000000000004c080  2766 FUNC    GLOBAL DEFAULT   12 s2n_connection_wipe
  2845: 000000000004c080  2766 FUNC    GLOBAL DEFAULT   12 s2n_connection_wipe
   114: 0000000000027d00  2647 FUNC    LOCAL  DEFAULT   12 s2n_handshake_read_io
   789: 00000000000bc180  2545 FUNC    LOCAL  DEFAULT   12 KeccakF1600_StatePermute
   207: 000000000003a720  2534 FUNC    LOCAL  DEFAULT   12 s2n_deserialize_resumption_state
  2488: 000000000008a440  2452 FUNC    LOCAL  DEFAULT   12 KeccakF1600_StatePermute_r1
   800: 00000000000bf7d0  2444 FUNC    LOCAL  DEFAULT   12 KeccakF1600_StatePermute
   714: 00000000000923b0  2444 FUNC    LOCAL  DEFAULT   12 KeccakF1600_StatePermute
   368: 000000000005d010  2441 FUNC    LOCAL  DEFAULT   12 s2n_client_psk_recv
   945: 000000000007c4a0  2440 FUNC    LOCAL  DEFAULT   12 BIKE1_L1_R2_crypto_kem_enc
  2148: 000000000007ce30  2234 FUNC    LOCAL  DEFAULT   12 BIKE1_L1_R2_crypto_kem_dec
   373: 00000000000292c0  2167 FUNC    GLOBAL DEFAULT   12 s2n_negotiate
  2541: 00000000000292c0  2167 FUNC    GLOBAL DEFAULT   12 s2n_negotiate
  1082: 000000000008f6f0  2074 FUNC    LOCAL  DEFAULT   12 EphemeralKeyGeneration_B_r1
  2236: 0000000000089a90  1977 FUNC    LOCAL  DEFAULT   12 BIKE_L1_R3_crypto_kem_dec
  1319: 000000000008c750  1964 FUNC    LOCAL  DEFAULT   12 fpinv503_chain_mont
  2122: 0000000000057e20  1909 FUNC    LOCAL  DEFAULT   12 s2n_server_hello_recv
   301: 0000000000058ff0  1847 FUNC    LOCAL  DEFAULT   12 s2n_server_key_share_recv
  2302: 000000000008efe0  1795 FUNC    LOCAL  DEFAULT   12 EphemeralKeyGeneration_A_r1
  1570: 0000000000088830  1696 FUNC    LOCAL  DEFAULT   12 gf2x_mod_inv
  2209: 00000000000893f0  1683 FUNC    LOCAL  DEFAULT   12 BIKE_L1_R3_crypto_kem_enc
  1547: 000000000007be20  1661 FUNC    LOCAL  DEFAULT   12 BIKE1_L1_R2_crypto_kem_keypair
   816: 00000000000c3640  1644 FUNC    LOCAL  DEFAULT   12 fpinv_chain_mont
   396: 000000000005f090  1590 FUNC    LOCAL  DEFAULT   12 s2n_client_key_share_recv
  1092: 000000000007b510  1552 FUNC    LOCAL  DEFAULT   12 BIKE1_L1_R1_crypto_kem_enc
  1260: 0000000000043550  1486 FUNC    LOCAL  DEFAULT   12 s2n_prf_key_expansion
  2115: 0000000000082c80  1465 FUNC    LOCAL  DEFAULT   12 gf2x_mul_base_pclmul
  2059: 00000000000a15c0  1395 FUNC    LOCAL  DEFAULT   12 s2n_kyber_512_r3_KeccakP1600times4_ExtractAndAddLanesAll
  2228: 0000000000053370  1377 FUNC    LOCAL  DEFAULT   12 s2n_record_parse_cbc
   404: 00000000000374f0  1365 FUNC    GLOBAL DEFAULT   12 s2n_config_add_ticket_crypto_key
  2673: 00000000000374f0  1365 FUNC    GLOBAL DEFAULT   12 s2n_config_add_ticket_crypto_key

alexw91 commented 2 years ago

Now that https://github.com/aws/s2n-tls/pull/3392 has been merged, and older PQ algorithms have been removed. Here are the current 50 largest symbols in s2n.

~/workspace/github/s2n/lib$ readelf -s --wide libs2n.so | sort -nr -k3 | head -50 
   248: 00000000000e0ce0 32768 OBJECT  LOCAL  DEFAULT   24 handshakes
   246: 00000000000d8ce0 32768 OBJECT  LOCAL  DEFAULT   24 tls13_handshakes
  1166: 0000000000087700 31563 FUNC    LOCAL  DEFAULT   12 s2n_kyber_512_r3_KeccakF1600times4_FastLoop_Absorb
   258: 00000000000e9d60 31488 OBJECT  LOCAL  DEFAULT   25 handshake_type_str
  1395: 000000000007c780 29740 FUNC    LOCAL  DEFAULT   12 s2n_kyber_512_r3_KeccakP1600times4_PermuteAll_24rounds
  1248: 000000000008f250 16859 FUNC    LOCAL  DEFAULT   12 s2n_kyber_512_r3_KeccakP1600times4_12rounds_FastLoop_Absorb
  1834: 0000000000083bb0 15182 FUNC    LOCAL  DEFAULT   12 s2n_kyber_512_r3_KeccakP1600times4_PermuteAll_12rounds
  1181: 000000000001ba00  4222 FUNC    LOCAL  DEFAULT   12 s2n_asn1_time_to_nano_since_epoch_ticks
  1808: 000000000004abd0  3697 FUNC    LOCAL  DEFAULT   12 s2n_record_writev
  1856: 0000000000054b90  3033 FUNC    LOCAL  DEFAULT   12 s2n_x509_validator_validate_cert_chain
   362: 0000000000077470  2990 FUNC    GLOBAL DEFAULT   12 s2n_strerror
  2431: 0000000000077470  2990 FUNC    GLOBAL DEFAULT   12 s2n_strerror
   275: 0000000000078020  2954 FUNC    GLOBAL DEFAULT   12 s2n_strerror_name
  2085: 0000000000078020  2954 FUNC    GLOBAL DEFAULT   12 s2n_strerror_name
   253: 00000000000451c0  2736 FUNC    LOCAL  DEFAULT   12 s2n_handshake_read_io
   438: 000000000004e9d0  2684 FUNC    GLOBAL DEFAULT   12 s2n_connection_wipe
  2298: 000000000004e9d0  2684 FUNC    GLOBAL DEFAULT   12 s2n_connection_wipe
   203: 000000000003a5e0  2566 FUNC    LOCAL  DEFAULT   12 s2n_deserialize_resumption_state
   662: 0000000000096dc0  2545 FUNC    LOCAL  DEFAULT   12 KeccakF1600_StatePermute
   392: 000000000005f4a0  2441 FUNC    LOCAL  DEFAULT   12 s2n_client_psk_recv
  1877: 00000000000467a0  2300 FUNC    LOCAL  DEFAULT   12 s2n_negotiate_impl
  1057: 00000000000d5e20  2208 OBJECT  LOCAL  DEFAULT   24 security_policy_selection
  1663: 0000000000059970  2169 FUNC    LOCAL  DEFAULT   12 s2n_server_hello_recv
   642: 00000000000bc200  2048 OBJECT  LOCAL  DEFAULT   14 idx
   327: 000000000005b600  2027 FUNC    LOCAL  DEFAULT   12 s2n_server_key_share_recv
   447: 0000000000041ec0  1961 FUNC    GLOBAL DEFAULT   12 s2n_error_get_alert
  2145: 0000000000041ec0  1961 FUNC    GLOBAL DEFAULT   12 s2n_error_get_alert
  1498: 0000000000032cf0  1834 FUNC    LOCAL  DEFAULT   12 s2n_parse_client_hello
   424: 0000000000061c50  1590 FUNC    LOCAL  DEFAULT   12 s2n_client_key_share_recv
  1020: 0000000000041700  1502 FUNC    LOCAL  DEFAULT   12 s2n_prf_key_expansion
  1615: 000000000007c200  1395 FUNC    LOCAL  DEFAULT   12 s2n_kyber_512_r3_KeccakP1600times4_ExtractAndAddLanesAll
  1741: 00000000000557c0  1377 FUNC    LOCAL  DEFAULT   12 s2n_record_parse_cbc
   413: 0000000000037260  1365 FUNC    GLOBAL DEFAULT   12 s2n_config_add_ticket_crypto_key
  2120: 0000000000037260  1365 FUNC    GLOBAL DEFAULT   12 s2n_config_add_ticket_crypto_key
   227: 000000000003ff50  1283 FUNC    LOCAL  DEFAULT   12 s2n_prf
   948: 00000000000bd1a0  1280 OBJECT  LOCAL  DEFAULT   14 s2n_kyber_512_r3_qdata
  1773: 00000000000529b0  1279 FUNC    LOCAL  DEFAULT   12 s2n_record_parse_aead
   676: 0000000000047cb0  1217 FUNC    LOCAL  DEFAULT   12 s2n_sendv_with_offset_impl
  1921: 0000000000074230  1215 FUNC    LOCAL  DEFAULT   12 s2n_hmac_init
   738: 0000000000045fb0  1182 FUNC    LOCAL  DEFAULT   12 s2n_conn_set_handshake_type
  1025: 00000000000324b0  1160 FUNC    LOCAL  DEFAULT   12 s2n_client_hello_send
  1427: 000000000003ce50  1129 FUNC    LOCAL  DEFAULT   12 s2n_decrypt_session_ticket
  1227: 000000000007b220  1128 FUNC    LOCAL  DEFAULT   12 s2n_kyber_512_r3_KeccakP1600times4_AddLanesAll
   683: 000000000006b950  1098 FUNC    LOCAL  DEFAULT   12 s2n_drbg_instantiate
   422: 0000000000061720  1097 FUNC    LOCAL  DEFAULT   12 s2n_client_key_share_send
   930: 000000000003d2c0  1084 FUNC    LOCAL  DEFAULT   12 s2n_decrypt_session_cache
   781: 000000000006de60  1081 FUNC    LOCAL  DEFAULT   12 s2n_evp_sign
  1101: 00000000000533d0  1078 FUNC    LOCAL  DEFAULT   12 s2n_client_cert_recv
   788: 000000000004c620  1072 FUNC    LOCAL  DEFAULT   12 s2n_tls13_server_nst_recv
   204: 000000000003aff0  1054 FUNC    LOCAL  DEFAULT   12 s2n_serialize_resumption_state

alexw91 commented 2 years ago

Out of curiosity, I locally applied the below patch, and the size of libs2n.so decreased from 1,084,160 to 937,528 bytes. A reduction of 13.5%. An improved patch would track the file and line number variables separately, and then write those values into s2n_debug_str at runtime when an error is encountered, but the simpler below patch gives an idea of how many bytes it could save.

diff --git a/error/s2n_errno.h b/error/s2n_errno.h
index a257500e..d3d2c920 100755
--- a/error/s2n_errno.h
+++ b/error/s2n_errno.h
@@ -298,7 +298,7 @@ extern __thread const char *s2n_debug_str;
 #define STRING_(s) TO_STRING(s)
 #define STRING__LINE__ STRING_(__LINE__)

-#define _S2N_DEBUG_LINE     "Error encountered in " __FILE__ ":" STRING__LINE__
+#define _S2N_DEBUG_LINE     "Error encountered"
 #define _S2N_ERROR( x )     do { s2n_debug_str = _S2N_DEBUG_LINE; s2n_errno = ( x ); s2n_calculate_stacktrace(); } while (0)
 #define S2N_ERROR_PRESERVE_ERRNO() do { return -1; } while (0)
 #define S2N_ERROR_IS_BLOCKING( x )    ( s2n_error_get_type(x) == S2N_ERR_T_BLOCKED )

camshaft commented 2 years ago

I've got a PR that does exactly that https://github.com/aws/s2n-tls/pull/3118

aws / s2n-tls