# How to use a stream cipher to sign a message?

Are there known constructions which allow to sign a message M (let's say it will be sent as clear text) using a stream cipher C and a symmetric secret key K? So, we have M, C, K and we want to send M|S where S = SIGN(C,K,M) and | is the concatenation operator.

• You may be looking for mesage authentication codes. Nov 24 '15 at 9:44
• Universal hash + symmetric cipher is a common MAC construction. E.g. Poly1305 is used that way in the TLS cipher suite.
– otus
Nov 24 '15 at 10:32
• I think you could build a block cipher from the stream cipher and use said block cipher to implement a standard MAC (e.g. CMAC).
– SEJPM
Nov 24 '15 at 19:34
• A stream cipher generates a key stream. The key stream is then XOR'ed with the plain text. The problem is that a stream cipher doesn't collect any state when that's happening. So you at least need some kind of compression function in addition to the stream cipher. Nov 24 '15 at 23:31
• I was thinking about using the stream cipher to encrypt only the output of an error detection code that was applied to M or something along those lines. Nov 26 '15 at 10:27

Poly1305 is the authenticator in NaCl, and it's built with a stream cipher. First it feeds your message into a big polynomial, to give a checksum. The coefficients of the polynomial are derived from the bytes of your message, and the value of x in the polynomial comes from half of your secret key. Then it encrypts that checksum, using the other half of your secret key along with a nonce. The cipher for encrypting the checksum can be anything; it was AES in the original paper and it's XSalsa20 in the NaCl implementation. You need the cipher because the checksum by itself can leak the x that generated it.
One important difference between a polynomial MAC and a hash, is that it's easy to find collisions in the polynomial. If you know x you can find its multiplicative inverse, and then you can mix that into a message to control the exact checksum you end up with. A polynomial MAC doesn't uniquely determine its input like a good cryptographic hash does.