Questions about a SHA3 cipher stream encryption scheme

Question

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;

for(read_message=0;read_message<message_length;read_message+=base_key.length()) //work in blocks of SHA3 outputs
    {
    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 1

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.