2

On my walk to work today I thought of the following encryption algorithm and could not determine the flaw. It uses one time pad's that don't need to be shared and has a Diffie-Hellman key exchange flavor to it:

  1. Say Alice wants to sent a message M to Bob so she generates a random one-time pad A and sends M' = (M xor A) to Bob.

  2. Bob also generates a one-time pad B and sends M'' = (M' xor B) back to Alice.

  3. Alice then uses her one-time pad again and sends M''' = (M'' xor A) back to Bob.

  4. Bob then simply retrieves the original message which is (M''' xor B).

That cypher sent in step 1 is (M xor A). The cypher send in step 2 is (M xor A xor B). The cypher sender in step 3 is (M xor A xor B xor A) = (M xor B). Bob then can decrypt the final message M = (M xor B xor B). All eavesdroppers only see messages encrypted with some safe combination of the keys A and B. Even though Bob can determine Alice's one-time pad A in step 3, there was never any need to share keys.

Here is a simple 32-bit example (^ = xor):

M = 1234ABCD  secret message
A = 4A3109AD  Alice's key
B = F499803C  Bob'e key

M         = 1234ABCD
M^A       = 5805A260
M^A^B     = AC9C225C
M^A^B^A   = E6AD2BF1
M^A^B^A^B = 1234ABCD

Why is this not perfectly secure? (P.S., I am ignoring trust issues and man-in-the middle issues -- which may be where the problem lies).

2 Answers 2

8

An eavesdropper will see all three messages (M xor A), (M xor A xor B) and (M xor B)

He combines them with (M xor A) xor (M xor A xor B) xor (M xor B) which gives M

1
  • 1
    Yep. Toss that. Save as an exam question ... Tee her...
    – wcochran
    Sep 16, 2016 at 20:12
-2

You've gone and made something almost exactly like my encryption algorithm. The problem is, the One Time Pad only works with modular addition; that means every byte must be added to a byte in the key stream. The generic operation would be:

M = "Hello world!"

K = "MyKeypadding"

Let's assume the encoding to be UTF-8

M = "\x48\x65\x6C\x6C\x6F\x20\x77\x6F\x72\x6C\x64\x21"

K = "\x4D\x79\x4B\x65\x79\x70\x61\x64\x64\x69\x6E\x67"

Add every byte and modulo 16

for (i=1; i<=11; i+1){ // i < message_length

M[i] = (M[i] + K[i]) % 0xff

}

Which makes M' = "\x95\xDE\xB7..."

And to solve it, just subtract the key. If the difference is less than 0, add the negative difference to 0xff (255).

1
  • 1
    The question is about how secure the algorithm is during message transfer, not about the algorithm implementation. Moreover, addition plus modulo vs. XOR is really irrelavant with one time pads; both will produce equivalent cyphertexts from a security point of view.
    – grochmal
    Sep 16, 2016 at 23:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .