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.