What is the best way to prove that you wrote the encrypted message on a piece of paper? As most of us know, many conspirators have died because of false message implants, Mary Queen of Scots, for example.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Moreover, how can one prove the integrity of that message. $\endgroup$– PatriotCommented Jun 27, 2019 at 21:56
-
$\begingroup$ Signature schemes work - regardless if you print out the message on paper. And signatures can be used to prove authenticity. If you look for a scheme to be done by hand, this is insecure if an adversary has access to a computer. $\endgroup$– tyloCommented Jun 28, 2019 at 20:12
-
$\begingroup$ @Neo1009 I presume that one can only use paper and pencil to authenticate that message. Is that right? – $\endgroup$– PatriotCommented Jul 8, 2019 at 12:57
-
$\begingroup$ @Patriot yes that is correct. $\endgroup$– Neo1009Commented Jul 18, 2019 at 22:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
You have asked about the authentication of a hand-written message, but let's also include an integrity check as a desired service.
Let's say that your message was encrypted with a one-time pad. The following methods of early modern cryptography will not do:
(1) Russian copulation (which is designed to further conceal names, headers, salutations, etc.)
(2) Variable-length padding
(3) Using a reasonably-sized tabula recta
For example:
Plaintext (your message): DONOT NEGOT IATE
Truly random key: JQOXF RMSUA PWBI
-------------------
Ciphertext: MEBLY EQYIT XWUM
Variable padding added:
KIPXQ NECEM EBLYE QYITX WUMRZ NUDOA DIEHL ARAIT EMONG ESEBO SLAVO
But this is no solution. People used to simply take it for granted that the message was authenticated because their pre-shared symmetric key worked to decrypt it.
Option A
However, one could take advantage of having pre-shared secrets, especially with the OTP because this must have already been done anyway. First, determine the size limit of the ciphertexts that will be sent. For example--choose thirty-one characters-- and draw a box, say 31 columns wide and 34 rows deep. Write the plaintext across the top in the first row. Yes, this is going to be a short message, but notice that this system might be amenable to using code. Next, under each character of the plaintext, write the predetermined 31-character authenticator for that character. For example:
DONOT NEGOT IATE (__truly random, pre-established, one-time, filler__)
DONO...
FTID...
GWOZ...
NRFG...
RIUW...
QESD...
JFLK...
GUEE...
MUNF...
ARAI...
TEMO...
NGES...
EBOS...
LAVO...
WAZY...
QLYX...
etc.
etc.
To clarify, this means that each character in the plaintext will have a thirty-one character authenticator, and these will always be different (which recalls homophonic substitution and your reference to Mary Queen of Scots).
It is crucial that all of these values be generated in a "truly random" manner.
There will be a table similar to this:
If 1st character is "A" = KFGEIOGZUZDOITSEHAJNWNSYFEBMAXY
If 1st character is "B" = BREHYEMKIDHFDDJBDIHTDZGDOODYHWV
(etc.)
If 2nd character is "A" = VRDABALALAJEOQZFURJVLPQWVMVAECZ
(etc.)
So, each character in the ciphertext will correspond to one of the 26 possible authenticators, and this is going to end up being a little booklet of truly random values.
The last two rows will be a truly random authenticator which will match the indicator tag. The indicator tag will appear above the message, and will mainly be used for convenience--to indicate message sequence and which key to use.
For example (which is not to be encrypted):
AVRAL OBESE XIANG POLAR GRIME TIARA HANOI THUGZ
It will, of course, correspond with the shared secret authenticator in the last two rows of the message. Both will be non-sequential. The shared secret authenticator will only be used once. As you can see, the pre-established size of the message is very important.
Again, the authenticator will be 62 characters long and take up the last two rows of the message.
For example:
ATSOHKIFZPYTSWTEHKANNAVASUUXWO
IMDYSDFFLHTGEISOUBZFWQBXRQOKSI
Now, pass your intended one-time pad key over the whole thing.
Note: for this option we could expand the alphabet for added strength. Everything is going to depend on the strength of the key, and a long key it will be.
Option B
Using Poly1305 by hand might be a solution, but that is going to take some work. You are also going to have to devise a method for adding that information to your message. Poly1305 has a 32-bit preshared key that cannot be reused. Good advice, coming from forest and, graciously, from Ross J. Anderson himself, says use a Carter-Wegman universal hash function.
Option C
Construct a one-time MAC according to these instructions.
-
1$\begingroup$ There are some manual problems with a C (OTMAC). Those instructions start with using 340282366920938463463374607431768211507 for $q$ if chunking 128 bit groups. A OTP block is 8 bits (or even less). So you either go large (tricky with an abacus) or small and repeat 16 times (or more) per message with 1st prime $>2^8$ (257). Then you might need another 16 $x,y$ unique pairs. Option B (poly) is going to be similarly complex to compute as you've realised. $\endgroup$ Commented Aug 4, 2019 at 12:21
-
$\begingroup$ This is what I was driving at with the other answer. It's very hard to apply modern strong MAC things to a paper based system. There has to be compromise. Or revert to the old ways of radio burst Morse transmission which doesn't need authentication. An acoustic (de)modulator would be simplish to make. $\endgroup$ Commented Aug 4, 2019 at 12:45
-
$\begingroup$ @PaulUszak I am with you. These are some interesting questions. I want to make the solutions work. $\endgroup$– PatriotCommented Aug 4, 2019 at 12:54
$\begingroup$
$\endgroup$
I believe you could use Encrypt-last-block CBC-MAC (ECBC-MAC) with random permutations as "block ciphers" and a one-time pad to encrypt the last blocks. See my answer to a similar question. Pretty sure the scheme is secure
