Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

The cipher is an triple key polyalphabetic cipher also known as an Quagmire IV by the ACA. An example would be here: Quagmire IV example and info (pardon the ads)

I posses the IV key and the PT key. The IV key runs vertically and sets the shifts of the lookup alphabets for the ciphertext. The IV key is the length of the PT and is an plain English phrase. The PT key sets the shifts of the plaintext lookup alphabet. The length of the PT is ~120 characters, is in plain English and I possess an crib consisting of 4 letters and it's location in the ciphertext.

I have read and tried to adapt this method of solving a Quagmire IV but it deals with recovering the PT without the PT key but it does give insight. E.g. if we know the CT key and the IV key, the PT can be reduced to an simple substitution cipher.

I have attempted to attack the cipher using other methods used to solve polyalphabetic ciphers like Kerckhoff's principle and Kaliski but these and other methods I have used to solve simpler polyalphabetic ciphers have not yielded anything.

The question is what is the best manner of attack for this sort of cipher? Even the smallest bit of info about the CT key would be useful. E.g. if I found that the CT key length was 6, I could brute force it. I am not looking for solutions but more techniques/attacks that have some validity to them.

Edited for cipher details (below)

CT

JOZIPMTOHWBFAZPACLRKOHOYSVHLKKRCQTUKJGBGKLCPRFOOACGCFTTDSIQPQRAFKDPMTRXSFOGTKMJRIJGNUTUCVAZNGNNMKAAAMXPLTQCXNQPDJPOKPFA

IV Key

THERESAVOICETHATKEEPSONCALLINGMEDOWNTHEROADTHATSWHEREALWAYSBEEVERYSTOPIMAKEIMAKEANEWFRIENDCANTSTAYFORLONGJUSTTURNAROUND

PT Key

UPSTAIR

Crib

RXSF == THEY

share|improve this question
add comment

2 Answers 2

up vote 0 down vote accepted

I can't comment yet and have no solution, but I still wanted to post my own analysis and hope it'll get you a bit further. BTW, the site you linked to with the info about Quagmire IV is mine and yes, sorry about the ads! I haven't updated it in many, many years, so I was surprised to see it pop up :)

The first thing to do is try to find plausible candidates for letters in the keyword. I'm absolutely assuming the CT key was produced in the same way the PT keyword was, i.e. a keyed alphabet and not a completely random one. The latter case will require hill-climbing algorithms and is not in scope at this time.

From the crib I could deduce:

  • P and R are 3 letters apart (2 between them). Since in the regular alphabet there's only one between them, I think both are used in the keyword. PxxR. If you put the R in front, the P ends up at the back of the alphabet and this is unlikely, since that would require almost every letter after the P in a regular alphabet to have been used in the keyword.
  • I and X are 13 letters apart. I think the I is not part of the keyword, because if you put the I at the front somewhere the X is totally out of place somewhere in the middle and it could only be the 11th, 12th or 13th letter in the keyword and I assume the keyword is shorter.
  • However, the X may be part of the keyword, since the I ends up near its original location when the X is put at the front, but this requires that at least 5 letters that normally come after the I appear in the keyword, plus one extra letter for every position that X moves to the back. This makes it more likely that the X is the first or second letter in the keyword, than any other.
  • The M and S are 10 letters apart, where normally they are only 6 letters apart. This implies that either one of them was used in the keyword. Both are possible, since the other letter would end up reasonably close to their original positions in the alphabet. If the M was used, it is most likely one of the last letters in the keyword; if the S was used it is likely one of the first three or four.
  • The A and F are 24 letters apart, as opposed to the original 5 letters. From this it is highly unlikely that the A alone was used, since that would leave the F way at back of the alphabet. Either both were used in the order of FxA, with one letter between them, or the F alone was used as the second to last letter of the keyword and the A is the beginning of the padding.

Putting this all together, I believe the keyword definitely contains P??R, S or M, and F?A, not necessarily in that order. It may contain an X at the beginning as well.

share|improve this answer
1  
So your comment about the hill-climbing algorithm helped. I created a dictionary attack along the lines of a hill climber and it returned: REJOICE, which I then was able to figure out that the actual CT key was: REJOINS. –  christiangeek Feb 14 '13 at 19:47
    
Nice! And how sadly wrong I was about the letters... did the other letters of the keyword appear in alphabetical order? –  John Willemse Feb 14 '13 at 21:37
    
the PT Key was aligned under the letter 'q' instead of 'a' so that was probably the curve ball. My hill climber was based on the I.C. so even though the output was scrambled and did not appear to be PT, it had the same I.C. as PT so I then knew I needed to descramble it to recover the PT (based on that method I posted in my OP). After that and some massaging of the CT key, I could work backwards to reconstruct the tableau. –  christiangeek Feb 15 '13 at 17:28
add comment

I still can't comment but I'm trying to solve it. If I succeed I'll tell you how I did it but it'll be a bit of a mess. Could you check my working and see if he crib works out correctly if I choose the key XSPYFR. Basically I lay out the encryption as in the explanation and then I fill in a blank key and look at the encryption/ decryption of the crib. From the first letter of the crib it looks like the key must have P__R and from the third character it looks like it should start with an S. From the last character of the crib it looks like it should contain an F. And the second character seems to constrain the number of letters in the password from I to X to two or else X is in the password. This is all assuming the password is quite short.

share|improve this answer
    
a valid suggestion, I updated my question –  christiangeek Feb 4 '13 at 16:15
    
yes the key that is missing is the corresponding key to DRUMROL(L) in the example –  christiangeek Feb 4 '13 at 17:49
    
I could not get the crib to line up correctly using XSPYFR as the key –  christiangeek Feb 5 '13 at 18:44
    
The IV characters corresponding to the crib are "PIMA" yes? The crib row contents I have are P Y F R A B C D E G H I J K L M N O Q T U V W Z X S R T T <br/> I J K L M N O Q T U V W Z X S P Y F R A B C D E G H X H H <br/> M N O Q T U V W Z X S P Y F R A B C D E G H I J K L S E E <br/> A B C D E G H I J K L M N O Q T U V W Z X S P Y F R F Y Y <br/> –  Barack Obama Feb 5 '13 at 19:01
    
The first keyed alphabet is **U P S T A I R B C D E F G H J K L M N O Q V W X Y Z ** –  Barack Obama Feb 5 '13 at 19:08
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.