Ensuring Diverse Public Broadcasting Discussion
Mission to represent marginalized voices in the debate dominated by commercial interests. Public Service Broadcasting (PSB) defined as high-quality, impartial news and content for all audiences. BBC, Channel 4, ITV, and Five each play a unique role in fulfilling the purposes and remits of public service broadcasting, promoting citizenship, education, creativity, and societal cohesion. Central to this is the importance of an engaged population, independent journalism, social cohesion, and raising awareness of critical issues for employability and education.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Linear Feedback Shift Register (LFSR) and how they are used for stream ciphers
K = a,b K = a,b LCG LCG y4, y3, y2, y1, y0 x4, x3, x2, x1, x0 x4, x3, x2, x1, x0 What s in here?
Linear feedback shift registers Si Generate the Has to be small/cheap ? ? k k low power usage Si Si Xi Yi Xi Xi Yi Si - the clear text bits Q: What is the ? ? A: LFSR - the cipher text bits - the key bits
The A5/1 stream cipher in cell phones https://en.wikipedia.org/wiki/A5/1 It was initially kept secret, but became public knowledge through leaks and reverse engineering Uses 3 LFSR s
A5/1 A5/1 is a stream cipher used to provide over-the-air communication privacy in the GSM cellular telephone standard. It is one of seven algorithms which were specified for GSM use. It was initially kept secret, but became public knowledge through leaks and reverse engineering. A number of serious weaknesses in the cipher have been identified. A5/1 is used in Europe and the United States. A5/2 was a deliberate weakening of the algorithm for certain export regions. .. In 2000, around 130 million GSM customers relied on A5/1 to protect the confidentiality of their voice communications; by 2011, it was 4 billion. https://www.independent.co.uk/life-style/gadgets-and- tech/news/there-are-officially-more-mobile-devices-than- people-in-the-world-9780518.html Wikipedia entry, A5/1
This is an xor gate LFSR a series of flip-flops with feedback loops Output: (not clocked) Si 0 1 0 0 S0 = 0 Flip-flop holds: 1 0 0 (Starting values are agreed upon a priori) each square is a flip flop which holds 1 bit input on the left, output on the right each time the clock ticks, they shift right one flip flop (hence shift register )
LFSR a series of flip-flops with feedback loops (not clocked) Output: Si 0 1 0 0 S0 = 0 clock The starting FF values are set at 100. The xor gate has 00 as inputs hence it has an output of 0 Flip-flop holds: 1 0 0 (Starting values are agreed upon a priori)
LFSR a series of flip-flops with feedback loops (not clocked) Output: Si 0 1 0 0 S0 = 0 clock Think of these as continuous and fixed. When the clock goes high FF s look at their inputs & generate new outputs Flip-flop holds: 1 0 0 (Starting values are agreed upon a priori)
(not clocked) 0 1 0 0 So when the clock goes high, the bit on their input is the bit they next hold (These are D FlipFlops)
(not clocked) 0 1 0 0 FF0 FF1 FF2 Hence, each clock tick causes the bits to right shift one place
LFSR a series of flip-flops with feedback loops Output: (not clocked) Si 1 S0 = 0 S1 = 0 0 1 0 FF0 FF2 FF1 Flip-flop holds: 1 0 0 clk 0 1 0 0 0 after the clock tick, FF0 became what FF1 was FF1 became what FF2 was FF2 became 0 since that was its input when the clock ticked
LFSR a series of flip-flops with feedback loops Output: (not clocked) Si 1 0 1 0 S0 = 0 FF0 FF2 FF1 Flip-flop holds: 1 0 0 clk 0 1 0 0 0 FF2 is now FF1 xor FF0 Remember we started with 1 0 0
(not clocked) 1 0 1 0 FF0 FF2 FF1 Si Flip-flop holds: 1 0 0 clk 0 1 0 0 0 What happen after the next clock tick?
(not clocked) 1 1 0 1 FF0 FF2 FF1 Si Flip-flop holds: 1 0 0 clk 0 1 0 1 0 1 1 0 0 Keep going What is the next Si? When does it stop? How many unique FF patterns can there be?
(not clocked) 1 1 0 1 FF0 FF2 FF1 Si Flip-flop holds: 1 0 0 clk 0 1 0 1 0 1 1 0 0 What happen after the next clock tick?
Mathematically speaking: Output: (not clocked) Si 0 1 0 0 S0 = 0 ) S0 ) S3 =( S1 mod 2 or ( + S3 S1 S0 = ( ) Consider this until it is clear why S4 S5 S2 S4 S1 S3 = ( ) = ( )
LFSR a series of flip-flops with feedback loops Output: (not clocked) Si 0 1 0 0 S0 = 0 Flip-flop holds: 1 0 0 Why is there an XOR gate here but not here?
Max period is not guaranteed under all xor combinations so let s generalize so any FF may participate in the feedback: f1 f0 ffm-1 p1 Pm-1 p0 Sm-1 s1 s0
Max period is not guaranteed under all xor combinations so let s generalize so any FF may participate in the feedback: f1 f0 ffm-1 p1 Pm-1 p0 Sm-1 s1 s0 Think of the Pi as on/off switches
Max period was 7, but wed like >>7 Luckily, the max period is (2**m) - 1 where m == number of flip flops So we can get a very large max period without an insane number of FF s e.g. 32 flip flops gives us a max period of > 4 billion f1 f0 ffm-1 p1 Pm-1 p0 s1 s0 Sm-1 Arbitrary number of flip-flops, arbitrary choice for feedback
Luckily, the max period is (2**m) - 1 where m == number of flip flops So we can get a very large max period without an insane number of FF s e.g. 32 flip flops gives us a max period of > 4 billion. How many do we need? How many do we need? Remember, we re using them for key bits so we need one per each bit of voice Bits/sample * sample/second * seconds/call == bits/call LCG LCG y4, y3, y2, y1, y0 x4, x3, x2, x1, x0 x4, x3, x2, x1, x0
Bits/sample * sample/second * seconds/call == bits/call Some data points: Skype: 16 bits/sample; 16,000 samples/second AMR: 4.75 ---- 7.4 ----- 12.2 kbits/sec CD: 44,100 samples/second LCG LCG y4, y3, y2, y1, y0 x4, x3, x2, x1, x0 x4, x3, x2, x1, x0
f1 f0 ffm-1 p1 Pm-1 p0 Sm-1 s1 s0 si pi Starting values for flip-flops Vector of choices for open/closed (feedback, or not?) Set by the standard
f1 f0 ffm-1 p1 Pm-1 p0 s1 s0 Sm-1 S0 P0 S1 P1 Pm-1 + Sm-2 Pm-2 + Sm-1 Sm + + S1 P0 S2 P1 + Sm-1 Pm-2 Pm-1 + Sm + + Sm+1 i+j Pj Sm+i
A5/1: the "original" un-weakened GSM encryption algorithm A5/2: the "export variant" weakened version of A5/1 A5/3: KASUMI, in use in 3G networks, stronger than A5/1 A5/4: SNOW 3G, in use in 4G LTE networks
complexity story GSM vs CDMA 3 lfsr s majority rule clocking several attacks https://en.wikipedia.org/wiki/A5/1 https://yro.slashdot.org/story/13/12/14/0148251/nsa-able-to-crack-a51-cellphone-crypto
