EnRUPT – The Simpler The Better

What’s up with this patent application? It clearly seems to cover a large number of ciphers: Dragon, Salsa20, ChaCha, Trivium, XXTEA, EnRUPT and possibly others that employ the same feedback structure:

where A and B are two positive constants offsetting the index by no more than a half of the block/state. In other words, all the ciphers that update each bit/word by a function of at least two of its neighbors from both sides, regardless if the bits/words are updated all simultaneously, in groups or one by one.

The DES was patented, the IDEA is patented, the SHA-2 is patented and the IBM and Hitachi hold patents for the ADD-XOR-ROL ciphers, none of which seem to harm the wide-spread use of any of those ciphers and hash functions. So crypto patents may not be a problem for the cipher’s acceptance after all, at least not as much as some of the patent-hating academics are claiming it to be…

However, I do have some explaining to do. First of all, the first provisional application for it was filed on the 5^th of November 2004, that is six days before both Salsa20 and Dragon were first published on the 11^th of November 2004. AFAIK, the only cipher with the above structure that was published before that date is XXTEA, which I honestly was not aware of before filing that application.

I am no patent attorney, but as a cryptographer who may be called in as a consultant, I can guarantee that it can be easily shown to the court that it is not obvious how the use of other distances could be beneficial or that it could be trivially derived from the XXTEA structure that uses only the two nearest neighbors. Why not? Because it could be more secure and it could be totally insecure. It is the security that is the whole purpose of a cryptographic component and is the reason why they are designed the way they are. For a cipher or any other cryptographic component to be insecure is like for an airplane or any other flying machine to not be able to lift off the ground. It cannot be called a flying machine if it can’t fly. In this case, security of one is not directly obvious from the other, however small the differences may be, and if you are calling it “cryptographic”, you are automatically claiming cryptographic security.

So if this patent is granted, I anticipate some difficulties for all the ciphers with the above structure. However, all the constructions of this one particular form including EnRUPT are certainly off the hook since XXTEA is prior art:

All the similar-looking “incomplete” designs like Rabbit, all the known FSRs, block chaining mechanisms and T-Functions published before this patent application was filed update the current word only by the neighbors located on one side of the current bit/word being updated. Even Prof. Bernstein’s SURF, the predecessor of Salsa20, updates each word by only one of its neighbors. All the “complete” Feistel-Network ciphers including all the “complete” source-heavy UFNs like MD5, SHA, etc. may appear somewhat similar, but in them the entire block/state is involved in the feedback. All such constructions are outside the scope of this patent application.

One may argue that for instance Salsa20 can also be viewed as a square, but that is a weak argument that may or may not hold. The word indexes in Salsa20 are quite clear, with certain well-defined distances between each other… It can be twisted to look like any shape with word shuffling, but that does not change its structure. Patent claims can easily cover something for what it is, but they cannot be invalidated by how else one can see it. A microchip can be viewed as a piece of adulterated sand. Nevertheless, every microchip has many patents protecting the technology in it quite successfully.

I cannot predict if this patent application will be granted, how or if it will ever be used against any cipher, or what the outcome may be, but one thing is certain: EnRUPT is identical in its structure to the XXTEA, which is obviously prior art.

To everyone else, good luck!