botan: MacOS: botan built with Xcode-13 fails SHA-3 tests

Apple released Xcode-13. When Botan is built with it, it fails tests. Both master and release-2, in the same way. On all my Macs.

Branch release-2

Configuration

./configure.py --prefix=/opt/local --with-os-features=security_framework,apple_keychain,commoncrypto,getentropy --with-openmp --with-commoncrypto --with-openssl --with-boost --with-lzma --with-bzip2 --with-zlib --with-sqlite3 --with-python-version=2.7 --with-sphinx --with-pdf --cc-abi-flags='-march=native -O3 -I/opt/local/include' 2>&1 | tee conf-out.txt

Configuration output:

$ cat conf-out.txt 
   INFO: ./configure.py invoked with options "--prefix=/opt/local --with-os-features=security_framework,apple_keychain,commoncrypto,getentropy --with-openmp --with-commoncrypto --with-openssl --with-boost --with-lzma --with-bzip2 --with-zlib --with-sqlite3 --with-python-version=2.7 --with-sphinx --with-pdf --cc-abi-flags=-march=native -O3 -I/opt/local/include"
   INFO: Configuring to build Botan 2.18.1 (revision git:b420a4545b0f9219a88c209e4c8c2474d519dfac)
   INFO: Running under 3.9.7 (default, Sep  1 2021, 12:35:15) [Clang 12.0.5 (clang-1205.0.22.9)]
   INFO: Implicit --cc-bin=clang++ due to environment variable CXX
   INFO: Implicit --cxxflags=-std=gnu++17 -O3 -march=native -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk due to environment variable CXXFLAGS
   INFO: Autodetected platform information: OS="Darwin" machine="x86_64" proc="i386"
   INFO: Guessing target OS is darwin (use --os to set)
   INFO: Guessing target processor is a x86_64 (use --cpu to set)
   INFO: Using /etc/ssl/cert.pem as system certificate store
   INFO: Auto-detected compiler version 4.0
   INFO: Auto-detected compiler arch x86_64
   INFO: Target is clang:4.0-macos-x86_64
   INFO: Assuming target x86_64 is little endian
   INFO: Skipping (incompatible CPU): aes_armv8 aes_power8 sha1_armv8 sha2_32_armv8 sm4_armv8
   INFO: Skipping (incompatible OS): certstor_system_windows proc_walk win32_stats
   INFO: Skipping (requires external dependency): tpm
   INFO: Enabling use of external dependency boost
   INFO: Enabling use of external dependency bzip2
   INFO: Enabling use of external dependency commoncrypto
   INFO: Enabling use of external dependency lzma
   INFO: Enabling use of external dependency openssl
   INFO: Enabling use of external dependency sqlite3
   INFO: Enabling use of external dependency zlib
   INFO: Loading modules: adler32 aead aes aes_ni aes_vperm aont argon2 aria asio asn1 auto_rng base base32 base58 base64 bcrypt bcrypt_pbkdf bigint blake2 block blowfish boost bzip2 camellia cascade cast128 cast256 cbc cbc_mac ccm cecpq1 certstor_flatfile certstor_sql certstor_sqlite3 certstor_system certstor_system_macos cfb chacha chacha20poly1305 chacha_avx2 chacha_rng chacha_simd32 checksum cmac comb4p commoncrypto compression cpuid crc24 crc32 cryptobox ctr curve25519 des dev_random dh dl_algo dl_group dlies dsa dyn_load eax ec_group ecc_key ecdh ecdsa ecgdsa ecies eckcdsa ed25519 elgamal eme_oaep eme_pkcs1 eme_raw emsa1 emsa_pkcs1 emsa_pssr emsa_raw emsa_x931 entropy fd_unix ffi filters fpe_fe1 gcm getentropy ghash ghash_cpu ghash_vperm gmac gost_28147 gost_3410 gost_3411 hash hash_id hex hkdf hmac hmac_drbg hotp http_util idea idea_sse2 iso9796 kasumi kdf kdf1 kdf1_iso18033 kdf2 keccak keypair lion locking_allocator lzma mac mce mceies md4 md5 mdx_hash mem_pool mgf1 misty1 mode_pad modes mp newhope nist_keywrap noekeon noekeon_simd numbertheory ocb ofb openssl par_hash passhash9 pbes2 pbkdf pbkdf1 pbkdf2 pem pgp_s2k pk_pad pkcs11 poly1305 poly_dbl prf_tls prf_x942 processor_rng psk_db pubkey rc4 rdrand_rng rdseed rfc3394 rfc6979 rmd160 rng roughtime rsa salsa20 scrypt seed serpent serpent_avx2 serpent_simd sessions_sql sessions_sqlite3 sha1 sha1_sse2 sha1_x86 sha2_32 sha2_32_bmi2 sha2_32_x86 sha2_64 sha2_64_bmi2 sha3 sha3_bmi2 shacal2 shacal2_avx2 shacal2_simd shacal2_x86 shake shake_cipher simd simd_avx2 siphash siv skein sm2 sm3 sm4 socket sodium sp800_108 sp800_56a sp800_56c sqlite3 srp6 stateful_rng stream streebog system_rng thread_utils threefish_512 threefish_512_avx2 tiger tls tls_10 tls_cbc tss twofish utils uuid whirlpool x509 x919_mac xmss xtea xts zlib
   INFO: Using symlink to link files into build dir (use --link-method to change)
   INFO: Botan 2.18.1 (revision git:b420a4545b0f9219a88c209e4c8c2474d519dfac) (unreleased undated) build setup is complete

Build output: make-out.txt.gz

Tests output

.  .  .  .  .
1416a6f128a2567fdf10079d74d2f64aaa8e2834216c698118f69109580b0f61c6fc53fdd578276e4f6b1e8fb1e5cd04a2450620c1dca97c517dc81ecfbd3776fbb75b2f211ddef474304929e0a2ef57121ba873a145e7cec15d3af0605f6e9cbc84ff70e4072f9e694557c302e2c2bb3db14bd52707b47890731e0cf6181d297d012967c3fd561f905b8a4ba23487]
xmss_verify_invalid:
XMSS/SHA2_10_256 verify invalid signature ran 28 tests in 28.65 msec all ok
XMSS/SHA2_10_512 verify invalid signature ran 28 tests in 74.90 msec all ok
XMSS/SHA2_16_256 verify invalid signature ran 28 tests in 37.11 msec all ok
XMSS/SHA2_16_512 verify invalid signature ran 28 tests in 94.26 msec all ok
XMSS/SHA2_20_256 verify invalid signature ran 28 tests in 41.33 msec all ok
XMSS/SHA2_20_512 verify invalid signature ran 28 tests in 88.67 msec all ok
XMSS/SHAKE_10_256 verify invalid signature ran 28 tests in 25.33 msec all ok
XMSS/SHAKE_10_512 verify invalid signature ran 28 tests in 95.61 msec all ok
XMSS/SHAKE_16_256 verify invalid signature ran 28 tests in 53.11 msec all ok
XMSS/SHAKE_16_512 verify invalid signature ran 28 tests in 118.49 msec all ok
XMSS/SHAKE_20_256 verify invalid signature ran 28 tests in 31.91 msec all ok
XMSS/SHAKE_20_512 verify invalid signature ran 28 tests in 129.48 msec all ok
Tests complete ran 2858301 tests in 18.89 sec 17713 tests failed

Full output: make-out.txt.gz

Branch master

Configuration

./configure.py --prefix=/opt/local --with-os-features=security_framework,apple_keychain,commoncrypto,getentropy --with-commoncrypto --with-openssl --with-boost --with-lzma --with-bzip2 --with-zlib --with-sqlite3 --with-python-version=3.9 --with-sphinx --with-pdf --system-cert-bundle=/opt/local/share/curl/curl-ca-bundle.crt --cc-abi-flags='-march=native -O3 -I/opt/local/include' 2>&1 | tee conf-out.txt

Output:

$ cat conf-out.txt 
   INFO: ./configure.py invoked with options "--prefix=/opt/local --with-os-features=security_framework,apple_keychain,commoncrypto,getentropy --with-commoncrypto --with-openssl --with-boost --with-lzma --with-bzip2 --with-zlib --with-sqlite3 --with-python-version=3.9 --with-sphinx --with-pdf --system-cert-bundle=/opt/local/share/curl/curl-ca-bundle.crt --cc-abi-flags=-march=native -O3 -I/opt/local/include"
   INFO: Configuring to build Botan 3.0.0-alpha0 (revision git:20e87b077c113744600510c431af1396663260a0)
   INFO: Running under 3.9.7 (default, Sep  1 2021, 12:35:15) [Clang 12.0.5 (clang-1205.0.22.9)]
   INFO: Implicit --cc-bin=clang++ due to environment variable CXX
   INFO: Implicit --cxxflags=-std=gnu++17 -O3 -march=native -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk due to environment variable CXXFLAGS
   INFO: Autodetected platform information: OS="Darwin" machine="x86_64" proc="i386"
   INFO: Guessing target OS is darwin (use --os to set)
   INFO: Guessing target processor is a x86_64 (use --cpu to set)
   INFO: Auto-detected compiler version 4.0
   INFO: Auto-detected compiler arch x86_64
   INFO: Target is clang:4.0-macos-x86_64
   INFO: Assuming target x86_64 is little endian
   INFO: Skipping (incompatible CPU): aes_armv8 aes_power8 sha1_armv8 sha2_32_armv8 shacal2_armv8 sm4_armv8
   INFO: Skipping (incompatible OS): certstor_system_windows win32_stats
   INFO: Skipping (requires external dependency): tpm
   INFO: Enabling use of external dependency boost
   INFO: Enabling use of external dependency bzip2
   INFO: Enabling use of external dependency commoncrypto
   INFO: Enabling use of external dependency lzma
   INFO: Enabling use of external dependency openssl
   INFO: Enabling use of external dependency sqlite3
   INFO: Enabling use of external dependency zlib
   INFO: Loading modules: adler32 aead aes aes_ni aes_vperm argon2 argon2fmt aria asio asn1 auto_rng base base32 base58 base64 bcrypt bcrypt_pbkdf bigint blake2 blake2mac block blowfish boost bzip2 camellia cascade cast128 cbc ccm cecpq1 certstor_flatfile certstor_sql certstor_sqlite3 certstor_system certstor_system_macos cfb chacha chacha20poly1305 chacha_avx2 chacha_rng chacha_simd32 checksum cmac comb4p commoncrypto compression cpuid crc24 crc32 cryptobox ctr curve25519 des dh dl_algo dl_group dlies dsa dyn_load eax ec_group ec_h2c ecc_key ecdh ecdsa ecgdsa ecies eckcdsa ed25519 elgamal eme_oaep eme_pkcs1 eme_raw emsa1 emsa_pkcs1 emsa_pssr emsa_raw emsa_x931 entropy fd_unix ffi filters fpe_fe1 gcm getentropy ghash ghash_cpu ghash_vperm gmac gost_28147 gost_3410 gost_3411 hash hash_id hex hkdf hmac hmac_drbg hotp http_util idea idea_sse2 iso9796 kdf kdf1 kdf1_iso18033 kdf2 keccak keypair lion locking_allocator lzma mac mce md4 md5 mdx_hash mem_pool mgf1 mode_pad modes mp newhope nist_keywrap noekeon noekeon_simd numbertheory ocb ofb openssl par_hash passhash9 pbes2 pbkdf pbkdf2 pem pgp_s2k pk_pad pkcs11 poly1305 poly_dbl prf_tls prf_x942 processor_rng psk_db pubkey rc4 rdseed rfc3394 rfc6979 rmd160 rng roughtime rsa salsa20 scrypt seed serpent serpent_avx2 serpent_simd sessions_sql sessions_sqlite3 sha1 sha1_sse2 sha1_x86 sha2_32 sha2_32_bmi2 sha2_32_x86 sha2_64 sha2_64_bmi2 sha3 sha3_bmi2 shacal2 shacal2_avx2 shacal2_simd shacal2_x86 shake shake_cipher simd simd_avx2 siphash siv skein sm2 sm3 sm4 socket sodium sp800_108 sp800_56a sp800_56c sqlite3 srp6 stateful_rng stream streebog system_rng thread_utils threefish_512 threefish_512_avx2 tls tls_cbc tss twofish utils uuid whirlpool x509 x919_mac xmss xts zlib
   INFO: Using symlink to link files into build dir (use --link-method to change)
   INFO: Botan 3.0.0-alpha0 (revision git:20e87b077c113744600510c431af1396663260a0) (unreleased undated) build setup is complete

Build output: make-out.txt.gz

Tests

.  .  .  .  .
c81ecfbd3776fbb75b2f211ddef474304929e0a2ef57121ba873a145e7cec15d3af0605f6e9cbc84ff70e4072f9e694557c302e2c2bb3db14bd52707b47890731e0cf6181d297d012967c3fd561f905b8a4ba23487 
xmss_verify_invalid:
XMSS/SHA2_10_256 verify invalid signature ran 28 tests in 34.19 msec all ok
XMSS/SHA2_10_512 verify invalid signature ran 28 tests in 69.04 msec all ok
XMSS/SHA2_16_256 verify invalid signature ran 28 tests in 34.38 msec all ok
XMSS/SHA2_16_512 verify invalid signature ran 28 tests in 94.06 msec all ok
XMSS/SHA2_20_256 verify invalid signature ran 28 tests in 40.87 msec all ok
XMSS/SHA2_20_512 verify invalid signature ran 28 tests in 79.71 msec all ok
XMSS/SHAKE_10_256 verify invalid signature ran 28 tests in 30.20 msec all ok
XMSS/SHAKE_10_512 verify invalid signature ran 28 tests in 83.43 msec all ok
XMSS/SHAKE_16_256 verify invalid signature ran 28 tests in 46.80 msec all ok
XMSS/SHAKE_16_512 verify invalid signature ran 28 tests in 130.14 msec all ok
XMSS/SHAKE_20_256 verify invalid signature ran 28 tests in 29.96 msec all ok
XMSS/SHAKE_20_512 verify invalid signature ran 28 tests in 121.47 msec all ok
Tests complete ran 2850756 tests in 18.28 sec 17713 tests failed (in entropy hash hash_rep mac newhope stream xmss_sign xmss_verify)

Full output: test-out.txt.gz

About this issue

  • Original URL
  • State: closed
  • Created 3 years ago
  • Comments: 30 (12 by maintainers)

Most upvoted comments

I merged a commit upstream on Monday that may fix this: https://reviews.llvm.org/D106613

+3
vtjnash on Sep 29, 2021 
Tests complete ran 2675970 tests in 8.54 sec all tests ok

🎉🎉

+2
reneme on Sep 24, 2021

Here’s a minimal example (that doesn’t depend on Botan), reproducing the discrepancy.

With -O1 (and apple clang 13) it works fine and the assertions at the end check out; for -O2 and above they don’t. 🤡

#include <cstdint>
#include <cassert>

template<size_t ROT, typename T>
inline constexpr T rotl(T input)
   {
   static_assert(ROT > 0 && ROT < 8*sizeof(T), "Invalid rotation constant");
   return static_cast<T>((input << ROT) | (input >> (8*sizeof(T) - ROT)));
   }

inline void SHA3_round(uint64_t T[25], const uint64_t A[25], uint64_t RC)
   {
   const uint64_t C0 = A[0] ^ A[5] ^ A[10] ^ A[15] ^ A[20];
   const uint64_t C1 = A[1] ^ A[6] ^ A[11] ^ A[16] ^ A[21];

   // the calculation of C2 fails for -O3 or -O2 with clang 12
   // FWIW: it would produce a value that doesn't fit into a _signed_ 64-bit int
   const uint64_t C2 = A[2] ^ A[7] ^ A[12] ^ A[17] ^ A[22];

   const uint64_t C3 = A[3] ^ A[8] ^ A[13] ^ A[18] ^ A[23];
   const uint64_t C4 = A[4] ^ A[9] ^ A[14] ^ A[19] ^ A[24];

   const uint64_t D0 = rotl<1>(C0) ^ C3;
   const uint64_t D1 = rotl<1>(C1) ^ C4;
   const uint64_t D2 = rotl<1>(C2) ^ C0;
   const uint64_t D3 = rotl<1>(C3) ^ C1;
   const uint64_t D4 = rotl<1>(C4) ^ C2;

   const uint64_t B00 =          A[ 0] ^ D1;
   const uint64_t B01 = rotl<44>(A[ 6] ^ D2);
   const uint64_t B02 = rotl<43>(A[12] ^ D3);
   const uint64_t B03 = rotl<21>(A[18] ^ D4);
   const uint64_t B04 = rotl<14>(A[24] ^ D0);
   T[ 0] = B00 ^ (~B01 & B02) ^ RC;
   T[ 1] = B01 ^ (~B02 & B03);
   T[ 2] = B02 ^ (~B03 & B04);
   T[ 3] = B03 ^ (~B04 & B00);
   T[ 4] = B04 ^ (~B00 & B01);

   const uint64_t B05 = rotl<28>(A[ 3] ^ D4);
   const uint64_t B06 = rotl<20>(A[ 9] ^ D0);
   const uint64_t B07 = rotl< 3>(A[10] ^ D1);
   const uint64_t B08 = rotl<45>(A[16] ^ D2);
   const uint64_t B09 = rotl<61>(A[22] ^ D3);
   T[ 5] = B05 ^ (~B06 & B07);
   T[ 6] = B06 ^ (~B07 & B08);
   T[ 7] = B07 ^ (~B08 & B09);
   T[ 8] = B08 ^ (~B09 & B05);
   T[ 9] = B09 ^ (~B05 & B06);

   // --- instructions starting from here can be removed
   //     and the -O3 dicrepancy is still triggered

   const uint64_t B10 = rotl< 1>(A[ 1] ^ D2);
   const uint64_t B11 = rotl< 6>(A[ 7] ^ D3);
   const uint64_t B12 = rotl<25>(A[13] ^ D4);
   const uint64_t B13 = rotl< 8>(A[19] ^ D0);
   const uint64_t B14 = rotl<18>(A[20] ^ D1);
   T[10] = B10 ^ (~B11 & B12);
   T[11] = B11 ^ (~B12 & B13);
   T[12] = B12 ^ (~B13 & B14);
   T[13] = B13 ^ (~B14 & B10);
   T[14] = B14 ^ (~B10 & B11);

   const uint64_t B15 = rotl<27>(A[ 4] ^ D0);
   const uint64_t B16 = rotl<36>(A[ 5] ^ D1);
   const uint64_t B17 = rotl<10>(A[11] ^ D2);
   const uint64_t B18 = rotl<15>(A[17] ^ D3);
   const uint64_t B19 = rotl<56>(A[23] ^ D4);
   T[15] = B15 ^ (~B16 & B17);
   T[16] = B16 ^ (~B17 & B18);
   T[17] = B17 ^ (~B18 & B19);
   T[18] = B18 ^ (~B19 & B15);
   T[19] = B19 ^ (~B15 & B16);

   const uint64_t B20 = rotl<62>(A[ 2] ^ D3);
   const uint64_t B21 = rotl<55>(A[ 8] ^ D4);
   const uint64_t B22 = rotl<39>(A[14] ^ D0);
   const uint64_t B23 = rotl<41>(A[15] ^ D1);
   const uint64_t B24 = rotl< 2>(A[21] ^ D2);
   T[20] = B20 ^ (~B21 & B22);
   T[21] = B21 ^ (~B22 & B23);
   T[22] = B22 ^ (~B23 & B24);
   T[23] = B23 ^ (~B24 & B20);
   T[24] = B24 ^ (~B20 & B21);
   }

int main()
{
    uint64_t T[25];

    uint64_t A[25] = {
        15515230172486u, 9751542238472685244u, 220181482233372672u,
        2303197730119u, 9537012007446913720u, 0u, 14782389640143539577u,
        2305843009213693952u, 1056340403235818873u, 16396894922196123648u,
        13438274300558u, 3440198220943040u, 0u, 3435902021559310u, 64u,
        14313837075027532897u, 32768u, 6880396441885696u, 14320469711924527201u,
        0u, 9814829303127743595u, 18014398509481984u, 14444556046857390455u,
        4611686018427387904u, 18041275058083100u };

    SHA3_round(T, A, 0x0000000000008082);

    assert(T[0]  == 16394434931424703552u);
    assert(T[1]  == 10202638136074191489u);
    assert(T[2]  == 6432602484395933614u);
    assert(T[3]  == 10616058301262943899u);
    assert(T[4]  == 14391824303596635982u);
    assert(T[5]  == 5673590995284149638u);
    assert(T[6]  == 15681872423764765508u);
    assert(T[7]  == 11470206704342013341u);
    assert(T[8]  == 8508807405493883168u);
    assert(T[9]  == 9461805213344568570u);
    assert(T[10] == 8792313850970105187u);
    assert(T[11] == 13508586629627657374u);
    assert(T[12] == 5157283382205130943u);
    assert(T[13] == 375019647457809685u);
    assert(T[14] == 9294608398083155963u);
    assert(T[15] == 16923121173371064314u);
    assert(T[16] == 4737739424553008030u);
    assert(T[17] == 5823987023293412593u);
    assert(T[18] == 13908063749137376267u);
    assert(T[19] == 13781177305593198238u);
    assert(T[20] == 9673833001659673401u);
    assert(T[21] == 17282395057630454440u);
    assert(T[22] == 12906624984756985556u);
    assert(T[23] == 3081478361927354234u);
    assert(T[24] == 93297594635310132u);

    return 0;
}
+2
reneme on Sep 23, 2021

For what it’s worth: The clang (trunk) build available on Compiler Explorer indeed produces the correct output. As of this writing, the clang (trunk) build was fcdefc8 committed earlier today and hence probably included your upstream change from Monday. Thanks a lot, everybody!

+1
reneme on Oct 1, 2021

Okay, this is becoming a goose chase, I’m afraid. I compared the input values in A of the above mentioned second invocation of SHA3_round() in the first iteration of the for loop in SHA_3::permute(). The 25 array values are consistent across -O0 and -O3. However, the first value to deviate is C2 calculated here. Again: the input values in A are the same for -O0 and -O3, I compared it time and again. Though C2 is “16961422039339595127” for -O0 and 2528292126282103808 for -O3 (and -O2, FWIW).

Enough for today…

+1
reneme on Sep 23, 2021

Turns out: After moving SHA3_round() into another compilation unit (avoiding the inline) the problem persists. But if I exclusively rebuild the new compilation unit (containing SHA3_round()) and relink the rest, the result is correct. So the optimizer seems to trip over the bitshift stuff in SHA3_round() after all.

+1
reneme on Sep 23, 2021
Read more comments on GitHub
← botan: MacOS 10.15: system RNG test crashes
botan: Segfault when running botan-test under Debian X32 →