2
$\begingroup$

I have been looking into the CAESAR submissions as I'm interested in a cipher that can process a stream of unknown or large size (E.g. socket, file) while providing authentication. My understanding is that the current standard approach is for the application to slice the data into blocks and use some well-known AEAD mode like GCM (including the chunk number to prevent block suppression, duplication, and reordering).

However, ciphers like Keyak v2 take care of this by themselves by supporting intermediate tags, which combined with being online makes for a good fit for the above use case. Note that tags in Keyak v2 authenticate all plaintext chunks prior to that tag, thus protecting against suppression, duplication, and reordering of intermediate chunks; also worth mentioning that this is a Encrypt-and-MAC approach.

All this got me thinking of potential attacks against ciphers making use of intermediate tags. The way Keyak v2 is designed an attacker can't remove intermediate chunks from the ciphertext, but (s)he would be able to remove as many blocks as (s)he wanted starting from the back. This is interesting as is something you can't do against for example GCM because the MAC is applied over the whole ciphertext. A (contrived, I know) example would be for an attacker to remove the last blocks of the transmission of a number:

Original Ciphertext: 1000|Tag1|0000|Tag2 Modified Cipphertext: 1000|Tag1

The victim would have no way to detect such ciphertext modification as long as the removal of the block doesn't break the semantics of the underlying protocol (like in this example). I know that this is also possible if you're slicing the data at the application level and using GCM, but I expected the likes of Keyak v2 to solve it somehow. Unless I am missing something important, this looks like a relatively big downside of intermediate tags.

What's wrong with my reasoning? Is this just a risk we have to assume if we want to process streams in this way?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I'm not familiar with Keyak, but a simple way to solve this issue would be to calculate the last authentication tag in some slightly different manner than the previous ones (e.g. just including a single "this is the last chunk" bit as associated input data). That way, truncating the message would cause the verification of the new last chunk to fail, since that chunk was not originally tagged as the last one. $\endgroup$
    – Ilmari Karonen
    Sep 17 '16 at 20:53
  • $\begingroup$ Wouldn't that defeat the purpose? The receiver would have to hold off from using any data until the last chunk was received. $\endgroup$
    – Adrian
    Sep 20 '16 at 17:05
  • 2
    $\begingroup$ There can be no scheme that would let the receiver verify the integrity of the entire message before they've actually received the whole message – a bit of thought should show why that's logically impossible. The best any progressive scheme can do is 1) let the receiver know that the parts received so far haven't been tampered with, and 2) once the whole message has been received, prove that no part of it has been omitted. If it is not safe for the receiver to process any part of the message before all of it has been verified, then the receiver must indeed buffer the whole message. $\endgroup$
    – Ilmari Karonen
    Sep 20 '16 at 17:13
  • $\begingroup$ Yeah, that makes sense. The gist of my original question was to verify that assumption. However, the introduction of intermediate tags seems to be useless if the receiver can't securely use the message until it has been received completely, unless the benefit resides in how much data you have to keep in memory at any given point. Other than that, you may as well use plain AES-GCM with its single tag at the end of the data stream and obtain the same security, right? $\endgroup$
    – Adrian
    Sep 20 '16 at 17:20
  • 1
    $\begingroup$ There are a number of practical advantages to incremental authentication. One is that the sender doesn't need to buffer the full message; this is particularly relevant for two-pass modes like SIV, where one would normally be unable to even begin encryption before the MAC has been fully computed. Also, for many purposes (like, say, encrypted audio/video streaming), it may be acceptable to begin processing the message even before the receiver knows that it has been fully received; an incremental authentication scheme still guarantees that they at least have a prefix of an authentic message. $\endgroup$
    – Ilmari Karonen
    Sep 20 '16 at 17:43
1
$\begingroup$

As the specification of Keyak v2 explains:

To produce a tag that depends on the full message and not only on the message bits that have been injected in a single duplex instance, Motorist performs some dedicated processing at the end of each message called a knot. It extracts chaining values from each duplex instance, concatenates them, and injects them into all duplex instances. This makes the state of all duplex instances depend on the full sequence of messages. Then it extracts a tag from a single duplex object.

right within chapter 1 (emphasis mine). Note that Motorist is the underlying construction of Keyak 2.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you elaborate? I don't see how that is compatible with intermediate tags and releasing ciphertext by chunks as the tag that depends on the full message needs the full message to be processed before it can be calculated. Does this mean that there is a 'final block' that the receiver expects and that if the communication ends before that an error is returned? $\endgroup$
    – Adrian
    Sep 16 '16 at 11:59
  • $\begingroup$ The idea of a 'final block' would somewhat defeat the purpose of intermediate tags by forcing the receiver to wait for the full stream, wouldn't it? $\endgroup$
    – Adrian
    Sep 16 '16 at 12:08

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.