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.

  • $\begingroup$ You may be looking for mesage authentication codes. $\endgroup$
    – fkraiem
    Nov 24 '15 at 9:44
  • 1
    $\begingroup$ Universal hash + symmetric cipher is a common MAC construction. E.g. Poly1305 is used that way in the TLS cipher suite. $\endgroup$
    – otus
    Nov 24 '15 at 10:32
  • 1
    $\begingroup$ 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). $\endgroup$
    – SEJPM
    Nov 24 '15 at 19:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Nov 24 '15 at 23:31
  • $\begingroup$ 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. $\endgroup$
    – daruma
    Nov 26 '15 at 10:27

Many caveats: I'm not qualified to write this answer, but hopefully other folks can correct my mistakes. Outside of NaCl's crypto_box and crypto_secretbox constructions, there are a lot of ways to misuse a polynomial MAC. That might be why Thomas Ptacek specifically recommends against them. The standard way to sign a message using a symmetric key is HMAC, and this question seems like kind of an "assuming I'm forced to used a stream cipher instead of a hash for some reason" thought experiment.

That said.

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.

Another important difference is that the polynomial MAC relies on a unique nonce (for the cipher) to keep its key secret, which means nonce reuse is extra specially terrible.


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.