5
$\begingroup$

The Trivium encryption algorithm has two inputs, key and IV, both of which are 80 bits long. Let's call it Trivium(key, IV) → keystream. My question is whether doing Trivium(key, input) and taking the first 80 bit of keystream would result in a secure PRF.

I have found another way to create a PRF from a stream cipher, but that seems to be for stream ciphers that do not have an IV input, so such a complex construction might not be needed for one that does. Based on reading the Trivium algorithm description paper and the Trivium design paper I feel like my construction should be secure but I have no idea how to go around proving it.

This question was spurred by wondering whether I could implement authenticated encryption using only Trivium as a primitive. If I could turn it into a PRF, as far as I understand I could construct something similar to CBC-MAC from it. (Of course this doesn't make much sense to because rekeying the cipher, which you'd need to do for every 8 bytes, is quite slow.)

$\endgroup$
  • 1
    $\begingroup$ I'm pretty sure the standard security proof for CPA security of nonce-based stream ciphers does assume the stream cipher to behave like a PRF. $\endgroup$ – SEJPM Oct 6 at 13:53
  • $\begingroup$ With the limited description above, wouldn't your input data be limited to 80 bits / 10 bytes? $\endgroup$ – Maarten Bodewes Oct 7 at 9:25
  • $\begingroup$ Yes. My understanding was that a PRF is usually defined to map from a fixed-size input to a fixed-size output. Is that not correct? $\endgroup$ – nortti Oct 7 at 15:51
  • $\begingroup$ @nortti: PRFs can have either fixed- or variable-size input domains. Block ciphers are the most common example of fixed-size input PRFs. HMAC is the most common example of a variable input size PRF, but see also CMAC. $\endgroup$ – Luis Casillas Oct 7 at 22:36
3
$\begingroup$

To attempt such a proof you need a definition of what security properties an IV-based stream cipher is supposed to provide. For example, like this (very informally):

  • A nonce-based cipher is secure if and only if its encryptions are indistinguishable from random bitstrings of the same length to a nonce-respecting adversary that's allowed to carry out a chosen-plaintext attack.

The "nonce-respecting" bit is important, because one of the key assumptions in a PRF is that it's supposed to be secure against adversarially-chosen inputs, and the inclusion of "nonce-respecting" in such a definition is to give the adversary as much control over nonces as we can get away with. (Note not all ciphers meet this standard—e.g., CBC-mode encryption doesn't, because it requires random nonces. Evaluating whether Trivium meets this standard is a whole 'nother topic.)

So if encrypting message $p$ with key $k$ and nonce $n$ is notated as $Enc^n_k(p)$, then your proposed PRF construction would be:

$$ PRF_k(m) = Enc^m_k(0^{80}) $$

...where $0^{80}$ is the 80-bit all-zero string. And what you want to prove is that, given a secret, random choice of $k$, if an attacker who can choose messages $m$ could distinguish your PRF apart from a random function, then they could break the underlying nonce-based cipher.

In this case, that follows by observing that if there was such a chosen-message attack they could mount against the PRF, it would imply the existence a corresponding attack on the cipher by querying for the encryption of the same plaintext $0^{80}$ repeatedly but with different, adversarially-controlled nonces.

$\endgroup$

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.