Thread: one time pad breakable debate

  1. #46
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Quote Originally Posted by kryptkat View Post
    even a short 13 char brute force generates 35 gigabytes of data. looking through the contest data 4 hours a day for a week i only got through 2 gigs. then did a shorter one. due to a programming error i made was the only reason type in key using the data did not work. if the program had worked correctly then that would have worked type in one key word at time with data.
    I assume you mean the contest rogster001 held here recently? That was not a one time pad, and therefore could be bruteforced. A true one time pad CANNOT be bruteforced, we have already stated so several times.


    getting hold of the key books is a valid way of "breaking the one time pad". meow.
    I guess you can call it that. Personally I don't think decrypting using a known key is the same as breaking a cipher though.

    can we refrain from posting "break this" please and stick to the debate. thank you.
    I didn't literally mean you should break it The point I was trying to make, and that brewbuck further clarified, is that yes you can bruteforce a list of all possible words but you cannot know which one is the correct one. It is impossible. And saying that the encryption is broken because one of the words in your bruteforced wordlist is the correct one is just plain wrong.

    if your one time pad uses xor and 0 to 256 you can make a program to ignore anything that is not 'a' to 'z' or 'A' to 'Z' then use a spell checker to throw out nonwords. even though that will reduce the file size intelligence still has to be used to interpret any possible messages. the correct one or not.
    And how would you know only letters from the English alphabet is used? Maybe the plaintext is German? What about punctuation? What if it's not even text?
    I haven't ran brewbuck's code sample, but from quickly looking over it it seems to be able to handle any type of file, both text and binary. How would you find a reliable method of determining if your bruteforced answer is the correct one or not?

  2. #47
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by kryptkat View Post
    if your one time pad uses xor and 0 to 256 you can make a program to ignore anything that is not 'a' to 'z' or 'A' to 'Z' then use a spell checker to throw out nonwords. even though that will reduce the file size intelligence still has to be used to interpret any possible messages. the correct one or not.
    breaking is a one time pad can be a quandary.
    Nope, that may work with a caeser cypher, but it's useless against the OTP. The bottom line is that a brute force attack wouldn't reveal a single bit of information. Period.
    Last edited by Sebastiani; 03-14-2010 at 08:37 AM. Reason: (emphasis mine)

  3. #48
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    @kryptkat

    First, you need a true random source, not the output of some computer algorithm.
    WPI Cryptography and Information Security (CRIS): True Random Number Generators (TRNGs)

    Second, in an ideal scenario, Alice and Bob meet in secret and both make a copy of the pad. No one else knows what the pad is. However, if Bob is stuck in enemy territory, life gets a lot more interesting...
    See above for earlier mentions of the key distribution problem.

    Third, you need as much pad as there is data. If you're trying to send 1MB of data, then you NEED 1MB of pad as well. The volume of pad needed is another problem OTP has, compared to algorithmic approaches.

    Forth, for Alice, immediately after encrypting x bytes of message with x bytes of pad, then x bytes of pad MUST BE DESTROYED. This is vital. Past breaks on OTP have been because people failed to understand what once actually means.

    Fifth, for Bob, immediately after decrypting the message with x bytes of pad, then x bytes of pad MUST BE DESTROYED.

    If Eve gets a hold of either pad, then the game is over.
    Alice and Bob have to assume that Eve has a copy of the encrypted message and is just waiting for A/B to screw up and leave the pad in an exposed state.

    > even a short 13 char brute force generates 35 gigabytes of data. looking through the contest data 4 hours a day for a week i only got through 2 gigs.
    Yawn - you're wasting your time.


    Cyphertext
    mngqr30=gy8vq5yabq

    Four possible permutations (out of billions)
    Fancy a meal@20:00
    kryptkat is wrong!
    KILL THE PRESIDENT
    twilight mushrooms

    Unless you have the pad (not bloomin' likely if Alice and Bob are in any way competent), then you have ZERO information to figure out which is the real message, as all are equally plausible.

    The 4th one might just mean the same as the 3rd one. Without the secret phrase book, you would still be in the dark.

    But your fictitious decrypt would also have generated the third message as well, but why would you believe that message rather than any of the others?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #49
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Salem
    First, you need a true random source, not the output of some computer algorithm.
    WPI Cryptography and Information Security (CRIS): True Random Number Generators (TRNGs)

    Third, you need as much pad as there is data. If you're trying to send 1MB of data, then you NEED 1MB of pad as well. The volume of pad needed is another problem OTP has, compared to algorithmic approaches.

    Forth, for Alice, immediately after encrypting x bytes of message with x bytes of pad, then x bytes of pad MUST BE DESTROYED. This is vital. Past breaks on OTP have been because people failed to understand what once actually means.

    Fifth, for Bob, immediately after decrypting the message with x bytes of pad, then x bytes of pad MUST BE DESTROYED.
    Quote Originally Posted by Salem
    Unless you have the pad (not bloomin' likely if Alice and Bob are in any way competent), then you have ZERO information to figure out which is the real message, as all are equally plausible.

    The 4th one might just mean the same as the 3rd one. Without the secret phrase book, you would still be in the dark.

    But your fictitious decrypt would also have generated the third message as well, but why would you believe that message rather than any of the others?
    Aye, these reiterate and elaborate on what I have already told kryptkat, but apparently kryptkat still does not get it:
    Quote Originally Posted by laserlight
    The problem is, does the intercepted order read "monday attack cboard" or is it "do not attack cboard"? With a one time pad, both are equally likely, but if you guess wrong, cboard might be destroyed. This is what is meant by a one time pad being unbreakable. You can find the plain text, but you cannot identify it as the plain text with any confidence because there are so many alternatives that are equally likely to be the original plain text, even after you have discarded those that are not.
    Quote Originally Posted by laserlight
    The main problem concerning the use of a one time pad is key management: the key material must be established in advance over a secure channel, be sufficient for all secure communication until new key material can be established, and then only ever used once.
    Quote Originally Posted by laserlight
    Oh, and besides problems with key distribution, usage and storage, there's also the problem of key generation: the keys really must be random.
    From kryptkat's point of view, as long as you can list the plaintext among a list of possible messages, the encryption is broken, even if you cannot determine exactly which is the plaintext. If we look at this in terms of a lottery: according to kryptkat, everyone who plays in a lottery that can be won has already won the lottery, because whatever bet you place could be a winning bet, even if it isn't.
    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

  5. #50
    Registered User kryptkat's Avatar
    Join Date
    Dec 2002
    Posts
    638
    a while back i did a study of randomology where i made a program called "wickid.c" that placed pixels at random points to see what random looked like. apparently i was the only one to see patterns. i believe this is because i have faster vision processing. young cats can see the dot move along the tv crt screen where the older cats could see the whole picture.

    lets say i modify this program so that no dots are displayed and only a single porn.bmp is. now further modification to encrypt it with a one time pad. random run or program random generator or your own "key.txt" where you supply a single random number one at a time or predetermined random in the file "key.txt". with true random numbers. your own true random source.

    pic encrypted with true random source one time pad check now to the brute force of the key the entire length of the data. check. " what differentiates a one time pad and these other cryptosystems is that the number of possible keys is no less than the number of possible messages (and all are equally likely). " and " cannot see the wood for the trees " would hold true no matter what the data. so as the file is brute forced other porn images appear. woohoo a porn generator ! <backflip> <backflip> <backflip> <backflip> meow ! < double laided out backflip> meow ! all kinds of porn. all kinds of fetish porn. all kinds of kitty porn ! stuff never even heard of. images magically appear. pictures that have never been taken by a digital camera. no need to use a camera any more thanks to the porn generator. a porn generator would put the porn industry right out of business. every porn film ever made right through your new porn generator. films never made come right through your porn generator too. all theoretically possible.

    seriously i think you would only get parts of the original image where the rest if wrong key would appear as random pixels or blobs. out of focus if you will as an analogy. until you get the correct key then your image would be 100% clear or in focus as an analogy.

    text i believe is the same out of focus. with the correct key the rest of the message will be there. with the short two character or a few words the obfuscatetion is more unclear. but with a larger text you can get more of a coherent message. i get it. i just happen to disagree.

    And how would you know only letters from the English alphabet is used? Maybe the plaintext is German? What about punctuation? What if it's not even text?
    trying every key to see what shows up.

    How would you find a reliable method of determining if your bruteforced answer is the correct one or not?
    in the movie and in books about ww2 the cryptanalysis sent out <leeked> specific information to confirm what the cipher was about. "midway has a boiler problem. needs new replacement water heater " as example.

    we were discussing using the vigenere with a random key the entire length of the message. the weakness ironically would be the use of the chart lookup. i know normal vigenere is not a one time pad.

    salem thank you for the link. for the record i am not wrong. just a diffff belieffff

    i believe the one time pad is breakable. if you brute force it trying every possible key that would negate weather it was created by a true random number generator or not. sooner or later the key would be found. that is the question on the table if the message text is exposed it is broken even if the user or person looking at it does not recognize the message as being the actual one. depending on what was in the message that would be the point that external intel would have to begin.

    thank you all for participating in the debate. you can all set a flame your nitrocellulose page now. <pooffff>

  6. #51
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by kryptkat
    seriously i think you would only get parts of the original image where the rest if wrong key would appear as random pixels or blobs. out of focus if you will as an analogy. until you get the correct key then your image would be 100% clear or in focus as an analogy.

    text i believe is the same out of focus. with the correct key the rest of the message will be there. with the short two character or a few words the obfuscatetion is more unclear. but with a larger text you can get more of a coherent message. i get it. i just happen to disagree.
    You think wrong: you are not thinking of what this information theoretic perfect secrecy of a one time pad means. You don't get it: you are still harping on something that applies to "normal" ciphers like AES, but not to a one time pad. I simply do not understand why you cannot understand that with information theoretic perfect secrecy, you cannot determine the correct key because you, as the attacker, have no way of differentiating it from other possible keys that appear to be correct.

    The only room you have to disagree is to dispute this notion of perfect secrecy, i.e., to state that even if there is no way of differentiating the actual key from other possible keys, as long as the attacker can include the actual key in the list of possible keys, the encryption is broken. If you want to define it this way, fine, but you are alone in your definition of "perfect secrecy".

    Quote Originally Posted by kryptkat
    in the movie and in books about ww2 the cryptanalysis sent out <leeked> specific information to confirm what the cipher was about. "midway has a boiler problem. needs new replacement water heater " as example.
    You are talking about a known plaintext attack. This can work when you are trying to break a cipher that is not equivalent to a one time pad, but it is completely ineffective against a one time pad. All you would be able to derive from such cryptanalysis is a key that will never again be used. It is as if you figured out the key, but in the meantime the key has changed.

    Quote Originally Posted by kryptkat
    i believe the one time pad is breakable. if you brute force it trying every possible key that would negate weather it was created by a true random number generator or not. sooner or later the key would be found. that is the question on the table if the message text is exposed it is broken even if the user or person looking at it does not recognize the message as being the actual one. depending on what was in the message that would be the point that external intel would have to begin.
    This is precisely what I mean by you using your own definition of what it means for encryption to be broken. Don't you understand that all you need to "brute force it trying every possible key" is the length of the ciphertext? You do not even need the ciphertext. Therefore, this talk about "depending on what was in the message that would be the point that external intel would have to begin" is laughable, because this "external intel" has to process all plausible messages of the length of the ciphertext, including messages that contradict each other. In other words, after "breaking" the one time pad, you know nothing more about the message than before you "broke" it. This is the key to understand what this information theoretic perfect secrecy is about.
    Last edited by laserlight; 03-16-2010 at 04:28 AM.
    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. #52
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Quote Originally Posted by kryptkat View Post
    i believe the one time pad is breakable. if you brute force it trying every possible key that would negate weather it was created by a true random number generator or not. sooner or later the key would be found. that is the question on the table if the message text is exposed it is broken even if the user or person looking at it does not recognize the message as being the actual one. depending on what was in the message that would be the point that external intel would have to begin.
    Sigh, why do we even bother trying to explain?
    With that definition all encryption is useless because all encryption can be broken without having neither the key, plaintext or ciphertext.
    Using Infinite monkey theorem - Wikipedia, the free encyclopedia will eventually give you the plaintext
    Last edited by _Mike; 03-16-2010 at 04:32 AM. Reason: spelling

  8. #53
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    If we look at this in terms of a lottery: according to kryptkat, everyone who plays in a lottery that can be won has already won the lottery, because whatever bet you place could be a winning bet, even if it isn't.
    i suggest new username Schrodingers Kat then

  9. #54
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by kryptkat View Post
    a while back i did a study of randomology where i made a program called "wickid.c" that placed pixels at random points to see what random looked like. apparently i was the only one to see patterns. i believe this is because i have faster vision processing. young cats can see the dot move along the tv crt screen where the older cats could see the whole picture.

    lets say i modify this program so that no dots are displayed and only a single porn.bmp is. now further modification to encrypt it with a one time pad. random run or program random generator or your own "key.txt" where you supply a single random number one at a time or predetermined random in the file "key.txt". with true random numbers. your own true random source.

    pic encrypted with true random source one time pad check now to the brute force of the key the entire length of the data. check. " what differentiates a one time pad and these other cryptosystems is that the number of possible keys is no less than the number of possible messages (and all are equally likely). " and " cannot see the wood for the trees " would hold true no matter what the data. so as the file is brute forced other porn images appear. woohoo a porn generator ! <backflip> <backflip> <backflip> <backflip> meow ! < double laided out backflip> meow ! all kinds of porn. all kinds of fetish porn. all kinds of kitty porn ! stuff never even heard of. images magically appear. pictures that have never been taken by a digital camera. no need to use a camera any more thanks to the porn generator. a porn generator would put the porn industry right out of business. every porn film ever made right through your new porn generator. films never made come right through your porn generator too. all theoretically possible.

    seriously i think you would only get parts of the original image where the rest if wrong key would appear as random pixels or blobs. out of focus if you will as an analogy. until you get the correct key then your image would be 100% clear or in focus as an analogy.

    text i believe is the same out of focus. with the correct key the rest of the message will be there. with the short two character or a few words the obfuscatetion is more unclear. but with a larger text you can get more of a coherent message. i get it. i just happen to disagree.


    trying every key to see what shows up.


    in the movie and in books about ww2 the cryptanalysis sent out <leeked> specific information to confirm what the cipher was about. "midway has a boiler problem. needs new replacement water heater " as example.

    we were discussing using the vigenere with a random key the entire length of the message. the weakness ironically would be the use of the chart lookup. i know normal vigenere is not a one time pad.

    salem thank you for the link. for the record i am not wrong. just a diffff belieffff

    i believe the one time pad is breakable. if you brute force it trying every possible key that would negate weather it was created by a true random number generator or not. sooner or later the key would be found. that is the question on the table if the message text is exposed it is broken even if the user or person looking at it does not recognize the message as being the actual one. depending on what was in the message that would be the point that external intel would have to begin.

    thank you all for participating in the debate. you can all set a flame your nitrocellulose page now. <pooffff>
    Hmm...yes, well that was adequately disturbing. Thank you, Kryptkat. On second thought, I'm actually glad you don't grasp the concepts too well...
    Last edited by Sebastiani; 03-16-2010 at 05:37 AM.

  10. #55
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by kryptkat View Post
    a while back i did a study of randomology where i made a program called "wickid.c" that placed pixels at random points to see what random looked like. apparently i was the only one to see patterns. i believe this is because i have faster vision processing. young cats can see the dot move along the tv crt screen where the older cats could see the whole picture.
    If you used your computer's random number generator -- rand() -- of course you will notice patterns because it is not truly random, it produces "randomesque" patterns.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main() {
    	int i;
            for (i=0;i<100;i++) printf("%d ",rand());
    	return 0;
    }
    Run that as many times as you like. Every single time, you will get the exact same sequence of "random" numbers. That's a pattern alright.

    You cannot study "randomness" using a computer RNG. This was the point of the discussion vis, why you cannot easily create a one-time pad with one.

    One way to get a truly random one-time pad would be to get the user to type randomly or whatever for 8X the length of the message, then do odd/even modulus on this pad to get bits.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  11. #56
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    I didn't read this thread because I can't believe this discussion actually exists. FACT: It is impossible. Assuming the pad is random enough.
    Easy to explain as well. Let's say you have a character A you want to encrypt using one character K. You can do "A ^ K" to get the encrypted text, and the other side, knowing the key, can do "(A ^ K) ^ K = A" to decrypt it.
    Without knowing K, K can be anything. Meaning that, with an 8-bit-byte, K can have 256 distinct values. Meaning that any given character XOR'ed with K can have 256 distinct values. Yes, that is any character whatsoever.
    Even if you expect a certain plaintext to be sent you can never prove that it was indeed sent without ever knowing the key.

    Probably this was explained already, though. But as I said, I couldn't be bothered reading everything. I did read this:

    Quote Originally Posted by MK27 View Post
    One way to get a truly random one-time pad would be to get the user to type randomly or whatever for 8X the length of the message, then do odd/even modulus on this pad to get bits.
    Actually that would probably be still pretty non-random. But /dev/random does something quite similar, except with a lot more input depending on many variables. I think you can call that "REALLY" random, as it depends on about an infinite number of unpredictable factors coming from the person operating the computer and many other environmental sources (I bet it uses network traffic and stuff as well).

  12. #57
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    One way to get a truly random one-time pad would be to get the user to type randomly or whatever for 8X the length of the message....
    apparently even random typing is not to be trusted as random keyboard bashing still reveals patterns , see Simon Singh's 'The Code Book', hell see the book anyway, its class....and i think a certain contributor to this discussion would benefit !!

  13. #58
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by EVOEx View Post
    Actually that would probably be still pretty non-random.
    No, it would be very random, since each keypress would be simply evaluated as either "odd" or "even", your tendency to hit "asdf" frequently would be irrelevant (it's just odd-odd-even-even), and there is an 8:1 keypress:message character ration.

    I was going to say hit keys for the same length as the message then do % 0-7 on each key value to set 8 bits, but this will be prone to obvious patterns I think.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  14. #59
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by MK27 View Post
    No, it would be very random, since each keypress would be simply evaluated as either "odd" or "even", your tendency to hit "asdf" frequently would be irrelevant (it's just odd-odd-even-even), and there is an 8:1 keypress:message character ration.

    I was going to say hit keys for the same length as the message then do % 0-7 on each key value to set 8 bits, but this will be prone to obvious patterns I think.
    Okay let me type a random string as I might, would I be prompted with such a thing not knowing how important randomness was:
    asdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfas dfasdfasdfasdfasdfasdf

    Should I continue?
    Woops, only 1 possible bit :P. Personally, I have the tendency to type aerg if I just hit the keyboard randomly. But not very accurately, so there would be a few misses. But still, 80% of the bits would be the same.

    /dev/random is loads better :P.

  15. #60
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Personally, I like the use of radioactive decay to generate random numbers.
    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

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