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 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 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.rb
