Thread: one time pad breakable debate

  1. #31
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Mario F.
    But the seed is not the key. Hence why I put it in double quotes. The key will be generated by the seed. The mechanism for said generation is an RNG. Meaning the actual key can be generated on the fly and the decryption is made right after, as long as:

    a) you possess the correct seed
    b) you possess the correct RNG
    c) you possess the correct decryption algorithm
    According to Kerckhoffs' principle, the attacker knows the PRNG and decryption algorithm.

    What you described is a possible use of a PRNG to implement a stream cipher. This can be secure with the use of a cryptographically secure PRNG, but it does not have the property of being unbreakable like a one time pad. By observing sufficient ciphertext, it is theoretically possible to determine the state of the PRNG, and thus break the encryption.
    Last edited by laserlight; 03-12-2010 at 11:49 AM. Reason: I always get the guy's name wrong, grr...
    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

  2. #32
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by laserlight View Post
    What you described is a possible use of a PRNG to implement a stream cipher. This can be secure with the use of a cryptographically secure PRNG, but it does not have the property of being unbreakable like a one time pad. By observing sufficient ciphertext, it is theoretically possible to determine the state of the PRNG, and thus break the encryption.

    I promise I'll munch on that, laserlight. But you still will have the pad to deal with. I'm not weakening the security. I may eventually agree I'm not strengthening it either after I give it some thought. But that's not the point. You will still have to pass the pad. I'm only suggesting storing/distributing the key can be simplified.
    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. #33
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Mario F. View Post
    Note really MK. It would be sensible to store the RNG with the decryption algorithm.
    Presuming the only secret part is the long int key, that does mean that your public decrytion algorithm w/ RNG can only have LONG_INT_MAX possible keys.

    If you can keep the algorithm and the RNG secret, yeah, this could be more convenient, but then you are still stuck with all the security problems vis. storage and distribution of the algo & RNG. Also, this would no longer be a "one time" pad, since the algo and RNG are static.
    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

  4. #34
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    The pad wasn't removed. The only thing happening is that I added another layer at the top to simplify the key distribution.

    I really can't see what am I doing wrong trying to explain this. I kinda give up if you don't mind.
    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.

  5. #35
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Mario F. View Post
    I really can't see what am I doing wrong trying to explain this. I kinda give up if you don't mind.
    Well ditto -- my point is, going by your method, if you have the algo and the RNG, you only have to deal with LONG_INT_MAX possible keys, not 2^(message length*8) possibilities.

    As I think laserlight has indicated, that would mean this is not the same thing as a true one time pad, in which each bit is uniquely indeterminate -- a seeded RNG will not do that, it will produce LONG_INT_MAX patterns of bits: the bits are not uniquely indeterminate in relation to one another, they are in accord with the pattern contained in the RNG.

    So it is encryption, but it is NOT a one time pad (and probably not as unbreakable). A true one time pad key generator will generate 2^8000 possible keys for a 1000 byte message. A RNG with a long int seed cannot do that. You need to add some complications/additional randomness (I think ssh or pgp will use concurrent system events to do this) -- which then excludes using a simple seed to reproduce the message key elsewhere (which is why a ssh/pgp key is longer than 8 bytes).
    Last edited by MK27; 03-12-2010 at 12:17 PM.
    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

  6. #36
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Mario F.
    But you still will have the pad to deal with. I'm not weakening the security.
    Ah, but that does not mean anything. You see, all stream ciphers behave like one time pads. There is a keystream (a "pad") that is combined with the plaintext (e.g., by XOR). Block ciphers behave similiarly too, except that their "pads" come in blocks.

    So 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). Unfortunately, if you are basing your key selection on a seed, then this means that the number of possible seeds must be no less than the number of possible messages, and the PRNG must co-operate by generating different sequences for each seed.

    But if the number of possible seeds is no less than the number of possible messages, your seeds can potentially be huge, thus negating the benefits of the scheme in the first place.
    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. #37
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Yup. I promised I would think about it and I did.
    I can see now what you guys are telling me. Slap me for not noticing the obvious. Well done.
    Last edited by Mario F.; 03-12-2010 at 12:32 PM.
    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.

  8. #38
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by brewbuck View Post
    It only uses rand() if you don't provide your own key. I did not have a portable source of randomness. In reality, you would generate your own key from a truly random source and use that. Obviously, keys generated by PRNGs are not suitable because the seed is fixed length. But that isn't the point I'm making -- regardless of what key you use, I can easily produce a key that decrypts to any plaintext of my choice. The ability to do that doesn't depend on how secure the key is. If you doubt it, go ahead and generate your own random key -- I can do it regardless.
    Well, anyway, so that you can demonstrate your point to the fullest extent, I've some data for you.
    D5CB20FFEAEDE53CE741DAB3C3AA0713F4DDA2
    It's a small message, but it was going to be. I picked the key by draws from a hat, so it should be sufficiently random.

  9. #39
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by whiteflags View Post
    Well, anyway, so that you can demonstrate your point to the fullest extent, I've some data for you.
    I've found a key! Here it is:

    Code:
    9CEB459180829C1C8220AEDAADCD27779BBAD1
    What happens when you decrypt your ciphertext using this key?
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #40
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by brewbuck View Post
    What happens when you decrypt your ciphertext using this key?
    The hat re-appears.
    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. #41
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Quote Originally Posted by brewbuck View Post
    I've found a key! Here it is:

    Code:
    9CEB459180829C1C8220AEDAADCD27779BBAD1
    You are soo wrong The key is obviously
    Code:
    91A4478CCA8C9759C732B7D2AFC6277095A9D1

  12. #42
    Registered User kryptkat's Avatar
    Join Date
    Dec 2002
    Posts
    638
    Well i wrote a short paragraph, compiled and ran the program, here is the output of my ciphertext.txt file.
    unfortunately the decrypt did not want to work, i tried several times differently, i dont know if i am missing something
    i think i ran in to the same problems.

    what i mean by exposed is that it is plain text even if it is hiding among the safety of the other plausible messages. therefore it is nude.... exposed.

    much better to do with a copy of the key for a reassured confident claim of undoing a one time pad. sure.

    laserlight quote
    Huh? The key is supposed to be secret. A sane attacker who is in possession of the key (and knows the algorithm) would not bother with cryptanalysis. He/she would decrypt the ciphertext immediately. To talk about "a reassured confident claim of undoing a one time pad" in this context is thus rubbish.
    you missed the point. confidence in knowing that is the correct answer not bragging rights.

    Which also makes it, by the way, an excellent deniable encryption method. And it comes with plausible deniability as a bonus.
    got to love that ! meow !

    One time pads are usually implemented by XOR:
    yes the standard one time pad is xor. we were discussing of using a full length size of the text key for vigenere as a one time pad. probably with out the chart reading would work too.

    even an xor pad can be brute forced providing plain text. exposing the message along with a lot more text that has nothing to do with the message or key. even given all the extra it is still broken. what is done with the data is subjective and not relevant to it being broken.

    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.

    As far as I know, historically one-time pads have indeed been broken (ones used by Soviet spies). But that was only because the opponents got hold of the key-books and / or the Soviets reused keys for several messages.
    getting hold of the key books is a valid way of "breaking the one time pad". meow.

    can we refrain from posting "break this" please and stick to the debate. thank you.

    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.

  13. #43
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.
    I think there might be job for you with the US government.
    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. #44
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Three pages explaining this and the cat still didn't get it.
    A gorilla would.

    Consider the following original text: "We will meet in the 22/05/2007 and destroy the world at 12:05". After encryption, there's nothing you can do to successfully decrypt this without the key. All dates and times will be possible results in your decryption attempts. You will not know which one is true, unless you acquire that information outside the context of the cipher.
    Last edited by Mario F.; 03-14-2010 at 08:02 AM.
    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.

  15. #45
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by kryptkat
    what i mean by exposed is that it is plain text even if it is hiding among the safety of the other plausible messages. therefore it is nude.... exposed.
    Then your definition of "exposed" is useless.

    Quote Originally Posted by kryptkat
    you missed the point. confidence in knowing that is the correct answer not bragging rights.
    I think you missed the point of encryption.

    Quote Originally Posted by kryptkat
    getting hold of the key books is a valid way of "breaking the one time pad".
    It is a valid way of breaking a specific use of encryption. However, it does not constitute breaking an encryption algorithm.

    Quote Originally Posted by kryptkat
    even an xor pad can be brute forced providing plain text. exposing the message along with a lot more text that has nothing to do with the message or key. even given all the extra it is still broken. what is done with the data is subjective and not relevant to it being broken.
    It is not broken. You are inventing your own terminology here.

    The way I see it, using your definitions, there is indeed no encryption algorithm that, in theory, cannot be broken, since by "broken" you mean "can guess the message, even if you can never tell if it is the message". Now, shall the rest of us just go back to using Shannon's definition of perfect secrecy with respect to information theory and leave you wallowing in your own world?
    Last edited by laserlight; 03-14-2010 at 08:18 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

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