Skein or Keccak stream cipher construction

I am wondering if using Skein or the Keccak hash algorithm in this construction (as a stream cipher) is secure:

• $H$ = Keccak or Skein hash with a 256 bit output
• $K$ = The main 256 bit random key, pre-shared between sender and receiver
• $K_M$ = A secondary 256 bit random key for creating the MAC, pre-shared between sender and receiver
• $IV$ = A per message 256 bit random initialization vector, sent in the clear with the ciphertext and MAC
• $i$ = counter starting at 0 for each message which increments by 1 every 256 bit block
• $K_i$ = 256 bit block of the generated key for encrypting the corresponding 256 bit block of the plaintext $P_i$
• $P_i$ = 256 bit block of the plaintext. The final plaintext block would be padded to the right with 0 bits, thus the final concatenated plaintext is a multiple of 256 bits and disguises the true plaintext length.
• $C_i$ = 256 bit block of ciphertext
• $|$ = concatenation
• ⊕ = XOR

Encryption:

1. $K_i$ = $H$($K$ | $IV$ | $i$)
2. $C_i$ = $K_i$ ⊕ $P_i$

MAC:

• $H$($K_M$ | $IV$ | $C_i$ ... $C_n$)

I hope I explained that clearly.

My other question:

Is there a particular attack on using the same key for encryption and MAC?

• The stream cipher part is essentially counter mode with a hash function. – Paŭlo Ebermann Oct 6 '14 at 17:48

I am wondering if using Skein or the Keccak hash algorithm in this construction (as a stream cipher) is secure:

In the case of Skein and Keccak it should be secure. However, both of those have defined their own cipher modes which you should IMO prefer. (For speed and compatibility, if not security.)

• The Skein one is defined in section 4.10 of the paper. It uses the underlying primitive directly rather than hashing the key and nonce.

• For Keccak the web site links to a separate paper on an authenticated encryption mode. It uses the sponge to squeeze a larger number of output bits, like the SHAKE modes of the hash function.

Alternatively, in the case of Keccak/SHA-3 you may want to use one of the SHAKE extendable output functions, which produce an arbitrarily long output stream. They may also be faster than repeated calls to the hash function.

Is there a particular attack on using the same key for encryption and MAC?

You should make sure the MAC invocation can never match an encryption one. I.e. it is not possible for $K|IV|C$ to match any $K|IV|i$. Easiest would probably be to add a string to make them differ, like $H(K|\text{'E'}|IV|i)$ and $H(K|\text{'A'}|IV|C)$.

In that case the MAC and encryption are independent, and a known or chosen plaintext attack cannot leak any extra MAC values.

Generically, your construction is not necessarily secure. First a hash function doesn't have to be a secure MAC when you prepend the key. Second, a stream cipher must be a PRF, which is a stronger condition than unforgeability for a MAC.

For example, you could define a stupid MAC like: $MAC_k(m)||MAC_k(m)$ and it would be just as strong a MAC as the original, but would make a lousy stream cipher.

(In practice most MACs do seem to also claim to be PRF.)

• [+1] For what it’s worth: there’s a question handling “Is there a difference between PRF and a hash function?” which provides some additional info (and confirms the later part of this answer). – e-sushi Aug 5 '14 at 12:43
• From reading the papers it appears to be that I would need to develop my own custom implementation of Skein or Keccak to use their special cipher modes. It's unlikely that anyone has developed a library for the standard Skein/Keccak hash function which will implement those modes. From the responses here it appears HMAC-SHA1 is a reasonable PRF so could be used in the similar construction above. Do you think HMAC-Skein/Keccak would be a stronger alternative? – kimi Oct 6 '14 at 1:01
• If HMAC-Skein/Keccak is considered secure for the stream cipher above, then why need the HMAC at all? Skein & Keccak don't actually require HMAC to be secure as a MAC in the form H(K | M) (see questions 1 and 2). Therefore, is there a reason not to just use the stream cipher construction in the question? It would be considerably faster than HMAC. – kimi Oct 6 '14 at 1:07
• "However, both of those have defined their own cipher modes which you should IMO prefer. (For compatibility, if not security.)" I think compatibility might be actually easier if it was just using the plain hash function. There would be more libraries implementing that variant, than the special cipher mode variants. There are also reference test vectors in the publications which show the correct hash outputs, whereas there are none for the special cipher modes. – kimi Oct 6 '14 at 1:17
• @kimi, yes, just using one of them in your construction should be ok, HMAC isn't needed. However, you may want to use the SHAKE mode, if that's available in the SHA-3 library, since it should be faster and as secure. – otus Oct 6 '14 at 4:37

If you replace $H$ with a MAC that is build using $H$, i.e. NMAC, then it will be provably secure. Encryption will be $C_i = MAC_k(IV | i) \oplus P_i$. You are guaranteed by the MAC security property (existential forgery) that an adversary cannot generate any of the key stream on his own and so you are left with a secure stream cipher. Just using $H$ by itself probably will not have any attacks on it (or else they would lead to some significant weakness in the underlying hash function) but it will not be provably secure.

The problem with your construction in general is that you are assuming some strong hiding property of the hash function that may or may not exist. The main properties of a cryptographic hash function are:

1. Pre-image resistance: for a given $x$, it should be difficult to find a message $m$ such that $H(m) = x$

2. Second pre-image resistance: for a given $x$ and $m$, such that $H(m) = x$, it should be difficult to find $m'$ such that $m \neq m'$ and $H(m') = x$

3. Collision resistance: it should be difficult to find two messages $m$ and $m'$ such that $H(m) = H(m')$

Collision resistance implies second pre-image resistance, and in most cases also implies pre-image resistance, so it is the most useful one to consider. However, a hash function could be collision resistance and still leak many of the bits of the input. For instance, if $H$ is a collision resistant hash function, you can construct $H'$ as follows:

$$H'(m) = \text{first 10 bits of m } | H(m)$$

and it will still be collision resistant. Now, obviously SHA-3 does not have this property, but the point is that it was not tested for strict hiding. If you wanted that you would use an actual cipher which was tested for that. Therefore you should not use it as if it does have that property.

• Digging around I can see from this answer and this answer that Skein and Keccak are secure as MACs in the form $H$($K$ | $M$) and they have strong collision resistance, second pre-image resistance and pre-image resistance. Shouldn't they have the required hiding property for use as a stream cipher? It seems overkill and slow to need NMAC or HMAC when it is already secure... – kimi Aug 5 '14 at 1:18
• Oh well sure, if it has a built-in MAC mode then you can certainly use that. I wasn't aware of that before. I meant only that you cannot generically use a hash function for encryption like you were proposing, but a MAC would suffice. It doesn't have to be NMAC. – Travis Mayberry Aug 5 '14 at 2:44
• A MAC does not necessarily suffice. $\:$ One needs a PRF. $\;\;\;\;$ – user991 Aug 5 '14 at 4:19
• Oh you're right Ricky. I remembered you could encrypt from a MAC but actually you would have to do it one bit at a time. You could have a degenerate MAC that always sets the last bit to one for instance, which would make a bad stream cipher. But you could do something like a Goldreich-Levin hard core predicate and use that to encrypt a single bit. But, you could do the same thing with a hash function so actually my whole point is kind of nullified :D – Travis Mayberry Aug 5 '14 at 11:21
• In particular, even though one is "guaranteed by the MAC security property (existential forgery) that an adversary cannot generate any of the key stream on" its own, that does not necessarily give a secure stream cipher. $\;$ – user991 Aug 5 '14 at 18:37