Can I construct a feasible stream cipher out of HMAC and a secure hash algorithm?

I have constructed a stream cipher from a secure hash algorithm and a HMAC. Here is a brief description of the algorithm:

Let: (Actually Objective-C styled pseudo code)

• [data SHA512Hash]: SHA-512 hash of data,
• [data SHA512HMAC:key]: SHA-512 HMAC of data with key,
• [data xor:another]: bitwise XOR of two data and another which have the same length,
• [data bytesTo:index]: first index bytes of data,
• [data removeFirstBytes:count]: remove first count bytes from data,
• [data length]: length of data.
• [data concat:other]: Concatenate other after data.
• [Data new]: allocate an empty buffer.

Pseudocode: (Or actual Objective-C code?)

Data hkey = [key SHA512]; // Hash to make lengths match.
Data segKey = [IV SHA512];

Data dest = [Data new]; // This will be the output
Data last = (Some constant)

do {
// Cut off hash-sized chunks of source data
Data segment = [data bytesTo:[hkey length]];
[data removeFirstBytes:[hkey length]];

// Derive a new segment key
segKey = [segKey SHA512HMAC:hkey]; // or [segKey SHA512HMAC:[hkey concat:last]]? If so, how to decrypt?

// XOR
last = [segment xor:[segKey bytesTo:[segment length]]] // Truncates to make length match
dest = [dest concat:last];
} while ([data length] > 0)


From some other questions I am suggested that this is SHA-512 HMAC running in OFB mode but what about the change in the code comment?

This code seem to decipher itself when given the same key.

• Could you use real pseudocode, because I have no idea of what this Data IV = [key SHA512]; means... or maybe try to explain the thing in english. Commented Sep 18, 2013 at 19:14
• Of what I know of stream cyphers, it is certainly possible to build a stream cypher out of a keyed hash function, like SHA-512 HMAC, Salsa20 is exactly that. The problem is that SHA-512 HMAC has such uneeded security guarantees (for the purpose) that makes it orders of magnitude slower than any stream cipher "by desing". Commented Sep 18, 2013 at 19:19
• @Ivella, it simply means a hash of the key. Objective C looks a lot like a reverse polish calculator :). As I don't see a nonce, I presume something is missing from this stream cipher implementation. Commented Sep 18, 2013 at 19:32

2 Answers

Here is your algorithm in formula form, which might be easier to understand for non-objective-C-experts:

Encryption:

• $P_1 \mathbin\Vert P_2 \mathbin\Vert \dots \mathbin\Vert P_n := P$ (split plaintext in blocks, same size as hash output, except the last one)
• $K := \operatorname{SHA256}(\mathit{key})$
• $O_0 := \mathit{IV} (= K)$
• $O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K, O_{i-1})$ for all $i \in \{ 1, \dots, n\}$ (key stream)
• $C_i := P_i \oplus O_i$ for all $i \in \{ 1, \dots, n\}$ (the usual stream cipher XOR)
• $C := C_1 \mathbin\Vert \dots \mathbin\Vert C_n$

(where the last block $O_n$ is truncated to match the length of $P_n$)

Decryption: same, but with $C_i$ and $P_i$ swapped.

• $P_i := C_i \oplus O_i$ for all $i \in \{ 1, \dots, n\}$

As you remarked right, this is output feedback mode (OFB) with HMAC-SHA-512, with the key reused as the IV. (The value you named IV – $K$ here – is actually the effective key, derived by SHA-256 from the original key, the IV is your first segkey, initialized to the same value).

If you use the commented variant with

• $O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K \mathbin\Vert C_{i-1}, O_{i-1})$,

you have some new mode which is like a mixture of cipher feedback mode and output feedback mode, which uses the cipher feedback as part of the key (?). It is not a synchronous stream cipher anymore, as the keystream depends on the previous ciphertext. You can still decrypt it, you just have to use the previous version of segment instead of the previous version of last as input in the decryption function (i.e. you need one more variable in your program).

If you want to stay with established modes of operation, here is cipher feedback mode (CFB):

• $O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K, C_{i-1})$

This is Counter mode (CTR):

• $O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K, i)$

The analogons to ECB, CBC, PCBC don't work with a MAC (or other PRF like a keyed hash), as there is no inverse which would be needed for decryption.

Also, as Ivella remarked, your stream cipher is a lot slower than dedicated stream ciphers, or the same modes applied to a block cipher.

• Key and IV is unlinked now. Commented Sep 19, 2013 at 8:41
• Unlinking IV and Key does not really change much. It is still a mode of operation, where you swap the fast symmetric block cipher to a slow hash function (due to its unnecessary properties).
– tylo
Commented Sep 19, 2013 at 10:40
• @tylo I have two alternatives that is almost the same: one use SHA512-HMAC as CSPRNG and operate on 512-bit blocks and keys (The SHA512 hashing at the input of key and IV is to normalise lengths), another based on AES with 128-bit blocks and 256-bit keys. To me the 256-bit key length is a little too short. Commented Sep 19, 2013 at 11:33
• I hope you are not going to actually use this... I was assuming that this is just bouncing ideas around or for practice. Implementing your own crypto is really really bad, if you are not an absolute expert for that. And considering your last sentence, I don't think you are. AES (even 128 bit) is considered secure - unless you have to assume sidechannel attacks (e.g. via cache/timing), related key attacks and such.
– tylo
Commented Sep 19, 2013 at 13:36
• @tylo Packaged and published, but with a strong disclaimer and deprecation mark. I submitted this algorithm to some academic institution for evaluation though. Commented Sep 20, 2013 at 17:36

For clarity, we can rewrite this scheme as a keystream S generated by S[i] = HMAC-SHA512(K, S[i-1]), for a key K and with the initialization that S[0] = iv (the used keystream starts at S[1]). Basically, iteratively hash the last output to produce the keystream.

The choice of IV for the variable name is confusing. The first two lines are:

Data IV = [key SHA512]; // Should I derive this? If not, then how?
Data segKey = IV;


Based on the usage here:

segKey = [segKey SHA512HMAC:IV];


and the definition of [X SHA512HMAC:Y], "IV" both used as the HMAC key and the initialized value of segKey is set to IV. (Was the SHA512HMAC line supposed to be segKey = [segKey SHA512HMAC:key] instead?)

This is indeed OFB mode using a PRF (HMAC-SHA512) instead of a block cipher, which should be a suitable substitution.

The alternative proposal is

 [segKey SHA512HMAC:[IV concat:last]]


which concatenates IV and the previous ciphertext block for use as the HMAC key.

This is very close to CFB mode. CFB uses the ciphertext as the data input, whereas this mode used it as an addition to the key. To use CFB, change the line to segKey = [last SHA512HMAC:[IV]]. Both versions can be used for decryption: As you decrypt ciphertext blocks to plaintext, store the ciphertext block in an additional variable to use during the next iteration.

That said about the algorithm, there's a critical flaw. In the beginning, note that the IV is always derived from the key. (Technically, the IV is the key, but regardless, the problem is that they are a deterministic pair.) This means that every keystream produced with that key will be identical since the key will always produce the same IV. Reusing a PRG stream is very bad, since it's easily defeated with a known-plaintext attack and can even be defeated by just a ciphertext-only attack (assuming moderate, but not explicit, knowledge of the plaintext). This means the key can never be safely re-used. Allowing only one-time secure use of a key is probably not a desirable property.

Instead, the IV should be generated separately from the key and should be unique for each encryption with the key. Perhaps start with a random IV and increment by one for each encrypted message.

• last is not S[i-1], but the XOR of that and the plaintext (i.e. the last ciphertext block). Commented Sep 18, 2013 at 19:45
• Whoops, you are right. Not sure how I missed that, considering what I used it for CFB mode. Commented Sep 18, 2013 at 19:47
• So I should unlink initial segkey and IV variable? (I have no idea why I named my variables like this) Commented Sep 19, 2013 at 5:12
• Yes, they should be independent, assuming you want to use the key more than one time. Commented Sep 19, 2013 at 5:45
• @B-Con Now I unlinked them. IV is now generated randomly every time (reading /dev/urandom) but can I put IV with cipher text together safely? (Key is still handled separately though) Commented Sep 19, 2013 at 8:40