one time pad breakable debate

Printable View

Show 80 post(s) from this thread on one page

03-17-2010
MK27

Quote:

Originally Posted by whiteflags

Can I ask another question then? Doesn't unform distribution (and fair distribution, for that matter) mean equal probability? Natural methods of randomness have this property. Correct me if I am wrong but you are saying that this simple method of yours is suitable for a one time pad. That can't be true if it has a bias toward specific bits, no matter how small.

Look: this is stupid.

If the distribution of characters in the English language means that using the mod 2 algorithm will on average yield 47% zero and 53% one, that means that by changing the algorithm, you could achieve exactly 50%. Just pick the characters according to the average distribution.

Presto! Now you have an algorithm, that when applied to English language texts, should ideally (on average, with a greater degree of accuracy in a larger sample, just like any other kind of random data) yield exactly 50% ones and exactly 50% zeros!

Hooray, now we have perfectly uniform distribution and perfectly equal probability! From the exact same source!

Now, explain how this makes the data "more" or "less" random. Otherwise this criteria is pure red herring (and I don't care if some grad student somewhere has fallen for it or not).

I believe the concern with equal probability is for the purpose of evaluating "unknown" sources. If it appears skewed, then that skew will just keep increasing with the volume
of data. In this case, don't bother -- we already have all the data in the form of the Statistical Distribution of letters in the English language.

In the case of the "random typing" to bitstream test, if you want to use the keyboard for random bits, adjust the method until you get, on average, equal probability for each bit. The criticism is that people will not "evenly distribute" their key presses: so there must be statistical trends. If you have fifty keys, take your data for those fifty keys, then assign so that you will end up with the distribution you want.

The whole premise of the evaluation is bogus. I am sure it will be impossible to eliminate recurrent patterns of characters. But if you cannot get an even distribution of bits, that's simply because you did not try to do so.

Which is like turning the Geiger counter up too high and saying, well, the distribution is not even, I guess radioactive decay is no good.

I'm coming to agree with Mario F. here, vis, this is a purely academic debate in pursuit of a definition of "random" which has little or no real value.
03-17-2010
laserlight

Quote:

Originally Posted by MK27

That the bits are independent of one another is sufficient. If you want to test the algorithm, and not just a sample of data, you have to demonstrate that you can guess the next bit at a rate better than the distribution of the bit. The exact distribution is irrelevant.

Sufficient for what? If the random distribution is not uniform, then using the bits for a one time pad results in less information being contained in the key than expected. Basically, a non-uniform distribution has bias when you want to use it for keys that are equally likely.

Quote:

Originally Posted by MK27

Yeah, and I have read the paper and hopefully made clear that IMO it is not a good paper

I cannot say if the paper is a good paper after just a cursory glance, but after reading about the amount of data that was considered, it was obvious that the conclusions of that experiment are more or less useless except as a reference for future work.

Quote:

Originally Posted by kryptkat

if you recognize your own data then you can agree that a one time pad was cracked ? even if you have to add the stipulations that only someone in the "know" can say "yes" that is the data or verified through external verification after the fact by torture or trickery or other means ?

Torture and trickery (and even bribery) are valid methods of cryptanalysis (although torture is immoral and may be illegal). But these are not considered when we talk about the strength of an encryption algorithm because they go against Kerckhoff's assumption that only the key is secret.

Quote:

Originally Posted by kryptkat

or if the file is long enough to see what comes in to focus <analogy> or the rest of the data makes sense.

You might want to search the Web for "unicity distance". A one time pad has infinite unicity distance.

Quote:

Originally Posted by kryptkat

please do not say i am wrong. please respect me for having a different opinions or beliefs.

As I said, within the bounds of your own definitions, you are not wrong. But when we use the definitions that are accepted by cryptographers, you are wrong.

Quote:

Originally Posted by kryptkat

only in theory.

Yes, in practice, one time pads are rarely used because it is so difficult to get them right. Thus...

Quote:

Originally Posted by kryptkat

laserlight have you ever really used a real nitrocellulose one time pad ?

... no. I have had no reason to use one time pads anyway.
03-17-2010
pianorain

Quote:

Originally Posted by whiteflags

Can I ask another question then? Doesn't unform distribution (and fair distribution, for that matter) mean equal probability? Natural methods of randomness have this property. Correct me if I am wrong but you are saying that this simple method of yours is suitable for a one time pad. That can't be true if it has a bias toward specific bits, no matter how small.

Yes, this seems correct. For example, suppose I have a hat with four slips of paper: two with '1' and two with '0'. I could draw a slip out of the hat, write down the binary digit, and return the slip. This method of generating binary digits has both properties of bit independence and uniform distribution. It makes sense.

However, if the hat contained one '1' and three '0', despite bit independence in how the bits are selected, the distribution is wildly skewed. I don't think anyone here would argue that this method of generating random binary digits is good. This illustrates the need for a generator to generate bits with as close to equal probability as possible.
03-17-2010
Mario F.

Quote:

Originally Posted by laserlight

The Diehard tests are quite famous, and then I believe NIST also provides a test suite. The problem that I am facing right now is how to select source text. You need a great deal of it to be statistically significant.

I believe they should be a function of the number of discreet values, no? And quite a large number of text at that, I suppose.

I don't know what to say at this point. Certainly I would not wish for your to start typing millions of random characters in order to produce something relevant for these tests to chew on. I certainly can't be bothered myself doing it just to try and prove my point.

Quote:

Originally Posted by pianorain

I simply don't know of and have never heard of any source citing what you're saying. Meanwhile, I know I've heard of sources saying exactly the opposite: that random human typing is non-random. It's beyond me to try to test definitively either way. I'm just trying to present my thoughts. Once again, apologies for any disrespect to your argument.

No. I felt no disrespect. Just annoyance :)

It's that the author himself cannot prove this. And yet it is being debated as a veritable truth. It's a logical observation no doubt based on some form of testing. But where? How? What? With whom? These are left unanswered by the author and any other references I've looked up on the internet (and oh boy, did I try to search for them!). I cannot simply accept that when all my cells in my body tell me otherwise. When I'm completely incapable of duplicating or predicting a series of characters I myself typed randomly on the keyboard. When in fact, I even sustain that is logical to assume that we will tend to an acceptable distribution if we are instructed to type randomly at a keyboard.

Do you agree tiredness may affect what what characters you type? Do you agree body temperature, weather conditions, your vigil levels, your concentration, your emotional levels, your health, all can affect what keys your fingers will move on? That over a long period of time these factors interact in such a manner resembling the factors behind tossing a bag of die onto the air, rendering any hope of predicting or duplicating the pad virtually useless?

There may be some truth to what you support over a relatively small sequence. But this cannot hold true for on any real live application of a one-time pad where the plaintext could be the size of a small book, or even a page. And especially if the plaintext contains information that can lead to easy confusion, like dates, values or formulas.
03-17-2010
MK27

Quote:

Originally Posted by laserlight

Sufficient for what? If the random distribution is not uniform, then using the bits for a one time pad results in less information being contained in the key than expected. Basically, a non-uniform distribution has bias when you want to use it for keys that are equally likely.

Sure -- so in reality this would mean what, you start guessing all the keys starting with the 51% more likely bit? Horseshoes and handgrenades! What is that going to help?

Altho I did describe how you could achieve 50/50 distribution by tweaking the algorithm, I still think you would have to be insane to consider that a meaningful improvement.
03-17-2010
laserlight

Quote:

Originally Posted by MK27

If the distribution of characters in the English language means that using the mod 2 algorithm will on average yield 47% zero and 53% one, that means that by changing the algorithm, you could achieve exactly 50%. Just pick the characters according to the average distribution.

Not necessarily, e.g., it may be the case that there is no configuration that achieves exactly 50% on average. But yes, this is why I decided to describe your proposed RNG in terms of an unspecified hash function instead of ASCII value modulo 2: I felt that in a practical implementation it may be necessary to use a different hash function.

I do not think that this is necessarily enough though. My impression is that statistical randomness involves more than just a uniform distribution (after all, a uniform distribution can be converted to other random distributions, and vice versa).

Quote:

Originally Posted by MK27

Sure -- so in reality this would mean what, you start guessing all the keys starting with the 51% more likely bit? Horseshoes and handgrenades! What is that going to help?

I am not sure: my cryptanalysis knowledge is really bad. But remember, we're talking about the information theoretic perfect secrecy of a one time pad. This is uh, different from the reality of cryptography and cryptanalysis in practice.
03-17-2010
MK27

Quote:

Originally Posted by laserlight

But remember, we're talking about the information theoretic perfect secrecy of a one time pad.

That is horseshoes and hand-grenades. Even if you get 60% of the bits correct, the secrecy of the one time pad is still perfect -- it has not been weakened at all.

To weaken the value of the pad generator, you would have to demonstrate that it does not have a 100% unbreakable success rate. So whereas a valid pad generator will generate keys that are never broken, a "weaker" generator might produce keys that could be broken 1 in a million times.

By saying, well, I know the generator is skewed to produce 52% 1, so I can get better than 50% of the bits correct -- that is meaningless. Getting 50 or 60 or even 75% of the bits correct will not translate to an improvement in breaking the pad. You will still never break a key, even once.

I think it is good to have an interest in research and (apparently) authoritative criteria and sources, but as I said a while ago, many of you are engaged in naive reification.

Reification is the fallacy of regarding a concept as a real thing. This is a fallacy in so far you are now out to find the real thing (which does not exist) instead of refining your conceptualization. Someone says "the real thing of randomness means even distribution" -- rather than trying to comprehend the significance or value of even distribution with regard to randomness, you now ascribe "even distribution" to be a "real property" of "true randomness". Eventually you end up with hypotheses that make no sense -- eg, this key generator does not achieve perfectly even distribution, therefore it is not truly random, therefore someone could break a key it generates.

That last step is pure faith, and what's more, it's wrong -- no one will ever break a key this way. You have replaced your brain with a set of false idols.

I was interested to learn that "In statistics, reification is the use of an idealized model of a statistical process. The model is then used to make inferences connecting model results, which imperfectly represent the actual process, with experimental observations."

define: reification - Google Search
03-17-2010
whiteflags

Quote:

Originally Posted by MK27

Now, explain how this makes the data "more" or "less" random.

Remember those contests M&M had, where you had to find the bag with the red M&Ms? The winner of the contest was a random one, because every bag could have been the winner. There is no other observable factor in the winning choice. Now, there was probably more than one person who won the contest, but whether it was five or 100 people, you could not reduce the favorable outcome.

You may have a bag of M&Ms that appears to win the contest for a long time. (M&Ms, being delicious, you decide you don't care about the contest.) But then you come across a blue one, or whatever. If you tried for the longest permutation of red M&Ms in a bag, your results would be skewed by the number of M&Ms in the bag, for all bags.

But the selection of colors that goes into M&Ms bags could be truly random, because there are only 5 (IIRC) and the probability for each is equal. How Mars chooses its colors for each bag is something I do not know. But if the distribution were equal, then you eating candy and guessing the color would be truly random because an endless string of red candies is as possible as any other permutation.

It may be that an imperfect solution is good enough most of the time, but it comes down to there being no other observable factor in a try in a permutation. We may not live in a truly random world, but equal probability is not hard to strive for in nature. You could simply have five of each color in your hand.

And they wont melt. HTH.
03-17-2010
MK27

Quote:

Originally Posted by whiteflags

But if the distribution were equal, then you eating candy and guessing the color would be truly random because an endless string of red candies is as possible as any other permutation.

This is a terrible example. Even if the distribution were 1:100:1000:10000:100000 it would be make exactly no difference to determining which M&M ended up in which bag.

Maybe if you could apply this to the case at hand (the one time pad generator), you might make some sense.
03-17-2010
pianorain

Quote:

Originally Posted by Mario F.

Do you agree tiredness may affect what what characters you type? Do you agree body temperature, weather conditions, your vigil levels, your concentration, your emotional levels, your health, all can affect what keys your fingers will move on? That over a long period of time these factors interact in such a manner resembling the factors behind tossing a bag of die onto the air, rendering any hope of predicting or duplicating the pad virtually useless?

I definitely agree that all of those factors could play a part in what characters are typed in flail-text. Indeed, I'm sure that as my fingers got tired generating 4 680-character flail-text strings, I hit keys differently than I would if I'd given myself a break. However, I can't agree that those factors make the pad generation "random".

The "tossing a bag of dice" is not a good example. I think tossing a bag of dice is a fine example of randomness. An example I think more closely illustrates what I'm trying to convey would be tossing a bag of dice, where each die has been slightly weighted to land on 6 more often than the others. Tossing the bag is fine; the problem is with the dice. Similarly, flail-text is fine; the problem is with the input device. When flailing, I know that my fingers hit some keys significantly more often than others. No matter how hard I seem to try, I end up with most of my keys being closer to the middle of the keyboard, only rarely hitting keys near the corners. As the author of the paper pointed out, flail-text may contain statistically significant two-letter sequences due to a finger pressing both keys at once; I know mine do. Of course, this is a personal observation; your flail-text may be more random than my own.

The reduction of flail-text to the binary representation may be able adjust for these deficiencies, as laserlight pointed out. Now that I understand her suggestion to use an unspecified hash function instead of just mod 2, it seems more reasonable.

Quote:

Originally Posted by Mario F.

There may be some truth to what you support over a relatively small sequence. But this cannot hold true for on any real live application of a one-time pad where the plaintext could be the size of a small book, or even a page. And especially if the plaintext contains information that can lead to easy confusion, like dates, values or formulas.

I'm not suggesting any sort of practical attack. I'm just looking at things logically. If the pad used in a OTP is not generated randomly, then an attacker can use the information about how a pad is generated to develop an attack. (Remember, the user gets only one secret, and it's not how the pad is generated.) If flail-text is not sufficiently random, it should not be used to generate a pad. In this case, it seems that the standards used to test a CS-PRNG would be strict enough for a definition of 'sufficiently random'. Because a CS-PRNG is tested for "next-bit" vulnerabilities, flail-text should also be tested in this manner. The only part I'm a bit shaky on is whether or not the "next-bit" test implies that all bit strings of a single length show up with equal probability. Now, if we're defining 'sufficiently random' as 'it's good enough for me', then obviously we don't have to worry about such things.
03-17-2010
whiteflags

If the random number generator cannot select an output from a source where all possible outputs could be outputs, how is it truly random?

It doesn't matter how random the output looks. It doesn't matter if you can nigger rig the output to lie with statistics, the crucial point is that if your going to make a truly random coin flipper, you can't make the algorithm prefer heads. You have to make it so that it could choose heads or tails equally. Otherwise you get patterns, which means that there is a seed somewhere that could reproduce the outcome in a reliable way.

Or rather I should use the word period: the term for the length of outputs a generator gives, before it repeats. That's deterministic and random is by definition not deterministic.
03-17-2010
laserlight

Quote:

Originally Posted by MK27

Even if you get 60% of the bits correct, the secrecy of the one time pad is still perfect -- it has not been weakened at all.

Actually, no. If you get just one of the bits correct, the one time pad has been broken, for that bit. Each bit of the keystream is a separate key in its own right.

But I think that this is just due to inaccurate terminology: you probably mean to say that even if you can statistically predict that 60% of the bits will be 0 (or 1, as the case may be), you still have no information as to which bit is which.

Quote:

Originally Posted by MK27

rather than trying to comprehend the significance or value of even distribution with regard to randomness, you now ascribe "even distribution" to be a "real property" of "true randomness".

"Randomness" has different meanings in different fields. There is no single universally accepted definition of randomness.

Quote:

Originally Posted by MK27

That last step is pure faith, and what's more, it's wrong -- no one will ever break a key this way.

Yes, it is faith: I trust that the experts know what they are talking about because I do not have the requisite knowledge, and have not had the opportunity to examine what they would reply to such objections.

There is the saying that a little knowledge can be a dangerous thing. Your arguments go beyond my knowledge, but then I am not convinced that you actually have more knowledge than I do: you are reasoning with less knowledge than experts, so it may be the case that your reasoning is flawed because you have not considered something.

On the other hand, newcomers to a field do make breakthroughs by insights that have been ignored because of unwarranted unassumptions. However, such cases are rare.

Quote:

Originally Posted by MK27

You have replaced your brain with a set of false idols.

I suggest that you avoid these kind of ad hominem comments. It may be the way you like to express yourself, but frankly, it is offensive.
03-17-2010
Mario F.

Quote:

Originally Posted by pianorain

I'm not suggesting any sort of practical attack. I'm just looking at things logically. If the pad used in a OTP is not generated randomly, then an attacker can use the information about how a pad is generated to develop an attack. (Remember, the user gets only one secret, and it's not how the pad is generated.) If flail-text is not sufficiently random, it should not be used to generate a pad.

Well, there's nothing to argue there.

But let me end this way: If one day it is indeed proven that by randomly typing at a keyboard we can not produce good enough random sequences, I'll be very dissapointed with mankind.
03-17-2010
MK27

Quote:

Originally Posted by laserlight

Actually, no. If you get just one of the bits correct, the one time pad has been broken, for that bit. Each bit of the keystream is a separate key in its own right.

So no "properly generated" one time pad can be broken less than 50%. By simply setting all bits to one, I now can rest assured that 50% of the characters in my deciphered message are correct. :p

Quote:

Yes, it is faith: I trust that the experts know what they are talking about because I do not have the requisite knowledge, and have not had the opportunity to examine what they would reply to such objections.

I'll assume they would say that if no one can break any key you have generated, then your message is still safe.

Quote:

There is the saying that a little knowledge can be a dangerous thing.

No doubt.

Quote:

you are reasoning with less knowledge than experts, so it may be the case that your reasoning is flawed because you have not considered something.

We probably have a somewhat different understanding of who experts are and what they are quite often about. Mine is cynical :p

Quote:

I suggest that you avoid these kind of ad hominem comments. It may be the way you like to express yourself, but frankly, it is offensive.

Yeah. I apologize. I've gotten a little over the top obsessive in this thread and there is nothing left for me to prove. I'll stop now.

Quote:

Originally Posted by Mario F.

But let me end this way: If one day it is indeed proven that by randomly typing at a keyboard we can not produce good enough random sequences, I'll be very dissapointed with mankind.

Reality is a tough nut to crack.
03-17-2010
laserlight

Quote:

Originally Posted by MK27

So no "properly generated" one time pad can be broken less than 50%. By simply setting all bits to one, I now can rest assured that 50% of the characters in my deciphered message are correct.

Using your definition of what it means to correctly guess a bit, yes, that is true.

Quote:

Originally Posted by MK27

I'll assume they would say that if no one can break any key you have generated, then your message is still safe.

I already know that :)

But the test here is not whether no one can break any key that I have generated; the test is whether, given infinite storage, instant retrieval, processing power that can perform all computations instantly, and with sufficient ciphertext, it is possible to obtain any information at all about the plaintext (other than possibly its length). If that can be done, then the cipher is not equivalent to a one time pad.

That said, my lack of knowledge of information theory is not a dead end; we can always pose questions to one or more experts.

So, could you restate your objection to the requirement of uniform distribution for a RNG whose output is suitable for use as a one time pad?

Quote:

Originally Posted by MK27

We probably have a somewhat different understanding of who experts are and what they are quite often about. Mine is cynical

That is the kind irrational paranoia that is a good quality in security professionals ;)
03-17-2010
MK27

Quote:

Originally Posted by laserlight

Using your definition of what it means to correctly guess a bit, yes, that is true.

My definition? :confused: It's not...

Quote:

Originally Posted by laserlight

If you get just one of the bits correct, the one time pad has been broken, for that bit. Each bit of the keystream is a separate key in its own right.

Quote:

the test is whether, given infinite storage, instant retrieval, processing power that can perform all computations instantly, and with sufficient ciphertext, it is possible to obtain any information at all about the plaintext (other than possibly its length). If that can be done, then the cipher is not equivalent to a one time pad.

If you know the generator is "a proper one" with 50% distribution, then you can get half the bits correct by just guessing one all the time. If you know that the distribution (by the algorithm) is 53/47, then you should be able to get 53%. The problem is, in both cases you will not know which ones are correct, so I am not sure if this constitutes "any information at all".

Quote:

So, could you restate your objection to the requirement of uniform distribution for a RNG whose output is suitable for use as a one time pad?

Because it is neither a necessary nor a sufficient criteria in and of itself. I think it is a decent guiding principle, but that is sort of self evident: no one is going to mistakenly believe that a generator that does this: 1111111111111 is effective. This is just fiddling with a gauge on the Geiger counter, and believing that because you have not tuned your inputs correctly that radioactive decay is no good.

By treating it as a necessary criteria, you fall into the trap whiteflags did: believing that an uneven probability indicates less randomness. If have a box with 10 holes in the bottom, 6 of them blue, 3 of them green, and 1 of them red, if I drop a ball in the box and shake it until it goes into a hole, there is an even probability that it will land in any particular hole, but only a 10% chance that hole will be red: is that random? ;)

Quote:

That is the kind irrational paranoia that is a good quality in security professionals

It is not paranoia if they really are out to get you -- then it's wisdom.
03-17-2010
laserlight

Quote:

Originally Posted by MK27

The problem is, in both cases you will not know which ones are correct, so I am not sure if this constitutes "any information at all".

Yes, that is why I think that you are not actually getting the bits correct. You are just getting the distribution correct.

Quote:

Originally Posted by MK27

By treating it as a necessary criteria, you fall into the trap whiteflags did: believing that an uneven probability indicates less randomness. If have a box with 10 holes in the bottom, 6 of them blue, 3 of them green, and 1 of them red, if I drop a ball in the box and shake it until it goes into a hole, there is an even probability that it will land in any particular hole, but only a 10% chance that hole will be red: is that random?

It is. But it this randomness sufficient for a one time pad? Basically, the aim is to generate as much random information as there is plaintext. This is related to the concept of entropy. If I should link to Wikipedia: Entropy (information theory).

Notice that Schneier prefaces his statements with "for our purposes" and "from our point of view". In fact, I have left out the part where he briefly discusses some philosophical ideas about randomness which are not used in cryptography.
03-17-2010
MK27

Quote:

Originally Posted by laserlight

Notice that Schneier prefaces his statements with "for our purposes" and "from our point of view".

Well, to put it bluntly: As far as I am concerned, anyone who thinks that plain language text arbitrarily converted (with mod 2) to a bitstream does not represent the very essence of entropy has failed to understand life, nature, the universe, and mostly everything in it.

I would consider any circuitous attempt to demonstrate this is not clearly so misguided or babylonic (ie, non-sensical), not matter how much material you want to reference (here not referring to anything in particular, I haven't read that article yet), and most of this thread bares that out.

That may seem arrogant or ignorant, at first glance, but I assure you it isn't. :p
03-17-2010
laserlight

Quote:

Originally Posted by MK27

Well, to put it bluntly: As far as I am concerned, anyone who thinks that plain language text arbitrarily converted (with mod 2) to a bitstream does not represent the very essence of entropy has failed to understand life, nature, the universe, and mostly everything in it.

I would consider any circuitous attempt to demonstrate this is not clearly so misguided or babylonic (ie, non-sensical), not matter how much material you want to reference.

Well... so you are saying that you will never change your mind, even if you can be shown to be wrong?

I would think that a more sensible approach is to hold to your convictions unless you are shown evidence that they are untenable.

Quote:

Originally Posted by MK27

That may seem arrogant or ignorant, at first glance, but I assure you it isn't.

I find it rather ironic that you claim to be cynical of experts and yet so easily give assurances as if you are an expert ;)
03-17-2010
MK27

Quote:

Originally Posted by laserlight

Well... so you are saying that you will never change your mind, even if you can be shown to be wrong?

Not at all, I do that here occasionally. Some days I seem to end up doing it a lot...

However, that does not mean that I need to give credence to every possible objection, or that I need to exhaustively research the color of the sky to be very confident it is blue.

Quote:

I would think that a more sensible approach is to hold to your convictions unless you are shown evidence that they are untenable.

Definitely.

Quote:

I find it rather ironic that you claim to be cynical of experts and yet so easily give assurances as if you are an expert ;)

I never claim to be an expert on anything, because I am not. But I don't think you need to be an expert in anything in order to understand something. There are a lot of "somethings" that I am confident I understand and maybe I seem to give "assurances" about them.

I will admit that sometimes I'll assert something I'm uncertain of, just to see if someone will contradict or correct me, in a rational manner (in which case I acknowledge I was mistaken).

WRT experts, I don't trust authority: so I will not take someone's word for something because they claim expertise (including credentials) if I think they are wrong -- they also need to make sense, unfortunately. In my experience, that does not seem to be difficult for genuinely knowledgeable people to do if they are so inclined.

Conversely, many people in all walks of life seem to consider it their raison d'etre to habitually introduce irrational doubts into the world. That is not necessarily bad (qv, some Sufis) but it is also not necessarily good (qv, some Sufis). Either way, it does go on.
03-17-2010
laserlight

Quote:

Originally Posted by MK27

However, that does not mean that I need to give credence to every possible objection, or that I need to exhaustively research the color of the sky to be very confident it is blue.

That is true. Let me try one last attempt: you cited a scenario of "a box with 10 holes in the bottom". Consider the scenario of coin flipping. When you flip a coin, you generate 1 bit of random information. So, if you flip a coin 8 times, you should get 8 bits of random information. But suppose that the coin is not a fair coin, e.g., it is weighted on one side. Would you really still get 8 bits of random information after 8 flips?

The idea here is that you don't, e.g., you get 7 bits of random information. But now, if you take the 8 bits generated from the coin flips and use it in a one time pad to encrypt 8 bits of information, then you would have actually used a key of effectively 7 bits, not 8 bits, to encrypt 8 bits of information.

In theory, this means that the 8 bits of ciphertext do not entirely depend on the 8 bits of key, as the actual information in the key is 7 bits. There is 1 bit of ciphertext that actually depends on both the plaintext and the key. It probably is not enough to deduce the entire plaintext, and in practice may not even be enough to deduce a single bit, but it still does not amount to perfect secrecy.

Relating this back to "plain language text arbitrarily converted (with mod 2) to a bitstream", it means that just because the process is random does not mean that you necessarily get at least as much random information as you need. So, "the very essence of entropy" is a grand phrase, but not necessarily an accurate one.
03-17-2010
Sebastiani

Quote:

Originally Posted by laserlight

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.

Not necessarily...it just has to be hard to guess!

Quote:

Originally Posted by MK27

Well I fulfilled both criteria:
1) the key generated will be at least as large as the data.
2) the key was generated using a truly random source (to understand why and how this is so, read the thread*).
*paraphrased: human language texts considered as a modulus 2 of ascii values does not contain any pattern; it is a random sequence of 0 and 1.

You don't actually need "true" randomness, IMO. Theoretically, a distribution close to 50% (of 0's and 1's) is most desirable, and that heuristic could then be used to verify the integrity of the chosen algorithm. So, for example:

- A key of arbitrary length is selected by the user. Both binary and text modes should be available (eg: via command line options, stdin, file, etc).
- If the key is shorter than the data then it is expanded, otherwise it's truncated. The expansion shouldn't produce any large blocks of repetitive patterns (such as zeros), obviously. A sufficiently complex fractal could be used, for example.
- The OTP is applied to the data.
- Lather, rinse, repeat.

The fact that the guessed password reveals the data is also a non-issue, or at least it has nothing to do with the security of the algorithm. That's just a matter of key management, really. As always, a "strong" password must be chosen. That kind of goes without saying, though, doesn't it?
03-17-2010
MK27

Quote:

Originally Posted by laserlight

, "the very essence of entropy" is a grand phrase, but not necessarily an accurate one.

It is essentially an entropic source. The fact that it ends up being 47:53 is symptomatic of that -- the distribution is not perfect because the source is entropic. Who would have guessed?

Quote:

Originally Posted by laserlight

Consider the scenario of coin flipping. When you flip a coin, you generate 1 bit of random information. So, if you flip a coin 8 times, you should get 8 bits of random information. But suppose that the coin is not a fair coin, e.g., it is weighted on one side. Would you really still get 8 bits of random information after 8 flips?

The idea here is that you don't, e.g., you get 7 bits of random information.

Here's another version of the box: I have a weighted coin that 3/5 of the time lands heads. Let's make a bet on 20 flips, and you can call it, but to make it fair, whoever chooses heads needs 13 flips, whereas tails only needs 9 flips to win.

Heads or tails? Just kidding. The real question: why do my odds make this fair? For the same reason that a tie with a (perfectly weighted) coin on 20 flips is unlikely, even tho that coin has a 50/50 distribution.

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!

So perfect distribution is not (or should not be) the primary goal. It's an organizing principle. Do not reify it. Methinks this is an example of where experts sometimes lose -- the real world being not an ivory tower and all.

This is strong a criticism of my plain text algorithm, since it would appear that the longer the sample, the more likely you are to end up with a 47/53 split.

I would assume, however, that radioactive decay represents the same problem -- getting closer to a perfect 50/50 is not an improvement.

A perfect random bitstream generator would have the same odds of producing a stream of continuous zeros as a stream of continuous ones as a stream consisting of exactly 50% ones and exactly 50% zeros. There should be no ratio more likely than any other.

By aiming for perfect distribution, you reduce the entropic potential of your system.

I'm starting to believe the keyboard is not such a bad method at all.* Lemme set up the test differently: you play against the computer, and it uses perceptrons to guess your random sequence. Of course the first time it fails, but if you keep using the same technique, it may get better. So you vary your technique to include extreme cases that are unpredictable in context.

In light of all that, maybe doing mod 2 on plain text is not so great -- but it is probably about as good as radioactive decay (presuming radioactive decay represents a 50/50 distribution, which in all honest I have no idea).

I'm gonna assert the best key generator will have no predictable distribution at all.

Quote:

Originally Posted by Sebastiani

You don't actually need "true" randomness, IMO. Theoretically, a distribution close to 50% (of 0's and 1's) is most desirable,

Only if you are pragmatic :p, in which case maybe 47/53 is pragmatically close enough to the (far from perfectly random) 50/50.

One thought I had here would be to take if str[1] < str[2] reverse the skew (from 53/47 to 47/53). The generator that could be 47/53 or (just as likely) 53/47 is probably better than the one that is consistently 50/50.

* That paper supplied by pianorain, btw, was really really bad. That was a grade five level paper.
http://www.daimi.au.dk/~ivan/Pseudorandom05.pdf
Altho in grade five you would probably get an "A" for being earnest and serious. An "A" level paper for grade 5 students. I would be ashamed of myself if I prepared that paper as anything more than crude notes and vague ideas (that need some deep consideration) at a university.
03-17-2010
Sebastiani

Quote:

Originally Posted by MK27

Only if you are pragmatic :p, in which case maybe 47/53 is pragmatically close enough to the (far from perfectly random) 50/50.

One thought I had here would be to take if str[1] < str[2] reverse the skew (from 53/47 to 47/53). The generator that could be 47/53 or (just as likely) 53/47 is probably better than the one that is consistently 50/50.

Well right, which is why I said "close to". Hell, 80/20 would still work, but staying close to the optimal distribution just makes things that much more secure. You could monitor that by analysing the entire resultant key or the individual bytes, but the former would likely be most effective (though probably slower). The most important aspect, though, is checking that large predictable blocks don't arise in the key. A CRC type algorithm, or similar, might help prevent that from happening, though.
03-17-2010
brewbuck

Laserlight's example of the coin flip is correct. An unfair (non-50/50) coin results in less than 1 bit of information per flip. Suppose the coin is 40/60:

H(flip) = -P(tail)*lg2(P(tail)) -P(head)*lg2(P(head))
= -0.6*lg2(0.6)-0.4*lg2(0.4)
= 0.971 bits per flip

The fact that it is still random is not the point. The INFORMATION is what matters. If a 1 bit is more probable than a 0 bit, then you can simply guess that all bits of the key are 1, and the majority of decrypted bits will be correct.
03-17-2010
whiteflags

Quote:

Originally Posted by MK27

IF I, AS THE CRACKER, KNOW THAT YOU ARE OBSESSED WITH PERFECT DISTRIBUTION, GUESS WHAT JUST HAPPENED? HA HA HA!

What do you think this means?
03-17-2010
Mario F.

Quote:

Originally Posted by MK27

I'm gonna assert the best key generator will have no predictable distribution at all.

This is essentially my argument and also supported by Schneider. And I couldn't have put it better than you did.

Essentially, issues like distribution serve our purposes only downstream, after the sequence or the algorithm is known in order to constitute a case for or against randomness. They are properties of the Randomness. They are not however defining. This is very important, because in the face of a less than optimal RNG, we still have randomness.

It's essential at this point to remember everyone that there is no formal definition for randomness. This every expert agrees and non experts like ourselves will, with more or less effort, come to realize. And I think anyone doubtful of the how meaningful this argument is, I suggest you stop and think for a moment how relevant to the discussion are the words "No Formal Definition". In laymen terms it simply means we don't know what randomness is! Which leads also to we cannot measure randomness.

What with our limited knowledge of "How Things Work" we have been doing, is find systems that can generate Unpredictable and Non Duplicable (sp? help me here folks) sequences. That's all. And that's what I believe Schneider stresses. And what variables like Distribution or Periodicity are, is just intelligent, yet limited, methods to somehow measure these two characteristics.

As MK so well puts, an good RNG is in fact a system without even a predictable distribution. And this is what we have been observing in those cases in nature where we have been looking for RNGs (like radioactive decay, dice, and I insist randomly typing at a keyboard, or randomly moving the mouse on the screen).

PRNGs are more easily measure because they rely simply on smart mathematics. The nature of the system is at the reach of anyone. Here I do not support anymore that anything less than an optimal distribution is desirable, simply because PRNGs are purely deterministic and as such a less than optimal distribution greatly facilitates the prediction and duplication of results. So this is where I depart from MK. An optimal distribution (say, that 50/50) actually makes it more difficult to predict the result. Not easier because I found the distribution.
03-17-2010
MK27

Quote:

Originally Posted by brewbuck

The fact that it is still random is not the point. The INFORMATION is what matters. If a 1 bit is more probable than a 0 bit, then you can simply guess that all bits of the key are 1, and the majority of decrypted bits will be correct.

If you promise me a 50/50 distribution, I can just guess one bit or the other and get half the bits correct. Getting a few percent more is not much difference.

So if a perfect algorithm results in me easily solving 50% of the key, and an imperfect one 53%, your idea of the right vs. wrong way to do things here is delusional. You recite all the liturgy you want. Delusion. The cheese smells in Denmark, and all that. Again:

Quote:

A perfect random bitstream generator would have the same odds of producing a stream of continuous zeros as a stream of continuous ones as a stream consisting of exactly 50% ones and exactly 50% zeros. There should be no ratio more likely than any other.

By aiming for perfect distribution, you reduce the entropic potential of your system.

Around and around...
03-17-2010
Sebastiani

Quote:

Originally Posted by Mario F.

It's essential at this point to remember everyone that there is no formal definition for randomness. This every expert agrees and non experts like ourselves will, with more or less effort, come to realize. And I think anyone doubtful of the how meaningful this argument is, I suggest you stop and think for a moment how relevant to the discussion are the words "No Formal Definition". In laymen terms it simply means we don't know what randomness is! Which leads also to we cannot measure randomness.

What with our limited knowledge of "How Things Work" we have been doing, is find systems that can generate Unpredictable and Non Duplicable (sp? help me here folks) sequences. That's all. And that's what I believe Schneider stresses. And what variables like Distribution or Periodicity are, is just intelligent, yet limited, methods to somehow measure these two characteristics.

It all boils down to entropy, but essentially yes, you are correct - it cannot be measured directly, or rather, so tangibly. Entropy is, after all, in the eye of the encoder! You really have to take an heuristic approach in cases like this, to see the forest from the trees...
03-17-2010
Mario F.

Quote:

Originally Posted by MK27

If you promise me a 50/50 distribution, I can just guess one bit or the other and get half the bits correct.

Hmm... this is a shocking statement. You are forgetting that you don't need to know the distribution. if you are bruteforcing, a lower distribution will essentially mean you will find more correct bits, even if you don't know what the actual distribution is.

Example:
If you have a 1/2 distribution, you will find half of the correct bits. If you have a lower 2/3 distribution you will find 2 thirds of the correct bits regardless of knowing or not what the distribution is, simply by guessing.

Again, this does not remove the random nature of the sequence. I agree there. But especially for PRNGs where the remaining bits are weakened by a known, measurable and deterministic system, this is death.
03-17-2010
MK27

Quote:

Originally Posted by Sebastiani

It all boils down to entropy, but essentially yes, you are correct - it cannot be measured directly, or rather, so tangibly. Entropy is, after all, in the eye of the encoder! You really have to take an heuristic approach in cases like this, to see the forest from the trees...

:p I was gonna site that little gem of Mario's too. The emperor wears no clothes!

Reminded me of a Derek Jarman movie about Wittgenstein, where he (L.W.) suddenly recognizes something about his own myopic vision of the "ice world".

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 :p

The point being, there are no random sources, only entropic wells to tap.
03-17-2010
Mario F.

Yah, but i still had no one correct my spelling there. Help?
03-17-2010
whiteflags

I think where everyone has a cerebral disconnect is where distribution applies. Some of us seem to think that uniform distribution means that out of all generated data, the data will appear in equal quantities, such that you can guess 1/nth of it by brute force. Not at all the case. It just means that you've selected something that may "seem right".

In cryptography especially, seeming right is tantamount to disaster. The output of an rng has nothing to do with its randomness, it's how random it is going to be. If a generator favors 1 as opposed to 0 by whatever amount... it may produce things that are very random... but without an equal probability, I just cannot define something as random. There's always some other factor.

The whole point of a period in a random system is after x tries, there is no choice, it's going to repeat the period, unless the prng is self modifying (and that would be interesting).

I just start to wonder if I make sense to anyone at all. :o
03-17-2010
MK27

Quote:

Originally Posted by whiteflags

Some of us seem to think that uniform distribution means that out of all generated data, the data will appear in equal quantities, such that you can guess 1/nth of it by brute force. Not at all the case.

So you could get a stream of all ones with a uniform distribution, is what you are saying. I guess so!

Quote:

If a generator favors 1 as opposed to 0 by whatever amount... it may produce things that are very random... but without an equal probability, I just cannot define something as random. There's always some other factor.

You are still hung-up on this REIFIED idea of randomness. You need to read some critiques of Platonism my friend!

If a generator does not favor 1 or 0 zero by any amount, then it must favor a uniform distribution. That is not random.

Quote:

A perfect random bitstream generator would have the same odds of producing a stream of continuous zeros as a stream of continuous ones as a stream consisting of exactly 50% ones and exactly 50% zeros. There should be no ratio more likely than any other.

Given infinite time and computing power, what kind of distribution would you assign to such a generator at the end? Uniform? ;)

Do you see some paradoxical problems starting to form? There are a few routes to a uniform distribution. And the one that makes it there first is not the winner! Therefore: you can never declare a distribution uniform until you have all the data the generator will ever produce! You are just guesstimating the truth!

It's all because of that reification fallacy. I'm starting to understand where this came from...:p

Quote:

Originally Posted by whiteflags

I just start to wonder if I make sense to anyone at all. :o
03-17-2010
whiteflags

In a word, yes!

I want you to fully understand my point, so I am going to use the same quote.

"A perfect random bitstream generator would have the same odds of producing a stream of continuous zeros as a stream of continuous ones as a stream consisting of exactly 50% ones and exactly 50% zeros. There should be no ratio more likely than any other."

Except, with dice, 1/6 is not greater than 1/6. With bits, a system that has an equal number of ones as to choose from as outcomes, versus an equal number of zeros, is going to be perfectly random. If you choose a source that maps to 47 zeros amd 53 ones, that's not going to be random, according to your own damn quote, because a one is more favorable than zero.

This is why I kept telling you I don't care how you nigger rig the results so that there are 50 zeros and 50 ones, or whatever. You cannot determine randomness through output. A stream of ones is as likely as a stream of zeros if the outcomes are equally likely. This is distribution. Distribution has nothing to do with output. Bold, capitals, color. I have been trying to explain this to you the whole time. The keyboard is not a random source because you have not shown me a keyboard that maps to an equal number of ones and zeros.

If you don't want to believe that, you misunderstand your own quote.
03-17-2010
laserlight

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.
03-17-2010
NeonBlack

Quote:

Originally Posted by laserlight

God does not play dice with the universe.

God can do whatever the hell he wants to.
03-17-2010
Mario F.

Quote:

Originally Posted by whiteflags

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.
03-17-2010
whiteflags

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.)

Quote:

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.
03-18-2010
Mario F.

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.
03-18-2010
kryptkat

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 ?
03-18-2010
Mario F.

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 ?

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.
03-18-2010
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. 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.
03-18-2010
laserlight

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.
03-18-2010
Sebastiani

Quote:

Originally Posted by laserlight

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

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.
03-18-2010
laserlight

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.
03-19-2010
pianorain
Quote:

Originally Posted by MK27

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.
03-19-2010
laserlight

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.
03-19-2010
kryptkat

Quote:

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.
03-19-2010
laserlight

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.
03-19-2010
kryptkat

no not freq analysis. rolling the same char over the entire file. a roll up like you would do with caesar . do each char then put together the ones that stand out as the char rolled with the rest to make text. brute force of a single letter at a time. by the xor logic.
03-19-2010
pianorain

Quote:

Originally Posted by kryptkat

the ones that stand out

If you can provided a working definition of how to determine which pieces of data 'stand out' and are correct, then this method is valid.
03-21-2010
kryptkat

i have been thinking about what you have said. i am not so sure the user or one brute forcing the one time pad file actually has to recognize 100% of everything.

here is why.

example. attacker has no knowledge of what the one time pad contains. brute forces file. by the same token that when you look in the temporary files folder everything has a .tmp extension. when you open one of those files after copying the entire contents to another folder with notepad you will see a few characters that specify what type of file it is 99% of the time. eighter by bmp or avi or mpeg or jpg or wpc or mz whatever. one of them is backwards i think it is swf so you might see fws. that would be part of the files header. you may not recognize any of the rest of the ascii characters as instructions or data but by seeing the header specifyier you would know exactly what type of file it is. all that is left is to change the extension and load it in to a program that uses that file format. a bit map viewer if .bmp or mpeg player if .mpg etc. with the brute force a program to run through say .bmp if had header of bmp flip through all the files and "see which one comes in to focus" or is clear image. like before it was encrypted with a one time pad. a program made to flip through each file at one .bmp per second and stop when user hits button. ideally stopping at correct image. or if a video stream or mpeg file let run to see which is played properly. with mz extension changed to .exe as executable and run on a machine not connected to anything or have anything of value on it to see what it does. again attacker just finds correct file with out recognizing 100% of contents. by just going for a header attack. may end up trying many different file types and will if any type of file format <see any rfc pertaining to file formats> had been encrypted with a one time pad. except for solely raw data <no header> i would like to remind you that most text programs or text editors such as .wpd or .doc use a file formatted data containing a header file type specifier.
03-21-2010
laserlight
There are two reasons why your idea does not work against a one time pad:
- Brute force is insufficient to determine the header as the portion of ciphertext corresponding to the header, like the rest of the ciphertext, depends entirely on the key.
- Even if you know the header by some other means, brute force is insufficient to determine the contents, for the same reason. Recall that the key used for the header and the key used for the contents are different, so obtaining the key used for the header is no help. Granted, the attacker has some idea of what the contents would look like, but he/she still is unable to determine the correct contents from among all the possible contents of the same length.
On the other hand, for ciphers that are not equivalent to a one time pad, your idea is a good one as it means that the cryptanalyst has useful information about plaintext and corresponding ciphertext.
03-21-2010
Mario F.

Kryptkat, but you are still confronted with the real problem of decrypting the BMP contents. You may even know a priori the cipher hides a BMP file. Let's assume that. But each byte in a one-time pad is entirely independent of the other bytes. So, you will have an infinite number of possible matches in which a BMP header will be revealed but which data blocks will show all sorts of images. From a rather intense bitmaped version of a nude Mona Lisa, to 2428 different bitmaps showing possible plans for a nuclear bomb.
03-21-2010
Salem

I can't believe this thread is still going.

Or that kk is still spouting nonsense.

> blah blah ... with the brute force a program to run through say .bmp if had header of bmp flip ... blah blah
So you "brute force" "d!" into "BM" and you latch onto that it might be a BMP file.

So how are you going to validate the next 4 bytes (the length). That's every combination from zero to 4GB. Some of those combinations will be printable characters in themselves.
So one such permutation will be "X BI"

Do you now revise your guessing that it is a text file beginning with "BMX BI" and then try and take a shot at the next few characters being "KES FOR SALE".

By the same token, it may still be a very large BMP file. So how are you going to choose?

All that blather about files in the tmp directory is irrelevant. If the attacker has your disk, there's no need to brute force a damn thing.
03-22-2010
kryptkat

Quote:

but you are still confronted with the real problem of decrypting the BMP contents.
....

Brute force is insufficient to determine the header as the portion of ciphertext corresponding to the header, like the rest of the ciphertext, depends entirely on the key.
....
So how are you going to validate the next 4 bytes (the length). That's every combination from zero to 4GB. Some of those combinations will be printable characters in themselves.
So one such permutation will be "X BI"

i am saying look at the data files that the brute force program made. it tried every possible key from 0 0 0 0 0 0 0 0 ==> too end length of file too 256 256 256 256 256 256 256 256 ==> too end length of file. a file corresponding to each key. i am saying look for something that looks like a header and try a program that would use that type of file. with the few exceptions ie mz or raw data etc. find the image or video stream that comes in to focus.... plays or displays with out any data corruption. this is a weakness in the vernam encryption. <xor rand() run>

Quote:

So, you will have an infinite number of possible matches in which a BMP header will be revealed but which data blocks will show all sorts of images. From a rather intense bitmaped version of a nude Mona Lisa, to 2428 different bitmaps showing possible plans for a nuclear bomb.

i likie the porn generator idea better. woohoo free kitty porn.
03-22-2010
laserlight

Quote:

Originally Posted by kryptkat

i am saying look for something that looks like a header and try a program that would use that type of file. with the few exceptions ie mz or raw data etc. find the image or video stream that comes in to focus.... plays or displays with out any data corruption. this is a weakness in the vernam encryption.

You are still missing the point: you can find many images or video streams that come into focus. They all play or display perfectly well without any data corruption, and they all seem equally likely to be the plaintext. Therefore, this weakness that you speak of does not exist when a one time pad is correctly used.
03-22-2010
Mario F.

This is hopeless kryptkat. You aren't making any effort to understand the arguments being produced here and still have no idea what a One-Time pad is. Since you insist it is breakable, it clearly reveals you have no idea what you are talking about.

But that would be ok, if it didn't take 15 f*** pages to teach you and you still didn't get it. Go cure your idiocy somewhere else.
03-22-2010
Sebastiani

Quote:

Originally Posted by kryptkat

i am saying look at the data files that the brute force program made. it tried every possible key from 0 0 0 0 0 0 0 0 ==> too end length of file too 256 256 256 256 256 256 256 256 ==> too end length of file. a file corresponding to each key. i am saying look for something that looks like a header and try a program that would use that type of file. with the few exceptions ie mz or raw data etc. find the image or video stream that comes in to focus.... plays or displays with out any data corruption. this is a weakness in the vernam encryption. <xor rand() run>
i likie the porn generator idea better. woohoo free kitty porn.

The "One Time Pad" scheme does have one weakness, actually - the number 11. The reason why this is so is because it corresponds closest to the number 2, and since it comes after 10 (which *is* the number 2 in base 2, btw), representing the decimal system that we use today. Decimal is used because the metric system doesn't work with other number bases. Anyway, the number 11 always has it's lowest bit set (always), and that's the key to cracking this OTP® thing. If you XOR every byte with 11 you get a value that, when XOR'ed with the original value, yields...you guessed it - 11! This suprising property can be used to reveal the Legendre symbol (I think). Even though you can't factor the OTP®, you can inspect it's symbols for "flak". These are extra bits that represent anomolies in the data. This is where the number 11 comes in to play. Hth.
03-22-2010
EVOEx

Quote:

Originally Posted by Sebastiani

The "One Time Pad" scheme does have one weakness, actually - the number 11. The reason why this is so is because it corresponds closest to the number 2, and since it comes after 10 (which *is* the number 2 in base 2, btw), representing the decimal system that we use today. Decimal is used because the metric system doesn't work with other number bases. Anyway, the number 11 always has it's lowest bit set (always), and that's the key to cracking this OTP® thing. If you XOR every byte with 11 you get a value that, when XOR'ed with the original value, yields...you guessed it - 11! This suprising property can be used to reveal the Legendre symbol (I think). Even though you can't factor the OTP®, you can inspect it's symbols for "flak". These are extra bits that represent anomolies in the data. This is where the number 11 comes in to play. Hth.

You're 100% correct! Great explanation.
(I bet you were right laserlight :P)

Quote:

Originally Posted by kryptkat

i am saying look at the data files that the brute force program made. it tried every possible key from 0 0 0 0 0 0 0 0 ==> too end length of file too 256 256 256 256 256 256 256 256 ==> too end length of file. a file corresponding to each key. i am saying look for something that looks like a header and try a program that would use that type of file. with the few exceptions ie mz or raw data etc. find the image or video stream that comes in to focus.... plays or displays with out any data corruption. this is a weakness in the vernam encryption. <xor rand() run>

Please tell me this is a joke, because otherwise you STILL don't get it.
If you try every combination from 0 0 0 0 0 ... 0 to 255 255 255 255 ... 255 in the length of the file, then ANY FILE of the same length will be a decrypted version of that string using the proper key. That is, let's say we have an encrypted text "00 00 00", then if you get to key "79 65 73", the output is "yes". Is this correct? Maybe. But when you get to key "41 53 53", the output is "ASS". Is this correct? Who knows!
And so on. For any three letter word there will be a key so that it decrypts to that word. And using an actual one time pad (and not MK27's algorithm :P), there is no way of which key was the right one without knowing the key.
03-22-2010
Mario F.

Sebastiani was obviously joking. There's only one person here who still doesn't understand the properties of a One-Time pad, not because it hasn't been explained to them, but because they don't make an effort trying to understand what has been told to them for the last 15 pages. Which does make them rather dense... or a troll... or both. And that person is not Sebastiani. Trust me.
03-22-2010
kryptkat

Quote:

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.

if what would be done in red were done all you would end up with is key files. i would call that a standard key file. only good for a file of that length. if no xor was done there would be less likely chances of recovering the data. the question becomes "is data analysis part of cryptanalysis ?" by looking through each xored file. each one file increment by one <last byte> in the key. until the last key.

i insist that for video or pictures and most formatted file types
that ONE of those files from a brute force using every key will be the correct one. unless you can prove that the "porn generator" would really happen. there would be only one "focused" image or video stream. as for text that would be harder to say which one is correct. going to external intel if you have that. i do understand and believe it is a matter of trying every data file the question becomes "is data analysis part of cryptanalysis ?"
03-22-2010
EVOEx

Quote:

Originally Posted by kryptkat

if what would be done in red were done all you would end up with is key files. i would call that a standard key file. only good for a file of that length. if no xor was done there would be less likely chances of recovering the data. the question becomes "is data analysis part of cryptanalysis ?" by looking through each xored file. each one file increment by one <last byte> in the key. until the last key.

i insist that for video or pictures and most formatted file types
that ONE of those files from a brute force using every key will be the correct one. unless you can prove that the "porn generator" would really happen. there would be only one "focused" image or video stream. as for text that would be harder to say which one is correct. going to external intel if you have that. i do understand and believe it is a matter of trying every data file the question becomes "is data analysis part of cryptanalysis ?"

I didn't read the entire thread, but damn, are you a troll? I think you must be. I've seen others say it but now I've seen it for myself. Otherwise, re-read my last message.
And the part you quoted is WRONG. Where did that come from? Well, you can find out the key if you remember the plaintext EXACTLY.
03-22-2010
laserlight

Quote:

Originally Posted by kryptkat

if what would be done in red were done all you would end up with is key files. i would call that a standard key file. only good for a file of that length.

Err... the key of a one time pad cipher is indeed only good for a file (or whatever plaintext) of that length.

Quote:

Originally Posted by kryptkat

i insist that for video or pictures and most formatted file types
that ONE of those files from a brute force using every key will be the correct one.

I insist, and know for sure, that for all kinds of plaintext, one of the possible plaintexts obtained by brute force will be the correct one. That as much is self-evident.

Quote:

Originally Posted by kryptkat

there would be only one "focused" image or video stream.

But this is wrong. There will be many "focused" images or video streams, all of which are equally likely to be the correct one.

Quote:

Originally Posted by kryptkat

i do understand and believe it is a matter of trying every data file the question becomes "is data analysis part of cryptanalysis ?"

There is no data to analyse since all that you are doing is pure guesswork, not intelligent guesswork, because there is no information about the plaintext to be obtained from the ciphertext, other than perhaps the length of the plaintext.
03-29-2010
kryptkat

i think a demo is in order. the original image is at the left. the following image was brute forced.
one of the images is 45% of the correct key. one of the images is 60% of the correct key. one of the images is 100% the correct key. i will let you make up your own mind as to which image is the correct key. all i did was enlarge the image by two only to show the distortion more clearly.
<meow "show the distortion more clearly" > i will let you make up your own mind to how much of the actual image you really need to make a positive identification.

i would like to conclude this debate with the demo. thank you all for participating in the debate.

real life example.
there was this file of pedo that put up on the internet a image of himself that was swirled. he thought that it could not be unswirled. someone unswirled that image enough for law enforcement to make a positive identification. it was on amw. although it was not a one time pad it is a good example of what can be done and how much it takes to make a positive identification. as i recall it was undone about 80%.

analogy.
if there was a brand new car in front of you. behind you is this large warehouse filled with millions of keys. if it were a contest they would put a time limit on you so that you would be less likely to unlock the car and drive off with it the winner. for the analogy we will give you all the time it takes to try every single key. for one individual that would be a long chore. it might take you four weeks or more. but for an agency or large corporation they could put many employees on the task to find the correct key. that would shorten the time it takes to find the correct key.
with a file it is more of a matter of percentage of file undone with the correct key for that byte. i like the focus analogy or percent of file undone.

yes i had a little fun with the porn generator concept to make a point. remember you were the ones saying "you can not see the tree through all the woodies".

no i am not a troll and i am not trolling. the quote put up with red in it was what laserlight said. the demo should show you what really happens based on actual experience.

this concludes the one time pad debate.
03-29-2010
Mario F.

Kryptkat,

Under a one-time pad, and for that exact same file you show here, you would have other possible keys showing the exact same effect. Only, instead of laserlight cute avatar you would be seeing mine. In other keys you would be seeing yours, in other keys laserlight avatar would be blonde (nooo!), and in other keys you would have a text file with a portion of the United States Declaration of Independence in Romanian. Other keys would result in a wave file with a rather poignant Kumbaya interpretation (which you would unfortunately miss because the file was too small).

Even assuming you would have knowledge on the format of the message and could discard the wave file and the text file, how could you know the real image between the millions, billions, trillions, [...] of possible combinations resulting in a valid image?

Aren't you aware that you actually didn't yet understand the implications of a one-time pad?
03-29-2010
pianorain

Like Mario said, assuming that you knew for a fact that it was an image file and only the image had been touched with the one time pad, you would still have to account for every possible image of that size.

You say you've brute-forced your way to laserlight's avatar. That's interesting. Did you find any keys that looked like anyone else's avatar? For example, let's say that laserlight's avatar is the encrypted message. Well, this key turns laserlight's avatar into MK27's avatar. Ah-ha! That must be the encrypted message, right? Well, no. This key turns laserlight's avatar into brewbuck's avatar. So, which is it? Which interpretation is correct?

Also, you have provided no source code. This would be helpful to determine you've done what you've actually said. Here is my source code that generates the keys above and verifies that they correctly turn laserlight's avatar into other avatars.

Obviously, these keys are just as valid as any other. A full brute-force search of possible keys would generate these keys as well as trillions of others. This is why OTP cannot be broken. You cannot distinguish the correct message from the overwhelming number of false positives.
03-29-2010
bernt

i think a demo is in order. the original image is at the left. the following images were brute forced.

sorry, couldn't help myself.
03-29-2010
brewbuck

Quote:

Originally Posted by pianorain

You cannot distinguish the correct message from the overwhelming number of false positives.

I prefer other explanations, because this way of looking at it leads some people to think that if only there was "some way" to sieve through the results to find "true" positives, the method could be broken.

At its heart, the problem is an information-theoretic one. Each plaintext bit is modified by a completely random key bit. This obliterates the information in the ciphertext, by making the distribution of the ciphertext precisely equal to the distribution of the key. Any deviation from the uniform case is wiped away. In other words, the conditional entropy of the plaintext given the key, is equal to the entropy of the key. Without knowledge of the key, there is no information about the plaintext. The ability to always find a key which decrypts to an arbitrary plaintext, seems to fall on some peoples' deaf ears.

And by the way, I'm glad people are fooling around with the program I posted. There is a way to use it to generate arbitrary keys to decrypt ciphertexts into arbitrary plaintexts, and you guys obviously have figured out how to do it. It's not really that hard, given some basic knowledge of the way XOR works.
03-30-2010
EVOEx

Quote:

Originally Posted by kryptkat

analogy.
if there was a brand new car in front of you. behind you is this large warehouse filled with millions of keys. if it were a contest they would put a time limit on you so that you would be less likely to unlock the car and drive off with it the winner. for the analogy we will give you all the time it takes to try every single key. for one individual that would be a long chore. it might take you four weeks or more. but for an agency or large corporation they could put many employees on the task to find the correct key. that would shorten the time it takes to find the correct key.
with a file it is more of a matter of percentage of file undone with the correct key for that byte. i like the focus analogy or percent of file undone.

@bernt: Nice work ;-). Although I doubt it'll make kryptkat understand.

Wow. Okay. This is hopeless, but I'm going to give it one more try.
Your analogy is off. Let me give you a good analogy:
Let's say you have X keys. However, each key unlocks a box and in each box, there is a text. Some might make sense, some might not. That's the situation with one time pads. Now, there are 2^(8*100) possible keys for a 100 byte string. Well, it doesn't even matter that's a lot (I think it's a lot more than the number of atoms in the universe), but worse is that each key unlocks one box. And one out of a million boxes contain a meaningful message. You can never know which message was intended.

I even showed you how a single encrypted message could be any word of the same length. Did you even read that message? Did you fail to understand it and simply decide not to reply?

Funny how you claim that a wrong message, showing that you still don't grasp the concept after so many pages, can conclude the discussion.
03-30-2010
laserlight

Emphasis mine:

Quote:

Originally Posted by kryptkat

real life example.
there was this file of pedo that put up on the internet a image of himself that was swirled. he thought that it could not be unswirled. someone unswirled that image enough for law enforcement to make a positive identification. it was on amw. although it was not a one time pad it is a good example of what can be done and how much it takes to make a positive identification. as i recall it was undone about 80%.

The part in bold means that your "real life example" is completely invalid. Completely.

The "swirl" is akin to the use of other cryptosystems, where at least in theory it is possible to obtain the plaintext from sufficient ciphertext by brute force. In fact, since the "swirl" is not designed for encryption, it means that it is much weaker, i.e., more like "snake oil" encryption than AES.

Quote:

Originally Posted by kryptkat

no i am not a troll and i am not trolling. the quote put up with red in it was what laserlight said. the demo should show you what really happens based on actual experience.

Your "actual experience" is faked. You merely went through an exercise designed to appear as if you broke a one time pad, and perhaps you actually managed to fool yourself. Fortunately, this does not fool anyone who understands the information theoretic perfect secrecy provided by the correct use of a one time pad.

Quote:

Originally Posted by kryptkat

this concludes the one time pad debate.

I can agree with this. It concludes that you do not understand why the correct use of a one time pad provides information theoretic perfect secrecy, despite the best efforts of many to help you to understand.

If you still believe that everyone else is wrong, then write a paper. Publish it. Speak at conferences. Become world famous. Every introductory textbook to cryptography (and some more advanced ones, and probably also those on computer security in general) will have to be corrected due to your findings.
03-30-2010
jwenting

It is in theory possible to break the encryption on a one-time pad and receive the cleartext as a result through brute force BUT by definition you'd only have that one message decrypted.
Any other message encrypted using a one-time pad, even one generated using the same system, would still be undecipherable except through the same brute force approach, the previous success providing no basis at all on which to shorten the time required for the decoding effort.

While retrieving that one message might yield valuable information to the party doing the decryption, by the time this has been achieved and verified to be at least a feasible decryption (rather than something completely unrelated, see prior responses) the information encrypted using the one-time pad will usually be outdated and no longer of operational value to the intercepting parties (which is the purpose of using encryption at all, slowing down a potential opponent's efforts at reading your communications until such a time as that communication is no longer relevant to your efforts).
03-30-2010
laserlight

Quote:

Originally Posted by jwenting

It is in theory possible to break the encryption on a one-time pad and receive the cleartext as a result through brute force BUT by definition you'd only have that one message decrypted.

What do you mean by "by definition you'd only have that one message decrypted"?

Quote:

Originally Posted by jwenting

Any other message encrypted using a one-time pad, even one generated using the same system, would still be undecipherable except through the same brute force approach, the previous success providing no basis at all on which to shorten the time required for the decoding effort.

What do you mean by "one generated using the same system"?

Quote:

Originally Posted by jwenting

While retrieving that one message might yield valuable information to the party doing the decryption, by the time this has been achieved and verified to be at least a feasible decryption (rather than something completely unrelated, see prior responses) the information encrypted using the one-time pad will usually be outdated and no longer of operational value to the intercepting parties

Well, it is more than that, actually: in order to verify that the decrypted message is indeed the plaintext, the attacker must have sufficient external information such that he/she does not need the ciphertext in the first place.
03-30-2010
Mario F.

God! And full circle we come back to the first post.

What a complete nonsense!
03-30-2010
jwenting

Quote:

What do you mean by "by definition you'd only have that one message decrypted"?

Which part don't you understand?
He'd have that single message, and no means to get any other.
That's the nature of the one-time pad.

Quote:

What do you mean by "one generated using the same system"?

Another pad created by the same generator, obviously.
Do you think the NSA writes a new generator for every key they generate?
Or a new generator generator?

Quote:

Well, it is more than that, actually: in order to verify that the decrypted message is indeed the plaintext, the attacker must have sufficient external information such that he/she does not need the ciphertext in the first place.

Conceivably so. And at the time he has succeeded deciphering it he'll have that information or otherwise no longer need to attain it, making the effort pointless.
For example the message might be about an impending military operation against him. By the time he breaks the code, the operation will have been long since executed.
03-30-2010
rogster001

Quote:

And at the time he has succeeded deciphering it he'll have that information or otherwise no longer need to attain it, making the effort pointless.
For example the message might be about an impending military operation against him. By the time he breaks the code, the operation will have been long since executed.

this sort of thing has been pointed out already, in another thread and early in this one, probably about twenty times in this endless thread haha

we are lumbering toward the semantics debate again, i am going to try and derail it already >>

The verb "to break" in the context of decrypting a coded message means > 'reveal the message intended by the person(s) that coded the message to start with'

it does not mean "succeed in distilling any kind of coherent message At All from the coded document"

which is what some people have argued most pedantically
03-30-2010
EVOEx

Quote:

Originally Posted by jwenting

Conceivably so. And at the time he has succeeded deciphering it he'll have that information or otherwise no longer need to attain it, making the effort pointless.
For example the message might be about an impending military operation against him. By the time he breaks the code, the operation will have been long since executed.

Actually, either I don't understand this part well enough or you fail to understand one time pads as well. Because you don't have any bit of information about decoding it. Even if you know everything about the operation, even if you know half of the plain text, you can NEVER KNOW the rest. Even if the military operation has been executed a hundred times. Not only practically impossible (eg. that the world will be destructed before you can crack it) but actually theoretically impossible (eg. that if you had an infinite amount of resources and time, you still wouldn't be able to get any bit of information from the message).
03-30-2010
laserlight

Quote:

Originally Posted by jwenting

Which part don't you understand?
He'd have that single message, and no means to get any other.
That's the nature of the one-time pad.

The problem is, he will not "have that single message", unless it is obtained by some other way (e.g., torture). Brute force is not sufficient to break a correct use of a one time pad. That's the nature of the one-time pad.

Quote:

Originally Posted by jwenting

Another pad created by the same generator, obviously.
Do you think the NSA writes a new generator for every key they generate?
Or a new generator generator?

Sorry, but if you read this thread, you would see that we went into a discussion of random number generators. If you are talking about a pseudorandom number generator, then no, I am fairly certain that the NSA does not use PRNGs for one time pad key material. But if you are talking about a "real" RNG, then talking about "the same system" sounds strange.
03-31-2010
jwenting

AFAIK the NSA and others use interstellar background noise as a feed for their generators, with filters applied to remove recurring patterns.
That's as random as it comes.

And indeed, you can't ever know if what you got from a brute force attempt to decrypt something encrypted using a one time pad is the original message.
That's what makes it as secure as it is.
But that's not my point. Point is, it IS possible to brute force the original message, you'd just have a very hard time knowing when you'd succeeded :)

Show 80 post(s) from this thread on one page

All times are GMT -6. The time now is 11:01 PM.