One Time Pad cryptography: Solving Source Integrity, Message Integrity and Delivery Acknowledgment

I remember the first time I heard about One Time Pad. I was working at a major corporation and we were working on an project involving not One Time Pad but a distributed ledger. At some point, and while chatting in Slack, I asked him to crack my encrypted phrase with a simple password based algorithm to prove his skills, since we have exchanged some cryptographic conversations during lunch, and quickly enough, he cracked it. After he explained me how he did I asked him: isn’t there an unbreakable algorithm? And this is how I discovered One Time Pad. Apparently he could not crack my One Time Pad cipher I sent later…

This day I started learning about one time pad and how to use it practically. It’s fascinating that we have a cryptographic algorithm to transmit data securely from point to point but still, no standard way to use it in real world scenarios.

The most common complaints are:

• The key has to be fully random
• The parties have to meet to exchange the key
• There is no message integrity mechanism

They are valid concerns but those can still be met:

• True random number sources really exist in form of hardware.
• Parties can meet once and exchange huge keys, enough to survive years of communication

We still have the one open concern “There is no message integrity mechanism”, so that sticked to my mind for quite some time. There should be a way to know that the message received came from our expected source and its the correct message. Furthermore, as a sender, I would like to know if my message arrived correctly at the destination…

Frank Miller, an american cryptographer and banker, in 1882 was the first who formulated One Time Pad.

Later on, in 1940, Claude Shannon proved mathematically how One Time Pad is mathematically unbreakable due to the nature of random numbers.

At this point One Time Pad is still considered an unbreakable cipher because you can’t really predict a truly random number, if I can switch a lemon by another fruit randomly in secret and I deliver you the switched fruit, how can you guess with certainly what was the original fruit switched?

The encryption is solid in principle, however, to make it practical in the real world you have to consider two points of communication and quickly you see that One Time Pad lacks in its foundation Source Integrity, Message Integrity and Delivery Acknowledgment. Any cipher delivered to the recipient can come from anyone, not the expected sender, and all keys, when performing the XOR operation are valid keys since they just switch values in the cipher and give a result.

So three questions arise for the receiver:

• Is this message coming from the source I expect?
• Is this key the the right key to use to decrypt the message?
• Is the message I decrypted the correct message my source sent me?

If the answer to any of the questions above is “no”, the receiver won’t be able to trust the message, and he might use his key for the wrong message which will consume a pad of his correct key, making impossible to communicate further with the correct source (the one that has his mirror key) since he lost track of the correct offset to use for the next message.

What the receiver wants is to be sure that the message he gets is the intended one and came from the source he expect. This simple limitation on the basic formulation on One Time Pad makes it a useless algorithm to use in production.

But hold on, I have found a solution…

It’s true that is unbreakable by definition, but if we cannot trust the Source and the Key pad used, can we really trust the method?

One important question also arise from the sender:

• Did my message arrive and was it correctly decrypted by my contact?

To answer this question there is only a solution, receive a message back from the receiver, proving the sender that he did.

Now lets see how…

Solving integrity: A key chunk sailed under a pad

All those problems can be solved by including a header in each message sent which travels encrypted. This is how it looks:

source_id: <A_PIECE_OF_THE_KEY_CONTIGUOUS_TO_MESSAGE>
seq: <THE_SEQUENCE_NUMBER_OF_THIS_MESSAGE>
offset: <THE_OFFSET_OF_THE_KEY_USED_IN_THIS_MESSAGE>

<THE_MESSAGE_TO_TRANSMIT>

The ‘seq’ and ‘offset’ can be included by the sender easily by looking at the current state of his key.

To construct the ‘source_id’ consider this: both parties share the same key and is secret. The key is used in One Time Pad for encryption/decryption, but the fact that is secret makes possible for the sender to include a chunk of it, encrypted in the message itself. This key pad chunk is a range of the key only used for message integrity (contiguous to the key used to encrypt the message itself) and it travels encrypted under a different pad. We can name this key chunk ‘source_id’ and be included as a header in the encrypted message

This 3 fields, included by the sender and encrypted under the pad will be used for the receiver to:

1. Verify Source Integrity: the receiver will compare the ‘source_id’ value with the value of his own key contiguous to the message being decrypted, if it matches, the message came from the correct source.

2. Verify Message Integrity: the 3 fields at once verify message integrity. ‘seq’ and ‘offset’ confirms the receiver that he used the correct key range, while ‘source_id’ confirms the message came from the correct source (since the source has the same key chunk as the receiver do).

At this point the receiver is sure the message came from his source, its the correct message he intended to sent and he consumed the correct part of his key (correct message from correct source).

The receiver side is good to go…

Solving Message Acknowledgment

At this point, the receiver has received the message but the sender doesn’t have a way to know if the receiver has received the message, and more importantly, the exact message he sent, and not a different one.

To solve this problem the sender will wait for a message in plain text from the receiver with the same ‘source_id’ value he sent, which can only be revealed to the receiver once he has received and decrypted the correct message the sender is waiting for acknowledgment for.

Here is the flow:

Bob sends message to Alice:

source_id: 1827737281999
seq: 1
offset: 5
Hello

Alice: Decrypts and checks for integrity:

Metadata looks correct!
I got the correct message!

Alice Sends Bob the acknowledgment:

1827737281999

Bob

I got the correct acknowledgment!
The message I sent arrived at the receiver!

Implementation

Fortunately I have spent the time building this system into a toolkit that works on any major operating system.

The result is otp-toolkit which allows you to have a keychain of contacts and perform and encrypt/decrypt operations using One Time Pad following this integrity and acknowledgment mechanisms.

The program is also prepared to avoid consuming a key chunk if the integrity validation fails, or if the encrypt/decrypt operation fails mid operation. It also implements the acknowledgment mechanism built in.

This cli can be used directly, for manually send/receive messages directly, or be used by third party apps like aloo does.

Conclusion

This One Time Pad implementation allows you to transmit one time pad messages even through an unsecure channel, since the receiver performs full validation on the message received.

It allows both parties to trust the messages received and prevent key mis-use (using wrong key pad) even in the case the message is tampered during transmission.

It also allows the receiver to know when a message sent has arrived to the sender.

With this solutions we finally have a production ready One Time Pad implementation that works for real life scenarios.

References:

• otp-toolkit : Implementation described in this article
• Frank Miller (Wikipedia) : Author who formulated One Time Pad
• Claude Shannon : Proved One Time Pad unbreakability

← Back to all posts