2
$\begingroup$

Consider the following paper based OTP

  1. Plaintext has 11 possible symbols 0-10.
  2. $C_i = M_i + K_i\ mod\ 11$.
  3. $K_i$ comes from a pre-shared key material which is never reused.

How to introduce data integrity/ MAC in it which can be calculated using pen & paper.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Use SHA3-224 HMAC.

Define a security parameter $\kappa$, and both sides consume that much $K_i$ keying material. A paper based OTP will probably choose a smaller parameter than a TCP-based protocol would choose.

Compute and append the $\kappa$ prefix of the HMAC result to the message, encoded as base 11 digits.

Transmit the $C_i$ message as above.

Receiver computes HMAC and verifies that the prefix matches.

EDIT

...which can be calculated using pen & paper.

Oohhhh. Well there's a new wrinkle.

Define a new security parameter $D$, number of check digits to send.

Define a base $B$. It most naturally would be 11, but for human convenience we may choose to make it 10. It is possible that some casting out nines procedure would motivate using 9.

Find a running total of the various $M_i$ figures, $\mod B$, and write the number down beneath each $M_i$.

Append the final $D$ such numbers to the message.

Transmit this augmented message as OP describes. Notice that each check digit is protected by its own $K_i$.

Receiver performs the same steps to verify.


Observation: Mallet has a much better chance for undetected corruption of one of the final $D$ characters of the original message under this "scheme-A", especially if he wants to corrupt its final character.

Remedy: In "scheme-B", consume $D$ characters of the $K_i$ keying material and append those to the original message at the very beginning of the procedure, so we're transmitting a checksum of characters both unknown and known to the recipient.


Assume that "keying material is cheap", so for example we are willing to consume 200 characters of $K_i$ to send a message of length 100. Could we use that to improve robustness? Assume that "$D$ is small", that is, $D < \sqrt{ |M| }$ where $|M|$ is length of message.

Second observation: Humans are fallible. Sometimes we write down arithmetic mistakes. Could we rescue parts of a message that Alice accidentally garbled?

Remedy: Starting from the message's end, break out $D$ message chunks. Most will be of equal size; the first few are likely to be shorter by one. Compute and transmit per-chunk checksums independently.

At this point I also want to send "more than one" (how many?) combined checksum digits which summarize the individual transmitted checksums. Maybe one for the odds, one for the evens? Or a tree that transmits eight checksums, then four checksums of pairs, then two checksums, then finally a master checksum?

Leaning on the "fallibility" aspect, maybe spend part of our checksum budget on computing / transmitting checksums of reversed message characters?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.