Thread: Decrypting OTP ciphertext

  1. #1
    Caution: Wet Floor
    Join Date
    May 2006
    Posts
    55

    Decrypting OTP ciphertext

    (See Stroustrup, The C++ Programming Language (3rd ed.), p. 164).

    How would you help decrypt messages encrypted using the OTP algorithm?

    I'm able to encrypt messages alright using XOR:

    Code:
    while there are characters in message: 
         message XOR key = ciphertext;
    The key ("pad") has the same number of characters as the message, and is generated using a truly random RNG; true randomness is required for perfect security.

    Suppose you're presented with an OTP-encoded message. How would you generate a list of plausable messages and keys?

    My first idea was to generate message-key pairs by exhaustion and apply grammar rules for indo-european languages to each generated message, but that would have to be done ~10^21 times for a 20-character-long message.

    Is there a quicker way to do this? I don't know where to start : (

    Thanks.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I think that's the hole point with OTP generated encryption. It is literally unbreakable other than by brute force, and that takes a very long time...

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by matsp View Post
    I think that's the hole point with OTP generated encryption. It is literally unbreakable other than by brute force, and that takes a very long time...
    It's not breakable period, by brute force or any other method.

  4. #4
    Caution: Wet Floor
    Join Date
    May 2006
    Posts
    55
    What about just generating messages that are grammatically correct? A combination like

    "97xj34m725"

    probably wouldn't occur in a plaintext message....

    Also:

    If the key is shorter than the message, the encryption is not secure. Why is that?

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    In practical terms, for messages with any reasonable content, yes, I agree - the only possible way to break One Time Pad encryption is by having a copy of the One Time Pad used for the message.

    Of course you CAN break it by brute force - ANY encryption can be broken by that method. Just try every permutation in every position, and you will sooner or later find the right combination [1]. Of course, there are 26 combinations for each position, so the number of possible permuations is 26 to the power of message length, which quickly gets to a HUGE number [that assumes that you only use A-Z keys too, which may not be the case - in which case it takes off at even more rapid rate].

    It is obviously also necessary to have some mechanism to recognise "words" in some way.


    [1] Of course, you can probably use some heuristics for "cutting the attempt short" when a partiucular letter doesn't make any meaning in that position. Although there is of course no guarantee that the message doesn't starts or ends with "%%A!"H##11211NNNAZZmmAAAE" just to confuse people, and that there are some extra random letters thrown in for good measure here and there. .


    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by slippy View Post
    What about just generating messages that are grammatically correct? A combination like

    "97xj34m725"

    probably wouldn't occur in a plaintext message....

    Also:

    If the key is shorter than the message, the encryption is not secure. Why is that?
    If the key is (noticably) shorter than the message, it is more likely that the breaker can "guess" the key based on the frequency of certain letters in "average text" (in English, S and E are amongst the most common).

    As I stated in the other message, there is nothing saying that there isn't nonsense "filler" stuff in the message, but you can of course expect SOME of the message to have valid content. It helps if you know which language it is supposed to be, as for example KK doesn't occur very often in English words [if at all], but isn't that unlikely in Finish.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    > Of course you CAN break it by brute force - ANY encryption can be broken by that method.

    With a random OTP, all possible output messages are equally likely, so in particular all possible output messages that satisfy any criterion you want are equally likely. Sure, with brute force you will eventually generate the right message, but you won't have any way of recognizing it. The only way to break OTP is if the pad isn't truly random, as can happen if one is lazy and decides to reuse a pad.

    Edit: Actually, that's not right - plausible-looking output messages are more likely, of course, but since there is a one-to-one correspondence between output messages and keys, if the key is truly random and unknown then the encrypted message can't provide any information that one didn't have to begin with (except for the message's length, and even that's just an upper bound, since the message could have been padded with random garbage). In other words, instead of trying random keys and looking for plausible-looking output messages, one may as well just generate every possible output message of the given length and sort through those instead.
    Last edited by robatino; 12-24-2007 at 08:02 PM.

  8. #8
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    >Just try every permutation in every position, and you will sooner or later find the right combination

    But the problem is distinguishing the correct plaintext from the wrong ones, isn't it? Assuming the key is perfectly random, the only way you could find the correct plaintext is if there is only one possible plaintext of the same length of the ciphertext.

    On the other hand, if there is any kind of pattern in the key, it might be possible to recognize when that pattern is apparent in a guessed key and also produces a reasonable decryption.
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by slippy View Post
    What about just generating messages that are grammatically correct? A combination like

    "97xj34m725"

    probably wouldn't occur in a plaintext message....
    Usually, as an extra precaution, an key based encryption is use in conjunction with a simple cypher, so that even if the codebreaker finds the key, he won't immediately be able to recognize that the key was correct.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  10. #10
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by matsp View Post
    Of course you CAN break it by brute force - ANY encryption can be broken by that method.
    Untrue. There are a huge number of plausible messages the ciphertext could decrypt to, each with a different key. It is impossible in principle to determine which is which.

    Seriously, Claude Shannon didn't get this wrong.

    Here's a 16 character ciphertext:

    67c6697351ff4aec29cdbaabf2fbe346

    This was encrypted by XOR'ing the plaintext with a 16 bit one time pad.

    Tell me what this decrypts to, using pad 13ae0000719639cc48edc9ce91898632.

    What about pad 10ae001039df25824cedd3d8d2929779? Pad 0fa91e53329e24cc50a2cf8b869e8f2a? Pad 10ae001039df279f4eedd38b9f9e8228?

    Which of those messages is correct? Do you see the problem now?
    Last edited by brewbuck; 12-24-2007 at 08:07 PM.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Well, matsp is correct in the sense that you can break it by brute force, just that you would not know when you have broken it
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Or in other words, randomly generating text is just as effective a technique for "breaking" OTPs as randomly generating keys and trying them out.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Require help decrypting XOR.
    By mkthnx001 in forum C++ Programming
    Replies: 15
    Last Post: 05-17-2009, 07:15 PM
  2. decrypting
    By cyberCLoWn in forum C++ Programming
    Replies: 11
    Last Post: 12-30-2003, 04:20 PM