Using the output of a stream cipher, how to guarantee the integrity of 4 bytes of data? I am designing a simple and secure stream communication protocol. My idea was to build each message sent to the wire as:

(message size || clear text || UHASH(message size || clear text)) $\oplus$ unique stream cipher output

where UHASH is the main function from UMAC (see question Using UMAC with stream cypher), || is concatenation and $\oplus$ is exclusive or.

The problem is that I found it was very easy to DoS attack my system; all it takes is to flip a high order bit of the 4 byte message size, and the receiver will wait for a multiple gigabyte message before having the chance to verify the MAC.

My solution is, if the message is bigger than some reasonably small size, I will add a MAC just after the size, validating it, so no very long message will be expected without validation. It seems to work, but given the overhead of calculated a 8 bytes keyed MAC from a 4 byte value, I wondered if there is any simple way of guaranteeing the integrity of such a small value using only a stream cypher and a few bytes more than the value I want to protect.

Do you know of any? For instance, let $\times$ be multiplication mod $2^{32}$, sending such a header:

(message size $\oplus$ cipher output 1) || (message size $\times$ cipher output 2)

would solve my problem? I understand that the probability of forgery can not be smaller than $1 / 2^{n} $ for the n extra verifications bits I send, but how to guarantee this chance is close to the minimum?
So you have a small integer, and you want to transmit it in such a way that (a) you don't particularly care if the attacker finds out what that integer is, but (b) no matter what the attacker changes or substitutes, you don't want the receiver to be tricked into thinking you sent some other number (in particular, some other much larger number).

securing the integer

As you've already figured out, that is exactly the purpose of a MAC such as a UMAC
and the purpose of a digital signature.

There are many protocols (including gzip and MP3) that add a CRC immediately after the header, in order to allow the receiver to immediately reject a packet with accidental noise in the "length" field (a), (b), for exactly the reason you mention.

I've seen a few ad-hoc constructions where the transmitter sends the number N
followed by some simple function of N, such as (N+1), (~N), (-N), N itself again, CRC(N), fletcher_checksum(N), etc.

Alas, as you already know, a standard CRC is vulnerable to malicious modification (even when encrypted by a stream cipher):
an attacker who knows the exact position of the length field and the CRC that covers it
can flip the high bit of the length field, and then flip the effected bits of the CRC,
resulting in a valid-looking header -- even if the entire message -- length, CRC, and all -- is protected by a "perfectly-secure" one-time pad.
(Most other "simple function of N" are just as vulnerable).

(Does switching from a stream cipher to a block cipher help?)

Your idea of using a MAC such as UMAC to protect the header (including the "length" field and perhaps also including a few bytes of random nonce) helps a lot, but it doesn't completely fix the DoS issue you mention:

message = header || MAC(header) || clear text || MAC( header || clear text )


then transmit

( message ) ⊕ unique stream cipher


The " Should we MAC-then-encrypt or encrypt-then-MAC? " question implies that it may be better to do that in the opposite order:

header = (length || other stuff) ⊕ unique stream cipher
body = (clear text of message) ⊕ unique stream cipher


then transmit

header || MAC( header ) || body || MAC( header || body )


Either way, the attacker won't be able to "blindly" DoS your system by sending a short message that looks like a valid header for a gigabytes-long message, unless he comes up with a valid-looking MAC(header) -- which is difficult.

securing the integer isn't enough

However, if you ever really do start sending a valid message with a valid header indicating "gigabytes of data will follow", and then if the attacker manages to insert or delete or change any bits or bytes in the following message, then the receiver will still get hung up doing useless work processing those gigabytes of data, only to throw them all away in the end.
(And what happens next week when the attacker sends a short message that replays that valid "gigabytes of data follows" message header again?)

alternatives that don't require securing the integer

For this reason, many protocols and file formats (ZMODEM, IPv4, IPv6, gzip, MP3, etc.) put a hard limit on the maximum length of a packet (with a "length" field of 16 or fewer bits), forcing larger amounts of data to be chopped up into a series of packets.
Rather than "a 4 byte message size",
they have, for example, "a 12 bit message size field",
and then files of data longer than 4 KBytes are sent as a series of packets,
each packet with its own independent CRC or MAC or digital signature.

In addition to avoiding the "DoS" problem you describe, breaking up long messages into packets
also has other advantages.
When a few packets are damaged by "innocent" noise,
the system can figure out which packets were damaged,
and then resend just those packets,
rather than re-sending the multi-gigabyte file all over again from the beginning.

Possibly related questions:


Can you make a hash out of a stream cipher?
Converting a stream cipher into a block cipher