Public-key XOR Encryption?

[HaxSoft]

Suppose that host A wants to talk to host B on a network. All messages from A go to server X first and X forwards the message to B. NOW, using simple XOR encryption, A can make the message unreadable to X (and also B), but how can A tell B which key to use for decifering without revealing the key to X? A and B can only communicate through X.


[A] ---> [X] ===> [B]
[A] <=== [X] <--- [B]

---> Sent message
===> Forwarded message



I have been wondering about this for some time and can't seem to find a solution.

I know, it can be done using the RSA encryption algorithm, but I am interested in using XOR encryption (or similar reversible algorithm).

[kedaman]

If A and B can't talk to each other then how can they agree on a encryption at all?

[Starman]

It can be done.

This seems a good place to test it.

You/Me can be A and B

everyone else can be X.

[kedaman]

Hows that possible? either A or B has to initially know something that X doesn't know or A or B would need to communicate once before entering this system.

[Starman]

I'll encrypt with my password, no-one else knows this.

I post the encrypted file on here.

You use the same algorithm to encrypt the encrypted file with your password - no-one knows this either.

You post the doubly encrypted file on here.

I'll decrypt with my password and post the result back here.

You can then decrypt the file with your password and read the original text.

If the passwords are good then no-one else will be able to read the contents of the file.

endcrypt routine at :
http://forums.vb-world.net/showthread.php?s=&threadid=56787

[kedaman]

well eh, i can't think that would be secure with syncronous encryption.

[Starman]

If the password is at least as long as the text to be encrypted and all the password characters are truly chosen at random then the encryption is secure.

Trying to crack any text length of this encryption could result in any text of the same length. you have no idea which character encrypted which.

'Open the door at midnight' would be as likely to be the original text as 'Switch off all the lights'.

[Starman]

One caveat: Having removed the first encryption, A will be able to discover B's password as A already knows the plaintext, but this could save time in future communications - as long as A and B are prepared to risk re-using a password - which is not good practice.

[HaxSoft]

In the following "diagram", m = Plain-text, 1=A's key, 2=B's key, and 'm12' represents m xor 1 xor 2:


m xor 1 = m1 - A sends m1 to X
m1 xor 2 = m12 - X forwards it to B and B sends m12 back
m12 xor 1 = m2 - X forwards m12 to A, who applies its key
m2 xor m = 2 - A applies the plain-text msg to find key


A and B should be able to exchange keys in order to communicate, However X monitors all this activity and does this:

A sends m1 to X and X stores it, then forwards it to B

B applies its key (2) which produces m12. This gets sent back to X.

X now cracks B's key by doing m1 xor m12 = 2

So if X is a cracker, it will break B's key; otherwise, X will be decent enough not to, but we can't rely on that.

It takes more to make it secure. This is because of the reversibility. Perhaps there is some way of A and B applying random keys on top of their regular keys ... but something tells me it doesn't change anything.

[Guv]

When I red the post by Starman I thought my intuitive no vote was wrong. but the post by HaxSoft shows how to find both keys and the clear text.

Does anybody have any further ideas? If not, "no" is the correct vote.

Bravo, HaxSoft, with a good try to Starman.

[kedaman]

That's what i meant, asyncronous encryption would do the trick

[HaxSoft]

Originally, I thought it would be possible -- I think I got the idea about a year ago. But now, I am getting more and more convinced that it is impossible to make it secure.

However, I want to find the way, if the way is there. I tend to think that it's not impossible just because I can't figure it out.

So if anyone has any idea at all, it would be greatly appreciated. It doesn't have to be any solution, just any idea. IF it can be done, it would be something new in the "encryption world", so to speak.

Starman's idea was good -- I agree with that. I have worked with the same idea myself, but I think there is something missing. Maybe a random key of some sort ... Or maybe A and B could take advantage of a fixed key for A and another fixed key for B and then combine these with randomly generated keys.

Man, maybe it's just impossible.

[Guv]

It seems that "Private Key" methods like Xor encryption cannot do this job.

"Public Key" methods were invented/discovered about 30-40 years ago. They could handle this problem. There are several such methods, based on "Trap Door" algorithms. The name comes from the idea that it is easy to fall though a trap, but tuff to climb back out of the pit.

I do not know the actual algorithm, but one method is based on the product of large prime numbers. The idea works as follows. There is an encryption algorithm using a long number (say 300 or more decimal digits), which is the product of two prime numbers. The decryption algorithm requires knowing the two factors. You can send your associate the large number and the encryption algorithm, allowing anybody to eavesdrop on the communication. He encrypts a message and sends it to you using an insecure method of communication.A hacker would need to factor the huge number in order to crack the system. As of now, numbers beyond a certain size cannot be factored by modern computers. In the future, who knows?

One problem with the method using prime numbers is the possibility of some modern day Fermat developing an algorithm for factoring humongous numbers. Fermat was rumored to have methods unknown to modern mathematicians.

Another problem is the possibility of some obsessive compulsive number theory fanatic just happening to know the factors. There are folks out there who collect large prime numbers the way some people collect stamps, coins, match books, et cetera. One of them could try the 200 hundred or so big primes in his collection and be lucky.

As far as I know, the government is not using Public Key methods. Mainly due to paranoia, but with some good reasons to be afraid. You can never tell when there will be a break thru. All the Public Key methods use algorithms not known to have easy solutions now, but I do not think any involve a provably impossible problem.

[Starman]

I stand corrected. Well spotted HaxSoft!

I have been wondering if B could make a further alteration that only B would know, such as chop the file and rebuild it in a different order - but then A would not be able to remove his encryption...

There must be a way - if you admit that is impossible then you will never find a solution.

[HaxSoft]

Ha ha ha, Starman -- I am not going to admit it is impossible unless I have to.

I have been thinking about the same thing. If A had something that only A knows and B has something only B knows, but how do they "sneak" those keys through X?

I am using this A, B, X model because I would like a system where someone might be evesdropping and yet two people (or computers) could exchange information in a relatively secure way. Nothing is 100% secure as Guv points out.

And yes, I guess public keys are allowed. The only restrictions are:

1) A and B can only communicate through X.
2) The encryption algorithm has to be reversible, like XOR is.
3) A and B have not talked beforehand (they don't share any secret knowledge).

[kedaman]

I may have not understood this correctly from the beginning, but now when you clarify those restrictions, even RSA won't pass, and a similar but stronger wouldn't either, B and X stands at the same position from A's POV and cannot clarify weather a message was sent from B or X.

[Guv]

The requirement for "reversibility like Xor" makes this problem impossible. The HaxSoft analysis of Xor encryption will always be applicable.

Face facts: Anything A tells B and vice versa is known to X. The decryption algorithm must somehow be different from the encryption algorithm.

Public Key methods do this job. A has a secret (to him) decryption algorithm and via X sends encryption instructions to B. B has a secret (to him) decryption algorithm and sends encryption instructions (via X) to A.

A and B each use a publicly known encryption algorithm and a secret decryption algorithm.

There is another cute gimmick with these Public Key methods. They can be used to verify the identity of the sender of a message. This is not easy to grok if you do not concentrate a little bit. A uses his decryption algorithm to create a garbled version of his own name. A appends this garbage to a clear text message. A then uses B's encryption algorithm to create a message to be sent to B. B uses his decryption algorithm to decrypt the message. At the end of the message is some garbled text. B uses A's encryption algorithm versus the garbled text. This results in a clear text version of A's name or other verifying data.Since B knows that A's encryption algorithm is known only to A, B knows that the message came from A.

[Starman]

This seems to be becomming even more complicated. If A and B have no prior knowledge of each other I can't see why they should want to communicate or why it should matter exactly who they communicate with. As Kedaman has now pointed out the initial message may be originated by X and neither A nor B will ever know.

I felt that the original question was to do with private communication in a public area such as this forum and that the two parties would be able to meet and publicly declare a wish to chat in secret, if one of these parties was X then B wouldn't be able to join in.

Guv: isn't that how credit card security is performed on the web?

[kedaman]

A then uses B's encryption algorithm to create a message to be sent to B.

This is where RSA fails (yes RSA is the strongest asyncronous encryption currently), in this issue, simply because A and B knows something that X doesn't know. The idea was that all information pass trough X, according to paragraph 3, no secret (to X) keys allowed.

The only way you get trought this is to assume X is stupid, more stupid than B, and i don't think you want to do that, Any method allowed to B is available to X, so Encryption will never be secure in this issue.

[Guv]

Kedaman: Public Key encryption would work, but would not satisfy the reversibility requirement.

Public key encryption would allow you to appear on a nationally televised TV talk show and announce your encryption algorithm.

Anybody who saw the show could send you a coded message which only you could decrypt.

The encrypt and decrypt algorithms for Public key methods are obviously not reversible like Xor methods.

BTW: I thought it was assumed that X would pass messages back and forth without lying about the transmissions, misrepresenting the source, changing the transmission text, et cetera. I thought that the only skulduggery allowed him was eavesdropping and attempting to crack the codes.

[kedaman]

I see your point Guv, it was a while ago i read about RSA encryption and i was sure you had to pass something private before you could start using keys in public, i looked up the same page again they explaind it clearly but were diffuse, just on this point, without giving that impression, i guess you're right, thanks for correcting me. They did although clearly state RSA encryption is way too slow for file transfers, and is used mainly for messenging like email.

Now if HaxSoft would allow X modifying or why not just pass it's own messages to B is just something i assumed a hacker could do.

[HaxSoft]

OK, I can't say that I have had any clear definition of the requirements from the start of this discussion, haha. I make up the rules as we play the game :-)

There is no reason why X should not be able to "lie" to A or B. After all, X is the link between the two hosts and could, in theory, send anything to either of the two.

A and B might very well know something that X doesn't, but they just can't tell each other what they know without X listening in on it. A and B have not talked before ... you could think of this thing as two programmers sharing (secret) source code through some server, like ICQ or whatever.

The requirement for reversibility ... I'd like to keep that for a while.

It is true that A has a major problem knowing whether a given message came from X or from B, unless of course A and B know something that X doesn't.

[Guv]

HaxSoft: If you want to keep reversibility, forget it. This problem has no solution. If X cannot be trusted to pass messages without altering them, you should not be using X for your communications. It is bad enough if you cannot trust him not to eavesdrop. No sense using him if he cannot be trusted to do anything valid for you.

BTW: I did not think that Public Key methods were slow enough to discard them for that reason. They might have other drawbacks.

Another thought on the subject of Xor encryption. Unless it is impossible to guess any part of a message, you should use a simple substitution encryption prior to the Xor encryption.

For example, suppose that Clinton White House messages were encrypted. You might guess that "Lewinsky" would be in some messages (remember the era, I am thinking of?). If you Xor "Lewinsky" against many parts of a message, you have some chance of discovering part of the Xor Key. Now take the results of Xor "Lewinsky" and Xor those results versus other parts of the message or versus other messages. If something looks like part or all of an English word, you have part of the Xor Key.

Simple substitution encryption prior to Xor encryption thwarts the above attack.

[Starman]

Guv: If the key is random and at least as long as the text (and only used for one message) then a codebreaker would discover 'Lewinsky' in any position of the text, but would have no way of telling where the word actually occurred in the plaintext or whether it was in the message at all. Even if the word was at the beginning of the message, the partial key derived from this would be of no help for the rest of the message.
Unlike Enigma, there is no rotation of the key to look for.

[kedaman]

Yep, otherways Xor encryption would be useless. I have Xor encryption on my homepage that is used in combination with rnd function which makes it impossible to find any combinations whatever message you pass. Although If you alter a message with nulls, you could see the whole key but if you alter the random seed every time you use it, you get on the secure side. I did some tests a while ago and rnd has about 2^117 returnvalue series using decimal datatypes for the seed, if you combine that with another key you have enough combination for security, but of course, you have to alter all the time, but an altering key is not a big issue.

Doesn't relate to this case though, you need to share the keys/altering algoritms in private

[HaxSoft]

I realize that I have brought the proof that it is impossible myself actually (that post I submitted when X cracked B's key).

I managed to create a system where A can send a combined key that can not be derrived/extracted from A's messages, but it was a weird and complicated thing including three messages, 4 keys, and a plain-text message. The thing is, that X can't crack it, but neither can B.

My thought was to pass some messages to B and have B encrypt them using amongst other things this "secret" key. However, I won't bother with bringing a lengthy explanation because it leads nowhere anyway (I worked 6 hours on the problem today ... I KNOW it's impossible, so if anyone reads this post and hasn't voted yet, then please vote NO, haha).

OK, so that rules out reversibility completely! As Guv pointed out, as long as we require reversibility, then there is no solution. I kinda thought so before, but now I KNOW.

[Starman]

HaxSoft: Can I change my vote ?

I was shocked when you pointed out the now rather obviously large hole in my solution. Probably not as shocked as anybody who thought that it was secure and actually used it though.

I'm just reading up on the ideas behind quantum encryption and wondering if there is any way it could be applied here.

[HaxSoft]

Starman Yeah, well... can you change your vote? Not unless a moderator is willing to do so ... I don't think I can do that. Maybe they should allow the one that creates a poll to change it, haha.

On the other hand, it was a matter of what we THOUGHT and not what we KNOW (don't feel bad, I voted YES myself).

So, now that reversibility is out (for the time being, hehe)... maybe it's time for some other approach.

What is the basic idea of quantum encryption? Do you have a URL or something?

[Starman]

The basic idea (as I understand it) is that the data can only be read once - the act of reading it destroys the information - so it cannot be intercepted and re-transmitted without detection.

here is a short article by Simon Singh who's 'The Code Book' makes a good read.

http://www.newscientist.co.uk/ns/19991002/quantumcon.html

[kedaman]

That's sounds like a solution :) Hmm maybe i should change my vote

[Guv]

Starman: In theory you are perfectly correct. A key as long as the message and used only once is probably uncrackable.

In practice, the downstream loading problem tends to cause keys to be used more than once. For other practical reasons, keys tend to be some fixed length a lot shorter than the clear text. Hence an Xor encryption often needs a little something extra.

[HaxSoft]

Try XORing an EXE file, which usually contains large sequences of 0x00 bytes ... the key is clearly visible because 0x00 xor key = key!!!!

You might run-length encode the EXE file, so that the sections of 0x00 disappear to get rid of this problem. Also, with XOR encryption and files, it is important to change the filename (and extension) so as to minimize the risk of anyone making (correct) assumptions about the file's original contents.

For instance, if I XOR a GIF file, anyone who has worked with a hex editor would know that the first five bytes in the file are GIF87 or GIF89. That means, they can find the first 5 characters in the key.

This is probably not a XOR-specific problem; it might be used to crack other encryptions as well. Someone mentioned that you could shuffle the bytes, which sounds like an idea.

That quantum encryption sounds very interesting, though.

By the way, how do you like my new smiley? I made him today (got tired of encryption and had to do something else, haha)

[Chris]

We can use the requestID as the encryption/decryption key.

That mean, when any client connect to the server, the server should key thier requestID into an array.

When there is a chat establish between to client, the server should send the respective client requestID to the others client.

E.g.

Client A connect to server, Server X get the Client A's RequestID.
As well as for Client B.

So, When Client A make a chat request to Client B, through the Server X. Server X should first send the Client A' Request ID to Client B and vice versa.

As a result, both Client A and Client B can different encrypted data send through the connection.

[Starman]

Just a thought as I know little about the web but –
If A posted a possible key on a web page with a hit counter, the code could be designed so that the page is destroyed after one hit. If it was B that accessed the page first then B would have the key. It only remains for A to decide if B is the correct recipient of the key.

I realise that this may be in contravention of requirements 1 and 3 but you did say that the rules may change.

[ttingen]

PGP has a plug-in for ICQ. Somehow it works with public/private key encryption. I haven't used it - just read about it briefly on their site. Check out their site and in the features you'll find instant messaging encryption:

http://www.pgp.com/products/dtop-security/default-encryption.asp

[HaxSoft]

This thread has many great ideas and thoughts. I think that Starman is on to something there with that web site and the hit counter.

It would required us to change the rules. Or rather, EXTEND the rules.

A can't talk to B other than through X. If we change the rules so that A and B can surf each other's web sites (haha, bending rules here BIG TIME), then they could at least exchange keys.

A ONE-TIME key on a web page generated with PHP and authentication and stuff would solve some problems.

Might be worth a test in a real-world environment.

That PGP plug-in for ICQ that ttingen refers to sounds interesting. I think I will go try that out.

[Chris]

HaxSoft, here is some disadvantage that I think off. If every single chat must go through X, then X will be busy all the time and may get crash one day... Who know... this really might happen

[HaxSoft]

Originally posted by Chris
HaxSoft, here is some disadvantage that I think off. If every single chat must go through X, then X will be busy all the time and may get crash one day... Who know... this really might happen

Chris:

A and B did originally have to communicate through X. This was because I was interested in finding out whether or not it is possible to communicate securely using a reversible encryption algorithm such as XOR encryption WITHOUT knowing any secret prior to communicating with another party.

The original idea (in my head) was the classical example with Alice sending a message to Bob and Eve evesdropping, thus the A and B -- X was chosen because A and B won't really know whether X is there.

However, the discussion took some turns (again, in MY head :)) and I think some of the other participants got a few ideas too.

If we think about my original post, then I certainly HOPE that X crashes, haha.

[Lord Orwell]

I once wrote an encryption program. It let you choose a file on your hard drive to use as the key. All you have to do to avoid the large null groups is to ignore them and move to the next character.
I can see where if you were to encrypt a file though, your key might show up. That is why you should .zip a file first (and change the file extension) before encrypting it. It removes large blank areas of any type.

The only solution to your dilemma works like this:

.a - x - b
. \ /
. -y-

In other words, have two ways to communicate. Transmit the key with one and the encrypted message with the other.

or another example would be you agree that the key is going to be the 97th word of the email you send before the message. Something like that.

[Starman]

If your key is long and random it may well be reflected in large groups of nulls - but who would know ?

[Nucleus]

Maybe a lateral solution.... based on steganography rather than cryptography.

A is a VB programmer (which he must be if he is designing XOR encryption). Makes a game / some other app such as an address book chat program, etc. Sends application to B. The application opens up and asks user for their name, as many/most applications do.

On entering A as a username, up comes the XOR code and extra documentation.

The chances of X entering A's name either on purpose or by accident is small to insignificant unless X and A share the same name, making this approach workable in just about all circumstances.

;) :cool: :) :p :D

[Starman]

I’m not convinced. If you take this thread to be X and I post a message here to HaxSoft saying ‘Try this, I think you’ll find it very INTERESTING’ then I think X may spot the message. Also, if soon after this post HaxSoft starts sending encrypted looking files X’s assumption has to be that a key has recently changed hands and would guess where to look. I also have no idea what name HaxSoft may use to log-on to my program and of course any prompting I give has to come over this thread so will be visible to X.

[Nucleus]

Starman you said: If you take this thread To be X And I post a message here To HaxSoft saying ‘Try this, I think you’ll find it very INTERESTING’ Then I think X may spot the message.

Well no one said anything other than sending the application to B. Let's say there was no covering note other than 'Please try out my new application'.

Also, if soon after this post HaxSoft starts sending encrypted looking files X’s assumption has to be that a key has recently changed hands and would guess where to look.

Depends on the instructions delivered with the code. The instructions could detail that the encryption not start form x months/years from the date the application is recieved and in the mean time A and B communicate frequently with each other including sending other software to each other. This further removes the likelyhood of X ever finding out the which mail contained the code let alone trying to work out how to access the code.

The approach I have offered is not infallible, but then again show me any sort of encryption/steganography that is. It does however offer a plausible approach given very difficult constraints.

[Starman]

HaxSoft, Your March 7th Smiley has gone, but I copied it.

Did anyone else take a copy or do we have a key?

[Starman]

Nucleus,
Something you said reminded me about the smiley. As you say it's not infallible but now the smiley has gone, a key is available to anyone who took a copy - unfortunately X who may have a copy is unlikely to admit it and will be able to decipher any messages.

[Nucleus]

X has key, but it is disguised and unrecognisable as key to X, so code is safe.

[Starman]

All the avatars have gone, is it just me or has the site dropped them?

[Zaei]

The answer to the problem is to use a different method of decryption then you use for encryption. For example, Here is "Hello" encrypted:
"200000717I1015X197Y197S92UH717e1015l197l197o92". Try and decode it. It uses xor encryption, and it IS reversible. look below for the answer:



























































The method to decode it is really simple. The first several numbers before the "0000" is the length of the string after encryption. you go through that string, up to that length, following the "0000", and remove all letters. You are then left with a series of numbers, followed by some letters with numbers in between. for instance, you have "H", followed by "717". Replace all "717"s with "H"s, in the encrypted string (theres only one in this example). Repeat that with all of the letter-number combinations. I wrote it so that the xor value is random * (random * 1200). This is easily expandable, but the way to solve this problem is to provide the decryption method inside the encrypted string, in such a way that no one knows its actually there (except B =). Just for example purposes, comment, please =).

Z.

[Nucleus]

How do you tell B how to decrypt it without X knowing? This is the problem.

[Zaei]

Hotmail =).

Z.

[vbzero]

Hi guys!

I read your opinions and points of that "absolute secure" connection and I had an idea.

Maybe it's only a stupid thought...

I remembered when I was a child, we kids often wanted to talk together in a way that the grown ups didn't understand what we are saying.

There were 2 ways to do that:

1. We figured out a secret language before and then we could talk. (But if someone watched us - he knew what we were saying)

2. We tried to communicate in a way, so that the other party could nearly imagine what the first one was saying and if it was correct, we applied....

There must be also a way for computers to do that.

[nishantp]

In order for this to work, A and B must be able to talk toeach other confidentially. Hotmail is a good idea :) If both parties have the algorithm, and X doesnt, then X cant do anything with it. If the encryption with Xor is strong enough, the encryption should be secure. Those simple examples of xor encryption are very simple indeed.

[eiSecure]

Here's an easy solution:

Instead of the password, use a digital certificate.