Need a very fast one-to-one algorithm, possibly encryption

Question

I need a very, very fast one-to-one algorithm. The algorithm doesn't need to be unbreakable. Reasonably strong is enough but it must be lightning fast. I will be implementing it in hardware. Area is a concern, too, so it shouldn't use too much logic.

It should be a function f_N(x) whose input is an N-bit number and whose output is an N-bit number. N is a constant, probably between 20-70. The function must be one-to-one. (ie invertible, meaning that decryption is possible. Decryption speed is irrelevant.)

I need to encrypt in under 3ns, which is about 333M inputs per second. DES, for example, does about 50Mbits per second. I need 333M inputs per second.

So far I've been using a Feistel cipher with about 6 rounds. That seems to take about 3ns.

Suggestions?

More notes

There have been some questions so I'll explain. I need to put keys into a hash table. The standard method is to hash the input key and use the result as an index into a table. Each row in the table must store the original key. Information theory tells us that the rows of the table don't actually need to be as wide as the input key, but rather as wide as the input key less the number of bits in the address of the table. For example:

• input: x (N bits)
• hash: x%128 (8 bits)
• verifier: floor(x/128) (N-8 bits)

It would be silly on a CPU where integers are usually the same width but I'm doing it in hardware.

x%128 is an easy hash to break. In fact, if the input keys only differ in the first few bits, you will have broken the hash on accident. I want a hash that won't be broken on accident and might even be difficult to break on purpose. I also tried an LFSR. LFSRs are fast but two LFSRs of equal length generate hash results that are correlated linearly. (If f(x) and g(x) give the same hash for two different polynomials, f(x+1) and g(x+1) are easily correlated.)

So, I need a function with N-bit input and V-bit,H-bit output (V+H=N) where it is difficult to find two inputs of length N such that both will output the same H. Encryption fits the bill in that it leaves the output the same length as the input and it is difficult to reverse. Something other than encryption might work, too, though it seems like what I want is almost the very definition of encryption.

Sorry about not explaining all this up-front. Hope that this clarifies things.

Answer 1

I am wondering if you are not concerned about the strength of the encryption then perhaps you don't need to be encrypting at all. The most important part of an encryption algorithm is is it strength. If the encryption is weak then you are not doing any good by encrypting in the first place.

Answer 2

I would recommend my old friend, the Tiny Encryption Algorithm

It's both fast and extremely low on footprint, which you probably also have to consider when implementing in hardware.

Answer 3

XOR is your way out :)

Answer 4

What's wrong with using a 64-bit "key" value and xor-ing each byte? You can cycle through the key as many times as needed to xor any plaintext bits after the first 64.

A 64-bit key could be an 8-char password or an 8-byte hash of a passphrase.

Since the key has almost as many bits as the message, it will actually be rather strong and extremely fast.

Answer 5

Here are some benchmarks with some algorithms: http://gd.tuwien.ac.at/privacy/crypto/libs/cryptlib/benchmarks.html

Note that these benchmarks are testing implementations of algorithms, so it might not be what you are looking for.

Answer 6

The following does not satisfy your requirement of a one-to-one function, but perhaps it might be of use if speed is paramount. (If it won't work, then I'd suggest a divide and conquer route: you are working in hardware, so theoretically you should be able to encrypt and decrypt in parallel, unless one input's encryption is dependent on previous inputs' encryptions.)

Just about the fastest hardware algorithm for what I would call "munging" is to treat your inputs conceptually as a bitstream, and XOR them with the bitstream output of a cryptographically secure and reconstructable bit generator -- reconstructable if you wish to decrypt it. One example which is simple and lightning-fast, but by itself is not secure, is a linear feedback shift register (LFSR). Choose a long period (2¹²⁸ - 1 or 2²⁵⁶ - 1 or something like that). The wikipedia page suggests modifications to enhance security. You could also try occasionally (e.g. once every M bits where M = 4096, 16384, 65536, whatever) XORing the state of the LFSR with the output of a slower but more secure bitstream (either a stream cipher, or a block cipher encrypting a predetermined set of inputs, e.g. an incrementing sequence, or a delayed snapshot of the LFSR state) -- though this falls into the don't-invent-your-own cryptographic technique, the idea being that well-known cryptographic techniques have had large amounts of energy invested on testing whether they have vulnerabilities.

Answer 7

When you say "fast" do you care only about throughput, or is latency itself of the highest importance?

If latency is not quite as important as throughput, is there any reason why you can't use a standard Feistel cipher that is known to be secure, and instead of having the full number of rounds (e.g. like 16 in Blowfish) output from combinational logic, stick a register in between each round, so that you pipeline the encryption algorithm? It would essentially require the same amount of hardware (a little bit more to add some flip-flops for registers) as a known secure encryption algorithm, but the propagation delay would only be that of one round of the Feistel network + the propagation delay of the flip-flops.

Answer 8

If you are doing this in hardware why don't you just use a standard block cipher on a DSP?

How Well Are High-End DSPs Suited for the AES Algorithms?