0
$\begingroup$

Considering a message of n bits, one ridiculously short key of 1 bit and using this cryptographic function which performs the XOR operation to each bit of the message, resulting in a single ciphertext, could we assume that if the attacker doesn't know anything but this ciphertext, that this system is anywhere close to being safe?

$\endgroup$
  • $\begingroup$ You say "symmetric algorithm", but can we presume that this is about a repeated one-time-pad? Knowing this term will give you a lot of information already. $\endgroup$ – Maarten Bodewes Jan 18 '18 at 11:40
4
$\begingroup$

If we don't know anything about the original n bit message, we can guess the message with probability $1/2^n$ which for anything but very small values of n quickly becomes zero. However if we xor the message with a single bit (repeating it n times) we only have 2 possible keys: 1 and 0. And the xor result is either the original message or it's negation. Therefor given a cipher text we have exactly two possibilities for plain text. And even if we know nothing about the plain text and can't validate our guess we can still guess with 50% chance of success.

Guessing the plain-text with 50% likelyhood is not secure by any means.

Obviously even with a very limited understanding of plain text, we would be able to determine which of the 2 options is correct.

Note security proofs for One-Time-Pad do not apply as we are repeating the key in the same message. This is no better than repeating it in later messages.

$\endgroup$
3
$\begingroup$

It seems you are describing an OTP with a repeated key, which is known to be insecure.

To test if a key is correct it is required to test the result of decryption. In this case the message is either itself - for key 0 or - it's complement, for a key with value 1. That means that if you can distinguish between the message itself and it's complement that you can "brute-force" the key. For this you can for instance find a pattern in the message. With this toy problem that pattern can be just a single bit of the message for which the value is known.

Even without testing, the fact that the message is either the ciphertext itself or its complement means that information about the message is leaked; the bits are constrained to a particular value and depend on any other bit of the ciphertext. If information about the message is leaked then the scheme is broken. You should not be able to find that any of the possible $2ˆn$ messages is more or less likely than the other ($P={1\over{2ˆn}}$) and you know have two messages that are likely with a probability $1\over2$ and all the others have probability zero.

TL;DR as you might expect, this is nowhere close to being secure.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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