Thread: one time pad breakable debate

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?

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.

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.

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.

Emphasis mine:

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.

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.

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.

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"?

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"?

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.

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

What a complete nonsense!

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

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.

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.