Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
Challenge on Vigenere encrypted ciphertexts
Topic Started: Jun 4 2016, 03:57 PM (388 Views)
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
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)[space]We[space]need[space]a[space]randomly[space]and[space]unique[space]IV[space]double[space]the[space]length[space]of[space]the[space]plaintext.
[space][space][space]It[space]can[space]be[space]generated[space]using[space]a[space]PRNG[space]or[space]a[space]dice[space]and[space]a[space]alphabet[space]square,[space]like[space]
[space][space][space]below
[space][space][space]
[space][space][space][space][space][space][space][space]1[space][space]2[space][space]3[space][space]4[space][space]5[space][space]6
[space][space][space][space][space][space]+------------------
[space][space][space][space]1[space]|[space]A[space][space]B[space][space]C[space][space]D[space][space]E[space][space]F
[space][space][space][space]2[space]|[space]G[space][space]H[space][space]I[space][space]J[space][space]K[space][space]L
[space][space][space][space]3[space]|[space]M[space][space]N[space][space]O[space][space]P[space][space]Q[space][space]R
[space][space][space][space]4[space]|[space]S[space][space]T[space][space]U[space][space]V[space][space]W[space][space]X
[space][space][space][space]5[space]|[space]Y[space][space]Z[space][space]0[space][space]1[space][space]2[space][space]3
[space][space][space][space]6[space]|[space]4[space][space]5[space][space]6[space][space]7[space][space]8[space][space]9
[space][space][space][space]
[space][space]The[space]first[space]die[space]roll[space]selects[space]a[space]row[space]in[space]the[space]table[space]and[space]the[space]second[space]a[space]column.[space]

[space][space]So,[space]for[space]example,[space]a[space]roll[space]of[space]2[space]followed[space]by[space]a[space]roll[space]of[space]4[space]would[space]select[space]the
[space][space]letter[space]"J"[space]from[space]the[space]table[space]above.[space]To[space]generate[space]upper/lower[space]case
[space][space]characters[space]or[space]some[space]symbols[space]a[space]coin[space]flip[space]can[space]be[space]used,[space]heads[space]capital,
[space][space]tails[space]lower[space]case.[space]Using[space]the[space]table[space]above[space]we[space]can[space]include[space]numbers[space]as
[space][space]well.

[space][space]Assuming[space]we[space]have[space]a[space]plaintext[space]like
[space][space]
[space][space][space][space]This[space]Plaintext[space]does[space]not[space]contain[space]any[space]Number
[space][space]
[space][space]and[space]we[space]use[space]only[space]capital[space]letters,[space]prepared[space]for[space]encryption[space]it[space]would[space]read[space]
[space][space]
[space][space][space][space]THISPLAINTEXTDOESNOTCONTAINANYNUMBER

[space][space]So[space]the[space]generated[space]IV,[space]double[space]the[space]length[space]of[space]the[space]plaintext,[space]could[space]read[space]like
[space][space]
[space][space][space][space]URKFYEUXZSWHYCTDZDBYLYPNVRRLIFSCCVPUULLRHQTGSFYALDBZYXWTOFKSTIZDSVWTKJST


2)[space]In[space]this[space]step[space]we[space]encrypt[space]the[space]IV[space]with[space]our[space]pre-shared[space]secret[space]key,[space]which[space]read

[space][space][space][space]THISISOURSECRETKEY
[space][space][space][space]
[space][space][space]As[space]result[space]we[space]have[space]an[space]encrypted[space]IV
[space][space][space]
[space][space][space][space]NYSXGWIRQKAJPGMNDBUFTQXFJLIDMHJGVFTSNSTJPIHAJXCCCHUJCVPAWXSKHCQVWXNXDTWR

[space][space][space][space]
3)[space]Now[space]we[space]split[space]the[space]encrypted[space]IV[space]in[space]two[space]parts[space]of[space]equal[space]length

[space][space][space][space]NYSXGWIRQKAJPGMNDBUFTQXFJLIDMHJGVFTS
[space][space][space][space]NSTJPIHAJXCCCHUJCVPAWXSKHCQVWXNXDTWR


4)[space]In[space]this[space]step[space]we[space]encrypt[space]the[space]upper[space]part[space]of[space]the[space]encrypted[space]IV[space]using[space]the[space]lower[space]as[space]
[space][space][space]its[space]key[space]which[space]will[space]give[space]as[space]the[space]actual[space]cipher/encryption[space]key
[space][space][space][space]
[space][space][space][space]AQLGVEPRZHCLRNGWFWJFPNPPQNYYIEWDYYPJ
[space][space][space][space]
[space][space][space][space]
5)[space]Now[space]we[space]are[space]ready[space]for[space]encryption[space]of[space]the[space]plaintext[space]using[space]the[space]previously[space]generated[space]
[space][space][space]cipher[space]key
[space][space][space][space]
[space][space][space][space]THISPLAINTEXTDOESNOTCONTAINANYNUMBER
[space][space][space][space]AQLGVEPRZHCLRNGWFWJFPNPPQNYYIEWDYYPJ
[space][space][space][space]------------------------------------
[space][space][space][space]TXTYKPPZMAGIKQUAXJXYRBCIQVLYVCJXKZTA
[space][space][space][space]
6)[space]In[space]the[space]final[space]step[space]we[space]send[space]the[space]original[space]IV[space]alongside[space]the[space]ciphertext

[space][space][space][space]URKFYEUXZSWHYCTDZDBYLYPNVRRLIFSCCVPU
[space][space][space][space]ULLRHQTGSFYALDBZYXWTOFKSTIZDSVWTKJST
[space][space][space][space]TXTYKPPZMAGIKQUAXJXYRBCIQVLYVCJXKZTA



The[space]receiver[space]need[space]to[space]generate[space]the[space]cipher/encryption[space]key[space]first[space]out[space]of[space]the[space]IV[space]using[space]our[space]
pre-shared[space]secret[space]key.[space]He[space]actually[space]perform[space]step[space]2[space]to[space]4[space]and[space]now[space]is[space]able[space]to[space]decrypt[space]the[space]
ciphertext.

[space][space][space][space]TXTYKPPZMAGIKQUAXJXYRBCIQVLYVCJXKZTA
[space][space][space][space]AQLGVEPRZHCLRNGWFWJFPNPPQNYYIEWDYYPJ
[space][space][space][space]------------------------------------
[space][space][space][space]THISPLAINTEXTDOESNOTCONTAINANYNUMBER[space][space][space][space]

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.

Challenge 1 - click to show details


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.

Challenge 2 - click to show details

Now I'm very curious if this can be broken and if yes, how.

Well than, good luck!

Cheers,
Karl-Uwe



EDIT: another typo in the explanation
Edited by Karl-Uwe Frank, Jun 4 2016, 04:32 PM.
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
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

http://www.guballa.de/vigenere-solver
https://f00l.de/hacking/vigenere.php
http://www.mygeocachingprofile.com/codebreaker.vigenerecipher.aspx

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?
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
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[space]HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
SAMPLE..............................SA[space]MPLE
MQXTDK..............................BK[space]TRMW..................................


MQXT..................................
TRMW..................................
--------------------------------------
FHJP..................................


SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ[space][space]<=[space]ciphertext
FHJP..................................[space]
--------------------------------------
NWWN
Nothing useful so far.



Now we try SIMPLE.
Code:
 
UQLESGWLMBTLTGPQBEYVEKMGUAOXRWFRDYITJK[space]HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
SIMPLE..............................SI[space]MPLE
MYXTDK..............................BS[space]TRMW..................................


MYXT..................................
TRMW..................................
--------------------------------------
FPJP..................................


SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ[space][space]<=[space]ciphertext
FPJP..................................[space][space]<=[space]partial[space]potentially[space]cipher[space]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[space]HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
SIMPLY..............................SI[space]MPLY
MYXTDE..............................BS[space]TRMQ..................................


MYXT..................................
TRMQ..................................
--------------------------------------
FPJJ..................................


SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ[space][space]<=[space]ciphertext
FPJP..................................[space][space]<=[space]partial[space]potentially[space]cipher[space]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.
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
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[space]HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
VENDOR..............................VE[space]NDOR
PUYHGX................................[space]UFPJ

PUYH..................................
UFPJ..................................
--------------------------------------
JZNQ

SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ[space][space]<=[space]ciphertext
JZNQ..................................[space][space]<=[space]partial[space]potentially[space]cipher[space]key
--------------------------------------
JESM..................................


And both, SIMPLE and SIMPLY, do produce perhaps something meaningful.
Code:
 
UQLESGWLMBTLTGPQBEYVEKMGUAOXRWFRDYITJK[space]HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
SIMPLE..............................SI[space]MPLE
MYXTDK..............................BS[space]TRMW..................................


MYXT..................................
TRMW..................................
--------------------------------------
FPJP..................................


SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ[space][space]<=[space]ciphertext
FPJP..................................[space][space]<=[space]partial[space]potentially[space]cipher[space]key
--------------------------------------
NOWN..................................


UQLESGWLMBTLTGPQBEYVEKMGUAOXRWFRDYITJK[space]HCBSUDQHTBBUPCXAUIUTUMXJORIMDEPBGUAGOG
SIMPLY..............................SI[space]MPLY
MYXTDE..............................BS[space]TRMQ..................................


MYXT..................................
TRMQ..................................
--------------------------------------
FPJJ..................................


SDFCXSBJZOFWMNWWDOIFTHYCQGTICPVHZSYXFQ[space][space]<=[space]ciphertext
FPJP..................................[space][space]<=[space]partial[space]potentially[space]cipher[space]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[space]plaintext[space]=[space]acf1f0803b34c53f65b441bc594d17f1a23c9bc31a26cbca2a31a4254ff4177d


1.7
BLJOGBTZTQZOSWHPMMOKLYGQJXPOYWDMRXWWSLQTWLFNNOUWQXSRJWURU
LWGGXIIUMDWBQUCSQBVTCKPTROHWGJGEMISEKAEWOHTBUUPLDRCORPIPX
WDNGMFQPSSHCWTAAJJDEOGAYDIUHSIJYWCXAGTWYAZSPUKEGLRYCDLYYX

SHA256[space]plaintext[space]=[space]d44259ae5dd536ba2332e97396312b0f6e150503046010ec0bbbe68d0458673f


And by the way, a nice wordlist of the English language is available over here
http://www.bestwordlist.com/index.htm

cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
Here are four more triplets, same plaintext length as 1.1 to 1.5,
encrypted with the same secret key.
Code:
 
1.8
TFGVBKDYRCLBJQUNVXTFNWHQMKDYDTXBAWKVLJ[space]
VHEPESLVWVLIBGRFIMHGMEBXUMRPFGWWODXDAB
GWJBJNLSIFVXTYMWLBQRSIMGDXOTEECSHLQKIO

SHA256[space]plaintext[space]=[space]aab93b3f93827963f00257998200245476be5163b6063190528cd1bb629fdb20


1.9
UDCLZQWYXRXTWEGNADNJPJNEYPSKENPVSSOOVH[space]
ZZIOHVTMFRXVJRBHVEPOYDBLLJHSRKHIKLFXPT
MKHUXJQYDJXUCZEZSTDGVGOGRICIGNBEOZIYSO

SHA256[space]plaintext[space]=[space]a17d5a3eb3bf9d5949fa18ab4de62de181485ca5f00c049a5f1c5b8ad63d6b19


1.10
PUMDZKWLLZQHNZNIGXWOBOYQOZYKGURJYGYOXI[space]
ICPVSEJLDPJXPKIUBQCDZDHBZJUEKWVEUVMYNC
QEYTIMGKPEIDNKKPXWGMVFUECNZFNCNWEXZZSY

SHA256[space]plaintext[space]=[space]e4b1a8cf95eeed90696a2ff66d444f52110a67a85b1cd3122b9d471f78212b0c


1.11
GRKEIRWYBICGFDMKFTDDULEURMLVRWENPJSBZS[space]
NYVGBRYXNDYKXPYOBEJOVCCXFXIBLBBFAKHBLO
PMOBYRESPAFQYIHYYVQMOKNXITJNDVCBYFAWFH

SHA256[space]plaintext[space]=[space]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.
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
*** ATTENTION ***

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

I'm terribly sorry.
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
JOE.TEKK1
Elite member
[ *  *  *  *  * ]
Karl

i see this still is of interest to you. We learn each day. Joe.
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
ZetaBoards - Free Forum Hosting
ZetaBoards gives you all the tools to create a successful discussion community.
« Previous Topic · Challenges · Next Topic »
Add Reply