# One Time Pad Algorithm without sharing keys

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^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).

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`

• Yep. Toss that. Save as an exam question ... Tee her... Commented Sep 16, 2016 at 20:12

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!"

# 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).

• 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. Commented Sep 16, 2016 at 23:23