Thread: one time pad breakable debate

  1. #1
    Registered User kryptkat's Avatar
    Join Date
    Dec 2002
    Posts
    638

    one time pad breakable debate

    one time pad breakable debate

    conversation moved to general discussion. since one time pad discussion is not part of the contest thread. it should have its own thread.

    if it can be done. then it can be undone. simple mathematics referring to the one time pad. brute force from a-z for example a character only a-z one time pad is where the debate is. that may be guess work to the actual message. once the message is exposed it is broken. much better to do with a copy of the key for a reassured confident claim of undoing a one time pad. sure.

    i understand clearly what you are saying. too many alternative words show up that have nothing to do with the key or the message text.

    'cannot see the wood for the trees'
    by the same token
    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.
    a secure channel ? you can not know for sure ever if the channel is secure. an assumption of reasonable security is made.

    as said already the message exposed along with other words that also make sense that have nothing to do with the key or message when exposed are different than jumbled text that do not make a word. at least with the exposed words you have a place to start applying external intel to what you have to see what fits or makes the most sense as to which message was the real one encrypted. one time pads are breakable. <crash sound>
    Last edited by kryptkat; 03-11-2010 at 03:17 PM.

  2. #2
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    The reason a one time pad cannot be broken is that it can produce a huge amount of semi-valid (as in answers that might appear to valid when read, but actually aren't) decryption answers, and without knowing the actual key used, or parts of what the plaintext should be, you have no way of knowing if you've gotten the correct answer or not.

    a secure channel ? you can not know for sure ever if the channel is secure. an assumption of reasonable security is made.
    Yes you can. A "secure channel" doesn't automatically translate to digital communication. If you for example meet with someone and tell them the key face to face in a place you know isn't under audio surveillance you can be sure that the "message channel" is indeed secure.

    Btw, if you are so convinced one time pads can so easily be broken then here's an exercise for you.
    Code:
    char encrypted[2] = { 45, 16 };
    char key[2] = { ?, ? };
    char plaintext[3];
    	
    plaintext[0] = encrypted[0] ^ key[0];
    plaintext[1] = encrypted[1] ^ key[1];
    plaintext[2] = 0;
    printf("plaintext is '%s'\n", plaintext);
    What is the plaintext? (hint: it's a common 2 letter english word)

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Given any ciphertext encrypted with a one time pad, I can construct a pad which, when used to decrypt the ciphertext, yields a zip file full of child porn.

    It should be immediately obvious than when each ciphertext bit is the product of a plaintext bit with a unique key bit, that the cipher is unconditionally secure. Anyone who thinks otherwise is lacking some basic logic abilities.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    I don't know math and I am still not this krazy. You might get a good batting average for Wheel of Fortune type "common phrases" but there is just no way you could do a couple of paragraphs even once without a warehouse full of mainframes -- for a couple weeks.
    Last edited by MK27; 03-11-2010 at 07:01 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

  5. #5
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Quote Originally Posted by brewbuck View Post
    Given any ciphertext encrypted with a one time pad, I can construct a pad which, when used to decrypt the ciphertext, yields a zip file full of child porn.
    Yes this is what I meant by a semi-valid result. You get a result that might seem valid, ie. a zip file where the crc of it checks out okey and all.. And it is possible that this might have been the unencrypted plaintext but it is impossible to know for sure.

  6. #6
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Which also makes it, by the way, an excellent deniable encryption method. And it comes with plausible deniability as a bonus.
    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. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by MK27 View Post
    I don't know math and I am still not this krazy. You might get a good batting average for Wheel of Fortune type "common phrases" but there is just no way you could do a couple of paragraphs even once without a warehouse full of mainframes -- for a couple weeks.
    It's not a matter of computing power. It is IMPOSSIBLE. For each plaintext bit, there is a key bit. The key bit is not correlated to the plaintext bit. The number of possible plaintexts is equal to the number of keys. Thus, absolutely no information about the plaintext is contained in the ciphertext.

    One time pads are usually implemented by XOR:

    Code:
    ciphertext = plaintext ^ key
    Using algebraic property of XOR, we get:

    Code:
    key = ciphertext ^ plaintext
    Thus, for ANY ciphertext, I can construct a key, which when applied to the ciphertext, yields an arbitrary plaintext.

    The proof is not dependent on XOR. So long as the number of key bits is equal to or greater than the number of plaintext bits, the cipher cannot be broken. Period.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by brewbuck View Post
    One time pads are usually implemented by XOR:
    Okay Well what I meant is that with a warehouse full of mainframes for a few weeks you could generate all the possible keys for say a 1000 byte message -- not sure how big 2^8000 is but pretty big. Probably I do not even know the word for a number that big. Actually maybe you could do this on your desktop during this millennium.

    Once you have all the keys all you have to do is narrow down the possibilities.
    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. #9
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    By generating all possible keys (let's agree for now it would be feasible), you are generating all possible permutations to the 1000 byte message. One of those keys will result in an excerpt of War & Peace, another in a rather lengthy laundry list.

    And one of them will contain the repeated phrase "This cipher can't be broken!".
    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.

  10. #10
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by MK27 View Post
    Okay Well what I meant is that with a warehouse full of mainframes for a few weeks you could generate all the possible keys for say a 1000 byte message -- not sure how big 2^8000 is but pretty big. Probably I do not even know the word for a number that big. Actually maybe you could do this on your desktop during this millennium.

    Once you have all the keys all you have to do is narrow down the possibilities.
    You cannot narrow down the possibilities when the set of possibilities is, literally, the set of all possible strings of length N. Any string of length N could have been the plaintext, and a key exists for each such string.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    So my computer's whole millennium would be for nought, is what you are saying.
    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

  12. #12
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by MK27 View Post
    So my computer's whole millennium would be for nought, is what you are saying.
    You would find every valid-looking plaintext that can be formed from N bits. Among all the brute force decryptions, one of them would be correct, but there is no way of knowing which of the valid-looking decryptions is correct.

    Going back to _Mike's example, I have a two-letter word. The ciphertext is 0xA109. What's the plaintext? Surely an exhaustive search of 65536 possibilities should take only a fraction of a second.

    One thing that will pop out is "in". Another thing that will pop out is "up". Another thing that will pop out is "an". Also, "it", "if", "hi", "as".... Which one is the proper decryption? You can't tell. The only way to know is by knowing the true key. This is what we mean by "unbreakable." Even brute force doesn't work.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Sure but -- this is just conjecture -- I bet the number of valid english words included in that 65536 combinations, as a ratio, is much higher than the ratio of grammatically valid, rationally coherent/meaningful messages you could fit into 1000 ascii bytes vs. the 2^8000 possibilities -- a number which in my math ignorance I think has at least several hundred digits.
    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. #14
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Let's just make it abundantly clear, ok? Here's a one-time-pad encryption program:

    Code:
    /* otp.c -- one time pad
     *
     * Usage:
     *
     * To encrypt a file 'data.txt' using 'key.txt', writing output to 'out.txt':
     *   opt -encrypt data.txt out.txt key.txt
     *
     * To decrypt a file 'cipher.txt' using 'key.txt', writing output to 'out.txt':
     *   opt -decrypt cipher.txt out.txt key.txt
     *
     * To encrypt a file 'data.txt' using a randomly generated key, writing output
     * to 'out.txt' and the key to 'key.txt':
     *   opt -encrypt data.txt out.txt
     *
     *
     * Example, which first encrypts, then decrypts:
     *   opt -encrypt data.txt out.txt
     *   opt -decrypt out.txt decrypted.txt key.txt
     */
    
    #include <stdio.h>
    #include <stdlib.h>
    
    void puthex( int c, FILE *fp )
    {
        static const char hexdigit[] = "0123456789ABCDEF";
        fputc( hexdigit[ c >> 4 ], fp );
        fputc( hexdigit[ c & 15 ], fp );
    }
    
    int gethex( FILE *fp )
    {
        int c = 0;
        int h;
        h = fgetc( fp );
        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 );
        h = fgetc( fp );
        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;
    }
    
    int main( int argc, char **argv )
    {
        int i;
        int doDecrypt = 0;
        int doCreateKey = 0;
        const char *inFilename = NULL;
        const char *outFilename = NULL;
        const char *keyFilename = NULL;
        FILE *inFile;
        FILE *outFile;
        FILE *keyFile;
    
        if( argc < 4 )
        {
    	fprintf( stderr, "Usage error: See source file for usage.\n" );
    	exit( 1 );
        }
        if( strcmp( argv[ 1 ], "-decrypt" ) == 0 )
    	doDecrypt = 1;
        if( doDecrypt && argc < 5 )
        {
    	fprintf( stderr, "Usage error: See source file for usage.\n" );
    	exit( 1 );
        }
        inFilename = argv[ 2 ];
        outFilename = argv[ 3 ];
        if( !doDecrypt && argc < 5 )
        {
    	keyFilename = "key.txt";
    	doCreateKey = 1;
        }
        else
    	keyFilename = argv[ 4 ];
    
        inFile = fopen( inFilename, "rb" );
        outFile = fopen( outFilename, "wb" );
        if( !doCreateKey )
    	keyFile = fopen( keyFilename, "rb" );
        else
    	keyFile = fopen( keyFilename, "wb" );
    
        if( !doDecrypt )
        {
    	int c1, c2;
    	for( ; ; )
    	{
    	    c1 = fgetc( inFile );
    	    if( c1 == EOF )
    		break;
    	    if( doCreateKey )
    	    {
    		c2 = rand() & 0xFF;
    		puthex( c2, keyFile );
    	    }
    	    else
    		c2 = gethex( keyFile );
    	    if( c2 == EOF )
    	    {
    		fprintf( stderr, "Key data is not long enough.\n" );
    		exit( 1 );
    	    }
    	    c1 ^= c2;
    	    puthex( c1, outFile );
    	}
        }
        else
        {
    	int c1, c2;
    	for( ; ; )
    	{
    	    c1 = gethex( inFile );
    	    if( c1 == EOF )
    		break;
    	    c2 = gethex( keyFile );
    	    if( c2 == EOF )
    	    {
    		fprintf( stderr, "Key data is not long enough.\n" );
    		exit( 1 );
    	    }
    	    c1 ^= c2;
    	    fputc( c1, outFile );
    	}
        }
        fclose( inFile );
        fclose( outFile );
        fclose( keyFile );
        return 0;
    }
    Please write a paragraph of text. Place this into "plaintext.txt". Then run:

    Code:
    otp -encrypt plaintext.txt ciphertext.txt
    This will auto-generate a key into "key.txt". Do NOT tell me the key. Verify that the key works by doing:

    Code:
    otp -decrypt ciphertext.txt out.txt key.txt
    The contents of "out.txt" should match "plaintext.txt".

    Then, post the contents of "ciphertext.txt" here, and hopefully I can demonstrate what I'm talking about.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by kryptkat
    if it can be done. then it can be undone. simple mathematics referring to the one time pad.
    That is obvious and true, if you possess the one time pad (i.e., the key).

    Quote Originally Posted by kryptkat
    brute force from a-z for example a character only a-z one time pad is where the debate is. that may be guess work to the actual message.
    That would be useless guess work, since every unit of the ciphertext depends on a unit of the key that is independent of all other units.

    The only useful guess work is to guess the message given the length of the ciphertext. But this guesswork requires a great amount of external knowledge, to the point where one might even be able to deduce the message without the ciphertext, which would imply that the encryption was not useful in the first place.

    Quote Originally Posted by kryptkat
    once the message is exposed it is broken.
    The problem is, the message cannot be exposed, because it is hiding in safety among the other plausible messages.

    Quote Originally Posted by kryptkat
    much better to do with a copy of the key for a reassured confident claim of undoing a one time pad. sure.
    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.


    Please refer to the original discussion in order to see what kryptkat has already been told.
    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