PS6

215 Secure Communications on the Battlefield? Gary Krahn History For two days in June 1942, the fate of the U.S. Fleet (rebuilt since Pearl Harbor) hung on the meaning of two letters - AF. Between December 1941 and June 1942, the Japanese Navy under the command of Admiral Yamamoto had swept from one victory to another. Yamamoto knew it was essential to achieve victories in rapid succession. Given time, America could starve Japan of fuel. At Midway he would deal the U.S. Fleet a crushing defeat that would put it permanently out of action. On May 20, 1942 Yamamoto broadcast his plans for the final destruction of the U.S. Fleet in a series of orders to his own fleet. At the same time the U.S. Combat Intelligence Unit at Pearl Harbor started to break into the stream of five- digit code groups that concealed the admiral’s intentions. The projected battle began to emerge, however, the when and where remained hidden in mysterious letter groups that defied analysis. The key location was coded: AF. The U.S. crypto unit employed one of the oldest tricks in the book. Using a code that they knew the Japanese had already broken, they arranged for the U.S. Garrison on Midway to broadcast the news that they were short of fresh water. Two days later, Yamamoto broadcasts to his fleet, “AF is short of freshwater.” Admiral Nimitz was now able to get his fleet to Midway and surprise the Japanese. The Americans destroyed all four of the big Japanese aircraft carriers that had attacked Pearl Harbor. As Admiral Nimitz later observed: “Midway was a victory of intelligence.” Introduction On the battlefield we must have the ability to transmit information quickly and securely. Information management is a combat multiplier that is critical to implementing the principals of maneuver, surprise, and initiative on the modern battlefield. Successful military units must be able to send information in a disguised form so that only the intended recipients can remove the disguise and read the message. Whether positioning units, 216 disseminating logistics, or coordinating an attack, secure information is vital for military operations. The Word Cryptography is from the Greek ‘kryptos’ (hidden) and ‘graphein’ (to write). The traditional goal of cryptography has been to ensure privacy in communication by transforming data to render it unintelligible to all but the intended recipient. This can be achieved through the use of an encoding scheme that relies on a secret key known only by the sender and intended recipient. The message we want to send is called the plaintext and the disguised message is called the ciphertext. The message may be formed by using only the familiar symbols A – Z. If we don’t include blanks, however, then all of the words are run together and the messages are harder to read. The process of converting a plaintext to a ciphertext is called enciphering or encryption, and the reverse process is called deciphering. Suppose the information we are to transmit comes from the set of symbols {A, B, C, . . . , Z}. Using binary communications we can associate a sequence of 0’s and 1’s with each of these symbols. For example, A Õ 00000 B Õ 10100 C Õ 00001 D Õ 01010 E Õ 10011 G Õ 11111. Hence, a 10100 00000 01011 sequence represents the message “BAD.” In the hostile environment of the battlefield we want information to remain secret. Furthermore, we want to disguise the message to the enemy; however, we want our friendly units to be able to convert the disguised message into its original form. We can represent this process by the following simple model: Plain Text Channel Cipher Text Plain Text encoder decoder Plain Text CM f¾ ®¾ MC f¾ ®¾ - 1 An enciphering transformation is a function that takes a plaintext message and gives us a ciphertext message. In other words, it is a mapping f from the set M of all possible plaintext messages to the set C of all possible ciphertext messages. We can represent this transformation schematically by the diagram: MCM ¾ ®¾¾ ®¾ - 1ff , where f –1 is the map for deciphering. Exercise 0: If the map (f) is not a one-to-one mapping (or function), what difficulties may the receiver encounter when using the map f –1 during deciphering. 217 Solution: Since the map (f) is not one-to-one then f –1 is not a function and it is possible during deciphering that an enciphered letter is mapped to more than one plaintext letter. Therefore, the receiver may not be able to determine with absolute certainty the actual plaintext message. Modern high-speed communication systems handle information in binary form. To disguise or encipher a binary message during transmission one could randomly change the bits of the message. An efficient technique to encipher is to add, bit by bit modulo 2, a random binary sequence, S, to the message, M, generating a ciphertext. The receiver, also knowing S, can then add S to the ciphertext bit by bit modulo 2 to retrieve the original message, M. This random binary sequence S can not be truly random. It should, however, possess properties associated with a random process. Note: Modulo 2 addition is defined as follows: 1 Å 1 = 0; 1 Å 0 = 1; 0 Å 1 = 1; and 0 Å 0 = 0. Example 1: Suppose M is the message 10100 00000 01011 (representing the word BAD). We define a function f from the message set to the cipher set by f (M) = M Å 10101 01011 01011. In other words, f adds the sequence (or key) S =10101 01011 01011 bit by bit modulo 2 to M to form C. 10100 00000 01011 ( M ) Å 10101 01011 01011 ( S ) 00001 01011 00000 ( C ) The receiver deciphers the ciphertext C by adding the key S modulo 2 to C to recreate the message M. 00001 01011 00000 ( C ) Å 10101 01011 01011 ( S ) 10100 00000 01011 ( M ) If the key, S, is random-looking then the resulting ciphertext, C, tend to be random-like. We may apply the key to many messages throughout some period of operations. Therefore, there is a need for high-speed techniques to generate random-like sequences. One of the simplest and most efficient devices for generating or modeling deterministic, random looking sequences of 0’s and 1’s is the shift-register. The usefulness of sequences generated by a shift-register depends in large part on their randomness properties. In a sense, no finite sequence is truly random. 218 In particular, no sequence that depends on a few parameters, such as the feedback connections of a linear feedback shift-register, can be considered truly random. Solomon W. Golomb introduced the name pseudo-random for periodic binary sequences because they satisfy the three randomness properties of balance, runs, and correlation. We will discuss these properties later. Feedback Shift-Register Design A binary shift-register of span n is a collection {w(i): i = 0,1, . . . , n-1} of n- storage registers each capable of holding a value from the set {0,1}. The contents of the n-storage registers, the n-tuple (sj, sj+1, . . . , sj+n-1), is denoted as the state of the register at time j for each j ³ 0. An example is shown in Figure 1. w0 w1 w2 w3 wn-2 wn-1 1 0 0 1 . . . 1 0 Figure 1: n Storage Devices There is a feedback rule computed from the contents of the n-storage registers called the feedback function (Figure 2). If the feedback function is f (sj, sj + 1, . . . , sj + n - 1) = sj + n = c0sj Å c1sj + 1 Å . . . Å c n – 1 sj + n – 1 = ,0 , 1 0 jsc kj n k k £+ - = å where the coefficients c0, c1, . . . , and c n -1 are 1’s or 0’s, and the summation is modulo 2 addition the shift register is called linear. w0 w1 w2 w3 wn-2 wn-1 1 0 0 1 . . . 1 0 c0 c1 c2 c3 cn-2 cn-1 f (sj, sj + 1, . . . , sj + n - 1) Figure 2: Feedback Shift-Register Model At the pulse of an external clock the content of the storage register wi + 1 is shifted into wi for i =0, 1,. . . , n-2 and the value of the computed feedback function f (sj, sj + 1, . . . , sj + n - 1) is shifted into storage register wn-1. Example 2: Using the above notation, let n = 4, c0 = c1 = 1, c2 = c3 = 0. Thus, sj+4 = sj Å sj+1 modulo 2. The wiring of this linear feedback shift-register (LFSR) is w0 w1 w2 w3 sj sj+1 sj+2 sj+3 sj+4 = sj Å sj+1 219 Figure 3: A Linear Feedback Shift-Register Model Note: the connections from sj+2 and sj+3 are open since c2 = 0 and c3 = 0. Successive iterations from the initial configuration in Figure 3 look like: w0 w1 w2 w3 s0 s1 s2 s3 TICK OF THE CLOCK w0 w1 w2 w3 s1 s2 s3 s4 TICK OF THE CLOCK w0 w1 w2 w3 s2 s3 s4 s5 The successor of the register fill vector s0, s1, . . . , sn-1 is the vector s1, s2, . . . , sn, where the value sn is the computed feedback function f (s0, s1, . . . , sn-1). To generate successive states we iterate this procedure. With each tick of the clock, the register completes another step through a sequence of states. If we set the initial fill of the register to be 0001, such that s0 = 0, s1= 0, s2 = 0, and s3 = 1, then the successive states of the register are: 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0 1 For this example, the state sequence of register fills repeats with a period of 15. The history of stage w3, which is underlined, is the sequence {100110101111000}, periodically repeated. If the contents of the register are initially not all 0’s, the linear shift-register will cycle through all 15 different states before repeating itself. In general, it is possible to construct a span n linear 220 shift-register of the form in Figure 2 that will cycle through all 2n-1 different states before repeating itself for every n ³ 1. Associated with each linear feedback shift-register (LFSR) is the characteristic polynomial j n j j n xcxxfxC å - = +== 1 0 )()( . In Example 2 the characteristic polynomial is .14 ++ xx Exercise 1: Explain why any linear shift-register of span n will generate a sequence that is ultimately periodic with a period p £ 2n -1. (Sequences being the history of a selected storage register.) Solution: Each state of the shift register is completely determined by the previous state and the feedback function. Since there are only a finite number of states, some state must eventually repeat. Working with n-stage shift registers with 0’s and 1’s, the size of the possible state set is 2n . The linearity of the feedback function guarantees that the all zero state is always its own successor. Therefore, the longest possible shift register cycle contains all of the nonzero states, and is periodic of period 2n –1. A sequence generated by a linear feedback shift-register of span n having a period 2n –1 is called a maximum length linear shift register sequence or more simply an m-sequence. Exercise 2: Construct the LFSR with the characteristic polynomial .13 +x Furthermore, if the initial state of this shift-register is 001, write the periodic sequence that it generates. Solution: : Using the above notation, let n = 3, c0 = 1, c2 = 0. Thus, sj+3 = sj modulo 2. The wiring of this LFSR is as follows: w0 w1 w2 sj sj+1 sj+2 sj+3 = sj The sequence is 100 of period 3. This LFSR does not generate an m-sequence of length 7. 221 Exercise 3: Construct the LFSR with the characteristic polynomial .13 ++ xx Furthermore, if the initial state of the shift-register is 001, write the periodic sequence that is generated. Solution: Using the above notation, let n = 3, c0 = 1, c2 = 1. Thus, sj+3 = sj Å sj+1 modulo 2. The wiring of this LFSR is as follows: w0 w1 w2 sj sj+1 sj+2 sj+3 = sj Å sj+1 The sequence is 1011100 of period 7. This LFSR does generate an m-sequence of length 7. Randomness Properties of m-sequences The usefulness of m-sequences depends in large part on their having nearly ideal randomness properties. The randomness properties that we would like a sequence to have are given below. The Balance Property: In a sequence the number of ONEs is the same as the number of ZEROs. The Run Property: Among the runs of ONEs and ZEROs in a sequence, one-half the runs are of length one, one-fourth are of length two, one-eighth are of length three, and so on, as long as these fractions give meaningful number of runs. The Correlation Property: When a sequence is compared term–by–term with a cyclically shifted version of the same sequence, the number of agreements equals the number of disagreements. We will discover that m-sequences satisfy the above randomness properties as closely as possible for each period of the sequence. Exercise 3: Given that every non-zero n-tuple is seen as a state within a LFSR exactly once during the generation of an m-sequence, explain why the balance property holds for every m-sequence. In particular, there are 2n-1 ONEs and 2n-1 –1 ZEROs in an m-sequence of length 2n –1. Solution: An n stage shift-register generating an m-sequence cycles through all 2n –1 states before it repeats. In decimal notation, each state can be thought of representing an integer from 1 to 2n –1. From 1 to 2n –1 there are 2n-1 odd integers and 2n-1 even integers. Thus, an 222 m-sequence contains 2n-1 ONEs and 2n-1 –1 ZEROs and will therefore always possess the balance property. Example 3: Given below is an m-sequence of length 63 generated from a span n = 6 LFSR. Marked on the sequence are the runs of length greater than 2. 54 2 32 4 3 3 22 232 2 26 000001000011000101001111100001110010001110111011001101010111111 Exercise 4: In Example 3 there are a total of 32 runs, including the singleton runs. One half of the runs (16) are of length one, one fourth (8) are of length two, one eighth (4) are of length three, and one sixteenth (2) are of length four. For each of these lengths there are equally many runs of ZEROs and ONEs. Finally, there is one run of five consecutive ZEROs and one of six consecutive ONEs. Explain why the run property holds for all m-sequences. Solution: In an m-sequence of period 2n –1, every non-zero n-tuple occurs exactly once. If the n-tuple 000… 0 occurs, the sequence will remain forever in the state 000… 0 . Therefore, the n-tuple, 000… 0, nevers occurs in an m-sequence. Since every non-zero n-tuple occurs, the n-tuple 111… 1 must occur exactly once with a zero preceding and following this all ONE n-tuple. The (n+2)-tuple, 011… 10, contains the n-tuples [011… 1]10 and 01[1… 110]. These n-tuples are not repeated elsewhere in the sequence. Hence, there can be no run of n-1 ONEs in the sequence. However, there is exactly one run of length n-1 of ZEROs, represented in the consecutive n-tuple 10… 00 and 00… 01. Now consider the runs of ONEs and length r where 20 -£< nr . Each such run can be made to correspond to n-tuples of the type 2 . . . 01 . . . 110 -- rnr xxx where the x’s are arbitrary bits. The number of such n-tuples of run length r is 2n-r-2. A similar argument gives the same number of runs of ZEROs of length r. This completely determines the run structure of m-sequences. Experiment: Compare an m-sequence {si} with a cyclic shift of itself. This comparison is called autocorrelation. Suppose an m-sequence is added to itself bit by bit using modulo 2 addition. When the sequence is added in phase with itself, we get the null sequence. When the sequence is added to each out of phase shift of the sequence a miracle occurs. What is this miracle? Explain. Do m-sequences have the correlation property? Explain. 223 Solution: When the sequence is added to each out of phase shift of the sequence, the resulting sequence is a non-zero sequence that is a shifted version of the original sequence. This property is known as the Shift-and-Add property. For example, 1011100, denoted by {si}, is an m-sequence. Let {si+1} denoted the sequence {si} shifted to the left by one bit. We find that {si+1} = 0111001. When {si+1} and {si} are added modular 2 (bit by bit) the resulting sequence is 1100101. A (1) in the resulting sequence means that {si+1} and {si} disagreed in that position while a (0) means that {si+1} and {si} agreed in that position. Since the resulting sequence is an m-sequence it follows that the number of agreements and disagreements between an m-sequence and a shifted version of the same m-sequence are just about equal. Hence, m-sequences possess the correlation property. Examples of the shift-and-add property are given below: s0 1011100 s0 1011100 s0 1011100 s1 Å 0111001 s2 Å 1110010 s4 Å 1001011 s3 1100101 s6 0101110 s5 0010111 We say that the shift-and-add pairs for the sequence 1011100 are (1,3), (2,6), and (4,5), e.g., the sequence 1011100 added modulo 2 to a shifted (by 3) version of itself produces a shifted (by 1) version of itself. Because m-sequences satisfy the three randomness properties they are sometimes referred to as pseudo-random or pseudo-noise sequences. Moreover, m-sequences are the only deterministic sequences that have the randomness properties and distinct n-tuples in each period of length 2n –1. Exercise 5: Let us say a segment from an unknown m-sequence (S) is added to a shifted (by 3) version of itself: (S) 101011101100. . .0111110011 Unknown m-sequence (S3) Å 011101100011. . .1110011010 shift of 3 (S5) 110110001111. . .1001101001 shift of 5 We can see that (3,5) is a shift and add pair for the sequence (S). Furthermore, the sum S Å S3 Å S5 = 000. . . 0000, the all zero sequence. (S) 101011101100. . .0111110011 Unknown m-sequence (S3) 011101100011. . .1110011010 shift of 3 (S5) Å 110110001111. . .1001101001 shift of 5 000000000000000000000000 SUM 224 What if the unknown m-sequence (S) was copied by a person who on the average made 10% errors in the sequence at random as she records the sequence (S’) from a digital communication network. The mod 2 sum of (S’) and the sequence of shifts of 3 and 5, i.e., S’ Å S’3 Å S’5 = S would no longer be the zero sequence. In fact, it would give us a sequence (S) with some percentage of ones. How would you estimate the density of ones in (S) if (3,5) was truly a shift-and-ad