I'm wondering if XTS is used (Random Access is needed) what the best solution for authentication is. If I wouldn't need random access, I would take AES-GCM or AES-CBC-HMAC but random access is a must.

What mode of operation would be prefered for random access with authentication?

  • $\begingroup$ You need to do chunking yourself to get that or use one of these super-advanced modes that allow intermediate tags to be computed. $\endgroup$ – SEJPM Jan 22 '19 at 16:50
  • $\begingroup$ I assume you mean "random access" by "decrypting arbitrary part of ciphertext, operate on it, and securely encrypting it again". $\endgroup$ – DannyNiu Jan 23 '19 at 9:23
  • $\begingroup$ @SEJPM: what are these super-advanced modes? $\endgroup$ – 0xcd Jan 23 '19 at 9:45
  • $\begingroup$ @DannyNiu: Yes, decrypt and encrypt on a random place. The place is aligned with the size of a block. So we can say we need access (read/write) to a specific block. $\endgroup$ – 0xcd Jan 23 '19 at 9:46
  • 1
    $\begingroup$ One of the ciphers which have the entry for "intermediate tags" set in table 2 of this paper. Though note that I think none of these ciphers actually made it to the finalist selection. $\endgroup$ – SEJPM Jan 23 '19 at 19:01

I assume you mean "random access" by "decrypting arbitrary part of ciphertext, operate on it, and securely encrypting it again".

The XTS mode is designed as a "Full-Disk Encryption" mode, which means it does not have the slightest concern with authentication.

From practical perspective, I recommend having a keyed tuple or tree hashing mode for authentication. Some of which are specified in NIST SP 800-185. You may also want to check out Sakura tree-hashing encoding scheme.


Tuple hashing is a hashing scheme, where a sequence of bit/octet strings is hashed in such way, that guarantees the uniqueness of the output, even when otherwise their simple concatenation would have resulted in some ambiguity. For example, hashing the concatenation of "ab" + "c" would be the same as "a" + "bc", but the tuple hashing of $(\text{"ab"}, \text{"c"})$ would be different from $(\text{"a"}, \text{"bc"})$.

Tuple hashing is usually sequential, but it doesn't always have to be.

Tree hashing is an efficiently method for hashing long messages. Example include Merkle tree. During the SHA-3 competition, the Keccak team proposed the Sakura tree-hashing encoding scheme, to solve the shortcomings of various ad-hoc tree-hashing encodings.

I added the "keyed" in the previous text to mean that they're supposed to be used as authentication tag.

  • $\begingroup$ Can you explain me alitle more about these "keyed tuple or tree hashing mode"? I'm not sure if I understand the keyed tuple right and I don't know what tree hashing is. $\endgroup$ – 0xcd Jan 23 '19 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.