A simple encryption scheme

tinstaafl

Basically this scheme uses variable offsets, but it generates the bytes on the fly. They aren't truly random, but there aren't any obvious patterns and the output passes all the NIST tests.

Since a simple password can be used to do the de/encryption it is much easier to hand off to the recipient and any good password generator can create one.

Since only part of the generated sub keys are used, it becomes very difficult if not impossible to reverse engineer the sub key to find the previous or next sub key.

167 Views
About the Author
class Cipher
{
    public static IEnumerable<byte> Encrypt(string key, IEnumerable<byte> data)
    {
        return GetBytes(key, data);
    }
    public static IEnumerable<byte> Decrypt(string key, IEnumerable<byte> data)
    {
        return GetBytes(key, data);
    }
    private static IEnumerable<byte> GetBytes(string key, IEnumerable<byte> data)
    {
        if (key == null)
        {
            key = "";
        }
        if (data == null)
        {
            data = new byte[] { 0 };
        }
        var temp = Sha3.Sha3512().ComputeHash(Encoding.UTF8.GetBytes(key));
        return data.Select(x => { var y = (byte)(x ^ temp[0]); 
                                  temp = Sha3.Sha3512().ComputeHash(temp);
                                  return y; });
    }
}
JamesCherrill 4,334 Most Valuable Poster Moderator Featured Poster

That looks like fun! To see if I understood it correctly I tried a Java version. Before I publish it maybe you could validate it by decoding the following:

key = "DaniWeb"
data = {-87, 8, -88, 77, -110, -100, -123, -1, 86}

cheers
J

JamesCherrill 4,334 Most Valuable Poster Moderator Featured Poster

ps why not use all the bytes in the hash before taking the hit on computing a new hash? Could make a difference if you are encoding a lot of bytes?

tinstaafl 1,146 Posting Maven

The main problem I see, is that in .net the byte is unsigned 8 bits. In Java the byte is signed 8 bits. In order for this to work in Java you would need to restrict the values to 0-255.

My thought is that using only the first byte would make it difficult, if not impossible, to reverse engineer the hash before and the hash after. In my tests encrypting 2 MB of data only took a few seconds.

JamesCherrill 4,334 Most Valuable Poster Moderator Featured Poster

I don't see the problem with bytes. Both languages generate valid SHA512 bytes, and this program just uses XOR; no artithmetic operations, so the signed/unsigned difference never comes into play. A byte is just 8 bits in the end.

I'm sure you're right about the inpossibility of reverse engineering. I just thought that the same applies to temp[1+1] from temp[i] if temp is a SHA digest.

Anyway...
Did you have a chance to try the test data I posted? I can express that as unsigned byte integers if that makes it easier...

data = {169, 8, 168, 77, 146, 156, 133, 255, 86}

JamesCherrill 4,334 Most Valuable Poster Moderator Featured Poster

Yes, I had SHA=256. My mistake.
Herewith the data using SHA-512...

71, 210, 218, 188, 244, 138, 119, 150, 216

any better?

tinstaafl 1,146 Posting Maven

On other thing my algorithm uses SHA3-512 and now you're using SHA-512.

JamesCherrill 4,334 Most Valuable Poster Moderator Featured Poster

That'll teach me not to speed read.

OK, let's start again. Here's an encrypted string using my Java implementation of your algorithm with SHA3-512 digest and unsigned bytes for the output. The key is "DaniWeb".

{106, 70, 34, 67, 100, 200, 183, 166, 159}

If I implemented correctly then you should be able to decrypt that. Please let me know.

Re using only the first byte... my suggestion to use them all has a major flaw: if you manage to guess the first 64 bytes then you can generate the second digest and so on. That could be a viable scenario if the encoded message had some guessable content at the start, eg "To: ...".
One simple fix is to XOR the digest with the key before you create a new digest.
Is it worth it?
I benchmarked a 10MB dataset. Calculating a new digest for each byte ran at 520mSec/MB. Using the whole digest before recalculating ran at 13mSec/MB. That's 5 tedious seconds vs an imperceptible 130mSec for the 10Meg.

tinstaafl 1,146 Posting Maven

That works now. I'll have to do some more thinking on reusing the key. That's usually considered bad practice.

tinstaafl 1,146 Posting Maven

Came up with something new. Instead of reusing the key, how about meeting in the middle and using half the hash. This should increase the speed considerably, while still making it impossible to reverse engineer the hash:

using System;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using SHA3.Net;

class Cipher
{
    public static IEnumerable<byte> Encrypt(string key, IEnumerable<byte> data)
    {
        return GetBytes(key, data);
    }
    public static IEnumerable<byte> Decrypt(string key, IEnumerable<byte> data)
    {
        return GetBytes(key, data);
    }
    static byte[] tempHash = new byte[64];
    static IEnumerable<byte> GetBytes(string key, IEnumerable<byte> data)
    {
        if (key == null)
        {
            key = "";
        }
        if (data == null)
        {
            data = new byte[] { 0 };
        }
        tempHash = Sha3.Sha3512().ComputeHash(Encoding.UTF8.GetBytes(key));
        return GetBytes(data);
    }
    static IEnumerable<byte> GetBytes(IEnumerable<byte> data)
    {
        var next = data.GetEnumerator();
        int limit = data.Count();                
        for (int i = 0; i < limit; i += 32)
        {
            for (int j = 0; j < 32 && (j + i) < limit; ++j)
            {
                next.MoveNext();
                var retVal = (byte)(next.Current ^ tempHash[j]);
                yield return retVal;
            }
            tempHash = Sha3.Sha3512().ComputeHash(tempHash);
        }
    }
}
JamesCherrill 4,334 Most Valuable Poster Moderator Featured Poster

yes, that makes sense to me. it looks like creating the digests dominates the execution speed, so using 32 bytes instead of just 1 will run about 30x faster, and about half as fast as using all 64. i guess it reduces the security level equivalent to that of SHA3-256, which is more than good enough for any normal application.
it does still have the theoretical danger that if someone does manage to obtain the missing 32 bytes anywhere in the message then they can immediately read everything that follows, even though they still don't know the key. Maybe thats too obscure to matter.
i'll update my version with that later (i'm just on my ipad now)

ps; while I agree 100% about the dangers of "key re-use", i don't see how that term applies to what i suggested. I'll address that in a separate post later.

tinstaafl 1,146 Posting Maven

@JamesCherrill
I've been doing some more research, and I agree I could use the key like you suggest.

After even more thought, I reasoned that if I obscure the hash byte by XOR'ing with the key, wouldn't it make sense to also obscure the data the same way. I'm not sure if that helps or might be overkill, but I implemented it to see what you think.

I also added different key management. Rather than using the passed in password as is, I added a BCrypt library to hash the password and use that for the encryption and decryption. I'm not sure if there is a better way to handle the key, without implementing a secure server and using TLS.

class Cipher
{
    private enum EncryptionMode
    {
        Encrypt = 1,
        Decrypt = -1
    }
    public static IEnumerable<byte> Encrypt(string password, IEnumerable<byte> data,out string key)
    {
        if (password == null)
        {
            password = "";
        }
        if (data == null)
        {
            data = new byte[] { 0 };
        }
        key = MakeKey(password);
        return GetBytes(data, key, EncryptionMode.Encrypt);
    }
    public static IEnumerable<byte> Decrypt(IEnumerable<byte> data, string key)
    {
        if (key == null)
        {
            key = "";
        }
        if (data == null)
        {
            data = new byte[] { 0 };
        }
        return GetBytes(data, key, EncryptionMode.Decrypt);
    }
    static IEnumerable<byte> GetBytes(IEnumerable<byte> data, string key, EncryptionMode mode)
    {
        var hash = Sha3.Sha3512().ComputeHash(Encoding.UTF8.GetBytes(key));
        int i = 0;
        foreach(var b in data)
        {
            //modulo 64
            int hashIndex = (int)(((uint)i<<26) >> 26);
            if(i > 0 && hashIndex == 0)
            {
                hash = Sha3.Sha3512().ComputeHash(hash);
            }
            byte offset = (byte)key[i % key.Length];
            var retVal = mode == EncryptionMode.Encrypt ? EncryptByte(b,offset,hash[hashIndex]) : DecryptByte(b,offset,hash[hashIndex]);
            hash[hashIndex] ^= offset;
            ++i;
            yield return retVal;
        }
    }
    static byte EncryptByte(byte data, byte offset, byte hash) => (byte)(data ^ offset ^ hash);
    static byte DecryptByte(byte data, byte offset, byte hash) => (byte)(data ^ hash ^ offset);

    static string MakeKey(string password) => BCrypt.Net.BCrypt.HashPassword(password);
}
JamesCherrill 4,334 Most Valuable Poster Moderator Featured Poster

Hello again - I thought his topic had faded out, but obviously I was wrong!. Excellent!

I obscure the hash byte by XOR'ing with the key, wouldn't it make sense to also obscure the data the same way.

Well, XOR is as near to free as a hardware op can be (TANSTAAFXOR ?), so it can't do any harm, so why not?

43: hash = Sha3.Sha3512().ComputeHash(hash);

In a prevoius post I talked about if, somehow, you found one of he 64 byte hashes (eg by XORing with a section of message that you happened to know or could guess) the that unlocks the rest of the message. I would XOR the hash with the key each time to prevent that, as in hash = Sha3.Sha3512().ComputeHash(hash ^ key); I guess your XOR of the hash with the data and th ekey achieves the same result?

ps XOR commutes, so data ^ offset ^ hash is the same as data ^ hash ^ offset, so your two Byte functions are exactly the same.

I can see that BCrypting the key adds a level of obscurity, but if, somehow, you could find the original key from an encrypted message without BCrypt, then you could just as easily find BCrypt(key). You wouldn't have to find the original key. So Ilm guessing that it doesn't add any security.

I did have some thoughts about the problem of key re-use with an XORed stream cypher,and I have asuggestion, but I have to go out now, so I'll post it later. :)

J

JamesCherrill 4,334 Most Valuable Poster Moderator Featured Poster

I read about code re-use with an XORed stream, and that left me worried. Given 2 Messages M1 and M2 and a stream of bytes S such as we get from the SHAs, the enocded messages are M1^S and M2^S. If you XOR those two together you get M1^S^M2^S, which is the same as M1^M2^S^S. But S^S evaluates to all zeros, so M1^S^M2^S == M1^M2 - the simple XOR of the two plaintexts. Now if you know/guess anything about M1 you can derive the corresponding parts of M2 and v-v.
So generating the same stream S twice is an absolute no-no.
The simplest solution seems to me to use a random salt and share that by attaching it, unencoded of course, to the start of the message. Instead of the key you use some combination of the salt and key (XOR, concatenate or whatever). That way S is as secret as the key, but as unique as the salt, and the implemenation is trivial.
What do you think?

tinstaafl 1,146 Posting Maven

I guess your XOR of the hash with the data and th ekey achieves the same result?

My thought was that since the key and the hash are both byte[] the XOR'ing the hash with the key would require iterating over both. Doing the XOR inside the main loop(hash[hashIndex] ^= offset;) eliminates an extra loop and to my mind still obscures the hash so that each hash would have no relation to the next without the key.

So Ilm guessing that it doesn't add any security.

I think, though, by making sure that the key is cryptographically generated, it removes the question of how good the password is, and puts it on the same level as any symmetric key. Keeping the key secure would be up to the user. I'm not aware of a better solution.

ps XOR commutes, so data ^ offset ^ hash is the same as data ^ hash ^ offset, so your two Byte functions are exactly the same.

Yes I see that now. I've corrected that:

class Cipher
{
    public static IEnumerable<byte> Encrypt(string password, IEnumerable<byte> data,out string key)
    {
        if (password == null)
        {
            password = "";
        }
        if (data == null)
        {
            data = new byte[] { 0 };
        }
        key = MakeKey(password);
        return GetBytes(data, key);
    }
    public static IEnumerable<byte> Decrypt(IEnumerable<byte> data, string key)
    {
        if (data == null)
        {
            data = new byte[] { 0 };
        }
        return GetBytes(data, key);
    }
    static IEnumerable<byte> GetBytes(IEnumerable<byte> data, string key)
    {
        var hash = Sha3.Sha3512().ComputeHash(Encoding.UTF8.GetBytes(key));
        int i = 0;
        foreach(var b in data)
        {
            //modulo 64
            int hashIndex = (int)(((uint)i<<26) >> 26);
            if(i > 0 && hashIndex == 0)
            {
                hash = Sha3.Sha3512().ComputeHash(hash);
            }
            byte offset = (byte)key[i % key.Length];
            var retVal = (byte)(b ^ offset ^ hash[hashIndex]);
            hash[hashIndex] ^= offset;
            ++i;
            yield return retVal;
        }
    }

    static string MakeKey(string password) => BCrypt.Net.BCrypt.HashPassword(password);
}
tinstaafl 1,146 Posting Maven

The simplest solution seems to me to use a random salt and share that by attaching it,

It's my understanding, that the key generated by BCrypt uses a random salt and that generating keys with the same password will result in different keys being used. Have I misunderstood something? Do you think it's worth having the BCrypt key and an additional salt?

tinstaafl 1,146 Posting Maven

I just noticed that BCrypt includes a 7 character header in the key it generates. I think having known characters present in the key would be wrong, so I've changed the MakeKey function to strip them out:

static string MakeKey(string password) => BCrypt.Net.BCrypt.HashPassword(password).Remove(0, 7);
JamesCherrill 4,334 Most Valuable Poster Moderator Featured Poster

It's necessary that the receiver can generate the same sequesnce of keys as the sender, otherwize he can't decode the message. If you use a random salt and don't share that in plaintext, then how can the receiver generate the same sequence?

tinstaafl 1,146 Posting Maven

The key is returned to the originator of the encryption as well as the encrypted data. This can then be sent to the receiver to decrypt the data. Because a salt was used when making the key, even if the originator uses the same password, a different key will be returned. It will be impossible to encrypt 2 messages with the same key. Would always having unique keys be enough?

tinstaafl 1,146 Posting Maven

I took a look at BCrypt again and realized that the salt is included in the key. I'm thinking that it would make more sense to separate the salt and the hash, and this would allow me to follow the process, you outlined earlier, without generating a new salt. I've modified the class to accomplish this.

class Cipher
{
    public static IEnumerable<byte> Encrypt(string password, IEnumerable<byte> data,out string key)
    {
        if (password == null)
        {
            password = "";
        }
        if (data == null)
        {
            data = new byte[] { 0 };
        }
        var hash = MakeKey(password);
        key = new string(hash, 22, 31);
        string salt = new string(hash, 0, 22);
        return GetBytes(data, key,salt);
    }
    public static IEnumerable<byte> Decrypt(IEnumerable<byte> data, string key)
    {
        if (data == null)
        {
            data = new byte[] { 0 };
        }
        return GetBytes(data, key);
    }
    static IEnumerable<byte> GetBytes(IEnumerable<byte> data, string key, string salt = "")
    {
        int saltLength = 0;
        if(salt == "")
        {
            salt = new string(data.Take(22).Select(x => (char)x).ToArray());
            saltLength = 22;
        }
        else
        {
            foreach(char c in salt)
            {
                yield return (byte)c;
            }
        }
        key = $"{salt}{key}";               
        var hash = Sha3.Sha3512().ComputeHash(Encoding.UTF8.GetBytes(key));
        int i = 0;
        foreach (var b in data.Skip(saltLength))
        {
            //modulo 64
            int hashIndex = (int)(((uint)i << 26) >> 26);
            if (i > 0 && hashIndex == 0)
            {
                hash = Sha3.Sha3512().ComputeHash(hash);
            }
            byte offset = (byte)key[i % key.Length];
            var retVal = (byte)(b ^ offset ^ hash[hashIndex]);
            hash[hashIndex] ^= offset;
            ++i;
            yield return retVal;
        }
    }

    static char[] MakeKey(string password) => BCrypt.Net.BCrypt.HashPassword(password).Skip(7).ToArray();
}
JamesCherrill 4,334 Most Valuable Poster Moderator Featured Poster

That looks good to me.

JamesCherrill 4,334 Most Valuable Poster Moderator Featured Poster

Now that the algorithm is sealed, I’ve indulged my love of structuring code for maximum clarity and maintainability, and made a Java version accordingly.

The structure follows the short spec: use a public random salt and a shared secret to create a (long enough) stream of bytes, and XOR the data with those bytes. Share the salt by prepending it to the encrypted data.

So the core is a new private class KeyStream whose constructor takes a salt and a secret.It has one public method nextByte() that returns the next byte in the stream. It encapsulates all the SHA stuff, and allows for trivial swap-in of different generation algorithms.

Given that class the encode/decode methods look really simple.. here’s encode’s full implementation

public byte[] encode(byte[] data, String secret) {
    // generate new random salt for every encode
    byte[] salt = new byte[saltLength];
    random.nextBytes(salt);

    KeyStream keyStream = new KeyStream(salt, secret);

    // return salt followed by encrypted data
    byte[] result = Arrays.copyOf(salt, saltLength + data.length);
    for (int i = 0; i < data.length; i++) {
        result[i + saltLength] = (byte) (data[i] ^ keyStream.nextByte());
    }
    return result;
}

Liberated from all the external representation stuff, the KeyStream class is also clear and simple. The constructor creates an initial digest, and nextByte is just

    byte nextByte() { // returns the next byte in the stream
        if (position >= streamBytes.length) {
            // get some new bytes hashing the old bytes and the secret
            digest.update(streamBytes);
            digest.update(secretBytes);
            streamBytes = digest.digest();
            position = 0;
        }
        return streamBytes[position++];
    }

For final packaging I’ve allowed the user to specify a hash algorithm and a salt length, with defaults of SHA3-512 and 8 bytes.
Here’s the full implementation:

public class Cipher {

    public Cipher(String digestName, int saltLength) {
        this.saltLength = saltLength;
        try {
            digest = MessageDigest.getInstance(digestName);
        } catch (NoSuchAlgorithmException ex) {
            throw new RuntimeException("Cannot find " + digestName, ex);
        }
    }

    public Cipher() { // default options
        this("SHA3-512", 8);
    }

    public byte[] encode(byte[] data, String secret) {
        // generate new random salt for every encode
        byte[] salt = new byte[saltLength];
        random.nextBytes(salt);

        KeyStream keyStream = new KeyStream(salt, secret);

        // return salt followed by encrypted data
        byte[] result = Arrays.copyOf(salt, saltLength + data.length);
        for (int i = 0; i < data.length; i++) {
            result[i + saltLength] = (byte) (data[i] ^ keyStream.nextByte());
        }
        return result;
    }

    public byte[] decode(byte[] data, String secret) {
        // extract salt from the start of the encrypted data
        byte[] salt = Arrays.copyOf(data, saltLength);

        KeyStream keyStream = new KeyStream(salt, secret);

        byte[] result = new byte[data.length - saltLength];
        for (int i = 0; i < result.length; i++) {
            result[i] = (byte) (data[i + saltLength] ^ keyStream.nextByte());
        }
        return result;
    }

    // end public interface

    private final int saltLength;
    private final MessageDigest digest;
    private final SecureRandom random = new SecureRandom();

    private class KeyStream {
        // a stream of bytes derived from the salt and the secret String

        private byte[] secretBytes;
        private byte[] streamBytes;
        private int position;

        KeyStream(byte[] salt, String secret) {
            secretBytes = secret.getBytes(StandardCharsets.UTF_8);
            // create initial set of bytes by hashing the salt and secret
            digest.update(salt);
            digest.update(secretBytes);
            streamBytes = digest.digest();
            position = 0;
        }

        byte nextByte() { // returns the next byte in the stream
            if (position >= streamBytes.length) {
                // get some new bytes hashing the old bytes and the secret
                digest.update(streamBytes);
                digest.update(secretBytes);
                streamBytes = digest.digest();
                position = 0;
            }
            return streamBytes[position++];
        }
    }
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.