Cipher challenge #1 from Joshua Holden: Merkle’s Puzzles

The Mathematics of Secrets by Joshua Holden takes readers on a tour of the mathematics behind cryptography. Most books about cryptography are organized historically, or around how codes and ciphers have been used in government and military intelligence or bank transactions. Holden instead focuses on how mathematical principles underpin the ways that different codes and ciphers operate. Discussing the majority of ancient and modern ciphers currently known, The Mathematics of Secrets sheds light on both code making and code breaking. Over the next few weeks, we’ll be running a series of cipher challenges from Joshua Holden. Presenting the first, on Merkle’s puzzles. 

For over two thousand years, everyone assumed that before Alice and Bob start sending secret messages, they’d need to get together somewhere where an eavesdropper couldn’t overhear them in order to agree on the secret key they would use. In the fall of 1974, Ralph Merkle was an undergraduate at the University of California, Berkeley, and taking a class in computer security. He began wondering if there was a way around the assumption that everyone had always made. Was it possible for Alice to send Bob a message without having them agree on a key beforehand? Systems that do this are now called public-key cryptography, and they are a key ingredient in Internet commerce. Maybe Alice and Bob could agree on a key through some process that the eavesdropper couldn’t understand, even if she could overhear it.

Merkle’s idea, which is now commonly known as Merkle’s puzzles, was slow to be accepted and went through several revisions. Here is the version that was finally published. Alice starts by creating a large number of encrypted messages (the puzzles) and sends them to Bob.

The beginning of Merkle’s puzzles.

Merkle suggested that the encryption should be chosen so that breaking each puzzle by brute force is “tedious, but quite possible.” For our very small example, we will just use a cipher which shifts each letter in the message by a specified number of letters. Here are ten puzzles:

VGPVY QUGXG PVYGP VAQPG UKZVG GPUGX GPVGG PBTPU XSNHT JZFEB
GJBAV ARSVI RFRIR AGRRA GJRYI RFRIR AGRRA VTDHC BMABD QMPUP
AFSPO JOFUF FOUFO TFWFO UXFOU ZGJWF TFWFO UFFOI RCXJQ EHHZF
JIZJI ZNDSO RZIOT ADAOZ ZINZQ ZIOZZ IWOPL KDWJH SEXRJ IKAVV
YBJSY DSNSJ YJJSY BJSYD KNAJX JAJSK TZWXJ AJSYJ JSFNY UZAKM
QCTCL RFPCC RUCLR WDMSP RCCLD GDRCC LQCTC LRCCL JLXUW HAYDT
ADLUA FMVBY ALUVU LVULZ LCLUZ LCLUA LLUGE AMPWB PSEQG IKDSV
JXHUU VYLUJ XHUUJ UDDYD UIULU DJUUD AUTRC SGBOD ALQUS ERDWN
RDUDM SDDMS VDMSX RDUDM SDDMM HMDSD DMRHW SDDMR DUDMS DDMAW
BEMTD MBEMV BGBPZ MMMQO PBMMV AMDMV NQDMA MDMVB MMVUR YCEZC

Alice explains to Bob that each puzzle consists of three sets of numbers. The first number is an ID number to identify the puzzle. The second set of numbers is a secret key from a more secure cipher which Alice and Bob could actually use to communicate. The last number is the same for all puzzles and is a check so that Bob can make sure he has solved the puzzle correctly. Finally, the puzzles are padded with random letters so that they are all the same length, and each puzzle is encrypted by shifting a different number of letters.

Bob picks one of the puzzles at random and solves it by a brute force search. He then sends Alice the ID number encrypted in the puzzle.

Bob solves the puzzle.

For example, if he picked the puzzle on the fifth line above, he might try shifting the letters:

YBJSY DSNSJ YJJSY BJSYD KNAJX JAJSK TZWXJ AJSYJ JSFNY UZAKM
zcktz etotk zkktz cktze lobky kbktl uaxyk bktzk ktgoz vabln
adlua fupul allua dluaf mpclz lclum vbyzl clual luhpa wbcmo
bemvb gvqvm bmmvb emvbg nqdma mdmvn wczam dmvbm mviqb xcdnp

qtbkq vkfkb qbbkq tbkqv cfsbp bsbkc lropb sbkqb bkxfq mrsce
ruclr wlglc rcclr uclrw dgtcq ctcld mspqc tclrc clygr nstdf
svdms xmhmd sddms vdmsx ehudr dudme ntqrd udmsd dmzhs otueg
twent ynine teent wenty fives evenf ourse vente enait puvfh

Now he knows the ID number is “twenty” and the secret key is 19, 25, 7, 4. He sends Alice “twenty”.

Alice has a list of the decrypted puzzles, sorted by ID number:

ID secret key check
zero nineteen ten seven twentyfive seventeen
one one six twenty fifteen seventeen
two nine five seventeen twelve seventeen
three five three ten nine seventeen
seventeen twenty seventeen nineteen sixteen seventeen
twenty nineteen twentyfive seven four seventeen
twentyfour ten one one seven seventeen

So she can also look up the secret key and find that it is 19, 25, 7, 4. Now Alice and Bob both know a secret key to a secure cipher, and they can start sending encrypted messages. (For examples of ciphers they might use, see Sections 1.6, 4.4, and 4.5 of The Mathematics of Secrets.)

Alice and Bob both have the secret key.

Can Eve the eavesdropper figure out the secret key? Let’s see what she has overheard. She has the encryptions of all of the puzzles, and the check number. She doesn’t know which puzzle Bob picked, but she does know that the ID number was “twenty”. And she doesn’t have Alice’s list of decrypted puzzles. It looks like she has to solve all of the puzzles before she can figure out which one Bob picked and get the secret key. This of course is possible, but will take her a lot longer than the procedure took Alice or Bob.

Eve can’t keep up.

Merkle’s puzzles were always a proof of concept — even Merkle knew that they wouldn’t work in practice. Alice and Bob’s advantage over Eve just isn’t large enough. Nevertheless, they had a direct impact on the development of public-key systems that are still very much in use on the Internet, such as the ones in Chapters 7 and 8 of The Mathematics of Secrets.

Actually, the version of Merkle’s puzzles that I’ve given here has a hole in it. The shift cipher has a weakness that lets Eve use Bob’s ID number to figure out which puzzle he solved without solving them herself. Can you use it to find the secret key which goes with ID number “ten”?

Trackbacks

  1. […] few weeks, we’ll be running a series of cipher challenges from Joshua Holden. The first was on Merkle’s puzzles. Today’s focuses on subliminal […]