ARCFOUR-Extended

The utility encrypts or decrypts standard input to standard output, using the path name of a user-provided key file as its only non-option argument.

Either option -e (for encryption) or -d (for decryption) is mandatory in order to specify the operation to be performed.

The utility combines the standard ARCFOUR stream cipher algorithm with modified key setup and a customized mode of operation in order to make it more secure.

All encryptions will be salted, allowing safe re-use of the same encryption key for different messages, even if the messages happen to be identical.

Also, an ARCFOUR-based message authentication code will be added to every encrypted message ("encrypt-then-MAC"), detecting any manipulation or corruption of the encrypted message.

Usage

$ a4x -e KEY_FILE < PLAINTEXT_FILE > CIPHERTEXT_FILE
$ a4x -d KEY_FILE < CIPHERTEXT_FILE > PLAINTEXT_FILE
$ a4x -h
$ a4x -H [ HASH_BIT_SIZE ] < DATA_FILE > HASH
$ a4x -m KEY_FILE [ MAC_BIT_SIZE ] < DATA_FILE > MAC
$ a4x -r KEY_FILE [ PERSONALIZER ] > PSEUDORANDOM_DATA
$ a4x -r -d KEY_FILE [ PERSONALIZER ] < PSEUDORANDOM_DATA
$ a4x -p SALT_FILE ITERATIONS [ PERSONALIZER ] < PASS_PHRASE > KEY_MATERIAL
$ a4x -a < BINARY_DATA > ASCII_ARMORED_DATA
$ a4x -a -w WRAP_COLUMNS < BINARY_DATA > ASCII_ARMORED_DATA
$ a4x -a -d < ASCII_ARMORED_DATA > BINARY_DATA
$ a4x -V

HASH_BIT_SIZE and MAC_BIT_SIZE must be a positive multiple of 8 and default to 256. Other popular choices for the hash size are 160, 192, 224, 384 and 512 bit.

-e and -d encrypt/decrypt the input file. Encrypting also prepends a 256-bit salt and appends a 256-bit MAC to the output stream, and decrypting verifies that MAC. Because of the salt and the MAC, the ciphertext will be 64 bytes larger than the plaintext.

-h shows usage help.

-H calculates a cryptographic hash over the input file

-m calculates a message authentication code (MAC) over the input file. The MAC is based on the provided KEY_FILE. The MAC ensures the message cannot be tampered with by an attacker, because then the MAC would no longer match.

-r creates a pseudo-random sequence based on both the KEY_FILE and the optional PERSONALIZER string argument. It will only stop once the output device becomes full or the output is a pipe and the receiver (such as "dd") stops reading. This can be used to overwrite storage volumes with unpredictable data.

-r -d checks that a pseudo-random sequence like the one created by -r is identical to the data read from standard input. This can be used to verify that a storage medium correctly stored all the data previously written to it using option -r.

-p derives a key from a pass phrase read from standard input, a binary salt, and an optional personalization string. This can be used as a password-based key derivation function, such as a replacement for PBKDF2. It can also be used for key stretching. This is very similar to -r except that it reads from standard input. ITERATIONS is the amount of additional work being done for deriving the key, use 0 for the default amount. It is recommended to select a value for ITERATIONS by timing different choicess and selecting a value that takes between 0.25 and .5 seconds for completion (start outputting key material).

-a performs RFC-3548 "Base64"-enoding withouz use od padding characters. It uses the following encoding alphabet: ASCII characters "A" through "Z", "a" through "z", "2" through "7", "+" and "/". -a can be used alone or as the -a modifier with most other commands. When used alone, "ASCII-armors" binary input and writes the human-readable ASCII encoding to standard output. -ad reverts the transformation. -a can be used for generation of high-quality ASCII passwords when ascii-armoring data from /dev/random. By adding -a as a modifier to other commands, they no longer output or expect binary data but rather expect or generate ascii-armored data. ASCII-armoring will also insert a newline after every 70 bytes of output, except for -p. When decoding, -a will ignore all newlines. Note that the order of options is significant in cases where there is ambiguitiy: -ad means ascii-dearmoring, while -da means decryption of ASCII-armored ciphertext. But -ea and -ae mean the same because there is no ambiguity.

-w $WIDTH can override the default line splitting width used by -a. This means a newline will be inserted after every $WIDTH characters written. By default, $WIDTH is 70 for all modes except for -p where $WIDTH defaults to 0. 0 means that no newlines should ever be inserted. The default has been chosen so that ascii-armored output when being quoted with "> " in an e-mail reply will never exceed 72 columns, which is the maximum recommended internal line width for RFC-822 e-mails. Note that -s does not imply -a. When used in a context that does not involve Base64-encoding, the option has no effect.

-V shows the program’s version number.

-b $BUFFER_SIZE is an additional option which does not refer to a particular command. It can be specified together with any command. It allows to override the default I/O buffer size. The value is specified in bytes and will be rounded up to the next multiple of the system’s MMU page size. Depending on the command, up to two buffers of this size will be allocated. The default is 16 MiB, but smaller default values will be attempted(by repeated halving of the buffer size, down to a minimum of 8 KiB) if not enough memory is available.

Basic ARCFOUR Algorithm

This as a generalized description of the standard ARCFOUR algorithm, which is used for both key setup and cryptographically-secure pseudo-random generation:

1. i= j= 0; s[all indices mod 256]
2. Preset s[i]= 0 .. 255
3. Move i one position to the right
4. Move j by (s[i] + optional_next_key_octet()) positions to the right
5. Swap s[] values at indices i and j.
6. Optionally output s[index equal to sum of values just swapped]
7. Go back to step 3 unless finished

Details:

• This basic algorithm is the same for standard ARCFOUR implementations as well as for the extended ARCFOUR-XA algorithm.

• As hinted by step 1, all indexes to array s[] have to be reduced modulo the array’s size, which is 256 elements. This is not explicitly mentioned in the remaining steps, but has to be applied there too.

• optional_next_key_octet() is a function which provides the next input key material octet. It is only used in the key setup phase and always yields 0 during normal operation.

• In the standard ARCFOUR algorithm’s key setup phase, optional_next_key_octet() always returns key[i modulo keysize] and the key setup phase ends at step 7 after 256 octets have been produced by optional_next_key_octet().

• Step 2 is only used during key setup. It is skipped during normal operation.

• Step 6 is only used during normal operation. It is skipped during key setup.

• The output value optionally produced by step 6 represents a cryptographically-secure pseudo random number sequence which is completely pre-determined by the key used in the key setup phase.

• In the standard ARCFOUR algorithm, the CPRNG-sequence produced by step 6 is directly XORed with the input stream in order to encrypt or decrypt it.

Modified key setup

As mentioned before, ARCFOUR-XA does not use the standard ARCFOUR key setup, but rather an modified version of it.

• All bytes of the key are fed into step 4 of the basic algorithm. Feeding does not stop after the first 256 octets of the key nor will the key be recycled and fed multiple times into step 4 if it is shorter than 256 octets.

• After the all key bytes have been fed into step 4, an octet with value 0x80 is fed in order to separate the key stream from its suffix.

• The key stream suffix is fed last into step 4. It starts with an octet containing the count of the remaining octets in the suffix. Those remaining octets represent the octet count of the key and are fed as a base-256 big-endian integer with as few octets as possible (but at least one octet).

• After processing all octets of the (suffixed) key as explained above, step 1 of the generalized description is executed again. Then the normal standard ARCFOUR algorithm is run 3328 (= 256 + 4 * 768) times in order to "warm up" the CPRNG and protect against several known attacks on standard ARCFOUR (which does not do such warm-up). The output octets generated during this warm-up phase are not used and just thrown away.

Key setup Q & A

Question: Why not recycle the key?

The original algorithm recylces the key until 256 bytes of key material have been fed into step 4. Why don’t you do this? Isn’t the modified key setup less secure?

Answer: We don’t need to recycle the key because we have added the "warm-up phase" as a replacement. Also, adding the same key multiple times does not increase the entropy of the internal state. See the next answer for details.

In addition, the primitive cyclic repetition of the key in the original algorithm led to the fact that keys "HA", "HAHA" and "HAHAHA" are all the same. This has all been fixed in the new key setup.

Question: What is entropy?

Answer: In the context of cryptography, entropy means true randomness.

Or maybe unpredictability would describe it better.

It describes the information that an attacker does not possess, cannot predict and cannot derive from other data at the attacker’s disposal.

Most prominently, entropy is present in the form of a key or pass phrase not known to the attacker.

But entropy is also required for generating safe random salts, IVs and nonces. (Counter-based salts and nonces do not need entropy, but then of course a counter needs to be stored and updated somewhere.)

Entropy cannot be "generated" by any algorithm, it can only be harvested from true-random sources.

Generally, only few entropy sources are available to a program. "/dev/random" is the most prominent one.

"/dev/urandom" on the other hand is not a suitable source for entropy. It might include entropy, but there is no guarantee. Therefore, if the security of keys is paramount, cryptographic random keys must never be drawn from "/dev/urandom".

Unfortunately, many programs still do this. Prominent examples include openssl and openssh. Nevertheless, this is a grave mistake.

If you are unlucky, depending on the exact configuration, an attacker might not just be able to decrypt the encrypted SSH-connection, but even be able to reconstruct your private SSH key!

So don’t underestimate the importance of entropy. It’s the thing that "fuels" your cryptographic keys and pass phrases and makes them secure. But it is also required for creating ephemeral random keys used internally by many cryptographic algorithms.

Question: Why 3328 rounds?!?

Answer: The warm-up-count of 256 + 4 * 768 dropped (thrown-away) output octets has been chosen as follows: The normal SCAN default is to throw away 768 bytes ("ARCFOUR-DROP768"). It has however been mentioned that 3072 bytes (= 4 * 768) would be "more conservative". So we use that, because we definitely want to be conservative about security! The 256 additional drops have been added due to the fact that the modified key setup is actually shortened compared to the original one: The original key setup will always process 256 octets, even if the key is shorter. As we allow key lengths down to a size of 0 bytes, we added 256 to the warm-up count in order to process at least as many octets as the original algorithm even in that case.

Question: Why shorten the key setup?

Why not feed the key into step 4 multiple times until 256 octets have been processed like the original algorithm does?

Answer: The original algorithm did not throw away any bytes at the end of the key setup phase. It still had to initialize all 256 sbox-entries, though. So it recycled the key as a simple way to achieve that without extra code. But there is no real advantage by feeding the same key multiple times. This cannot increase the entropy of the sbox. Adding any octets has the same effect (stirring the sbox) as recycling the key. So we add a large number of binary zero bytes instead of recycled key bytes, which also stirs the sbox.

Adding binary zero key bytes is the same as just running the basic core algorithm, because optional_next_key_octet() returns 0 outside of the key setup which is exactly the same as providing a key byte of binary zero within the key setup.

Why not stop after 256 key octets like the original algorithm?

The key setup only needs to stir around 256 octets of the sbox. After 256 steps, all original octets have been moved, so why not stop there but stir even more?

Answer: First of all, it is never a good idea to throw away available key material. The more key bytes are used to stir the sbox, the greater its entropy will become up the the maximum defined by the structure of the sbox (around 1684 bit).

Aren’t keys longer than 256 octets useless?

Theoretically yes, because the sbox cannot store more than about 1684 bits of entropy, which is 211 octets (rounded up).

But that only refers to completely random binary key bytes.

If keys are not as random, either because the random number generator has biases, or because the key is human-chosen text or consists of a human-readable encoding (such as base-64 or hexadecimal digits) rather than binary bytes, then a longer key size can compensate for the reduced entropy per key byte.

For instance, the pass phrase "ABC" and "414243" have the same basic amount of entropy, because the second phrase is just a hex dump of the first one. A hex dump will be longer than the text it encodes, but the entropy of any encoding is the same as that of the decoded data.

Think of entropy as if it were energy. One can transform one form of energy into other forms, or convert between matter and energy. But none of this changes the amount of energy present.

What exactly is the "key"? Is it a pass-phrase or something binary?

The key is binary. But as any text can also be interpreted as binary data, a text file is equally fine as a key file.

There is also no inherent advantage of a binary key file over a human-readable pass phrase stored in a text file except that a binary random key will provide more entropy per byte and can thus be shorter than a pass phrase for the same level of security.

But as this implementation allows key files of arbitrary size, it is always possible to make a text pass phrase as long as necessary in order to match the security of even the highest-quality binary random key.

Another different thing to consider, however, is portability.

As long as you just copy an existing key file to a different platform after creating it for the first time on some platform, portability is not an issue: The binary contents of the file will always be the same.

However, if you choose to input the pass phrase via the keyboard locally and then write it into a key file for use, more things need to be considered.

Those are: The text-to-binary-encoding and the line-ending representation used by the local system.

This is because text files, when interpreted binary like as encryption keys, always need to be encoded in some way in order to be stored as binary bytes. And all lines in a text file, normally end with a newline sequence, which is also different among operating systems. This applies even if the file contains just a single line of text, such as a pass phrase.

In order to maximize portability, I advise using the following approach for creating binary key files out of user-provided pass phrases:

• Remove the newline from the end of the input. I. e. do not include the terminating newline sequence at the end of the input line into the key file. This eliminates those differences between operating systems. In addition, the newline sequence is always the same for a particular system and would therefore add little to none entropy to the resulting key.

• Encode the pass phrase as UTF-8 NFKC ("normalization form compatibility composition"), without any BOM ("byte-order mark"). Compared to UTF-16 and UTF-32 this has the advantage that byte order is not an issue, so the encoding is unique and no BOM is needed.

Note that plain old ASCII is a subset of UTF-8 NFKC, so you can use your pass phrase directly if it only contains ASCII characters.

The following command will ensure that some file "password.txt" contains only ASCII-characters:

$ iconv -t US-ASCII password.txt | tr -d '\n' > binary_secret.key

LATIN-1 is also a subset of UTF-8 NFKC, so no special considerations about the NFKC-stuff are necessary for such pass phrases either. Do this:

$ iconv -t LATIN1 password.txt | iconv -f LATIN1 -t UTF-8 \
  | tr -d '\n' > binary_secret.key

If you need the Euro sign, use WINDOWS-1252 instead of LATIN1 in the iconv command above. Even though this is not a subset of LATIN1, is is nevertheless a single-byte character set which is also a subset of UNICODE. This means the temporary conversion into a single-byte character set will already perform the required normalization, and the back-conversion into UNICODE will not change the normalization form.

In other words, the above approach will actually work for any single-byte code page into which the passphrase file will be converted as an intermediate step before converting further into UTF-8.

Only if you have really special UNICODE-characters in your pass phrase or use non-western languages, you need to ensure than the UTF-8 text is normalized properly. I know of two utilities which can be used for NFKC normalization:

$ idn -n password.txt | tr -d '\n' > binary_secret.key

(part of package "idn" on my system) and

$ uconv -x '::nfkc;' password.txt | tr -d '\n' > binary_secret.key

(part of package "icu-devtools" on my system).

But most of the time the ASCII, LATIN1 or WINDOWS-1252 character sets should be sufficient, and then the iconv-utility is enough and the idn or uconv utilities will never be required.

The most important thing to remember that pass phrase or key security is all about entropy and never about a particular encoding.

Security-wise it is no difference whether you use 16 bytes from /dev/random as a binary key file, or a textual hex-dump of the same bytes, or a base-62 or base-64 encoding of it: The resulting pass phrases will have different sizes, but always the same entropy and thus security.

So use the encoding which you feel most comfortable with.

Binary key files use less space on disk, but a base-62 (i. e. ASCII alphanumeric) password can easier be pasted in e-Mails or chats.

base-64 encoding is also very handy, although any "=" characters should be stripped because they are only used for padding and not part of the encoded data themselves. (It does not hurt keeping them, however - it will just make the pass phrase longer without changing its entropy, wasting a few bytes of disk space for storing the pad characters.)

Question: What is the keystream terminator 0x80 good for?

Answer: Because the core key setup step 4 cannot determine between trailing binary zeros of the key and the zero bytes added by the key warm-up. So the key 00 00 would be the same as 00 00 00. By adding the terminator we change the effective key to 00 00 80 as compared to 00 00 00 80 which can now be distinguished.

Question: Why has the size of the key been included in the keystream suffix?

Answer: Because it does not hurt and we want to use the key setup algorithm unchanged also as the basis for a cryptographic hash algorithm. Such algorithms are always threatened by prefix/suffix attacks where the attacker tries to exploit the fact that an older message with known hash value is a suffix of the new message or vice versa. Including the message size as a counter thwarts such attacks, because then messages of different sizes can never be prefixes or suffixes of one another.

Question: Why using big endian for the keystream octet count?

Answer: While it is true that little endian output would be easier if the whole count was to be stored within a single variable, we want to use at least a 128 bit counter in order to ensure it will never wrap around. Not all programming languages provide 128 bit integers, so the counter will be implemented as an array of shorter integers instead. But this means that the array has to be scanned starting at the "most significant" side in order to find out how many significant octets there are, and this effort will be the same for both little- and big-endian output. The only difference is the direction in which the index runs, so there is virtually no advantage of choosing either endianness over the other. And when in doubt, I always choose big endian, because it seems more natural to me that important things come first and smaller details later. It is also the way we humans write numbers on paper, and therefore easier to decipher when reading a hex dump.

Question: Why not using base-128 for the octet count?

It is much easier to encode any unsigned integer by just outputting it in little-endian order, writing out the least significant 7 bits plus a "continuation" bit that tells whether this has been the last octet of the encoding.

Answer: This is true if the whole counter fits into a single variable. But this will most likely not be the case here because the counter is too wide. Implementing the same algorithm for multi-precision integer is not as much fun or as efficient as for the single-variable case. Also, not all CPUs like shifting by 7 bit. While it is true that the ALUs of all performance-oriented CPUs have a barrel-shifter which can do this efficiently, many tiny CPUs do not have one and shifting by any amount of bits other than 1 bit will slow things down there. So it is best to avoid shifting by more than 1 bit, or at all, if this can easily be managed. Which it can in this case.

XA Mode of Operation

ARCFOUR-XA uses the XA mode of operation rather than the standard ARCFOUR method which simply XORs CPRNG octets into the input stream in order to create the output stream.

ARCFOUR-XA consumes 2 CPRNG octets for every encryption instead, and works as follows:

C[i] = (P[i] XOR CPRNG[2 * i]) + CPRNG[2 * i + 1]
P[i] = (C[i] - CPRNG[2 * i + 1]) XOR CPRNG[2 * i]

where "+" and "-" are addition/subtraction modulo 256 and CPRNG[j] is the jth output (assuming the first j is 0) returned by the ARCFOUR algorithm after key setup.

As one might have already guessed, XA stands for "XOR-Add".

ARCFOUR-XA-HASH

The following cryptographically secure hash function is used as part of the message authentication process:

• The ARCFOUR-XA algorithm is used to encrypt an initial vector, using all octets of the message to be hashed as the key. The output of that encryption is the hash.

• The updating of the hash is merged with the key setup and warm-up phases. That is, instead of throwing away the octets that could be generated during key setup and the warm-up phases, all those bytes are actually used with the XA-mode to repeatedly encrypting the IV in a cyclic fashion.

• The IV must have the same size as the intended output hash, and consists of all binary zeros by default. Customized versions of the hash may use other IVs, though.

• Because the size of the IV can be chosen freely, ARCFOUR-XA-HASH can create hashes of any desired bit sizes. An instance of the algorithm generating hashes of $N bits shall be referred to as ARCFOUR-XA-HASH-$N.

ARCFOUR-XA MAC

The ARCFOUR-XA-HASH-256 algorithm is customized with a secret 256-bit IV instead of the all-zero default IV.

By doing so, the ARCFOUR-XA-HASH-256 becomes the ARCFOUR-XA-MAC-256, and the secret IV becomes the 256-bit MAC key.

Key derivation phase

The utility used for encryption will not use ARCFOUR-XA directly for encryption or decryption with the user-provided key file.

Instead, the user-provided key file will be used to set up an ARCFOUR-XA CPRNG (but skipping the XOR-ADD part because we do not need to encrypt anything here) which shall generate multiple binary octet strings for different purposes in the following order:

• 32 octets <salt_encryption>

• 32 octets <mac_key>

• 211 octets <payload_encryption>

• optionally (only for encryption operation) 32 octets <salt_creation>

The CPRNG is derived from the encryption algorithm by encrypting an infinite stream of octets containing the value zero.

Encrypted message layout

The encrypted output generated by this utility will have the following structure:

• 32 octets salt encrypted by ARCFOUR-XA with <salt_encryption> as encryption key

• All octets of the plaintext input message as payload encrypted with the ARCFOUR-XA algorithm and using <payload_encryption> as the encryption key

• 32 octets MAC calculated over all the output octets so far (i. e. over the encrypted salt and payload), using <mac_key> as the key for the ARCFOUR-XA-MAC-256.

The encrypted output stream will therefore always be 64 octets larger than the original plaintext input stream.

The length of the input message need not be known in advance for encryption/decryption.

The position of the MAC within an encrypted input stream is detected by encountering EOF, which is known to be 32 octets after the first octet of the MAC.

Salt generation

A salt only need needs to be generated for encryption.

Decryption just reads the encrypted salt from the first 32 octets of the message and uses <salt_encryption> as the key for decrypting the salt.

A new salt is generated by calculating the ARCFOUR-XA-MAC-256 for some input with <salt_creation> as the MAC key.

The input used for salt creation is composed of the following components, fed onto the MAC calculation in arbitrary order:

• 32 octets from /dev/random, or some other OS-specific "true randomness" source. This is optional if a counter-file (see below) is available.

• The binary output of localtime()

• The binary output of clock()

If possible, the utility should also keep a binary 512-bit per-user counter within some state file and increment this counter (ignoring overflow) for every encryption, then including its new value into the MAC also.

The counter file shall be protected by a file lock in order to assure access to it will be serialized and updates will be atomic.

The counter value may (if not existing yet) be initialized using the ARCFOUR-XA-HASH-512 over all of some of the following data items:

• 32 bytes from /dev/random. Avoid using /dev/urandom if possible. This needs only be done once, so it is OK to wait a little if /dev/random should block.

• The hostname as returned by hostname -f on Linux

• The host’s IP addresses as returned by hostname -I on Linux

• The user/group memberships as returned by id on POSIX systems

• The current value of /proc/sys/kernel/random/boot_id on Linux

• The contents of file /etc/machine-id on Linux

• The contents of file /proc/cpuid on Linux

• The current result of ps -AHlf on Linux

• And anything else one might think of that can deliver entropy, such as the current value of performance counters provided by some CPUs.

Optionally, the above entropy sources (except for /dev/random) may also be sampled regularly based on the current counter value, combining them with the old counter value into a new hash to act as the new counter value.

However, this should only be done occasionally, in order to not put too much stress on the system. For instance, once a week, by estimating the number of encryption invocations typically happening during a week. The sampling will then be triggered the next time the counter value equals a multiple of the estimated interval value.

License

The application itself is licenced under the GPLv3.

Several re-usable source files which are not application-specific and may be useful as parts of a generic utility library are licenced under the less restrictive LGPLv3.

The files COPYING.GPLv3 and COPYING.LGPLv3 contain copies of the original GNU license texts.