one time pad breakable debate

This is a discussion on one time pad breakable debate within the General Discussions forums, part of the Community Boards category; i think a demo is in order. the original image is at the left. the following image was brute forced. ...

  1. #226
    Registered User kryptkat's Avatar
    Join Date
    Dec 2002
    Posts
    638
    i think a demo is in order. the original image is at the left. the following image was brute forced.
    one of the images is 45% of the correct key. one of the images is 60% of the correct key. one of the images is 100% the correct key. i will let you make up your own mind as to which image is the correct key. all i did was enlarge the image by two only to show the distortion more clearly.
    <meow "show the distortion more clearly" > i will let you make up your own mind to how much of the actual image you really need to make a positive identification.

    i would like to conclude this debate with the demo. thank you all for participating in the debate.

    real life example.
    there was this file of pedo that put up on the internet a image of himself that was swirled. he thought that it could not be unswirled. someone unswirled that image enough for law enforcement to make a positive identification. it was on amw. although it was not a one time pad it is a good example of what can be done and how much it takes to make a positive identification. as i recall it was undone about 80%.

    analogy.
    if there was a brand new car in front of you. behind you is this large warehouse filled with millions of keys. if it were a contest they would put a time limit on you so that you would be less likely to unlock the car and drive off with it the winner. for the analogy we will give you all the time it takes to try every single key. for one individual that would be a long chore. it might take you four weeks or more. but for an agency or large corporation they could put many employees on the task to find the correct key. that would shorten the time it takes to find the correct key.
    with a file it is more of a matter of percentage of file undone with the correct key for that byte. i like the focus analogy or percent of file undone.

    yes i had a little fun with the porn generator concept to make a point. remember you were the ones saying "you can not see the tree through all the woodies".

    no i am not a troll and i am not trolling. the quote put up with red in it was what laserlight said. the demo should show you what really happens based on actual experience.


    this concludes the one time pad debate.
    Attached Images Attached Images  

  2. #227
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,467
    Kryptkat,

    Under a one-time pad, and for that exact same file you show here, you would have other possible keys showing the exact same effect. Only, instead of laserlight cute avatar you would be seeing mine. In other keys you would be seeing yours, in other keys laserlight avatar would be blonde (nooo!), and in other keys you would have a text file with a portion of the United States Declaration of Independence in Romanian. Other keys would result in a wave file with a rather poignant Kumbaya interpretation (which you would unfortunately miss because the file was too small).

    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?

    Aren't you aware that you actually didn't yet understand the implications of a one-time pad?
    Last edited by Mario F.; 03-29-2010 at 06:41 PM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    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.

  3. #228
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Like Mario said, assuming that you knew for a fact that it was an image file and only the image had been touched with the one time pad, you would still have to account for every possible image of that size.

    You say you've brute-forced your way to laserlight's avatar. That's interesting. Did you find any keys that looked like anyone else's avatar? For example, let's say that laserlight's avatar is the encrypted message. Well, this key turns laserlight's avatar into MK27's avatar. Ah-ha! That must be the encrypted message, right? Well, no. This key turns laserlight's avatar into brewbuck's avatar. So, which is it? Which interpretation is correct?

    Also, you have provided no source code. This would be helpful to determine you've done what you've actually said. Here is my source code that generates the keys above and verifies that they correctly turn laserlight's avatar into other avatars.

    Obviously, these keys are just as valid as any other. A full brute-force search of possible keys would generate these keys as well as trillions of others. This is why OTP cannot be broken. You cannot distinguish the correct message from the overwhelming number of false positives.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #229
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    i think a demo is in order. the original image is at the left. the following images were brute forced.

    sorry, couldn't help myself.
    Attached Images Attached Images  
    Consider this post signed

  5. #230
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by pianorain View Post
    You cannot distinguish the correct message from the overwhelming number of false positives.
    I prefer other explanations, because this way of looking at it leads some people to think that if only there was "some way" to sieve through the results to find "true" positives, the method could be broken.

    At its heart, the problem is an information-theoretic one. Each plaintext bit is modified by a completely random key bit. This obliterates the information in the ciphertext, by making the distribution of the ciphertext precisely equal to the distribution of the key. Any deviation from the uniform case is wiped away. In other words, the conditional entropy of the plaintext given the key, is equal to the entropy of the key. Without knowledge of the key, there is no information about the plaintext. The ability to always find a key which decrypts to an arbitrary plaintext, seems to fall on some peoples' deaf ears.

    And by the way, I'm glad people are fooling around with the program I posted. There is a way to use it to generate arbitrary keys to decrypt ciphertexts into arbitrary plaintexts, and you guys obviously have figured out how to do it. It's not really that hard, given some basic knowledge of the way XOR works.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  6. #231
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by kryptkat View Post
    analogy.
    if there was a brand new car in front of you. behind you is this large warehouse filled with millions of keys. if it were a contest they would put a time limit on you so that you would be less likely to unlock the car and drive off with it the winner. for the analogy we will give you all the time it takes to try every single key. for one individual that would be a long chore. it might take you four weeks or more. but for an agency or large corporation they could put many employees on the task to find the correct key. that would shorten the time it takes to find the correct key.
    with a file it is more of a matter of percentage of file undone with the correct key for that byte. i like the focus analogy or percent of file undone.
    @bernt: Nice work ;-). Although I doubt it'll make kryptkat understand.

    Wow. Okay. This is hopeless, but I'm going to give it one more try.
    Your analogy is off. Let me give you a good analogy:
    Let's say you have X keys. However, each key unlocks a box and in each box, there is a text. Some might make sense, some might not. That's the situation with one time pads. Now, there are 2^(8*100) possible keys for a 100 byte string. Well, it doesn't even matter that's a lot (I think it's a lot more than the number of atoms in the universe), but worse is that each key unlocks one box. And one out of a million boxes contain a meaningful message. You can never know which message was intended.

    I even showed you how a single encrypted message could be any word of the same length. Did you even read that message? Did you fail to understand it and simply decide not to reply?

    Funny how you claim that a wrong message, showing that you still don't grasp the concept after so many pages, can conclude the discussion.

  7. #232
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,744
    Emphasis mine:
    Quote Originally Posted by kryptkat
    real life example.
    there was this file of pedo that put up on the internet a image of himself that was swirled. he thought that it could not be unswirled. someone unswirled that image enough for law enforcement to make a positive identification. it was on amw. although it was not a one time pad it is a good example of what can be done and how much it takes to make a positive identification. as i recall it was undone about 80%.
    The part in bold means that your "real life example" is completely invalid. Completely.

    The "swirl" is akin to the use of other cryptosystems, where at least in theory it is possible to obtain the plaintext from sufficient ciphertext by brute force. In fact, since the "swirl" is not designed for encryption, it means that it is much weaker, i.e., more like "snake oil" encryption than AES.

    Quote Originally Posted by kryptkat
    no i am not a troll and i am not trolling. the quote put up with red in it was what laserlight said. the demo should show you what really happens based on actual experience.
    Your "actual experience" is faked. You merely went through an exercise designed to appear as if you broke a one time pad, and perhaps you actually managed to fool yourself. Fortunately, this does not fool anyone who understands the information theoretic perfect secrecy provided by the correct use of a one time pad.

    Quote Originally Posted by kryptkat
    this concludes the one time pad debate.
    I can agree with this. It concludes that you do not understand why the correct use of a one time pad provides information theoretic perfect secrecy, despite the best efforts of many to help you to understand.

    If you still believe that everyone else is wrong, then write a paper. Publish it. Speak at conferences. Become world famous. Every introductory textbook to cryptography (and some more advanced ones, and probably also those on computer security in general) will have to be corrected due to your findings.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #233
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    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.

    While retrieving that one message might yield valuable information to the party doing the decryption, by the time this has been achieved and verified to be at least a feasible decryption (rather than something completely unrelated, see prior responses) the information encrypted using the one-time pad will usually be outdated and no longer of operational value to the intercepting parties (which is the purpose of using encryption at all, slowing down a potential opponent's efforts at reading your communications until such a time as that communication is no longer relevant to your efforts).

  9. #234
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,744
    Quote Originally Posted by jwenting
    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.
    What do you mean by "by definition you'd only have that one message decrypted"?

    Quote Originally Posted by jwenting
    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.
    What do you mean by "one generated using the same system"?

    Quote Originally Posted by jwenting
    While retrieving that one message might yield valuable information to the party doing the decryption, by the time this has been achieved and verified to be at least a feasible decryption (rather than something completely unrelated, see prior responses) the information encrypted using the one-time pad will usually be outdated and no longer of operational value to the intercepting parties
    Well, it is more than that, actually: in order to verify that the decrypted message is indeed the plaintext, the attacker must have sufficient external information such that he/she does not need the ciphertext in the first place.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #235
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,467
    God! And full circle we come back to the first post.

    What a complete nonsense!
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    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.

  11. #236
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    What do you mean by "by definition you'd only have that one message decrypted"?
    Which part don't you understand?
    He'd have that single message, and no means to get any other.
    That's the nature of the one-time pad.

    What do you mean by "one generated using the same system"?
    Another pad created by the same generator, obviously.
    Do you think the NSA writes a new generator for every key they generate?
    Or a new generator generator?

    Well, it is more than that, actually: in order to verify that the decrypted message is indeed the plaintext, the attacker must have sufficient external information such that he/she does not need the ciphertext in the first place.
    Conceivably so. And at the time he has succeeded deciphering it he'll have that information or otherwise no longer need to attain it, making the effort pointless.
    For example the message might be about an impending military operation against him. By the time he breaks the code, the operation will have been long since executed.

  12. #237
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,425
    And at the time he has succeeded deciphering it he'll have that information or otherwise no longer need to attain it, making the effort pointless.
    For example the message might be about an impending military operation against him. By the time he breaks the code, the operation will have been long since executed.
    this sort of thing has been pointed out already, in another thread and early in this one, probably about twenty times in this endless thread haha

    we are lumbering toward the semantics debate again, i am going to try and derail it already >>

    The verb "to break" in the context of decrypting a coded message means > 'reveal the message intended by the person(s) that coded the message to start with'

    it does not mean "succeed in distilling any kind of coherent message At All from the coded document"

    which is what some people have argued most pedantically
    Last edited by rogster001; 03-30-2010 at 07:47 AM.

  13. #238
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by jwenting View Post
    Conceivably so. And at the time he has succeeded deciphering it he'll have that information or otherwise no longer need to attain it, making the effort pointless.
    For example the message might be about an impending military operation against him. By the time he breaks the code, the operation will have been long since executed.
    Actually, either I don't understand this part well enough or you fail to understand one time pads as well. Because you don't have any bit of information about decoding it. Even if you know everything about the operation, even if you know half of the plain text, you can NEVER KNOW the rest. Even if the military operation has been executed a hundred times. 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).

  14. #239
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,744
    Quote Originally Posted by jwenting
    Which part don't you understand?
    He'd have that single message, and no means to get any other.
    That's the nature of the one-time pad.
    The problem is, he will not "have that single message", unless it is obtained by some other way (e.g., torture). Brute force is not sufficient to break a correct use of a one time pad. That's the nature of the one-time pad.

    Quote Originally Posted by jwenting
    Another pad created by the same generator, obviously.
    Do you think the NSA writes a new generator for every key they generate?
    Or a new generator generator?
    Sorry, but if you read this thread, you would see that we went into a discussion of random number generators. If you are talking about a pseudorandom number generator, then no, I am fairly certain that the NSA does not use PRNGs for one time pad key material. But if you are talking about a "real" RNG, then talking about "the same system" sounds strange.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #240
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    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

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, 05:00 PM
  4. relating date....
    By Prakash in forum C Programming
    Replies: 3
    Last Post: 09-19-2001, 09:08 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21