Explanation of ecbs and ecbscrypto


This is my explanation and discussion page. You need to know how ecbs works to know how to use the test programs and verify my claims.

ecbs PRNG algorithm and my claims

The ecbs PRNG and crypto programs are written in C and run on Linux X86-64 platform. They should work on any modern version of Linux but I can't say for sure since I only have Fedora and CentOS. But I'm 99 percent certain.

The ecbs algorithm consists of several components, each of which contributes to the overall output, but some of them seem redundant since they can be disabled and still pass Practrand. The algorithm is designed to be robust. 

1. There are no weak keys.
2. The details of the hardcoded values do not matter.
3. The ecbs algorithm can be scaled down to 8 bit integers resulting
   in 131 state bits and 9 LFSR elements without a setsize function,
   and 243 bits with setsize and 9-15 elements, to allow for different sizes.
4. Individual components of the algorithm can be disabled or altered
   to always return a constant value, and it still works well.
5. Only one secret key needed. It uses nonces, so the active key is
   always created from /dev/random and encrypted by the secret key
   before replacing the secret key in the PRNG state.
As a result of 2, we can alter the algorithm almost any way, as long as we leave the same structure and it doesn't matter. All we need to do is ensure we start from a known state to get repeatable results. As a result of 5, you only need one secret key for yourself, forever. But if you want to share encrypted data with another person, then you would need a different secret key that only you and the authorized other know. To do that you have to be able to trust the other and never mix you personal data with the shared data. That's easy enough if you only want your trusted family members to be able to decrypt your data. Or maybe it's your lawyer, or your doctor, or whatever. But they each need the same version of ecbscryptogen and the same key. Because ecbscryptogen creates new programs, a version system does not make sense. Instead, I have a signature (using -v to display) which is two random numbers generated from a standard starting state. Note, the taps are all labeled tapa with a digit. This is because initially I considered haveing more than one set of taps, tapa1-n and tapb1-n, and possibly tapc1-n. During development it became clear that multiple sets of taps would bloat the code and cause more opportunity for error than it was worth. So I only used one set of taps, but kept the label tapa. That's why they are not simply tap1-8. 
lfsralen = 127;
lfsra[i] = i;  /* This sets their value to same as their index number */
adder1 = 0;
adder2 = 0;
adder3 = 0;
adder4 = 0;
shift = 63;
tapa1 = 0;
tapa2 = 1;
tapa3 = 2;
tapa4 = 3;
tapa5 = 4;
tapa6 = 5;
tapa7 = 6;
tapa8 = 7;
After this, ecbs64() is called MAXLEN*2 times, and then the next two numbers are saved as the signature. This will always start from the same initial state, so the only difference in output will be if the ecbs64() algorithm is different. The signature() function call replaces whatever the current state is, with the above state, and then restores the previous state as if nothing had happened. The signature is not used for anything except display. It can't tell you if it will decrypt any particular file, but it can tell you if you are using the same program or not, in case you ever change something in the algorithm for testing or any other reason. This is how you can tell if your copy of ecbscryptogen will work with somebody elses copy.

The first component is the LFSR which consists of 9 to 127 elements, and 8 taps. The taps are set to any unique values within the LFSR elements range. Taps are always decremented in lockstep on each call to ecbs, and are reset to the maximum value, (the last element of the LFSR), when they drop below 0.

When I refer to tapa below, I mean the element pointed to by tapa. It's too awkward to continually say "the element pointed to by tapa1" so I just say tapa1 or tapa5 or whatever, but really it means the LFSR element, not the actual tap value.

Next we have the formulas which update the values of tapa1 and tapa5. Tapa1 and tapa5 are eventually XOR'd and returned as the random number. There are two formula lines, one for tapa1 and one for tapa5. They mix their update taps with taps 2-4 for tapa1 and taps 5-8 for tapa5. So, now we have, taps, LFSR elements, and formulas to update the LFSR elements and return a number.

Then we have rotates for tapa1 and tapa5. These are determined by the shift variable which specifies the rotate amount. The shift variable is decremented and reset to some value between 1 and 63 based on one of the tapped elements. The tap chosen for this should not be use for other things outside the formula lines, but taps do have to be reused for this, and other things. That sounds bad and really having a whole nother set of taps might be better, but we are already ridiculously big and slow.

Also we have the adders, which are four 64 bit numbers that are used as a single 256 bit counter. Each these values is mixed with a tapped element. Once again, we have to reuse taps from the formula lines, and thats not ideal, but I think its workable here. The alternative is another set of taps to decrement.

Here, for tap swaps, I mean tha actual values of the taps, and NOT the LFSR elements they point to.

Then we have tap swaps. We select a tap at random based on some tapped element. That tap is swapped with its immediate neighbor to the right, thus tapa1 would be swapped with tapa2, and tapa7 would wrap around and be swapped with tapa1.

Finally we have a check to reset the size of the LFSR. This uses the power variable and if a tapped element matches a hardcoded number of size of the power variable, then the setsize function is called. The setsize function resets the size of the LFSR and reassigns the taps, and updates all LFSR elements. It does this by calling ecbs and saving the output to generate new values. The LFSR alements are not explicitly updated, but the taps and counters are, and by calling ecbs for random numbers to update the taps and length, the elements get mangled beyond recognition, and travel a totally different path.

So we have these important elements and they happen in this order. There are two formula lines and two decrement shift and rotate tap lines. 

1. LFSR and taps - Decrement taps
2. Adders - Increment the adders and mix with tapped elements
3. Formula one - Mix tapa1, tapa2, tapa3, tapa4
4. Shift - Decrement shift value and reset to value of tapped element % 63
5. Rotates - Rotate tapa1 based on shift value
6. Tap swaps - Swap one tap with its neighbor based in value of tapped element
7. Formula one - Mix tapa1, tapa2, tapa3, tapa4
8. Shift - Decrement shift value and reset to value of tapped element % 63
9. Rotates - Rotate tapa1 based on shift value
10. Setsize - Check if some tapped element % power = some hardcoded number
11. Return tapa1 XOR tapa2

Each of these elements, except the LFSR and taps, can be turned off or disabled using the testecbs programs. Thats what those programs are for. The intersting thing is that the formulas can be replaced to return a constant values for tapa1 and tapa5, so they always get set to the exact same number on every call, and yet it still passed practrand to a terabyte or more. Same thing with the tap swaps. Disable completely and the random numbers are still good. Disable rotates and it still works. Disable the adders and it works if there are some one bits in the LFSR elements. By disabling certain components, you can see that the rest of them are robust enough to still generate good numbers and pass Practrand to terabytes. Now when you read the help output you'll know what you are doing. The one thing that causes instant failure is to disable the adders completely and zero out the LFSR. There must be a 1 bit somewhere in the adders being used, or in the LFSR elements. But that state can't happen in the normal ecbs algortihm because the adders are always used, so for real use, you can consider the all zero state to be as valid as any other.

The full algorithm is used in ecbscrypto and ecbscryptogen which both use 64 bit blocks and ecbs64 PRNG. I haven't made an 8 bit version of the crypto programs because they are actually useful and work as is. The crypto programs are not for testing, they are for real life use. Of course you would be stupid to use them for anything in real life, but they are available nonetheless.

You can test ecbscryptog with Practrand by changing the ecbscryptog program to pipe directly to RNG_test, or mcp or bigcrush or whatever. But you would have to edit and recompile ecbscryptogen.c because of the shared memory data transfer mechanism. There is a shmctl command to destroy the shared memory segement. You must first comment out this line, in the if (savefiles) conditional.

shmctl(destroyshmid,IPC_RMID,NULL);

Leave the other one just before normal unlinks. Uncomment the fprintf line, just after the sprintf(command line, so it will print the command. Leave the sprintf command as is, but we don't let ecbscryptogen execute it. 

        sprintf(command, "cat %s | %s >> %s", filename, myexe, outfile);
/*fprintf(stderr, "%s\n", command);*/

Finally, comment out the system command. This is so ecbscryptogen does not execute the command which would read the shared memory and destroy it. Make sure you delete the one in ENCRYPT section, not DECYRPT section. 

        system(command);

There are exactly three lines that need to be changed. The fprintf line has to be UNCommented, and the system and shmctl commands have Commented out. They are each marked in the source code with a comment line containing the word "Comment" with upper case C. Search for "Comment" in vi to find these lines. They are the only lines you need to mess with.

Then compile and run the ecbscryptogen program normally with the -g CLI option. You will have to provide a filename, and a secret key. The filename doesn't matter, we won't really be using it, but it has to actually exist.

The generated program is in either /run/user/uid/ or /dev/shm/ or current working directory. We try to save it in a memory based filesystem first and hard disk only if no other choice. That program is named ecbscryptog.c without the trailing n in cryptogen. You can uncomment the fprintf that prints the "mycompile" string to see the full path if you want. That prints the compile command which includes both the source code file name and the executable filename with full path specification. But usually it will be /run/user/uid/ or /dev/shm/ or current working directory.

After running ecbscryptogen with -g flag. The fprintf command string will print something like this. My uid is 1000, and that's the default for first user on the system. So that's why the path below has 1000 in it, but yours might be different. Use the id command to find out. 

    cat tmp.txt | /run/user/1000/ecbscryptog >> tmp.txt.enc

Change that to read more like this, using /dev/zero for endless input file. You could use your own plaintext generator or any file for the input file. 

cat /dev/zero | /run/user/1000/ecbscryptog | RNG_test stdin64

Now you are encrypting nothing but an endless stream of zeros. Here is the kicker. If you stop that process, and try to run it again, it will fail practrand immediately. The reason is because the shared memory is destroyed after use, so the second time you try to run it, ecbscryptog can get nothing but zero's from the nonexistant shared memory. This causes the LFSR output to be an endless stream of zero's because everything is initialized to zero from lack of shared memory to read state from. This is an intended feature.

Encryption will take a long time because each round requires two random numbers so we need 8 numbers per block, like using a 64 bit number for each byte instead of each 8 byte block. So it will run 8 times slower because we need to generate 8 times as many numbers for each number of output. But if you are patient it will pass eventually. If you live in a place with power outages, you might not be able to complete a 32 terabyte Practrand test. For the encryption, it would probably take a month or more. I haven't run all the tests yet because I'm still running various disabled 8 bit versions of testecbs8 with special key files to test the bare minimum needed to pass Practrand to 32 terabytes. I've done them in the past but I have to start all over with this new finalized version of ecbs algorithm. So I'm starting my testing from scratch, but I have no doubts about the results.

The testecbs programs are not meant for normal use. If you wanted to use the PRNG for a real purpose you would have to use the stripped down real version. You could use the 8 bit version as a very small PRNG on an 8 bit CPU and you could limit the size to 9-15 elements which would be a maximum state size of 15*8 + 4*8 + 8*3 + 8 + (8*8) = 248 bits. By removing the setsize function we could remove the 8*8 bits which hold the power number, and set the fixed size to say 12 bytes for 12*8 + 4*8 + 8*3 + 8 = 160 and you would get decent random numbers and a very long period. Speed may still be an issue though because of the the complexity, even removing the setsize check. It would probably not be masked by the pipelining and branch prediction of high end CPUs. However, for Intel X86-64 architecture these work fine if you can wait a few millionths of a second longer for each number.

If you download any of these programs, look at the source code first and make sure it looks legit. Actually read the source code and the comments to see what is going on. It's written in a very simple, easy style with lots of comments. Grep ^comp to get the compile command, or just figure it out yourself. There should be no missing libraries. It's all just the default stuff that comes with Linux. Then, after compiling, execute with just the -h option and pipe through less or other pager, and read all the help stuff. You need to know what the options do to use them effectively. You can just execute the programs with no CLI options and redirect the output to some program or file. The output is raw binary random numbers so it will mess up your screen.

The crypto programs are worthy of looking at. I know any cryptographer will say it's not worth their time to debunk, but like all Kruger-Dunning children, I still think my crypto programs are beyond reach of cryptanalysis because of the dynamic nature of the algorithm. Take a look at the source code for the encrypt and decrypt functions. The encrypt and decrypt functions are called by ENCRYPT and DECRYPT sections of main() that do some setup work with nonces and call the fencrypt() and fdecrypt() functions which use a standard feistel cipher with four iterations built in, and applied rounds number of times, where rounds is either default 4 or specified as CLI option. FYI, I named them fencrypt and fdecrypt to avoid name clash with built-in functions in the standard C library.

To use the crypto programs securely you must have a firewalled Linux computer with the basic standard install including the gcc compiler. It must be a single user machine with no logins except yourself. If you are not rooted, then it's safe to work with your plaintext documents. The crypto programs are not designed to be a complete backup and encryption program, all they do is encrypt or decrypt a single file at a time. They are not really useful for much other than keeping your backup files private in case you want to store them on the cloud or something like that.

The ecbscryptogen program is especially secure. First of all, it does not actually encrypt or decrypt, it creates a one time use program to do the encryption or decryption. The one time program is a random permutation of the ecbs PRNG and this program adds a second nonce to the output file for decryption. So ecbscryptogen uses two nonces, one to seed the PRNG for creating the one time program, and then the one time program adds its nonce for the actual encryption or decryption. The nonces are 320 bits, of 5 64bit integers, and these are encrypted by the programs and used to seed the PRNG state. Thus every time you run the ecbscryptogen program, it creates a ecbscryptog program which is unique and will never ever be generated again. After use, the one time program is deleted, removing any trace of the algorithm details. The reason we need two nonces is for decryption. ecbscryptogen must be provided a secret key. That secret key is used by ecbscryptogen to encrypt the first nonce and that encrypted nonce is used to reseed the PRNG. Then, using the new state, the one time program is created using random values for the constants. Then, ecbascryptogen compiles the one time program and executes it passing the CLI options needed to encrypt or decrypt and output a new file. The one time program, creates its own nonce and encrypts it, and uses that to reseed the PRNG again, so we use two completely different seeds to generate the program and to encrypt or decrypt the file. Because of this we have at least 80 bytes of nonce prepened to evey encrypted file. Additonally, there is an 8 byte final count block appened. Because we process 8 byte blocks we have to know have many leftover bytes we have at the end of the file because it may be not be an exact divisor of 8, and we can't just print out any extra zero bytes we end up with. So we have a total of 88 bytes added to every file encrypted. That's a lot and not good for small files. But for anything worth encrypting, it's worth the space. Read the How it works link below for more details.


Links to professional PRNG sites and a lot of discussion about ecbs

How to use testecbs8 and testecbs64

A cryptographic cipher program that leaves no trace of itself after use. How ecbscryptogen works.

     I have some files available for download, source code only.

     testecbs8.c     - Source code for the smallest version.

     testecbs64.c    - Source code for the largest version.

     ecbscrypto.c    - Source code for a standalone cipher program.
                       encrypts or decrypts, reads STDIN and writes STDOUT.

     ecbscryptogen.c - Source code for a "standalone, data dependent,
                       cipher program" generator program. This program
                       creates a new program and executes it to encrypt
                       or decrypt. Very mysterious, and harder than $%!^
                       to program and debug.
p> View or Download testecbs64.c, testecbs8.c, ecbscrypto.c, ecbscryptogen.c and some minor utilities.

Back to main index page.