4
$\begingroup$

Can anyone comment if the stream cipher described here is safe? The author claims it to be unbreakable, but does not provide any evidence or proof to support this. For completeness, I have reproduced the algorithm below.

Encryption routine (Alice$\to$Bob)

  1. Calculates a shared secret: $s=$Curve25519(Alice_private_key, Bob_public_key)

  2. Calculates N seeds $s_1,\dots,s_n$: $$s_0 = \mathrm{SHA256}(s);\quad s_n = \mathrm{SHA256}(s_{n-1})$$

  3. Calculates N keys $k_1,\dots,k_n$: $$k_n = \mathrm{SHA256}(\overline{s_n})$$ (where $\bar{s}$ is the bitwise compliment of $s$)

  4. Encrypts the plaintext via xor: $$c_n = p_n \oplus k_n$$

Upon receipt Bob decrypts the ciphertext by repeating the identical steps, except he derives the shared secret $s$ using his private key and Alice's public key.

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ Unbreakable? That's a bold claim. $\endgroup$
    – hunter
    Commented Apr 8, 2014 at 21:08
  • 2
    $\begingroup$ unbreakable up to max 128-bit security level, possibly less in practice depending on generation method of ECC private keys, and as mentioned already, vulnerable to known plaintext type attacks $\endgroup$
    – Richie Frame
    Commented Apr 9, 2014 at 1:36
  • 3
    $\begingroup$ Unbreakable means the creator wants to mislead you or doesn't know what he's talking about. Imagine a pharmaceutical issuing a new drug and claiming that it can cure virus X now and in the future, despite any mutations! Case in point, unbreakable under some assumptions is not unbreakable. $\endgroup$
    – rath
    Commented Apr 9, 2014 at 13:55

1 Answer 1

Reset to default
9
$\begingroup$

Some brief thoughts:

Shared secret Generation: $$s=E_a(B)=E_b(A)$$ The shared secret is generated by encrypting the other users public key with your private key. This is effectively an ECDH step, which is very reasonable, and one of the key aims of C25519$^{[1]}$.

Key Generation: $$s_0=\mathrm{SHA256}(s); s_i=\mathrm{SHA256}(s_{i-1})$$ First, using the definition above, they generate seeds. This doesn't seem an unreasonable way of expanding one seed into many. $$k_n = \mathrm{SHA256}(\overline{s_n})$$ Yes, I'm happy that the $k_n$ should look pretty random.

Xor combinator: This isn't at all unreasonable, and most use this technique for combining their stream with the plaintext.

Overall? Assuming the relation required in the first step holds, which I'm unsure and sceptical about, then first impressions are that this scheme should be ok. At the end of the day it's basically using to seed a $\mathrm{SHA256}$-based stream cipher. Cryptographically, this means it will at best have the security bounds from the weakest of those primitives. Whilst this is certainly not genuinely 'unbreakable', it should be computationally secure. However, there are some far more significant issues with it that won't be addressed by 'is it secure'? I'll note some of them now...

Key reuse As noted by the original author, this scheme only generates a single key-stream, seeded by the two public keys through the ECDH step. The dangers of reusing an xor keystream are severe - it leaks the xor of the plaintexts, which is often sufficient to allow a total break: $$c_a=m_a\oplus K;c_b=m_b\oplus K \implies c_a\oplus c_b = m_a\oplus m_b$$ This could be resolved by adding a nonce to the original step, which is arguably the biggest issue of the scheme. That is, $$s_0=\mathrm{SHA256}(s||N)$$ Where $N$ is a nonce, although it does not have to be unpredictable.

Why should I care? This is the biggest issue with most homebrew schemes. Unless a scheme can demonstrate some advantage over the other schemes in existence, then why on earth wouldn't I just use those? In this case, it won't be particularly quick given the number of SHA calls made, won't be very nice to parellelise due to the recursive nature by which the stream is generated, and after all that it's just an xor-based stream cipher. See this question for why you should always think at least 3$^{[1]}$ times before using an encryption algorithm rather than an authenticated encryption algorithm.

[1]: Thanks to DrLecter for clarification on this point.

[2]: In the old days, people used to be told "think twice before doing $x$". However, as we are all aware, lots of people still did $x$. As such, I'm pushing for raising the number of "think's" required. Obviously as a cryptographer I'd like to go for at least 64-bit security, but for now 3 will have to do.

Improve this answer
$\endgroup$
2
  • $\begingroup$ +1 for pointing out the lack of authentication. AES-GCM seems like a much better option. $\endgroup$
    – hunter
    Commented Apr 8, 2014 at 22:40
  • 1
    $\begingroup$ @user12480: Does this answer your question, because if so do mark it as such. If not, do clarify why it's not - we strive to leave every question as answered here on Crypto.SE $\endgroup$
    – Cryptographeur
    Commented Apr 13, 2014 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.