### Thread: Challenge on Vigenere encrypted ciphertexts

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

2.2)
JYENCIGJEHGELEIXWIDRNEWSJQZCJVFOKIF
OLZQIVCTLEYFBTLRUBYSTAFZCBEGMYDUKBJ
JYYHIVLIMZJMVIHKAAOCQMDQODHLELFYMYD

2.3)
INNHUUUKILSIPJUEEYUDKRYDRCBRBCXEQHVLKWER
WYDNOMKLDYBIIIUTKACHHEHKQBTXAUDZYJTZXPKA
QBUWEKMJLCQDQEOLZELIBLKMTIYMGPHAOHQHBPTL

SHA256 plaintext = a116c4b23801f1491e39765f31a1ebbea4eda3010b740243da7090dcdaeb50df

2.4)
NWHLRSIDVCWPMOJKYJFEJVFSYCGNFVAOSCAX
FDBKKLUOHGWTINJAHURWCGOHBJKUGDOFANFJ
LIIYSKYCJBTGFHDFFNHZUENVARWAGWBWDMLR

2.5)
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. 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?
3. 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.
4. 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..................................```
...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
5. 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
ZZIOHVTMFRXVJRBHVEPOYDBLLJHSRKHIKLFXPT
MKHUXJQYDJXUCZEZSTDGVGOGRICIGNBEOZIYSO

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.
6. 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.