The history of cryptography has shown that unbreakable ciphers had in many cases been cracked shortly after their widespread use had begun. One famous example is the "Enigma" encryption machine used by the Nazis in world war two: British specialists at Bletchley Park had been able to crack the clever permutation code. This resulted in detailed knowledge about most German military operations and in the total loss of the German submarines.
 

The widespread DES algorithm has long been supposed to be unbreakable. In January 1999 a test performed by RSA Data Security, Inc. (San Mateo, Calif., USA) proved that it takes less than 22.25 hours to crack the 56 bit algorithm by brute-force (by trying all 256 possibilities). That was 365 days after the same company needed 41 days for that task! RSA claim to have a much better cipher, which is obviously true.

Today a code length of 128 bit is regarded as safe by experts (1000 bit for RSA). Thus, it took just 25 years for the experts to actually double their requirements in key size (which is effectively 10000000000000000000 times more than what was initially regarded "safe"!!!).

It is indeed true that a key size of 256 bit are absolutely secure. There exists (even theoretically) no machine which can break such a code within an acceptable period of time.
But one can never be sure that there exists absolutely no shortcut.

Technology advances quickly. Day by day it becomes more likely that somebody is able to decrypt files containing confidential data. Why not simply oversize the encryption algorithm to solve this nasty but inevitable security problem?
The main reason is speed! It is usually claimed that long keys slow down the algorithm too much. That's true because execution time increases at least by the key size at the power of two.

A new approach implying self-compiling machine code solves that problem. Execution time increases only linearly with key size. The idea behind it is to randomize the algorithm itself. That’s why I have named it „Polymorphic Method“. What if both data and the actual encryption algorithm are undefined in the beginning. An Opponent who wants to break your key feels deprived of any constant. Working with variables only quickly becomes pretty complex. Commonly known ciphers use one key - say one variable. A mathematic equation comprising two variables cannot be solved! For cryptography, there is of course a solution - but the only way to find it is to search exhaustively the whole keyspace. This problem is one-dimensional for common ciphers and two-dimensional for the Polymorphic Cipher.
The Polymorphic Method is among the strongest ciphers available today and it's probably the strongest. The method simply takes advantage of machine code assembled at random to yield extraordinary security against all kinds of attacks. It is even intrinsically safe against the analysis of the program's instruction sequence because the instruction sequence itself is a variable! It is important to know that the key assumption for successful cryptoanalysis is detailed knowledge of the encryption algorithm - but the actual Polymorphic Method’s algorithm is inherently UNKNOWN.

Basic principle of the Polymorphic Method

Two different passwords (or two parts of one password) are fed into random number generators. The one RNG on the left produces a byte stream which is compiled into machine code. The compiler simply assembles standardized building blocks, adjusts addresses as well as entry- and exit points to generate a piece of machine code which affects the key data array during execution of the machine code. The key data array is initialized by the right RNG which is biased by the right password.

After the machine code has been executed, the content of the key data array can be used to encrypt plaintext through the application of the xor function. The content of the key data array can and should alternatively be used for biasing an underlying cryptographic algorithm which is simple and fast. By doing this, the complexity of the total crypto system increases and it becomes much more difficult to analyze the internal state of the key data array, although the information it contains gives no clue about the keys.

It is even more confusing to sometimes recompile the instruction sequence. This makes the method dynamically polymorphic.

The compiler internal to the Polymorphic Encryption Method compiles replaceable code fragments which use the processor’s registers in an identical way. Each building block can be exchanged by any other. The actual code length can vary due to differences in complexity but not the way data is passed from one building block to the other. A data array is used as a long variable which is initialized by a password. It takes the place of the key as known from conventional crypto algorithms. The CPU works on this key data array and performs permutations, modulo-divisions, shifts and other nonlinear operations.

An implementation of a Polymorphic Method is publically available as a Windows program called „Best Possible Privacy“. It’s crypto engine uses the CPU register ebx as input and output register, eax as general purpose buffer and ebp as base pointer to the key data array. The key data array that ebp points at is 256 bytes long.

Example of a simple building block

The xor operation alters ebx and four bytes of the key data array:

  push ebp;         // save the start address of the key data array for later
  mov eax,123;             // load offset: constant data which was calculated by the compiler
  add ebp,eax;
  mov eax,[ebp+0];  // load key[ebp+0] in AL and key[ebp+1] in the next upper byte of eax and
                    // so on up to key[ebp+3]
  xor ebx,eax;             // this instruction can be replaced by another or a set of instructions
  xor [ebp+x],ebx;  // change the key data array frequently; x is defined by the compiler and
                    // chooses one element of the key
  pop ebp;          // restore start address of the key data array

Instead of xor it is of course possible to calculate sums, to perform shifts, multiplications and modulo divisions, as well as to calculate pseudorandom numbers with more complex instruction combinations. A good implementation of the presented method should rely on a set of building blocks which change a lot of key bytes and not just 32 bit. Simple xor instructions, as well as addition and subtraction are cryptographically weak, but the general code assembly method can be demonstrated best with these.

Instructions should alter the key quite frequently for not to offer the possibility to cryptoanalyze it by using a ciphertext codebook. When the method is used as pseudo random number generator, the result in ebx can be further processed. The internal state represented by the key data array is big enough for not to be directly or indirectly exposed.

An example for a much more cryptographically safe building block is a CRC32 implementation:  

The function calculates a 32 bit CRC according to IEEE 802. The polynomial is: x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 +x + 1. X32 does of course not exist and the 1 only inverts the input data. Thus, the polynomial can be written as: $04C11DB7

  push ebp;         // ebp MUST never be really destroyed
  and  eax,127;     // perform an operation with four key bytes at a time using eax from the
                       previous instruction block
  add  ebp,eax;
  mov  eax,[ebp+0]; // load key[ebp+0] in AL and key[ebp+1] in the next upper byte of eax
                       and so on up to key[ebp+3]
  mov  esi,ebp;     // save ebp for later to alter the key
  pop  ebp;         // get original base of the key data array
  push ebp;         // restore stack frame
  push ebx;         // save ebx for later
  mov  ecx,32;      // counter for the loop
  xor  edx,edx;     // edx is used to clear the zero flag before the loop @rep1 command below
@rep1:rcl ebx,1;    // shift data in from ebx
  rcl  eax,1;       // use eax as CRC buffer
  jnc  @cnt1;       // CRC decision
  xor  eax,$04C11DB7;      // xor with IEEE 802 generator polynomial
@cnt1:add dl,1;     // clear Zero-Flag (will be rarely necessary)
  loop @rep1;
  pop  ebx;         // restore old ebx value. ebx keeps a running 32 bit result
  mov  ebp,esi;     // get the address of the previously selected key data bytes
  mov  [ebp+0],eax; // alter the key
  xor  ebx,eax;     // alter ebx
  // here is the end of the CRC routine
  pop   ebp;         // exit the routine by restoring the original ebp

The presented building block only affects four key data bytes. Depending on the size of the key data array it should affect much more key bits for good attack security. It is very simple to extend the routine for satisfying this demand.

It is possible to add loops over one or more instruction blocks. This is usually performed by adding the 80386 loopne-command. The method spends more time on crunching instructions and that simply slows it down in order to make cryptoanalysis a time-consuming job. By altering ebp with every loop cycle, the key can influence the algorithm more often.

8192 bit keys are definitely too long. The increase in security with so many key bits is negligible compared to 256 bit. Uncrackable is simply uncrackable. In spite of this, the implementation of PMC in ciphers.de’s BPP file encryption tool comes with this key size. Why not?

Attack security 

Each instruction affects at least 32 bits of data and sometimes it alters the key.

If there are only 4 cryptographic instruction blocks and 16 of these blocks can be assembled chaotically one after the other, there exist 4¹⁶ = 4294967296 different possibilities for the actual encryption algorithm! If 128 instruction blocks were to be assembled, a choice of 4¹²⁸ = 1,158*10⁷⁷ combinations would result (standard 128 bit encryption yields a total of 3,403*10³⁸).

It is important to note that this is without affecting execution time because there is the requirement for a well-shuffled key data array which must be guaranteed by conventional algorithms as well.

The Polymorphic Method features a substancially higher attack security than any conventional method. In order to calculate the total attack security, the number of code combinations must be multiplied by the number of key combinations. Key size may be 16 bytes = 128 bits; thus there exist 2¹²⁸ = 3,403*10³⁸ combinations for the key stored in the key data array. The two keyspaces multiplied yield 1,158*10⁷⁷ * 3,403*10³⁸ = 3,913*10¹¹⁵ possible key combinations for the Polymorphic Method.

In order to compare conventional cryptographic methods with the Polymorphic Method, the total keyspaces must be compared. As both methods are assumed to work on a 128 bit data key, this comparison is legal. Thus, the polymorphic method beats any conventional method by a factor of 3,913*10¹¹⁵ / 3,403*10³⁸ = 1,150*10⁷⁷  (!). This is more than the number of atoms on our planet!

The actual implementation in the cryptographic program „Best Possible Privacy“ uses 32 instructions and three bit of constant data per instruction. Thus, there are 32 ways to affect the algorithm multiplied by 8 possibilities for constant data => 256 = 2⁸ variations

If the algorithm is limited to 1024 instruction blocks, there are 2^{(1024 * 8)} = 2⁸¹⁹² different code combinations possible and equally probable! The 256 byte keyspace further enhances attack security to yield 2⁸¹⁹² * 2²⁰⁴⁸ = 2¹⁰²⁴⁰. Note that nearly 100% of the security comes from the compiler. The new method uses commonly known techniques but enhances them significantly.

Attacks and their likelyhood of success on the Polymorphic Method

Attacks are not algorithms, but instead just general approaches which must be reinvented for every new type of cipher.
It is generally assumed that The Opponent knows the design of the cipher and has virtually any amount of plaintext and corresponding ciphertext ("known plaintext"). It is further assumed that The Opponent has the real-time ability to obtain "defined plaintext" by enciphering messages at will and collecting the resulting ciphertext.

Exhaustive Search (Brute Force on the keys)

Try each possible key until the message deciphers properly. Try most-likely keys first.

A keyspace of at least 128 bits should be sufficient to prevent exhaustive search in the foreseeable future. The keying system for the Polymorphic Method is hard to implement with less than 256 bits and has usually a keyspace substancially beyond this value - around 2048 bits, not counting the key combinations for the instruction key which usually provide more than 99.9999999999% of the total security.

Chosen Key

Try various keys on known plaintext and compare the resulting ciphertext to the actual ciphertext, to try and build the correct key value.

As the key is more or less the algorithm itself, the task of an opponent is hopeless because the one-way polymorphic function comes in different shapes with each key, which is so big, that there is no possibility to isolate and work separately on some kind of table. A computer can only be as big as there are atoms on this planet.

Ciphertext-Only Codebook

Collect as many ciphertexts as possible and try to understand their contents through usage and relationships; then, when a ciphertext occurs, look it up. This treats the block cipher like a code, and is the classic approach to code-breaking.

Just as some letters are more frequently used than others, words and phrases also have usage frequencies, as do blocks which contain plaintext. If the cipher block size is small (under 64 bytes), and if the ciphering key is not changed frequently, it may be possible to build a codebook of block values with their intended meanings.
Codebook attacks of any sort are ideally prevented by having a large number of block values, which implies a large block size. Once the block size is at least, say, 64 bytes, it can be expected that the amount of uniqueness in each block exceeds anyone's ability to collect and form a codebook.
Since the complexity of any sort of a codebook attack is related to block size only, doing "triple" anything will not affect increase this complexity. In particular, this means that Triple DES is no stronger than DES itself under this sort of attack, which is based on block size and not transformation complexity.
The Polymorphic Method is best implemented with a 1024 byte block size and the instruction sequence changing with every block. The method is further ideal for producing a seed for some random number generator which decouples the algorithm from the generation of the confusion sequence. Because a Polymorphic Method comes in different shapes with each key, any kind of codebook will contain mostly noise and will not be of great use.

Known Plaintext

Somehow "obtain" both the plaintext and the corresponding ciphertext for some large number of encipherings under one key.

With this kind of attack, one plaintext-ciphertext pair contains sufficient information to obtain the content of the key data array. In order to identify a key, both keys must be guessed using the Exhaustive Search method.
As both the input to the compiler as well as the keys are unknown, it is difficult to reveal the full internal state without revealing the underlying crypto system. The Polymorphic Method hides roughly three quarters of the internal state in the actual instruction code and that alone provides sufficient complexity. Note that a single known plaintext and ciphertext pair probably would identify a DES key!

Known-Plaintext Codebook

Collect as many ciphertexts and associated plaintext blocks as possible; then, when a ciphertext occurs, look it up.

Small block ciphers prevent codebook attacks by randomizing the plaintext (often with Cipher Block Chaining) so that the plaintext block values are distributed evenly across all possible block values.
Codebook attacks are ideally prevented by having a large number of block values, which implies a large block size. To prevent this attack for the future, a block size of 64 bytes is regarded as safe so the uniqueness it does contain assures that there will be too many different blocks to catalog. A 1024 byte block size and the use of a confusion sequence generator with at least 64 byte internal state makes it impossible to gain any ground on this kind of attack.
As the key is more or less the algorithm itself, the idea to create a table ends in logging noise.

Chosen Plaintext

Without knowing the key, arrange to cipher data at will and capture the associated ciphertext. Dynamically modify the data to reveal the key, or keyed values in the cipher.

The point here is not to decipher the associated ciphertext because the opponent is producing the original plaintext. If the opponents have chosen plaintext capabilities, they can probably also submit arbitrary ciphertext blocks for deciphering.
The weakness to be exploited here usually depends upon the ciphering system beyond the core cipher per se - a point with little internal state. As far as the Polymorphic Method is concerned, there is no static algorithm with some known weakness. Instead, there are a lot of possible weaknesses – each possible keyed state. The Chosen Plaintext attack is not applicable here.

Chosen-Plaintext Codebook

Create as many ciphertexts and associated plaintext blocks as possible; then, when a ciphertext occurs, look it up.

This is much like the previous codebook attacks, now with the ability to fill the codebook at will and at electronic speeds. Again, the ability to do this depends upon the cipher having a relatively small block size and on a fixed cryptographic algorithm. This attack is again not applicable because it’s simpler and equally efficient to try all possible keys.

Meet-in-the-Middle

With a multi-layered structure, given known-or defined-plaintext, search the top keyspace to find every possible result, and search the bottom keyspace to find every possible value.

With a two-level construct and a small block size, matches can be verified with a few subsequent known-plaintext/ciphertext pairs. Of course, three and more-level constructs can always be partitioned into two sections so a meet-in-the-middle attack can always be applied; this just may be pretty complex.
As each layer in a good crypto algorithm contains a huge amount of keyed state or „keyspace“, the Polymorphic Method uses a large key and consequently adds a huge amount of unknown algorithm which multiplies with in the beginning unknown data keyspace to yield extraordinary complexity.

Key Bit Bias

Through extensive ciphering of fixed plaintext data under a variety of different keys, it may sometimes be possible to associate key bits with the statistical value of some ciphertext bits. This knowledge will break a conventional cipher quickly.
As different keys inevitably produce different cipher algorithms, statistics cannot help to link ciphertext with plaintext. There’s simply a new independent variable in the game with the Polymorphic Method as each key state has some pretty unique weakness.

Differential Cryptanalysis

Exploit known properties of particular known substitution tables to effectively reduce the number of "rounds" in an iterated block cipher.

The original form of Differential Cryptanalysis mainly applies to iterated block ciphers with known tables, neither of which are present here. For an iterative cipher like DES, statistical unbalance can be found in known, fixed substitutions and that can be exploited to peer back into previous iteration steps.
For the Polymorphic Cipher Method, each different input value will actually select a different cipher, and this results in a completely variable transformation. It is hard and very inefficient to attack a transformation which changes it’s structure completely whenever it is probed.

Summary

Except for the possibility to gain knowledge of the final state of the key data array in the basic configuration, there is nothing else to find out. There is no possibility to identify a key other than by searching exhaustively. The available keyspace is much greater than for any other cryptographic method. In order to compare the presented method with conventional methods, a conventional method has some data keyspace and only one possibility for the algorithm. The presented Polymorphic Method has the same data keyspace and an additional algorithm keyspace. All in all, the new method features a dramatic increase in security compared to common approaches.
It is worth imagining that cryptographically strong ciphers like DES, GOST, IDEA; Hashes, etc. are the building blocks of the Polymorphic Method. The weaknesses of each specific building block would vanish. The result would probably be a perfect cipher.

Speed

The original implementation of PMC in the BPP file encryption tool is by far too slow when compared with the latest developments. The latest variant with 512 bit key length is implemented in PMC Ciphers BPP Disk Encryption. This crypto engine comes with an encryption speed of 500Mbit/s, which is approximately 10 times the speed of AES (Rijndael algorithm) operating with 256 bit keys! BPP Disk is a hard disk encryption tool which adds encrypted file-hosted volumes and encrypts raw NTFS partitions. It is available for Windows 2000 ,Windows XP and “Windows 2003 Server” operating systems.

Conclusion

For PMC, which was secret of state in 1999 in Germany, there exists no attack other than exhaustive search. There’s no theoretical or practical way to to reconstruct keys from plaintext.
The presented method comes with a comparable number of „data keys“ as conventional symmetric encryption methods. It adds a significant amount of possible and equally probable algorithmic keys, thus yielding substancially higher security and speed.

The 512 bit PMC crypto engine implemented in our product BPP Disk Encryption uses the most probably fastest encryption algorithm in the world!