Thread: one time pad breakable debate

  1. #76
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    It is easy to see how there are patterns of letters, and even meta-patterns of such patterns in phrases, etc, and it is exactly for that reason that there can be no patterns in the sequence reduced to binary.
    I note that your original assertion included "random" keyboard banging. Do you still include that, or do you now believe that the input should be restricted to natural language text?

    Quote Originally Posted by MK27
    I am again asserting that language amounts to a natural phenomenon (like radiation) and considered this way specific instances of it are reduced to true chaos -- they can no longer be meaningful, predictable, or patterned, because what made them meaningful/predictable/patterned (26 characters) has been reduced out.
    I think that this is where my doubt lies: is this assertion a self-evident statement of fact, or is it just an unproven hypothesis?

    But let's move on: suppose I wanted to test this statement. What do you propose is the best way for me to obtain the data and convert it to a byte array such that it can be checked with a statistical test of randomness?

    Quote Originally Posted by MK27
    Given sufficient apparatus, context, and knowledge (like a knowledge and appartus we probably do not posses, and it would be absurd) the decay you observe could easily be 100% predicable down to the individual atom.
    If I remember correctly, this is debatable, and physicists tend to be in favour of the proposition that it is the case that it is physically impossible to make such a prediction, regardless of the technical knowledge and apparatus available. Unfortunately, the actual physics discussion is somewhat beyond me.
    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. #77
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    I note that your original assertion included "random" keyboard banging. Do you still include that, or do you now believe that the input should be restricted to natural language text?
    Either one will be fine, since while it would be hard to avoid going "asdf" a few times, it will not be hard to avoid going "asdfgherlanaienwnfuxcbebwnmwifvnnmgke" more than once, I think. I added the bit about just using normal language when I realized it would work just as well because of the reduction from base 27 (letters + space) to base 2 completely removes any pattern which existed in base 27.

    I think that this is where my doubt lies: is this assertion a self-evident statement of fact, or is it just an unproven hypothesis?
    It is deductive as opposed to inductive/empirical, but even in science many or most "ideas" are: just that you may want to prove something empirically as well. In this case, I think that will be unnecessary because it could be proven mathematically -- generally in science, mathematical (ie, deductive) proof I think is taken to be as good or better than empirical proof (which you could prove this empirically as well).

    IMO, a sane and rational person should not have to do either one here unless they are irrationally paranoid (IMO, I am baffled this provoked a discussion -- it seems like discussing "Could 2+2 really be 4, or might it be something else?"). It is on a level with saying, because I have never played the lottery, I am uncertain that the odds are really against me. No. Simple contemplation indicates this, even if you too lazy to "explicitly demonstrate it mathematically".

    But let's move on: suppose I wanted to test this statement. What do you propose is the best way for me to obtain the data and convert it to a byte array such that it can be checked with a statistical test of randomness?
    Any way. Apply it to the dictionary. Apply it to this thread. Neither one will contain any statistically meaningful frequency of predicable patterns. 2+2=4.

    If I remember correctly, this is debatable, and physicists tend to be in favour of the proposition that it is the case that it is physically impossible to make such a prediction, regardless of the technical knowledge and apparatus available.
    That hinges on your acceptance of the irreducibility of the Uncertainty Principle, I would guess. Einstein, eg, did not and felt that the "Uncertainty Principle" had a limited lifespan, ie, all events are ultimately determinate. I do not have enough interest in physics to say whether the Uncertainty Principle is accepted pragmatically or if there is some real evidence to prove that the location of an electron really is indeterminate from one moment to the next -- but I would guess the former ("uncertainty" is just accepted pragmaticlly), so I am banking a little bit that in the future all events on an atomic level could be predicted. But that is kind of red herringish, I believe what's really important there is that:

    even given predictability, the event which generated the sequence (an actual decay event) cannot be "deduced" or assumed like: if I have a segment of the data, I can tell you the rest of it without witnessing the event. Nope! The matter is gone! The same thing: given a segment of the 1 and 0 from a string, I can tell you the rest of the string. Nope! The "matter" is gone!
    To clarify: even if the entire sequence of data is based on 100% predicable phenomenon, without the phenomenon, you could not say (based on a few seconds of decay data) what happened during the rest of the time because you do not have the matter (which decayed, producing the data) to examine. In the same way, given part of the bit sequence created from a text, you could not say what the rest of the text was, so you certainly could not say what the rest of the bit sequence was. The same few seconds of decay data could probably be produced by quite different decay events, just like the same sequence of bits could be produced by very different texts. The conversion is highly reductive and therefore irreversible.

    Anyway, sorry if I have been a bit rude or curt to anyone, but I kind of think that is okay when "discussing" whether 2+2 equals 4. Most people would not entertain that for very long before they assert that:

    1) 2+2=4
    2) You are silly to believe anything else. Stop it, now.
    Last edited by MK27; 03-16-2010 at 11:34 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

  3. #78
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    MK27, MK27, MK27...
    I agree that in the hypothetical situation that you can figure out all information of the smallest particles that exist of which we don't even yet know they exist. Of course, this is only possible in the hypothetical case that the uncertainty principle (which, yes, is accepted generally, although I, too, doubt it will hold for the smallest of particles) is false.
    So maybe, in a couple of hundred years, we are able to predict the future output of such a random number generator based on decay.
    Another question is whether we can ever calculate what happened back in time. I doubt it, as multiple events produce the same output, probably.
    The only reason I can see the "decay" RNG would be broken is that in the far future we can decide the *future* output of it. So it needs to be in the hands of someone who wants to break your data *before* you send it. In this hypothetical situation.

    About your key generation algorithm, were it based on an actual text, you could brute force it by going through several words of the dictionary, string them together, decrypt the data with that and see if it produces anything that is sensible. It's not easy to brute force, but you'll definitely know when you've cracked it, as both the output and the key will make sense.
    The same holds - a bit - when the input is the result of hitting the keyboard randomly. Because humans suck at producing anything random (fact), even this "random" input will "look" right.
    In contrast with "proper" key generation algorithms, the key is completely senseless and thus there is nothing to brute force to actual make sense.

  4. #79
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    IMO, a sane and rational person should not have to do either one here unless they are irrationally paranoid
    Sometimes, security experts or wanna-be experts do seem irrationally paranoid to normal people

    But there are good reasons to use empirical tests: if the tests fail despite being correct, then it can reveal a mistake in the theory, or something that needs to be accounted for in practice, e.g., the random distribution, a straightforward implementation that turns out to be a non-obvious mistake, etc. This is why I say that implementations that use even widely accepted sources of "true" randomness are still tested.

    Passing a battery of tests does not prove that the RNG is suitable for use in a one time pad, but it does lend some supporting evidence.

    Quote Originally Posted by MK27
    It is on a level with saying, because I have never played the lottery, I am uncertain that the odds are really against me.
    I regard as more like: because I do not know the rules of the lottery, I am uncertain that the odds are really against me.

    Quote Originally Posted by MK27
    I do not have enough interest in physics to say whether the Uncertainty Principle is accepted pragmatically or if there is some real evidence to prove that the location of an electron really is indeterminate from one moment to the next -- but I would guess the former ("uncertainty" is just accepted pragmaticlly)
    It depends on what you mean by "pragmatically", but the undergraduate physics that my university teaches at cross-faculty level holds that there is "real evidence".
    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. #80
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by EVOEx View Post
    Another question is whether we can ever calculate what happened back in time. I doubt it, as multiple events produce the same output, probably.
    Yes, I said exactly the same thing; this is why you still need the event to "predict" the data. Like I also said, you have to read and comprehend at the same time, otherwise you are stuck making moot points Just admit you have made a mistake of interpretation here and be done with it.

    Quote Originally Posted by EVOEx View Post
    About your key generation algorithm, were it based on an actual text, you could brute force it by going through several words of the dictionary, string them together, decrypt the data with that and see if it produces anything that is sensible. It's not easy to brute force, but you'll definitely know when you've cracked it, as both the output and the key will make sense.
    Wrong. You are now repeating kryptcat's argument. Here is a five bit sequence:

    11011

    Please tell me what word formed it. Guess what: there is more than one possibility and you have NO CHANCE of determining which one it is. Largely because of that, your guess will have exactly ZERO VALUE in determining the meaning of the sequence.

    In essence, and in fact, the text is a one time pad key to the bit sequence, and because of that fact, you will not be able to break it using brute force or any other method.
    Last edited by MK27; 03-16-2010 at 12: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

  6. #81
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by MK27 View Post
    Yes, I said exactly the same thing; this is why you still need the event to "predict" the data. Like I also said, you have to read and comprehend at the same time, otherwise you are stuck making moot points Just admit you have made a mistake of interpretation here and be done with it.



    Wrong. You are now repeating kryptcat's argument. Here is a five bit sequence:

    11011

    Please tell me what word formed it. Guess what: there is more than one possibility and you have NO CHANCE of determining which one it is. Largely because of that, your guess will have exactly ZERO VALUE in determining the meaning of the sequence.

    In essence, and in fact, the text is a one time pad key to the bit sequence, and because of that fact, you will not be able to break it using brute force or any other.
    Of course you can't know. Just like frequency analysis is useless...
    In small texts.
    But larger texts make it possible what I - and apparently kryptcat - said.

  7. #82
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    I regard as more like: because I do not know the rules of the lottery, I am uncertain that the odds are really against me.
    Almost akin to arguing about whether the sky is blue then finally going "Oh, you mean that sky"...what do you think the rules/odds are? In general? More silliness laserlight

    It depends on what you mean by "pragmatically", but the undergraduate physics that my university teaches at cross-faculty level holds that there is "real evidence".
    I'll take your word for that -- I don't know.
    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

  8. #83
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by EVOEx View Post
    But larger texts make it possible what I - and apparently kryptcat - said.
    Well, at least kryptcat has someone else on side now. Unfortunately you are both still wrong.
    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. #84
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    I'll take your word for that -- I don't know.
    And I have to take the word of my lecturers as I don't know what they really teach at higher levels

    Quote Originally Posted by MK27
    Well, at least kryptcat has someone else on side now.
    No, frequency analysis is useless against a one time pad.

    But now the argument becomes a little clearer: if your argument rests on the assertion that "the text is a one time pad key to the bit sequence", then key management automatically becomes a practical problem, e.g., if users have a tendency to enter or otherwise pick common text, then the method fails.
    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. #85
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by MK27 View Post
    Well, at least kryptcat has someone else on side now. Unfortunately you are both still wrong.
    So tell me why my argument is wrong for long texts. I'm not going to take your word on this.

    I'm not saying it's easy. It's going to take a lot of brute forcing and analysis to decide whether texts make sense... But don't you agree that if two texts make sense you know you've cracked the encryption?

  11. #86
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by EVOEx View Post
    Because humans suck at producing anything random (fact), even this "random" input will "look" right.
    I cannot believe this is what is blinding you here. You are totally out of context; I have already explained that 3-4 times.

    If I dissolved your body in acid, allowed the remains to solidify, and used radioactive decay, would that data be "less random" because a human produced it?

    Think again about what I am talking about. Here is part of this post converted with:
    Code:
    for (i=0;i<strlen(str);i++) printf("%d", str[i]%2);
    10110010001011010001101101010011000100101011100101 00011101010010100101100100110010000010010011110010 01110001010100111000100111000010011110100101101010 10010001110001011110101001111001110000010001010010 00111001001100011111101001110000101110010100010101 1110010110010100101100010111010*

    Now, there are "non random" patterns in the event -- in fact it is not random at all, it is actual meaningful text. This is what I meant about the radioactive decay event -- which could be something that is totally predictable and full of meaningful, information rich patterns, but also produce random data of a given sort.

    Why this is so

    It may be hard for humans to avoid repetition in conscious acts and thus we are bad at producing random data. However, it would be very hard EVEN INTENTIONALLY to produce repeated patterns in a bit sequences converted one to one from characters in some text you type, while still using a meaningful sequence of words (ie, you can't go "word word word word" -- you must construct a sentence). Since it will be very difficult just to produce any pattern at all after conversion, I promise: it will be literally impossible to do it by accident. This is what I mean by "out of context".

    *for some reason this appeared with spaces in it...
    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. #87
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by EVOEx View Post
    But don't you agree that if two texts make sense you know you've cracked the encryption?
    No. This is the one time pad debate, and as far as we have been able to determine, kryptcat is the only person on Earth who thinks it is breakable. So you don't have to take my word on that -- google.

    Long or short text -- it does not matter. The key is the same length as the text. It contains no determinate repeating patterns (the text does). All you can do is assert that some part of it, eg:

    1

    Must be (assuming lower case ascii) one of acegikmoqsuwy, and not one of bdfhjlnprtvxz. And so on. With say 500 digits, you have now 13^500 possibilities. Punch "13^500" into your calculator. Trying to determine the inputed data for the key is going to be even harder than just trying all possible keys (2^500* -- still a ridiculously huge number). Even when your computer is done brute forcing the possibilities (in a few millennia), you will still not be much further along than where you started, vis, reducing them.

    *since the bit key need to be 8X as long as the message text, 500 is not a valid length, but you could have 504 bit key for a 63 byte message.
    Last edited by MK27; 03-16-2010 at 12:33 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

  13. #88
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Just answer this question:
    If we get a meaningful text for which we apply your algorithm to convert it to your key and decrypt an encrypted text with this and we get another meaningful text.... Do you agree that you can be pretty much sure that the meaningful text you started with was what the user entered?

  14. #89
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300

    Lightbulb

    This is actually a pretty good idea -- you do not have to keep the algorithm secret, and you do not need an RNG or a Geiger counter. And you do not have to use real text, any set of character strings at all will do. Just make sure it is not related to the message text. And you will have a truly random key generator.
    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

  15. #90
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by EVOEx View Post
    Just answer this question:
    If we get a meaningful text for which we apply your algorithm to convert it to your key and decrypt an encrypted text with this and we get another meaningful text.... Do you agree that you can be pretty much sure that the meaningful text you started with was what the user entered?
    If you have the key, yeah, that is the whole point. But if you have the key you don't need to "break" the text which created the key -- you can skip straight to decrypting the message.

    If you don't have the key, it would be more or less totally insane to start trying to come up with the random text which produced it, and test that to see if it produces a key which will decrypt the message itself.
    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

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