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

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
    Yep. Toss that. Save as an exam question ... Tee her... – wcochran Sep 16 '16 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
    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 '16 at 23:23

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.