Hi, I have heard somewhere that using XOR is not reversible (they spoke about encryption) but I do not understand how it was meant? AFAIK even with OR operation you cannot find out which of the two bits was 1. Please, could anyone who knows how it was meant explain it to me? Thank you
+5
A:
I think you have probably misquoted them slightly.
They probably meant that using a one-time pad is unbreakable because unless you have a copy of the one time pad there is absolutely no information in the ciphertext that you can use to recover the plaintext. You cannot use statistical analysis or even a brute-force search because all inputs could give the output with equal probability and there's no way to know which input is the right one.
One-time pads are typically implemented using XOR, but the irreversibility is because it is a one time pad, not because of the XOR operation.
Mark Byers
2010-02-24 14:19:40
To add to your answer: Unberakable, in case your one-time key is as long as your data (that means 1GB key for 1GB of plaintext) and it is NEVER reused (hence "one-time").
Piskvor
2010-02-24 14:21:54
@Piskvor: and (extremely important) really is *entirely* unpredictable.
Jerry Coffin
2010-02-24 14:25:42
@Piskvor: Correct. Another source of weakness is the random number generator. If you use a weak pseudo-random number generator, or seed from the time, it might also be possible to break the encryption. A true random source (e.g. radioactive decay) would be unbreakable though - there is no way to predict the next bit from the preceding bits.
Mark Byers
2010-02-24 14:26:47
Well, it resembles the Vermanns cipher to me :)
Snake
2010-02-24 14:27:22
"It is derived from the Vernam cipher, named after Gilbert Vernam, one of its inventors."
Mark Byers
2010-02-24 14:29:25
+3
A:
You probably mean "XOR encryption is unbreakable without the key"
If the key is random and is as long as the message (so it never repeats), the XOR cipher is more secure. With a keystream is generated by a pseudo-random number generator, the result is a stream cipher. With a key that is truly random, the result is a one-time pad, which is unbreakable even in theory.
Otto Allmendinger
2010-02-24 14:21:26
+1
A:
They probably meant XOR is reversible, unlike either AND or OR. For encryption, this is interesting primarily with respect to Vernam ciphers -- ones where your cipher produces a key stream, which you XOR with the data stream. On the receiving end, you can XOR the encrypted stream with the same key stream, and get the plaintext back.
It's also interesting from a viewpoint of cryptanalysis. For example, if two streams were enciphered with the same key stream, XORing them with each other gives you the XOR of the two plaintext streams, with all effects of the key stream removed. At this point, you can use a "sliding window" technique: XOR something you think is likely to be in one message at various points with that stream, and if it's there, the result will be the intelligible text of the other message.
Jerry Coffin
2010-02-24 14:24:33