one time pad breakable debate

Originally Posted by Mario F.

But the seed is not the key. Hence why I put it in double quotes. The key will be generated by the seed. The mechanism for said generation is an RNG. Meaning the actual key can be generated on the fly and the decryption is made right after, as long as:

a) you possess the correct seed
b) you possess the correct RNG
c) you possess the correct decryption algorithm

According to Kerckhoffs' principle, the attacker knows the PRNG and decryption algorithm.

What you described is a possible use of a PRNG to implement a stream cipher. This can be secure with the use of a cryptographically secure PRNG, but it does not have the property of being unbreakable like a one time pad. By observing sufficient ciphertext, it is theoretically possible to determine the state of the PRNG, and thus break the encryption.

Originally Posted by laserlight

What you described is a possible use of a PRNG to implement a stream cipher. This can be secure with the use of a cryptographically secure PRNG, but it does not have the property of being unbreakable like a one time pad. By observing sufficient ciphertext, it is theoretically possible to determine the state of the PRNG, and thus break the encryption.

I promise I'll munch on that, laserlight. But you still will have the pad to deal with. I'm not weakening the security. I may eventually agree I'm not strengthening it either after I give it some thought. But that's not the point. You will still have to pass the pad. I'm only suggesting storing/distributing the key can be simplified.

Originally Posted by Mario F.

Note really MK. It would be sensible to store the RNG with the decryption algorithm.

Presuming the only secret part is the long int key, that does mean that your public decrytion algorithm w/ RNG can only have LONG_INT_MAX possible keys.

If you can keep the algorithm and the RNG secret, yeah, this could be more convenient, but then you are still stuck with all the security problems vis. storage and distribution of the algo & RNG. Also, this would no longer be a "one time" pad, since the algo and RNG are static.

The pad wasn't removed. The only thing happening is that I added another layer at the top to simplify the key distribution.

I really can't see what am I doing wrong trying to explain this. I kinda give up if you don't mind.

Originally Posted by Mario F.

I really can't see what am I doing wrong trying to explain this. I kinda give up if you don't mind.

Well ditto -- my point is, going by your method, if you have the algo and the RNG, you only have to deal with LONG_INT_MAX possible keys, not 2^(message length*8) possibilities.

As I think laserlight has indicated, that would mean this is not the same thing as a true one time pad, in which each bit is uniquely indeterminate -- a seeded RNG will not do that, it will produce LONG_INT_MAX patterns of bits: the bits are not uniquely indeterminate in relation to one another, they are in accord with the pattern contained in the RNG.

So it is encryption, but it is NOT a one time pad (and probably not as unbreakable). A true one time pad key generator will generate 2^8000 possible keys for a 1000 byte message. A RNG with a long int seed cannot do that. You need to add some complications/additional randomness (I think ssh or pgp will use concurrent system events to do this) -- which then excludes using a simple seed to reproduce the message key elsewhere (which is why a ssh/pgp key is longer than 8 bytes).

Originally Posted by Mario F.

But you still will have the pad to deal with. I'm not weakening the security.

Ah, but that does not mean anything. You see, all stream ciphers behave like one time pads. There is a keystream (a "pad") that is combined with the plaintext (e.g., by XOR). Block ciphers behave similiarly too, except that their "pads" come in blocks.

So what differentiates a one time pad and these other cryptosystems is that the number of possible keys is no less than the number of possible messages (and all are equally likely). Unfortunately, if you are basing your key selection on a seed, then this means that the number of possible seeds must be no less than the number of possible messages, and the PRNG must co-operate by generating different sequences for each seed.

But if the number of possible seeds is no less than the number of possible messages, your seeds can potentially be huge, thus negating the benefits of the scheme in the first place.

Yup. I promised I would think about it and I did.
I can see now what you guys are telling me. Slap me for not noticing the obvious. Well done.

Originally Posted by brewbuck

It only uses rand() if you don't provide your own key. I did not have a portable source of randomness. In reality, you would generate your own key from a truly random source and use that. Obviously, keys generated by PRNGs are not suitable because the seed is fixed length. But that isn't the point I'm making -- regardless of what key you use, I can easily produce a key that decrypts to any plaintext of my choice. The ability to do that doesn't depend on how secure the key is. If you doubt it, go ahead and generate your own random key -- I can do it regardless.

Well, anyway, so that you can demonstrate your point to the fullest extent, I've some data for you.

D5CB20FFEAEDE53CE741DAB3C3AA0713F4DDA2

It's a small message, but it was going to be. I picked the key by draws from a hat, so it should be sufficiently random.

Originally Posted by whiteflags

Well, anyway, so that you can demonstrate your point to the fullest extent, I've some data for you.

I've found a key! Here it is:

Code:

9CEB459180829C1C8220AEDAADCD27779BBAD1

What happens when you decrypt your ciphertext using this key?

Originally Posted by brewbuck

What happens when you decrypt your ciphertext using this key?

The hat re-appears.

Originally Posted by brewbuck

I've found a key! Here it is:

Code:

9CEB459180829C1C8220AEDAADCD27779BBAD1

You are soo wrong The key is obviously

Code:

91A4478CCA8C9759C732B7D2AFC6277095A9D1

Well i wrote a short paragraph, compiled and ran the program, here is the output of my ciphertext.txt file.
unfortunately the decrypt did not want to work, i tried several times differently, i dont know if i am missing something

i think i ran in to the same problems.

what i mean by exposed is that it is plain text even if it is hiding among the safety of the other plausible messages. therefore it is nude.... exposed.

much better to do with a copy of the key for a reassured confident claim of undoing a one time pad. sure.

laserlight quote
Huh? The key is supposed to be secret. A sane attacker who is in possession of the key (and knows the algorithm) would not bother with cryptanalysis. He/she would decrypt the ciphertext immediately. To talk about "a reassured confident claim of undoing a one time pad" in this context is thus rubbish.

you missed the point. confidence in knowing that is the correct answer not bragging rights.

Which also makes it, by the way, an excellent deniable encryption method. And it comes with plausible deniability as a bonus.

got to love that ! meow !

One time pads are usually implemented by XOR:

yes the standard one time pad is xor. we were discussing of using a full length size of the text key for vigenere as a one time pad. probably with out the chart reading would work too.

even an xor pad can be brute forced providing plain text. exposing the message along with a lot more text that has nothing to do with the message or key. even given all the extra it is still broken. what is done with the data is subjective and not relevant to it being broken.

even a short 13 char brute force generates 35 gigabytes of data. looking through the contest data 4 hours a day for a week i only got through 2 gigs. then did a shorter one. due to a programming error i made was the only reason type in key using the data did not work. if the program had worked correctly then that would have worked type in one key word at time with data.

As far as I know, historically one-time pads have indeed been broken (ones used by Soviet spies). But that was only because the opponents got hold of the key-books and / or the Soviets reused keys for several messages.

getting hold of the key books is a valid way of "breaking the one time pad". meow.

can we refrain from posting "break this" please and stick to the debate. thank you.

if your one time pad uses xor and 0 to 256 you can make a program to ignore anything that is not 'a' to 'z' or 'A' to 'Z' then use a spell checker to throw out nonwords. even though that will reduce the file size intelligence still has to be used to interpret any possible messages. the correct one or not.

breaking is a one time pad can be a quandary.

Originally Posted by kryptkat

if your one time pad uses xor and 0 to 256 you can make a program to ignore anything that is not 'a' to 'z' or 'A' to 'Z' then use a spell checker to throw out nonwords. even though that will reduce the file size intelligence still has to be used to interpret any possible messages. the correct one or not.

I think there might be job for you with the US government.

Three pages explaining this and the cat still didn't get it.
A gorilla would.

Consider the following original text: "We will meet in the 22/05/2007 and destroy the world at 12:05". After encryption, there's nothing you can do to successfully decrypt this without the key. All dates and times will be possible results in your decryption attempts. You will not know which one is true, unless you acquire that information outside the context of the cipher.

Originally Posted by kryptkat

what i mean by exposed is that it is plain text even if it is hiding among the safety of the other plausible messages. therefore it is nude.... exposed.

Then your definition of "exposed" is useless.

Originally Posted by kryptkat

you missed the point. confidence in knowing that is the correct answer not bragging rights.

I think you missed the point of encryption.

Originally Posted by kryptkat

getting hold of the key books is a valid way of "breaking the one time pad".

It is a valid way of breaking a specific use of encryption. However, it does not constitute breaking an encryption algorithm.

Originally Posted by kryptkat

even an xor pad can be brute forced providing plain text. exposing the message along with a lot more text that has nothing to do with the message or key. even given all the extra it is still broken. what is done with the data is subjective and not relevant to it being broken.

It is not broken. You are inventing your own terminology here.

The way I see it, using your definitions, there is indeed no encryption algorithm that, in theory, cannot be broken, since by "broken" you mean "can guess the message, even if you can never tell if it is the message". Now, shall the rest of us just go back to using Shannon's definition of perfect secrecy with respect to information theory and leave you wallowing in your own world?