Questions about a SHA3 cipher stream encryption scheme

I have written an encryption implementation using a hash as a cipherstream for demonstration purposes. I know it is slower than more sensible options such as AES but I am interested in several things, which I will list at the bottom of this message.

NOTE: I am writing this in a pseudo-language that resembles C++ and using string for simplicity, I know that in practice the stream can output null character and cause trouble with string reading. SHA3 is assumed to be the 512-bit flavor.

SHA3_Sym_Enc(key,message)
{
base_key=SHA3(key); //not really needed, but in case we will ever allow the key to be "anything", we'll standardize the initial value like this

keystream="";
int counter=0;

{
hash_block=SHA3(base_key+string(counter)); //H(base_key+#) -> block#
keystream+=hash_block; //add blocks into one big pseudorandom output
counter++;
}

keystream=keystream.Left(message.length()); //our keystream works in blocks, and might output bigger than the message, so trim any excess

return message^keystream; //XOR the keystream with the message, output
}

void main()
{
scanf(key); //input user key

nonce=generate_random_bytes(sizeof(SHA3)); //generate a nonce, SHA3-length should be enough

message_key=SHA3(key+nonce); //build the actual key that is going to encrypt the message via concat and hash

ciphertext=SHA3_Sym_Enc(message_key,plaintext); //output the encrypted message via the function described earlier

final_message=ciphertext+SHA3(ciphertext+message_key)+nonce; //append a MAC and the nonce to the message, note that we are not doing HMAC because SHA3 is supposedly immune to length extension attacks
}


final_message is [ciphertext][MAC][nonce].

Decryption:

1. Break up final_message, extract the MAC and nonce, their lengths are predetermined and they are known to be at the end so this will be easy
2. Take key+nonce and hash, reach message_key
3. Hash ciphertext+message_key, if they = MAC, the message is untampered
4. parse the ciphertext back through the function to rebuild the original message

Now my questions:

1. If given a large enough password, does this system appear secure?

2. The hash function used here has a 512bit output and 1066 bits of internal state; does it really provide 512 bits of security? Also because hashes produce wildly different and unrelatable outputs for even tiny incremental changes, would this mean it's immune to a related key attack, even without a nonce? I ask these because AES only goes up to 256 bits and has some known issues with related keys, and as far as these two points go, this stream would be superior?

3. If I were to chain only half of the output instead of the full H(base_key+counter), in order to further hide any vital info about the keystream's origins that an attacker would try to obtain, how many bits of security would I lose? Would I go down to 511 or 256? I think it would be really nice because the stream could, in theory, at some point output a block identical to a previous block, and this in full implementation would mean that the stream has reached an interval and starts repeating, but this one would not because the out-of-sight bits are still different, further confusing an attacker.

• Answer to A): Yes. This is some variation of CTR Mode using the easiest (secure) Keccak MAC. But please change the order of ciphertext and key in the authentication Keccak call. – SEJPM Feb 11 '16 at 18:16
• Haha! Yes, I wrote this in a hurry, the function parameters are (message, key) but I'm then calling it as (key, message). The actual implementation doesn't contain this mistake. Thanks for pointing it out! :) – Searinox Feb 11 '16 at 18:58
• Not an answer, but you might want to look at the stream cipher mode defined by the authors of Keccak instead: sponge.noekeon.org/SpongeDuplex.pdf – otus Feb 12 '16 at 7:15

TL;DR: The idea is good and the implementation should work securely (with a solid security margin), given that some tweaks are implemented.

How secure is it?

A) If given a large enough password, does this system appear secure?

If you replace "password" with "key", then the answer should be yes.

For analysis purposes, let's define $E_K(M) = \operatorname{MAC}_K(\text{CTR} || \text{Nonce})\oplus M$, with $\operatorname{MAC}_K(M) = \operatorname{Keccak}(K||M)$. The nonce is message based and the counter is call-based, i.e. the counter increases by one every 512 bit. The MAC was already analyzed here.

Let's further define $E^A_K(M) = \text{Nonce}||E_{K1}(M)||MAC_K(E_{K2}(M))$ which is the full authenticated encryption mode. Note that I have used different keys here for authentication and for encryption. This removes potentially dangerous dependencies between the two components. Not furthar that the order of key and ciphertext was swapped for the authentication to obtain more consistency and don't do potentially dangerous things.

The encryption component of the above is basically CTR-Mode, with a split-up counter where one part is "static" and one part is "dynamic", like is done in GCM. As you properly randomize it using the nonce and the counter, this is a proper instance and therefore the standard security bound of $2^{n/2}$ (for non-permutations) holds, i.e. the encryption strength is 256-bit. This is is due to the fact that you expect collisions from the hash after roughly $2^{n/2}$ invocations with different values and thereby can derive information about the plaintext from this. As for the authentication, at least collision attacks are required to break the standard encrypt-then-mac, also giving (at least) 256-bit security.

If you truncate the output of the hash function, security will decrease accordingly. SHA-3-256 would only yield 128-bit strength, as you'd expect collisons after only $2^{128}$ calls instead of $2^{256}$.

Potential Improvements

1. Make the keys independent.
2. Make the order of arguments to the hash consistent (i.e. always the key first)
3. Take associcated data (AD) into account, especially the nonce should always be authenticated.

Real Life applications

If this wasn't for demonstrations purposes you should strongly avoid rolling your own crypto and rather use AES-GCM (which should be faster anyways), any standard AES authenticated encryption scheme, Keyak or the scheme linked by otus in the comments: "Duplexing the sponge: single-pass authenticated encryption and other applications" by Bertoni, Daemen et. al.

• I went with very conservative security estimates here. It may very well be, that the security margins are higher and that things like key independence are not required, but it will be secure at least in this configuration. – SEJPM Feb 12 '16 at 14:58
• Since message_key is the unique key used to actually encrypt each message and key is the base key from which the message_key is built using the nonce, could key independence work by MAC-ing with key and encrypting with message_key? This could also save time as I no longer need to concat and hash key and nonce before verifying the MAC. Also, I'm not sure I understand the relationship that can be established between MAC key and decryption key. – Searinox Feb 12 '16 at 16:26
• Also: Building on the cryptosystem here: Let's assume a wifi-style comm protocol, where all transmissions are public, those the AP and qualified clients both know the key, unqualified clients do not, and each session should be isolated from other users' eavesdrop. Is the following a secure idea? 1. Use Diffie-Hellman to first establish a common nonce 2. Concat and hash the access point key with the nonce to create a session_key unique to each client 3. Use that key the encryption key in the above scheme, each encrypted message also containing a counter to prevent replay attacks. – Searinox Feb 13 '16 at 9:35
• @Searinox, I think I made a mistake here. You do have a form of key independence that should be strong enough. You use $K_1=H(K||N)$ and $K_2=H(K_1)$. The more standard approach for this would be HKDF (based off the key) or MAC'ing "Authentication" and "Encryption" using key (or something similar) and using the results as keys. – SEJPM Feb 13 '16 at 13:40
• @Searinox, the best real-life solution would be TLS-PSK with (EC)DHE and AES-GCM. – SEJPM Feb 13 '16 at 13:41