1 Background Data: Naval Warfare, Battle of the Atlantic, Cryptography, and the Code Game Randy H. Katz CS Division, EECS Dept. University of California, Berkeley Spring 2009 Battle of the Atlantic Allied Convoys vs. German U-Boats • Germans on the Offensive, Allies on the Defensive – Choosing Targets – Assembling Forces – Finding the Enemy – Attacking with Precision or Causing As Much Damage as Possible – Avoiding/Surviving Defenders – Determining the Effects of Naval Combat2 Battle of the Atlantic Allied Convoys vs. German U-Boats • Allies on the Offensive, Germans on the Defensive – Choosing Targets – Assembling Forces – Finding the Enemy – Attacking with Precision or Causing As Much Damage as Possible – Avoiding/Surviving Defenders – Determining the Effects of Naval Combat3 Convoys “Das Boot”4 Naval Intelligence Finding 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 with the 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 at Midway • Technology and the Battle of the Atlantic – Airborne Radars, High Frequency Direction Finding Signals Intelligence • Collecting information about a (potential) foe's capabilities (economic, military) and intentions (political, military) as old as nations themselves! • New about the late 19th and 20th Centuries: – Rise of far-flung empires, increasing use of technologies for communications, need for command and control5 Development of Communications Technology • Commercial = Militarily Relevant Technologies – Electric Telegraph (1837) – Undersea Cables (1842); transatlantic cable (1866) – Transcontinental Telegraph (1861); crucial role in American Civil War – Marconi, Radio (1895): first customer--the Royal Navy! • Counter measures: cut foe's undersea cables, message interception, 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 to individual and location? – Can the interceptor be fooled? traffic analysis and deception? – Can the communicator be stopped from successfully communicating? jamming? – Can the communicator hide his/her communications? stealth?6 Intelligence Collection • Spying, reconnaissance, spy satellites, code breaking • Human intelligence (HUMINT) aka spies • Signal intelligence (SIGINT)/Communications intelligence (COMINT) often used interchangeable, especially up through WWII – Modern militaries use many forms of electromagnetic radiation that don't involve communications, but are used for detection (e.g., RADAR) – Information derived from the monitoring, interception, decryption and evaluation of enemy radio communications – Naval intelligence particularly important, as until the development of recon satellites, the ability to put "eyes" at sea was very limited! Codebreaking • Before the Age of Radio, much more difficult to intercept cable traffic • Radio potentially places large numbers of encrypted messages in the hands of the cryptanalysts – Key to breaking the code! – British Admiralty Room 40: Codebreaking Room7 Enigma Machine • Existence of ULTRA ("Very Special Intelligence") first revealed in 1974! Changed completely the way we view the history 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: doubly encrypted message keys • Poles reverse engineer a stolen Enigma machine • Invention of the Bombe: mechanical device to exhaust all enumerations • New Enigma stumps the Poles who turn to the British (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!8 “Enigma” Enigma Deciphered9 The Bombe Colossus The Code Game % Letter Occurrence in English Text a 7.49 b 1.29 c 3.54 d 3.62 e 14.00 f 2.18 g 1.74 h 4.22 i 6.65 j 0.27 k 0.47 l 3.57 m 3.39 n 6.74 o 7.37 p 2.43 q 0.26 r 6.14 s 6.95 t 9.85 u 3.00 v 1.16 w 1.69 x 0.28 y 1.64 z 0.0410 The Code Game More Text Analysis • Common Digrams: – th he at st an in ea nd er en re nt to es on ed is ti • Common Trigrams: – the and tha hat ent ion for tio has edt tis ers res ter con ing men tho • Double Letters: – ll tt ss ee pp oo rr ff cc dd nn • Common word ending letters: – e t s d n r y • Most common words: – the of are I and you a can to he her that in was is has it him