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.

Below is the cipher text I am trying to break and as you can see its rather short which is why I am having so much trouble.

WOYFN ZCMSH VUVTG BFUTW ABTZP FHIMF TFOSU UXFQC HKVKG MPUUQ 
MHRXI OVBRZ EPJYF KKVJW GEIOV HUKEB JUNSM THIMF TFKUB ULMMQX

What I know about this ciphertext:

  • Key is 6 characters long and repeats (Given by the person who encrypted it)
  • There is a single character missing from the start of the ciphertext! (Also given)
  • It uses a simple cipher I believe a vigenere cipher.
  • Friedman IC: 1.143 (kappa-plaintext: 0.4396) which is why i think its a vigenere cipher

I have spent many hours on this but to be honest im not very good at breaking these codes.

My problem that iv run into is that once I break the cipher into its sections they are all very short and hence frequency alaysis fails.

I would really appreciate if someone could either confirm or find the crypto system being used as well as any more information about how one would find the plaintext + key or better yet find the key itself and explain how you manage it with such a short piece of ciphertext

Edit: There was some debate as to the validity of this question so here is some more information from my attempts:

Streams:

  • ?ZUUZFUKUXZKEKSFU IC = 3.6833 (kappa-plaintext: 1.4167)
  • WCVTPTXVUIEKIEMTL IC = 1.1471 (kappa-plaintext: 0.4412)
  • OMTWFFFKQOPVOBTFM IC = 2.1029 (kappa-plaintext: 0.8088)
  • YSGAHOQGMVJJVJHKM IC = 1.3382 (kappa-plaintext: 0.5147)
  • FHBBISCMHBYWHUIUQ IC = 1.5294 (kappa-plaintext: 0.5882)
  • NVFTMUHPRRFGUNMBX IC = 0.9559 (kappa-plaintext: 0.3676)

These numbers don't look good. they are almost all drastically off normal distribution for any language.

The main point to my question is:

  • Does Vigenere Seem like a reasonable fit (given those streams are correct)?
  • Is it possible to use that analysis in any way? I cant see how it can be effective with only 17 characters per stream. Most letters frequencies are 0.
  • What other ciphers are possible? How could I identify that they are in use?

I am happy to provide more information I am just not sure what else is useful.

share|improve this question

migrated from security.stackexchange.com May 13 '12 at 18:07

This question came from our site for Information security professionals.

2  
Alas, this question is not really on topic for crypto.SE either. The FAQ is pretty clear about it. (Personally, I kind of like these kinds of questions, at least as long as they look reasonably likely to be answerable and show more research effort than just "please break this cipher for me", but the consensus seems to be that they're all off topic here.) –  Ilmari Karonen May 13 '12 at 22:48
1  
I disagree with the fact that this isn't the place to ask. Reading the FAQ it says that its not ok to "Can I challenge people to decode something?" but it does also say that you can ask homework questions. I believe thats what im asking. I am not really after the solution more how would one approach this question given the limited ciphertext and that I have tried the attacks I know of. –  Nick May 14 '12 at 3:15
2  
As I wrote that FAQ, I'll weigh in with what I think - the "challenge people to decode something" was meant to deal with "please decode XYZ bet you can't !11!!1"-type questions, of which we've had a few. It's not meant to discourage questions which are a decent attempt at cryptanalysis, although I think they do need to be reasonably answerable. As is, I think we could do with as much information as you can give - perhaps the results of your frequency analysis, for example? However, I don't see the need to fire a mod close vote at it, although the community or other mods may disagree :) –  Ninefingers May 16 '12 at 9:45
    
Also, if you feel the FAQ can be improved, do weigh in on meta :) –  Ninefingers May 16 '12 at 9:45

4 Answers 4

I don't know the solution, but since you say you're only asking for hints, here's a few that occurred to me:

  • If this is a Vigenère cipher, the missing character at the beginning should not matter (much): if you encrypt a message with the key FOOBAR and drop the first letter of the output, you can decrypt the resulting ciphertext with the key OOBARF.

  • As ewanm89 notes, the obvious way to attack a Vigenère cipher, after you've determined the key length is $n$, is to write it with $n$ letters per row and attack each column as if it were a Caesar cipher. There are automated tools for doing that, such as pygenere; they may not always give the correct answer for very short messages, but yours looks long enough that they should at least have a decent chance.

  • The most notable feature I see in your ciphertext is that the string HIMFTF occurs twice, at offsets 26 and 86. That does strongly suggest that the key length may be a divisor of 60; alas, 60 has lots of small divisors (including 6, which you believe the key length to be), so that doesn't really give that much information. It does at least rule out 7, 8 and 9 as likely key lengths.

share|improve this answer
    
Hey thank you for the advice, I had noticed the HIMFTF myself. but the reason why I know the length is 6 is because the person that encrypted the message (The tutor for my class) told me that it was 6 long and that it repeats. –  Nick May 15 '12 at 0:16
    
PS I have now tried Pygenere again and it does not yield the message. Keep in mind that I am only guessing that this is Vigenere. Is there any way to work out if that is correct? –  Nick May 15 '12 at 0:17

The easiest way in this case to work out if it is vigenere is to brute force it.

You know the key is only 6 characters. Take a vigenere decryption function and a dictionary file of 6 character words. Decrypt using the first word, then compute a histogram of the resulting plaintext. Compare with what you would expect to see given the distribution of characters in english language text. If the two are close, visually inspect. If they are not close or visual inspection fails, continue.

Look around on google for histogram comparison ideas. A simple sum of differences should work then set a threshold for what to display.

share|improve this answer
    
Cryptool is a nice crypto learning tool that supports classical cipher cryptanalysis such as for Vigenère ciphers. There is also an online version, but I'm not sure whether this only works for the German page or also for the English page. –  DrLecter Dec 17 '13 at 15:12

As already stated it is a Vigenere cipher. Here even the length of the key is already known. A principle approach to break the cipher is as follows:

Try different keys. For each key construct the corresponding clear text and check how similar the clear text is to the English language.

How well this algorithm works depends on how good your check for the English language is. So you need a function, which takes a decoded clear text as input and returns a measure for the probability that the text is English. Such function is called fitness function, the returned value is the fitness of the clear text. The fitness function is not restricted to the Vigenere cipher, it can be used for breaking other ciphers as well.

Now most Vigenere solvers are looking at the frequency of single letters, which means the fitness function is based on so called monograms. This works more or less well if the cipher text is much longer than the key. For the cipher given here those solvers will probably not determine the correct key.

Instead of counting the frequency of single letters it is much better to count the frequency of bigrams, i.e. you are looking always at two neighboring letters of the clear text. This greatly improves the accuracy of the fitness function.

There are 26 different monograms (A..Z) in the English language, but 26*26 = 676 bigrams (AA..ZZ). Thus using bigrams will probably require a computer program, while using monograms the cipher can still be broken by hand.

So let's assume you have a table which provides for each bigram the probability that it occurs in English text (the most frequent bigram of the English language is "TH" [~2.7%]) . One option to implement a fitness function is to multiply the probabilities of all bigrams of the clear text. The greater the resulting value, the more probable it is that the text is English.

So you just need to find the key where the resulting clear text has the highest fitness value.

A brute force over the complete solution space (key length = 6 => 26^6 possible keys) is not needed, it is sufficient to look at neighboring letters of the key only.

Using this approach the cipher text given here can be broken rather easily. The algorithm is implemented here: http://www.guballa.de/pages/geocaching/vigenere-solver.php

I have also provided a more detailed description of the algorithm (http://www.guballa.de/pages/bits-bytes/implementierung-eines-vigenere-solvers.php), but that's in German.

Using trigrams (or even quadgrams) would make the algorithm even stronger.

I found that it is even possible to break Vigenere ciphers if the cipher text is only as long as four times of the key length.

share|improve this answer
    
Additional resource which explains rather well the fitness function: practicalcryptography.com/cryptanalysis/text-characterisation/… –  Jagu May 1 at 17:45

I can confirm that this can be solved as a Vigenere cipher. The decoded message reads [c]ongratulations on solving the puzzle we hope you enjoy computer and network security and the wargames puzzles good luck.

share|improve this answer
4  
Hello Eli and welcome to Crypto. There is a word: "If you give a man a fish, you feed him for one night. But if you teach him how to fish, he will be fed for the rest of his life." I think, it will be more helpful, if you explain how your approached the problem instead of spoiling the solution. But congratulations for finding it. –  Hendrik Brummermann Jun 15 '12 at 6:46
4  
Eli, I would have to agree with Hendrik. Of course one can find the key from your solution, but that doesn't help the OP learn how to actually find the key in future problems. –  Thomas Jun 15 '12 at 13:08
1  
I agree with the others on providing a little explanation as to how you decoded this. I don't think it needs to be a step by step guide, but a brief overview of what you did would no doubt steer the OP in the right direction :) –  Ninefingers Jun 15 '12 at 21:41
3  
Thank you for decryption this. Although I have to agree with the comments above. If in the exam they ask "How would you attack this cipher if you were given this info" I don't think they would be to impressed if i said "Post to crypto.stackechange.com". I would be interested to know how you achieved this so I could do it again to a different ciphertext with a different key/plaintext. –  Nick Jun 17 '12 at 22:31
1  
@Nick, the explanation is right above. Attacking a Vigenere cipher with known key length is trivial. Let me repeat. You feed the cipher with various keys of that length and count digrams in decrypted gibberish until you hit some threshold. At this point there would be few partially colliding keys that would partially decrypt the message. Look at these, reconstruct the rest of the message and roll it back to the original key if you must. –  Eli Jun 18 '12 at 7:10

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.