Thread: one time pad breakable debate

  1. #16
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    post the contents of "ciphertext.txt" here, and hopefully I can demonstrate what I'm talking about
    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 but every time the key length error came up so i could not test that.
    Strangely the first time i ran it the decrypt executed but the out file just looked like another key, then it would not work again after that. if its my usage thats at fault go ahead with the sample cipher below, or let me know what you think i doing wrong and i will go again.

    5D4CDBEA850DB5CF3EFC2C9885D38C99DBC7B55BF3645BF145 30696F63C332AEDC603DBA26C8F8D2776628186D5044713AA1 BB9EE38131547D62E77E74BEC25746EE388F2E1C4594762C5D 90EA152CA9C32660862B3013A40AA751DB5E5ED34D984AFEF1 85FB6DBFC3B9ED6ADC00F82D44EF12A1FBA09DF4DD84BDA535 C608A3CB66B7105EBAEB14E28C36250D8B01FD0EB8B676E9F3 651D1F83729EE126240367A58658403FB2AB676A471CFB7595 A7B1EABAC53B1250BB5D5695A7AAA7F8482BB2E31992B17844 91AF904E0CF5EF216D3E3C6CB113EFDF186E7F724847E17371 13F9AE0C31A9C3E0470B608C32056AF91D7AB1735D0E0FBC83 222BBE331B1F9E73D477D9C641FD179726

  2. #17
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #18
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by anon
    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.
    That is why I stated that "the main problem concerning the use of a one time pad is key management".

    EDIT:
    Oh, and besides problems with key distribution, usage and storage, there's also the problem of key generation: the keys really must be random.
    Last edited by laserlight; 03-12-2010 at 09:42 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

  4. #19
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Yeah I can probably crack some of brewbuck's keys just because he didn't seed rand.

  5. #20
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472

    .

    Quote Originally Posted by whiteflags View Post
    Yeah I can probably crack some of brewbuck's keys just because he didn't seed rand.
    haha, yeah, i did notice ciphers generated were strangely identical
    Last edited by rogster001; 03-12-2010 at 10:13 AM.

  6. #21
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by laserlight View Post
    Oh, and besides problems with key distribution, usage and storage, there's also the problem of key generation: the keys really must be random.
    Which, if done for computer purposes, does remove most concerns regarding key distribution and storage. The "key" can be as simple as a long integer.
    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.

  7. #22
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Mario F.
    Which, if done for computer purposes, does remove most concerns regarding key distribution and storage. The "key" can be as simple as a long integer.
    You still have a key distribution problem: if you use public key encryption to establish a secure channel, then breaking the public key cryptosystem (or the protocol, or its implementation, if they are flawed) would break your scheme. Key storage is probably less of a problem for computers, yes, but if your key is a single long integer, you only can encrypt a message equivalent to a single long integer.
    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

  8. #23
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Mario F. View Post
    Which, if done for computer purposes, does remove most concerns regarding key distribution and storage. The "key" can be as simple as a long integer.
    So the key would be the "random seed"? That makes the actual key much much much more predictable, since rather than 2^8000 possibilities for a 1000 byte message, you now have only LONG_INT_MAX possibilities, for a message of any length.

    That would be extremely simple simple to crack. Just using rand() in a naive way to generate a key will defeat most of the purpose.
    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

  9. #24
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    So the key would be the "random seed"?
    No, that would not make a one time pad. If you use a cryptographically secure PRNG it may still be rather secure, but it will not be a one time pad and thus will not have the theoretically unbreakable property of a one time pad.
    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

  10. #25
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    No, that would not make a one time pad. If you use a cryptographically secure PRNG it may still be rather secure, but it will not be a one time pad and thus will not have the theoretically unbreakable property of a one time pad.
    Okay, but that is what brewbuck's method boils down to -- it is the sequence used by your random number generator, which is not very secret. Even if you seeded it, the number of message length keys this could produce is limited to LONG_INT_MAX.

    Cracking something that simple would be -- simple.
    Last edited by MK27; 03-12-2010 at 10:51 AM.
    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. #26
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    Okay, but that is what brewbuck's method boils down to -- it is the sequence used by your random number generator, which is not very secret.
    I suppose you can provide your own key.txt that contains key that is properly randomly generated. Note that it is not about the secrecy of the PRNG: even if you use the NSA's best cryptographically secure PRNG that no one outside of the NSA knows, the resulting key would not constitute a one time pad simply because the seed has less information than the 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

  12. #27
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    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

    So the seed is just another layer of security, if you will. And a more convenient way of transporting the key.

    Quote Originally Posted by MK27
    So the key would be the "random seed"? That makes the actual key much much much more predictable, since rather than 2^8000 possibilities for a 1000 byte message, you now have only LONG_INT_MAX possibilities.
    Only if you know the RNG.
    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.

  13. #28
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Mario F. View Post
    Only if you know the RNG.
    That is the "only" only to which I referred. So all you have done is shifted the problem of key storage and security around -- it is now a question of RNG storage, usage, distribution, and security.
    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. #29
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Note really MK. It would be sensible to store the RNG with the decryption algorithm. There's thus no added concerns past those you had without it. And I just removed out of the equation any concerns regarding they key storage.

    You may ask why I would want to do that. For no particular reason, really. Just outlying that key distribution and storage can be simplified down to a long integer without it needing be a "document" the same size or larger as the cipher.
    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. #30
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    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.

    If you guys are saying that it's not decrypting properly, then the "trick" I was going to demonstrate isn't going to work... What exactly are the commands you are using? The following should be working:

    Code:
    otp -encrypt plaintext.txt ciphertext.txt
    otp -decrypt ciphertext.txt out.txt key.txt
    If out.txt isn't looking like plaintext.txt then something's wrong. I tested this thing pretty extensively before posting it.

    The gethex() function only allows upper case hex digits. If there are spaces or other characters in your key, it will mess up the input. If that's the case, try replacing the gethex() function with this one, which is more tolerant (at least tolerant to whitespace):

    Code:
    int gethex( FILE *fp )
    {
        int c = 0;
        int h;
        do
        {
            h = fgetc( fp );
        } while( isspace( h ) );
        if( h == EOF )
    	return EOF;
        if( h >= '0' && h <= '9' )
    	c += 16 * ( h - '0' );
        else if( h >= 'A' && h <= 'F' )
    	c += 16 * ( h - 'A' + 10 );
        do
        {
            h = fgetc( fp );
        } while( isspace( h ) );
        if( h == EOF )
    	return EOF;
        if( h >= '0' && h <= '9' )
    	c += h - '0';
        else if( h >= 'A' && h <= 'F' )
    	c += h - 'A' + 10;
        return c;
    }
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

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