Thread: one time pad breakable debate

Originally Posted by EVOEx

The trick is that you can actually KNOW when you have the proper key as both the input text as the decrypted text make sense. If that is true, you can be fairly sure you have the right combination, even though it is fairly unlikely you will find this using this algorithm.

Alright, here's what I see as your point, which at first glance is sort of feasible. This is the scrambled text, byte values for a 5 letter word:
41 211 90 7 146
All you have to do is find a 30 character "sensible" text that could generate a 30 bit key according to the known algorithm, %2, whereby that key will produce a five letter word and bingo -- that's gotta be it.

Wrong.

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

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

What's more, using text was only a suggestion -- the algo would work with garbage data too.

Originally Posted by laserlight

Unless it is feasible to guess the key source text.

Now you are proposing kryptkat's solution, since the source text would be synonymous with the key. It is not feasible to "guess" the text, you would have to gain possession of it. That's cheating!

Originally Posted by MK27

Now you are proposing kryptkat's solution, since the source text would be synonymous with the key. It is not feasible to "guess" the text, you would have to gain possession of it. That's cheating!

It is not cheating if you can determine that certain sets of text are much more likely to be used than others. It is only a one time pad if the pad is used once.

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.

The pad would only be used once.* One of the "statistics" thrown about Queens, where I live, is that there are more than 200 languages actively used by the residents. I presume these all have written forms and potentially ascii-ish forms too (if not, it could be accommodated); maybe we can rule out the ones that that use pictograms.

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

* someone else could by coincidence use the same one, but the same is true no matter how you generate it (it could have been used before).

Originally Posted by MK27

I presume these all have written forms and potentially ascii-ish forms too (if not, it could be accommodated); maybe we can rule out the ones that that use pictograms.

Unicode.

Originally Posted by MK27

The pad would only be used once. (...) That's a lot of available text.

The problem is that the sets of text are not all equally likely to be chosen by a given user. Recall why brute force can be effective in practice against hashed passwords (where a salt is not used): users tend to choose weak passwords for convenience, and these passwords are thus susceptible to a dictionary attack.

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

Originally Posted by EVOEx

Actually, very few combination of letters actually form something meaningful. Especially if the texts become longer. Try it; type 10 random characters and see how many make sense. The longer the text, the less combinations will make sense.
Especially if it takes context into account.

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

Arrgggh -- EVOEx, are you the kind of person that when you reach a T junction with this sign, you habitually turn left and are baffled by the oncoming traffic?

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

1011101100

Each of which could be any one of thirteen letters (let's ditch punctuation and spaces) -- I think you will find there is more than one possibility for any bit sequence. So there will always be a "meaningful" correspondence. You cannot reduce the number of possible keys this way...you will cause an "accident".

I'm still not sure what there is to debate about MK's idea. It may not be your traditional approach to randomness. But I cannot see how it is any less efficient.

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

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

The problem for anyone trying to break a one-time pad is not finding the key. Is finding the relevant original text among the near infinite number of possible matches.

Originally Posted by MK27

One way to get a truly random one-time pad would be to get the user to type randomly or whatever for 8X the length of the message, then do odd/even modulus on this pad to get bits.

No, this is wrong. You're relying on a human to be random. If humans were adequately random, brute force dictionary attacks would not work.

Originally Posted by MK27

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

1011101100

Each of which could be any one of thirteen letters.

This is irrelevant. We're not concerned with finding the text used to produce the ten random bits. We're only concerned with finding the ten bits. In this case, see above.

Humans are not random.

Originally Posted by pianorain

No, this is wrong. You're relying on a human to be random. If humans were adequately random, brute force dictionary attacks would not work.

He said randomly type on the keyboard.

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

This is irrelevant. We're not concerned with finding the text used to produce the ten random bits. We're only concerned with finding the ten bits. In this case, see above.

nope. You are interested in finding the solution to the cipher. Not in finding the key. Or better, your only hope to break a One-time Pad is trying to decipher the cipher. Not trying to find the key.

Originally Posted by Mario F.

He said randomly type on the keyboard.

Wait, did you just say "use a human as a PRNG"? Humans are not random.

Originally Posted by Mario F.

Here's a challenge: Type randomly on your keyboard for 30 seconds fast and furiously with all your fingers from both hands... Done?

Now, do it again. Wake me up in 20 or 30 years when you finally match the exact same sequence of characters.

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

Take a look at the ASCII keyboard under this scenario:

Code:

1 1 1 0 0 1 1 1 1 0
 1 1 0 0 1 0 0 1 0
  0 0 1 0 0 0 1

I hope I don't "randomly" draw all my characters from the Q row. That's a lot of 1's. Using the Z row isn't a good idea either - lots of 0's.

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

Originally Posted by pianorain

Wait, did you just say "use a human as a PRNG"? Humans are not random.

Really? Prove it. If you can, you just did science a big favor and answered one of the fundamental questions of humanity. Nobel Prize will be too little for you. Meanwhile, you may as well have proven we live in an entirely deterministic universe and the quest for randomness is forever a wild goose chase.

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

Take a look at the ASCII keyboard under this scenario:

Code:

1 1 1 0 0 1 1 1 1 0
 1 1 0 0 1 0 0 1 0
  0 0 1 0 0 0 1

Erm... I don't think you understood MK's algorithm.

Originally Posted by Mario F.

Erm... I don't think you understood MK's algorithm.

It seems to be emphatically stated many times.

Originally Posted by MK27

One way to get a truly random one-time pad would be to get the user to type randomly or whatever for 8X the length of the message, then do odd/even modulus on this pad to get bits.

Originally Posted by MK27

Look at a paragraph of text as an odd-even (binary) sequence based on ascii values. Every character transformed to 0 or 1. You are now looking at truly random natural data.

Originally Posted by MK27

Here is the alphabet:

10101010101010101010101010101010

Indeed, I doubt even MK27 understands his algorithm, considering in one place he says "random text" and yet:

Originally Posted by MK27

The best idea would be to just type words (the space character is even, but all the vowels are odd).

No. Not that type of understanding. But what his algorithm means.

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

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

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

EDit: Oh, and remember: That keyboard you draw... that's the key. But you don't know the key. So you can't draw it as you did. So, again how do you plan to decipher the pad?