Thread: one time pad breakable debate

  1. #196
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    Randomness isn't, IMO. I'm a determinist like Einstein. Randomness is an illusion.

    Entropy is I see more like an effect of an "arbitrary" event or juxtaposition, as in thermodynamics or quantum physics. On which I am no expert

    The point being, there are no random sources, only entropic wells to tap.
    That's a fine philosophical view of randomness (of the lack thereof). It has no bearing on the concept on randomness with respect to cryptography, which works even if say, God does not play dice with the universe.
    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. #197
    Registered User NeonBlack's Avatar
    Join Date
    Nov 2007
    Posts
    431
    Quote Originally Posted by laserlight View Post
    God does not play dice with the universe.
    God can do whatever the hell he wants to.
    I copied it from the last program in which I passed a parameter, which would have been pre-1989 I guess. - esbo

  3. #198
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by whiteflags View Post
    If you choose a source that maps to 47 zeros amd 53 ones, that's not going to be random
    I hope you are talking exclusively of deterministic PRNGs.

    An RNG input will condition the results, admittedly mapping to 47 zeros and 53 ones. But you will still get a random result if you cannot measure the quality of the RNG in any possible way. And here too there is no form of rigging the output (like running an extractor to produce a uniform distribution) that will change the fact the original sequence was random, despite not being uniformly distributed.
    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.

  4. #199
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I am talking exclusively about the generator that MK says is random.

    If I understand what you mean, then a generator can be random even if the probability of an outcome is not constant. (Again, uniformly distributed stuff... there is a wiki page.)

    In probability theory and statistics, the discrete uniform distribution is a probability distribution whereby a finite number of values are equally likely to be observed; every one of n values has equal probability 1/n.
    Maybe that's clearer.... Otherwise, frankly I give up then with sincere apologies. I understood this as a fundamental part of unpredictability. It might be me, but I'd need some help learning this correctly, if I am wrong.

  5. #200
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    You are correct, as far as I know. But only where the definition is applicable. And this is why they run extractors on RNGs. To achieve that characteristic dear to fields like cryptography where randomness needs to be mathematically defined.

    However a uniform distribution, merely defines a characteristic of a known system. It does not by itself determine the condition of being random. It's defines the quality of that randomness. What has been defining randomness for us so far is our inability to determine the next outcome without any margin of error whatsoever (shocking!). That's why we look for generators outside deterministic origins. Reading noise levels from rain is bound do produce random data, data we have no way of predicting or duplicating and that is fully non deterministic to the best of our current scientific knowledge and technological abilities. Yet we know full well, before we start reading it, that the output of those noise levels will contain undesirable patterns and bias. We do not question their random condition, but because we need a uniform distribution we merely call them Weak Random Data.

    I agree that under such fields as cryptanalysis, it doesn't matter. Laserlight also repeatedly tried to put this point across. And I agree. We cannot just extrapolate a concept and trample over centuries of well defined and mathematically established rules concerning random data generation. But I felt I needed to insist that the original data is still random, despite not being very useful for some purposes under its present condition.

    It's not that cryptanalysis has a definition for Random. It's that it has requirements for Random. I think this is an important distinction.
    Last edited by Mario F.; 03-18-2010 at 05:53 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.

  6. #201
    Registered User kryptkat's Avatar
    Join Date
    Dec 2002
    Posts
    638
    Unicity distance - Wikipedia, the free encyclopedia

    true randomness can not be mathematically defined. that is the problem. as programmers we can only try to simulate true randomness.

    http://www.cacr.math.uwaterloo.ca/hac/about/chap5.pdf
    is that the whole chapter or just part of the chapter ?

    this is more fascinating than a ball of string.

    exactly how many numbers do you really need to find the seed ? do you have any handy code you could paste that would find the seed ?

    i provide you with a senerio where your criteria is met. a user recognizing the message as the one that was encrypted. the user lost the key and had to brute force the file to recover the data. how is that not considered breaking a one time pad ?

  7. #202
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by kryptkat View Post
    i provide you with a senerio where your criteria is met. a user recognizing the message as the one that was encrypted. the user lost the key and had to brute force the file to recover the data. how is that not considered breaking a one time pad ?
    As someone who knows the contents of the plaintext, you have a determining advantage over an attacker who is exactly trying to establish what the contents of the plaintext are. You are not attacking the cipher because a one-time pad is exactly defined by its ability to hide the real plaintext behind a seemingly infinite number of possible matches. And you cannot test this ability if you know what the plaintest is. In other words, you are not attacking the cipher because the one thing that defines it is never put to the test.

    Your example can serve other type of ciphers, mind you. But just not a One-Time Pad.
    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. #203
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    Lightbulb

    You know, I just realized a very easy way to implement a "repetitive" OTP (eg: wherein the key is shorter than the data and so is repeated for the length of the data) that would be sufficiently secure (provided that the key is "reasonably strong", of course): Just compress the data before applying the key. The only requirement there is that the compression format couldn't contain any "signature" bytes that could be used to reveal the key. I actually have a Huffman compressor that uses such a convention (it relies on sanity checks to verify the file rather than signatures). The attacker would have to resort to trying to guess the key without the benefit of analytic methods.
    Last edited by Sebastiani; 03-18-2010 at 09:26 AM. Reason: ...

  9. #204
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by kryptkat
    i provide you with a senerio where your criteria is met. a user recognizing the message as the one that was encrypted. the user lost the key and had to brute force the file to recover the data. how is that not considered breaking a one time pad ?
    It is obviously not breaking a one time pad, since the user would have known the plaintext even without cryptanalysis. If the user does not know the plaintext, then he/she would be unable to recognise the message.

    Quote Originally Posted by Sebastiani
    You know, I just realized a very easy way to implement a "repetitive" OTP (eg: wherein the key is shorter than the data and so is repeated for the length of the data) that would be sufficiently secure (provided that the key is "reasonably strong", of course): Just compress the data before applying the key.
    Yes, that is a good idea, and I believe that it is already in use when implementing ciphers in practice (including those not equivalent to a one time pad). Of course, in the end it must the case that the key is not repeated, otherwise it is not a one time pad.

    Quote Originally Posted by Sebastiani
    The only requirement there is that the compression format couldn't contain any "signature" bytes that could be used to reveal the key.
    For a one time pad, that does not matter. The portion of the key revealed has nothing to do with the rest of the data.
    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. #205
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by laserlight View Post
    Yes, that is a good idea, and I believe that it is already in use when implementing ciphers in practice (including those not equivalent to a one time pad). Of course, in the end it must the case that the key is not repeated, otherwise it is not a one time pad.
    Right, and no doubt a true OTP would be much more secure.

    Quote Originally Posted by laserlight View Post
    For a one time pad, that does not matter. The portion of the key revealed has nothing to do with the rest of the data.
    Yes, for a true OTP that is indeed the case, but if the key is actually being repeated then revealing a portion of the key would necessarily expose each and every cell that corresponds to that index of the key. So for example, let's say the attacker knows that the data is a text file. He starts with a guess that the key block is N bytes long, and then xor's the Xth index of each block with the value V. If every byte altered yields a character, it's marked as a possible candidate, and the process continues. Then all of the permutations of candidate combinations are tried and compared with a dictionary. The value of N is incremented and the process repeats. Even though it's just a brute force technique, the rejection criteria may well speed things up quite a bit, making it an ugly but notheless feasable approach.

  11. #206
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by kryptkat
    i provide you with a senerio where your criteria is met. a user recognizing the message as the one that was encrypted. the user lost the key and had to brute force the file to recover the data. how is that not considered breaking a one time pad ?
    How can that be considered as breaking a one time pad? Let's make your scenario harder: not only has the user lost the key, but the user has lost the encrypted file as well. It is obvious that using your idea, the user can still recover the message, simply by brute force. In other words, it is not even necessary to have the ciphertext to retrieve the plaintext. Therefore, there is no cryptanalysis involved; you're only testing the user's ability to recognise the message when it is shown to him/her.
    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. #207
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    Quote Originally Posted by MK27 View Post
    I'm gonna assert the best key generator will have no predictable distribution at all.
    This is an interesting idea. I want to make sure I understand what you're saying. For all two-bit strings, which of the following scenarios best exemplifies what you mean by 'no predictable distribution'?
    1. There are four two-bit strings: 00, 01, 10, 11. Each of these strings has a 25% chance of being generated by the RNG.
    2. There are three bit ratios: 100/0, 50/50, 0/100. Each of these bit ratios has a 33% chance of being generated by the RNG.
    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. #208
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    Let's go back to the idea that a 1000 bits represents 2^1000 possibilities. If I use a RNG that guarantees a 50/50 distribution, or is based on an algorithm admired for such, then that is no longer true...

    IF I, AS THE CRACKER, KNOW THAT YOU ARE OBSESSED WITH PERFECT DISTRIBUTION, GUESS WHAT JUST HAPPENED? HA HA HA!
    With a uniform distribution, each bit is equally likely to be a 0 or a 1, by definition. Therefore, a RNG with a uniform distribution has a probability of 1/(2^1000) to generate a sequence that consists entirely of 0s, and indeed this probability is the same for any particular sequence of 1000 bits. So, the adversary is not better off with this knowledge.

    EDIT:
    Ah, I see that whiteflags has already mentioned this, although I would not go so far as to say that distribution has nothing to do with output since it is the distribution that determines characteristics of the output (more than just the proportion of 0s and 1s). I believe that this is an idea behind the use of statistical tests of randomness, i.e., by testing a sufficiently large sample of output, you can draw some conclusions about how "random" is the random sequence generated, and thus how good is the quality of the PRNG or RNG for the intended purpose.
    Last edited by laserlight; 03-19-2010 at 08:48 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

  14. #209
    Registered User kryptkat's Avatar
    Join Date
    Dec 2002
    Posts
    638
    How can that be considered as breaking a one time pad? Let's make your scenario harder: not only has the user lost the key, but the user has lost the encrypted file as well. It is obvious that using your idea, the user can still recover the message, simply by brute force. In other words, it is not even necessary to have the ciphertext to retrieve the plaintext. Therefore, there is no cryptanalysis involved; you're only testing the user's ability to recognise the message when it is shown to him/her.
    nice. that makes sense.

    but what about video ? say a video stream or pictures. you know i am correct about the focus thing. you or the user or the attacker may recognize pictures or normal movies or even porn. you think that would be considered breaking a one time pad then ?

    if a user xors the most popular letters say 's' 'a' and 't' they might get them in the correct spot. then guess some of the correct words cryptanalysis is just testing and guessing anyway. ie one line of 't' then one run on the file with 's' then one run on the file with the other letters to see what shows up.

  15. #210
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by kryptkat
    but what about video ? say a video stream or pictures. you know i am correct about the focus thing. you or the user or the attacker may recognize pictures or normal movies or even porn. you think that would be considered breaking a one time pad then ?
    No, because even if the attacker has external information that tells him/her that the plaintext is video of a particular format, the attacker would still be faced with all possible videos of that format that can be encoded and encrypted such that it produces a ciphertext of that length. Since all those videos are equally likely, recognising one of them does not mean anything... further down the road of brute force, the attacker will recognise another, and another, and another, etc. Eventually, one of them will be the plaintext, but with just this information, the attacker will never be able to honestly say that aha!, among all those that I recognise, this video is most likely to be the plaintext.

    Quote Originally Posted by kryptkat
    if a user xors the most popular letters say 's' 'a' and 't' they might get them in the correct spot. then guess some of the correct words cryptanalysis is just testing and guessing anyway. ie one line of 't' then one run on the file with 's' then one run on the file with the other letters to see what shows up.
    You seem to be talking about frequency analysis. Again, this does not work against a one time pad, because the attacker has no way to verify which of the guesses is correct. The idea that because the ciphertext depends entirely on the key, as long as you do not know the key, you can derive no information about the plaintext, regardless of your cryptanalysis technique.

    We only have to be concerned with brute force. If brute force does not cut it, nothing else will, including frequency analysis.
    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