version 3

December 28, 1998

Author: Dianelos Georgoudis, TecApro International

GodSave is a new data encryption algorithm, designed by Dianelos Georgoudis of TecApro International Corp., and placed in the public domain.

PART 1: THE ALGORITHM AND THE SOURCE CODE

Normal encryption algorithms, such as the IDEA encryption algorithm that is used by PGP, apply a single complex function to the plaintext and the key in order to produce the ciphertext. Since the algorithm is public this means that even though the data flow in the algorithm is unknown, the operations applied to this data flow are known. Any such encryption algorithm can by cryptanalysed and maybe broken. For example, we can be sure that there are a lot of smart people with a lot of expensive equipment trying to break IDEA right now, in fact it may have been broken already. If a commonly used encryption algorithm has already been broken by some agency we can be sure that the same agency will do all that they can in order to get it trusted and used by many organizations.

The GodSave encryption algorithm which is described in this paper represents a departure from the normal approach. It does not employ a single encryption function, but rather it employs a very large family of different encryption functions and it chooses one of them every time it encrypts a new block of plaintext. The choice of which encryption function is applied depends both on the key and on the plaintext. With traditional encryption algorithms an attacker knows exactly what operations are applied to the plaintext and key. With GodSave what the algorithm does is variable so the attacker does not know what operations are applied to the plaintext and the key, even though the algorithm itself is public. By keeping secret not only the key but also what is done to the key and the plaintext the GodSave approach tries to maximize the security of the encryption algorithm, regardless of the current or future state of the art of cryptanalysis. Even more important, the GodSave algorithm can very easily be modified to produce non standard versions.

The principal design criteria of GodSave encryption algorithm are:

The GodSave algorithm is implemented in Pascal and should be available in C by the time you read this. The source code contains some 8086 assembly language routines for the definition of the 32 hash functions. These routines can easily be translated into other assembly languages. The GodSave interface is simple and flexible allowing the encryption of blocks of size between 16 bytes and 1024 bytes.

The remainder of this document is in two parts. The first part provides a complete description of the GodSave algorithm. The second part contains some general ideas about security.

The GodSave algorithm is based on a very elegant idea of Phil Karn. Take a plaintext of 2N bytes and split it into two halves T1 and T2, each of N bytes. Also split the encryption key into two halves K1 and K2. Now find a very good one way hash function S and use it to scramble the "concatenation" of K1 and T1 in order to produce a block of N bytes which you then XOR (exclusive OR) with T2 to produce C2 a block of N bytes which is the second half of the ciphertext:

In a similar manner, scramble the other half of the key K2 with C2 (the ciphertext already computed) and XOR it with the first half of the plaintext T1 to produce C1 the first half of the ciphertext:

The complete ciphertext is the concatenation of blocks C1 and C2.

In order to decrypt the ciphertext, repeat the operation in reverse order. Split the ciphertext (C1,C2) in two halves C1 and C2. Now scramble C2 with K2 and XOR the result with C1 in order to produce the first half of the plaintext T1, a block of N bytes:

Now that you know T1 you can compute T2 as follows:

The beauty of Karn's idea is that its security is based on the quality of the scrambler S. If you can create a good scrambler then you can create a good encryption algorithm. By the way, Karn put his idea in the public domain, which is the main reason I did the same with GodSave.

Before I describe the GodSave algorithm I want to introduce my terminology. I use the term "scrambler" for a one-way hash function that produces a block of data of the same size as the original block, and "hash function" for a one-way hash function that reduces the size of the block that it processes. A byte is a 8 bit value.

The GodSave algorithm is based upon Karn's method but it differs from it in three ways. The first change I made was to introduce a parametric scrambler. I start by dividing the key in four equal parts: K1s, K1t, K2s, K2t. The component K1t is used as the first half of the encryption key and the component K1s is used to select from the very large number of scramblers available the one to be used to encrypt the first half of the plaintext T1:

In a similar manner K2t and K2s are used to encrypt the second part of the ciphertext to produce the first half of the ciphertext:

To decrypt the ciphertext (C1,C2) the operations are applied in reverse order:

As you can see, the sub-keys K1t and K2t are used to modify the data to be scrambled, and the subkeys K1s and K2s are used to select a scrambler, that is they define how the data will be scrambled. Since GodSave uses a key of 256 bytes each sub-key is still a very large 64 bytes (512 bits) long.

The second change I made was designed to remove a weakness in Karn's algorithm which was detected by Luby-Rackoff. This can be illustrated as follows: suppose that we know the plaintext (A,B) and we know that it produces a ciphertext (X,Y), and that we also know that the plaintext (A,C) - in which we know that the first half of the message but we do not know the second half - produces a ciphertext (W,Z). Then we can compute the unknown plaintext C as follows:

The first stage in the encryption of first message gives us:

The first stage in the encryption of second message gives us:

Combining these two results gives us the value of C in the form:

GodSave avoids the weakness in Karn's algorithm by always modifying the first half of the plaintext before encrypting it. This can be achieved by replacing the first half of the plaintext T1 by the (T1 xor T2) before applying the original algorithm. Thus GodSave's version of the Karn algorithm (without parametrization) is :

To encrypt

To decrypt:

The third change I made is designed to defend against dictionary attacks, that is against the situation in which the attacker tries to determine the encryption key by testing in turn the values in a dictionary of potential keys. Dictionary attacks are based on the fact that people do not like to have to remember long or complicated keys or passwords and so very often use quite simple ones. No matter how good the encryption algorithm, if an attacker tries a few million possibilities and in this way is able to discover the encryption key of just a few users then the security of the entire organization could be compromised. In the GodSave algorithm I defend against this kind of attack by introducing the concept of a secure "master key".

A final note: For operational reasons GodSave does not concatenate the key and plaintext before applying the scrambler, but rather combines them in a different manner (through operations XOR).

Here is the detailed description of two rounds GodSave:

To encrypt:

To dencrypt:

GodSave includes several optional features designed to strengthen its security. All of these optional features can be used individually on in a combined manner.

Luby-Rackoff, who detected the weakness in Karn's algorithm, proposed another way to avoid it. His idea was to use Karn's algorithm twice, i.e. Karn( Karn( T ) ) -> C, that is to say the plaintext (T1-T2) is first encrypted into (X1,X2) which is then encrypted again to produce the ciphertext (C1,C2). To further increase security a different set of keys is used for the third and fourth round. Thus the double Karn algorithm (or four-round Luby-Rackoff) is:

to encrypt:

to decrypt:

The GodSave algorithm allows four, six and eight rounds of Luby-Rackoff encryption as an option. For example, the GodSave version of six rounds Luby-Rackoff encryption is as follows (observe that different keys are used in each round):

To encrypt:

To decrypt:

Apart from dictionary attacks which were treated in the previous section, most cryptanalytic attacks belong to one of two types: known plaintext attack or chosen plaintext attacks. Here the attacker studies a large number of plaintext-ciphertext pairs, and tries to deduce the key used to perform the encryption.

GodSave includes two optional features to defend against these types of attack:

I have provided one other option in GodSave for those who need maximum security. This GodSave optional feature offers what I call "lazy" encryption. The procedure applied is as follows: first a pseudo random sequence is generated of the same size as the plaintext. This sequence is then appended to the plaintext and the "extended" plaintext is then encrypted. Lazy encryption avoids the need to divide the plaintext in two, but produces a ciphertext that is twice as large. The algorithm is as follows:

To encrypt a plaintext T:

To decrypt:

This variant of the GodSave algorithm has the interesting property that both C2 and C1 will be at least as good a random sequence as the original random sequence R, even if you use a mediocre scrambler S. I suspect that if you use a true random generator to produce R, then this cipher is absolutely unbreakable.

All GodSave's options are independent and can be combined one with another. For example, the user can ask for a four rounds and lazy encryption if he wishes. The resulting algorithm is quite complex:

To encrypt plaintext T:

To decrypt:

GodSave normally allows the encryption of blocks up to 1024 bytes. When using lazy encryption only blocks up to 512 bytes can be used.

1. Extract the next 5 bits of the key K to obtain an index "i" (value between 0 and 31) that indexes one of the 32 hash functions. On every other iteration, the five bits of the key are combined with the value of H computed in the previous iteration:

2. Use index i to select a hash function and apply it to the current value of text T to produce a 32 bit value H:

3. Combine H with the key K to produce an index "j" (value between 0 and 6) that indexes one of the 7 primitive scrambler functions.

4. Use the index j to select a primitive scrambler function and apply it to the current value of text T to produce an incrementally scrambled text to be used as input to the next iteration.

In short, in each iteration bits of the key are used to select a hash function which is then applied to the current state of the text to generate a value which is used to select a primitive scrambler function which in turn is then used to modify the text. Notice that both the key and the text are used to define the sequence in which the hash functions and primitive scramblers are applied.

All 32 hash functions are implemented in 8086 assembler and all have a similar structure, but not an identical size. Each function, first traverses the complete text processing 8 bytes at a time, then it processes either the first or the last 32 bytes of the text again. (It follows that the permitted sizes of input text are multiples of 8 bytes and that the minimum size of the input text is 32 bytes.) All hash functions are built up from a variety of machine instructions including XORs, additions and subtractions (with or without carry), circular and linear shifts, and, less frequently, ANDs and ORs.

These hash functions were derived by a process of brute force searching. A generator was created which randomly produced over 100 million potential hash functions, respecting a few basic design criteria (such as that all available registers should be used) and a test procedure then ran these hash functions on random data blocks with sizes between 32 y 256 bytes, changing 1, 2, 3 or 4 bits and testing how often the resulting hash value was identical to the original, or differed only in 1 bit, 2 bits, etc. In this way the best 32 hash functions were chosen.

All primitive scramblers are relatively simple functions and each one is implemented both in high level language and in 8086 assembler. Here follows a brief description of each of the primitive scramblers.

It is not easy to justify this choice of primitive scramble functions. However the following arguments provide the rational for the functions which I chose.

There are a few other details of the scrambler that should be mentioned, namely:

After completing these iterations, a check is made to verify that each primitive scrambler function has been executed at least once, twice or three times (depending on the value of the level parameter). If not, the unused primitive scramblers are applied to the text up to the minimum number of times.

The scrambler uses a key of 64 bytes. The first 254 bits (almost exactly 32 bytes) are used as parameters for the primitive scrambler functions, while the last 32 bytes are used (5 bits at a time) to select the next hash function. With a level value of 10, which generates between 15 and 30 iterations, 75 to 150 bits of the key are used for this purpose. This means that with a level value of 10 a total of 329 to 404 bits of the key affect the processing performed by the scrambler.

Note that even at the minimum value of level (0), which generates between 5 and 10 iterations, at least 279 bits of the key are used by the scrambler. Thus the performance of the scrambler is highly dependent on its key.

Finally some comments on the quality of the scrambler. I believe the GodSave scrambler to be of very good quality. At the minimum value of level (0) and with several of the primitive scramblers disabled the scrambler produces an excellent "avalanche" effect, that is to say that a 1 bit change in the original text thoroughly scrambles the end-result.

The style parameter has a five bit value which is interpreted as follows:

All values of the style parameter, from 0 to 31, are legal, but the processing necessary for implementing each one varies a lot. The following table describes each encryption style and gives you an idea about the workload for each one, assuming encryption of blocks of 256 bytes and level parameter set to 10.

I recommend the use of the following style values:

- The primary encryption key (256 bytes) used for rounds one and two.

- The secondary encryption key (256 bytes) used for rounds tree and four.

- The tertiary encryption key (256 bytes) used for rounds five and six.

- The quaternary encryption key (256 bytes) used for rounds seven and eight.

- The scrambler key (64 bytes) used with key randomization

- The scrambler key (64 bytes) used with text randomization

- 32 bytes needed to initialize the index for the 32 primitive hash functions.

- 192 bytes needed to initialize the 32 primitive hash functions.

- 128 bytes that specify how each block of text will be distributed in two halves.

- 128 bytes that specify how the two halves are united again in one block

In all, the user key and master key (up to 512 bytes) are used to produce a total of 1632 bytes for the internal keys. Not all keys are necessarily used. For example, when GodSave is called with four rounds, then the tertiary and quaternary encryption keys are not used. When the master key and user key are sufficiently long (more then 10 characters) then one fourth of them is reserved for the computation of the secondary encryption key. In this case the primary and secondary keys are functionally independent.

The GodSave algorithm itself includes two base keys initialized with true random sequences. One is a base scrambler key of 64 bytes (BSK) and the other is the base key of 448 bytes (BK). Half of the declared master key (MK1) is combined with the declared user key UK and XORed with the base key to obtain a new value for the base key:

The other half of the declared master key (MK2) is combined with the base scrambler key (BSK) to produce a new value for the base scrambler key:

Using this base scrambler key, the entire 448 bytes of the new base key (BK) are scrambled to produce the definitive value of the base key:

The base scramble key is modified and the base key is scrambled again in three successive cycles. The resulting base keys are used to initialize the rest of the internal keys:

It is difficult to estimate the security of GodSave because the state of the art in cryptology is unknown. Nevertheless, the variable nature of the algorithm allows for some projections. Let us suppose that level 10, style 3 encryption is used.

Comparing a large number of known plaintext ciphertext pairs is not useful because each uses a different key. Choosing a plaintext is not useful, because it gets randomized before encryption. So an attacker is stuck with unknown keys and plaintexts.

Up to this point in the description of the GodSave algorithm I have focused attention on the structure of the algorithm and the level of security which it can provide. In this final section I want to comment on the performance of the algorithm.

The speed of GodSave (as implemented in the original Pascal source code made available in http://196.40.15.121/Encryption/index.html) is described in the following table where the number of bytes encrypted per second is given per 1 MHz of Pentium. This means that if you use a 166 MHz Pentium processor you should multiply these numbers by 166 to find the approximate speed for your computer.

Number of bytes encrypted per second per MHz on a Pentium

An encryption/decryption speed of 50 Kbytes per second on a mid-range PC is adequate for many popular applications, such as communications (including phone conversations) and the storage of sensitive documents. However this level of performance may be a limiting factor in the implementation of other applications such as secure data bases.

When used at level 0, then 1000 bytes per second per 1 MHz of Pentium processor will be generated. At level 10, 650 bytes will be generated per second.

GodSave technology and the source code included here are copyrighted by TecApro International but they are placed in the public domain so that they can be used freely. TecApro makes no claims is not liable for any consequences deriving from the use of this technology or source code. Any product that uses this technology must display the notice "Encryption using TecApro's GodSave technology, version 3". Users may also freely modify the GodSave source code or technology. If you choose to do so, your product must display the notice "Encryption derived from TecApro's GodSave technology, version 3".

The source code developed by TecApro to implement the GodSave technology can be downloaded from several Internet Web sites. For an up to date list of these Web sites, please visit "http://www.tecapro.com/". Currently only the Pascal source code is available; by the time you read this the C implementation should be available. In the same site you will find a Windows DLL file, which you can use from C and Pascal applications.

3.3. MODIFYING THE GODSAVE ALGORITHM

There are many simple and straightforward changes a user can make to the source code, to produce a non standard version of the GodSave technology, without compromising the quality of the algorithm. The strength of the GodSave algorithm resides in its variability which is increased by the creation of non standard versions. Security is increased by the use of a non standard version because in that case an attacker needs to have physical access to the source code or the executable code and in the later case the attacker also has to disassemble the code before being able to mount an effective attack on the algorithm.

Any non standard version of GodSave that is produced will of course not work with the standard version, nor with other non standard versions. However the use of a non standard version may be the best choice in some situations, such as security for a closed organization, or the development of a vertical application.

Here are some examples of the sort of simple changes that can be made to the GodSave algorithm:

If you want to be more ambitious you could add a new primitive scrambler (but I recommend you do not remove one of the existing scramblers). Be careful that the new primitive scrambler does not diminish in a significant way the information content of the text which it processes, that is to say the new scrambler when applied to two different texts should generate with high probability two different results.

Currently only TecApro is developing products that incorporate GodSave technology. The products currently available, or soon to be available which incorporate this technology are:

"TecApro TecaMail" is a secure E-mail client for Internet. Besides message encryption, the product includes many interesting features such as: multi-language user interface and spell-checkers; validation of the reception and reading of messages; filters; inclusion of spoken messages in an E-mail; internal compression of messages; etc.

"TecApro TecaCom" is a secure, real-time communications program for Internet. It allows two users to concurrently perform activities such as: chat using the keyboard; talk to each other; send or receive files; and remotely control each others DOS applications. The price of this product is USD 24.

"TecApro Eureka" is a plug-in for Eudora Pro 3.0 that offers GodSave encryption for the users of this popular E-mail program. This product is under development and will cost USD 9 when available (aprox. date August 1997).

"TecApro TecaCrypt" is a general purpose encryption utility. The aim is to provide a utility which the user can use to maintain specific files or directories in disk encrypted at all times, while allowing all Windows applications to access them in a transparent way. This product is under development and will cost USD 24 when available (aprox. date July 1997).

PART 2: IDEAS, OBSERVATIONS AND OPEN QUESTIONS

The current version of the GodSave technology is a block encryption/decryption algorithm, and does not include algorithms for key management. In this section I want to describe the way in which one could construct a key management algorithm for the GodSave Technology.

The GodSave algorithm is a member of a class of algorithms known as "symmetric". This means that the key used to decrypt a ciphertext must be the same as the key used to encrypt the plaintext. In a networked environment with many individual users, it soon becomes impractical to create and distribute different keys for all the possible pairs of users who need to communicate. What's more the keys have to be distributed over a secure channel and protected and stored with great care by each user. One way to solve this problem is to use an asymmetric encryption algorithm known as "public key cryptography". In these systems the key needed to decrypt a message is different from the key need to encrypt it. The use of public key encryption greatly simplifies the key management problem because each user can "publish" the key to be used to encrypt messages sent to him. In addition a user has a private key which he uses to decrypt the messages sent to him. The problem with public key encryption is that the two keys are related and the security of the system depends on the analytic impossibility or the computational unfeasibility of deducing one key from the other. However the security of the most widely used implementation of public key cryptography, RSA, depends on the assumption that it is extremely difficult to factor very large numbers. Even though the currently known (published) mathematical methods of factoring are slow, there is no proof that much more efficient methods cannot exist. Therefore it is prudent to suppose that more efficient algorithms do indeed exist and that they may have already been discovered but not published because the discover wants to benefit from keeping the procedure secret.

Key management lies at the very heart of a secure communication system. If everybody uses a particular method (say RSA public keys) to create, communicate and store keys, and if this system can be broken then the security of the whole system is compromised, because all the keys will be discovered. It is an important feature of a good security system that if a breach occurs it should be possible to contain it locally and not let it compromise the overall security of the system. Fortunately, In many situations the use of public key cryptography as a means of solving the key management problem is not essential.

As an example of how the GodSave technology can help an organization solve its key management problem consider the following situation:

An organization which has offices in several different locations, each with its own local area network, wants all its staff to be able to communicate by means of a secure E-mail system. If the organization uses GodSave technology as the basis for implementing its secure communication system then it could use the following protocol to solve the key management problem:

On the security server (one per network) and only on the security server resides a level-0 master key, which is unique for the whole organization. This master key could for example de stored in a physical device that is tamper proof. In principle nobody needs actually know and have to remember this level-0 master key.

Once per day, the level-0 master key is only used to produce a level-1 master key. This can be achieved in many ways, for example by scrambling the current date.

When Alice wants to send a secure message to Bob she must first identify herself. This is a local problem, which depending on the level of security required can be solved in many ways. For example Alice could be identified by: her personal password; her physical location; her signature on a digitizing tablet; correct answers to a personal quiz; a voice timbre test; an image of her retina; her fingerprints; the heat distribution on her face, or whatever.

Alice constructs a block of data (the message "ticket") that contains the following information:

She then encrypts this message ticket using her personal password and an empty (null) master key and mails the resulting ciphertext to the local security server.

The security server then encrypts the message ticket using an empty password and the level-1 master key, and it then encrypts the level-2 master key using Alice's password and the level-3A master key. It sends Alice's computer both ciphertexts and the level-3A master key unencrypted.

Here are some of the important characteristics of this protocol:

Personal keys are known only by the local security server; there is no organization wide list personal keys and no need to communicate these keys to remote networks.

This key protocol can be extended to cover individual remote users. For example, if Alice travels all around the country and needs to communicate using her notebook, then the following modification to step 3 in the key protocol already described can be used.

Periodically load, by some means or other, Alice's computer with a level-3 master key that is known only to Alice's computer and the security server to which she is assigned.

This way it is not necessary to transmit an unencrypted level-3 master key. In order to read Alice's mail, an attacker must now have physical access to her computer in order to steal the level-3 master key, be able intercept her communications, and know or be able to guess her password. If an attacker is able to achieve such a broad range of security breaches then the organization will not do any better using public key cryptography.

In this section I want to share with you some of my ideas for developing and extending the GodSave technology. This way I hope to encourage you to explore and exploit some of these ideas.

A good encryption algorithm makes a good one-way hash function because, by definition, it is very difficult to deduce the plaintext from the ciphertext. The idea here then is to use the Karn encryption algorithm as the scrambler for a "higher order Karn".

Start by dividing the key in 4 subkeys K1..K4, and the text in 4 subtexts T1..T4, and then apply the basic Karn algorithm to obtain:

where the symbol "." means "concatenated with", E denotes the GodSave encryption algorithm and C1.C2.C3.C4 is the ciphertext.

Substituting the Karn algorithm for the scrambler function SS we get:

To encrypt:

To decrypt:

where S denotes the Scrambler used.

It is an open question whether this approach produces a stronger cipher.

With all algorithmic (pseudo) random generators some regularity can be found by studying a sequence that is long enough. I believe it is possible to build a "cryptographically secure generator", by randomly selecting a group of independent generators out of a large pool of generators, XORing their output, and using this particular generator only to generate a small random sequence.

We would achieve comparable security (quality of randomness) but better performance if we chose 5 generators out of a pool of 50.

An interesting consequence of Karn's algorithm is the affinity between ciphers and scramblers: if you have a good scrambler you can produce a good cipher. The contrary is also true: if you have a good cipher you can produce a good one-way function, i.e. a good scrambler.

To round out this paper I would like to present some personal observations on the ethics of trying to develop a secure encryption algorithm. Without doubt, encryption is a tool that can be used by criminals and other "enemies of society" to do harm. However, the same applies to almost any other tool, such as cars, cellular phones or binoculars. I can understand the preoccupation of governments that the existence of a secure encryption algorithm would make it impossible to intercept the communications of criminals and other enemies of society. However, I firmly believe that our personal information is our private property and that we have the right to safeguard it as well as we can. Personally I am not paranoid about governments. I believe that modern democratic governments are basically good and accurately reflect the attitudes and culture of the people they govern. But Internet is becoming the nervous system of our world, and if any entity were permitted the right to read or disrupt the flow of information on the Internet, it would amount to an unacceptable and dangerous concentration of power.

With the advances of the information technologies, governments already have at their disposal many powerful tools to aid them in their fight against crime (both violent and white-collar). Take the international financial system as an example. This system has been created as a public service and is regulated by governments. I feel such systems should be designed in a way that they take full advantage of modern technology, and that they should be open to inspection. Thus, for example, all large or repetitive financial transactions, without even the need for any warrants, should be routinely and automatically examined to detect criminal activity. My point is that even though personal information is private, nobody should have the right to use the international financial system created by society, in a way contrary to the public interest. Personally I don't want anybody to be able to read my work or my letters, but I don't care if there are automatic systems in place that detect whether I am using the financial system in order to sell drugs or arms or to avoid paying taxes.

One last personal note on ethics and public policy. I believe that ethics in politics should not be an abstract concept, and that the impact of a law or regulation on the public interest should be quantified so as to keep it in perspective. For example, organizations that produce or sell tobacco or handguns contribute directly to the killing of orders of magnitude more people than criminal organizations which produce or sell illegal drugs, but governments invest much more in combating and controlling the latter than the former. Then again people who cheat on their taxes do orders of magnitude more harm to society than criminals who rob banks or gas stations. Ask yourself, how probable it is that you will die in a war or a terrorist attack compared with the probability that you will die from cancer? Clearly the second threat is hundreds of times more serious for the average individual, yet governments invest much more in combating the former risk. If public investment in defending against these threats is inversely proportional to the threats themselves, then there is something very wrong with our democracy. It seems to me that law makers who pressure for spending public funds on defense instead of on cancer research, are orders of magnitude more dangerous to the average citizen then an international terrorist. Every political decision and its impact on the public interest should not be discussed in isolation and out of context, nor should they be discussed in an emotional manner, rather it should be weighed (for both cost and benefit) and put into perspective with the whole of public interest.