How ecbscryptogen works, lots of gory details.
The ecbscryptogen program, how it works, and why it's secure.
Here is why ecbscryptogen is secure.
The way cryptographers crack ciphers is to analyze the output and the intermediate output of cipher algorithms to find correlations. Eventually they work out the weaknesses and can figure out a way to reduce the various possibilities they need to test to figure out the original key, and thus decrypt the message. But this relies on the fact the the cryptographer has a copy of the program used to create the ciphertext. But what if they don't have a copy? The argument cryptographers use is that of course there is always a chance that a copy could get loose into the wild no matter how secure the computer, so they simply assume that the cryptographer will always know the exact algorithm used. That is true for most cryptosystems.
What makes ecbscryptogen different is that there is no single algorithm and there is no program that is used more than once to encipher a plaintext. What we do is instead of just using the secret key to encrypt the data, ecbscryptogen uses the secret key to generate a random crypto program in the ecbs PRNG family. They all have the same basic stucture which the cryptographer will know, but the details will be different for every execution, so the cryptanalysis has to be generalized to work on all instances, which is a much bigger problem. All the cryptographer has is the general algorithm structure and the ciphertext, but not the actual program used. Even the user will not know the details because the generated program is used once and then deleted so nobody ever sees it. It will never be generated again since the random nonce is 256 bits.
So we have two things going for us. First we generate a whole new program, which you could think of as a gigantic nonce thingy in and of itself, because its only used once. Second, we have the real 256 bit nonce that is used to seed the LFSR. Remember, a nonce is only used once, and it doesn't have to be secret because we encrypt it before using it to seed the LFSR. The reason you can use the same key over and over is that we only use the user provided secret key to encrypt the nonce. And since nobody knows or will ever see the encrypted nonce, the seeded state it produces is never revealed. And after that, the user provided key is never used again.
You have four 64 bit counters initialized with random 64 bit values. You have 127 64 bit state elements initialized with random 64 bit values. You have a shift variable that is decremented twice on each call and used to rotate two elements of the state array.
You have 8 taps initialized to random unique element indexes of the state array. The taps are decremented on each call and reset to max value when passing below 0.
The tap1 element of the state array is rotated shift times.
Four elements are operated on with one multiply and three random operations selected from plus, minus, and XOR, with the result stored in the tap1 element.
One tap is chosen based on the value of one of the tapped elements and the value of that tap is swapped with the value of the next tap, cycling back to tap 0 when the last tap is selected. This is sort of a reverse bubble sort.
Then the shift variable is decremented again and tap5 element is rotated shift times.
Four elements are operated on with one multiply and three random operations selected from plus, minus, and XOR, with the result stored in the tap5.
One of the tapped elements is used to check matching constant value that will cause a reset fuction to be called, amounting to about once every million calls on average. This totally resets all the tap values and the length of the state array. This means that some of the elements in the upper end of the state array are only spradically used, while elements near the beginning of the state array are always used.
So what the cryptographer knows is that these things are happening, but unlike other algorithms, he doesn't know which elements are being used for what operations. Even though all the operations are deterministic, including the constant values generated by the ecbscryptogen program when it creates the ecbscryptog program which has a strictly defined algorithm, that will never be repeated or used again. We simply use a different cipher algorithm every time we run the program. No two messages will ever be encrypted using the same algorithm, ever.
This is all the attacker has to go on. The question marks represent unknown constant values and in the formula lines, unknown parenthesis that may or may not exist, affecting the order of the unknown operations. I left out the taps decrements because they never change.
lfsra[?] = lfsra[?] ? adder1;
lfsra[?] = lfsra[?] ? adder2;
lfsra[?] = lfsra[?] ? adder3;
lfsra[?] = lfsra[?] ? adder4;
lfsra[tapa1] = ??lfsra[?]??? ? ??lfsra[?]??? ? ?lfsra[?]??? ? ??lfsra[?]???
--shift
if (shift == 0) {
shift = 63;
}
lfsra[tapa1] = ((lfsra[tapa1] >> shift) | (lfsra[tapa1] << (64-shift)));
swap = (lfsra[?] ^ lfsra[?]) & 7;
switch (swap) {
case 0: tmp = tapa1;
tapa1 = tapa2;
tapa2 = tmp;
break;
case 1: tmp = tapa2;
tapa2 = tapa3;
tapa3 = tmp;
break;
case 2: tmp = tapa3;
tapa3 = tapa4;
tapa4 = tmp;
break;
case 3: tmp = tapa4;
tapa4 = tapa5;
tapa5 = tmp;
break;
case 4: tmp = tapa5;
tapa5 = tapa6;
tapa6 = tmp;
break;
case 5: tmp = tapa6;
tapa6 = tapa7;
tapa7 = tmp;
break;
case 6: tmp = tapa7;
tapa7 = tapa8;
tapa8 = tmp;
break;
case 7: tmp = tapa8;
tapa8 = tapa1;
tapa1 = tmp;
break;
default: break;
}
lfsra[tapa5] = ??lfsra[?]??? ? ??lfsra[?]??? ? ?lfsra[?]??? ? ??lfsra[?]???
--shift;
if (shift == 0) {
shift = (lfsra[?] & 63);
if (shift == 0) {
shift = 63;
}
}
lfsra[tapa5] = ((lfsra[tapa5] >> shift) | (lfsra[tapa5] << (64-shift)));
if ((lfsra[?] & power) == ?) {
setsize = ( lfsra[?] & (MAXLEN-1) );
setsize |= (MAXLEN/2);
ecbs64setsize(setsize);
}
return(lfsra[tapa?] ^ lfsra[tapa?] ^ lfsra[tapa?] ^ lfsra[tapa?]);
The parts that never change are the tap decrements and tap swap order. It would be too much code to randomize the tap swaps any more than just picking one at random. Picking a second one is another line of code to execute.
Ok, thats the PRNG part but there is also the encryption part. First, when encrypting, the gen program creates a nonce that IT uses to create the encrypt/decrypt generated program. This first nonce is used by ecbscryptogen and has nothing to do with the encrypted message. It just tells ecbscryptogen of the future how to create the encrypt/decrypt program. When those programs are run, they just ignore the first 256 bit nonce. But the encrypt program adds its own 256 bit nonce which is used to seed for encrypt or decrypt. The generated program is the same program for encrypt and decrypt, only executed with E or D flag by the ecbscryptogen program.
So ecbscryptogen creates ecbscryptog (without the "en" at the end), and then executes that with -E or -D flag. So it looks funny that the decrypt program runs and ignores the first nonce entirely, because it was used to create the program reading it. In addition, the nonces are really 320 bits because they are really 5 64 bit integers. The last 64 bit integer of the second nonce is used as a message nonce to replace the first "last plaintext" block which doesn't exist but is needed for CBC mode. One thing I don't do is encrypt the last plaintext block before saving. Rather than feed in the output that anybody can see, I prefer to use the unknown plaintext input. Without encryption, that could be part of a known plaintext attack but I don't think it's feasable. I will revisit this one. Maybe both pre and post encryption should be used.
So what happens is each new plaintext block is first saved away, and then XOR'd with the last plaintext block BEFORE encryption. Then last plaintext block becomes the new plaintext we saved before encryption. The encrypted block is then written out and we start over. There is no separate encryption of the last plaintext block because that would double the time, or seriously impact if we used reduced rounds on the internal encryption. But I have another thing. We also feed the last plaintext block into the LFSR by mixing with an LFSR element. Right now that's hardcoded in the generation program, but could be randomized to almost any LFSR element. The randomization would only be in the generation program and in the generated program it would be hardcoded. We can mix in plaintext or XOR'd plaintext or output text into any LFSR element or any of the adders except adder1 and adder2 which should never be altered ever. Since ecbs is variable length, we might want to limit to elements in the first half of the LFSR array which are always in use because the shortest length is always at least half the maximum length. That means the LFSR length is always at least 65 and up to 127. 64 and 128 are not allowed as valid LFSR lengths in ecbs64. So thats any of 65 LFSR elements or one of the two adders, 3 or 4. This mixing is done before the encrypt or decyrpt call, and will take effect immediately if using adder3 or adder4 and randomly lagged using any other LFSR element, average of 12 bytes between taps so on average any of the lower LFSR elements will have an average effect lag of 6-7 ecbs64() calls. But since the fiestel structure uses 2 calls per block times number of rounds so at minimum the LFSR feedback lag will take 3 encrypt calls to affect the PRNG output. And if using default 4 rounds, thats 8 calls, so probably the next encrypt will be affected by the PRNG feedback from the last encrypt.
Finally, for last block padding, I have to use an additional block that does nothing but tell how many bytes of the last black to use, because the original input file might not end on an 8-byte boundary. We may have 1 - 7 bytes leftover. So I always add lastblock count block after the very last block of encrypted plaintext data. Now Bruce Schneier recommends using a 1 bit followed by some 0 bits and finally the last block count. I think that might be because of poor encryption algorithms that work better with some 1 bits mixed in. That's not a problem for ecbs64 but for simplicity I just take that number, it will be a 64 bit unsigned integer with value ranging from 1 to 8. First encrypt noncebuffer[4] and XOR the lastcount block with that, and then encrypt it. For decrypt, first encrypt noncebuffer[4] to move the lfsr state but then decrypt lastcount block and then XOR with noncebuffer[4] to restore the 1-8 value. This provides pretty much random input to be encrypted so the final output block which is always known to be the lastcount block can be encrypted to many more possible outputs than just 7 possible inputs could produce. I think not equivilent to simply encrypting twice, because using the nonce provides another unknown input to vex the cryptographer.
There are a few steps taken to prevent data leakage.
First, ecbacryptogen can be run in interactive mode so that command line parameters are not seen by the ps -ef command. If no CLI arguments are given it prompts for E or D, filename, number of rounds, and any key arguments. The key data has to be given part by part if there are more than one part. You can't just put it all on one line if you have multiple key strings or file. But if you enter them in the same order they will be used the same way. For example, a readable file or empty file is processed identically either way, and a string is added to state the same way with the one exception that strings must NOT be quoted in interactive mode, and backlashes have no effect in interactive mode. But for the most part, if you know what the shell does with backslashes, you can enter them like that to get the exact same internal key. The shell strips off the enclosing quote marks, interactive mode does not. The shell alternates removing consecutive backslashes when followed by a backslash or double quote. Interactive mode does not. So it's not always identical to CLI key data input, but for the most part it is, unless you have a lot of backslashes in your key material. Any real ecbscryptogen CLI option given in the interactive key data input is ignored entirely. The interactive key data input cannot be used to enter CLI options, and the real CLI options cannot be used as CLI or interactive key data. You can put them in a file and let it read the file, but thats the only way.
Second, we attempt to find a memory based filesystem to create the generated program and its executable in. Third, we use shared memory to pass the PRNG state, the encrypt/decrypt flag, number of rounds, and filenames, to the generated program. ecbscryptogen creates a shared memory in the OS, and writes all the stuff needed for the generated program to do it's job. Then it executes the generated program. The first thing the generated program does is read the shared memory to load the PRNG state and get it's instructions. Immediatly after reading the shared memory it is destroyed. ecbscryptogen also attempts to destroy it, after the generated program execution has returned, just in case something went wrong. Additionally we use a random proj_id number for the ftok() call. I found through testing that any 8 bit integer will work. The filename has to be either "shmfile" or "/dev/shm/shmfile" and it works. But, if you want to use any other filename, then that file has to exist in /dev/shm or some other memory based filesystem. All you have to do is touch the file, and rm it afterwards. But that leaks too much information, so I just use /dev/shm/shmfile and keep it in the OS only. The execution is simply the name of the file and nothing else.
/dev/shm/ecbscryptog
One thing you could do is move the ecbsgryptogen executable to your home bin directory. Name it bash. Then change your environment $PATH variable to have your ~/bin directory come before /usr/bin. As long as you don't duplicate real system commands in your bin directory, it won't hurt anything. Then from in your home bin directory, run bash. Don't use ./ or full path, just "bash" by itself. It will look identical to a normal bash shell in ps output. I'm not that worried about it though, if they are on my computer and seeing ps output, I've already lost.
Ok so to use this securely you need to have a secret key. That secret key has to be long, random, and secret. Unfortunately, in our universe, it's easy to select two of the three, but all three at once is damm near impossible. About the best you can do is have something you can remember that is very long, or something written down on paper that can be kept secret. And if you want to be able to share ciphers then you have to share not only the cipher program, but the secret key as well. I would use the most totally random printable stuff, kept on paper for transfer. To exchange secret keys, you can do it any way you want, but over the internet. Some folks use encrypted email, or TXT messages on the cell phone, or a voice call. But I would use physical exchange of paper first if possible, and TXT message with some sort of secondary authentication, such as getting a TXT message that contains a passkey that you enter into a web site, and then it generates a one time use number that you MUST use within minutes to get a secret key. Or you could just meet the other guy in a public place and give him a peice of paper. Or you could walk past him discretely in the subway and make a hidden transfer that nobody would notice. Or you could use a dead drop somewhere. Unless you or the other guy are under active surveillence, the dead drop is the safest way. The worst that can happen is it gets lost to animals, weather, garbage collection, or whatever. One dead drop you can easily use is to go into McDonalds, and order. Sit at a table, it could be the waiting area table for the to-go customers. Have the secret key on a sticky pad, and stick it under the table near the center. If anybody other than the intended recipient finds it, which is unlikely, they won't have a clue what it is. If you suspect that happens, don't ever use that same restaraunt for a dead drop location. But if the sticky pad is sticky enough, it won't fall off. You can use a small piece of duct tape to make sure it wont fall off. Nobody will reach under there looking for it.
A real possiblity is to use a web site and TXT message. The TXT message, or email, is not encrypted. But the message provides a secret key, that may be compromised already, but may not be. The recipient is sent to a web site, with the secret key provided in the clear by the email or TXT message. Recipient enters the secret key and is provided another secret key in response. The second secret key is the one to use to obtain a third secret key which is the real one time secret key. The web site will never return the same number for the same input. So it's a race. If the recipient can get to the web site before the eavesdropper, and if the eavesdropper cannot intercept the web site traffic, then the winner gets the usable first and second secret keys, but if Eve, gets there first, then the recipient will get an invalid pair. The recipient can tell by running some test for standardized input that should produce standard output. If the eavesdropper can intercept traffic from both sender and recipient, then no key exchange can work without some sort of diffie-helleman type protocal. But if those are already broken by NSA, and how many unkown others, you better resort to physical exchange, maybe mixed with some code.
Here's a cumbersome but probably secure way to exchange secret key with somebody across the country without meeting in person. Use snail mail, the US Postal Service. First, travel to some city far away, that you would never normally go to. Make sure you are not being followed. Buy some very common stationary. Get some sort of innocent looking, real return address, from nearby, but NOT your address, just some realistic address, such as the local library. Overdue book, yeah, thats the ticket. Handle all this stuff with care. Use rubber gloves and leave no DNA or prints. Even the slightest cough or sneeze will load it up with your DNA. You have to do this outdoors, on the balcony. Keep it inside another bigger, DNA free manila envelope until you can drop it discretely in a mailbox that would not arouse suspicion. For example, if the return address is on the other side of town, you might need some excuse to visit that part of the city.
This envelope is addressed to your recipient and it contains whatever seed information you need to transfer, perhaps, mixed with other stuff to not look like a secret key. You may have to provide hints in different ways for the recipient to be able to extract the correct secret key.
Remember, CIA, NSA, FBI, and so on, are able to open, examine, and even alter any physical stuff in postage mail. They have technical abilities to put it all back together totally undetected. And this is not just steaming the envelope open, anybody can do that. That's why lawyers often send their envelopes all taped up, so that tampering will be evident. So consider that and if you do use all those effects and things in a remote city, make sure there is no DNA on anything, and you have to destroy ALL leftovers and evidence that they ever existed, without a trace. And that can only be done by burning. But you have to be discrete. You can't have a bonfire in some city park.
It might be best to keep everything and burn it all when you get home, in small batches, until it's all gone. At that point you've done all you can short of physical contact in Istanbul.
Here's a fun, and practical way do it, if you can both get to the same city. Use an untrusted third party.
You go into McDonalds, or some drugstore or some place like that, and make sure they have a lost and found bin. Many public places do. Then you hang around for a while, have a coffee, or browse the aisles or whatever folks normally do at that place. Then walk up to the service counter and tell them you were supposed to meet a buddy and give him some pictures, or whatever sounds normal, could be some of your special Giant Pumpkin seeds, a textbook, something he forgot at your house, just anything. Of course it contains the secret key inside somewhere, but otherwise, just a normal jacket, or whatever he forgot. It could be an expensive pair of sunglasses, minus the case, so it's in a paper bag. You can write on the inside of a paper bag.
Now tell them he got hung up in traffic and you have to go to an important meeting, so could you just leave it in their lost and found, and you'll call your buddy and tell him to just pick it up here. Of course they will understand, and you put the label on it so they can identify it when he comes in. Give them as little information as possible about you or his real identity. If they want to see a driver's license, that's Ok, they won't run it through the computer, and they won't remember the name. It will be on the tag, just his name, that's all they get, and they won't record it or remember it.
You can do this just for fun at Fred Meyer or other large store that has a sit down deli counter with fast food. Order something and sit down for lunch. Then get a pretend phone call from work about some emergency and you are needed back at the office, or on a computer to fix an outage or something. Now it all looks normal to all observers, and you have a good excuse to give something of some nominal, but non-zero value to some third party, the deli counter guy maybe, or the lost and found department, and they hold it for you. Of course your buddy is right outside, hidden from view and waiting for you to leave, after which he makes his entrance.
The beauty of this scheme is that even if you are being tailed by the feds, the third party holds the secret key, and the feds have to take it from them. Unless you are a really big fish, they have to blow their cover to retrieve the secret key. And if your buddy is fast enough, he gets there before the feds do, and gets the secret key with no fuss. They literally have to make a federal case out of it to get the secret key, and in that case, they already enough stuff on you and the secret key is just preventative because it hasn't been used yet. They don't want to let on that they are surveilling you by revealing that they have the secret key which your buddy would find out if he got there late.
Links and my story so far.Explanation and detailed description of the algorithms and why they are as they are.
How to use testecbs8 and testecbs64.