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

Целта на това практическо упражнение е студентите да усвоят особеностите на 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.

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.

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

ОТР 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.