7
$\begingroup$

I was watching a Stanford lecture on Vigenère cipher and in it the professor said that – to break the cipher – we assume the length of the key is known. We then break the cipher into groups of this known length and then pick up (successively) the first, second, etc. members of each group and then break each of these using Caesar cipher.

The problem is: how would one break the cipher if the message length is short? Because then, we can not use the method which utilizes the frequency of letters to break the code.

For example:
Given the ciphertext ZZZJUCLUDTUNWGCQS and key is of size 6, can you crack this?
(Assuming you don’t know that the plaintext is WHATANICEDAYTODAY and the key is crypto.)

Improve this question
$\endgroup$
12
  • $\begingroup$ How short is "short" in the cases you want to consider? You have an answer so far, for "as short or shorter than the key". $\endgroup$
    – Neil Slater
    Commented Jul 10, 2014 at 12:41
  • $\begingroup$ I just gave an example for the cipher I'd like to be broken.Given the ciphertext ZZZJUCLUDTUNWGCQS and key is of size 6,can you crack this? $\endgroup$
    – user3676846
    Commented Jul 10, 2014 at 12:47
  • 1
    $\begingroup$ Frequency analysis will not help with that size of message. Instead you need to try a few things to optimise search for the correct key. There are also only 308915776 possible keys for a brute-force search, which importantly is smaller than the size of your possible message space, so you have enough information to discard junk decrypts. If this is a challenge, I'd start with all English 6-letter words though. $\endgroup$
    – Neil Slater
    Commented Jul 10, 2014 at 13:14
  • $\begingroup$ how did you arrive at the number of possible keys for brute force?and what do you mean by my possible message space and discarding junk decrypts?I'm sorry if these are obvious as I only just got started! $\endgroup$
    – user3676846
    Commented Jul 10, 2014 at 14:39
  • 2
    $\begingroup$ WHATANICEDAYTODAY was the plain text and the key is crypto $\endgroup$
    – user3676846
    Commented Jul 10, 2014 at 20:02

4 Answers 4

Reset to default
9
$\begingroup$

If the message is shorter than the key, then the Vigenere cipher is essentially the one-time pad, which is unbreakable for a random key. If the key is not random, then you may get some information on the plaintext.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ The message can be the same size as the key and still have the security of OTP. $\endgroup$
    – mikeazo
    Commented Jul 10, 2014 at 12:26
  • $\begingroup$ thank you for the info but my question does not pertain to this case.the key is shorter than the plaintext and is indeed replicated.i am confused regarding how to do frequency analysis if the plaintext is short,but not shorter than the key.As an example, how would one break the vigenere cipher ZZZJUCLUDTUNWGCQS given that the secret key is of size 6? $\endgroup$
    – user3676846
    Commented Jul 10, 2014 at 12:45
  • $\begingroup$ @user3676846 With such a short message and a key-size of 6, it would be feasible to simply brute-force the little bugger. You could simply “dump-a-list” like the tool on this site (note: that tool only checks the “most-probable keys”, while brute-forcing would mean we check ALL keys) and then look at which potential plaintexts make most sense. If you’re able to learn or guess the language of the plaintext, you could even optimize it with a dictionary-comparison to narrow down the list of potentially successful candidates… $\endgroup$
    – e-sushi
    Commented Jul 10, 2014 at 15:31
5
$\begingroup$

For breaking a Vigenere cipher by frequency analysis the length of the cipher text alone is not the crucial part. What really matters is the proportion cipher_text_len/key_len, as this indicates how many characters of the clear text are encoded by the same character of the key.

For the example you provided this proportion is below 3. Frequency analysis based on monograms (single letters) as you described will definitely fail. You can try to break the cipher by using frequency analysis of bigrams, trigrams or quadgrams instead but even with this method breaking your example will probably fail. My experience is that using trigrams allows breaking Vigenere ciphers where the proportion cipher_text_len/key_len is around 4 or higher (this varies from cipher to cipher).

Knowing the key length is not so important in my opinion. Instead of using the Kasisky method or the Friedman method (which both only work if the cipher text is much longer than the key), a computer can simply brute force over the candidate key lengths.

Another approach is using word dictionaries, see here: http://www.sichere.it/vigenere_tool.php?language=EN

It looks like this tool can break extremely short Vigenere ciphers. It requires that the clear text as well as the keyword consists of words only which are found in the dictionary, if I am not mistaken.

BTW, another important information when breaking the cipher is the language of the clear text.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I meant that the proportion of the cippher text to key is small,just as you mentioned.Thank you for your insightful answer.So you mean that in case the ratio is small,only brute force is a reliable way? $\endgroup$
    – user3676846
    Commented Jul 10, 2014 at 20:07
  • 1
    $\begingroup$ First of all thanks for posting the solution. The tool for which I posted the link could not solve the cipher, probably because "crypto" is not in the dictionary. I encrypted the clear text with the word "powder", and the tool was able to break the resulting cipher. Instead of trying all of the 26^6 potential keys I would start with 6-letter words as the key first. Even if the key was chosen randomly not the complete solution space must be checked. So if your key starts with "ab...." and results in the clear text "qj....", then obviously you don't need to check the keys "abaaaa".."abzzzz". $\endgroup$
    – Jagu
    Commented Jul 10, 2014 at 20:54
  • $\begingroup$ By 6 letter words you mean words in the enlish dictionary,right?Also,when you say " if your key starts with "ab...." and results in the clear text "qj...." then does this mean that brute force doesnt output the entire key and plaintext in one go? (I am not sure how brute force would run in such a scenario,pardon me) $\endgroup$
    – user3676846
    Commented Jul 10, 2014 at 21:13
  • $\begingroup$ The example was intended to show that you can modify a brute force attack over all 26^6 keys and reduce the number of keys to check. You could iterate over the first two chars of the key first (aa..zz). For each of these 26^2 keys you would be able to decode the first two chars of the cipher. Based on the obtained two chars of the clear text you decide if you continue using the key (i.e. extending it to a full 6-char key) or if you go to the next iteration. It is a trade off between additional logic to spend and execution time. Hopefully the clear text does not read "qj is a seldom bigram". $\endgroup$
    – Jagu
    Commented Jul 11, 2014 at 16:53
3
$\begingroup$

This is a bit contrived, because you have given the correct answer to your test:

WHATANICEDAYTODAY was the plain text and the key is crypto.

However, it shows one way to attack a short Vigenère cipher, where you have a message only a few times longer than the key.

I made the following assumptions:

  • Plain text was a short English text

  • The key was a 6-letter English word. The approach could be extended to brute-force all possible keys, but would take much longer.

Pseudo-code (original was in Ruby):

words = <load list of English words from file>
possible_keys = <all 6-letter words plus first 6 letters of all longer ones>
test_words = <words 2 or more letters long, sorted reverse by length>
test_regexp = <regular expression that matches any item in test_words>

for each possible_key:
  try_plaintext = decrypt( cipher_text, possible_key )
  test_matches = <all matches of test_regexp against try_plaintext>
  if <more than 2 matches> and <total length of matches more than 11>
    print <properties of possible match>

I got the following output:

["CATEGO", "WYFENNITJONYTFILL", "FEN NIT JON FILL"]
["CATOCA", "WYFURBITJERMTFIBP", "FUR BIT JERM FIB"]
["CAULES", "WYEXPJITIHPUTFHEN", "WYE JITI PUT HEN"]
["CENOBY", "WULUSDIPPESOTBOBQ", "ULU DIP PESO BOB"]
["CHALTA", "WRYXABIMCHAMTYBEY", "WRY BIM CHAM BEY"]
["CHAPTE", "WRYTAXIMCDAITYBAY", "WRY TAXI AIT BAY"]
["CHUMPY", "WREWEDIMIGEOTYHDC", "REWED IMI GEOTY"]
["CHUVAS", "WRENTJIMIXTUTYHUR", "WREN TJI MIX TUT"]
["CHYLEM", "WRAXPPIMEHPATYDEN", "RAX PIM PATY DEN"]
["CHYMAS", "WRAWTJIMEGTUTYDDR", "WRAW TJI MEG TUT"]
["CLEPTO", "WNUTANIIYDAYTUXAY", "NUT ANI YDAY TUX"]
["CRAPPI", "WHYTETICCDEETOBAC", "WHY TIC DEE TOBA"]
["CRAPPO", "WHYTENICCDEYTOBAC", "WHY TEN DEY TOBA"]
["CRASSU", "WHYQBHICCABSTOBXZ", "WHY HIC CAB STOB"]
["CREATA", "WHUIABICYSAMTOXPY", "HUIA ICY SAM TOX"]
["CREATE", "WHUIAXICYSAITOXPY", "HUIA ICY SAI TOX"]
["CREATO", "WHUIANICYSAYTOXPY", "HUIA ICY SAY TOX"]
["CREEPM", "WHUEEPICYOEATOXLC", "HUE EPIC YOE TOX"]
["CRYALG", "WHAIIVICESIGTODPG", "WHA VICE SIG TOD"]
["CRYPTA", "WHATABICEDAMTODAY", "WHATA BICE DAM TODAY"]
["CRYPTE", "WHATAXICEDAITODAY", "WHATA ICED AIT ODA"]
["CRYPTI", "WHATATICEDAETODAY", "WHATA TICE DAE TODAY"]
["CRYPTO", "WHATANICEDAYTODAY", "WHATA NICE DAY TODAY"]
["CRYPTU", "WHATAHICEDASTODAY", "WHATA HIC DAS TODAY"]
["CRYSTA", "WHAQABICEAAMTODXY", "WHA BICE AAM TOD"]
["CYCLAM", "WAWXTPIVAHTATHZER", "WAW IVA TATH ZER"]
["CYCLES", "WAWXPJIVAHPUTHZEN", "WAW JIVA PUT ZEN"]
["CYCLOS", "WAWXFJIVAHFUTHZED", "WAW JIVA FUT ZED"]
["CYTORY", "WAFUCDIVJECOTHIBA", "WAF DIV COTH IBA"]
["DIOPTI", "VQKTATHLODAESXNAY", "TATH LOD AES NAY"]
["DOUBTI", "VKEHATHFIRAESRHOY", "HATH FIR AES RHO"]
["ECYPHE", "UWATMXGREDMIRDDAK", "WAT RED MIRD DAK"]
["ELAEOT", "UNYEFIGICOFTRUBLD", "NYE FIG COFT RUB"]
["ENNEAT", "ULLETIGGPOTTRSOLR", "ULL TIG POTT SOL"]
["EPOPTI", "UJKTATGEODAERQNAY", "TAT GEO DAER NAY"]
["ERUPTI", "UHETATGCIDAEROHAY", "HET CID AERO HAY"]
["ETHENI", "UFREGTGAVOGERMULE", "REG AVO GERM ULE"]
["ETHENY", "UFREGDGAVOGORMULE", "REG AVO GOR MULE"]
["GENERO", "SULECNEPPOCYPBOLA", "ULE NEP CYP BOLA"]
["GENOTY", "SULUADEPPEAOPBOBY", "SULU ADE PEA BOB"]
["GENYAN", "SULKTOEPPUTZPBORR", "SULK TOE PUT BOR"]
["GEOPLA", "SUKTIBEPODIMPBNAG", "SUK TIB POD IMP NAG"]
["GEOPRU", "SUKTCHEPODCSPBNAA", "SUK TCHE POD NAA"]
["GONOCO", "SKLURNEFPERYPROBP", "LUR NEF PER PROB"]
["GONOPO", "SKLUENEFPEEYPROBC", "LUE NEF PEE PROB"]
["GRAFTI", "SHYDATECCNAEPOBKY", "SHY DATE NAE POB"]
["GRAFTO", "SHYDANECCNAYPOBKY", "SHY DANE NAY POB"]
["GRANTO", "SHYVANECCFAYPOBCY", "SHY VANE FAY POB"]
["GRAPTA", "SHYTABECCDAMPOBAY", "SHY TAB DAMP BAY"]
["GRAPTO", "SHYTANECCDAYPOBAY", "SHY TANE DAY POB"]
["GREFFO", "SHUDONECYNOYPOXKM", "SHU DONE NOY POX"]
["GREMLI", "SHUWITECYGIEPOXDG", "SHU WITE GIE POX"]
["GRUFFI", "SHEDOTECINOEPOHKM", "SHED TEC INO POH"]
["GRUFFY", "SHEDODECINOOPOHKM", "SHED ODE INO POH"]
["GRUMLY", "SHEWIDECIGIOPOHDG", "SHE WIDE CIG POH"]
["GRUMPY", "SHEWEDECIGEOPOHDC", "SHE WEDE CIG POH"]
["GRUNTI", "SHEVATECIFAEPOHCY", "SHEVA TEC FAE POH"]
["GUDEFA", "SEVEOBEZZOOMPLYLM", "EVE OBE ZOOM PLY"]
["HAIRLO", "RYQRINDTUBIYOFTYG", "RIND TUB IYO TYG"]
["HEBEGY", "RUXENDDPBONOOBALL", "RUX END BON BALL"]
["HEIRLO", "RUQRINDPUBIYOBTYG", "RIND PUB IYO TYG"]
["HEXENB", "RUBEGADPFOGLOBELE", "RUBE GAD FOG LOBE"]
["HEXEST", "RUBEBIDPFOBTOBELZ", "RUBE BID FOB TOBE"]
["HEXYLI", "RUBKITDPFUIEOBERG", "RUB KIT PFUI OBE"]
["HOROLO", "RKHUINDFLEIYORKBG", "KHU IND LEI YORK"]
["HYDATO", "RAVIANDVZSAYOHYPY", "RAVI AND SAY HYP"]
["HYMETT", "RAMEAIDVQOATOHPLY", "RAME AID OAT PLY"]
["HYPOBU", "RAJUSHDVNESSOHMBQ", "RAJ USH NESS OHM"]
["INUREM", "QLERPPCGIBPANSHYN", "LERP GIB PAN SHY"]
["KENOTI", "OULUATAPPEAELBOBY", "ULUA TAP PEA ELB"]
["KETOXI", "OUFUWTAPJEWELBIBU", "OUF TAP JEWEL BIB"]
["KLEPTO", "ONUTANAIYDAYLUXAY", "NUT ANA YDAY LUX"]
["KNOBLI", "OLKHITAGORIELSNOG", "HIT AGO RIE SNOG"]
["KNUBBY", "OLEHSDAGIRSOLSHOQ", "OLE DAG SOL SHOQ"]
["KNURLE", "OLERIXAGIBIILSHYG", "OLE RIX AGIB SHY"]
["KNURLI", "OLERITAGIBIELSHYG", "OLE RITA GIB ELS"]
["KNURLY", "OLERIDAGIBIOLSHYG", "OLE RID AGIB SHY"]
["MAYBLO", "MYAHINYTERIYJFDOG", "MYA HIN TERI DOG"]
["MENYAN", "MULKTOYPPUTZJBORR", "MULK TOY PUT BOR"]
["OXYBLE", "KBAHIXWWERIIHIDOG", "BAH WERI IHI DOG"]
["REOPPO", "HUKTENTPODEYEBNAC", "HUK TENT POD EYE"]
["RUCHIN", "HEWBLOTZALLZELZIJ", "HEW BLOT ALL ZEL"]
["SLAINT", "GNYAGISICKGTDUBHE", "YAGI SICK DUBHE"]
["SLEETI", "GNUEATSIYOAEDUXLY", "GNU EATS IYO DUX"]
["SNEEZY", "GLUEUDSGYOUODSXLS", "GLUE UDS YOU ODS"]
["STAHLI", "GFYBITSACLIEDMBIG", "BIT SAC LIED BIG"]
["STHENI", "GFREGTSAVOGEDMULE", "REG AVO GED MULE"]
["STUPOS", "GFETFJSAIDFUDMHAD", "FET SAID FUD HAD"]
["SUNBLI", "GELHITSZPRIEDLOOG", "GEL HIT PRIED LOO"]
["SYNAPO", "GALIENSVPSEYDHOPC", "GALI ENS SEY HOP"]
["SYNOCH", "GALURUSVPERFDHOBP", "GAL URUS PER HOB"]
["UNHARM", "ELRICPQGVSCABSUPA", "ELRIC SCAB SUPA"]
["UNOBEY", "ELKHPDQGORPOBSNON", "ELK GOR POBS NON"]
["UNOBLI", "ELKHITQGORIEBSNOG", "ELK HIT GOR SNOG"]
["UNOBTR", "ELKHAKQGORAVBSNOY", "ELK HAK GORA NOY"]
["UNOBTU", "ELKHAHQGORASBSNOY", "ELK HAH GORA NOY"]

I am not claiming this approach is efficient, it was completely ad-hoc. Tests based on number and likelihood of English bigrams or trigrams in the tried plaintext might be more robust. Also you could probably avoid hard-coding target test metrics by dynamically setting them to be close to best-seen-so-far.

Improve this answer
$\endgroup$
0
$\begingroup$

You actually could use Key Elimination to do so in the given condition, but impossible if the key is random and as big as the plaintext (which makes it an OTP).

The trick is to, in your case, modular-subtract two consecutive blocks to get to get the two plaintext blocks combined (i.e., second plaintext block used as the key for the first plaintext block), or use XOR operator to do so in case of binary plain/cipher texts. Then, analyze the result to figure out the first and second blocks of plaintext.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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