Super Fast Encryption (Linear Feedback Shift Register Sequences)

February 1, 2017 | Views: 4460

Begin Learning Cyber Security for FREE Now!

FREE REGISTRATIONAlready a Member Login Here

Estimated reading time: 2.5 minutes

Use 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

Share with Friends
FacebookTwitterGoogle+LinkedInEmail
Use Cybytes and
Tip the Author!
Join
Share with Friends
FacebookTwitterGoogle+LinkedInEmail
Ready to share your knowledge and expertise?
7 Comments
  1. I’m currently playing with your algorithm as a starting point for creating a “more” complex cipher. I will update you as soon as I add it complexity. Maybe you’ll have some input, so we can push it further! Thanks again for the idea! +30!

    • Thanks for the Cybytes. Feel free to message me when your done. Algorithms like AES and IDEA are (currently) perfect for layer 7. SSL/TLS is a great Layer 4/5 algorithm. IPsec is a great level 3 algorithm, if only we would finally move to IPV6. Thus, the kind of protection we want to provide is either level 2 or level 1 encryption. Working at level 1 requires a stream cipher as a message of any bit size is a valid mestage. Working at layer 2 means you can read the ethernet frame before encryption. That is, you would get a source MAC address (6 bytes), destination MAC address (6 bytes), and Ethernet length. Thus, message encryption can be salted per switch connection to ensure that a compromise in one IV does not cause a compromise in another. Remember that both the physical and Data Link layers need to be really fast, and therefore non linear arithmetic is probably going to cause too much propragation delay. Notably, Protocols like PPP, and companies like PacketLight offer security models for the data across your wire. Additionally, where packets travel across the web and therefore may easily find themselves in the hands of black hat hackers, At the 1st and 2nd OSI level we typically have physical security over our switches and internal wires. Thus, most companies prefer to only use Layer 3 encryption and above. Processing Speed is becoming ever so fast and EATHSec or even BitSec might become the norm. If quantum computers become mainstream, we have certain algorithms for those. LFSRS is therefore only required for a very small percentage of businesses where availibility trumps security, so we need a “free” way to aff security. Good luck Byte zealot

      Regards,

      ProgrammerE

  2. nice article

  3. do you have a source that explains the initialization vector example or is that just a written out sigma- thanks “from us noobs”

    • MAGLEV

      I came up with this example myself. The textbook referenced has another example.

      Let me try to walk you though my one.

      Initialization Vector (IV) is the secret key that you must come up with. Choosing the IV has nothing to do with Linear Feedback Shift Register sequences. For our purposes, we will let our IV be the vector (1, 0, 0). That is, gen(0) = 1, gen(1) = 0, and gen(2) = 0. We then generate new bits for our key by applying the inductive formula gen(x_{k+1}) = x_{k} + x_{k-2} (mod 2). Mod 2 is a fancy way of saying subtract or add 2 until you either get 0 or 1. gen(4) = gen(1) + gen(3) = 1 + 0 = 1. Thus, gen(4) = 1. gen(5) = gen(2) + gen(4) = 0 + 1 = 1. Therefore, gen(5) = 1. gen(6) = gen(3) + gen(5) = 0 + 1 = 1. Therefore, gen(6) = 1.
      gen(7) = gen(4) + gen(6) = 1 + 1 = 2. 2 is not 0 or 1, so we subtract 2 from it. The result is 0. Therefore, gen(7) = 0. gen(8) = gen(5) + gen(7) = 1 + 0 = 1. Therefore, gen(8) = 1. gen(9) = gen(6) + gen(8) = 1 + 1 = 2. 2 is not 0 or 1, so we subtract 2 from it. The result is 0. Therefore, gen(9) = 0. gen(10) = gen(7) + gen(9) = 0 + 0 = 0. Thus, gen(10) = 0. Notice that gen(8) = 1, gen(9) = 0, and gen(10) = 0. This is the same setup as the initialization vector. Thus, gen(11) = gen(4), gen(12) = gen(5), or in general gen(n) = gen(n+7) The resulting key extended using the linear recurrence is (1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, …). If the linear function is chosen well, the IV should generate a cycle of length approximately 2^k (this is a typo in the post). xor is a function which takes two boolean values (think 1 or 0) and returns 1 if they are the same. 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). xor(1, 1) = 0, xor(1, 0) = 1, xor(0, 0) = 1, and so on for all the bits in the plaintext. so the cypher text is (0, 1, 0, 1, 0, 1, 1, 1). To decrypt our message, we just xor it again with the same key. for the first bit, xor(1, xor(1, 1)) = xor(1, 0) = 1. xor(1, xor(1, 0)) = xor(1, 1) = 0. xor(0, xor(0, 0)) = xor(0, 0) = 0. and so on.

      I hope this helps

      Regards,

      ProgrammerE

  4. Very interesting way to create cipher. I believe if we add it some more complexity, we have a winner! But all in all, very good starting point eh? Thanks for this 😀

Comment on This

You must be logged in to post a comment.

Our Revolution

We believe Cyber Security training should be free, for everyone, FOREVER. Everyone, everywhere, deserves the OPPORTUNITY to learn, begin and grow a career in this fascinating field. Therefore, Cybrary is a free community where people, companies and training come together to give everyone the ability to collaborate in an open source way that is revolutionizing the cyber security educational experience.

Cybrary On The Go

Get the Cybrary app for Android for online and offline viewing of our lessons.

Get it on Google Play
 

Support Cybrary

Donate Here to Get This Month's Donor Badge

 
Skip to toolbar

We recommend always using caution when following any link

Are you sure you want to continue?

Continue
Cancel