UK government planning a database of every phone call and email by the public -- in the name of fighting terror....

[w¡n9Nµ7 §£@¥€r 123]

Another good explanation:

The one-time pad algorithm works by combining the message, whether text or digital bitstream, with an equal-length string of random numbers that serve as the key. Because the OTP key is the same size as the message, every possible unencrypted message is equally likely—hence, theoretically perfect security. Thus, encrypting a 1MB PowerPoint slide deck requires a key of almost 8.4 million random bits. Furthermore, to achieve this theoretical perfection, the key material must be perfectly random and never reused.

One problem is that generating perfectly random numbers is both virtually impossible and, for any given string, unprovable. According to Eric Weisstein at Wolfram Research’s MathWorld, “It is impossible to produce an arbitrarily long string of random digits and prove it is random.” Currently, the methods for generating the “truest” random numbers, those best suited for one-time pads, use some sort of unpredictable physical process, such as radio-active decay, thermal/electronic noise, or drift between multiple hardware clocks.

One-time pads being a symmetric cipher—that is, the encryption and decryption keys are identical—further necessitates that the lengthy keys be preshared to all parties in a communication channel. This one-to-one mapping of key to message partner also means a separate key for each, leading to a logistic nightmare managing the lengthy keys. For example, if you plan to send 100MB of encrypted material to 10 different parties, you need 1GB of perfectly random data—data that must be destroyed and never reused.

[mawilson 2,133]

Personally, I don't think an OTP is terribly useful as it depends on a secure means of transmitting the pad.

I think it's very useful -- in fact, more useful and secure than public-key cryptography.

Let's say you have my public key - how do you know for sure that it really is

my public key?

You could verify the key fingerprints with me over the phone, but what if the

government intercepted your call and replaced me with someone who sounds

like me?

I could get someone you know to sign and certify my public key with an exportable

signature, using his or her own private key, and assign it a high level of "trust"

on his or her keyring. In this case, my signed public key is as good as the

public key of the person you trust.

Ultimately, the only way to be sure is to meet in person and compare the keys.

But if we're going to do that, we might as well exchange one-time pads.

[w¡n9Nµ7 §£@¥€r 123]

Ultimately, the only way to be sure is to meet in person and compare the keys.

But if we're going to do that, we might as well exchange one-time pads.

Agreed, it works just fine as long as the messages are long enough (2^1,000,000,000 equally likely plaintext messages are more difficult to go through than 2^8) and it is possible to meet in person. Meeting in person isn't always possible. And, of course, the government (as long as we're being paranoid) could always send a lookalike in my stead

[SaadBell 0]

Too close to Big Brother for the likes of me.

[mawilson 2,133]

Ultimately, the only way to be sure is to meet in person and compare the keys.

But if we're going to do that, we might as well exchange one-time pads.

Agreed, it works just fine as long as the messages are long enough (2^1,000,000,000 equally likely plaintext messages are more difficult to go through than 2^8) and it is possible to meet in person. Meeting in person isn't always possible. And, of course, the government (as long as we're being paranoid) could always send a lookalike in my stead

You don't suppose Al Qaeda hosts key-signing parties for terrorists attending Jihadi training camps?

[w¡n9Nµ7 §£@¥€r 123]

That's a lot of pads. One per message, two per two-way transaction. If AQ does do that, then I hope we have infiltrators so they can get their hands on a few pads too!

[mawilson 2,133]

That's a lot of pads. One per message, two per two-way transaction. If AQ does do that, then I hope we have infiltrators so they can get their hands on a few pads too!

Well no - all they need is a USB key filled with random data, say 1GB.

If a message is less than 100K, that's good for 10,000 messages.

Of course if they start mailing PDFs of weapon designs and military

installations, they'll need a longer pad.

[w¡n9Nµ7 §£@¥€r 123]

And the longer the pad is, the more difficult it is to actually go through all the possible xor'd values from all the possible pads...

[mawilson 2,133]

And the longer the pad is, the more difficult it is to actually go through all the possible xor'd values from all the possible pads...

I'm not sure what you're saying. If the message is 5 bytes long, all you need is a 5-byte pad.

If the ciphertext is "7XH8^", what's the plaintext?

Algae? Group? Infer? Yokel? Sauté?

Could be any 5 letter word.

[w¡n9Nµ7 §£@¥€r 123]

The pad and the original message have to be of equal length for the xor, right? The length of the ciphertext will therefore be the same, right?

So if someone finds the ciphertext (-original message- xor pad), they know the length of the original message and of the pad.

So... if you know the pad is of length n, then there are 2^n (assuming messages are in binary) possible values of the pad, right? Those possible values could be generated (using charles' cray) and then each xor'd with the intercepted ciphertext to generate 2^n possible original messages.

If n is a small number, one could easily go through the set of possible original messages and guess which one was the original message.

If n is a large number, that becomes very difficult. Thus my statement that the longer the original message gets, the more secure.

Am I missing something?

Edited May 21, 2008 by VJ Troll

[Ban Hammer 13,352]

And the longer the pad is, the more difficult it is to actually go through all the possible xor'd values from all the possible pads...

I'm not sure what you're saying. If the message is 5 bytes long, all you need is a 5-byte pad.

If the ciphertext is "7XH8^", what's the plaintext?

Algae? Group? Infer? Yokel? Sauté?

Could be any 5 letter word.

jihad

[mawilson 2,133]

The pad and the original message have to be of equal length for the xor, right? The length of the ciphertext will therefore be the same, right?

So if someone finds the ciphertext (-original message- xor pad), they know the length of the original message and of the pad.

So... if you know the pad is of length n, then there are 2^n (assuming messages are in binary) possible values of the pad, right? Those possible values could be generated (using charles' cray) and then each xor'd with the intercepted ciphertext to generate 2^n possible original messages.

If n is a small number, one could easily go through the set of possible original messages and guess which one was the original message.

If n is a large number, that becomes very difficult. Thus my statement that the longer the original message gets, the more secure.

Am I missing something?

If the message is of length n, by going through all the possible values of the pad,

you will go through all the possible cleartext messages as well.

That doesn't help you much even if the message length is very small (like 5), and it

doesn't help you at all if the message is long.

You will get

"Obama continued to pick up superdelegates last week."

"The top rated ####### enlarger results 100% Guaranteed."

"Osama Bin Laden to run for president as a libertarian."

and

"Hamid, send more trained recruits to UK and America."

as possible cleartext values.

How would you know which one is correct?

And the longer the pad is, the more difficult it is to actually go through all the possible xor'd values from all the possible pads...

I'm not sure what you're saying. If the message is 5 bytes long, all you need is a 5-byte pad.

If the ciphertext is "7XH8^", what's the plaintext?

Algae? Group? Infer? Yokel? Sauté?

Could be any 5 letter word.

jihad

You got it - LOL

Edited May 21, 2008 by mawilson

[w¡n9Nµ7 §£@¥€r 123]

The pad and the original message have to be of equal length for the xor, right? The length of the ciphertext will therefore be the same, right?

So if someone finds the ciphertext (-original message- xor pad), they know the length of the original message and of the pad.

So... if you know the pad is of length n, then there are 2^n (assuming messages are in binary) possible values of the pad, right? Those possible values could be generated (using charles' cray) and then each xor'd with the intercepted ciphertext to generate 2^n possible original messages.

If n is a small number, one could easily go through the set of possible original messages and guess which one was the original message.

If n is a large number, that becomes very difficult. Thus my statement that the longer the original message gets, the more secure.

Am I missing something?

If the message is of length n, by going through all the possible values of the pad,

you will go through all the possible cleartext messages as well.

That doesn't help you much even if the message length is very small (like 5), and it

doesn't help you at all if the message is long.

You will get

"Obama continued to pick up superdelegates last week."

"The top rated ####### enlarger results 100% Guaranteed."

"Osama Bin Laden to run for president as a libertarian."

and

"Hamid, send more trained recruits to UK and America."

as possible cleartext values.

How would you know which one is correct?

Assuming n is small, are you saying all the possible cleartext messages will be potentially meaningful? Isn't it more likely that you will end up with:

We kill Barney the Dinosaur tomorrow

OR

ahyjkre tygv re tgd jjddfd jhjjjdjj djdj

OR

hh jihad tnkkdhs butterfly hdhil penisk

Edited May 21, 2008 by VJ Troll

[mawilson 2,133]

Assuming n is small, are you saying all the possible cleartext messages will be human-readable? Isn't it more likely that you will end up with:

We kill Barney the Dinosaur tomorrow

OR

ahyjkre tygv re tgd jjddfd jhjjjdjj djdj

OR

hh jihad tnkkdhs butterfly hdhil penisk

Even if you filter out the unreadable messages, you will still end up with millions

of human-readable messages of length n, all of which are equally likely to be

your cleartext.

[w¡n9Nµ7 §£@¥€r 123]

Assuming n is small, are you saying all the possible cleartext messages will be human-readable? Isn't it more likely that you will end up with:

We kill Barney the Dinosaur tomorrow

OR

ahyjkre tygv re tgd jjddfd jhjjjdjj djdj

OR

hh jihad tnkkdhs butterfly hdhil penisk

Even if you filter out the unreadable messages, you will still end up with millions

of human-readable messages of length n, all of which are equally likely to be

your cleartext.

With large values of n, yes. With small, maybe not. That's my only point. Even if there are multiple meaningful cleartexts in a scenario with 2^8 possible values, it's still a small enough number where each can be investigated/pursued independently.