Background Data:Naval Warfare,Battle of the Atlantic,Cryptography, and the Code GameRandy H. KatzCS Division, EECS Dept.University of California, BerkeleySpring 2008Battle of the AtlanticAllied Convoys vs. German U-Boats• Germans on the Offensive, Allies on theDefensive– Choosing Targets– Assembling Forces– Finding the Enemy– Attacking with Precision or Causing As MuchDamage as Possible– Avoiding/Surviving Defenders– Determining the Effects of Naval CombatBattle of the AtlanticAllied Convoys vs. German U-Boats• Allies on the Offensive, Germans on theDefensive– Choosing Targets– Assembling Forces– Finding the Enemy– Attacking with Precision or Causing As MuchDamage as Possible– Avoiding/Surviving Defenders– Determining the Effects of Naval CombatConvoys“Das Boot”Naval IntelligenceFinding the Enemy, Hiding Your Forces• Is an "unbreakable" code possible?• Is it possible to "hide" coded transmissions?• How do you balance the need to communicate withthe need to be invisible to easedropping?• Cryptography, Cryptanalysis– Heroic Codebreaking: Enigma, the Battle of the Atlantic,and the Development of the Computer– Codebreaking in the Pacific: Intelligence successes atMidway• Technology and the Battle of the Atlantic– Airborne Radars, High Frequency Direction FindingSignals Intelligence• Collecting information about a (potential)foe's capabilities (economic, military) andintentions (political, military) as old asnations themselves!• New about the late 19th and 20thCenturies:– Rise of far-flung empires, increasing use oftechnologies for communications, need forcommand and controlDevelopment ofCommunications Technology• Commercial = Militarily Relevant Technologies– Electric Telegraph (1837)– Undersea Cables (1842); transatlantic cable (1866)– Transcontinental Telegraph (1861); crucial role in American CivilWar– Marconi, Radio (1895): first customer--the Royal Navy!• Counter measures: cut foe's undersea cables, messageinterception, message deception;• Counter counter measure: radio communications• Counter counter counter measure: jamming, direction finding• Every measure has a counter measure, and in turn, a counter-counter measure!To Communicate is to Reveal• Communication methods lead to detection– Can the detector be detected? identified as toindividual and location?– Can the interceptor be fooled? traffic analysisand deception?– Can the communicator be stopped fromsuccessfully communicating? jamming?– Can the communicator hide his/hercommunications? stealth?Intelligence Collection• Spying, reconnaissance, spy satellites, code breaking• Human intelligence (HUMINT) aka spies• Signal intelligence (SIGINT)/Communicationsintelligence (COMINT) often used interchangeable,especially up through WWII– Modern militaries use many forms of electromagneticradiation that don't involve communications, but are usedfor detection (e.g., RADAR)– Information derived from the monitoring, interception,decryption and evaluation of enemy radio communications– Naval intelligence particularly important, as until thedevelopment of recon satellites, the ability to put "eyes" atsea was very limited!Codebreaking• Before the Age of Radio, much moredifficult to intercept cable traffic• Radio potentially places large numbersof encrypted messages in the handsof the cryptanalysts– Key to breaking the code!– British Admiralty Room 40:Codebreaking RoomEnigma Machine• Existence of ULTRA ("Very SpecialIntelligence") first revealed in 1974!Changed completely the way we view thehistory of WW II• Combined encoding/decoding machine– Five rotor system, three in use at any time– How it worked and why it was hard to crack• Use of per message keys makes analysis difficult• But patterns provide the way in: doublyencrypted message keys• Poles reverse engineer a stolen Enigma machine• Invention of the Bombe: mechanical device toexhaust all enumerations• New Enigma stumps the Poles who turn to theBritish (1939)Bletchley Park• Guessing the day key: cillies—common three letter sequences• Human operator weakness!• Rules of usage also limit the alternatives• Stereotypical message structure helps too• Turing’s idea: the crib--<common plain text, encrypted text>• If found, then could determine Enigma settings• Compute the transformation in parallel: Turing’s Bombe• 10 May 40: Germans change their message key scheme• Naval codes hardest to break—more sophisticated Enigma used• Battle of Atlantic was being lost! Solution: pinch the codebooks!“Enigma”Enigma DecipheredThe BombeColossusThe Code Game% Letter Occurrence in English Texta 7.49b 1.29c 3.54d 3.62e 14.00f 2.18g 1.74h 4.22i 6.65j 0.27k 0.47l 3.57m 3.39n 6.74o 7.37p 2.43q 0.26r 6.14s 6.95t 9.85u 3.00v 1.16w 1.69x 0.28y 1.64z 0.04The Code GameMore Text Analysis• Common Digrams:– th he at st an in ea nder en re nt to es on edis ti• Common Trigrams:– the and tha hat ent ionfor tio has edt tis ersres ter con ing men tho• Double Letters:– ll tt ss ee pp oo rr ff ccdd nn• Common word endingletters:– e t s d n r y• Most common words:– the of are I and you acan to he her that inwas is has it him hisNext WeekMissiles and the Cuban Missile Crisis• See class web page for readings:– Ballistic Missile Defense• http://www.missilethreat.com/overview/– Cuban Missile Crisis• http://www.gwu.edu/~nsarchiv/nsa/cuba_mis_cri/– 14 Days in October Web Site•