Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- DevCentral
- Technical Articles
- BlackHat 2016 F5 Cipher Challenge

Options

- Subscribe to RSS Feed
- Mark as New
- Mark as Read
- Bookmark
- Subscribe
- Email to a Friend
- Printer Friendly Page

pliam_250472

Historic F5 Account

Options

- Article History
- Subscribe to RSS Feed
- Mark as New
- Mark as Read
- Bookmark
- Subscribe
- Email to a Friend
- Printer Friendly Page

on 11-Aug-2016 14:00

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:

- 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

- 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
. Why should you?"*play fair**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.

- 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)

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

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.

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 of *information 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 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.rb**

Labels:

Comments

pliam_250472

Historic F5 Account

Hi Josh!

We think between 10-20 people worked either individually or in small teams to claim all prizes. The last correct solution and final prize was claimed near the end of BlackHat, so we don't even know how many were close behind at that time.

-F5 Cipher Challenge Team