[cryptography] "stream MAC" - does anything like it exist?

Steven Bellovin smb at cs.columbia.edu
Sun Sep 12 18:03:54 EDT 2010

On Sep 10, 2010, at 2:06 18PM, travis+ml-rbcryptography at subspacefield.org wrote:

> So there's an obvious (though imperfect) analogy between block ciphers
> and, say, HMAC.  Imperfect because authentication always seems to
> involve metadata.
> But is there a MAC analog to a stream cipher?  That is, something
> where you can spend a few bits authenticating each frame of a movie,
> or sound sample, for example, and have some probabilistic chance of
> detecting alteration at each frame.  I suppose it could also have uses
> with, say, an interactive SSH session, where each keystroke might be
> sent in its own packet.
> The closest thing I can think of is doing a truncated MAC on each
> frame.  Looking at HMAC, it looks like you could leave the inner hash
> running while also finalizing it for each frame (assuming your library
> supports this), so that you could keep it open to feed the next frame
> to it - this allows each truncated MAC to attest to the authenticity
> of prior frames, which might or might not allow you to get by with
> fewer bits of MAC per frame in certain applications (details of which
> are complicated and not particularly germane to this query).

I confess I'm not sure I understand what properties you're actually
looking forthat aren't handled by the truncated MAC you describe.
(I'd also that unless your frames are very small, truncation doesn't
buy you much.)  Are you looking for chaining properties between frames?
What are they?  (Stream ciphers don't have such, of course.)  Do you
want to MAC each frame with some probability, then get a strong MAC
on a group of frames?  I note that no matter the algorithm, the basic
properties are pretty obvious: if you have an N-bit authentication
field, the odds on a random field being accepted are 2^-N.  What else
do you want?

		--Steve Bellovin, http://www.cs.columbia.edu/~smb

More information about the cryptography mailing list