Super Fast Encryption (Linear Feedback Shift Register Sequences)

Estimated reading time: 2.5 minutesUse of cryptographic algorithms like Triple DES, AES, and Twofish is good for applications where you need high security and you can afford a slight delay. Credit card purchases, file transfers, and turn based games are good candidates for these kinds of algorithms. Real-time games, market data, and distributed computing needs to be extremely fast and need not be highly secure. Having security on these types of systems is still important as they provide a market advantage in secrecy. We use layered security to protect these types of resources. We protect the physical servers, but we still need a way to send data to and from different servers in an extraordinarily small amount of time. Thus, we want to work on the physical or data link layers. One way to accomplish this is to use linear feedback shift register sequences.

Come up with an IV (Initialization vector). The longer the IV, the more secure the transmission of the frame. The payoff is that longer IV’s are more time consuming. We then come up with a linear recurrence relation. If the IV has length k, the recurrence relation should describe the k + 1th bit in terms of a linear combination of the first to kth bits (Trappe & Washington, 2012).

E.g. IV = (1, 0, 0), gen(x_{k+1}) = x_{k} + x_{k-2} (mod 2). The resulting key extended using the linear recurrence is (1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, …). Notice that the pattern repeats after a period of 7. If the linear function is chosen well, the IV should generate a cycle of length approximately k^2. We then xor the generated key with our message to obtain our cypher text. Plaintext = (1, 1, 0, 0, 1, 0, 1, 0), key = (1, 0, 0, 1, 1, 1, 0, 1), so the cypher text is (0, 1, 0, 1, 0, 1, 1, 1). To decrypt our message, we just xor it again with the key.

Given the simplicity of the cryptographic function, we can implement this directly using hardware. This gives us a fast and relatively secure way to send information. However, this is not cryptographically secure if any plaintext is known. If we add the plaintext to the cipher text, we get back the key.

Remember the CIA Triad? Confidentiality, Integrity, and Availability are at odds with each other, and increased availability requires less security. While LFSRS are not perfect, they serve their purpose, and anyone inventing the next multiplayer shooter or video chat program should investigate the tradeoff between security and real-time communication and balance the two.

I hope you enjoyed this short but sweet article, more to come later

Regards,

ProgrammerE

---

References:

Trappe, W., & Washington, L. C. (2012). Introduction to Cryptography with Coding Theory. Upper Saddle River, New Jersey, United States of America: Pearson Education Inc. Retrieved January 26, 2016