5
$\begingroup$

Imagine Alice sending Bob a message. They act like this:

  1. Alice encrypts a message with her key and sends it to Bob.
  2. Bob encrypts the message again with his key and sends it back to Alice.
  3. Alice decrypts the message with her key. So now it is encrypted with Bob's key. Alice sends the message back to Bob, who decrypts it with his key and the message is revealed.

I've been told that this can't happen. But I wrote and tested a script in python that does exactly the story above.

It is a stand-alone exe file (5.5MB). Anybody who wants to analyze the encrypted messages or test the program is welcome to ask, or can download a simple version (s000.tinyupload.com/?file_id=03258436522243989466).


EDIT

Theory is good, but someone please decode this messages on the wire:19894,19992,20504,20605 then 2094064,2114056,2158273,2178878

and then 21263,21466,21473,21678

if they are decrypted i will take back my algorithm.

$\endgroup$
  • $\begingroup$ This sounds like diffie hellman key exchange. There, the original message is in fact another key, usually for faster symmetric key crypto. $\endgroup$ – phs Jul 15 '17 at 21:43
  • 1
    $\begingroup$ What do you mean "I've been told that this can't happen."? $\endgroup$ – Koray Tugay Jul 16 '17 at 10:10
  • 1
    $\begingroup$ In case you're wondering, I converted your A to an edit of your Q. Next time, use the EDIT button. Related to your …if they are decrypted I will take back my algorithm. – That's the moment where you dropped the ball a little bit as that's not how it works. Yet, I personally had a little giggle moment, due to the fact that it's funny how those lines could be interpreted as a threat. Anyway, please do not expect any professional cryptographer to look at your latest lines without a facepalm. $\endgroup$ – e-sushi Jul 17 '17 at 1:17
  • 3
    $\begingroup$ Security by obscurity is not considered real security. So if you want anybody to take a look at your algorithm, you've got to tell us about it first. Those numbers per se won't interest anybody. $\endgroup$ – Lery Jul 17 '17 at 8:22
36
$\begingroup$

But i wrote and tested a script in python that does exactly the story above.

Yes, obviously it can happen; however you have to be a bit careful about how you do it to actually be secure.

Here's is likely what your python script does; it generates a bitstring (based on the key), and xor's the bitstring and the plaintext together, generating the ciphertext (and decryption is precisely the same).

So, if we denote the original message as $M$, the bitstring that Alice's key generates as $A$, and Bob's bitstring as $B$, then here is how it goes:

Alice encrypts $M$ (that is, she generates her bitstring, and exclusive or's $M$ with it). She transmits that, that, she sends:

$$M \oplus A$$

Bob takes that result, and encrypts it with his bitstring; he transmits that, which is:

$$(M \oplus A) \oplus B$$

Alice takes that and decrypts it with her bitstring (which is also just exclusive or'ing the bitstring). Exclusive-or is both associative and commutitive, and so the result (which she sends) is:

$$M \oplus B$$

Bob receives that, and decrypts it, resulting in $M$.

So, it worked; what's the problem?

Well, if someone takes all three messages that were sent on the wire, and exclusive or's them togeter, they get:

$$(M \oplus A) \oplus (M \oplus A \oplus B) \oplus (M \oplus B) = M$$

So, it's easy to recover the original message, even if you don't know either Alice's or Bob's key.

Now, it can be done securely; however it's a lot more work. In Shamir's three pass protocol, it is done by selecting a value $g$ and a large prime $p$, and have Alice's and Bob's key $a, b$ be secret exponents relatively prime to $p-1$; the encryption of $M$ with Alice's key is $M^a \bmod p$; the decryption is $M^{a^{-1} \bmod p-1} \bmod p$; you need a bit of number theory to show that encryption and decryption are inverses of each other.

So, for Alice to send the message $M$, show first computes and sends:

$$M^a \bmod p$$

Bob responds with

$$(M^a \bmod p)^b \bmod p = M^{ab} \bmod p$$

Alice then decrypts this message, resulting in:

$$(M^{ab} \bmod p)^{a^{-1} \bmod p-1} \bmod p = M^b \bmod p$$

Bob then decrypts with his secret key, resulting in:

$$(M^b \bmod p)^{b^{-1} \bmod p-1} \bmod p = M$$

This all works, and is believed to be secure (given an appropriate choice of $p$), however it's as much work as public key cryptography, and so is more a curiosity than anything else.

$\endgroup$
  • 10
    $\begingroup$ Ha, I was writing exactly this. You type fast. You might also want to mention that your first scheme allows Alice to trivially recover Bob's key. $\endgroup$ – Lery Jul 14 '17 at 15:10
  • $\begingroup$ the algorithm used is that make hard the decryption for the man in the middle. Example: word "Cryptography" becomes 53754,57994,50016,53737,57149,57893,52913,53662,55121,58839,‌​51108,54561 then 11013538,12097098,10225252,11233014,11332753,12477221,104987‌​61,11558519,11230637‌​,12340493,10413576,1‌​1442642 and then 44888,49062,49926,55068,49341,54391,48380,53202,47598,52308,‌​49177,54031. at last it is revealed. And of course there are more complex algorithms. Everyone chooses a key everytime - they dont use the same key twice. $\endgroup$ – christostz Jul 14 '17 at 17:16
  • 7
    $\begingroup$ @christostz The numbers you posted are using raw RSA encryption, which is vulnerable to padding oracles. Public-key crypto is slow and hard - use symmetric-key whenever possible! $\endgroup$ – Riking Jul 15 '17 at 4:32
  • 1
    $\begingroup$ @Lery: Re: "your first scheme allows Alice to trivially recover Bob's key": True -- and vice versa -- but neither Alice nor Bob has any reason to reuse the same key for any other messages. A bigger issue IMHO is that Alice has no way to authenticate that she's actually talking to Bob, so the OP's "Alice decrypts the message with her key. So now it is encrypted with Bob's key" step could equally be "Alice decrypts the message with her key. So now it is encrypted with the attacker's key." $\endgroup$ – ruakh Jul 16 '17 at 5:29
6
$\begingroup$

If this works, depends on the encryption algorithm you use. It needs to have the special property $Enc_{K_1}(Enc_{K_2}(M)) = Enc_{K_2}(Enc_{K_1}(M))$.

Most traditional encryption schemes (AES) do not have this property, the symmetric equivalent of RSA is the only one that I am aware of.

EDIT: Stream cipher, if used correctly, work too.

$\endgroup$
  • $\begingroup$ For synchronous stream cipher, where you're just xoring a key stream with the cipher, like AES-CTR or ChaCha20, I agree, but for other such as AES-CFB, you would have some troubles achieving the same goal. $\endgroup$ – Lery Jul 17 '17 at 8:26

protected by e-sushi Jul 17 '17 at 1:24

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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