String encryption - suggestions asked

[wysota]

I think the first question we should ask here is "what do you need it for?"

[yop]

I think the first question we should ask here is "what do you need it for?"

Clients: Have a string of digits < 32 bytes
Server: Has the same string of digits

Expected outcomes:

1) Client encodes/encrypts the string in a way that it is difficult (NOT impossible) for the server to regenerate it. Any other client must be able to regenerate the string with no problem. The resulting string should be digits as well with the same strlen as the initial string.
2) Client produces a (strictly) 16 bit check sum that is impossible for the server to regenerate. Any other client can produce the same checksum.

In any case we can have "things" that the client only known but not the server. All the clients can share this "secret".

I just need some rough guidelines and then I can do my homework

[jacek]

Client encodes/encrypts the string in a way that it is difficult (NOT impossible) for the server to regenerate it. Any other client must be able to regenerate the string with no problem.

If the server will only know the encrypted string, you could use one-time pad, since it won't be able to reproduce the key easily[1]. The only problem is how to seed the random generator --- you might use some pre-shared seed combined with current time (if the clients are synchronized).

Other solution you might try is to devise n string mangling schemes. Like simple arithmetical operations, transpositions and so on. Then clients can decide which scheme they're using currently. All the server will be able to do is to guess which scheme was used and the chance for the right guess is 1/n.

You might want to dig around zero-knowledge protocols.

[1] Note that if the server knows a (+) k and b (+) k it also knows a (-) b. Where (+) is digit-wise sum modulo 10.

[wysota]

I think a simple permutation of digits satisfies the scheme. If the clients know the scheme of permutations used, they can reverse the process and the server won't have any knowledge about anything if it doesn't know the scheme. I think such thing is used by a security mechanism used by banks (and other) known as the token. I mean the "key change" scheme, the permutation is just a way to scramble input.

[TheRonin]

One way of doing the scrambling is to use a modified version of the RC4 stream cypher. The RC4 uses an array of bytes from 0 to 255. This array is then 'scrambled' with a password. The resulting scrambled array, we'll call it the s-box, is then used to encrypt the data by a similar scrambling process. The resulting cyphertext will be as long as the input-text.

My proposal is that you instead of using an array from 0 to 255, go from 0 to 9. Then the scrambling and encryption will only occur over those 10 digits. I.e., you're restricting your finite field to 10 instead of 256.

The reason for modifying RC4 instead of just making something up is that it's a known algorithm that you can find source code for online to alter AND it's *very* quick and simple. Also, it means that each client can have a list of keys instead of different procedures for scrambling data.

So the clients can share keys and decide on one to use for one communication session. They then encrypt their digits with the session key and send that. Only those that know the session key can decrypt the data.

With this scheme, you can make sure all the clients share a checksum-key. This key can be used to perform an encryption of the data that only the clients can reproduce - to create your checksum.

What thinks?

[jacek]

The reason for modifying RC4 instead of just making something up is that it's a known algorithm that you can find source code for online to alter AND it's *very* quick and simple. Also, it means that each client can have a list of keys instead of different procedures for scrambling data.

RC4 has a well-known weakness, so one should at least skip the initial bytes it generates.

The idea of several scrambling schemes comes from a method for electronic cash verification.

[TheRonin]

RC4 has a well-known weakness, so one should at least skip the initial bytes it generates.

Indeed, statistical analysis of the first few bytes can reveal a lot about the status of the s-box, indirectly revealing information about the key (the mentioned analysis requires a known plaintext to work). I made the assumption that our friend yop didn't require any extreme encryption scheme for his application. If that were the case, a stream cypher would not be recommended at all. Also, there are methods of patching the mentioned statistical weakness, such as you suggest, discarding the initial output.

I would think that the security in using different schemes instead of one scheme with keys would be less because of the reduced keyspace. If i were to use one of say, 100 schemes, i only have 100 possible combinations. Compare this to using a key of just 8 bits that gives you 256 possible combinations. You get greater security with less work since you don't need to create a bunch of different scrambling methods.

Perhaps they combine the two to get added security, but i would think that doing so would produce more potential security problems since some scrambling schemes may be weaker and more prone to attack than others. I believe using a strong method of encryption along with a stable framework for key distribution would be the wise choice, in the field. But i digress...Again, i'm assuming yop is not working on some critical system with enormous security requirements. If he is, i appologize for leading him astray with the less than optimal RC4..just trying to be helpful

[jacek]

If i were to use one of say, 100 schemes, i only have 100 possible combinations. Compare this to using a key of just 8 bits that gives you 256 possible combinations. You get greater security with less work since you don't need to create a bunch of different scrambling methods.

What about 20922789888000 schemes? And all you need is to write a single method that permutes 16-bit value. As long as the server can't tell the difference between a valid string and scrambled one (either by using data it has at hand or by asking one of the clients), you're protected by plain probability.

I believe using a strong method of encryption along with a stable framework for key distribution would be the wise choice, in the field.

Yes, you're right, but it's hard to meet those same-length and digits-only requirements.