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;
$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.
symmetric authentication authenticated-encryption one-time-pad
New contributor
$endgroup$
add a comment
|
$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.
symmetric authentication authenticated-encryption one-time-pad
New contributor
$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
add a comment
|
$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.
symmetric authentication authenticated-encryption one-time-pad
New contributor
$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
symmetric authentication authenticated-encryption one-time-pad
New contributor
New contributor
edited 5 hours ago
Lol4
New contributor
asked 8 hours ago
Lol4Lol4
62 bronze badges
62 bronze badges
New contributor
New contributor
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
add a comment
|
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
add a comment
|
2 Answers
2
active
oldest
votes
$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.
$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
|
show 4 more comments
$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.
$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
add a comment
|
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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.
$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
|
show 4 more comments
$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.
$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
|
show 4 more comments
$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.
$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.
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
|
show 4 more comments
$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
|
show 4 more comments
$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.
$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
add a comment
|
$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.
$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
add a comment
|
$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.
$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.
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
add a comment
|
$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
add a comment
|
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.
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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