BlackHat 2016 F5 Cipher Challenge
BlackHat 2016 F5 Cipher Challenge F5's BlackHat 2016 cipher challenge had several connecting puzzles. We hope you had fun with it! In this article we explain the puzzles and our design approach. First the nuts and bolts: The Puzzles Card puzzle #1: HSHRZQHCCKD Card puzzle #2: DIZKKVWRMZNBHGVIB Card puzzle #3: T-Shirt Puzzle: SF PS DS IY FR CS MB DM IN QN NP HR FV EI BX YG WF QW XC WY SM LK The Hints We agreed to tell any interested contestants that the easier solutions were necessary for the T-shirt puzzle. Meaning: the key to the hard puzzle *was* the concatenation of the 3 easier puzzle solutions, in the obvious order. We tried to hide in plain sight a hint about the T-shirt cipher, "Hackers don't play fair. Why should you?" Meaning: we used the Playfair cipher for part of the T-shirt. We put spaces between every two letters (called digrams). Meaning: A digraphic substitution cipher (Playfair). The Playfair key was itself a hint. Meaning: the T-shirt puzzle was literally a puzzle wrapped in a puzzle wrapped in a puzzle. Finally 'F5' was a hint. Meaning: we used ROT1, under which F encrypts to 5th letter E. The Solutions Card puzzle #1: ROT1 of "IT IS A RIDDLE" Card puzzle #2: Atbash of "WRAPPED IN A MYSTERY" Card puzzle #3: Pigpen variant below of "INSIDE AN ENIGMA" T-shirt puzzle: THERE IS NOTHING MORE DECEPTIVE THAN AN OBVIOUS FACT cipher: A nested application of Playfair and the two alphabetic ciphers from the card (see below) T-Shirt Details The Playfair key was the string, "ITISARIDDLEWRAPPEDINAMYSTERYINSIDEANENIGMA" leading to the the key matrix. I T S A R D L E W P N M Y G B C F H K O Q U V X Z Playfair maps digrams to digrams by drawing rectangles and flipping axes, or shifting, etc. Our initial diagrams are SF -> TH and PS -> ER The Playfair article on Wikipedia does a great job explaining this. Keep going and the initial decrypt will be THERE IS NOTHING LNQDCDBDOSHUDSGZMYLKXDQKEGTYWF You might feel stuck at this point, but remember the key is also a clue and you've only unwrapped the outer layer. Apply some cryptanalysis to (the beginning of) "LNQDCDBDOSHUDSGZMYLKXDQKEGTYWF" and you should recognize the rot1 cipher again, obtaining: MORE DECEPTIVE THAN ZMLYERLFHUZXG Again you may feel stuck but applying the hint again, you finally recognize atbash again and unwrap the innermost puzzle AN OBVIOUS FACT an hence the full solution: THERE IS NOTHING MORE DECEPTIVE THAN AN OBVIOUS FACT Explanations and Design Unless you were quite skilled with the modern tools, even the three "easier" puzzles might have taken several hours or more. Unfortunately these classical ciphers can be broken by well-known but not so widely-known tools available online (see below). Our own challenge was to create a puzzle which could be broken by hand with pencil and paper, but which would still resist sophisticated cryptographic techniques. We didn't want anyone to just paste the ciphertext into google or an online solver and wait for the solution. So, we experimented extensively with Playfair varying mock keys and plaintext just to see how effective online solvers were for various message lengths and common vocabulary. They are very effective indeed and they do NOT need the key. They simply attempt to exploit natural language redundancy such as guessable passphrase keys or low-entropy plaintext. While our 42-character key was not vulnerable to Playfair password guessing, our 44-character plaintext fell quickly to online solvers when encrypted with Playfair alone. Here are some good examples of online solvers exploiting these weaknesses. password guessing: http://www.quinapalus.com/playfair.html plaintext redundancy (via hill climbing) http://bionsgadgets.appspot.com/ww_forms/playfair_ph_web_worker3.html So we knew we needed to obfuscate both the input and output to Playfair in order to reduce the exploitable redundancy. We therefore conceived of the above technique. This puzzle was treated like a mini software development project with design phase, unit tests and beta testers. Some History Of course, in single blow in 1949, Claude Shannon [1] put the final nail in the coffin of 2 millennia of classical cryptography. He provided the theoretical framework for why straightforward Playfair could be broken on plaintext like ours. He quantitatively showed how the plaintext redundancy, measured by its entropy, plugs directly into his approximation of the unicity distance (the average length of ciphertext necessary to uniquely determine the key). In doing so Shannon introduced many concepts we still use in modern cryptography: the ideal cipher model, product ciphers and (according to many [2]) the subject ofinformation theory. Since then, classical encryption puzzles are often given with only a hint about the underlying cipher and with various twists on the original methods. [1] Shannon, Claude E. "Communication theory of secrecy systems." Bell system technical journal 28.4 (1949): 656-715. [2] Hellman, Martin, "Oral history interview with Martin Hellman" Charles Babbage Institute, Univ. of Minn, 2004. The Code The following "driver" script in Ruby was used to generate the T-shirt puzzle. It needs our playfair.rb library further below. #!/usr/bin/env ruby require_relative './playfair' keys = [ 'It is a riddle', 'wrapped in a mystery', 'inside an enigma' ].map{|p| p.gsub(/\s+/, '').downcase} key1 = keys[0] key2 = keys[1] key3 = keys[2] # alternate shift (can only be {1, 7, 9, 13, 18} if we want no j) shift = 1 # easy puzzles (not pigpen) ctx1 = Playfair.caesar(key1, shift) ctx2 = Playfair.atbash(key2) # instantiate Playfair object for hard puzzle cipher = Playfair.new(key1 + key2 + key3) # dump 5x5 key matrix cipher.dump # the plaintext ptxs = [ "There is nothing", "more deceptive than", "an obvious fact" ].map{|p| p.gsub(/\s+/, '').downcase} # intermediate plaintext (playfair plaintext input) ptx = ptxs[0] + Playfair.caesar(ptxs[1] + Playfair.atbash(ptxs[2]), shift) # compute the final t-shirt puzzle) ctx = cipher.encrypt(ptx) puts "hard puzzle:\n\t%s" % (0...ctx.size/2).map{|i| ctx[2*i, 2]}.join(' ').upcase The following is an implementation of Playfair in Ruby. #!/usr/bin/env ruby class Playfair attr_accessor :key, :key5x5, :coords def initialize(k) @key = k make_key end def make_key @key5x5 = {} @coords = {} k = key.downcase k.gsub!(/[^a-z]/, '') k.gsub!('j', 'i') k += "abcdefghiklmnopqrstuvwxyz" j = 0 (0...25).each do |i| coord = [i/5,i%5] while coords.has_key?(k[j]) do j += 1 end key5x5[coord] = k[j] coords[k[j]] = coord end end def iof(c) coords[c][0] end def jof(c) coords[c][1] end def encrypt_digram(di, fwd = true) incr = fwd ? 1 : -1 d1 = di[0] d2 = di[1] # check for improper rectangles raise "cannot encrypt double letter" if d1 == d2 return key5x5[[iof(d1), (jof(d1) + incr) % 5]] + key5x5[[iof(d2), (jof(d2) + incr) % 5]] if iof(d1) == iof(d2) return key5x5[[(iof(d1) + incr) % 5, jof(d1)]] + key5x5[[(iof(d2) + incr) % 5, jof(d2)]] if jof(d1) == jof(d2) # now we have a proper rectangle minj = [jof(d1), jof(d2)].min maxj = [jof(d1), jof(d2)].max del = maxj - minj key5x5[[iof(d1), jof(d1) + del*((jof(d1) < jof(d2)) ? 1 : -1)]] + key5x5[[iof(d2), jof(d2) + del*((jof(d2) < jof(d1)) ? 1 : -1)]] end def decrypt_digram(di) encrypt_digram(di, false) end def encrypt(p, fwd = true) # precondition as with key ptx = p.downcase.gsub(/[^a-z]/, '').gsub('j', 'i') # precondition doubles ptx.gsub!(/([a-z])\1/, '\1x\1') if fwd # apply encryption on digram ptx += 'q' unless 0 == (ptx.size % 2) (0...(ptx.size/2)).map{|i| encrypt_digram(ptx[2*i,2], fwd)}.join('') end def decrypt(ctx) encrypt(ctx, fwd = false).gsub(/([a-z])x\1/, '\1\1').sub(/q$/, '') end def to_s (0...5).map{|i| (0...5).map{|j| key5x5[[i,j]]}.join(' ')}.join("\n") end def dump puts "key matrix for '%s':" % key puts self end # # auxiliary ciphers # def self.caesar(msg, shift=3, fwd = true) # caesar (0...msg.size).map{|i| ((msg[i].ord - 'a'.ord - shift * (fwd ? 1 : -1)) % 26 + 'a'.ord).chr}.join('') end def self.atbash(msg) # atbash (0...msg.size).map{|i| (25 - msg[i].ord + 2*'a'.ord).chr}.join('') end end playfair.rbHackable Homes
Is your house vulnerable? Imagine coming home, disarming the alarm system, unlocking your doors and walking into a ransacked dwelling. There are no broken windows, no forced entry, no compromised doggie doors and really no indication that an intruder had entered. Welcome to your connected home. I stop short of calling it a 'smart' home since it's not yet intelligent enough to keep the bad guys out. From smartphone controlled front door locks to electrical outlets to security cameras to ovens, refrigerators and coffee machines, internet connected household objects are making their way into our homes. Our TVs, DVDs and DVRs are already. And anything connected to the internet, as we all know, is a potential target to be compromised. Researchers have shown how easy it is to infect automobiles and it is only a matter of time before crooks and a little bit of code will be able to watch you leave your driveway, disable your alarms, unlock your door, steal your valuables and get out with minimal trace. Those CSI/NCIS/Criminal Minds/L&O crime dramas will need to come up with some new ideas on how to solve the mystery during the trace-evidence musical montages. The hard-nosed old timer is baffled by the fact that there is nothing to indicate a break-in except for missing items. Is the victim lying for insurance fraud? Could it have been a family member? Or simply a raccoon? A real who-done-it! Until, of course, the geeky lab technician emerges from their lair with a laptop showing how the hacker remotely controlled the entire event. 'Look Boss, zeros and ones!' Many of these remotely controlled home devices use a wireless communications protocol called Z-Wave. It's a low power radio wave that allows home devices to communicate with each other and be controlled remotely over the internet. Last year, 1.5 million home automation products were sold in the US and that is expected to grow to 8 million in less than 5 years. An estimated 5 million Z-Wave devices will be shipped this year. Like any communications protocol, riff-raff will attempt to break it, intercept it and maliciously control it. And as the rush to get these connected devices in consumer's hands and homes grows, security protections may lag. I often convey that the hacks of the future just might involve your refrigerator. Someone takes out all the internet enabled fridges on the West Coast and there is a food spoilage surge since no one owns legacy fridges any more....let alone Styrofoam coolers. ps Related: 'Smart homes' are vulnerable, say hackers The five scariest hacks we saw last week From Car Jacking to Car Hacking The Prosecution Calls Your Smartphone to the Stand Mobile Threats Rise 261% in Perspective Q. The Safest Mobile Device? A. Depends Holiday Shopping SmartPhone Style SmartTV, Smartphones and Fill-in-the-Blank Employees Technorati Tags: blackhat,hacks,vulnerabilities,breach,home,house,smart phone,smart technology,silva,security,z-wave,smart devices,household Connect with Peter: Connect with F5:
