Crypto challenge 22: p ?6H DA:? @? 2? @=5 E96>6

So I'll start with the trivial part.

Title: A new spin on an old theme

Question: There has been some truly impressive code breaking in the more recent challenges. This challenge revives an old cipher, but introduces a new twist. Can you figure it out? This week the code, which will reveal a cryptic clue. Step two is to solve the clue and post the answer in plain text, for the points. The points breakdown will be 50 for the title and instructions, 50 for identifying the encryption scheme, 350 for cracking the main cipher and 50 for solving the cryptic clue.

Oops, sorry, I somehow didn't notice that pkwan already posted it. So please ignore my post.

x4u,

No problem, and welcome to the challenge. You have just missed out out on the first 50 points but there are plenty more to be had. The next fifty go for identifying the encryption scheme of the main cipher. The standard rules are three gueses per person and only the first three count if more are submitted. There are clues in the title and instructions to the cipher type.

I'm surprised that nobody has had a guess at the cipher type yet, so let's review the clues.
A new spin on an old theme implies that this is a variation on a cipher that we have had in an earlier challenge.
You can eliminate some of the more trivial ciphers e.g. monoalphabteic substitutions.
You can also eliminate transpositions, based on the frequency analysis.
That should leave a small number of ciphers to consider.

Still waiting for a guess at the cipher type. To narrow down the field I'll tell you that it's one of the ciphers available in Tyler Atkin's very neat collection of cipher tools - http://rumkin.com/tools/cipher/.

pkwan,

After a bit of help narrowing it down you have got it.

The next step is to break the code. The Vigenere tableau was made from a keyed alphabet. The cipher was encoded using another keyword. The cipher keyword can be found by the usual methods of index of coincidence or Kasiski's method. You can then break the message into a number of streams and perform frequency analysis on each to determine the likely substitutions.

Is there any references that have explanation of this type of cipher?

pkwan,

It's a conventional Vigenere, except that the alphabets in the Vigenere square are keyed instead of just appearing in alphabetical order. There are on-line implementations of the cipher at http://rumkin.com/tools/cipher/vigenere-keyed.php and http://members.aon.at/cipherclerk/CipherClerk.html.

More information about the encoding and analysis can be found at http://www.fortunecity.com/skyscraper/coding/379/lesson10.htm. If you can get hold of a copy of Military Cryptanalysis by William Friedman (published by Aegean Park Press) there is a detailed discussion of Vigenere ciphers with mixed alphabets and the code for a program in BASIC.

I think one of the problems with this puzzle is that there is not enough text to carry out meaningful frequency analysis. For this reason I have encrypted a second message using the same keys as the first and it is presented below.

R hnqdmby vpwe icp zvkbby zzjvg dwuhcwtyquwcu ke jqvcath bkuosj sbiv cq gawtlf dyystrmtwm ymzcaaslww. Dnkasmblaf dwuhcwtyquwqu vaqtxd eyyztfh qt earvquejgp, wonj yy zjfgwaswn jqwoap ul ukojax vvesbdw, kaiucbyd wtf adbmhbqkp. Xgnj mckaowia krw opkrxq tpwvygmxnaaslww cebs cbhfwv tswx fpsvjo vfle icp ofvt deaffneah rrk nbo fq kdvg se dxtvbm aox opgawanqpi pbpwgsy js r tqfjaw. Tv qu eib nugc sg aox jqga fdxgbyu al tbcpagm xyqwhk mxer et cwtbdrmlpy paa plpwqqt ti dxtvbmlka cey ilxsfp qaypzmva. Pbrrsekmb myf nsfb yzuvv swtxd rs plkbwaoa aox gdsvsm ul ryza mygr ja rfwc rvyspgqr ko edsfh et rrdf ae icdsfh et fdxgb jjy wukva xktff uejqa wfpgjsn xyqwhk trlqvpcmbbp htw obd dyeyrafu et fq kdvhvq.

To reduce the tedious work of elimination, and hypothesis testing, can you tell me if the structure of the vigenere tabels is standard, ie, each row comprising a standard caeser cipher, and shifting progressively by one character, or have the rows / columns been messed with?

Trying to extract a keyword from a standard vigenere table is hard enough...

Also, since this one is going slow, should I also be looking for a cryptic clue as to the keyword, or not?

Jason210,

If you read the comment history in this thread you will see that this is a keyed Vigenere cipher i.e. the alphabets are mixed up. There are no cryptic clues that directly reveal the keywords used to encrypt the Vigenere table and the message, so this is more of a true cryptanalysis challenge. There are some hints for attacking this type of cipher in the thread, as well as some references where you can find more detail about the cipher and some on-line implementations. You will also notice that I have left the text structure of the messages intact, so you can see how long the words are and where punctuation appears. This should allow you to do a probable word attack (hint: try the single letter words first) to recover parts of the message key and begin reconstructing the vigenere table. You can also find the length of the message keyword using the Kasiski method, exactly as you would with a standard Vigenere.

If there is no further progress on this cipher in the next day or two I will post the length of the message key.

Sorry about that - I didn't read it properly. Actually I was just reading about this cipher on that rumkin link you posted. This is a real toughie.

Since time is running out on this part of the zzle, I'm going to suggest a likely keyword length of 7, determined bu Index of Coincidence.

Jason210,

Nice work. The message key is 7 characters long.

Also, in your second sample, the ciphertext word "et" appears four times, and it is seperated by muliples of 7. And 7 is not divisable, so Kisiski method would also seem to confirm that the keyword is 7 long.

So now that you know the keyword length you can split the two messages into 7 streams. Each stream is effectively a monoalphabetic substitution and you can start identifying likely substitutions by frequency analysis. Also bear in mind that all of the streams use the same key with different offsets. You can also identify likely substitutions from the structure of the text e.g. common short words, common beginning and end letters etc.

Also, the first message, the position of "rja" also reveals the message key is of 7 characters log.

A bit tricky with the streams. Whilst the commonest letters "e" and "t" might be stand out significantly, the other letters are confusing as each stream is quite short - may be too short to do an effective frequency analysis..

I see why they developed Computers in WWII now. Would be useful to have some simple quantitive text analysis software...

Ok, this is me trying to learn these non-simple substituion cryptos...
When talking about a Vigenere, when they say "Once the length of the keyword is known, the ciphertext can be broken up into that many simple substitution cryptograms." are they meaning that you, for instance if using a 7-character key, would write the letters down in 7 different groups, so that you no longer have anything legible but rather have the capacity for frequency analysis...?

Jason210,

Some people would contend that the computer has eroded the skill of cryptanalysis to some extent. During WW2 the codebreakers at Bletchley had primitive computer equipment by our standards and most of the Enigma breaks were achieved by the ingenuity and persistence of the people. The firts message was too short, but you now have just over 100 characters per stream, which is considered about double the amount of text that would normally be required to break a monoalphabetic substitution.

dagesi,

Let's look at a simple example. Say your message is "the cat sat on the mat" and you keyword is "dog". If you apply a standard Vigenere to this you get the ciphertext "wvkfozvozrbzkssdh". You can verify this at http://islab.oregonstate.edu/koc/ece575/02Project/Mun+Lee/VigenereCipher.html or http://rumkin.com/tools/cipher/vigenere.php.

If you had to decrypt this and know that the keyword was three letters long then you know that every third letter is encrypted with the same Caesar shift. So you split the ciphertext into three streams, thus

wvk
foz
voz
rbz
kss
dh

or

wfvrkd
voobsh
kzzzs

if you prefer it in rows.

Each column/row is now a monoalphabetic substitution (a simple Caesar shift, in fact) and you can determine the likely shift with frequency analysis. The columns/rows are a bit short in this example, but the z in column/row 3 is most likely and E or a T, for example. With more text you can get a more accurate idea. With a little bit of trial and error you can crack the code.

This puzzle is more complicated because it is not a standard vigenere, so it is not just a simple case of sliding an alphabet around, but frequency analysis will still give an indication of likely substitutions. Also bear in mind that each substitution uses the same ordering of its alphabet, with a different offset.

We now know that this cipher uses a 7 letter keyword so we can split the cipher text into 7 streams. For the two messages this results in the following streams.

WdoawqfmnwxrrrlmqpdKutbqyp RypzuuqkittmwmuuttrpzwpadbdpkrqmwbwoparqdoaprTnodlmmwppdkxprmytkommfpdrddwtantmorq
jskuxjjtouzjdskbvrsuzguexx hvzzhwvuvlrzwbhwxfvwjnuxwybXawtxwhxvofrkxxnwtvuxxtxxtywxaszryzxbxuywgsdsxufwxrbbak
blldwfvvbymfqgdjpcssycqbbk npvjcccocfmcDlcqdhqofjlvkdmgoopncfffffkdtoqgqqgjgbyebpqtcfmsfudwglgcqfffgkffylbdfd
uwtvqawixtvrppcRwuweoephpq qwkvwuasqdtanawuequngquvawhnwpwaewplvnnvvppsfucqbcqrdaqvepvenvradrrrrhahbvupqqpduv
atpvvaeybwtjiiwjesawfseyyy debgtktjgywakftvytejwwkeitbjikvabvsetebgbgiyjesgypweratbyqaksvsosyjvkeeejaegwvhyeh
xeatabaCoedataoaxijumeeeae mibdyehsaymsadyayejyaoosufqmarysstvidaosmapjaigauahtmptmiaPmfspavzayotitjxjjhptetv
eygsKeylhbdriwcwccawcbfeq  bcywqjbbwsylswqqzagysajbcakckxglcsjcehfeawbswbafagkcllillybbbwlasarsercfykqskcwyfq

From the structure of the original messages you can work out some likely substitutions e.g. The single R at the start of message 2 can only be A or I. Let's make an educated guess that it's an A, seeing that there are some other single Rs in that stream. This means that you can substitute all Rs in stream 1 (the top row) with As. Applying frequency analysis to the streams and substituting likely letters, using the text structure for hints, you should be able to start identifying some likely words between the streams. If you can start with the Ts and Es, you can find some likely Hs and then move on to the Rs and Ss and Is, by looking for possible "there", "these" and "this" occurrences. Once you have managed to reconstruct parts of one alphabet you can transfer that knowledge to other lines. It's a bit tedious and I find that Excel can be quite useful for helping with the text manipulations.

>KelvinY...
Yeah, that was the impression I'd gotten... and what I'm currently working on... =]

Since this one is still proving difficult I will give you the Es and Ts for each stream. You will notice that the streams do not all follow the standard ETAION SHRDLU frequency distribution, which should be no surprise, as some variation must be expected.

Stream 1 2 3 4 5 6 7
E         Q X F T Y A B
T         M V C R E S A

Hi there

Well, it's not that it's difficult (now you've explained most of it thanks!!!), but the thing that has put me off is that it's somewhat tedious. I created an Excel document to do all the Index of Coincidence stats (I and K), and found a tool that counts letter frequencies. Taking a paper and pencil & seperating into streams and doing ETAION SHRDLU on each one, then putting it back together requires a little more time than I can afford, though I can see the way through it.

It should be fairly straightforward to write a small program that could offer a number of text tools that do all this...perhaps I can start something off.

Jason

TYPO: The character the represents E in stream 4 is a V not a T.

The list above should have been

Stream 1 2 3 4 5 6 7
E         Q X F V Y A B
T         M V C R E S A

Apologies to anyone who has been "fooled" by this mistake.

I just thought I'd share a quick and dirty VB to strip apart a string:

Function strip(a As String) As Variant

  x = Len(a)
 
  For y = 1 To x
    q = Mid(a, y, 1)
    If q >= "a" And q <= "z" Or q >= "A" And q <= "Z" Then
      strip = strip & q
    End If
  Next y
 

End Function

Function pullapart(a As String, q As Integer, Optional r As Integer = 0) As Variant

  a = strip(a)
 
  x = Len(a)
 
  ReDim pa(q)
   
  For z = 1 To q
    For y = 0 + z + r To x Step q
      pa(z) = pa(z) & Mid(a, y, 1)
    Next y
    If z > 1 Then
      pullapart = pullapart & "," & pa(z)
    Else
      pullapart = pa(z)
    End If
  Next z
   
 

End Function

*****

I'm going to assume people know how to process this since it's too much trouble not too...
The function is ran with pullapart(a,q,r), where:
a = the string
q = the number of characters in the key
r = any offset (optional)

It's not checking to see if you put stupid values in q or r and it will obviously die if there are double quotes in the string.

Another clue. I have added the substitutions for the letter A to the known list, which now looks like.

#: 1 2 3 4 5 6 7
E: Q X F V Y A B
T: M V C R E S A
A: R Z G W B Y C

Here is the second message


A problem that has always faced cryptanalysts is getting enough text to derive meaningful statistics.  Scientific cryptanalysis relies heavily on statistics such as frequency counts of single letters digraphs and trigraphs.  Each language has unique characteristics that appear once enough text has been collected and can be used to reveal the underlying message in a cipher.  It is the goal of the code breaker to collect enough text to accomplish his mission of revealing the hidden messages.  Meanwhile, the code maker tries to make it harder to break his codes while still sending enough information for his messages to be useful.

-Keola75

Nice work, Keola. You obviously cracked that long before I posted the latest clue. I assume that you have cracked the first message too, in which case you may want to post it to get the 350 points for it. Then there is just the 50 points for cracking the final clue outstanding.

OK, you just did and you have a minor mistake in your answer. You still get the points though, because you have obviously broken it.

The correction to your decode is that "Dig bol" should actually read "Big boy".

That's what I thought...I must have typoed the encryption while I was working on it=)

Just waiting for the answer to the final cryptic clue "Big boy and confused agency are the making of a dangerous lunatic." before closing this one. I'm a little surprised that our resident cryptic crossword expert, dagesi, hasn't knocked it off yet. :/

Final clue: The answer is 6 letters long.

Hmmm... that lets out psychotic and sociopath...
=]

Hmmm... Big boy could be SAM, though that seems too vague... and agency could mean operation which could then be ADD making the total SADDAM...

dagesi,
Not SADDAM, although very topical. You're making it harder than it actually is. By your standards I would have thought this was a pretty straightforward clue. :P

WOOHOO! So ends our longest running crypto challenge. Well done, pkwan, keola75 and dagesi. The answer to the cryptic clue was indeed MANIAC. The points are yours and I will assign them after leaving the question open for a short while longer. Keola, please post a brief description of how you cracked the cipher if you get a chance. This week's cipher was a Keyed Vigenere cipher ( http://rumkin.com/tools/cipher/vigenere-keyed.php ), much like the one on the Kryptos sculpture, with a tableau key of NOTSOEASY and a cipher key of KRYPTOS.

The full Vigenere table was
  | NOTS EAYB CDFG HIJK LMPQ RUVW XZ
N | NOTS EAYB CDFG HIJK LMPQ RUVW XZ
O | OTSE AYBC DFGH IJKL MPQR UVWX ZN
T | TSEA YBCD FGHI JKLM PQRU VWXZ NO
S | SEAY BCDF GHIJ KLMP QRUV WXZN OT
E | EAYB CDFG HIJK LMPQ RUVW XZNO TS
A | AYBC DFGH IJKL MPQR UVWX ZNOT SE
Y | YBCD FGHI JKLM PQRU VWXZ NOTS EA
B | BCDF GHIJ KLMP QRUV WXZN OTSE AY
C | CDFG HIJK LMPQ RUVW XZNO TSEA YB
D | DFGH IJKL MPQR UVWX ZNOT SEAY BC
F | FGHI JKLM PQRU VWXZ NOTS EAYB CD
G | GHIJ KLMP QRUV WXZN OTSE AYBC DF
H | HIJK LMPQ RUVW XZNO TSEA YBCD FG
I | IJKL MPQR UVWX ZNOT SEAY BCDF GH
J | JKLM PQRU VWXZ NOTS EAYB CDFG HI
K | KLMP QRUV WXZN OTSE AYBC DFGH IJ
L | LMPQ RUVW XZNO TSEA YBCD FGHI JK
M | MPQR UVWX ZNOT SEAY BCDF GHIJ KL
P | PQRU VWXZ NOTS EAYB CDFG HIJK LM
Q | QRUV WXZN OTSE AYBC DFGH IJKL MP
R | RUVW XZNO TSEA YBCD FGHI JKLM PQ
U | UVWX ZNOT SEAY BCDF GHIJ KLMP QR
V | VWXZ NOTS EAYB CDFG HIJK LMPQ RU
W | WXZN OTSE AYBC DFGH IJKL MPQR UV
X | XZNO TSEA YBCD FGHI JKLM PQRU VW
Z | ZNOT SEAY BCDF GHIJ KLMP QRUV WX

The puzzle title and instructions were encrypted using ROT47.

The current points totals after this challenge are as follows:

maramom    1925
pkwan    1675
RobinD    1425
keola75    950
Infinity08    675
Zelicia    525
Jason210    450
danrosenthal    125
Gieron    100
dagesi    100
NicoLaan    100
Galisteo8    75
JR2003    50
snoyes_jw    50