XSE Algorithm Description | ||||||||||||||||||||
This scheme uses Marsaglia's XorShift PRNG set to
generate a keystream, and then uses it to encrypt plaintext by simple
XOR operation (in a way possibly not so easy to break). Each PRNG requires
a 32bit seed and generates a different sequence of 32bit integers of period
2^32-1. As you probably already know, they are fast (3 shifts and 3 xor
to generate a number) and have good statistical properties (and yes, they
can be seen as linear functions). Shift amounts and directions differentiates
the 648 PRNGs that form the complete set. The primary key of the algorithm
is 128bit long (the MD5 hash of the string inserted on the command line).
Firstly this key is extended to 1040 bytes by using the MD5 hash function.
This key can be viewed as an array of 32bit words.
For every 32bit word of input (read sequentially), 4
(possibly) different PRNGs are selected from the set. Four sequential
key words chosen from the extended 1040-bytes key are used as seed for
the 4 PRNGs, generating 4 new numbers. These four numbers are used to
replace the four words of the key and to encrypt the input word in this
way: the first two are xored together and the result is rotated by a certain
amount that depends on the chosen PRNGs. The same is done for the 3rd
and 4th word. The two resulting values are xored with the input word,
together with another value that depends (again) on the 4 chosen PRNGs.
To achieve higher security, the algorithm periodically regenerates the
key and changes the PRNG selection function. (I know that all this sounds
vague and confusing - read carefully the pseudo code below for a throughtful
explanation) The following technique is used to make the cipher resistant to chosen and known plaintext attacks, and to verify payload integrity: upon encryption an MD5 value ("uniqueID") is output before the actual ciphertext. If the plaintext comes from a file, this value is equal to MD5(MD5(plaintext)+key); if it comes from stdin, this value is set to 16 bytes read from "/dev/urandom". The actual base key used during encryption is MD5(key+uniqueID). By doing this, each bit of the key (and thus of the ciphertext) depends on the entire plaintext. Upon decryption, a check is made to verify that the uniqueID of the decrypted data matches the one included in the ciphertext. If the ciphertext is modified by an attacker, this check will fail. If the uniqueID comes from "/dev/urandom" then this check is skipped (...only in this version...it could be made by calculating MD5(MD5(plaintext)+key) on input stream EOF and by appending it at the end of the output stream...but I'm lazy! :-). To be more precise, here is the detailed pseudo code of the encryption process.
I decided to make the number of rounds configurable so that
if you have to encrypt a small file (say 5MB or less -- should cover 90%
of uses) and you accept to wait a few tenth of second more, you can use
8 rounds with rapid key regeneration ("e8+" mode) to reach a high level
of security. As a general rule, watch your PC's hd activity led during
the "Encrypting..." phase. Try incrementing the number of rounds (or add
the "+" option) until the led starts to blink. By doing this, you won't
waste time waiting for your HD to do it's job. However, people needing
speed (say for streaming encrypted content) achieve speeds faster than
AES with default 1-round mode (unoptimized asm version runs 2x faster
than many AES implementations).
A word on self-decrypting files: by using this mode, you enable your friends to receive files encrypted with XSE and decrypt them without having anything installed on their machine. They just double-click on the self-decrypting executable and, after introducing the key, the original file appears next to it. It couldn't be easier! Keep in mind that the original filename is stored inside the executable in plain text (at least in this version). Two friends of mine ("Roccio" and "Mandingo"), made a nice little GUI for windows that uses the drag&drop method to automatically encrypt/decrypt files by calling the dos executable. It doesn't mess your registry file up, and it's extremely easy to use...try it!
|
||||||||||||||||||||
Final considerations |
||||||||||||||||||||
I really hope to get some feedback from all this
(flames excluded). I've done my best to make it secure, fast and scalable.
Every pass of this scheme has a reason behind and aims at making an attacker's
task more difficult. But while its security is kind of speculative, perhaps
its most important quality is simplicity. It should be very easy to cryptanalize
it and to find weaknesses/strong points against known attacks (which I
know very little, I admit...but that's why I'm posting it in a sci.crypt
sandbox!). I've even included a command line option ("-") that prevents
the periodic state reset, so that you can study the cipher more "confortably".
PLEASE, if you spend some time on this cipher, share your thoughts (positive
or negative) with me. Maybe it's strong, maybe I can improve it, maybe
it's dead in the water, but I'd really like to know your opinion - and
learn something more. One final word: if someone among you is an assemply code master and knows how to optimize my little and completely unoptimized asm loop in xse.c, you're welcome! :-) |