Въведение в мрежовата сигурност / Network security basics

admin
Free
  • 3 lessons
  • 0 quizzes
  • 10 week duration

Анализ на функционалността, програмна реализация, използване и разбиване на One-Time pad / Analysis of the functionality, development, implementation and brute-force attack of the One-time Pad cipher

1. Въведение

    Целта на това практическо упражнение е студентите да усвоят особеностите на One-Time pad (OTP). За изпълнението на поставената цел, ще се извърши теоретичен анализ на функционалността на ОТР и посредством работната среда на Python ще се реализира програмен модул за неговото прилагане. Създаването на модула ще бъде проследено и разяснено стъпка по стъпка. В края на практическото упражнение, студените ще тестват създадения от тях програмен модул и ще шифрират и дешифрират съобщения с ОТР. Ще бъде проследен процеса по осъществяване на Two-Times pad атака.

2. Цел на упражнението

  1. Анализ на функционалните особености на ОТР;
  2. Реализиране на програмен модул за прилагане на ОТР;
  3. Шифриране на текстова информация и дешифриране на шифрограми посредством създадения програмен модул;
  4. Изпълнение на Two-Times pad атака;

3. Цел на упражнението

    Изтеглете инсталационния файл на Python 2.7. След изтегляне, стартирайте инсталационния файл python-2.7.3.exe и инсталирайте работната среда с настройките по подразбиране. Стартиране на Python в графичен режим и се запознайте с работната среда. От меню Start изберете All Programs > Python 2.7 > IDLE (Python GUI). След като работния екран на Python се зареди разгледайте менютата и възможностите, които ви се предоставят.

4. Анализ на функционалните особености на ОТР

    Съществува шифър, който е толкова силен, че на практика е невъзможно да бъде разбит – независимо от мощността на компютъра, от времето за осъществяване на атаката или от познанията на криптографа. За съжаление този шифър е също толкова неудобен за употреба, колкото е и силен. На практика той се използва единствено за споделяне и разпространение на най-важните съобщения. Въпросния шифър представлява шифър с еднократно прилагане на ключ – One Time Pad (OTP). Всъщност този шифър е шифър на Виженер, за който:

  1. Ключът е точно толкова дълъг, колкото е и съобщението, което е шифрирано.
  2. Ключът е изграден от напълно случайни символи.
  3. Ключът се прилага само веднъж и не се използва никога повече за каквото и да е друго съобщение.
    Ако тези три правила се спазят, шифрираното съобщение е напълно защитено срещу каквато и да е криптографска атака. Дори и при безкрайна изчислителна мощ, този шифър не може да се разбие.
    Ключовете при този шифър се наричат тестета (pads) поради факта, че са се използвали хартиени блокове (тестета) за разпечатване им. Най-горния лист хартия се е откъсвал и унищожавал след употреба (шифриране или дешифриране), с което се е разкривал следващия подходящ за използване таен ключ от тестето.
    За да се демонстрира, защо OTP е неразбиваем, нека първо се анализира шифъра на Виженер и най-лесния метод за разбиването му – с прилагане на честотен анализ. При OTP този подход е неприложим, защото при ключ с дължина равна на съобщението, всички символи от шифрограмата имат еднаква вероятност да отговарят на всеки от символите в съобщението.
    Да кажем, че искаме да шифрираме съобщението “If you want to survive out here, you’ve got to know where your towel is.” Ако се премахнат разстоянията между отделните думи и пунктуационните елементи, това съобщение е с дължина от 55 символа. За да се приложи ОТР е необходимо да се използва ключ със същата дължина. Да приемем, че подходящ ключ е: “kcqyzhepxautiqekxejmoretzhztrw wqdylbttvejmedbsanybpxqik”. Шифрирането на съобщението ще е следното:

    Текст – ifyouwanttosurviveouthereyouv egottoknowwhereyourtowelis
    Ключ – kcqyzhepxautiqekxejmoretzhztr wwqdylbttvejmedbsanybpxqik
    Шифрограма – shomtdecqtilchzssixghyik dfnnmacewrzlghraqqvhzguerplbbqc

    Нека се поставим на мястото на изпълняващия атаката. Разполагаме с шифрограмата “shomtdec…”, но как да атакуваме шифъра? Атака с изчерпателно търсене на ключа няма да доведе до никакъв резултат, защото съществуват прекалено много възможни комбинации, дори и за съвременните суперкомпютри. Броят на ключовете е 26(брой на символите), което означава, че при 55 символа ще имаме 2655 или 666 091 878 431 395 624 153 823 182 526 730 590 376 250 379 528 249 805 353 030 484 209 594 192 101 376 възможни ключа (това важи само за английската азбука).
    Дори и в бъдеще да се разполага с (квантов) компютър с достатъчно изчислителна мощност, за да се осъществи атаката с изчерпателно търсене на ключа, то това няма да доведе до разбиване на ОТР. Това се дължи на факта, че за всяка шифрограма, възможния набор от съобщения е неограничен и с равномерно разпределение.
    Например, за шифрограмата “shomtdec…”, може да се твърди, че се използва текста “The myth of Osiris was of importance in ancient Egyptian religion.”, който е шифриран с ключа “zakavkxolfqdlzhwsqjbzmtwmmn akwurwexdcuywksgorghnnedvtcp”:

    Текст – themythofosiriswasofimportance inancientegyptianreligion
    Ключ – zakavkxolfqdlzhwsqjbzmtwmmnakwur wexdcuywksgorghnnedvtcp
    Шифрограма – shomtdecqtilchzssixghyikdf nnmacewrzlghraqqvhzguerplbbqc

    Идеята на дешифрирането на съобщенията е да се получи разбираем текст след прилагането на само един определен ключ. Както вече беше показано от предходния пример обаче, шифрограмата може да се получи в резултат от прилагането на различни ключове върху две напълно независими едно от друго съобщения. При ОТР, няма начин да се каже кое е оригиналното съобщение. Реално, всяко едни разбираемо съобщение, което е с дължина 55 символа е възможно да бъде шифрираното съобщение. Фактът, че определен ключ може да дешифрира шифрограмата в смислено изречение, не е гаранция, че това е оригиналния ключ.
    Използването на един и същ ключ за шифриране на две различни съобщения въвежда слабост. Използването на ОТР по този начин се нарича Two-times Pad, а атаката Two-times pad атака. Това наименование не е официално прието и същност се използва, за да се демонстрира, че ОТР се е използвал неправилно.
    Само поради факта, че даден ключ дешифрира шифрограмата в разбираема последователност, това не означава, че е използван правилен ключ. Използването на един и същи ключ за две различни съобщения позволява на атакуващия да съпостави резултата от прилагането на определен ключ за двете шифрограми и ако се получи смислена последователност за едната, но безсмислена за другата, то това не е правилния ключ. На практика, с много голяма вероятност може да се твърди, че за две шифрограми може да се приложи само един ключ, при който да се получат смислените оригинални съобщения.

5. Реализиране на програмен модул за прилагане на ОТР

    От меню Start изберете All Programs->Python 2.7->IDLE (Python GUI). На работния екран ще се зареди средата за разработване на приложения с Python.
1. Introduction

    The purpose of this practical exercise is to present to the students the specifics about the One-Time Pad (OTP). To achieve this, the students will get familiar with the provided theoretical analysis on the functionality of the OTP. With the help of the Python environment, the students will develop a code segment for the implementation of the OTP. The lab guide will provide detailed systematic guidelines for the development of the code segment. At the end of the exercise, the students will have to test the developed programing segment and will encode and decode OTP messages. The exercise will conclude with the execution of a Two-times pad attack against several OTP messages, which were encoded with the same key.

2. Purpose of the exercise

  1. Analysis on the functional specifics of the OTP;
  2. Development of a code segment for implementation of the OTP cipher;
  3. Encoding and decoding of messages using the created code segment;
  4. Execution of a Two-times pad attack;

3. Purpose of exercise

    Download the installation file for Python 2.7. After downloading the required files, execute file python-2.7.3.exe and install the work environment with default configuration. Start the Python GUI and get to know the working environment. From menu Start, choose All Programs > Python 2.7 > IDLE (Python GUI). When the IDLE environment is started, explore the environment and the menus.

4. Analysis on the functional specifics of the One-time pad

    In the whole (documented) history of humanity, only one cipher has proven to be truly unbreakable and to provide perfect security. This cipher is so strong that it cannot be forced or broken, regardless of the computational power of the attacking machine, the unlimited attack time or the knowledge of the cryptanalyst. Unfortunately, the use of this cipher is unfeasible in the real word or in the modern telecommunication systems. Nowadays, the cipher is only used in few actual situations – for the protection of the most important messages. It is also rumoured, that the nuclear launch codes of the majority of the nuclear power countries are protected with this cipher. This cipher is called the One-time Pad, but is also known as the perfect cipher. The cipher represents a modification of the Vigenere cipher, with the following functional specifics:

  1. The key is as long as the plaintext message;
  2. The key is a string of random symbols;
  3. The key is only used once and is never to be repeated.
    If these three simple rules are respected, the encoded message if perfectly protected against all known cryptographic attacks. Even with unlimited computational power, the cipher text protected with this cipher cannot be broken.
    The keys, which are used with the OTP, are called pads, because paper pads were used for the printing of the keys in the pre-computer eras. Once the key from the top page of the pad was used for the encoding of a message (or for its decoding at the receiver side), the top page was to be torn and destroyed. Beneath the torn page was a new page, which contained the next usable secret key
    To demonstrate, why the OTP is unbreakable, let us first analyse the Vigenere cipher and the easiest way to break it – by using frequency analysis. With the OTP, the frequency analysis is not usable, because with a key that is as long as the message, all symbols in the cipher text are having the same probability to correspond to a given symbol from the plaintext message.
    Let us say that we wish to encrypt the plaintext message “If you want to survive out here, you’ve got to know where your towel is.”. If we remove the spaces between the words, as well as the punctuation symbols, then this message will be formed by 55 symbols. To apply the OTP, we need to use a key with at least the same length. Let us take the following key as suitable: “kcqyzhepxautiqekxejmoretzhztrw wqdylbttvejmedbsanybpxqik”. The result from the application of the cipher is as follows:

    Plaintext Message – ifyouwanttosurviveouthereyo uvegottoknowwhereyourtowelis
    Key – kcqyzhepxautiqekxejmoretzhztrwwqdylbttve jmedbsanybpxqik
    Cipher text – shomtdecqtilchzssixghyikdfnnmacew rzlghraqqvhzguerplbbqc

    Let us pretend that we are the attacker of the telecommunication system where the message is being transmitted. We intercept the transmission of the cipher text and get the following message “shomtdec…”. But how to attack or brute-force the cipher text? Simple brute-force attack will not lead to any successful results for the key, because there are too many possibilities, even for the modern supercomputer clusters. The key space is equal to 26(number of symbols in the message), which means that for 55 symbols we will have 2655 or the number 666 091 878 431 395 624 153 823 182 526 730 590 376 250 379 528 249 805 353 030 484 209 594 192 101 376 – these are the possible keys (this is valid for the English alphabet only).
    If the quantum computing gets widely available in the near future and if we consider a quantum computer with unlimited computational power to perform a brute-force attack, the results from the attack will not be conclusive and OTP will still be unbreakable. This can be explained with the fact that for every cipher text, the possible number of plaintext messages is unlimited and with uniform distribution.
    For example, for the same cipher text “shomtdec…”, it can be said that we have used the plaintext message “The myth of Osiris was of importance in ancient Egyptian religion.”, with the key “zakavkxolfqdlzhwsqjbzmtwm mnakwurwexdcuywksgorghnnedvtcp”:

    Plaintext Message – themythofosiriswasofimportancei nancientegyptianreligion
    Key – zakavkxolfqdlzhwsqjbzmtwmmnakwurwexdcuywks gorghnnedvtcp
    Cipher text – shomtdecqtilchzssixghyikdfnnmacew rzlghraqqvhzguerplbbqc

    The idea for the deciphering of the messages is to get a meaningful text after the application of one specific key – the key used for the encryption of the message. As shown in the example above, the same cipher text can be obtained following the application of different keys on different meaningful plaintext messages. With the ОТР there is no way to say which was the original message. In reality, every meaningful message with the length of 55 symbols can be the encrypted message. The fact, that a specific key can decode the cipher text and the result will be a meaningful sentence or message, is not enough to guarantee that the used key was the one used in the creation of the cipher text.
    However, the use of the same key for the encoding and the decoding of two different messages introduces a weakness in the cipher. The use of ОТР in this way is called the Two-times Pad and the corresponding attack, which uses thus weakness, is called the Two-times pad. This name for the attack is not official and is actually used to demonstrate that the ОТР has been used in the wrong way.
    The sole fact that a key can be used for the deciphering of a given cipher text and the result from this will be a meaningful plaintext message is not a guarantee that the key is the correct one. The use of the same key for two different messages is however allowing the attacker to compare the results from the application of the key on both cipher texts. If the result from the deciphering of one of the messages is a meaningful text, but for the second one the result makes no sense, then the wrong key was used. In reality, it can be said that there is a significantly high probability to have the right key, if both deciphered messages have a meaningful content.

5. Development of a code segment for implementation of the OTP

    From the Start select All Programs->Python 2.7->IDLE (Python GUI). On the screen, you will see the IDLE Python environment.

    Създайте нов файл OTP_enc.py, който ще се използва за шифриране на съобщенията. Реализирайте програмния код, който е необходим за изпълнението на ОТР.
    Create a new file called OTP_enc.py. This file will be used for the encoding of the messages. Complete the file by introducing the code segment from below. This code will be used to implement the OTP for several messages. Try to analyze the code segment.

    В програмния код са дефинирани две функции – strxor(a, b) и encrypt(key, msg). Основното предназначение на първата функция е побитовото изключващо събиране на двоичните последователности, които се използват за представяне на всеки символ. Втората функция извиква първата и извежда на екрана шифрираните текстови последователности в шестнадесетичен вид. Променливите а1, а2, … , а11 се използват за въвеждане на текстовите съобщения. Променливата key се използва за съхранение на ключ, който ще се използва за шифриране на всички текстови последователности.
    Създайте друг файл OTP_dec.py. Този файл ще се използва за реализиране на програмния код за дешифриране на съобщенията.
    The code segment contains two functions – strxor(a, b) and encrypt(key, msg). The main purpose of the first function is to perform the xor of the message and the key. This is done one symbol at a time. The second function calls the first one and outputs the encoded text messages on the screen. The outputted messages are additionally in their hexadecimal form. The variables а1, а2, … , а11 are used for the introduction of the plaintext messages, which will be encoded. The variable key is used for the recording of the key, which will be used for the encoding of all plaintext messages.
    Create another file called OTP_dec.py. This file will be used for the deciphering of the cipher texts.

    В програмния код са дефинирани две функции – strxor(a, b) и decrypt(key, msg). Основното предназначение на първата функция е побитовото изключващо събиране на двоичните последователности, които се използват за представяне на всеки символ. Втората функция извиква първата и извежда на екрана резултата от процеса по дешифриране на съобщенията. Променливите а1, а2, … , а11 се използват за въвеждане на текстовите съобщения в шестнадесетичен вид, а променливите m1, m2, … , m11 се използват за извеждане на съобщенията като нормален текст. Променливата key се използва за съхранение на ключ, който се е използвал за шифриране на всички текстови последователности.

6. Шифриране на текстова информация и дешифриране на шифрограми посредством създадения програмен модул.

    Използвайте файла OTP_dec.py и за променливата key2 въвеждате директно текстово съобщение. Започнете с най-често използваното трибуквие в английския език – the. Променяйте параметъра m11 от процедурата ciphertexts = decrypt(key2, m11), за да преминете през всички шифрирани съобщения (от m1 до m11), като след всяка промяна изпълнявайте програмата и попълвайте резултата за променливата key, докато не получите стойност, при която текста за всички 11 съобщения е смислен. По този начин след няколко итерации ще успеете да дешифрирате търсеното съобщение – a11. Използвайте следните последователности за шифрограмите:
    There are two functions in the presented code segment – strxor(a, b) and decrypt(key, msg). The main purpose of the first function is the character-based xor of every bit in the strings, which are used for the representation of each symbol. The second function calls the first one and outputs on the screen the result of the deciphering process. The variables а1, а2, … , а11 are used for the introduction of the text messages in their hexadecima form, while the variables m1, m2, … , m11 are used for the output of the plaintext messages. The variable key is used for the storing of the key, which is being used for the encoding of all text messages.

6. Encoding and decoding of plaintext messages using the developed code segments for implementation of the OTP.

    Use the file OTP_dec.py. Introduce for the variable key2 the requested test text message. Start with the most widely used word in the English language – the. Change the value of m11 from the procedure ciphertexts = decrypt(key2, m11). This will allow you to decode all encrypted messages (from m1 to m11). After every change, run the program and fill in the result for the variable key until you get a value, for which all 11 messages have meaningful content. In this way, after few iterations you will manage to decipher the message, which was missing – a11. Use the following cipher texts in your experiments.


a1=’091f4f1c0357563d571f3d48182a3b70300c154b4003562a2e51570d4c2d142a651920122029581d2766251f 311a1c3b06462a1e6e0e5e0474442a13270523170e1623181a2f3f3b15210c000c48232572150250513143242b16 280d29725f2344392a3e415117000c2201592c354f’

a2=’1f0342051b185c20520a275f1837213d211750084208473d355f46091c24036e370f320236221d1661273d17 3d010672124b2c013b1b5800315b365026186652031a3c0c1f353f371a7945180a0129237208191505295461280129 0d292143650b2b62345c5b41151f241c5e2e66003e543d20194532762b2527244 00c53025a280f6a470229293f22077527252a24374d53324265163a09443a11112d30092e315e0850091e00550a18 205f283400155e4a0f566c54515e000610113b331e1b1c282253413e40′

a3=’02044518184a582c5703394814632b39340c15194351402c285d14070a381f20651f27022 0701c1b3323320e3e0b523418416f08200b430f2443261f3c572945 4d1d2b161d38262c1d3a0b4f15013e233d141e15102555282c1a29002d3e103516 222132574045151e7006452a2e4f2d43742f0d432 3332c3f282853155b195d670e384f082631362 0113c23306b2e315c55214562′

a4=’19145b01124c432655423e5441632b223d140404570356393241141a092 a1f3c364a200864351611333f210e3b1d1c721a563b0521 0c42563d596f073a1e255f4d1b2101076122301 175160a0c0c2f3972000451513354 223d1a300b3e72432d053f2777475d5250 1e311855692d0a35107c210a1b6b3a2738326b510e5f1b5c290d334341212b73300b3c34216b39315c5f381627 532a1410344301633d0e3c3257165c00034e190d4d33163833 0906435c03562d591053024311502b33020a5939395b493f1d0e3226074b3324487948′

a5=’19145b01124c432655423e5441632b223d140404 4308443d3f554748193f1f6e3102314737311517612d340372141d205756 210e3c1141023d58215033192217091c2d07163 122311b3b450004482b6b3f0419461026546d78072 e0139355865056d2f324046561708701a426 9211d2345246e17516b3b2738322a550441565e26186a07003e207 32643313e2f2d282b5c583e1627532a47443d500a6336133231401717′

a6=’1e05534c10575023160033115b31312030051e0a5 c08442029185d1b4c38156e23033a036423171f2466261f33191c3704406f023c48581827522 c05201e324e4d1020550e61352a 0d251100051a2b3b3a0 809150222592435166a4e383a453 6443d27255e5c4304043e121020321c6c43 212c0e5239252b242f6b5d1312134 5261223000f66′

a7=’091f4f1c0357563d571f3d48182b2923640 81f055751552c3f5614070a6c13 20310f2602372458062e66381426171e3e1e542a032d0d111135432715201e28504d1820114f2d37 2f54300b090d1a292e3f040441512 0562436102f0b3f7c101 6012e30324715541f003d005e20250e38593b200b1726 373b6b232e1202401f5e2e0f2b03412737732215 3039693f3f3c5845255823432049′

a8=’1e05531e1218503d534f34114f2a2c3564121119591443307a5752480f 3e033e310b3a0628290c1b2266300e26131139041f6f0c200c11023c52 3650311628170f1c6e160320252b1d330c0a064823257200044c512e57612b16300 b3e335c65132c3b241d1576500e3f185d26284 f2859273a115928222b242f6b461440184 0670e244f1620242767023 b77283f39385a5d2f446c5d3d08 472611052d3d472d3c5310 190d1612580d512b5f3e3 f001417581513645 64653050f1553343f40′

a9=’1e05534c335157295f0ac3795d2f243d250a500a5e 15171b09791409002b153c2c1e3c0a377c581b2f66301e361b063b185d 6f19214853133d592850261f23170b103c061b61262d16390c0c0e116a203c 0e1d5b5124492035032a0b3f725f2344252b305b1546050c3c1c4430661f3952 38271b1a20333b6b2027550e401 f472f0c394341202425224337322c256d385459245 16c423b0210385e17377910333057084 04e02115c0b16′

a10=’191944091655112c5f1f3d 544a3064702d0a50085f1f433b3b4b404818235a3a2d0f7 405283f1b196132280a375e523105562e192b48501874563d123b0334 561f10220c4f2d39361375161b100d2b26720e0c151a2448613512320b3e3b5129486d35 3f5a565f5004235553262b0d255e312a584022222 a6b35235741421a522e0f3e0a193c6 5312e17783530662 f304d1625446c55 3b0642345210262b4a 382d1f07510f05035a1b5d351 a6a250a0a524e0f 1730175c5b07065445303f4e1c173f7b42 50270c4f202b0645′

a11=’1e05534c045d523d5 31b755c5d303b312301500243 4b171e325d5a48193f1320224a 354737240a17202b7119 3b021a37051f6f032b1e54 0474423c1572032e524 d122b0c4f2c392a1175110 703066a243c020f1b’

7. Заключение

    ОТР е шифър на Виженер, при който се използва еднократен ключ с дължина равна на тази на съобщението, което прави разбиването на шифрограмите невъзможно. Въпреки това, този подход е безкрайно неудобен за прилагане в практиката. Обикновено се използва списък с ключове за всяка дата. По този начин, ако на 31 Октомври получите шифрограма, то можете да използвате първия от набора с ключове за нейното дешифриране и т.н. Основното правило при ОТР е да не се повтарят ключовете и да не се позволи достъпа до тях.
7. Conslusion

    ОТР is a Vigenere cipher that uses only once a single key with a length equal to that of the message, which is making the breaking of the cipher texts impossible. Despite this, this cipher is extremely unsuitable in the real world. Usually, a list of keys is used for each date. In this way, if on October 31 we get a cipher text, then we can use the first key for that date and decode it. The main rule with the ОТР is not to repeat the keys and not to allow access to them.