Report

LINEAR FEEDBACK SHIFT REGISTERS, GALOIS FIELDS, AND STREAM CIPHERS Mike Thomsen Cryptography II May 14th, 2012 Outline • Linear Feedback Shift Registers (LFSR) • Interesting properties of LFSR • Stream ciphers with LFSR – correlation attacks • A5/1 and it’s weaknesses • Looking forward Linear Feedback Shift Registers (LFSR) • Very basic example, 3 bit register Output Bit 1 2 XOR 3 1 0 1 1 1 0 Linear Feedback Shift Registers (LFSR) • bit register – is how long each state of the LFSR is. • Start state – the register is initialized. • Tap positions – the positions in which a new bit is determined and fed back in. • Used in hardware testing • Maximum possible register states is 2 − 1, all possible binary states of length . Linear Feedback Shift Registers (LFSR) Properties of LFSR • Maximal vs. non-maximal length • Cyclic • Non-maximal governed by front two bits. 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 Properties of LFSR • Columns are exact rotations of each other. • If we look at it as a matrix, different “initializations” or start states yield a rotation of the entire matrix. 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 Properties of LFSR • Columns are exact rotations of each other. • If we look at it as a matrix, different “initializations” or start states yield a rotation of the entire matrix. 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 LFSR and Galois Fields • So, how do we find the ‘maximal’ length tap positions? • We look at the number of bits, . • Define = 2−1 + 1, and try to factor this polynomial. • If factors = ⋅ ℎ … () exist, pick exponents of the factors with degree equal to . • Example, = 3. • = 7 + 1 = (x + 1)(x 3 + x 2 + 1)(x 3 + x + 1) • We have two sets of maximal length tap positions: [1,3] and [2,3]. LFSR and Galois Fields • Take = 3, start state [1,0,1] with different tap positions. Left is [2,3] ( 3 + 2 + 1), right is [1,3] ( 3 + + 1). 1 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 LFSR and Galois Fields • So, what do these polynomials that yield the maximal length tap positions correlate to Galois Fields? • When used, it is called the ‘characteristic polynomial’ of the LFSR, and they are all irreducible polynomials over the field (2 ). • Similarly, non-maximal are reducible polynomials. LFSR and Galois Fields • Can reverse the tap positions to get another, identical set of LFSR states. • If the original feedback set is [m, A, B, C], the reversed feedback set is described by [m, m-C, m-B, m-A]. • Easy to find another irreducible polynomial. LFSR and Galois Fields • We can now take this relationship into another cryptographic area, AES. • Quickly generate all elements of 256 for AES, tap positions [8,4,3,1]. • Given the ‘mirror’ or ‘reverse’ image property, we can determine another set of tap positions giving the same elements used in AES: [8,7,5,4]. • 2 / 8 + 4 + 3 + + 1 = 2 / 8 + 7 + 5 + 4 + 1 LFSR and Stream Ciphers • LFSR can be used as a stream cipher. • Remember that stream ciphers are similar to PRNG in that they output a single bit at a time, and data is encrypted bit by bit until the whole plaintext has been encrypted. • A single LFSR as a cipher is vulnerable to due it’s cyclic nature, so we combine multiple LFSR to achieve this. LFSR and Stream Ciphers • First, we define a boolean function. • For example, consider the following diagram. LFSR and Stream Ciphers • We determine beforehand, and give it some boolean function so that it produces the stream cipher output bit, either zero or one. Try to make non-linear. • Example: = 1 ⨁2 … ⨁ LFSR and Stream Ciphers – Correlation Attacks • Since registers are private, they are not independent beings to an attacker, so the whole system must be broken. • Idea: Try to correlate one register to the boolean function, improving a brute force attack. • If it is correlated, it can be broken separately (independent of the system), vastly improving complexity. • More likely than it seems, with enough registers, due to the linear nature of LFSR, some patterns and correlations will appear – linear recursive equations. LFSR and Stream Ciphers – Correlation Attacks • For example, 3 registers, each 16 bits long. • Brute force complexity is 23⋅16 = 248 . • If we have one of the three that is correlated, we now have complexity: 216 + 232 , a savings of 65535. • If two are correlated, complexity becomes: 3 ⋅ 216 , an even larger savings. LFSR and Stream Ciphers – A5/1 • Now we look at a stream cipher that is actually used in the real world – A5/1, used to encrypt over the air data in the GSM standard (Global System for Mobile Communication). • A5/2 is actually a weaker version of A5/1, poses a problem (meant to be secret) – “export regions”. • Over 4 billion customers use devices that use the GSM standard. • A ‘conversation’ is a sequence of frames – sent once every 4.6 milliseconds, so 28 frames a second. LFSR and Stream Ciphers – A5/1 • Use the following LFSR’s of length 19, 21, and 22. • R1 has taps 13,16,17,18 • R2 has taps 20, 21 • R3 has taps 7, 20, 21, 22 LFSR and Stream Ciphers – A5/1 • The protocol to encrypt data between two parties: • C1, C2, and C3 on previous slide are the ‘clock’ bits. A majority function is calculated, and if the bit agrees, the register is clocked. • After some initialization (with (64), (22) and doing no clocking) the LFSR’s are ready to begin producing stream cipher bits. • All 3 LFSR output bits are XOR’d together to produce the cipher output bit. • Each iteration, the majority function is calculated, and registers will be clocked if needed (creating a new state), until all 228 necessary bits are produced for the current frame. Attacks on A5/1 – Known Plaintext • Starting around 2000, people were creating massive preprocessed tables (at least (248 ) steps and requiring 64TB hard drive space) to try to break the cipher. • In the same year, new birthday attack developed. With 248 steps, 300 GB of hard drive space, and 2 minutes of keystream bits, could be recovered in less than a second. • Lookup attacks better getting better, 3TB, only needing 3- 5 minutes of conversation. Attacks on A5/1 – Active Attacks • Barkhan, Biham, and Keller developed the most serious weakness – an active attack with A5/2 – if the phone supports it. They also published another paper in 2006, furthering their attacks and fully breaking A5/1. • A5/3 or KASUMI Future • Algorithms like RC4/5/6 have been developed and avoid the use of LFSR – have their own set of problems. • LFSR are interesting and are good for ‘random’ hardware testing, and if constructed correctly, can be useful in some cryptographic applications. • Note that A5/1’s weaknesses are less about the structure of LFSR and more about the structure of GSM. References • Elad Barkan, Eli Biham, Nathan Keller, Instant Ciphertext- • • • • Only Cryptanalysis of GSM Encrypted Communication, 2003/2006 Patrik Edhal, On LFSR-based Stream Ciphers (PhD), 2003 Alex Biryukov, Adi Shamir, David Wagner, Real Time Cryptanalysis of A5/1 on a PC, 2000 http://www.newwaveinstruments.com/resources/articles/m _sequence_linear_feedback_shift_register_lfsr.htm Thomas Johansson, Fredrik Jonsson, Improved Fast Correlation Attacks on Stream Ciphers via Convolutional Codes, 1999