Thread: one time pad breakable debate

  1. #241
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by jwenting View Post
    AFAIK the NSA and others use interstellar background noise as a feed for their generators, with filters applied to remove recurring patterns.
    That's as random as it comes.

    And indeed, you can't ever know if what you got from a brute force attempt to decrypt something encrypted using a one time pad is the original message.
    That's what makes it as secure as it is.
    But that's not my point. Point is, it IS possible to brute force the original message, you'd just have a very hard time knowing when you'd succeeded
    You don't have a hard time knowing when you succeed, it's mathematically impossible to know when you succeed, as any message of the same length (or possibly less) can be retrieved from it and is undistinguishable from the original message. That's kind of what this entire topic is about.

  2. #242
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by jwenting
    But that's not my point. Point is, it IS possible to brute force the original message
    That's fine. It is the same thing as saying that it is (theoretically) possible to list all possible messages of a length equal to the plaintext, and that is obviously true.

    Quote Originally Posted by jwenting
    you'd just have a very hard time knowing when you'd succeeded
    Yes, so difficult that it is impossible.
    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

  3. #243
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    But that's not my point. Point is, it IS possible to brute force the original message, you'd just have a very hard time knowing when you'd succeeded
    aargh! [ tears hair out ] you would NEVER know, that has been shown multiple times in this debate, so stop arguing pedantic nonsense

  4. #244
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    Lightbulb

    Quote Originally Posted by jwenting View Post
    It is in theory possible to break the encryption on a one-time pad and receive the cleartext as a result through brute force BUT by definition you'd only have that one message decrypted.
    Any other message encrypted using a one-time pad, even one generated using the same system, would still be undecipherable except through the same brute force approach, the previous success providing no basis at all on which to shorten the time required for the decoding effort.
    Perhaps a thought experiment would help illustrate the predicament a little more clearly:

    There are two light switches in room A, one marked "DATA" and the other "CODE". The output of the two is fed into an XOR gate, and the result is sent along a wire to a light bulb in room B, which is occupied by you, the observer. Notice that it is impossible to infer the state of either of the switches from the state of the bulb. If the light is shining, the DATA/CODE pair is either going to be [1, 0] or [0, 1]. Conversely, if unlit, [1, 1] or [0, 0]. Either way, your guess has a 50% chance of being correct, and a 0% measure of certainty! The *only* way to know for sure is to know, a priori, the value of *one* of the switches. Until then, you are as good as blind.

  5. #245
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    I just encrypted a 2 letter word, the encrypted text reads: kv
    what is the decrypted 2 letter word? Shouldnt be impossible for you to brute-force that if it was breakable now would it?

  6. #246
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Shakti
    I just encrypted a 2 letter word, the encrypted text reads: kv
    what is the decrypted 2 letter word? Shouldnt be impossible for you to brute-force that if it was breakable now would it?
    It may be impossible to narrow down to a single plausible plaintext due to insufficient ciphertext (read up on unicity distance), whether or not a one time pad was used.
    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

  7. #247
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I think locking this thread would encourage people to read it, because we're repeating stuff now.

  8. #248
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by whiteflags View Post
    I think locking this thread would encourage people to read it, because we're repeating stuff now.
    Maybe they've read it but they're just ... erm... not too intelligent.

  9. #249
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    Ok, I give. One-time pads are breakable. You can brute force your way out of anything. And you can of course always find the correct key within a matter of hours of receiving your encrypted data.


    ...april fools.
    Consider this post signed

  10. #250
    Registered User kryptkat's Avatar
    Join Date
    Dec 2002
    Posts
    638
    you have just been handed a disk with a one time pad file on it and a key of equal length. you were not the one who encrypted the file you are just the recipient . how do you know for a fact that the file has not been corrupted ? how do you know for a fact that the key has not been corrupted ? how do you know for a fact that the file and the key have not been corrupted or switched or altered in any way ? before you can get to your computer at home you are in a doctors office. the nurse comes in a known spy and you pass out for a few minutes . you pass by several mri machines going to the lobby. on the way home you pass by several cell phone towers and tv and radio towers. you arrive home and insert the disk in to your computers floppy drive. you undo the file with the key. <right here this instant in time> the recipient has never seen the contents of the file. what does it take to identify the contents of the file ? <point external knowledge> external knowledge of the written language or knowledge base of images of object that make up the brains understanding of what objects are in order to interpret and identify what is there or that they are looking at. what if it is plans for a new trash compactor and you are in the automotive industry ? does it have to be in que with what you would normally do ? is it only when it is not related to your occupation do you suspect that the disk or file or key was switched or altered ? what if the contents was in another language that you do not know how then do you know if the data was not corrupted altered or switched ? what if a spy gets a hold of your disk with the file and key ? when the contents of the file are exposed it still requires interpretation when the contents of the file are examined. be it one file or several million separate files. when the contents of the file are exposed it is done be it opened broke or cracked. the programs part is done.

    there is an algorithm that will eventually sequentially get the next correct byte. there are also processes to narrow down the choices. distillation is a good way to put that. external knowledge is part of one file contents interpretation so why not many files contents interpretation and examination ? is it because there is only one file ? is it because there is a key ? is it because the contents would or may go along with what you do ?

    yes i knew what avatar image to look for. someone who has never seen that avatar before in the demo may guess the image that appears to be a photo. but with all the stuff on some avatars they might choose or guess the ones that do not appear to be a complete photo. they may think it is supposed to be that way. run it for yourself. you will find the experience to be real.

    Yes, so difficult that it is impossible.
    i believe you mean "improbable" . there is 1 key therefore there is one possibility. one possibility out of a million or billion or more. like hitting the lottery and yet there are people that hit the lottery. the question is "would you know if you hit the lottery" ? meow.

    Not only practically impossible (eg. that the world will be destructed before you can crack it) but actually theoretically impossible (eg. that if you had an infinite amount of resources and time, you still wouldn't be able to get any bit of information from the message).
    again i believe you mean "improbable" . there is 1 key therefore there is one possibility. one possibility out of a million or billion or more. like hitting the lottery and yet there are people that hit the lottery. the question is "would you know if you hit the lottery" ? meow. you would extrapolate information....just may not be of any use or correct information. still with one chance of getting the correct information.

    Even assuming you would have knowledge on the format of the message and could discard the wave file and the text file, how could you know the real image between the millions, billions, trillions, [...] of possible combinations resulting in a valid image?
    if brute forces were producing images that looked like photos a real "porn generator" or movie maker or image maker would be up and running putting the movie industry and camera businesses out of business ? i used the porn example because that is the only time you hear of encryption in the news. it is the only time you hear of anyone trying to undo encryption. unless you are specifically reading a book on the history of encryption.


    Brute force is not sufficient to break a correct use of a one time pad.
    vs
    brute force will expose the correct contents by generating the correct key sequence once.
    at the point of exposure of the correct contents no matter if the individual is the attacker or recipient or the one who encrypted the one time pad or doing data recovery it still goes to external knowledge based data analysis. which may or may not be considered cryptanalysis.


    thread ended <maybe?> . thank you all for your participation.

    yes i read all the posts.

  11. #251
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    I quite never met anyone like you. You should be proud.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  12. #252
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by kryptkat View Post
    i believe you mean "improbable" . there is 1 key therefore there is one possibility. one possibility out of a million or billion or more. like hitting the lottery and yet there are people that hit the lottery. the question is "would you know if you hit the lottery" ? meow.
    Wait. What? Read what I wrote again:
    Not only practically impossible (eg. that the world will be destructed before you can crack it) but actually theoretically impossible (eg. that if you had an infinite amount of resources and time, you still wouldn't be able to get any bit of information from the message).
    Does that sound like "improbable"? I mean IMPOSSIBLE. Clear, now?

    You were able to find out which of the avatars the right one was because you knew "the message". Of course, if you know the message, encryption is completely and utterly useless. If you didn't know the message you would have no idea which was the message.

    Now, let me show you a message, hexadecimally encoded: 1D AB 04 92 FF.
    What did I write here? Any 5-letter word that makes sense could fit there. "wrong". "idiot". "moron". "read!". "crap.". "right?". "apple". Which is the right one? Well, there is a key that would result in one of those for each of these words. And for all other words or combination of words of the same length. You, as reader without a key or any information on the key, can't have any idea which is the right one. Maybe I just called you a moron. Maybe I said you were wrong. Maybe I said apple. Maybe it didn't mean anything at all.
    In that sense, yes, you can brute force it. But you can never know that what you brute forced is correct. That is IMPOSSIBLE.

    Here's another message: 00 00 00 00 00 00 00 00 00 00 00.
    What does that mean? Well, "Heil Hitler" fits. But also "Peace 4 All". Which is the right one? Am I a nazi or a hippy? But then again, maybe it said "How are you". Or "I love you!". Or "Let's f_ck!". Or any combination of 11 characters. Right, maybe you'd know something about me, and know I'd write something in a certain direction. Still, it would amount up to so many meaningful combinations.
    And sure, you can, again, brute force it. But again, you shall never know if what you brute forced is correct. That is IMPOSSIBLE.

    Now, how would brute force work? Brute forcing would be no better than generating ALL possible combination of characters of the same length. So you don't even need the encrypted text! If you know it has a length of 5 and consists only of a-z, you don't need to know the encrypted text to figure out all combinations that would result out of the brute force:
    aaaaa
    aaaab
    aaaac
    .....
    aaaaz
    aaaba
    aaabb
    aaabc
    .....
    zzzzz

    So why even bother brute forcing the encrypted text? Just generate all possible combinations of characters. It's just as fast, just as good, and just as likely to find the proper plain text the first.


    Why am I still trying this? You are IMPOSSIBLE.

  13. #253
    Registered User jdragyn's Avatar
    Join Date
    Sep 2009
    Posts
    96
    Quote Originally Posted by kryptkat View Post
    you have just been handed a disk with a one time pad file on it and a key of equal length. you were not the one who encrypted the file you are just the recipient . how do you know for a fact that the file has not been corrupted ? how do you know for a fact that the key has not been corrupted ? how do you know for a fact that the file and the key have not been corrupted or switched or altered in any way ?
    You might want to seriously re-consider crossing any streets in the near future. How do you know a meteorite isn't going to fall to the earth in that exact spot during the exact moment you are crossing a street?

    What if there were no hypothetical situations?
    C+/- programmer extraordinaire

  14. #254
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by kryptkat
    you have just been handed a disk with a one time pad file on it and a key of equal length. you were not the one who encrypted the file you are just the recipient . how do you know for a fact that the file has not been corrupted ? how do you know for a fact that the key has not been corrupted ? how do you know for a fact that the file and the key have not been corrupted or switched or altered in any way ?
    Any beginner to cryptography knows that encryption provides secrecy (confidentiality), not data integrity.

    Quote Originally Posted by kryptkat
    i believe you mean "improbable" . there is 1 key therefore there is one possibility. one possibility out of a million or billion or more. like hitting the lottery and yet there are people that hit the lottery. the question is "would you know if you hit the lottery" ? meow.
    No, not improbable. Impossible. If it were only improbable, then with sufficient ciphertext, brute force would be enough to obtain the corresponding plaintext.
    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

  15. #255
    Registered User kryptkat's Avatar
    Join Date
    Dec 2002
    Posts
    638
    the computer or the program has no way to know if or when the correct data is exposed. when the computer or program exposes the correct data no matter what it may be the computers or the programs job is done .... that data is exposed cracked broken unencrypted what ever you want to call it. with one chance or exposure of one key makes no difference to the computer or software. at the point of exposure of the correct contents no matter if the individual is the attacker or recipient or the one who encrypted the one time pad or doing data recovery it still goes to external knowledge based data analysis. which may or may not be considered cryptanalysis.
    brute force will expose the correct contents by generating the correct key sequence once. if the attacker recognized the correct key it is then broken or cracked with external knowledge. therefore the correct term is improbable. because there is one chance in 256EEfilelength.

    should you get a porn generator i say enjoy it.

    If it were only improbable, then with sufficient ciphertext, brute force would be enough to obtain the corresponding plaintext.
    you would get the correct corresponding plaintext or other file or whatever was vernamed. even with unicity distance considered only the person that encrypted the small data would be the only one to recognize the correct contents instantly. anyone else would have to go on more external knowledge in order to have an educated guess about the contents of the unencrypted file.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Replies: 11
    Last Post: 03-29-2009, 12:27 PM
  3. calculating user time and time elapsed
    By Neildadon in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2003, 06:00 PM
  4. relating date....
    By Prakash in forum C Programming
    Replies: 3
    Last Post: 09-19-2001, 09:08 AM