Using the output of a stream cipher, how to guarantee the integrity of 4 bytes of data?

Question

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?

Answer 1

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

Answer 2

The problem you are solving is "how can I make sure some who can modify data doesn't confuse the message parsing logic, at least, to the extent that I don't recognize that something's wrong for quite a while".

First of all, how do you expect to handle the case where something is modified in the message? Do you immediately drop the encrypted connection, or do you hope to discard the corrupted message, and start recovering latter messages that haven't been corrupted?

If you expect that latter, well, with your approach, you need a way to recognize when the start of the next message begins, which isn't easy. In addition, if an attacker can insert or delete bytes from the stream, he can cause the stream cipher to lose sync, causing the decryption process to corrupt every byte.

If this the scenario you're in, I would advise a different approach: byte-stuffing and CFB mode (with width=8).

How byte stuffing works is fairly simple: we send each message as a frame, where the frame includes the message and the MAC tag; the message size isn't strictly necessary. For each frame, you first encode each byte of the message by keeping the bytes exactly as is, except for an FF byte; for that, you replace it with a FF 00 byte pattern. Once you sent the entire frame, you then append an FF FF sequence. You then CFB-mode encrypt the encoded frame, and send that.

On the reception side, you first CFB-mode decrypt the stream. When you decrypt an FF byte, you check the next byte; if the next byte is a 00, you act as if you received an FF in your frame; if it is another FF, you treat it as an end-of-frame (and any other value is an error). Once you've received an end-of-frame, you can then compute the MAC, and verify whether your have received the entire frame intact.

Now, consider an attacker that can modify the stream; he can corrupt the frame that is being sent (and possibly the next, if he can corrupt the end-of-frame sequence). However, once we get to the next frame, that frame is received properly (unless, of course, the attacker actively modifies that as well).

The reason we use CFB mode with width=8 is in case that attacker can insert or delete bytes; CFB mode can resynchronize after an insert or delete; most other modes cannot. Now, this mode is expensive (an cipher block operation for every byte send/received); however if you need to be tolerant to byte inserts/deletes, well, it's something you need.

The above assumes that an attacker can insert, delete and alter bytes; if you cannot insert or delete bytes, you can replace the CFB-mode with your favorite stream cipher. However, if he is able to insert individual bits (and thus break the correspondence between bits and bytes, you'll need CFB mode with width=1, and you'll need to do bit-stuffing; it's similar, but a tad more complex from a software standpoint.

Answer 3

If your message text is of variable size, then you need to split your message format into two parts and check their integrity separately:

• A header which contains at least the text length and some kind of MAC of the header.
• The text itself, and again some kind of MAC.

In order to avoid the DoS, the integrity of the header has to be checked before the (possibly large) text begins.

However, you don't want to reduce the complexity of the MAC value due to the probability of hash collisions.

Anyway, the first MAC can also cover additional information, e.g. the receiver or sender of the message, the send time, some kind of sequence number, etc. Because otherwise your messages are vulnerable to replay attacks or meddling with the receiver/sender addresses.

About your last suggestion: I am not entirely sure what your (message size x cipher output 2) stands for. If that's just another XOR, the attacker can flip the first bit of both words. In any other case: The attacker intercepts the entire message and then he knows the size. If the calculation in the 2nd part can be adjusted from one size to the other, he wins. right now I don't see another way than using a keyed hash for the integrity check.

Answer 4

SipHash is argued to be a pseudo-random function. If you were to use that it would work if I remember all the definitions correctly. Concretely use the stream as a key for SipHash, and send the length followed by the SipHash of the length.