I am building an encrypted NAS with 4 x 4TB hard drives and was wondering what the limit of 256 bit AES is when implemented via cryptsetup and luksFormat. As I understand it, the maximum plaintext size for 256 bit AES is 2^39 - 256 bits, but I'm not sure what that means in relation to how cryptsetup works. At face value my interpretation is that if you're dealing with a drive any larger than 68 GB's then you need something stronger than AES 256. However I'm sure there's reasons that's not the case considering bitlocker uses 128 and 256 bit regardless of volume size. Any insight on this is appreciated as I only thought of this AFTER establishing my NAS and am dreading the process of re-encrypting the drives.
AES is a block cipher. Wikipedia says:
The winner of the AES contest, Rijndael, supports block and key sizes of 128, 192, and 256 bits, but in AES the block size is always 128 bits. The extra block sizes were not adopted by the AES standard.
So AES 256 means Rijndael with a 128 bit block size and a 256 bit key.
The maximum size of data a block cipher can safely encrypt under the same key depends on it's block size, because the more blocks you encrypt with it, the larger the chance that two blocks will be the same. This will start leaking information the more it happens, so you want to avoid it.
However, the key size does not affect the number of blocks you can safely encrypt. So even if there was an AES-512, it wouldn't do anything to increase the maximum size of the plaintext you can encrypt.
Since AES block size is 128 bits (16 bytes) and thanks to the birthday paradox you can expect an identical block appearing after having encrypted about 2^64 (the square root of 2^128) blocks, so you might start to worry when you get in the region of encrypting 2^64 * 16 bytes with the same key.
Of course, that's not a hard limit. It's just that the likelihood that you're leaking information useful in breaking the encryption increases. You might be totally fine encrypting way more than that, or you might want to worry much earlier than that. But AES is completely fine for encrypting 4 or even 16 TB of data.
As for AES 512, maybe you're refering to a 512 bit key that gets split into two 256 bit parts for LUKS in aes-xts-plain mode? The man page of cryptsetup states:
For XTS mode you can optionally set a key size of 512 bits with the -s option. Key size for XTS mode is twice that for other modes for the same security level.
This means that in order to get the security of a 256 bit key, you need to specify a key size of 512 bits for XTS. You need double sized keys because in XTS mode AES is used twice, and each invocation uses one half of the key (see Explanation of the XTS Encryption Mode).