#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    144
    Rep Power
    60

    Challenge on Vigenere encrypted ciphertexts


    Just out of curiosity I like to post a challenge on Vigenere encrypted
    ciphertexts.

    As we all know, the Vigenere cipher is badly broken, except for one kind
    of usage - if the key is randomly and unique and as long as the plaintext.

    Obviously a very impractical solution, because we would need to share a
    bunch of such randomly and unique cipher keys in advance with our
    communication partner and we need to keep track of every key used.
    Effectively just as encrypting with a OTP.

    Perhaps there might be a simple solution how to take advantage of such
    randomly and unique cipher keys - by using a nonce/IV alongside the
    ciphertext. This way we can re-use a pre-shared key over and over again
    with the Vigenere encryption. There is just one point of critique, that
    the nonce/IV is double the size of the plaintext. Essentially this would
    mean in practice that the scheme might only be practical for the
    exchange of short text messages.

    Okay now let's have a look how it works.
    Code:
    1) We need a randomly and unique IV double the length of the plaintext.
       It can be generated using a PRNG or a dice and a alphabet square, like 
       below
       
            1  2  3  4  5  6
          +------------------
        1 | A  B  C  D  E  F
        2 | G  H  I  J  K  L
        3 | M  N  O  P  Q  R
        4 | S  T  U  V  W  X
        5 | Y  Z  0  1  2  3
        6 | 4  5  6  7  8  9
        
      The first die roll selects a row in the table and the second a column. 
    
      So, for example, a roll of 2 followed by a roll of 4 would select the
      letter "J" from the table above. To generate upper/lower case
      characters or some symbols a coin flip can be used, heads capital,
      tails lower case. Using the table above we can include numbers as
      well.
    
      Assuming we have a plaintext like
      
        This Plaintext does not contain any Number
      
      and we use only capital letters, prepared for encryption it would read 
      
        THISPLAINTEXTDOESNOTCONTAINANYNUMBER
    
      So the generated IV, double the length of the plaintext, could read like
      
        URKFYEUXZSWHYCTDZDBYLYPNVRRLIFSCCVPUULLRHQTGSFYALDBZYXWTOFKSTIZDSVWTKJST
    
    
    2) In this step we encrypt the IV with our pre-shared secret key, which read
    
        THISISOURSECRETKEY
        
       As result we have an encrypted IV
       
        NYSXGWIRQKAJPGMNDBUFTQXFJLIDMHJGVFTSNSTJPIHAJXCCCHUJCVPAWXSKHCQVWXNXDTWR
    
        
    3) Now we split the encrypted IV in two parts of equal length
    
        NYSXGWIRQKAJPGMNDBUFTQXFJLIDMHJGVFTS
        NSTJPIHAJXCCCHUJCVPAWXSKHCQVWXNXDTWR
    
    
    4) In this step we encrypt the upper part of the encrypted IV using the lower as 
       its key which will give as the actual cipher/encryption key
        
        AQLGVEPRZHCLRNGWFWJFPNPPQNYYIEWDYYPJ
        
        
    5) Now we are ready for encryption of the plaintext using the previously generated 
       cipher key
        
        THISPLAINTEXTDOESNOTCONTAINANYNUMBER
        AQLGVEPRZHCLRNGWFWJFPNPPQNYYIEWDYYPJ
        ------------------------------------
        TXTYKPPZMAGIKQUAXJXYRBCIQVLYVCJXKZTA
        
    6) In the final step we send the original IV alongside the ciphertext
    
        URKFYEUXZSWHYCTDZDBYLYPNVRRLIFSCCVPU
        ULLRHQTGSFYALDBZYXWTOFKSTIZDSVWTKJST
        TXTYKPPZMAGIKQUAXJXYRBCIQVLYVCJXKZTA
    
    
    
    The receiver need to generate the cipher/encryption key first out of the IV using our 
    pre-shared secret key. He actually perform step 2 to 4 and now is able to decrypt the 
    ciphertext.
    
        TXTYKPPZMAGIKQUAXJXYRBCIQVLYVCJXKZTA
        AQLGVEPRZHCLRNGWFWJFPNPPQNYYIEWDYYPJ
        ------------------------------------
        THISPLAINTEXTDOESNOTCONTAINANYNUMBER
    That's it.


    And now the challenge. It consist of 2 times 5 combination of IV and ciphertext.

    The first 5 ciphertexts are build from the same plaintext using the same keyword.
    The plaintext and keywords do not contain any number or special character, they are
    in the range A-Z (capital letters).

    The plaintext is of natural English language.
    The pre-shared secret key is semantic, of natural English language as well, and
    12 characters long.

    Code:
    SHA256 of the Plaintext = d3ebaef74ffd5aca9d7194acd4c0856156241681c22fa62a90f9cee1c6825ab2
    
    1.1)
    UQLESGWLMBTLTGPQBEYVEKMGUAOXRWFRDYITJK
    HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
    SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ
    
    2.1)
    VTRBLXXGRDVYSKLBTMYWLRPLAGSNLZHUUHLBBL
    ZRYELBNGTHXORMRMOVNWUJVOUDUVNDBOKYOFQU
    LVILHHZDEWDDNBMTPJBJALZMCYJHGRJXUFPEZF
    
    3.1)
    JXTILGTUXZKOXFKSEYHQWYIIFETJEDATAVSEUE
    QPYZMPYBQEOOVQOENCAAJMUYXSXPFVOWKQDTTE
    QXKNIEGMHPJTWAICZCXHAVRTKLNXRNPEALLVVI
    
    4.1)
    YREXTOLNHFMGIVMYYXJSVKAWOXIIXBBPFVPBYL
    HWWQMDSDMKRNUQUFYJUMSFPTMTRGWDCMITGNGO
    WYTTQASHNBOKGQQJEITVIAECIFWNBTEQDOLMMZ
    
    5.1)
    TJKNVLQYXYWTIFGKWCYHCNHSYQQKJNXWYWVQGI
    CNJDJWOCEDMISBYNVXCKJAGRGLAWTUIEVEACUD
    MHMWPQTRVNTSELODZBQIGYCWMQNFKWGPJALQIL
    The next five IV/ciphertext combinations are build from different
    plaintexts but the same key (not the one of 1.1 - 5.1). Again the
    plaintext is of natural English language, but the pre-shared secret key
    may be randomly chosen from the character range A-Z (capital letters).
    The plaintext and keyword does not contain any number or special
    character.

    Code:
    2.1)
    FFRMRBVIMHUURCKTMXBDECOVTNOYZLKHAUCG
    ZWFLLVIKLRWZLUTRIMJCPWYCJEJGVFGTSLJL
    KXEAPZMAQYQIGDAEYAKGZIJSFMJMCUEHKMXO
    
    SHA256 plaintext = 0adce11b1be0274cc606d9ca13cbed6aca38071e8b11a8e62922633a6ae7821d
    
    
    2.2)
    JYENCIGJEHGELEIXWIDRNEWSJQZCJVFOKIF
    OLZQIVCTLEYFBTLRUBYSTAFZCBEGMYDUKBJ
    JYYHIVLIMZJMVIHKAAOCQMDQODHLELFYMYD
    
    SHA256 plaintext = 3fa92ad44784381a319bff61c0763bec0da0e82fa8c37d507015f59e97043a20
    
    
    2.3)
    INNHUUUKILSIPJUEEYUDKRYDRCBRBCXEQHVLKWER
    WYDNOMKLDYBIIIUTKACHHEHKQBTXAUDZYJTZXPKA
    QBUWEKMJLCQDQEOLZELIBLKMTIYMGPHAOHQHBPTL
    
    SHA256 plaintext = a116c4b23801f1491e39765f31a1ebbea4eda3010b740243da7090dcdaeb50df
    
    
    2.4)
    NWHLRSIDVCWPMOJKYJFEJVFSYCGNFVAOSCAX
    FDBKKLUOHGWTINJAHURWCGOHBJKUGDOFANFJ
    LIIYSKYCJBTGFHDFFNHZUENVARWAGWBWDMLR
    
    SHA256 plaintext = 8e2dea7ad6eab85607b900649ff8d56c12bcb85b7d2bb1b8d197bbbf57195f70
    
    
    2.5)
    VNADFXYTOVFXYLGSFOKHBYQVNJUVUNSPZFJNMXOAZSL
    PQQWYPJMSHJRRHDYMEIWQKJVCKBTDOMRHRZCIRQXQHC
    ATHHDGGDZVITUBAWKICYFAPXAMRENNBIWAVSUHKIGAC
    
    SHA256 plaintext = a6c93957798fa27347397097948533475b14b6472939b265576ff91fa737c7be
    Now I'm very curious if this can be broken and if yes, how.

    Well than, good luck!

    Cheers,
    Karl-Uwe
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    144
    Rep Power
    60
    Well now, I like to mention that there is of course the option of brute
    force in finding at least the secret key of challenge 1.

    If we assume that a recent regular desktop PC would be able to generate
    8 billion keys per second, generating all possible keys would take
    about 128 days. Of course having much more computing power can solve
    this in a matter of minutes.

    And due to the birthday paradox, the knowledge of the key length and the
    fact that we also know that the key is of natural English language -
    therefore semantic - a potentially sophisticated algorithm might
    reduce the needed time further more.

    If we would have a specially crafted program that does the encryption of
    the IV and then the decryption of the ciphertext we can compare the hash
    in order to know that we have found the correct plaintext.

    With challenge 2 it's a bit more complicated as we don't know the length
    of the key used.

    Even a frequency or auto-correlation analysis will not work, because
    every IV is generated randomly and encryption with the secret key
    doesn't change this randomness.

    If you like you can verify that quit easily on your own at the following
    websites

    Vigenere Solver - www.guballa.de
    https://f00l.de/hacking/vigenere.php
    My Geocaching Profile.com

    if you post in all five ciphertext for example.

    SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ
    LVILHHZDEWDDNBMTPJBJALZMCYJHGRJXUFPEZF
    QXKNIEGMHPJTWAICZCXHAVRTKLNXRNPEALLVVI
    WYTTQASHNBOKGQQJEITVIAECIFWNBTEQDOLMMZ
    MHMWPQTRVNTSELODZBQIGYCWMQNFKWGPJALQIL

    Obviously it can't be solved that simple.


    Is anyone aware of another solution which is considerably more effective
    than brute force?
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    144
    Rep Power
    60
    So far no idea other than brute force from the community. Maybe I should
    give a hint how the encryption can broken other then brute force.

    Imagine we would try every 3 letter word, then every 4 letter word, then
    every 5 letter word of the English language and would use them only to
    encrypt the first 3, 4, 5, and so on position of the IV, this would
    reduce the search space for the key drastically.

    A function would simply compare the decrypted result with a dictionary
    and sort out everything that looks somehow pormising.

    And now imagine we we didn't succeed up to 5 letters and are trying ever
    6 letter word.

    Imagine at a certain point we would try SAMPLE

    Code:
    1.1)
    UQLESGWLMBTLTGPQBEYVEKMGUAOXRWFRDYITJK
    HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
    SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ

    Code:
    UQLESGWLMBTLTGPQBEYVEKMGUAOXRWFRDYITJK HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
    SAMPLE..............................SA MPLE
    MQXTDK..............................BK TRMW..................................
    
    
    MQXT..................................
    TRMW..................................
    --------------------------------------
    FHJP..................................
    
    
    SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ  <= ciphertext
    FHJP.................................. 
    --------------------------------------
    NWWN
    Nothing useful so far.



    Now we try SIMPLE.
    Code:
    UQLESGWLMBTLTGPQBEYVEKMGUAOXRWFRDYITJK HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
    SIMPLE..............................SI MPLE
    MYXTDK..............................BS TRMW..................................
    
    
    MYXT..................................
    TRMW..................................
    --------------------------------------
    FPJP..................................
    
    
    SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ  <= ciphertext
    FPJP..................................  <= partial potentially cipher key
    --------------------------------------
    NOWN..................................
    There might be something, because there is a NOW. A potential candidate.
    The algorithm would sort out this result.



    And after a while we will reach to try SIMPLY
    Code:
    UQLESGWLMBTLTGPQBEYVEKMGUAOXRWFRDYITJK HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
    SIMPLY..............................SI MPLY
    MYXTDE..............................BS TRMQ..................................
    
    
    MYXT..................................
    TRMQ..................................
    --------------------------------------
    FPJJ..................................
    
    
    SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ  <= ciphertext
    FPJP..................................  <= partial potentially cipher key
    --------------------------------------
    NOWT..................................
    Hm, looks way better, because a sentence of the plaintext clearly could
    begin with

    NOWTHERE..............................


    It seems we get something worth inspecting closer.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    144
    Rep Power
    60
    It seems that we have a minor problem with the first cribs.

    For example even VENDOR could produce potentially a proper word, the beginning of
    JESMIN.
    Code:
    UQLESGWLMBTLTGPQBEYVEKMGUAOXRWFRDYITJK HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
    VENDOR..............................VE NDOR
    PUYHGX................................ UFPJ
    
    PUYH..................................
    UFPJ..................................
    --------------------------------------
    JZNQ
    
    SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ  <= ciphertext
    JZNQ..................................  <= partial potentially cipher key
    --------------------------------------
    JESM..................................
    And both, SIMPLE and SIMPLY, do produce perhaps something meaningful.
    Code:
    UQLESGWLMBTLTGPQBEYVEKMGUAOXRWFRDYITJK HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
    SIMPLE..............................SI MPLE
    MYXTDK..............................BS TRMW..................................
    
    
    MYXT..................................
    TRMW..................................
    --------------------------------------
    FPJP..................................
    
    
    SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ  <= ciphertext
    FPJP..................................  <= partial potentially cipher key
    --------------------------------------
    NOWN..................................
    
    
    UQLESGWLMBTLTGPQBEYVEKMGUAOXRWFRDYITJK HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
    SIMPLY..............................SI MPLY
    MYXTDE..............................BS TRMQ..................................
    
    
    MYXT..................................
    TRMQ..................................
    --------------------------------------
    FPJJ..................................
    
    
    SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ  <= ciphertext
    FPJP..................................  <= partial potentially cipher key
    --------------------------------------
    NOWT..................................
    NOWN could lead to NOWNOTHINGNEW...
    ...while NOWT could become NOWTHESECRETMESSAGE...

    The problem is, that we only have the same plaintext encrypted with the
    same key, which doesn't help much. We clearly need some fresh
    ciphertexts in order to verify the correctness of the first part of the
    potential key.

    And here they are. Two different plaintexts encrypted with the same
    secret key as 1.1 to 1.5.
    Code:
    1.6
    SBNFXBMFHOKQMTSFPFISCUSDVFVGWGQLGPKUCQDF
    FPNBQZNYVJRVJBDLQBLUJICISEXEFRRKLYJDWHTN
    ANGCROLWBVBOFXWWMGFREUFPCEUFBGMYKHJGBRRP
    
    SHA256 plaintext = acf1f0803b34c53f65b441bc594d17f1a23c9bc31a26cbca2a31a4254ff4177d
    
    
    1.7
    BLJOGBTZTQZOSWHPMMOKLYGQJXPOYWDMRXWWSLQTWLFNNOUWQXSRJWURU
    LWGGXIIUMDWBQUCSQBVTCKPTROHWGJGEMISEKAEWOHTBUUPLDRCORPIPX
    WDNGMFQPSSHCWTAAJJDEOGAYDIUHSIJYWCXAGTWYAZSPUKEGLRYCDLYYX
    
    SHA256 plaintext = d44259ae5dd536ba2332e97396312b0f6e150503046010ec0bbbe68d0458673f
    And by the way, a nice wordlist of the English language is available over here
    http://www.bestwordlist.com/index.htm
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    144
    Rep Power
    60
    Here are four more triplets, same plaintext length as 1.1 to 1.5,
    encrypted with the same secret key.
    Code:
    1.8
    TFGVBKDYRCLBJQUNVXTFNWHQMKDYDTXBAWKVLJ	
    VHEPESLVWVLIBGRFIMHGMEBXUMRPFGWWODXDAB
    GWJBJNLSIFVXTYMWLBQRSIMGDXOTEECSHLQKIO
    
    SHA256 plaintext = aab93b3f93827963f00257998200245476be5163b6063190528cd1bb629fdb20
    
    
    1.9
    UDCLZQWYXRXTWEGNADNJPJNEYPSKENPVSSOOVH	
    ZZIOHVTMFRXVJRBHVEPOYDBLLJHSRKHIKLFXPT
    MKHUXJQYDJXUCZEZSTDGVGOGRICIGNBEOZIYSO
    
    SHA256 plaintext = a17d5a3eb3bf9d5949fa18ab4de62de181485ca5f00c049a5f1c5b8ad63d6b19
    
    
    1.10
    PUMDZKWLLZQHNZNIGXWOBOYQOZYKGURJYGYOXI	
    ICPVSEJLDPJXPKIUBQCDZDHBZJUEKWVEUVMYNC
    QEYTIMGKPEIDNKKPXWGMVFUECNZFNCNWEXZZSY
    
    SHA256 plaintext = e4b1a8cf95eeed90696a2ff66d444f52110a67a85b1cd3122b9d471f78212b0c
    
    
    1.11
    GRKEIRWYBICGFDMKFTDDULEURMLVRWENPJSBZS	
    NYVGBRYXNDYKXPYOBEJOVCCXFXIBLBBFAKHBLO
    PMOBYRESPAFQYIHYYVQMOKNXITJNDVCBYFAWFH
    
    SHA256 plaintext = 4e516063bfa7457d41b11a1641d8a3a0b3025a51bc65d27be307af799e975090
    The reason for the same length of these plaintexts is mainly to keep the
    shift of the key, when encrypting the IV, in a constant distance. This
    should make it a bit easier verifying that the proper beginning of a
    potential key was found.
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    144
    Rep Power
    60
    *** ATTENTION ***

    Due to a loss of data this challenge is considered as withdraw!!!

    I'm terribly sorry.

IMN logo majestic logo threadwatch logo seochat tools logo