Secure Communications ontheBattlefield?GaryKrahnHistoryFor two days in June 1942, the fate of the U.S.Fleet (rebuilt since Pearl Harbor)hungonthemeaningoftwoletters-AF.BetweenDecember1941andJune1942,theJapaneseNavyunderthecommandofAdmiralYamamotohadsweptfromonevictorytoanother.Yamamotoknewit was essentialtoachievevictoriesinrapidsuccession.Giventime,Americacould starveJapanoffuel.At Midway he would deal the U.S.Fleet a crushing defeatthat would put itpermanently out of action.OnMay20,1942Yamamotobroadcasthisplansforthefinal destructionof theU.S.Fleet in a series of orders to his own fleet.At the same time the U.S.Combat IntelligenceUnit atPearlHarbor startedtobreak intothestreamoffive-digitcodegroupsthatconcealedtheadmiral'sintentions.Theprojectedbattlebegan to emerge, however, the when and where remained hidden in mysteriouslettergroups that defied analysis.Thekey location was coded:AF.TheU.S.cryptounitemployed oneof theoldesttricks inthebook.Usinga codethattheyknewthe Japanesehad alreadybroken,theyarranged fortheU.sGarrison on Midwayto broadcast the news that they wereshortoffresh water.Two days later, Yamamoto broadcasts to his fleet,"AF is short of freshwater.AdmiralNimitzwasnowabletogethisfleettoMidwayand surprisetheJapanese.TheAmericans destroyed all fourofthebig JapaneseaircraftcarriersthathadattackedPearlHarbor.AsAdmiralNimitzlaterobserved"Midwaywasa victory of intelligence."IntroductionOnthebattlefield wemusthavetheabilitytotransmitinformationquicklyandsecurely.Information managementis acombat multiplier that is critical toimplementingtheprincipalsofmaneuversurprise,andinitiativeonthemodernbattlefield.Successfulmilitaryunitsmustbeableto sendinformation ina disguisedform sothat only the intended recipientscanremovethedisguiseandreadthemessage.Whetherpositioning units,215
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 fivedigit 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
disseminatinglogistics,or coordinatingan attack,secure information isvital formilitaryoperations.TheWord Cryptographyis fromthe Greek‘kryptos(hidden)and'graphein'(towrite).Thetraditionalgoalofcryptographyhasbeentoensureprivacyincommunication by transforming data to render it unintelligible to all but theintended recipient.This can be achieved through the use of an encodingschemethatreliesona secretkeyknownonlybythe senderand intendedrecipient.Themessagewewanttosendiscalledtheplaintextandthedisguisedmessage iscalledtheciphertext.Themessagemaybeformedbyusing onlythefamiliarsymbolsA-Z.If wedon't includeblanks,however,thenall of the words are run together and the messages are harderto read.Theprocess of converting a plaintext to a ciphertextis called enciphering orencryption,andthereverseprocess is calleddeciphering.Supposetheinformationwearetotransmitcomesfromthesetofsymbols(A,B,C,...,Z)Usingbinarycommunicationswecanassociatea sequenceof O'sand1'switheachofthesesymbols.Forexample,A→00000B→ 10100C→00001D→ 01010E→10011G→ 11111.Hence,a101000000001011sequencerepresentsthemessage"BAD."Inthehostile environment of thebattlefieldwe want informationto remainsecret.Furthermore,wewanttodisguisethemessagetotheenemy;however,wewantour friendly units to beable to convert the disguised message into its originalform. We can represent this process by the following simple model:PlainTextChannelCipher TextPlainTextencoderdecoderPlainTextTMMCCAn enciphering transformation is a function that takes aplaintext message andgivesusaciphertextmessage.Inotherwords,itisamappingf fromthesetMofall possibleplaintext messages tothe set c of all possible ciphertextmessages.We can representthistransformation schematicallybythe diagram:Mc→M,where f-1 is the map for deciphering.Exercise O: If the map (f)is nota one-to-onemapping (or function),whatdifficulties may the receiver encounter when using the map f-1 duringdeciphering.216
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 M C f ¾¾ ® C M 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: M ¾¾ ® C ¾ ¾ ® M - 1 f f , 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
Solution: Since the map (f) is not one-to-one then f-1is not a functionanditispossibleduringdecipheringthatanencipheredletterismappedtomorethanoneplaintext letter.Therefore,thereceivermaynotbeabletodeterminewithabsolutecertaintytheactual plaintextmessage.Modernhigh-speed communication systems handleinformation inbinaryform.Todisguiseorencipherabinarymessageduringtransmissiononecouldrandomlychangethebitsofthemessage.Anefficienttechnique to encipher is to add, bit by bit modulo 2, arandom binary sequence,S, to themessage,M,generating a ciphertext. The receiver,also knowingS, can then add S to the ciphertext bit by bit modulo 2toretrievetheoriginalmessage,M.This randombinarysequenceScannotbetrulyrandom.It should,however,possesspropertiesassociatedwitharandomprocess.Note:Modulo2additionisdefinedasfollows:1@1=0:1@0=1:0 01 =1; and 0 0 = 0.Example1:Supp0seMisthemessage101000000001011(representingtheword BAD).We definea functionf fromthemessagesettothe ciphersetbyf(M)=M101010101101011.Inotherwords,f addsthesequence(orkey)S=101010101101011bitbybitmodulo2toMtoformC(M)101000000001011(s)④101010101101011(c)000010101100000ThereceiverdecipherstheciphertextCbyaddingthekey Smodulo2to ctorecreatethemessageM.(c)000010101100000(s)④101010101101011101000000001011(M)If the key, S, is random-looking then the resulting ciphertext, C, tend to berandom-like.Wemayapplythekeytomanymessagesthroughout someperiodofoperations.Therefore,there isa need forhigh-speed techniques togeneraterandom-likesequences.Oneof thesimplestandmostefficientdevicesforgenerating or modeling deterministic,randomlooking sequencesof o0's and 1'sis the shift-register.Theusefulnessofsequencesgeneratedbyashift-registerdepends inlargepartontheir randomness properties.In a sense,no finitesequence istrulyrandom.217
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
In particular, no sequence that depends on a few parameters, such as thefeedbackconnectionsofa linearfeedbackshift-register,canbeconsideredtrulyrandom.SolomonW.Golombintroducedthenamepseudo-randomforperiodicbinarysequencesbecausetheysatisfythethreerandomnesspropertiesofbalance,runs,andcorrelation.Wewilldiscussthesepropertieslater.FeedbackShift-RegisterDesignAbinaryshift-registerof spann isa collection(w():i=o,1,...,n-1)ofn-storageregisters eachcapableof holding a valuefromthe set(0,1).Thecontentsofthen-storage registers, the n-tuple (s, Sj+1, .:, Sj+n-1), is denoted as the state of theregister at time j for each j≥ 0. An example is shown in Figure 1.WiWo02Figurel:nStorageDevicesThereisafeedbackrulecomputedfromthecontentsofthen-storageregisterscalledthefeedbackfunction(Figure2).If thefeedbackfunction isf(Sj, Sj+1, .., Sj+n-1) = Sj+n= CoS,@ CiSj+1@... Cn-1 Sj+n-1=Zesat,O≤j,k=0where the coefficients co, C1, .,and c n-1 are 1's or O's, and the summation ismodulo2additionthe shift registeris called linear.WiWoW2W3Wn-2Wnr-10：00工1Ic3coIciIc2ICn-2Cn-1f(s, Sj+1 .++, S+n-1)Figure2:FeedbackShift-RegisterModelAtthepulseofanexternal clockthecontentofthestorageregisterWi+isshiftedintowifori=0,1,..:,n-2andthevalueofthecomputedfeedbackfunctionf (sj, Sj+1, :..,Sj+n-1) is shifted into storage register Wn-1.Example2:Usingtheabovenotation,letn=4,Co=C=1,C2=C3=0.Thus,S+4=s, Sj+1 modulo 2.The wiring of this linear feedback shift-register (LFSR) isWoWW2W[sjS卜H Sj+2 I Sj+3S-4= s,@ S+1218
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 nstorage 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 c s j j k 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
Figure3:ALinearFeedbackShift-RegisterModelNote:theconnectionsfromSi+2andSi+3areopensinceC,=0andC=0.Successiveiterations fromthe initial configuration inFigure3look like:WoW1W3W2SoS1S2S3TICKOFTHECLOCKWoWiW2W3S2S1S3S4TICKOFTHECLOCKwoWiW2W3S2S3S4SsThesuccessoroftheregisterfillvectorSo,S1,...,Sn-1isthevector.S,S2,..,Sn,wherethevalueSnisthecomputedfeedbackfunctionf(so,S1,..:,Sn-1).TogeneratesuccessivestatesweiteratethisprocedureWitheachtickoftheclock,theregistercompletesanotherstepthroughasequence of states.If we set the initial fll of the register to be 0001,such thatSo=0, si=0, S2=0, and s3= 1, then the successive states of the register are:00010I010100l10011001001111011010001110110111111110I11101000100001Forthisexample,thestatesequenceofregisterfillsrepeatswithaperiodof15The history ofstage w3,whichis underlined, is the sequence(100110101111000),periodicallyrepeated.IfthecontentsoftheregisterareinitiallynotallO's,thelinearshift-registerwillcyclethroughall15differentstatesbefore repeating itself. Ingeneral, it is possibleto constructa span n linear219
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