TreeShell PRNG and Encryption Algorithm Review

Question

I've always wanted to come up with my own algorithm for encryption. Last evening I started writing "TreeShell" encryption algorithm that uses bit shifting and XOR operations on the bit level to do encryption.

This algorithm allows arbitrary length of data and protection key. The key is not stored, but hashed together with the random IV. The random IV is generated from TreeShell's own PRNG, which is shown below.

The length of the final ciphertext is not affected by the length of the key provided, but is the fixed-length IV prepended to the encrypted plaintext.

<?php

class TreeShell{

    const BLOCK_SIZE = 16;
    const BYTES = 4;
    const KEY_LENGTH = 256;

    public function encrypt($key, $plain){
        $iv = $this->iv();
        $ivs = $this->ivArrToString($iv);
        $keyHash = $this->keyHash($key, $ivs, $iv);

        $kHL = count($keyHash);
        $l = strlen($plain);
        $s = '';
        for($i = 0; $i < $l; $i+=4){
            $k = $i % ($kHL);
            $m = $this->stringToBlock($plain, $i);
            $j = $m ^ $keyHash[$k];
            $s .= $this->blockToString($j);
        }
        return $ivs . $s;
    }

    public function decrypt($cipher, $key){
        $ivsL = self::BLOCK_SIZE * self::BYTES;
        $ivs = substr($cipher, 0, $ivsL);
        $iv = $this->stringToIVArr($ivs);
        $keyHash = $this->keyHash($key, $ivs, $iv);

        $cipher = substr($cipher, $ivsL);
        $l = strlen($cipher);
        $kHL = count($keyHash);
        $s = '';
        for($i = 0; $i < $l; $i+=4){
            $k = $i % ($kHL);
            $m = $this->stringToBlock($cipher, $i);
            $j = $m ^ $keyHash[$k];
            $s .= $this->blockToString($j);
        }
        return rtrim($s);
    }

    private function iv(){
        $iv = array();
        for($i = 0; $i < self::BLOCK_SIZE; $i++){
            $iv[] = $this->prng(286331153, 4294967295);
        }
        return $iv;
    }

    private function stringToIVArr($ivs){
        $a = unpack('C*', $ivs);
        $l = count($a);
        $r = array();
        for($i = 1; $i <= $l; $i+=4){
            $c = 0;
            if(array_key_exists($i, $a)){
                $c += ($a[$i] << 24);
            }
            if(array_key_exists($i + 1, $a)){
                $c += ($a[$i + 1] << 16);
            }
            if(array_key_exists($i + 2, $a)){
                $c += ($a[$i + 2] << 8);
            }
            if(array_key_exists($i + 3, $a)){
                $c += ($a[$i + 3]);
            }
            $c = (($c & 0xFFFF) << 16) | (($c >> 16) & 0xFFFF);
            $r[] = $c;
        }
        return $r;
    }

    private function ivArrToString($iv){
        $s = '';
        foreach($iv as $a){
            $s .= $this->blockToString($a);
        }
        return $s;
    }

    private function blockToString($block){
        $block = (($block & 0xFFFF) << 16) | (($block >> 16) & 0xFFFF);
        $a = array(
            ($block >> 24) & 0xFF,
            ($block >> 16) & 0xFF,
            ($block >> 8) & 0xFF,
            ($block) & 0xFF
        );
        $s = '';
        foreach($a as $v){
            $s .= chr($v);
        }
        return $s;
    }

    private function stringToBlock($s, $i){
        $s = substr($s, $i, 4);
        $c = unpack('C*', $s);
        while(count($c) < 4){
            $c[] = 0;
        }
        $block = ($c[1] << 24) | ($c[2] << 16) | ($c[3] << 8) | ($c[4] << 0);
        $block = (($block & 0xFFFF) << 16) | (($block >> 16) & 0xFFFF);
        return $block;
    }

    private function keyHash($key, $ivs, $iv){
        $a = array();
        $l = strlen($key);
        $r = array();

        $y = $l;
        $o = $key;
        while($l < self::KEY_LENGTH){
            $key .= $o;
            $l += $y;
        }

        $key .= $ivs;
        $l += strlen($ivs);

        for($i = 0; $i < $l; $i+=4){
            $k = $i % self::BLOCK_SIZE;
            $m = $this->stringToBlock($key, $i);
            $j = $m ^ $iv[$k];
            $r[] = $this->hash32shift($j);
        }
        return $r;
    }

    private function bitRotate($value, $bits){
        if ($bits >0 ) {
            $bits %= 32;
            $value = ($value << $bits) | ($value >> (32 - $bits));
        } elseif ($bits < 0) {
            $bits = -$bits % 32;
            $value = ($value >> $bits) | ($value << (32 - $bits));
        }
        return $value;
    }

    private function hash32shift($key){
        $c2 = 0x27d4eb23; // a prime or an odd constant
        $key = ($key ^ 61) ^ $this->bitRotate($key, 16);
        $key = $key + ($key << 3);
        $key = $key ^ $this->bitRotate($key, 4);
        $key = $key * $c2;
        $key = $key ^ $this->bitRotate($key, 15);
        return $key;
    }


    private function prng($min = null, $max = null){
        static $seed = null;
        if($seed == null){
            if($min && $max){
                $seed = 2.14;
            }elseif($min){
                $seed = 1.24;
            }elseif($max){
                $seed = 0.78;
            }else{
                $seed = 0.65;
            }
            $i = ceil(time() % 50 * 5) + 10;
            while($i --> 0){
                $f = (sin(5 * pow($seed, 3)) + cos(10 * pow($seed, 2)) + 2) / 4;
                if($f > 0.5){
                    $seed += ceil($f * 96);
                }else{
                    $seed -= ceil($f * 32);    
                }
            }
        }
        $f = (sin(2 * pow($seed, 2)) + cos(3 * $seed) + sin(3 * $seed) + cos(2 * $seed) + 4) / 8;
        if($f > 0.5){
            $seed -= ceil($f * 1440);
        }else{
            $seed += ceil($f * 512);    
        }

        if(func_num_args() == 2){
            $f = ($f * ($max - $min)) + $min;
            if(is_int($min) && is_int($max)){
                $f = (int)ceil($f);
            }
        }

        return $f;
    }

}

I've tested the randomness of the PRNG as well as the data integrity of the ciphertext generated (by encrypting then decrypting a sample message using the same key). They look good to me.

How can I determine if this algorithm can be cracked within a reasonable time?

Note: The current problem with this algorithm is that given a plaintext is encrypted with a key "abc", and decrypted with the key "bcd", some of the plain text is decrypted. I am working to fix that. If you were writing the algorithm, what will you change in this algorithm to fix that problem?
The hash function has been fixed to make it to have more avalanche effect. Previously the avalanche effect was hardly seen, as such a similar passphrase used will reveal the encrypted plaintext partially.

Answer 1

First, an important disclaimer: I am not a crypto expert (IANACE). Because of this, I will not be reviewing your code in specific. I also encourage you to only trust reviews from crypto experts.

As I understand it, the most important thing to decide if your algorithm is strong is to learn about existing techniques for breaking algorithms, then apply those techniques against your own algorithm. Your algorithm must be able to withstand all existing known techniques.

Most homegrown ciphers are easily breakable, because they fail to consider techniques used by seasoned cryptographers. For example, there are many types of known-plaintext attacks, known-ciphertext attacks, and so on. (Many of them are catalogued in Bruce Schneier's excellent Applied Cryptography book.) You need know how to apply them all.

Another class of attacks to consider are side-channel attacks, and in particular timing oracle attacks. Does your function take longer or shorter if the key is invalid? This gives your attacker valuable information, and in the worst case allows them to reconstruct the correct key.

I also can't comment on the strength of your PRNG, but consider where your sources of entropy are, and whether an attacker can manipulate those to achieve less-than-random output.

As for your KDF (key derivation function), consider whether well-chosen ASCII passphrases (the most common case) give good coverage of the possible keyspace. You want good coverage, so that key distribution isn't skewed for the commonest class of passphrases---that would give an attacker valuable information. Also consider whether similar passphrases give rise to similar keys. They should not. Small changes to a passphrase should result in huge changes to the key, so that the passphrase isn't so easy to derive from a working key.

There are other things to consider also, but again, I'm not a crypto expert. But I hope this will get you started. :-)

Answer 2

They look good to me.

Sure, you are human. But what “looks” random to humans doesn't always have to be random. Have you done any tests like the DieHarder suite (provided by Robert Brown of Duke University) to check on the true randomness of you PRNG implementation? You definitely should check for entropy etc. before even thinking your prng is really as random as it seems to be! There are also smaller tools like fourmilab's ENT, but since you are targetting cryptography, I would go for the DieHarder suite as it covers more tests.

Also…

Your algorithm uses a pseudo-random number generator - which tends to be cryptographically insecure because it is not truly random. Instead a PRNG's output walks along the fixed sequence the PRNG produces. In a worst-case scenario, an attacker would only need to recover a few bits of your prng to recover the whole state of that PRNG … which would be a so-called "State recovery attack".

---

Btw.: Please feel invited to drop by at Crypto.SE and ask some questions if you need more indeep information related to cryptography, cryptographic, and or potential crypto-related security issues.