{"id":2399,"date":"2014-11-25T02:20:47","date_gmt":"2014-11-25T02:20:47","guid":{"rendered":"http:\/\/www.lifeandnews.com\/articles\/?p=2399"},"modified":"2016-08-08T04:57:44","modified_gmt":"2016-08-08T04:57:44","slug":"codebreaking-has-moved-on-since-turings-day-with-dangerous-implications","status":"publish","type":"post","link":"https:\/\/www.lifeandnews.com\/articles\/codebreaking-has-moved-on-since-turings-day-with-dangerous-implications\/","title":{"rendered":"Codebreaking has moved on since Turing&#8217;s day, with dangerous implications"},"content":{"rendered":"<p>By <a href=\"http:\/\/theconversation.com\/profiles\/bill-buchanan-124357\">Bill Buchanan<\/a><em>, Edinburgh Napier University <\/em><\/p>\n<p>We have always been been intrigued by keeping secrets and uncovering the secrets of others, whether that\u2019s childhood secret messages, or secrets and codebreaking of national importance.<\/p>\n<p>With a film, <a href=\"http:\/\/www.theguardian.com\/film\/2014\/nov\/20\/the-imitation-game-invents-new-slander-to-insult-alan-turing-reel-history\">The Imitation Game<\/a>, reprising the life of <a href=\"http:\/\/www.turingarchive.org\/\">Alan Turing<\/a> and his role in breaking the Nazi\u2019s Enigma cipher of World War II, how does one codebreak, then and now?<\/p>\n<h2>It\u2019s all in the cipher<\/h2>\n<p>Imagine that Bob and Alice wish to secretly communicate, and Eve, who wishes to listen in. Here \u201cplain text\u201d refers to the original message, and \u201ccipher text\u201d as the coded message.<\/p>\n<figure class=\"align-center zoomable\"><a href=\"https:\/\/62e528761d0685343e1c-f3d1b99a743ffa4142d9d7f1978d9686.ssl.cf2.rackcdn.com\/files\/65105\/area14mp\/image-20141120-4487-1u6kp1d.png\"><img src=\"https:\/\/62e528761d0685343e1c-f3d1b99a743ffa4142d9d7f1978d9686.ssl.cf2.rackcdn.com\/files\/65105\/width668\/image-20141120-4487-1u6kp1d.png\" alt=\"\" \/><\/a><\/figure>\n<p><span class=\"caption\">Secret messaging, ciphers, and those listening in.<\/span><br \/>\n<span class=\"attribution\"><span class=\"source\">Bill Buchanan<\/span>, <span class=\"license\">Author provided<\/span><\/span><\/p>\n<p>There are two ways of creating the cipher text:<\/p>\n<ul>\n<li>Having an algorithm (a cipher) that only Bob and Alice know, so that one applies the cipher to encode the text and the other applies the cipher in reverse to decode.<\/li>\n<li>Using a well-defined algorithm, but adding something that changes the way it operates which is easy for Bob and Alice to convert, but difficult for Eve to find.<\/li>\n<\/ul>\n<p>In the first case, to read their messages Eve will have to crack the cipher \u2013 to work out what method it uses to change plain text to cipher text. For example, the famous <a href=\"http:\/\/practicalcryptography.com\/ciphers\/caesar-cipher\/\">Julius Caesar cipher<\/a> is a form of <a href=\"http:\/\/www.cimt.plymouth.ac.uk\/resources\/codes\/codes_u1_text.pdf\">substitution cipher<\/a> that shifts letters in the alphabet a number of places, for example a shift of 13 means A becomes N, B becomes O, C becomes P and so on. This is an easy code to crack, as there are only 25 unique shifts.<\/p>\n<figure class=\"align-center\"><img src=\"https:\/\/62e528761d0685343e1c-f3d1b99a743ffa4142d9d7f1978d9686.ssl.cf2.rackcdn.com\/files\/65188\/width668\/image-20141121-1040-1scgtgy.png\" alt=\"\" \/><\/figure>\n<p><span class=\"caption\">A substitution cypher with the alphabet shifted 13 times (ROT13).<\/span><br \/>\n<span class=\"attribution\"><a class=\"source\" href=\"http:\/\/commons.wikimedia.org\/wiki\/File:ROT13.png\" rel=\"nofollow\">Matt Crypto<\/a><\/span><\/p>\n<p>Far harder would be a scrambled alphabet, in which any letter can be mapped to any other letter without the same substitution shift applying to all, as with the Caesar cypher. This leads to a colossal number of permutations \u2013 403 million billion billion \u2013 that, even with a supercomputer with which to try a billion mappings per second, would still take an average 6.3 billion years to crack.<\/p>\n<p>However, these ciphers&#8217; fundamental weakness is the <a href=\"http:\/\/asecuritysite.com\/challenges\/scramb\">occurrence of the letters<\/a>: in English, the letter with the most occurrences is likely to represent an E, the most common in the language. Performing a frequency analysis with this in mind makes much shorter work of it \u2013 about five minutes.<\/p>\n<p>&nbsp;<\/p>\n<p>In the early days it was the ciphers&#8217; text scrambling method that was kept secret. But if Eve manages to crack the cipher, neither Bob nor Alice will know \u2013 just as the Nazis didn\u2019t know the Allies had cracked Enigma. So modern cryptography uses a different approach: a public method to create the cipher, but a private key to use the cipher that Eve will find difficult to find. This is <a href=\"http:\/\/www.webopedia.com\/TERM\/P\/public_key_cryptography.html\">public key encryption<\/a>.<\/p>\n<h2>Codebreaking Enigma<\/h2>\n<p>In the days before computers, ciphers were mechanically generated \u2013 the <a href=\"http:\/\/www.cs.man.ac.uk\/~banach\/COMP61411.Info\/CourseSlides\/Wk1.3.Enigma.pdf\">Enigma cipher rotor machine<\/a> is a good example. It used a polyalphabetic substitution cipher \u2013 with three rotors to generate three alphabetic substitution shifts \u2013 and a secret key. The challenge was to determine both the algorithm used and the key.<\/p>\n<p>Enigma\u2019s weakness was that the machine prevented a plain text letter from being ciphered as itself (that is, from A ending up after three substitutions as A). This made the challenge easier as the codebreakers could dismiss any code that mapped to the same letter, bu this still left many alternatives \u2013 too many for a human to crack.<\/p>\n<figure class=\"align-center\"><img src=\"https:\/\/62e528761d0685343e1c-f3d1b99a743ffa4142d9d7f1978d9686.ssl.cf2.rackcdn.com\/files\/65126\/width668\/image-20141120-4481-psvei8.jpg\" alt=\"\" \/><\/figure>\n<p><span class=\"caption\">An Enigma\u2026 wrapped in a box.<\/span><br \/>\n<span class=\"attribution\"><span class=\"source\">Dominic Lipinski\/PA<\/span><\/span><\/p>\n<p>The mathematical prowess of the <a href=\"http:\/\/www.math.ucsd.edu\/~crypto\/students\/enigma.html\">Polish Cypher Bureau<\/a> had secretly first broken Enigma codes in 1932, with the aid of French intelligence. At the eve of the war they handed their work to the Allies, who were amazed. But by now the German military were using more advanced versions of the Enigma machine, with extra rotors and other features adding complexity to the cipher. <a href=\"http:\/\/www.historytoday.com\/blog\/books-blog\/kathryn-hadley\/reader-review-dilly-man-who-broke-enigmas\">Dilly Knox<\/a>, the British chief codebreaker, had some success but better equipment was required.<\/p>\n<p>Developing the work of the Polish Cypher Bureau, Turing and Gordon Welchman designed the electro-mechanical <a href=\"http:\/\/www.expertreviews.co.uk\/general\/1282126\/how-bletchley-park-broke-the-german-enigma-code\">Bombe<\/a>, a device designed to imitate Enigma machines wired back-to-back, which given certain information could narrow down the possible permutations of the Enigma machines&#8217; settings from <a href=\"http:\/\/www.codesandciphers.org.uk\/enigma\/enigma3.htm\">150 million million<\/a> to a more manageable number.<\/p>\n<figure class=\"align-center\"><img src=\"https:\/\/62e528761d0685343e1c-f3d1b99a743ffa4142d9d7f1978d9686.ssl.cf2.rackcdn.com\/files\/65129\/width668\/image-20141120-4461-1inj4y0.jpg\" alt=\"\" \/><\/figure>\n<p><span class=\"caption\">Former operator Jean Valentine, 82, explains the \u2018Bombe\u2019 cryptoanalysis machine behind her.<\/span><br \/>\n<span class=\"attribution\"><span class=\"source\">Rui Vieira\/PA<\/span><\/span><\/p>\n<p>But the true father of code cracking is <a href=\"http:\/\/www.colossus-computer.com\/colossus1.html\">Colossus<\/a>, the world\u2019s first programmable electronic digital computer, which was created by engineer <a href=\"http:\/\/home.bt.com\/news\/btlife\/bt-remembers-tommy-flowerss-achievements-11363857904783\">Tommy Flowers<\/a> in order to crack the Lorenz cipher, the more sophisticated successor to Enigma.<\/p>\n<figure class=\"align-center\"><img src=\"https:\/\/62e528761d0685343e1c-f3d1b99a743ffa4142d9d7f1978d9686.ssl.cf2.rackcdn.com\/files\/65128\/width668\/image-20141120-4493-1dtms5g.jpg\" alt=\"\" \/><\/figure>\n<p><span class=\"caption\">The rebuilt Colossos, the world\u2019s first computerised codebreaking machine with Tony Sale, it\u2019s creator.<\/span><br \/>\n<span class=\"attribution\"><span class=\"source\">Rui Vieira\/PA<\/span><\/span><\/p>\n<h2>Cracking crypto today<\/h2>\n<p>Computers are so much more powerful now than in Turing\u2019s day that their raw power can crack passwords or uncover encryption methods simply by crunching through all the different possible permutations.<\/p>\n<p>Most passwords are stored in a <a href=\"http:\/\/www.sans.edu\/research\/security-laboratory\/article\/hash-functions\">hash<\/a> \u2013 a fixed-length string of characters generated by a mathematical function from text of any length. This is a one-way process, so the hash cannot be reversed to gain the original text.<\/p>\n<p>However today it\u2019s possible to compile look-up tables of pre-hashed values, essentially a dictionary of hashes to compare to the plain text passwords they represent.<\/p>\n<p>As an illustration: a seven character password in lower case letters could be one of over 8 billion possible permutations. The graphics processor on a typical computer graphics card (which are excellent for this task) can check over 150m words per second, meaning the maximum time to crack any password is a mere 53 seconds.<\/p>\n<p>Adding upper case letters gives one thousand billion combinations, and a maximum time to crack of 114 minutes. Even when adding 20 more numeric characters and common punctuation marks to create more than ten thousand billion permutations, the maximum time is only 18 hours. Eight character passwords are a bit more difficult with 722 thousand billion permutations, but even so these can be cracked at an acceptably quick time of 1,337 hours or 55 days.<\/p>\n<p>The worry is that the distributed computing power of the cloud is making this process significantly easier. One of the most common hashing functions, <a href=\"http:\/\/www.md5.net\/\">MD5<\/a>, has been shown to be too weak to cope with the computing power that can now be thrown at it.<\/p>\n<p>Each MD5 hash is 128 bits long, so to store every possible seven character password hash would require 160 terabytes of storage space. While that seems like a lot, you can buy a 4TB drive for about \u00a3100, Microsoft advertises no limits to its storage, and Dropbox offers several terabytes for little cost. Similarly, using cloud processing power such as the <a href=\"http:\/\/aws.amazon.com\/ec2\/\">Amazon Cloud<\/a> it would be possible to rent processing time on 1,000 of these graphics cards for just <a href=\"http:\/\/aws.amazon.com\/ec2\/pricing\/\">pennies<\/a>, spread the task between them, and crack an eight-character password in an hour and a half.<\/p>\n<h2>Add salt to taste<\/h2>\n<p>The true way to increase the strength of a password is to add a <a href=\"http:\/\/security.stackexchange.com\/questions\/51959\/why-are-salted-hashes-more-secure\">salt<\/a>, a random string of text used to add complexity to a hashed password.<\/p>\n<p>For example, the seven-character salt \u201ceFUqsfi\u201d is added to the password \u201cpassword\u201d to create the string \u201ceFUqsfipassword\u201d. This produces a hash that is sufficiently random that it won\u2019t appear in a hash look-up table and, being 15 characters instead of eight, massively increases the complexity of trying to crack the password using brute force attacks, from 722 billion billion permutations to over 742 million billion billion permutations.<\/p>\n<p>Thus we have gone from the millions of dollars of investment to build and maintain Colossus, to a time where crackers have managed to<br \/>\ncreate the same hash signature for a <a href=\"https:\/\/www.linkedin.com\/pulse\/article\/20141105075217-%0A15260610-say-goodbye-to-md5-and-hello-to-the-largest-cipher-cracking-machine-ever-created\">different image<\/a>, and where it took<br \/>\njust 10 hours and cost only 65 cents plus tax on a GPU instance on the Amazon Cloud.<\/p>\n<p>So some of the pure intellect of Turing\u2019s day has gone, and now it\u2019s down to who has the fastest computer. The cloud itself is a supercomputer that is expanding by the day, and with <a href=\"https:\/\/crackstation.net\/hashing-security.htm\">websites<\/a> dedicated to analysing and storing as many hashed passwords as possible, the whole foundations of our password cryptography are starting to crumble, with profound implications for the security of the internet.<\/p>\n<p><img loading=\"lazy\" src=\"https:\/\/counter.theconversation.edu.au\/content\/34448\/count.gif\" alt=\"The Conversation\" width=\"1\" height=\"1\" \/><\/p>\n<p><em>Bill Buchanan does not work for, consult to, own shares in or receive funding from any company or organisation that would benefit from this article, and has no relevant affiliations.<\/em><\/p>\n<p>This article was originally published on <a href=\"http:\/\/theconversation.com\">The Conversation<\/a>.<br \/>\nRead the <a href=\"http:\/\/theconversation.com\/codebreaking-has-moved-on-since-turings-day-with-dangerous-implications-34448\">original article<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>By Bill Buchanan, Edinburgh Napier University We have always been been intrigued by keeping secrets and uncovering the secrets of others, whether that\u2019s childhood secret messages, or secrets and codebreaking of national importance. With a film, The Imitation Game, reprising the life of Alan Turing and his role in breaking the Nazi\u2019s Enigma cipher of [&hellip;]<\/p>\n","protected":false},"author":39,"featured_media":5227,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[291,8],"tags":[970,972,971,892,885,891,860],"_links":{"self":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts\/2399"}],"collection":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/comments?post=2399"}],"version-history":[{"count":2,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts\/2399\/revisions"}],"predecessor-version":[{"id":5226,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts\/2399\/revisions\/5226"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/media\/5227"}],"wp:attachment":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/media?parent=2399"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/categories?post=2399"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/tags?post=2399"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}