Let's assume for a second the password consisted of 20 genuinely random characters out of a character set of, say, 62 characters (lowercase/uppercase letters + numbers). That gives you 119 bits of entropy.

If you're the attacker and your goal is to do 1000 (≃ 2^10) rounds of SHA1 for each of those 2^119 potential passwords, couldn't you then just try to brute-force the 128-bit key directly, since 119 + 10 >= 128?

Put differently, wouldn't the statement "A fully random 20-character password has been cracked" amount to saying "AES-128 has been broken"?

You're underestimating the default PBKDF parameters used by LUKS1, `cryptsetup luksFormat` [1] benchmarks the `--pbkdf` function at runtime when configuring the keyslot, and the default iteration count is based on a target `--iter-time` [2], which is either 1s or 2s [3], unless overridden by the distro. I'm not entirely sure about the PRF (SHA1/256) used by LUKS1, it might be SHA-1 or SHA-256 [4].

For a LUKS1 image created with Ubuntu 18.04 on a i5-8265U ( Q3'18) CPU, that appears to result in an iteration count on the order of 1-2M. Assuming those hashcat benchmark numbers scale linearly on the iteration count, you're down to about 10kH/s for PBKDF2-HMAC-SHA1 or 5kH/s for PBKDF2-HMAC-SHA256.

Assuming 10kH/s, that drops you down to roughly 45 bits of entropy for 1k gpu-months, or 250k gpu-years to net 56 bits of entropy. Those would be on the order of [a-z0-9]{8} (41 bits), [a-zA-Z0-9]{8} (47 bits) or [a-z]{12} (56 bits).

OTOH it's easy to generate a 20-character password with far less entropy.

[1] https://man7.org/linux/man-pages/man8/cryptsetup-luksformat.... [2] https://wiki.archlinux.org/title/dm-crypt/Device_encryption#... [3] https://mirrors.edge.kernel.org/pub/linux/utils/cryptsetup/v... [4] https://gitlab.com/cryptsetup/cryptsetup/-/wikis/FrequentlyA...