Why do one-time pads not provide message authentication?One Time Pads and “Bit Flip” AttacksWould this simple encrypted chat program be feasible using One Time Pads?efficient authentication with broadcast encryption?Can you really insert the text you want in one-time pad?Is there a companion algorithm for OTP to ensure integrity and/or authentication?Can you exchange a shared key without any hardness assumptions?zendo data size restrictionsUnconditionally Secure AuthenticationClarification of Proof: Proving perfect secrecy for One Time PadsDoes one time pad randomness help brute force attacks?

Why does Principal Vagina say, "no relation" after introducing himself?

What does the British parliament hope to achieve by requesting a third Brexit extension?

How to respond to "Why didn't you do a postdoc after your PhD?"

What are the branches of statistics?

The travel to a friend

Advisor asked for my entire slide presentation so she could give the presentation at an international conference

I got this nail stuck in my tire, should I plug or replace?

I think Dollar General ran my debit card as a credit - how can I resolve this?

What happens if R is not revealed by one of Lightning Network nodes? (Payment cancelation)

How do I reset the TSA-unlocked indicator on my lock?

Can we not simply connect a battery to a RAM to prevent data loss during power cuts?

Why do one-time pads not provide message authentication?

What does すきすき mean here?

Is Schrodinger's Cat itself an observer?

Does an excessive table violate normalization rules?

Which culture used no personal names?

Does my protagonist need to be the most important character?

What is the design rationale for having armor and magic penetration mechanics?

My Villain scrys on the party, but I forgot about the sensor!

Fermat's polygonal number theorem

Can digital computers understand infinity?

Is it now possible to undetectably cross the Arctic Ocean on ski/kayak?

2 Guards, 3 Keys, 2 Locks

What does this text mean with capitalized letters?



Why do one-time pads not provide message authentication?


One Time Pads and “Bit Flip” AttacksWould this simple encrypted chat program be feasible using One Time Pads?efficient authentication with broadcast encryption?Can you really insert the text you want in one-time pad?Is there a companion algorithm for OTP to ensure integrity and/or authentication?Can you exchange a shared key without any hardness assumptions?zendo data size restrictionsUnconditionally Secure AuthenticationClarification of Proof: Proving perfect secrecy for One Time PadsDoes one time pad randomness help brute force attacks?






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;

.everyonelovesstackoverflowposition:absolute;height:1px;width:1px;opacity:0;top:0;left:0;pointer-events:none;








1














$begingroup$


It is often said that one-time pads do not provide message authentication. But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication? The probability of you getting a non-gibberish message is, I would have to spam you a noticeable quantity of messages to get one that decodes to something resembling what you expect to get.



Update: I was mostly considering attacks where ciphertext is not known, but the recipient is known. In that case, to try and guess what to send them is impossible, and the message seems like it is inherently authenticated. An attacker intercepting the ciphertext could, like the answers say, alter a bit here or there, maybe it could be good to have a message authentication hash as well.










share|improve this question









New contributor



Lol4 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$











  • 1




    $begingroup$
    Because if I can guess from context what any one part of the message might be, then I know exactly how to modify that part to read like something else of my choice.
    $endgroup$
    – Natanael
    8 hours ago










  • $begingroup$
    how can you guess from ciphertext encrypted with a symmetric key?
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    Yes, and remember that it doesn't have to be a malicious attacker. Or any person at all. It can just be innocent random transmission errors or a noisy channel due to atmospherics or a dodgy Ethernet connector. It would be embarrassing to invade the wrong country due to poor electrics. A British SAS team invaded France just a few years back, due to a communications mistake. And they all got arrested by a gendarme...
    $endgroup$
    – Paul Uszak
    5 hours ago

















1














$begingroup$


It is often said that one-time pads do not provide message authentication. But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication? The probability of you getting a non-gibberish message is, I would have to spam you a noticeable quantity of messages to get one that decodes to something resembling what you expect to get.



Update: I was mostly considering attacks where ciphertext is not known, but the recipient is known. In that case, to try and guess what to send them is impossible, and the message seems like it is inherently authenticated. An attacker intercepting the ciphertext could, like the answers say, alter a bit here or there, maybe it could be good to have a message authentication hash as well.










share|improve this question









New contributor



Lol4 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$











  • 1




    $begingroup$
    Because if I can guess from context what any one part of the message might be, then I know exactly how to modify that part to read like something else of my choice.
    $endgroup$
    – Natanael
    8 hours ago










  • $begingroup$
    how can you guess from ciphertext encrypted with a symmetric key?
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    Yes, and remember that it doesn't have to be a malicious attacker. Or any person at all. It can just be innocent random transmission errors or a noisy channel due to atmospherics or a dodgy Ethernet connector. It would be embarrassing to invade the wrong country due to poor electrics. A British SAS team invaded France just a few years back, due to a communications mistake. And they all got arrested by a gendarme...
    $endgroup$
    – Paul Uszak
    5 hours ago













1












1








1





$begingroup$


It is often said that one-time pads do not provide message authentication. But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication? The probability of you getting a non-gibberish message is, I would have to spam you a noticeable quantity of messages to get one that decodes to something resembling what you expect to get.



Update: I was mostly considering attacks where ciphertext is not known, but the recipient is known. In that case, to try and guess what to send them is impossible, and the message seems like it is inherently authenticated. An attacker intercepting the ciphertext could, like the answers say, alter a bit here or there, maybe it could be good to have a message authentication hash as well.










share|improve this question









New contributor



Lol4 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$




It is often said that one-time pads do not provide message authentication. But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication? The probability of you getting a non-gibberish message is, I would have to spam you a noticeable quantity of messages to get one that decodes to something resembling what you expect to get.



Update: I was mostly considering attacks where ciphertext is not known, but the recipient is known. In that case, to try and guess what to send them is impossible, and the message seems like it is inherently authenticated. An attacker intercepting the ciphertext could, like the answers say, alter a bit here or there, maybe it could be good to have a message authentication hash as well.







symmetric authentication authenticated-encryption one-time-pad






share|improve this question









New contributor



Lol4 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.










share|improve this question









New contributor



Lol4 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








share|improve this question




share|improve this question



share|improve this question








edited 5 hours ago







Lol4













New contributor



Lol4 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








asked 8 hours ago









Lol4Lol4

62 bronze badges




62 bronze badges




New contributor



Lol4 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.




New contributor




Lol4 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • 1




    $begingroup$
    Because if I can guess from context what any one part of the message might be, then I know exactly how to modify that part to read like something else of my choice.
    $endgroup$
    – Natanael
    8 hours ago










  • $begingroup$
    how can you guess from ciphertext encrypted with a symmetric key?
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    Yes, and remember that it doesn't have to be a malicious attacker. Or any person at all. It can just be innocent random transmission errors or a noisy channel due to atmospherics or a dodgy Ethernet connector. It would be embarrassing to invade the wrong country due to poor electrics. A British SAS team invaded France just a few years back, due to a communications mistake. And they all got arrested by a gendarme...
    $endgroup$
    – Paul Uszak
    5 hours ago












  • 1




    $begingroup$
    Because if I can guess from context what any one part of the message might be, then I know exactly how to modify that part to read like something else of my choice.
    $endgroup$
    – Natanael
    8 hours ago










  • $begingroup$
    how can you guess from ciphertext encrypted with a symmetric key?
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    Yes, and remember that it doesn't have to be a malicious attacker. Or any person at all. It can just be innocent random transmission errors or a noisy channel due to atmospherics or a dodgy Ethernet connector. It would be embarrassing to invade the wrong country due to poor electrics. A British SAS team invaded France just a few years back, due to a communications mistake. And they all got arrested by a gendarme...
    $endgroup$
    – Paul Uszak
    5 hours ago







1




1




$begingroup$
Because if I can guess from context what any one part of the message might be, then I know exactly how to modify that part to read like something else of my choice.
$endgroup$
– Natanael
8 hours ago




$begingroup$
Because if I can guess from context what any one part of the message might be, then I know exactly how to modify that part to read like something else of my choice.
$endgroup$
– Natanael
8 hours ago












$begingroup$
how can you guess from ciphertext encrypted with a symmetric key?
$endgroup$
– Lol4
7 hours ago




$begingroup$
how can you guess from ciphertext encrypted with a symmetric key?
$endgroup$
– Lol4
7 hours ago












$begingroup$
Yes, and remember that it doesn't have to be a malicious attacker. Or any person at all. It can just be innocent random transmission errors or a noisy channel due to atmospherics or a dodgy Ethernet connector. It would be embarrassing to invade the wrong country due to poor electrics. A British SAS team invaded France just a few years back, due to a communications mistake. And they all got arrested by a gendarme...
$endgroup$
– Paul Uszak
5 hours ago




$begingroup$
Yes, and remember that it doesn't have to be a malicious attacker. Or any person at all. It can just be innocent random transmission errors or a noisy channel due to atmospherics or a dodgy Ethernet connector. It would be embarrassing to invade the wrong country due to poor electrics. A British SAS team invaded France just a few years back, due to a communications mistake. And they all got arrested by a gendarme...
$endgroup$
– Paul Uszak
5 hours ago










2 Answers
2






active

oldest

votes


















1
















$begingroup$


get one that decodes to something resembling what you expect to get.




You don't always expect the exact detail though. You might transmit "Buy 1 million shares in ...", but the other end might receive "Buy 5 million shares in ..." due to malice or a noisy channel. One altered/corrupted bit might easily decode to something entirely sensible as I've shown. That depends on the mapping function in the decoding part of the cipher. $textDecode(c_i, k_i)$ may easily produce convincing output with a single bit's hamming distance between any two $c_i$ characters. 1 and 5 may very well be adjacent mappings within the $textDecode$ function.



It's not this is that likely though as you suggest. It's that this is statistically possible within the bounds of secure communication. It's called malleability in that the message can be 'shaped' to something else, either by accident or design. Thus some form of authentication mechanism (MAC) is warranted.






share|improve this answer










$endgroup$














  • $begingroup$
    how would you change "1" to "5" if you have ciphertext where you have absolutely no idea what the message it encrypts says?
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    to "shape" the message into something else, if you have absolutely no idea what the message is, you have to send all those "something else" to the receiving party, because they are the only one who can decode the ciphertext. They will notice that you spam them.
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    how is that not message authentication? if the only way someone else can fabricate a message to me is by sending me a trillion messages, I will just know. like, spam emails. you know its spam when you get a million requests from rich people wanting to give you money if you give them your bank account login codes.
    $endgroup$
    – Lol4
    7 hours ago











  • $begingroup$
    @Lol4 The One-Time Pad model doesn't allow you to assume that the adversary knows nothing about your message. It allows you to assume that the adversary cannot use the ciphertext to learn anything more about the message than they already know.
    $endgroup$
    – Ella Rose
    7 hours ago







  • 1




    $begingroup$
    @Lol4 Imagine it's your money that you've massively leveraged and you get this message. It was a "1" but it decoded to a "5" due to random tractor noise on the line, miss-keying by the telegraph operator or absolute flukey chance by an attacker trying to put you out of business. The important thing is that I've demonstrated that it's possible to receive an unauthentic message without recognising it. So OTP = malleable.
    $endgroup$
    – Paul Uszak
    7 hours ago


















1
















$begingroup$


But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication?




The informal criterion of "not complete gibberish" that you are applying here has two problems:




  • Malleability: It is trivial to modify OTP-encrypted ciphertexts so that they will decrypt to something that's unlikely to be "complete gibberish";


  • Computers are dumb: It assumes that the decrypted message is read by a human being possessed of common sense instead of acted upon by a dumb computer;

Malleability



This is the property many ciphers have that an attacker that doesn't know the key can nevertheless modify a ciphertext in such a way as to cause a predictable change in the plaintext it will decrypt to. One-time pads and stream ciphers (the computationally secure variant thereof) are subject to one particularly trivial form of this:



  • If you flip any bit of a ciphertext, that causes the corresponding bit of the plaintext to flip.

This means that if I flip a bit in a ciphertext, the resulting fake plaintext will be minimally different from the real one. I hope you agree this means it's unlikely to be "gibberish."



In comments you've expressed skepticism that an attacker could exploit that to fool a recipient, because they'd have to know or guess a fair amount about the plaintext that corresponds to a the ciphertext. But that's a condition that is often met in real life—for example we routinely encrypt network protocols and file formats that are publicly specified and such that an attacker can effectively guess the protocolar "skeleton" of encrypted messages. And we don't want them to be able to exploit this to modify that skeleton.



Computers are dumb



The other problem is that the scenario you're implicitly contemplating—a human being, possessed of common sense, reading a single decrypted message—is not the norm by any means. Most decrypted messages are acted upon by computers, slavishly literal and poorly programmed machines that will happily repeat the same humanly-absurd mistake billions of time per second with unintended consequences that nobody predicted. We can't rely on some common-sense human notion of "gibberish" to reject forgeries—we need a fool-proof mechanical way of rejecting forgeries, one that not even a computer can goof up.



Example: EFail attack



One recent real-life example that combines these two motifs is the EFail attack on encrypted email. It exploits:




  • Malleability: The attacker is able to modify an HTML emails' ciphertext to craft a forgery that decrypts to an HTML image tag with the original plaintext inside its URL;


  • Computers are dumb: Many email clients will obliviously decrypt that forged message and automatically make the HTTP request for the forged image tag before showing the plaintext to the user.

EFail is an attack against CBC-mode encryption, not stream ciphers or one-time pads, but cryptographers' general attitude to malleability is that it should not be allowed in practical systems, period.






share|improve this answer










$endgroup$














  • $begingroup$
    it isn't trivial to modify OTP-encrypted ciphertexts. a thousand bit message, a thousand possible bits you can alter, you have no knowledge of the message, and the recipient notices if you spam them with a thousand bits. if you want to get lucky and switch a "1" to a "5" without knowing what the message even says, that is not "trivial".
    $endgroup$
    – Lol4
    6 hours ago










  • $begingroup$
    I was mostly considering attacks where ciphertext is not known, as well (but the recipient is known. ) In that case, to try and guess what to send them is impossible. To intercept the message is more work.
    $endgroup$
    – Lol4
    6 hours ago












Your Answer








StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);







Lol4 is a new contributor. Be nice, and check out our Code of Conduct.









draft saved

draft discarded
















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f74880%2fwhy-do-one-time-pads-not-provide-message-authentication%23new-answer', 'question_page');

);

Post as a guest















Required, but never shown


























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









1
















$begingroup$


get one that decodes to something resembling what you expect to get.




You don't always expect the exact detail though. You might transmit "Buy 1 million shares in ...", but the other end might receive "Buy 5 million shares in ..." due to malice or a noisy channel. One altered/corrupted bit might easily decode to something entirely sensible as I've shown. That depends on the mapping function in the decoding part of the cipher. $textDecode(c_i, k_i)$ may easily produce convincing output with a single bit's hamming distance between any two $c_i$ characters. 1 and 5 may very well be adjacent mappings within the $textDecode$ function.



It's not this is that likely though as you suggest. It's that this is statistically possible within the bounds of secure communication. It's called malleability in that the message can be 'shaped' to something else, either by accident or design. Thus some form of authentication mechanism (MAC) is warranted.






share|improve this answer










$endgroup$














  • $begingroup$
    how would you change "1" to "5" if you have ciphertext where you have absolutely no idea what the message it encrypts says?
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    to "shape" the message into something else, if you have absolutely no idea what the message is, you have to send all those "something else" to the receiving party, because they are the only one who can decode the ciphertext. They will notice that you spam them.
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    how is that not message authentication? if the only way someone else can fabricate a message to me is by sending me a trillion messages, I will just know. like, spam emails. you know its spam when you get a million requests from rich people wanting to give you money if you give them your bank account login codes.
    $endgroup$
    – Lol4
    7 hours ago











  • $begingroup$
    @Lol4 The One-Time Pad model doesn't allow you to assume that the adversary knows nothing about your message. It allows you to assume that the adversary cannot use the ciphertext to learn anything more about the message than they already know.
    $endgroup$
    – Ella Rose
    7 hours ago







  • 1




    $begingroup$
    @Lol4 Imagine it's your money that you've massively leveraged and you get this message. It was a "1" but it decoded to a "5" due to random tractor noise on the line, miss-keying by the telegraph operator or absolute flukey chance by an attacker trying to put you out of business. The important thing is that I've demonstrated that it's possible to receive an unauthentic message without recognising it. So OTP = malleable.
    $endgroup$
    – Paul Uszak
    7 hours ago















1
















$begingroup$


get one that decodes to something resembling what you expect to get.




You don't always expect the exact detail though. You might transmit "Buy 1 million shares in ...", but the other end might receive "Buy 5 million shares in ..." due to malice or a noisy channel. One altered/corrupted bit might easily decode to something entirely sensible as I've shown. That depends on the mapping function in the decoding part of the cipher. $textDecode(c_i, k_i)$ may easily produce convincing output with a single bit's hamming distance between any two $c_i$ characters. 1 and 5 may very well be adjacent mappings within the $textDecode$ function.



It's not this is that likely though as you suggest. It's that this is statistically possible within the bounds of secure communication. It's called malleability in that the message can be 'shaped' to something else, either by accident or design. Thus some form of authentication mechanism (MAC) is warranted.






share|improve this answer










$endgroup$














  • $begingroup$
    how would you change "1" to "5" if you have ciphertext where you have absolutely no idea what the message it encrypts says?
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    to "shape" the message into something else, if you have absolutely no idea what the message is, you have to send all those "something else" to the receiving party, because they are the only one who can decode the ciphertext. They will notice that you spam them.
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    how is that not message authentication? if the only way someone else can fabricate a message to me is by sending me a trillion messages, I will just know. like, spam emails. you know its spam when you get a million requests from rich people wanting to give you money if you give them your bank account login codes.
    $endgroup$
    – Lol4
    7 hours ago











  • $begingroup$
    @Lol4 The One-Time Pad model doesn't allow you to assume that the adversary knows nothing about your message. It allows you to assume that the adversary cannot use the ciphertext to learn anything more about the message than they already know.
    $endgroup$
    – Ella Rose
    7 hours ago







  • 1




    $begingroup$
    @Lol4 Imagine it's your money that you've massively leveraged and you get this message. It was a "1" but it decoded to a "5" due to random tractor noise on the line, miss-keying by the telegraph operator or absolute flukey chance by an attacker trying to put you out of business. The important thing is that I've demonstrated that it's possible to receive an unauthentic message without recognising it. So OTP = malleable.
    $endgroup$
    – Paul Uszak
    7 hours ago













1














1










1







$begingroup$


get one that decodes to something resembling what you expect to get.




You don't always expect the exact detail though. You might transmit "Buy 1 million shares in ...", but the other end might receive "Buy 5 million shares in ..." due to malice or a noisy channel. One altered/corrupted bit might easily decode to something entirely sensible as I've shown. That depends on the mapping function in the decoding part of the cipher. $textDecode(c_i, k_i)$ may easily produce convincing output with a single bit's hamming distance between any two $c_i$ characters. 1 and 5 may very well be adjacent mappings within the $textDecode$ function.



It's not this is that likely though as you suggest. It's that this is statistically possible within the bounds of secure communication. It's called malleability in that the message can be 'shaped' to something else, either by accident or design. Thus some form of authentication mechanism (MAC) is warranted.






share|improve this answer










$endgroup$




get one that decodes to something resembling what you expect to get.




You don't always expect the exact detail though. You might transmit "Buy 1 million shares in ...", but the other end might receive "Buy 5 million shares in ..." due to malice or a noisy channel. One altered/corrupted bit might easily decode to something entirely sensible as I've shown. That depends on the mapping function in the decoding part of the cipher. $textDecode(c_i, k_i)$ may easily produce convincing output with a single bit's hamming distance between any two $c_i$ characters. 1 and 5 may very well be adjacent mappings within the $textDecode$ function.



It's not this is that likely though as you suggest. It's that this is statistically possible within the bounds of secure communication. It's called malleability in that the message can be 'shaped' to something else, either by accident or design. Thus some form of authentication mechanism (MAC) is warranted.







share|improve this answer













share|improve this answer




share|improve this answer



share|improve this answer










answered 7 hours ago









Paul UszakPaul Uszak

9,1331 gold badge18 silver badges43 bronze badges




9,1331 gold badge18 silver badges43 bronze badges














  • $begingroup$
    how would you change "1" to "5" if you have ciphertext where you have absolutely no idea what the message it encrypts says?
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    to "shape" the message into something else, if you have absolutely no idea what the message is, you have to send all those "something else" to the receiving party, because they are the only one who can decode the ciphertext. They will notice that you spam them.
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    how is that not message authentication? if the only way someone else can fabricate a message to me is by sending me a trillion messages, I will just know. like, spam emails. you know its spam when you get a million requests from rich people wanting to give you money if you give them your bank account login codes.
    $endgroup$
    – Lol4
    7 hours ago











  • $begingroup$
    @Lol4 The One-Time Pad model doesn't allow you to assume that the adversary knows nothing about your message. It allows you to assume that the adversary cannot use the ciphertext to learn anything more about the message than they already know.
    $endgroup$
    – Ella Rose
    7 hours ago







  • 1




    $begingroup$
    @Lol4 Imagine it's your money that you've massively leveraged and you get this message. It was a "1" but it decoded to a "5" due to random tractor noise on the line, miss-keying by the telegraph operator or absolute flukey chance by an attacker trying to put you out of business. The important thing is that I've demonstrated that it's possible to receive an unauthentic message without recognising it. So OTP = malleable.
    $endgroup$
    – Paul Uszak
    7 hours ago
















  • $begingroup$
    how would you change "1" to "5" if you have ciphertext where you have absolutely no idea what the message it encrypts says?
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    to "shape" the message into something else, if you have absolutely no idea what the message is, you have to send all those "something else" to the receiving party, because they are the only one who can decode the ciphertext. They will notice that you spam them.
    $endgroup$
    – Lol4
    7 hours ago










  • $begingroup$
    how is that not message authentication? if the only way someone else can fabricate a message to me is by sending me a trillion messages, I will just know. like, spam emails. you know its spam when you get a million requests from rich people wanting to give you money if you give them your bank account login codes.
    $endgroup$
    – Lol4
    7 hours ago











  • $begingroup$
    @Lol4 The One-Time Pad model doesn't allow you to assume that the adversary knows nothing about your message. It allows you to assume that the adversary cannot use the ciphertext to learn anything more about the message than they already know.
    $endgroup$
    – Ella Rose
    7 hours ago







  • 1




    $begingroup$
    @Lol4 Imagine it's your money that you've massively leveraged and you get this message. It was a "1" but it decoded to a "5" due to random tractor noise on the line, miss-keying by the telegraph operator or absolute flukey chance by an attacker trying to put you out of business. The important thing is that I've demonstrated that it's possible to receive an unauthentic message without recognising it. So OTP = malleable.
    $endgroup$
    – Paul Uszak
    7 hours ago















$begingroup$
how would you change "1" to "5" if you have ciphertext where you have absolutely no idea what the message it encrypts says?
$endgroup$
– Lol4
7 hours ago




$begingroup$
how would you change "1" to "5" if you have ciphertext where you have absolutely no idea what the message it encrypts says?
$endgroup$
– Lol4
7 hours ago












$begingroup$
to "shape" the message into something else, if you have absolutely no idea what the message is, you have to send all those "something else" to the receiving party, because they are the only one who can decode the ciphertext. They will notice that you spam them.
$endgroup$
– Lol4
7 hours ago




$begingroup$
to "shape" the message into something else, if you have absolutely no idea what the message is, you have to send all those "something else" to the receiving party, because they are the only one who can decode the ciphertext. They will notice that you spam them.
$endgroup$
– Lol4
7 hours ago












$begingroup$
how is that not message authentication? if the only way someone else can fabricate a message to me is by sending me a trillion messages, I will just know. like, spam emails. you know its spam when you get a million requests from rich people wanting to give you money if you give them your bank account login codes.
$endgroup$
– Lol4
7 hours ago





$begingroup$
how is that not message authentication? if the only way someone else can fabricate a message to me is by sending me a trillion messages, I will just know. like, spam emails. you know its spam when you get a million requests from rich people wanting to give you money if you give them your bank account login codes.
$endgroup$
– Lol4
7 hours ago













$begingroup$
@Lol4 The One-Time Pad model doesn't allow you to assume that the adversary knows nothing about your message. It allows you to assume that the adversary cannot use the ciphertext to learn anything more about the message than they already know.
$endgroup$
– Ella Rose
7 hours ago





$begingroup$
@Lol4 The One-Time Pad model doesn't allow you to assume that the adversary knows nothing about your message. It allows you to assume that the adversary cannot use the ciphertext to learn anything more about the message than they already know.
$endgroup$
– Ella Rose
7 hours ago





1




1




$begingroup$
@Lol4 Imagine it's your money that you've massively leveraged and you get this message. It was a "1" but it decoded to a "5" due to random tractor noise on the line, miss-keying by the telegraph operator or absolute flukey chance by an attacker trying to put you out of business. The important thing is that I've demonstrated that it's possible to receive an unauthentic message without recognising it. So OTP = malleable.
$endgroup$
– Paul Uszak
7 hours ago




$begingroup$
@Lol4 Imagine it's your money that you've massively leveraged and you get this message. It was a "1" but it decoded to a "5" due to random tractor noise on the line, miss-keying by the telegraph operator or absolute flukey chance by an attacker trying to put you out of business. The important thing is that I've demonstrated that it's possible to receive an unauthentic message without recognising it. So OTP = malleable.
$endgroup$
– Paul Uszak
7 hours ago













1
















$begingroup$


But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication?




The informal criterion of "not complete gibberish" that you are applying here has two problems:




  • Malleability: It is trivial to modify OTP-encrypted ciphertexts so that they will decrypt to something that's unlikely to be "complete gibberish";


  • Computers are dumb: It assumes that the decrypted message is read by a human being possessed of common sense instead of acted upon by a dumb computer;

Malleability



This is the property many ciphers have that an attacker that doesn't know the key can nevertheless modify a ciphertext in such a way as to cause a predictable change in the plaintext it will decrypt to. One-time pads and stream ciphers (the computationally secure variant thereof) are subject to one particularly trivial form of this:



  • If you flip any bit of a ciphertext, that causes the corresponding bit of the plaintext to flip.

This means that if I flip a bit in a ciphertext, the resulting fake plaintext will be minimally different from the real one. I hope you agree this means it's unlikely to be "gibberish."



In comments you've expressed skepticism that an attacker could exploit that to fool a recipient, because they'd have to know or guess a fair amount about the plaintext that corresponds to a the ciphertext. But that's a condition that is often met in real life—for example we routinely encrypt network protocols and file formats that are publicly specified and such that an attacker can effectively guess the protocolar "skeleton" of encrypted messages. And we don't want them to be able to exploit this to modify that skeleton.



Computers are dumb



The other problem is that the scenario you're implicitly contemplating—a human being, possessed of common sense, reading a single decrypted message—is not the norm by any means. Most decrypted messages are acted upon by computers, slavishly literal and poorly programmed machines that will happily repeat the same humanly-absurd mistake billions of time per second with unintended consequences that nobody predicted. We can't rely on some common-sense human notion of "gibberish" to reject forgeries—we need a fool-proof mechanical way of rejecting forgeries, one that not even a computer can goof up.



Example: EFail attack



One recent real-life example that combines these two motifs is the EFail attack on encrypted email. It exploits:




  • Malleability: The attacker is able to modify an HTML emails' ciphertext to craft a forgery that decrypts to an HTML image tag with the original plaintext inside its URL;


  • Computers are dumb: Many email clients will obliviously decrypt that forged message and automatically make the HTTP request for the forged image tag before showing the plaintext to the user.

EFail is an attack against CBC-mode encryption, not stream ciphers or one-time pads, but cryptographers' general attitude to malleability is that it should not be allowed in practical systems, period.






share|improve this answer










$endgroup$














  • $begingroup$
    it isn't trivial to modify OTP-encrypted ciphertexts. a thousand bit message, a thousand possible bits you can alter, you have no knowledge of the message, and the recipient notices if you spam them with a thousand bits. if you want to get lucky and switch a "1" to a "5" without knowing what the message even says, that is not "trivial".
    $endgroup$
    – Lol4
    6 hours ago










  • $begingroup$
    I was mostly considering attacks where ciphertext is not known, as well (but the recipient is known. ) In that case, to try and guess what to send them is impossible. To intercept the message is more work.
    $endgroup$
    – Lol4
    6 hours ago















1
















$begingroup$


But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication?




The informal criterion of "not complete gibberish" that you are applying here has two problems:




  • Malleability: It is trivial to modify OTP-encrypted ciphertexts so that they will decrypt to something that's unlikely to be "complete gibberish";


  • Computers are dumb: It assumes that the decrypted message is read by a human being possessed of common sense instead of acted upon by a dumb computer;

Malleability



This is the property many ciphers have that an attacker that doesn't know the key can nevertheless modify a ciphertext in such a way as to cause a predictable change in the plaintext it will decrypt to. One-time pads and stream ciphers (the computationally secure variant thereof) are subject to one particularly trivial form of this:



  • If you flip any bit of a ciphertext, that causes the corresponding bit of the plaintext to flip.

This means that if I flip a bit in a ciphertext, the resulting fake plaintext will be minimally different from the real one. I hope you agree this means it's unlikely to be "gibberish."



In comments you've expressed skepticism that an attacker could exploit that to fool a recipient, because they'd have to know or guess a fair amount about the plaintext that corresponds to a the ciphertext. But that's a condition that is often met in real life—for example we routinely encrypt network protocols and file formats that are publicly specified and such that an attacker can effectively guess the protocolar "skeleton" of encrypted messages. And we don't want them to be able to exploit this to modify that skeleton.



Computers are dumb



The other problem is that the scenario you're implicitly contemplating—a human being, possessed of common sense, reading a single decrypted message—is not the norm by any means. Most decrypted messages are acted upon by computers, slavishly literal and poorly programmed machines that will happily repeat the same humanly-absurd mistake billions of time per second with unintended consequences that nobody predicted. We can't rely on some common-sense human notion of "gibberish" to reject forgeries—we need a fool-proof mechanical way of rejecting forgeries, one that not even a computer can goof up.



Example: EFail attack



One recent real-life example that combines these two motifs is the EFail attack on encrypted email. It exploits:




  • Malleability: The attacker is able to modify an HTML emails' ciphertext to craft a forgery that decrypts to an HTML image tag with the original plaintext inside its URL;


  • Computers are dumb: Many email clients will obliviously decrypt that forged message and automatically make the HTTP request for the forged image tag before showing the plaintext to the user.

EFail is an attack against CBC-mode encryption, not stream ciphers or one-time pads, but cryptographers' general attitude to malleability is that it should not be allowed in practical systems, period.






share|improve this answer










$endgroup$














  • $begingroup$
    it isn't trivial to modify OTP-encrypted ciphertexts. a thousand bit message, a thousand possible bits you can alter, you have no knowledge of the message, and the recipient notices if you spam them with a thousand bits. if you want to get lucky and switch a "1" to a "5" without knowing what the message even says, that is not "trivial".
    $endgroup$
    – Lol4
    6 hours ago










  • $begingroup$
    I was mostly considering attacks where ciphertext is not known, as well (but the recipient is known. ) In that case, to try and guess what to send them is impossible. To intercept the message is more work.
    $endgroup$
    – Lol4
    6 hours ago













1














1










1







$begingroup$


But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication?




The informal criterion of "not complete gibberish" that you are applying here has two problems:




  • Malleability: It is trivial to modify OTP-encrypted ciphertexts so that they will decrypt to something that's unlikely to be "complete gibberish";


  • Computers are dumb: It assumes that the decrypted message is read by a human being possessed of common sense instead of acted upon by a dumb computer;

Malleability



This is the property many ciphers have that an attacker that doesn't know the key can nevertheless modify a ciphertext in such a way as to cause a predictable change in the plaintext it will decrypt to. One-time pads and stream ciphers (the computationally secure variant thereof) are subject to one particularly trivial form of this:



  • If you flip any bit of a ciphertext, that causes the corresponding bit of the plaintext to flip.

This means that if I flip a bit in a ciphertext, the resulting fake plaintext will be minimally different from the real one. I hope you agree this means it's unlikely to be "gibberish."



In comments you've expressed skepticism that an attacker could exploit that to fool a recipient, because they'd have to know or guess a fair amount about the plaintext that corresponds to a the ciphertext. But that's a condition that is often met in real life—for example we routinely encrypt network protocols and file formats that are publicly specified and such that an attacker can effectively guess the protocolar "skeleton" of encrypted messages. And we don't want them to be able to exploit this to modify that skeleton.



Computers are dumb



The other problem is that the scenario you're implicitly contemplating—a human being, possessed of common sense, reading a single decrypted message—is not the norm by any means. Most decrypted messages are acted upon by computers, slavishly literal and poorly programmed machines that will happily repeat the same humanly-absurd mistake billions of time per second with unintended consequences that nobody predicted. We can't rely on some common-sense human notion of "gibberish" to reject forgeries—we need a fool-proof mechanical way of rejecting forgeries, one that not even a computer can goof up.



Example: EFail attack



One recent real-life example that combines these two motifs is the EFail attack on encrypted email. It exploits:




  • Malleability: The attacker is able to modify an HTML emails' ciphertext to craft a forgery that decrypts to an HTML image tag with the original plaintext inside its URL;


  • Computers are dumb: Many email clients will obliviously decrypt that forged message and automatically make the HTTP request for the forged image tag before showing the plaintext to the user.

EFail is an attack against CBC-mode encryption, not stream ciphers or one-time pads, but cryptographers' general attitude to malleability is that it should not be allowed in practical systems, period.






share|improve this answer










$endgroup$




But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication?




The informal criterion of "not complete gibberish" that you are applying here has two problems:




  • Malleability: It is trivial to modify OTP-encrypted ciphertexts so that they will decrypt to something that's unlikely to be "complete gibberish";


  • Computers are dumb: It assumes that the decrypted message is read by a human being possessed of common sense instead of acted upon by a dumb computer;

Malleability



This is the property many ciphers have that an attacker that doesn't know the key can nevertheless modify a ciphertext in such a way as to cause a predictable change in the plaintext it will decrypt to. One-time pads and stream ciphers (the computationally secure variant thereof) are subject to one particularly trivial form of this:



  • If you flip any bit of a ciphertext, that causes the corresponding bit of the plaintext to flip.

This means that if I flip a bit in a ciphertext, the resulting fake plaintext will be minimally different from the real one. I hope you agree this means it's unlikely to be "gibberish."



In comments you've expressed skepticism that an attacker could exploit that to fool a recipient, because they'd have to know or guess a fair amount about the plaintext that corresponds to a the ciphertext. But that's a condition that is often met in real life—for example we routinely encrypt network protocols and file formats that are publicly specified and such that an attacker can effectively guess the protocolar "skeleton" of encrypted messages. And we don't want them to be able to exploit this to modify that skeleton.



Computers are dumb



The other problem is that the scenario you're implicitly contemplating—a human being, possessed of common sense, reading a single decrypted message—is not the norm by any means. Most decrypted messages are acted upon by computers, slavishly literal and poorly programmed machines that will happily repeat the same humanly-absurd mistake billions of time per second with unintended consequences that nobody predicted. We can't rely on some common-sense human notion of "gibberish" to reject forgeries—we need a fool-proof mechanical way of rejecting forgeries, one that not even a computer can goof up.



Example: EFail attack



One recent real-life example that combines these two motifs is the EFail attack on encrypted email. It exploits:




  • Malleability: The attacker is able to modify an HTML emails' ciphertext to craft a forgery that decrypts to an HTML image tag with the original plaintext inside its URL;


  • Computers are dumb: Many email clients will obliviously decrypt that forged message and automatically make the HTTP request for the forged image tag before showing the plaintext to the user.

EFail is an attack against CBC-mode encryption, not stream ciphers or one-time pads, but cryptographers' general attitude to malleability is that it should not be allowed in practical systems, period.







share|improve this answer













share|improve this answer




share|improve this answer



share|improve this answer










answered 6 hours ago









Luis CasillasLuis Casillas

10.3k1 gold badge16 silver badges38 bronze badges




10.3k1 gold badge16 silver badges38 bronze badges














  • $begingroup$
    it isn't trivial to modify OTP-encrypted ciphertexts. a thousand bit message, a thousand possible bits you can alter, you have no knowledge of the message, and the recipient notices if you spam them with a thousand bits. if you want to get lucky and switch a "1" to a "5" without knowing what the message even says, that is not "trivial".
    $endgroup$
    – Lol4
    6 hours ago










  • $begingroup$
    I was mostly considering attacks where ciphertext is not known, as well (but the recipient is known. ) In that case, to try and guess what to send them is impossible. To intercept the message is more work.
    $endgroup$
    – Lol4
    6 hours ago
















  • $begingroup$
    it isn't trivial to modify OTP-encrypted ciphertexts. a thousand bit message, a thousand possible bits you can alter, you have no knowledge of the message, and the recipient notices if you spam them with a thousand bits. if you want to get lucky and switch a "1" to a "5" without knowing what the message even says, that is not "trivial".
    $endgroup$
    – Lol4
    6 hours ago










  • $begingroup$
    I was mostly considering attacks where ciphertext is not known, as well (but the recipient is known. ) In that case, to try and guess what to send them is impossible. To intercept the message is more work.
    $endgroup$
    – Lol4
    6 hours ago















$begingroup$
it isn't trivial to modify OTP-encrypted ciphertexts. a thousand bit message, a thousand possible bits you can alter, you have no knowledge of the message, and the recipient notices if you spam them with a thousand bits. if you want to get lucky and switch a "1" to a "5" without knowing what the message even says, that is not "trivial".
$endgroup$
– Lol4
6 hours ago




$begingroup$
it isn't trivial to modify OTP-encrypted ciphertexts. a thousand bit message, a thousand possible bits you can alter, you have no knowledge of the message, and the recipient notices if you spam them with a thousand bits. if you want to get lucky and switch a "1" to a "5" without knowing what the message even says, that is not "trivial".
$endgroup$
– Lol4
6 hours ago












$begingroup$
I was mostly considering attacks where ciphertext is not known, as well (but the recipient is known. ) In that case, to try and guess what to send them is impossible. To intercept the message is more work.
$endgroup$
– Lol4
6 hours ago




$begingroup$
I was mostly considering attacks where ciphertext is not known, as well (but the recipient is known. ) In that case, to try and guess what to send them is impossible. To intercept the message is more work.
$endgroup$
– Lol4
6 hours ago











Lol4 is a new contributor. Be nice, and check out our Code of Conduct.









draft saved

draft discarded

















Lol4 is a new contributor. Be nice, and check out our Code of Conduct.












Lol4 is a new contributor. Be nice, and check out our Code of Conduct.











Lol4 is a new contributor. Be nice, and check out our Code of Conduct.














Thanks for contributing an answer to Cryptography Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid


  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f74880%2fwhy-do-one-time-pads-not-provide-message-authentication%23new-answer', 'question_page');

);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown









Popular posts from this blog

Invision Community Contents History See also References External links Navigation menuProprietaryinvisioncommunity.comIPS Community ForumsIPS Community Forumsthis blog entry"License Changes, IP.Board 3.4, and the Future""Interview -- Matt Mecham of Ibforums""CEO Invision Power Board, Matt Mecham Is a Liar, Thief!"IPB License Explanation 1.3, 1.3.1, 2.0, and 2.1ArchivedSecurity Fixes, Updates And Enhancements For IPB 1.3.1Archived"New Demo Accounts - Invision Power Services"the original"New Default Skin"the original"Invision Power Board 3.0.0 and Applications Released"the original"Archived copy"the original"Perpetual licenses being done away with""Release Notes - Invision Power Services""Introducing: IPS Community Suite 4!"Invision Community Release Notes

Canceling a color specificationRandomly assigning color to Graphics3D objects?Default color for Filling in Mathematica 9Coloring specific elements of sets with a prime modified order in an array plotHow to pick a color differing significantly from the colors already in a given color list?Detection of the text colorColor numbers based on their valueCan color schemes for use with ColorData include opacity specification?My dynamic color schemes

Tom Holland Mục lục Đầu đời và giáo dục | Sự nghiệp | Cuộc sống cá nhân | Phim tham gia | Giải thưởng và đề cử | Chú thích | Liên kết ngoài | Trình đơn chuyển hướngProfile“Person Details for Thomas Stanley Holland, "England and Wales Birth Registration Index, 1837-2008" — FamilySearch.org”"Meet Tom Holland... the 16-year-old star of The Impossible""Schoolboy actor Tom Holland finds himself in Oscar contention for role in tsunami drama"“Naomi Watts on the Prince William and Harry's reaction to her film about the late Princess Diana”lưu trữ"Holland and Pflueger Are West End's Two New 'Billy Elliots'""I'm so envious of my son, the movie star! British writer Dominic Holland's spent 20 years trying to crack Hollywood - but he's been beaten to it by a very unlikely rival"“Richard and Margaret Povey of Jersey, Channel Islands, UK: Information about Thomas Stanley Holland”"Tom Holland to play Billy Elliot""New Billy Elliot leaving the garage"Billy Elliot the Musical - Tom Holland - Billy"A Tale of four Billys: Tom Holland""The Feel Good Factor""Thames Christian College schoolboys join Myleene Klass for The Feelgood Factor""Government launches £600,000 arts bursaries pilot""BILLY's Chapman, Holland, Gardner & Jackson-Keen Visit Prime Minister""Elton John 'blown away' by Billy Elliot fifth birthday" (video with John's interview and fragments of Holland's performance)"First News interviews Arrietty's Tom Holland"“33rd Critics' Circle Film Awards winners”“National Board of Review Current Awards”Bản gốc"Ron Howard Whaling Tale 'In The Heart Of The Sea' Casts Tom Holland"“'Spider-Man' Finds Tom Holland to Star as New Web-Slinger”lưu trữ“Captain America: Civil War (2016)”“Film Review: ‘Captain America: Civil War’”lưu trữ“‘Captain America: Civil War’ review: Choose your own avenger”lưu trữ“The Lost City of Z reviews”“Sony Pictures and Marvel Studios Find Their 'Spider-Man' Star and Director”“‘Mary Magdalene’, ‘Current War’ & ‘Wind River’ Get 2017 Release Dates From Weinstein”“Lionsgate Unleashing Daisy Ridley & Tom Holland Starrer ‘Chaos Walking’ In Cannes”“PTA's 'Master' Leads Chicago Film Critics Nominations, UPDATED: Houston and Indiana Critics Nominations”“Nominaciones Goya 2013 Telecinco Cinema – ENG”“Jameson Empire Film Awards: Martin Freeman wins best actor for performance in The Hobbit”“34th Annual Young Artist Awards”Bản gốc“Teen Choice Awards 2016—Captain America: Civil War Leads Second Wave of Nominations”“BAFTA Film Award Nominations: ‘La La Land’ Leads Race”“Saturn Awards Nominations 2017: 'Rogue One,' 'Walking Dead' Lead”Tom HollandTom HollandTom HollandTom Hollandmedia.gettyimages.comWorldCat Identities300279794no20130442900000 0004 0355 42791085670554170004732cb16706349t(data)XX5557367