3
$\begingroup$

I was reading about how a one time pad output can be changed by a third party without the receiving person realising. Surely the output at the other end would be garbage? Also, could you not generate a crc for the output, encrypt it with the same random sequence so at the other end it could be decrypted and checked to make sure nothing has changed?

$\endgroup$
  • $\begingroup$ You are probably interested in this CTF writeup, which contains answers to both of your questions. $\endgroup$ – yyyyyyy Dec 12 '17 at 19:06
  • $\begingroup$ You'd typically combine an OTP with a carter-wegman style MAC. $\endgroup$ – CodesInChaos Dec 12 '17 at 23:20
1
$\begingroup$

I was reading about how a one time pad output can be changed by a third party without the receiving person realising. Surely the output at the other end would be garbage?

There's no guarantee either way that it will or it won't. And in fact, OTPs have one very unfortunate (but by no means fatal) property: an active adversary that flips one bit of the ciphertext will cause plaintext bit at the same position to flip (relative to the true plaintext) when the adulterated ciphertext is decrypted. The recipient must therefore be able to tell that the decrypted message is wrong from a single bit flip.

One key concept you're missing here is that in cryptography we generally assume that the adversary may have partial knowledge of the plaintext. Even though we often informally say that the goal of a cipher is to prevent the adversary from learning anything about the plaintexts, what that actually means is preventing them from learning anything more than what they already knew beforehand.

In real life, adversaries may know a lot about the plaintexts that the honest parties encrypt. Like, for example, they might know that the plaintext is an HTTP request to a certain path within the server, and the values of some but not all request parameters. And that sort of knowledge might be enough for the adversary to modify the ciphertext to produce a plaintext that the recipient cannot tell is a forgery.

And even if the adversary doesn't have certain knowledge of any part of the plaintext, they might have a bunch of reasonable guesses. So they might just repeatedly try and modify the ciphertexts according to those guesses and see if they get lucky. Even if most of the guesses result in garbage at the other end, this is much more dangerous than you're giving it credit for, because nowadays the other end is almost always a computer, not a human being. Programmers are routinely careless, and computers are really good at blindly following instructions even when the program's preconditions have not been met. They're also really fast, so the attacker could possibly get to try a ton of guesses before any human being spots it, and even if they don't succeed at their goal they could cause a ton of collateral damage by getting the computer to act funny and damage all sorts of data and business processes.

Also, could you not generate a crc for the output, encrypt it with the same random sequence so at the other end it could be decrypted and checked to make sure nothing has changed?

Nope, that's easy to defeat. If you flip one bit of the original message, it's easy to compute the bits that you must flip on its CRC to produce the CRC of the adulterated one. And this means you can just flip the corresponding encrypted CRC bits in the ciphertext as well.

$\endgroup$
  • $\begingroup$ Ah. What if I was to encrypt the CRC with a second random stream of numbers or am I missing the point? $\endgroup$ – Bipman Dec 13 '17 at 7:20
  • 1
    $\begingroup$ Encrypting the CRC with a second random stream is useless, since you can still flip whatever bits of the encrypted CRC, just like you could flip whatever bits of the original encrypted message. Anyway, CRC is a keyless, linear function so would be very weak against an adversary which is, well, adversarial. $\endgroup$ – AYun Dec 13 '17 at 10:14
  • $\begingroup$ Alternative formulation: encrypting the CRC with a second random stream is no different from encrypting the message and CRC with just one random stream, because you get the exact same probability distribution in either case. $n$ coin flips followed by $m$ coin flips is the same as $n + m$ coin flips. $\endgroup$ – Luis Casillas Dec 13 '17 at 22:30
  • $\begingroup$ Can anyone recommend a good book on the subject including the maths side? $\endgroup$ – Bipman Dec 14 '17 at 22:52
  • $\begingroup$ What if you salted the encrypted text with random numbers in random places or sorted the text into a random order? Would this not make it much more difficult to unscramble even if part of the text was known? $\endgroup$ – Bipman Dec 21 '17 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.