liblzma backdoor strings extracted from 5.6.1 (from a built-in trie)

hashes.txt

0810 b' from '
0678 b' ssh2'
00d8 b'%.48s:%.48s():%d (pid=%ld)\x00'
0708 b'%s'
0108 b'/usr/sbin/sshd\x00'
0870 b'Accepted password for '
01a0 b'Accepted publickey for '
0c40 b'BN_bin2bn\x00'
06d0 b'BN_bn2bin\x00'
0958 b'BN_dup\x00'
0418 b'BN_free\x00'
04e0 b'BN_num_bits\x00'
0790 b'Connection closed by '
0018 b'Could not chdir to home directory %s: %s\n\x00'
00b0 b'Could not get agent socket\x00'
0960 b'DISPLAY='
09d0 b'DSA_get0_pqg\x00'
0468 b'DSA_get0_pub_key\x00'
07e8 b'EC_KEY_get0_group\x00'
0268 b'EC_KEY_get0_public_key\x00'
06e0 b'EC_POINT_point2oct\x00'
0b28 b'EVP_CIPHER_CTX_free\x00'
0838 b'EVP_CIPHER_CTX_new\x00'
02a8 b'EVP_DecryptFinal_ex\x00'
0c08 b'EVP_DecryptInit_ex\x00'
03f0 b'EVP_DecryptUpdate\x00'
00f8 b'EVP_Digest\x00'
0408 b'EVP_DigestVerify\x00'
0118 b'EVP_DigestVerifyInit\x00'
0d10 b'EVP_MD_CTX_free\x00'
0af8 b'EVP_MD_CTX_new\x00'
06f8 b'EVP_PKEY_free\x00'
0758 b'EVP_PKEY_new_raw_public_key\x00'
0510 b'EVP_PKEY_set1_RSA\x00'
0c28 b'EVP_chacha20\x00'
0c60 b'EVP_sha256\x00'
0188 b'EVP_sm'
08c0 b'GLIBC_2.2.5\x00'
06a8 b'GLRO(dl_naudit) <= naudit\x00'
01e0 b'KRB5CCNAME\x00'
0cf0 b'LD_AUDIT='
0bc0 b'LD_BIND_NOT='
0a90 b'LD_DEBUG='
0b98 b'LD_PROFILE='
03e0 b'LD_USE_LOAD_BIAS='
0a88 b'LINES='
0ac0 b'RSA_free\x00'
0798 b'RSA_get0_key\x00'
0918 b'RSA_new\x00'
01d0 b'RSA_public_decrypt\x00'
0540 b'RSA_set0_key\x00'
08f8 b'RSA_sign\x00'
0990 b'SSH-2.0'
04a8 b'TERM='
00e0 b'Unrecognized internal syslog level code %d\n\x00'
0158 b'WAYLAND_DISPLAY='
0878 b'__errno_location\x00'
02b0 b'__libc_stack_end\x00'
0228 b'__libc_start_main\x00'
0a60 b'_dl_audit_preinit\x00'
09c8 b'_dl_audit_symbind_alt\x00'
08a8 b'_exit\x00'
05b0 b'_r_debug\x00'
05b8 b'_rtld_global\x00'
0a98 b'_rtld_global_ro\x00'
00b8 b'auth_root_allowed\x00'
01d8 b'authenticating'
0028 b'demote_sensitive_data\x00'
0348 b'getuid\x00'
0a48 b'ld-linux-x86-64.so'
07d0 b'libc.so'
07c0 b'libcrypto.so'
0590 b'liblzma.so'
0938 b'libsystemd.so'
0020 b'list_hostkey_types\x00'
0440 b'malloc_usable_size\x00'
00c0 b'mm_answer_authpassword\x00'
00c8 b'mm_answer_keyallowed\x00'
00d0 b'mm_answer_keyverify\x00'
0948 b'mm_answer_pam_start\x00'
0078 b'mm_choose_dh\x00'
0040 b'mm_do_pam_account\x00'
0050 b'mm_getpwnamallow\x00'
00a8 b'mm_log_handler\x00'
0038 b'mm_pty_allocate\x00'
00a0 b'mm_request_send\x00'
0048 b'mm_session_pty_cleanup2\x00'
0070 b'mm_sshpam_free_ctx\x00'
0058 b'mm_sshpam_init_ctx\x00'
0060 b'mm_sshpam_query\x00'
0068 b'mm_sshpam_respond\x00'
0030 b'mm_terminate\x00'
0c58 b'parse PAM\x00'
0400 b'password\x00'
04f0 b'preauth'
0690 b'pselect\x00'
07b8 b'publickey\x00'
0308 b'read\x00'
0710 b'rsa-sha2-256\x00'
0428 b'setlogmask\x00'
05f0 b'setresgid\x00'
0ab8 b'setresuid\x00'
0760 b'shutdown\x00'
0d08 b'ssh-2.0'
02c8 b'[email protected]\x00'
0088 b'sshpam_auth_passwd\x00'
0090 b'sshpam_query\x00'
0080 b'sshpam_respond\x00'
0098 b'start_pam\x00'
09f8 b'system\x00'
0198 b'unknown\x00'
0b10 b'user'
0380 b'write\x00'
0010 b'xcalloc: zero size\x00'
0b00 b'yolAbejyiejuvnup=Evjtgvsh5okmkAvj\x00'
0300 b'\x7fELF'

May anyone elaborate on the "builtin trie" part? I know what a trie is, but builtin how? How did this backdoor make use of it this trie or have the trie builtin in the first place? Any details on how it works?

That means the trie was built at compile time and stored directly inside the binary file. It's a normal trie, just instead of making it in memory at runtime, it's built-in the binary.