15 posts

## Puzzle one-time pads in Cryptography.

Back to Forum: Tech Off
• I was listening the other day to Steve Gibson with Leo Laporte's Security Now podcast. They explain the basis of cryptography and they talked about the one-time pads.

One problem with the one-time pads was that , though its unbreakable, you had to send the pad to the recipient in a secure way, and this is its weak point.

So one of the listeners during a Question and Answer session, suggested the following.

You have a box, that you put your message in, and you lock it with your lock (your one time pad) and send it to the recipient. The recipient, adds their lock to the box (with their one-time pad) and hence you get a doubly locked (encrypted). This doubly locked box goes back to the sender, and the sender then unlocks (decrypt it with their one-time pad), and sends it back to the recipient, who then unlock his lock (decrypt the message using their one-time pad) and so the recipient gets their own plain text message.

This way no one time pads (locks) are exchanged. Since one time pads are mathematically impossible to break due to maximum degree of entropy (disorder or randomness) it seems this way is an virtually impossible way to break it.

An observer would just see encrypted messages going back and forth. However, such a scheme would be vulnerable to cryptanalysis, since the 3rd party would see the messages before recipient encrypts it and after, so they can get the recipient's one time pad. and also for the sender.

Its all explained in the grc episode 36. But now, I was woundering, what if one does all the above under ssl or under RC4 with long keys, would this not be a perfect crypto-system that no one really can break with in reasonable time?

Secondly, what if the the observer (3rd part) get the one-time pad of the recipient or the sender by observing the messages before and after recipient encrypt it and before and after sender decrypt it? its a one-time pad, they cant use it to decrypt future messages but they can decrypt the current message they observed , but with alot of effort.

• Public key cryptography can be explained in terms of locks and keys too and it is easier than one-time pads too.

If I want you to send me encrypted messages, I send you my public key. This is like an unlimited supply of padlocks to which only I have the key.

When you send me a message you put it in a box and lock it with one of my padlocks. Send me the box and I can open it because I have the only key.

If you send me a supply of your padlocks, your public key, I can send you encrypted messages which only you can open.

The beauty of this system is that, after the setup, which does not have to be secure at all. You can send me any number of encrypted messages without requiring any ping-pong.

SimonJ

• SimonJ wrote:
﻿

Public key cryptography can be explained in terms of locks and keys too and it is easier than one-time pads too.

If I want you to send me encrypted messages, I send you my public key. This is like an unlimited supply of padlocks to which only I have the key.

When you send me a message you put it in a box and lock it with one of my padlocks. Send me the box and I can open it because I have the only key.

If you send me a supply of your padlocks, your public key, I can send you encrypted messages which only you can open.

The beauty of this system is that, after the setup, which does not have to be secure at all. You can send me any number of encrypted messages without requiring any ping-pong.

SimonJ

For example your ISP or any other 3rd party. They can get your public key, and get the RemoteEndPoints Public key, and they can talk to the remote point as if its you. So ISP would pretend its you, and then generate a key pair and talk to the remote end point as if its you, after decrypting the message the RemoteEndPoint sent to you, then they use your public key to send you the message again (the ISP would use your pulbic key to encrypt the message that the RemoteEndPoint Sent after having decrypting it).

So this public key thingy does not protect you against this.

So what then?

• This would assume that encryption is commutative, which I don't think it is.

• Sven Groot wrote:
﻿

This would assume that encryption is commutative, which I don't think it is.

In general they aren't. You are right. Although the VigenĂ¨re cipher should be commutative. As far as I know... You can use that as a one time pad, if the key is as long (or longer) as the text that is encrypted.

The idea of this thread is nice, but you get still (and only) the encryption of the public key thing. I mean if you broke that you are back at the vigenĂ¨re... you are seeing the message going back and forth. It's just easier to create a very very long public/private key pair...

• I find the security now podcast to shallow and often misleading. If you seriously are going to learn about crypto pick up a book and follow a cs course. The university of washington has a free crypto course that many ms employees attended.(2006)

You can find the course materials here;
http://www.cs.washington.edu/education/courses/csep590/06wi/lectures/

They also provide the link to a free online crypto book.

As for the one time pad;  it has two funamental difficulies. First of all, you need to make lagre quantities of truly random keys, Its a daunting and process intensive task. ( actually kgb used one time pad keys repeatedly during the cold war and nsa were listening into their conversations ) Secondly as mentioned, key distrubution and protection is difficult . As such the one time pad has little practical value for most people.

As for distribution of Secret Keys Using Public-Key Crypto there are a few of schemes that are widely used.

A simple one goes like this.

1. A generates a public/private key pair {PUa, PRa} and transmits a message to B consisting of PUa and an identifier of A, IDA.

2. B generates a secret key, Ks, and transmits it to A, encrypted with A's public key.

3. A computes D(PRa, E(PUa, Ks)) to recover the secret key. Because only A can decrypt the message, only A and B will know the identity of Ks.

This method are insecure against anyone who intercept messages and then relay it/ substitute another message, like the man in the middle attack.To protect against active/passive attacks, (assume that a and b have exchanged public keys)

1. A uses B's public key to encrypt a message to B containing an identifier of A (IDA) and a nonce (N1), which is used to identify this transaction uniquely.

2. B sends a message to A encrypted with PUa and containing A's nonce (N1) as well as a new nonce generated by B (N2) Because only B could have decrypted message (1), the presence of N1 in message (2) assures A that the correspondent is B.

3. A returns N2 encrypted using B's public key, to assure B that its correspondent is A.

4. A selects a secret key Ks and sends M = E(PUb, E(PRa, Ks)) to B. Encryption of this message with B's public key ensures that only B can read it; encryption with A's private key ensures that only A could have sent it.

5. B computes D(PUa, D(PRb, M)) to recover the secret key.

This scheme ensures both confidentiality and authentication in the exchange of a secret key.

One can alo use a KDC(IBM mainframe method) that shares a secret master key with each user and distributes secret session keys encrypted with the master key

• Comment removed at user's request.

• Man in the middle who gets your public key can encrypt things that only you can decrypt but they can't impersonate you or the other guy. To do that, they would need your or his private key to sign their message.

SimonJ

• SimonJ wrote:
﻿Man in the middle who gets your public key can encrypt things that only you can decrypt but they can't impersonate you or the other guy. To do that, they would need your or his private key to sign their message.

SimonJ

But it will work here.

Sender ----------------------------> Man-In-Middle (ISP) -------------->Reciver

So the sender sends their public key, the ISP would intercept it, and generate its own Keypair to communicate with your destination (reciver). The reciver will think that Man in middle is you, and it uses man in the middles's public key to communicate with the reciver.

To keep you connected and to be undetectable, the ISP then gets the message the Reciver wants to send to the sender, and decrypt it, since reciver sent it using ISP's public key, and then the ISP would reencrypt this packet data with the sender's public key and so on.

SO man in the middle acts like a proxy if you will .

• Programous wrote:
﻿

This method would work, sort of. Here are the problems though:

A)     A the end, only the sender knows the encryption of the receiver, the receiver cannot compute the encryption of the sender. Ex: you would have to do this process twice so that each party knows the encryption method of the other.

B)      One time pads are only mathematically unbreakable if only used once.  One would assume after the key exchange you would continue using the same key. Also, with one time pads, if the data transmitted at any time is known, the key is instantly broken.  As if you decrypt the cipher text with the clear text, you get the cipher.

C)      One time pads have to be the exact length of the data being sent. That means you have doubled your overhead.

So how can we generate a perfect crypto system that NO one in earth can decrypt it or compromise it except the intended reciver?

from what I hear in the Security Now episode, that maybe NSA and governemnts do have a backdoor to SSL and the currently available crypto systems, and especially ISPs, since the traffic (key exchanges) are happening in their medium.

• Intercept impersonation only works if you trust the man in the middle's self generated imposter signature. This would not be a sensible thing to do.

You should expect any sender's signature to be certified by a third party that you already trust.

SimonJ

• SimonJ wrote:
﻿Intercept impersonation only works if you trust the man in the middle's self generated imposter signature. This would not be a sensible thing to do.

You should expect any sender's signature to be certified by a third party that you already trust.

SimonJ

What would happen then if you dont trust any 3rd party Cetrification authority?

Secondly, what does certification by 3rd party imply? does it imply that they know your see your public key, and they affirm to the reciver that this public key belongs to the person who claims that this is their public key? Since publick / private keys are mathematically related, wouldn't there be a way for someone, to get the private key if you know the public key and the method used to generate the key pair?

See even here, Seteve Gibson says that the governments and other 3rd party might already have, a backdoor to SSL or other kinds of encryption used by the industry today.

So people have a false sense of security, privacy, and annonymity as far as the internet is concerned?

• If you don't trust anyone then you have to treat all data as suspect and you end up a paranoid gibbering wreck.

Trusting any certificate means that you trust the issuing authority to have checked the identity of the person to whom they issue the certificate and you trust the person to whom the certificate was issued to keep the private key safe.

Knowing a public key does not mean you can calculate the private key to which it belongs. That reverse engineering is very very difficult and time consuming. That is why public/private key cryptography works.

SimonJ

• SimonJ wrote:
﻿If you don't trust anyone then you have to treat all data as suspect and you end up a paranoid gibbering wreck.

Trusting any certificate means that you trust the issuing authority to have checked the identity of the person to whom they issue the certificate and you trust the person to whom the certificate was issued to keep the private key safe.

Knowing a public key does not mean you can calculate the private key to which it belongs. That reverse engineering is very very difficult and time consuming. That is why public/private key cryptography works.

SimonJ

What I think should happen is that we need a new OpenCryptosystem, where there is No key exchanges what so ever, and that the system uses 100% perfect brownian motion algorithms for perfect randomness.

The one-Time pad system is Unbreakable because mathematically and statistically its unbreakable. The only problem with this system, is that you need to give the pad to the recipient, and that is the weakest link.

Since one time pad fundamentally implies the XOR, would it not be cumuliative?

I am discussing this with a friend of mine, to see if its possible theoritically and practically, to modify the one-time pad system to work with-out the need to exchange keys.

In the Gibbson episodes, we see a good idea. Why not I become the sender and the psudo-reciver of an encrypted message, only allow the Eu-reciver to encrypt it again?

So in effect, I send the encrypted message to myself, I remove the encryption and destroy my key-pad.

Me -               - (R)eciver (owns its one-time pad, send message to R)
-          -
-     -
-   -
x         message exchange (single or double encrypted)
-   -
-     -
-         -
Me  -            - Reciver (Decrypt using its one-time pad and get rid of it)

To me this can work because the analogy works, only need to prefect such a system and you can get perfect crypto-system that can be used worldwide and that the industry can use.

• One question though, How does a server, or client, know that the message has been decrypted (ie. it is in plain text form)?

As in, if you selfsign the message with your private key, and the reciver would verify that it came from the sender,but how does the verification process work at the reciver end? They use the sender's public key to decrypt what the private key of the sender had encrypted. But then how does the reciver know or realize that the public key gave it a plain text decrypted message and hence the sender is really who they claim to be?