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; Originally Posted by laserlight EVOEx: when you talk about cryptanalysis, are you are talking about the use of MK27's proposed ...

  1. #106
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by laserlight View Post
    EVOEx: when you talk about cryptanalysis, are you are talking about the use of MK27's proposed RNG to generate a keystream, and then to cryptanalyse the resulting ciphertext to reason if the keystream constitutes a one time pad?
    I'm talking about brute forcing a text that generates a keystream to decode a captured message. If both the initial text used to get the random numbers and the decryption using this key make sense, you know you've broken the encryption.
    Which, of course, is impossible for actual random pads.

  2. #107
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by EVOEx View Post
    The trick is that you can actually KNOW when you have the proper key as both the input text as the decrypted text make sense. If that is true, you can be fairly sure you have the right combination, even though it is fairly unlikely you will find this using this algorithm.
    Alright, here's what I see as your point, which at first glance is sort of feasible. This is the scrambled text, byte values for a 5 letter word:
    41 211 90 7 146
    All you have to do is find a 30 character "sensible" text that could generate a 30 bit key according to the known algorithm, %2, whereby that key will produce a five letter word and bingo -- that's gotta be it.

    Wrong.

    If you have a key that generates a meaningful message, it would be easy to take that bit pattern and generate a corresponding text for it (you have 13 choices each time -- actually with punctuation and capitals, lets say you have 30 choices each time). Chance are you could do that with a message of any length. Going back to the five letter word, using modulus how many 30 character phrases could you come up with that would produce the "key" to produce a word from 5 scrambled bytes? The same number of phrases as there are possible keys, and most likely, even more than that, since just one such bit sequence could be produced by a whole bunch of possible word combinations.

    So it will not help -- very likely all 2^(8n) possible keys could be turned into meaningful key generating texts. This is because of the "irreversible reduction" involved.

    What's more, using text was only a suggestion -- the algo would work with garbage data too.
    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

  3. #108
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    Unless it is feasible to guess the key source text.
    Now you are proposing kryptkat's solution, since the source text would be synonymous with the key. It is not feasible to "guess" the text, you would have to gain possession of it. That's cheating!
    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. #109
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,660
    Quote Originally Posted by MK27
    Now you are proposing kryptkat's solution, since the source text would be synonymous with the key. It is not feasible to "guess" the text, you would have to gain possession of it. That's cheating!
    It is not cheating if you can determine that certain sets of text are much more likely to be used than others. It is only a one time pad if the pad is used once.
    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

  5. #110
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    It is not cheating if you can determine that certain sets of text are much more likely to be used than others. It is only a one time pad if the pad is used once.
    The pad would only be used once.* One of the "statistics" thrown about Queens, where I live, is that there are more than 200 languages actively used by the residents. I presume these all have written forms and potentially ascii-ish forms too (if not, it could be accommodated); maybe we can rule out the ones that that use pictograms.

    That's a lot of available text. I don't have to read or understand it -- my suggestion about using it was just to save time typing, etc. Plus, you can now take your (effectively) randomly chosen chunk of text and randomly choose a language to google translate it into. That will be even better, since the key text is less likely to make sense.

    * someone else could by coincidence use the same one, but the same is true no matter how you generate it (it could have been used before).
    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. #111
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,660
    Quote Originally Posted by MK27
    I presume these all have written forms and potentially ascii-ish forms too (if not, it could be accommodated); maybe we can rule out the ones that that use pictograms.
    Unicode.

    Quote Originally Posted by MK27
    The pad would only be used once. (...) That's a lot of available text.
    The problem is that the sets of text are not all equally likely to be chosen by a given user. Recall why brute force can be effective in practice against hashed passwords (where a salt is not used): users tend to choose weak passwords for convenience, and these passwords are thus susceptible to a dictionary attack.

    Now, in practice these text are more like passphrases rather than passwords (though the distinction is largely just a matter of style, in my opinion), thus brute force is likely to fail anyway. Yet, just as users reuse passwords, they may reuse source text. Training them not to do so is easier said than done; even trained spies blunder.
    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

  7. #112
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by MK27 View Post
    So it will not help -- very likely all 2^(8n) possible keys could be turned into meaningful key generating texts. This is because of the "irreversible reduction" involved.
    Actually, very few combination of letters actually form something meaningful. Especially if the texts become longer. Try it; type 10 random characters and see how many make sense. The longer the text, the less combinations will make sense.
    Especially if it takes context into account.

    Given a long text, how many combinations make sense? Not a lot. And in how many cases will both the decrypted and the input text makes sense? My bet: 1.

  8. #113
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by EVOEx View Post
    Actually, very few combination of letters actually form something meaningful. Especially if the texts become longer. Try it; type 10 random characters and see how many make sense. The longer the text, the less combinations will make sense.
    Especially if it takes context into account.

    Given a long text, how many combinations make sense? Not a lot. And in how many cases will both the decrypted and the input text makes sense? My bet: 1.
    Arrgggh -- EVOEx, are you the kind of person that when you reach a T junction with this sign, you habitually turn left and are baffled by the oncoming traffic?

    You are not dealing with 10 random characters, you are dealing with ten random bits:

    1011101100

    Each of which could be any one of thirteen letters (let's ditch punctuation and spaces) -- I think you will find there is more than one possibility for any bit sequence. So there will always be a "meaningful" correspondence. You cannot reduce the number of possible keys this way...you will cause an "accident".
    Attached Images Attached Images  
    Last edited by MK27; 03-16-2010 at 04:05 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

  9. #114
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,439
    I'm still not sure what there is to debate about MK's idea. It may not be your traditional approach to randomness. But I cannot see how it is any less efficient.

    I think we are rapidly approaching a concept of randomness no one here is in any position to prove or disprove. Patterns inside a randomly chosen key, do not remove the random nature of the key. Is a randomly picked phrase in War & Peace less random because we can actually read the text? Should a PRNG previously calculated distribution be reviewed because once we drew 7 numbers and they came up as 1234567?

    A pad only requirement is that it is truly random. This means what it means. An effective key can indeed be Chapter II of War & Peace in the Ukranian language and with gross translation errors, unless this choice can be traced. A system that renders text to a completely unrelated one-way binary representation is not better or worse.

    The problem for anyone trying to break a one-time pad is not finding the key. Is finding the relevant original text among the near infinite number of possible matches.
    Last edited by Mario F.; 03-16-2010 at 05:43 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.

  10. #115
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    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.
    No, this is wrong. You're relying on a human to be random. If humans were adequately random, brute force dictionary attacks would not work.
    Quote Originally Posted by MK27 View Post
    You are not dealing with 10 random characters, you are dealing with ten random bits:

    1011101100

    Each of which could be any one of thirteen letters.
    This is irrelevant. We're not concerned with finding the text used to produce the ten random bits. We're only concerned with finding the ten bits. In this case, see above.

    Humans are not random.
    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

  11. #116
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,439
    Quote Originally Posted by pianorain View Post
    No, this is wrong. You're relying on a human to be random. If humans were adequately random, brute force dictionary attacks would not work.
    He said randomly type on the keyboard.

    Here's a challenge:
    Type randomly on your keyboard for 30 seconds fast and furiously with all your fingers from both hands... Done?
    Now, do it again. Wake me up in 20 or 30 years when you finally match the exact same sequence of characters.

    This is irrelevant. We're not concerned with finding the text used to produce the ten random bits. We're only concerned with finding the ten bits. In this case, see above.
    nope. You are interested in finding the solution to the cipher. Not in finding the key. Or better, your only hope to break a One-time Pad is trying to decipher the cipher. Not trying to find the key.
    Last edited by Mario F.; 03-16-2010 at 05:56 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.

  12. #117
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote Originally Posted by Mario F. View Post
    He said randomly type on the keyboard.
    Wait, did you just say "use a human as a PRNG"? Humans are not random.

    Quote Originally Posted by Mario F. View Post
    Here's a challenge: Type randomly on your keyboard for 30 seconds fast and furiously with all your fingers from both hands... Done?

    Now, do it again. Wake me up in 20 or 30 years when you finally match the exact same sequence of characters.
    Fortunately, I don't have to match the exact same sequence of characters. I only have to match the last bit of each character.

    Take a look at the ASCII keyboard under this scenario:
    Code:
    1 1 1 0 0 1 1 1 1 0
     1 1 0 0 1 0 0 1 0
      0 0 1 0 0 0 1
    I hope I don't "randomly" draw all my characters from the Q row. That's a lot of 1's. Using the Z row isn't a good idea either - lots of 0's.

    The theoretical argument is simple; other people have been covering that. So, I wrote a quick program to compare a single "key" against my other random tries. So far, an average of 52 out of 59 bits are the same; my range of "same bits" is 50-53. This is with me furiously pounding keys on the keyboard. Of course, this is a small sample but I think it illustrates the point. Humans are not random.
    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

  13. #118
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,439
    Quote Originally Posted by pianorain View Post
    Wait, did you just say "use a human as a PRNG"? Humans are not random.
    Really? Prove it. If you can, you just did science a big favor and answered one of the fundamental questions of humanity. Nobel Prize will be too little for you. Meanwhile, you may as well have proven we live in an entirely deterministic universe and the quest for randomness is forever a wild goose chase.

    Fortunately, I don't have to match the exact same sequence of characters. I only have to match the last bit of each character.

    Take a look at the ASCII keyboard under this scenario:
    Code:
    1 1 1 0 0 1 1 1 1 0
     1 1 0 0 1 0 0 1 0
      0 0 1 0 0 0 1
    Erm... I don't think you understood MK's algorithm.
    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.

  14. #119
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote Originally Posted by Mario F. View Post
    Erm... I don't think you understood MK's algorithm.
    It seems to be emphatically stated many times.
    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.
    Quote Originally Posted by MK27 View Post
    Look at a paragraph of text as an odd-even (binary) sequence based on ascii values. Every character transformed to 0 or 1. You are now looking at truly random natural data.
    Quote Originally Posted by MK27 View Post
    Here is the alphabet:

    10101010101010101010101010101010
    Indeed, I doubt even MK27 understands his algorithm, considering in one place he says "random text" and yet:
    Quote Originally Posted by MK27 View Post
    The best idea would be to just type words (the space character is even, but all the vowels are odd).
    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

  15. #120
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,439
    No. Not that type of understanding. But what his algorithm means.

    Again, what are the only two requirements for the pad? Be the same size or larger than the cipher and be entirely random. Exactly how do you plan to convince me a pad made up of random set of bits is not going to serve ours purposes?

    You can argue, because those bits are being constructed from a binary alphabet representation of well-known characters? More, you can then follow on with "and the pad represents some unknown text". So what you have in fact is a pad that is a cipher that shows 1s and 0s created from some unknown text that can in fact have been randomly generated, or not.

    So how do you propose to solve the cipher that will give you the correct pad?

    EDit: Oh, and remember: That keyboard you draw... that's the key. But you don't know the key. So you can't draw it as you did. So, again how do you plan to decipher the pad?
    Last edited by Mario F.; 03-16-2010 at 07:32 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.

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