Page 1 of 2 12 Last
  • Jump to page:
    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2006
    Posts
    11
    Rep Power
    0

    Is XOR encryption unbreakable?


    Hi, I' ve read some documents on XOR encryption in the past.

    The thing is, that some mention that XOR encryption takes seconds to break and that it's rather trivial to do it.
    I recently read somewhere that XOR encryption is *unbreakable*, if the length of the key is the equal to the length of the plaintext.

    Is this correct?
  2. #2
  3. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,782
    Rep Power
    4302
    Whoever wrote that is smoking crack. It is vulnerable to a known plaintext attack. Allow me to demonstrate.

    * Assume I manage to give you a plain text message to encrypt.
    * Now assume that I have the resulting encrypted text that you've generated.
    * Now I know that your encryption method is XOR
    * I also know that the operation is basically (plaintext XOR secretkey) ==> encrypted message.
    * By the very nature of the XOR operation, to decode it, we just XOR again with the key (encrypted XOR secretkey) ==> plaintext.

    Now, I have access to a known plaintext and its associated encrypted text. Guess what happens when I do (plaintext XOR encrypted text). That's right, the result is secretkey.

    Now that I have your secretkey, I can decode all the messages you've sent so far (as long as those messages are below the length of my plaintext). Worse, if your secretkey is a page from a book instead of totally random numbers, I may be able to obtain my own copy of the book and decode messages that are even longer than my known plaintext.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2006
    Posts
    11
    Rep Power
    0
    I think that XOR encryption in that case becomes the Vernam Cipher aka one-time-pad, which is said to be unbreakable and the only secure and perfect cipher so far.

    (URL address blocked: See forum rules)~burt/learning/Csc609.051/notes/02.html
  6. #4
  7. It's only wrong if you're caught....
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Dec 2003
    Location
    Sydney, Australia
    Posts
    1,285
    Rep Power
    179
    What the people who said that XOR was unbreakable was probably the following:

    If your key is the same length as the message, and the key is created in such a way that it cannot be somehow guessed if they know other parts of the key, and you *never* reuse the key, then the message is secure.

    Its the same thing as One time pad ciphers, they've even been mathematically proven to be unbreakable, but the conditions which must be met for this to be true are the same as above.

    But these days ciphers are designed to work in much tougher situations.

    These days the requirements of ciphers are thus:

    • A key should not need to be overly long (256 bits for symmetric, and about 2048 for assymetric, I *think*)
    • You should be able to use the key an infinite amount of times without any negative effect, as such:
    • There should be know way of discerning the key if you know the contents of an encrypted message


    As you can see XOR ciphers can be secure, but they are secure in very limited circumstances, so other ciphers should always be used.

    [EDIT]: The link above is http://www.cs.miami.edu/~burt/learni.../notes/02.html
  8. #5
  9. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,782
    Rep Power
    4302
    Yes, the biggest problem with using one-time pad keys is the problem of key distribution. This is why they are used very sparingly and only in circumstances where very high security is needed (The hotline between Washington and Moscow was thought to use one). When you're using a one-time pad though, it doesn't really matter too much what encryption method you are using.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2006
    Posts
    42
    Rep Power
    13
    XOR is merely a way to combine key and data. There are many other ways to combine these things, but XOR is not weaker. In fact, XOR hides the distribution of data to be encrypted, and is the most common way to combine key and data.

    XOR is prefered for many reasons - that it can be used to "undo" the encryption, but if a long "key" is used, then how do you know the key to decrypt the data? One of the results of a bad key applied to the data is total garbage - the only way to read the data is to provide the correct key. The TOTALLY CORRRECT KEY. Anything else just gives you garbage.

    Ron.
  12. #7
  13. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,782
    Rep Power
    4302
    Yes, that's why I said when you're using a one-time pad, it doesn't matter too much exactly which encryption scheme you are using, since the security comes from the one-time pad rather than your encryption algorithm. There are many other such self-reversing algorithms (symmetric algorithms). A vigenere square would work equally well and would have been the method of choice around 150 years ago.

    XOR would be an extremely bad choice if (a) the key were reused and (b) a decoded plaintext was obtained, because it is possible to reverse the key from a decoded plaintext and use it to decode the other messages.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2006
    Posts
    11
    Rep Power
    0
    The TOTALLY CORRRECT KEY. Anything else just gives you garbage.
    So based on this, knowing that it is text that makes sense, I can identify the original message because the rest would contain garbage.

    Then it shouldn't be impossible to break.
    A bruteforce program would have to XOR the encrypted message with all the possible keys.
    The complexity of that algorithm would be 26^key_length (assuming that the plaintext contains only lowercase characters.
    Is this correct?

    Then by reading that output, I would identify which makes sense.

    Can I use this method to break the one-time pad (XOR) encrypted message?
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2006
    Posts
    42
    Rep Power
    13
    NO! If the key is as long as the text (in one-time-pad environment), then you would have an infinite number of breakouts.

    The "brute-force" attack ONLY works when you have the encoding algorithm! Period! Then, and only then, can you enter possible keys that might have been used to encrypt the message. Here is a message - 3275a bcd74 - - it is obviously 5 hex caracters, but what does it mean? Are there any pad characters? Perhaps the message is "now" with 2 pad characters - how do you determine that? 5 random characters will "decode" into EVERY word from 1-5 characters long! Which is the correct one? Now imagine a message of 10,000 characters long... You MUST have the encryption algoritym or your breakouts are meaningless...

    Nothing is impossible to break. But without the encryption algorithm you are fighting a losing battle - again, brute-force MEANS applying keys to a known algorithm in order to determine the key that was used for encryption.

    One-time-pads are combersome (as was pointed out) because you have to manage a key as long as the message, AND communicate that key to the person you want to read your message.

    Much more practical (and used today) is a shorter key that produces "random" values for as long as your message. Yoy see things like 128-bit encryption which means a person can use a key 128 bits long as a seed/salt into a Pseudo Random Number Generator (PRNG) to produce an encryption key to apply against the data to encrypt.

    XOR is often the way of applying that key, and it doesn't mean that it is any less secure... Security lies within the encryption algorithm, and NOT the method of applying they key to the data. Encryotion is as secure as the key-stream used ti encrypt the data, not in the way the key is applied to the data.... (sorry - I got long-winded).....

    Ron.
  18. #10
  19. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,782
    Rep Power
    4302
    Simple XOR is actually embarrassingly simple to break. Suggested reading: Applied Cryptography by Bruce Schneier.

    Selected quotes from chapter 1.2.3 (I have the first edition):
    It's an embarrassment to put this algorithm in a book like this because it's nothing more than a Vigenere cipher. It is included because it is so prevalent in commercial software packages, at least those in the MS-DOS and Macintosh worlds[1]. Unfortunately, if a software security program proclaims that it has a "proprietary encryption algorithm" -- one that is significantly faster than DES -- the odds are that it is some variant of this:
    ... snip basic XOR code and some comments about it ....

    There is no real security here. This kind of encryption is trivial to break, even without computers [2, 3]. It will only take a few minutes with a computer.

    Assume the plaintext is English. Furthermore, assume the key length is an arbitrary small number of bytes. Here's how to break it:

    1. Discover the length of the key by a procedure known as counting coincidences[4]. Trying each byte displacement of the ciphertext against iself, count those bytes that are equal. If the two ciphertext portions have used the same key, something over 6% of the bytes will be equal. If they have used a different key, then less than 0.4% will be equal (assuming a random key encrypting normal ASCII text; other plaintext will have different numbers). The smallest displacement that indicates an equal key is the length of the repeated key.

    2. Shift the ciphertext by that length and XOR with itself. This removes the key and leaves you with the plaintext XORed with itself, shifted by the key length. Since English has about one bit of real information per byte, there is plenty of redundancy for choosing a unique decryption.

    Despite this, the list of software vendors that tout this sort of algorithm as being "almost as secure as DES" is staggering [5]. It might keep your kid sister from reading your files, but it won't stop a cryptographer for more than a few minutes.
    References:
    1. A. Stevens, "Hacks, Spooks and Data Encryption", [i]Dr. Dobbs Journal[i], vol. 15, no. 9, Sep 1990, pp127-134, 147-149
    2. H.F. Gaines, Cryptanalysis, American Photographics Press, 1937 (Reprinted by Dover Publications, 1956)
    3. A. Sinkov, Elementary Cryptanalysis, Mathematical Association of America, 1966
    4. W.F. Friedman, The Index of Coincidence and Its Applications in Cryptography, Riverbank Publication No. 22, Riverbank Labs, 1920
    5. B. Schneier, "One way Hash Functions", Dr. Dobbs Journal, Vol. 10, No. 2, Feb 1993, pp 145-151.

    He goes on to talk about one-time pads in the next section.
    A random key sequence XORed with a nonrandom plaintext messages produces a completely random ciphertext message, an d no amount of computing power can change that.

    The caveat, and this is a big one, is that the key letters have to be generated randomly. Any attacks against this scheme wil be against the method used to generate the key sequence. If you use a cryptographically weak algorithm to generate your key sequence, there might be trouble. If you use a real random source -- this is much harder than it might first appear -- it is safe.

    Using a pseudo-random number generator doesn't count; often they have nonrandom properties. Many of the stream ciphers described later in this book try to approximate this system with a pseudo-random sequence, but most fail. The sequences they generate only seem random, but careful analysis yields nonrandomness, which a cryptanalyst can exploit.
    Hope you guys find this useful. You should definitely purchase the book -- it is one of the best resources about cryptography out there.

    Comments on this post

    • codergeek42 agrees : Very interesting!
    • B-Con agrees : Excellent suggested reading.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  20. #11
  21. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2006
    Posts
    11
    Rep Power
    0
    Thanks everyone!
  22. #12
  23. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2006
    Posts
    42
    Rep Power
    13
    In the modern world this analysis is totally worthless. It assumes that the key is directly applied against the text. It has been decades since that has been done - the "key" is used to prime a PRNG that generates the key that is used to encrypt the text. This analysis is totally bogus!

    This is my "key" - This is a test
    And this is the encrypted result - 1553b 06be0 ce6bd 82364 4e1d0 4c3fa 570e8 f6c2e 45332 2fef3 58218 677cd

    Please tell me the message, if it is so trivial. You cannot, because the "key" primed a PRNG that produced output that was XORed with the message. This example totally illustrates the lack of accuracy in your analysis. You pretend that the "key" is used directly, but this is never done. Your book illustrates a super-simplistic example that is not realistic. If it IS real, then break my nessage... You cannot!

    Ron.
  24. #13
  25. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,782
    Rep Power
    4302
    It is vulnerable to a known plaintext attack. Doesn't matter what your PRNG is doing because access to the plaintext will make it trivial to regenerate the number sequence and then the numbers can be used to then decrypt other messages that were encrypted with the same starting seed. A good cipher system should make it hard to compute the key from a known plaintext.

    By the way, the book I mentioned is a rather famous one written by a well known authority on the subject. You'd be well advised to contact the author yourself and discuss your crypto system with him.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  26. #14
  27. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2006
    Location
    Victoria, Australia
    Posts
    458
    Rep Power
    88
    Hey rascalcode, take a look at the original post in this thread.
    Does it look like belhifet is asking about simple XOR encryption, or using XOR encryption as just a part of complex algorithms in use these days? I would have to be completely persuaded to the former. So why are you arguing on the basis that he is talking about the latter, when everyone else is just talking about simple XOR encryption??????

    Also, if talking about the simplest form of XOR encryption, combining key with message, if the key is the same length as the message, and you get like 3 characters wrong with the key, won't only 3 characters in the resulting 'de-ciphered' text be wrong? or using a key half length say, only 6 characters? or if you were using a different length key, in the length of the de-ciphered message up to the length of the key, there would only be 3 characters wrong?
  28. #15
  29. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2007
    Posts
    2
    Rep Power
    0
    No encryption method is "unbreakable".
    If the hacker knows the encryption method and/or knows the type of information that is encrypted, (ex: movie file, picture files, audio files etc...) it definetly makes the data easier to decrypt.

    Since we know that no encryption type is completely unbreakable, the purpose of data encryption is to make it so difficult for the hacker to decrypt the data that by the time he/she decrypts it, the data would be outdated and/or unusable.

    There are types of data encryption that are extremely hard to break, even for a masterful computer.

    XOR encryption can be decrypted easily if a small password is used to encrypt a large file. To get the most out of XOR encryption, the best thing to do would be use a key that is the same size as the input file. The down side to XOR encryption is that the original file-size never increases.

    I recommend 256AES Encryption, mixed with blowfish and XOR encryption. (Not necessarily in that order), Each one has it's strength. -Have a good one. I recommend Googling for
    XOR Encrypter
Page 1 of 2 12 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo