8
$\begingroup$

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.

|improve this question
$\endgroup$
  • $\begingroup$ Sending the message in multiples is only bad if the attacker has meta data of the cypher (message length, time it was sent). If instead of 1 message you had a continuous stream (with random data filling the gaps between messages, or offline) then an observer wouldn't be able to do much in the middle. $\endgroup$ – daniel May 30 '17 at 23:40
  • $\begingroup$ @daniel This isn't a hypothetical question. UK Investigatory Powers Act 2016 means that all the meta data will be captured. I expect port hopping won't defeat the act. I'm not sure yet how much meta data can be hidden by SSL, but I think that it's not much. $\endgroup$ – Paul Uszak May 31 '17 at 0:15
  • $\begingroup$ Since comments are not for extended discussion; I moved my OTP transport chit-chat to a chatroom. After all, the Q here assumes "Sufficient hardware generated one time pad key material" to be available… most probably at both sides (sender/receiver). $\endgroup$ – e-sushi May 31 '17 at 9:47
  • $\begingroup$ what about xor-ing a known secret with a summation of the message, say the start or perhaps every 5th letter, appending that to the end of the plaintext before encrypting, separated by a reserved char. $\endgroup$ – dandavis Jun 1 '17 at 4:18
  • 1
    $\begingroup$ @eckes but for a MitM, a partially known plain text attack without other mechanisms its easy to change a value. Example "attack at 7 pm" can be changed to "attack at 8 pm" so the attack can split the 2 generals up just by adding 1 to the cipher text, if they know most of the plain text. they can do the same if the message is repeated in some way they also know. $\endgroup$ – daniel Jun 2 '17 at 9:01
3
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Very interesting. Is your formulae correct now? It's gone from 96% to 4% certainty. $\endgroup$ – Paul Uszak Oct 9 '18 at 18:59
  • 1
    $\begingroup$ And, can there be more than one tabula recta for any alphabet size? $\endgroup$ – Paul Uszak Oct 9 '18 at 19:00
  • 1
    $\begingroup$ Your alphabet is 28 characters long so the odds of a successful forgery would be 1 against 28^3, or 0.005%. So 99.995% confidence of authenticity, assuming my math is correct. $\endgroup$ – Meler Lawler Oct 9 '18 at 22:54
  • 1
    $\begingroup$ @MelerLawler Strictly speaking, you have verified the integrity of the plaintext to a quantifiable degree, but not its authenticity, correct? We take it that the message is authentic if our one-time pad works for decryption, and especially if it works with a pre-understood value for Russian Copulation. But do we in fact know the message is authentic? That is, signed by the sender we think. Is using the OTP the same as signing? $\endgroup$ – Patriot Jul 7 '19 at 1:55
  • 1
    $\begingroup$ Correct. I think all symmetric encryption (e.g. OTP) is inherently authenticated. So there's no reason to verify that the sender is who you think they are, just that their message hasn't been edited by someone else before it reached you. $\endgroup$ – Meler Lawler Jul 10 '19 at 23:47
5
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ @Paul Uszak: My system with $s=4$, $t=10$ is a 4-char wide Message Authenticator with 10-char one-time key. Contrary to a full-blown MAC, but just as in as in a Wegman-Carter authentication / universal hashing , the key must not be reused. That, and the moderate security (especially against local alterations), is a price for simple computation, and seems to match High security is of secondary importance. I plan to publish a latin square with quantified security against the attack in the third bullet by next week. Apologies for the premature wear of your board's paraphernalia :-) $\endgroup$ – fgrieu Jun 5 '17 at 14:15
  • 3
    $\begingroup$ I'm interested in seeing an example of this in action. i'm trying to make sense of it, but struggling to understand it fully. A simple example with the message "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG" and OTP key would be awesome. Perhaps a pastebin? $\endgroup$ – Aaron Toponce Sep 7 '18 at 15:57
  • 1
    $\begingroup$ @fgrieu I am very interested in seeing an example of this in action. No one that I can find on the internet has given a clear example of this. Claims of good security have been made by others, but no one has followed through and shown a good example. $\endgroup$ – Patriot Jul 23 '19 at 12:27
  • 1
    $\begingroup$ @fgrieu Please do that "future work"! I am sure several readers are waiting to see it. $\endgroup$ – Patriot Jul 23 '19 at 12:51
  • 1
    $\begingroup$ @Patriot it appears Aaron Toponce has worked out an example at aarontoponce.org/wiki/crypto/authentication $\endgroup$ – Lily Chung Oct 15 '19 at 7:34
3
$\begingroup$

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.

|improve this answer
$\endgroup$
2
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ The verification is only useful, if the message itself is secret. If the message is not secret, it is trivial to reproduce the otp and replace the message with another. If the checksum is weak it may be possible to know and change only part of the message. $\endgroup$ – Meir Maor May 30 '17 at 9:51
  • $\begingroup$ WRT "random looking" - think OTPed Twitter. So yes whilst sending random A-Z characters might conceivably happen, vast majority of messages would be what passes for language in the Twittersphere. $\endgroup$ – Paul Uszak May 30 '17 at 10:02
  • $\begingroup$ To make progress, we have to assume that the OTPs are secret and the messages are secret. This is the classical use case for historical OTP codes. I think that known plain text attacks will have to be considered as part of a second phase feasibility assessment... $\endgroup$ – Paul Uszak May 30 '17 at 12:38
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi May 31 '17 at 8:26
  • $\begingroup$ "MitM just needs to change so they don't work" - I've never considered this! Thank you. The usual case is to substitute the MitM's information. It never occurred that a successful attack would also be to simply disrupt the message. Is this where MitM attacks become akin to signal jamming? I wonder if the community makes this a formal distinction? $\endgroup$ – Paul Uszak Jun 2 '17 at 9:58
1
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Excellent! Do you have any references to the error authentication? Can I infer that Man in the Middle situations were not catered for? And that MitM attacks are not probable or realistic most of the time. $\endgroup$ – Paul Uszak Jun 4 '17 at 22:09
  • 3
    $\begingroup$ It's in "between silk and cyanide", a book on the history of cryptography in the SOE. They used radio directly. MITM was not considered a threat there. @PaulUszak $\endgroup$ – Henno Brandsma Jun 4 '17 at 22:18
  • $\begingroup$ They didn't all use radio. What about pigeons? Could they be intercepted and subjected to MITM men? $\endgroup$ – Paul Uszak Jun 20 '17 at 0:33
  • 1
    $\begingroup$ @Patriot the VIC cipher had no authentication AFAIK. $\endgroup$ – Henno Brandsma Jul 23 '19 at 12:46
  • 1
    $\begingroup$ @Patriot I’d say that’s just the system description as a whole, plus key information. If you knew all that it had to be the real agent, they probably thought. But there is no check as such, or a duress codeword. $\endgroup$ – Henno Brandsma Jul 23 '19 at 13:48
1
$\begingroup$

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

|improve this answer
$\endgroup$

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.