Does humanly verifiable one time pad authentication exist?

Question

Firstly some predicates:-

• Sufficient hardware generated one time pad key material.
• No pad reuse.
• Messages of 160 characters length (think Twitter).
• 28 characters only in use (A-Z, space and full stop alphabet. Think Morse).
• The very vast majority of messages based on English grammatical form.
• The messages would be typed on a computer and read via computer.

Would it be possible to authenticate a one time pad message manually by hand using say pen and paper? Perhaps even a spread sheet, but certainly no programming languages. Hence the typical HMAC is out. The character set and message length are not unmanageable with some determination.

But most importantly, the authentication only has to be manually provable to work. He will not be authenticating every message, just those he chooses to test. That means that the user has to be able to verify to himself that the algorithm works on the messaging system. So he can take an arbitrary message, authenticate and satisfy himself of correctness. The purpose is to create confidence in a manually verifiable way that the system is working correctly and not a fraud or victim of a Man in the Middle attack.

High security is of secondary importance, subservient to the need for provable manual verification of authentication. Whilst a one time pad is totally secure, the authentication algorithm needn't be. Any degree of authentication will be of interest for this question. It would be nice if any proposed solution could have the security level quantified in bits.

I appreciate that there is a spectrum of levels of security for the authentication mechanism. Clearly it ranges from no security (no authentication) to very secure (HMAC calculation). I think that unfortunately we're looking at the lower end of the scale towards the no security end, as the overriding criterion is human computation.

The most basic and brute force approach that occurs is simply sending the same message in multiples. So m ⊕ k1 | m ⊕ k2 | ... and so on. I believe that you'd get 4.8 bits of security for every concatenated message, but I'm probably wrong.

Answer 1

Create an "alphabet" containing every single possible tweet character exactly once, and construct a tabula recta based on this "alphabet".

Let a plaintext character be a checksum. Calculate the checksum with your tabula recta like this:

Find the first plaintext character in the first row of the table,

• go down until you find the second character,

  left or right until you find the third,

  up or down until you find the fourth,

  left or right until you find the fifth,

  up or down until your find the sixth, etc.

When you hit the last character, make a 90 degree turn and keep going until you hit the edge of the tabula recta. The character you land on is the checksum.

Insert the checksum at the same position in the message as the position of the first key character in your "alphabet".

If the receiver calculates the checksum of the message (ignoring the character at the position indicated by the first key character, of course) and finds it matches the decrypted checksum, he can be {100-[(1 ÷ alphabet length) × 100]}% sure the message was not modified by an adversary.

To give credit where it is due, I got the idea of this snaking operation on the tabula recta from prgomez.com.

Answer 2

I'll use $m\boxplus k$ for combining characters $m$ and $k$ by addition (modulo $n=28$) within the character set, or strings of individual characters of equal-length, rather than " m ⊕ k " in the question. I consider alphabetical ordering of $n$ (e.g. 28) characters with letters first, such that $\;\mathtt{'A'}\boxplus\mathtt{'A'}\;=\;\mathtt{'A'}\;$ and $\;\mathtt{'B'}\boxplus\mathtt{'C'}\;=\;\mathtt{'D'}\;$.

The question's method of sending $M\boxplus K_1\;\|\;M\boxplus K_2\;\|\;\dots$ is extremely insecure: replacing each ciphertext character $x$ by $x\boxplus\mathtt{'B'}$ is not detected, but correspondingly alters the message. There is a partial fix: for each character $m$ of the message, append to the message the character $m\boxplus m\boxplus m$, then encipher with OTP; since $\gcd(3,28)=1$, this makes altering a plaintext character precisely as hard (or easy) as guessing it. Even with that improvement, if the message (or a segment thereof) is known, it is possible to change it (or that segment) to anything desired, with certainty that the change goes undetected. That's insatisfactory.

Goals

1. Integrity check should be based on the plaintext, thus catching decryption errors (accidental or not) introduced by whatever deciphers, and avoiding the need to keep the full ciphertext for integrity check.
2. It shall remain convenient to decipher first (including while receiving), postponing integrity check.
3. Same unconditional plaintext confidentiality as OTP in ciphertext-only attacks, and only practically negligible leak under an attack model where the MitM gets to know if an attempted forgery succeeds or not. The receiver does not know the message length in advance. We posit integrity of the random pad, that it is synchronized between sender and receiver at the beginning of each message, and is never reused by sender or receiver.
4. In order to keep the integrity check feasible by hand, we restrict to use of the same $\boxplus$ as used for encryption, public latin square(s), random characters supplied by the random Pad (after those used by en/decryption), a moderate number of characters (or integer) variables (perhaps selection among these, and simple decimal arithmetic). Paper and pencil is OK (even if plaintext-leaking material gets written on it), a calculator is not.
5. The amount of work for integrity check should be minimized, as well as the transmission overhead, and drain of the random pad.
6. Quantifiable level of security against forgery, including with known plaintext (which makes sense if we do not fully trust whatever deciphers, see 1).

---

Circular buffer with latin square and addition (2017-06-03b)

We spare the first $s\ge2$ characters of ciphertext for integrity check, computed from the plaintext and the first $t\ge s$ characters of the random pad (or stream generator); think of $s=4$, $t=10$. The $s$ integrity check characters are computed by the sender, and optionally recomputed and verified by the receiver. All the rest is standard One Time Pad (or stream generator) and we do not further discuss encryption and decryption.

The system uses a single public $n\times n$ latin square; assume for now a random one.

For manual computation, the first $s$ characters of the random pad are written down (with - for space and + for the extra character). For each character of the plaintext, and then for each of the $t-s$ next characters of the random pad:

• fetch the latin square at the line defined by that character, and the column defined the last character that was written;
• combine the result using $\boxplus$ (addition modulo $n$ as used in the OTP) with the first character not striked-out (which is also the $s^\text{th}$ from the end), and strike that character;
• write the resulting character following the $s-1$ characters not striked.

The $s$ characters remaining are the check characters.

(In)Security:

• Each step combines the newly added character, leftmost and rightmost check characters, into a new check character, in a manner such that knowing 3 our of these 4 characters the other can be uniquely determined. It follows that the $s$ check characters remain uniformly distributed during the whole computation, for constant plaintext. No information about the plaintext can leak from the check characters, and information leak from acceptance/rejection is limited by the forgery rate.
• The tight alternation of the latin square and $\boxplus$ combiners quickly and non-linearly diffuse changes; this is critical (forgery is trivial if we replace the latin square with $\boxplus$).
• There is a forgery with $(n-1)^{-2}$ odds of success ($2\log(n-1)\approx9.5$-bit security): alter randomly two consecutive characters, then a third with $n-2$ non altered characters in-between. Slightly better strategies tailored to the latin square (and known/chosen plaintext if applicable) are possible. For the desired $n=28$ it is possible to objectively rank latin squares for their resistance to such attacks.
• Security can't be better than $s\log_2(n)$-bit (forgery by random choice of check characters); nor than $(t-s)\log_2(n)$-bit for known plaintext (guess of the $t-s$ characters at end of computation).

That's calling for future work.

---

Methods in Mark N. Wegman and J. Lawrence Carter's New Hash Functions and Their Use in Authentication and Set Equality, in Journal of Computer and System Sciences 22 (1981) would be great, but I did not find something easy to perform without a computer.

Answer 3

I didn't think it has to be this complicated, but the complexity is slowly creeping up.

We make every message the same length, from your question 160 characters, my method adds an extra message (the header) into the senders message, and the message again, so in transit the message is 327 characters. The sender will pad from the end of their text with white space. This may eat your key faster if you typically send 1 or 2 character messages, but it stops someone fingerprinting you from matching message lengths and allows the rest to work. Spaces at the end of the message will not be seen by the receiver.

Now before sending each message we build the header that needs to include an identifying string, a message checksum of some type, the entire message encrypted again using more of the OTP, and a new random start index of the message. Now begin the message at the index and wrap around, and place this header at a random location in the message. You would have your receiving program take out this header, then fix the messages order. Something like:

original message:"this is the message but one six zero chars"
padded message:"this is the message but one six zero chars                                                                                                                      "
identifying string:"zzzz"
checksum (my guess at the LRC character):"f"
random header position(0 to 160+7-1):7
random start index (1 to 28^2): 2 : "ab"
header:"zzzzfab"
next 160 OTP characters XORed with the message:"(160 rnd chars)"
message in transit:"(160 rnd chars) this izzzzfabs the message but one six zero chars                                                                                                                     "
message at receive:"this is the message but one six zero chars"

The identifying string should be strange and long enough not to appear in your messages. When initially transferring the OTP key also agree on this identifying string. The sender should avoid sending the identifying string in their plain message as it would goof up the receiver (but there are methods to deal with this).

The checksum, random header position and random message start index is to limit the effectiveness of MITM attacks by forcing them to guess at values. The checksum is the LRC of the other 326 characters in the message (it mainly serves to stop a MITM adding 1 to each character). The way I would implement the message start index is have at both ends a table with 28^2 = 784 different start locations, but you could make it more complex by changing the direction of text or in other ways. so for example:"aa" means start at 1 (no change). "ab" means start at 2. "ft" means start at 160. "zz" means start at 86. This table does not have to be secret, the added security comes from the index being sent with the message.

If you want to decrypt and verify then, skip 160 chars of your OTP, decrypt the whole message, skip back to the start of your OTP and decrypt the first half of the message. To check if it is authenticated make sure the values match. If you do not need to validate you can just throw away the first half and skip along in the OTP.

Re encrypting the whole message has a cost, it eats 3 bits of your OTP for each effective bit of message you send. And the message is now twice as long as the information you are sending.

Because of the scrambled order a MITM has a 1/167 chance of guessing the character position if they were attempting to change one character from the first 160 and the matching character from the remaining.

Answer 4

I've recently been interested in adding message integrity and authentication to hand ciphers, as I belong to a group of hobbyist classical cipher puzzle solvers, so discussions in this vein get people thinking.

I put together a wiki page on several approaches to adding message integrity as well as a couple ideas of adding authentication, including the answer by @fgrieu. Probably the the most practical approach without complicating the hand cipher too much is to:

1. Use the socialist millionaire protocol for authentication in the plaintext.
2. Calculate message integrity with something like the Damm algorithm.
3. Encrypt the message.

Notice that this is a MAC-then-Encrypt approach.

The recipient then:

1. Decrypts the message.
2. Looks for the authentication secrets.
   1. If the secrets do not exist or are unknown, the message may be fraudulent.
3. Calculate the checksum.
   1. If the calculated checksum does not match the sent checksum, the message might have been modified.

The goal is to produce an authentication and integrity solution that is at least as difficult to break as the security of the hand cipher. Just remember that Bruce Schneier said it best:

There are two kinds of cryptography in this world: cryptography that will stop your kid sister from reading your files, and cryptography that will stop major governments from reading your files.

This answer as about the former.

Answer 5

Authentication in one-time pad systems was a problem in WW2. How it was solved historically in the SOE at least: an agent has a pre-agreed error pattern (like making a spelling mistake in the seventh word). If he/she omitted to do this, it meant that he/she had been captured and was sending under duress. The captor did not know this pattern presumably, and would not suspect a correctly sent message. So the authentication key was the pattern of error, essentially.

Answer 6

Use a secret permutation of the alphabet as the top and side of the tabula recta used to encrypt and decrypt messages.