authentication and one time pads was re advanced one time pad in article s dbminnehb elang acslab umbc edu olson umbc edu bryan olson cmsc g writes the one time pad yeilds ideal security but has a well known flaw in authentication suppose you use a random bit stream as the pad and exclusive or as the encryption operation if an adversary knows the plaintext of a message he can change it into any other message here s how it works alice is sending bob a plaintext p under a key stream s alice computes the ciphertext c s xor p and sends it to bob eve knows the plainext p but wants the message to appear as p eve intercepts c and computes c c xor p xor p s xor p eve sends c to bob bob decrypts c by computing c xor s p thus receiving the false message which was substituted by eve firstly an aside i agree that the weakness exists but i have a lot of trouble believing that it represents a difficulty in real life given the purpose of the one time pad is to give unbreakable security and the expense of key distribution etc imply that the clients really do want that level of security these same people want to keep p a secret i find it hard to believe that eve might happen to have a copy of p lying around i am aware that the same argument applies to eve knowing even a small part of the message but eve must know exactly where which bytes in c her known susequence starts or the result will be garbled i find this at least as surprising back to the question if i had the resources to use a one time pad for such transmissions i would also append a message authentication code to the message using up the next bits of the one time pad as the key perhaps your original question basically asked whether there was any way to authenticate the message with the same degree of security as the pad itself provided and i don t know the answer however i would propose the following for discussion alice and bob have an arbitrary number of secret random bits to share which eve doesn t know she finds them out effectively by knowing some p and the corresponding c it is the fact that they correspond that causes the problem if a message authentication code was to be created using some one time pad operation such that eve could not know which parts of the mac were affected by which parts of the input she would be unable to forge a mac to correspond what is required is a non linear combiner of parts of the message non linear so that simply xoring or subtracting or whatever doesn t have exactly the same effect now at the end of the encrypted message c alice appends a n bit mac computed as follows s means the next full chunk of the one time pad compute c p xor s and pad to an n bit boundary with more of s break c into n bit chunks set mac to initialisation vector for i in each chunk sequentially set mac mac nlop c i at the end of this process mac is the message authentication code bob verifies the mac in the obvious manner he recovers the plaintext p then uses some more of his pad to reproduce the mac in the same manner nlop is the non linear operator and there is the rub the simplest non linear operator i can think of is an s box that is have a fixed even published permutation of the n bit integers an indexable table called sbox and use x nlop y x xor sbox y practically speaking i think this solves your problem as eve never sees the intermediate output c and hence can t deduce s or perform any valid substitution on it also practically speaking you want the mac to be fairly large say bits but you might not want a gigabyte say s box so you might work on byte sized s boxes but i think that is an irrelevant detail for the discussion at hand who will be first to point out my errors or give me a pointer to some literature greg rose australian computing and communications institute ggr acci com au use of the standard phrase hijacked may be inadvisable caa
