Hacker News Reader

Comment by mrob | Hacker News Reader

Couldn't Alice just repeat the plaintext many times (number agreed in advance when she shared the OTP), split it into bits, label each bit with a sequence number, shuffle all the labelled bits, then encrypt?

Then Bob can decrypt, split the message into labelled bits, and sort by sequence number. If any any of the repetitions of the message differ then it was tampered with.

View on HN

A variation on this would be: For each bit of the message take the next bit from the pad. If the bit is 0 then take a second bit from the pad and send it, then take a third bit, XOR it with the message, and send that. If the first bit is 1 then swap the order: take a second bit from the pad, XOR it with the message, and send that, then take a third bit from the pad and send it verbatim. The first bit is not transmitted. For decryption you do the same in reverse, checking that the verbatim pad bits match your copy of the pad.

This requires three times as much pad as regular OTP for the same plaintext, and the ciphertext is also twice as large, but it doesn't depend on any hash functions, all bits remain independent, and an attacker has no way to know which half of the ciphertext makes up the message. Any N-bit change in the ciphertext will have a ((2*N)-1)/(2*N) chance of being detected on the receiving side (50% for one bit, 75% for two bits, …).

Of course, if you are willing to trust message authentication codes something like OTP(pad1, message + MAC(pad2, message)) will be more efficient and has a higher chance of detecting tampering, especially for smaller numbers of bits.

At that point you might as well use a MAC.

You have to trust a hash function to do that, which doesn't seem likely if you require a one time pad.

Reply on news.ycombinator.com