5
$\begingroup$

I'm currently studying crypto and wondered what would be wrong with the following process...

I want to encrypt a long message $M$ with a short symmetric key $K$ and a public nonce $X$.

The idea is to increase the length of $K$ with successive hashes $$K' = H(X\mathbin\|K) \mathbin\| H(H(X\mathbin\|K)) \mathbin\| \cdots$$ until $length(K') = length(M)$.

Then encrypt with $$M' = X \mathbin\| (M \oplus K').$$

I'm not suggesting that I would use that instead of using something like libsodium.

But I would like to have some intuition about stream ciphers with something that I can understand completely.

Is there anything fundamentally broken with this approach? Is it possible to adjust this approach with minimal changes to make it not broken?

$\endgroup$
12
$\begingroup$

The Insecurity of Proposed Scheme

It is not as secure as it seems, in modern cryptography standards it is totally insecure. It is vulnerable to basic Known-Plaintext attacks (KPA) and in Modern Cryptography, we want a cipher secure against at least Chosen Plaintext Attack (CPA) or better Ind-CPA.

Now take the idea

$$K' = H(X\mathbin\|K) \mathbin\| H(H(X\mathbin\|K)) \mathbin\| \cdots.$$

If there is a known-plaintext block for the first output $H(X\mathbin\|K)$ then attackers can hash again and again (sometimes written as $H^s(X\mathbin\|K)$ ) to reveal the others without needing a key. So your design fails the next-bit test, i.e. the next bit of your keystream is predictable with 100%. The known block is not restricted to the first block, it can be anywhere except for the last block. All output keystream after the known block can be calculated. The previous blocks are secured with the pre-image resistance of the hash function.

The CTR mode with Hash

Instead, we used the CTR mode ( [1] as it is designed for PRF - Pseudo-Random Function - ( here we assume that the $H$ is a PRF). The CTR mode is CPA secure.

$$H(k,0) \mathbin\| H(k,1) \mathbin\| \cdots \mathbin\| H(k,\ell)$$ where the $\ell$ is the number that your message size divided into output size $b$ of the $H$ i.e. $\ell = len(m) / b$

The CTR mode doesn't require a PRP (Pseudo-Random Permutation, not proven yet, however, like AES), since it doesn't need the reverse of the encryption. For example, see the ChaCha20. Some restricted environment saves a lot of space for the implementation.

Transforming this scheme into OFB mode

The OFB mode is also CPA secure (the ECB is not). OFB produce the stream as $O_j = E_k(O_{j-1})$ with $O_0 = IV$. The encryption is performed as $C_j = P_j \oplus O_j$

As noted by SEJPM in the comments; Let define $H'(m)=H(m\|K)$ and produce the keystream similar to OFB.

$$K'=H'(X)\mathbin\| H'(H'(X))\mathbin\| \ldots$$ Note that in every step the key is added again. So the attacker needs the key to process from the known output stream. Assuming the used hash is a Random Oracle (RO) then this converts it into PRF then we can use the security arguments OFB.

Note that the hashes are candidates to Random Oracles.

$\endgroup$
  • 3
    $\begingroup$ I would go farther than say it's not "as secure as it seems". It is incredibly insecure. The chances that you know or can guess with reasonable probability some of the beginning of the message is extremely high in real world scenarios (headers). So for a large number of situations this is no security at all. Furthermore you don't even have to know the first one, any block will do for decrypting all following ones. $\endgroup$ – DRF Nov 15 '20 at 7:09
  • 3
    $\begingroup$ A potential fix to transform this into OFB mode though would be $H'(m)=H(m\|K); K'=H'(X)\|H'(H'(X))\|\ldots$ which transforms the hash (assuming it's an RO) into a PRF and thus makes the OFB security argument(s) applicable. $\endgroup$ – SEJPM Nov 15 '20 at 11:22
  • $\begingroup$ @SEJPM yes, added into the answer, thanks. $\endgroup$ – kelalaka Nov 15 '20 at 12:49
  • 1
    $\begingroup$ @DRF thanks, the answer is heavily updated. $\endgroup$ – kelalaka Nov 15 '20 at 15:06
  • $\begingroup$ Thank you! (1) In CTR mode, could H be a hash function like SHA-512 and I would simply call K' = SHA(K||0) || SHA(K||1) || ... || SHA(K||l)? (I'm asking this because the 2-arg H(k,i) has still some magic inside which I cannot translate to a hash function I use in the everyday.) (2) In OFB mode, if I expand your fix that would become K' = H(X||K) || H(H(X||K)||K) || H(H(H(X||K)||K)||K) || .... Ok I think it's obvious now that each subpart of the key must depend independently from the original key. Thank you very much. $\endgroup$ – Contaso Nov 15 '20 at 23:01

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.