How is LUKS dm-crypt secure if the key is stored with the encrypted data? I've posted this question over at superuser, but haven't had any success at getting answers. That's why I've posted it here. Furthermore, I believe this is a more appropriate place for it as it is questions about design of the encryption system and not about its usage.

How is LUKS dm-crypt secure if the key is stored with the encrypted data? To me, this seems like hanging a door key on the door it locks. Is a passphrase enough to secure it?

And a continuation: If it is secure to keep the key with the encrypted partition/container, am I correct in assuming that LUKS header backups can also be treated as normal files and not secret data?
The key is not stored with the encrypted data, the encrypted key is. This is part of the header. In short, when the volume is created a random key (the master key) is generated and this random key is encrypted using a key derived from the passphrase, and spread out (using an algorithm called 'afsplit'). This key derivation is designed to take a relatively long time (half a second or so), so it's relatively expensive to try passphrases as an attacker.
By design the system's security depends on the passphrase's quality; a bad passphrase is somewhat protected due to the long time per try, but would fail in the end. The header also contains an independent check to see that the passphrase that was entered has resulted in the correct master key.

The header is not secret but essential to open the volume: it contains all the parameters that have been used when the volume was created, so that (with a correct passphrase) the master key can be recomputed from the header (and this key is used to decrypt the actual file system data). So it's always stored with the data. It is recommended to backup the header (to a separate system, say a USB drive), but this is just to prevent data loss when the header would get corrupted (if a bit is changed, you cannot recompute the correct master key any more).