Расшифровка однобайтового шифрованного текста XOR |

Шифрование — это процесс кодирования сообщений таким образом, чтобы их могли прочитать и понять только те стороны, для которых они предназначены. Процесс извлечения исходного сообщения из зашифрованного называется расшифровкой. Шифрование обычно зашифровывает исходное сообщение с помощью ключа, называемого ключом шифрования, который согласовывают вовлеченные стороны.

Стойкость алгоритма шифрования определяется тем, насколько сложно было бы извлечь исходное сообщение, не зная ключа шифрования. Обычно это зависит от количества битов в ключе — чем больше ключ, тем больше времени требуется для расшифровки зашифрованных данных.

В этом эссе мы будем работать с очень простым шифром (алгоритмом шифрования), в котором используется ключ шифрования размером в один байт, и попытаемся расшифровать зашифрованный текст и получить исходное сообщение, не зная ключа шифрования. Постановка задачи, определенная выше, основана на Cryptopals Set 1 Challenge 3.

Алгоритм однобайтового XOR работает с ключом шифрования размером 1 байт, что означает, что ключ шифрования может быть одним из 256 возможных значений байта. Теперь мы подробно рассмотрим, как выглядят процессы шифрования и дешифрования для этого шифра.

Шифрование

В рамках процесса шифрования исходное сообщение повторяется побайтно, и каждый байт b подвергается операции XOR с ключом шифрования key и результирующий поток байтов снова преобразуется обратно в символы и отправляется другой стороне. Эти зашифрованные байты не обязательно должны быть среди обычных печатных символов и в идеале должны интерпретироваться как поток байтов. Ниже приведена реализация процесса шифрования на основе Python.

def single_byte_xor(text: bytes, key: int) -> bytes:
    """Given a plain text `text` as bytes and an encryption key `key` as a byte
    in range [0, 256) the function encrypts the text by performing
    XOR of all the bytes and the `key` and returns the resultant.
    """
    return bytes([b ^ key for b in text])

В качестве примера мы можем попробовать зашифровать обычный текст — abcd — с ключом шифрования 69 и в соответствии с алгоритмом мы выполняем побайтовое XOR над заданным открытым текстом. Для характера aбайт, т.е. значение ASCII 97 который при XORed с 69 приводит к 36 чей символьный эквивалент $аналогично для b зашифрованный байт 'за c это & и для d это !. Следовательно, когда abcd шифруется с использованием однобайтового шифра XOR и ключа шифрования 69результирующий зашифрованный текст, т. е. зашифрованное сообщение, $'&!.

Расшифровка

Расшифровка — это процесс извлечения исходного сообщения из зашифрованного зашифрованного текста с использованием ключа шифрования. XOR имеет имущество — если a = b ^ c тогда b = a ^ cследовательно, процесс расшифровки точно такой же, как и шифрование, т.е. мы повторяем зашифрованное сообщение побайтно и выполняем XOR каждого байта с ключом шифрования — результатом будет исходное сообщение.

Поскольку шифрование и дешифрование имеют одинаковую реализацию, мы передаем зашифрованный текст в функцию single_byte_xorопределенный выше, чтобы вернуть исходное сообщение.

>>> single_byte_xor(b"$'&!", 69)
b'abcd'

Все становится по-настоящему интересным, когда нам нужно восстановить исходное сообщение по зашифрованному тексту, не зная ключа шифрования; хотя мы знаем алгоритм шифрования.

В качестве образца открытого текста мы берем последние пару сообщений, отправленных по их немецкой военной радиосети во время Второй мировой войны. Эти сообщения были перехвачены и расшифрованы британскими войсками. В военное время сообщения шифровались с помощью Загадочная машина а также Алан Тьюринг лихо взломал код Энигмы (аналогично ключу шифрования), который использовался для шифрования сообщений на немецком языке.

В этом эссе вместо шифрования сообщения с помощью кода Enigma мы будем использовать однобайтовый шифр XOR и попытаемся восстановить исходное сообщение обратно, не зная ключа шифрования.

Здесь мы предполагаем, что исходное сообщение, которое нужно зашифровать, является настоящим английским предложением в нижнем регистре. Зашифрованный текст, который мы пытаемся расшифровать, может быть получен как

>>> key = 82
>>> plain_text = b'british troops entered cuxhaven at 1400 on 6 may - from now on all radio traffic will cease - wishing you all the best. lt kunkel.'
>>> single_byte_xor(plain_text, key)
b'0 ;&;!:r& =="!r7<&7 76r1\'*:3$7<r3&rcfbbr=<rdr?3+r\x7fr4 =?r<=%r=<r3>>r 36;=r& 344;1r%;>>r173!7r\x7fr%;!:;<5r+=\'r3>>r&:7r07!&|r>&r9\'<97>|'

Грубая сила

Существует очень ограниченное количество возможных ключей шифрования — 256, если быть точным — мы можем, очень удобно, пойти на подход Bruteforce и попытаться расшифровать зашифрованный текст каждым из них. Итак, мы начинаем перебирать все ключи в диапазоне [0, 256) and decrypt the ciphertext and see which one resembles the original message the most.

In the illustration above, we see that the message decrypted through key 82 is, in fact, our original message, while the other retrieved plain texts look scrambled and garbage. Doing this visually is very easy; we, as humans, are able to comprehend familiarity but how will a computer recognize this?

We need a way to quantify the closeness of a text to a genuine English sentence. Closer the decrypted text is to be a genuine English sentence, the closer it would be to our original plain text.

We can do this only because of our assumption — that the original plain text is a genuine English sentence.

ETAOIN SHRDLU

Letter Frequency is the number of times letters of an alphabet appear on average in written language. In the English language the letter frequency of letter a is 8.239%, for b it is 1.505% which means out of 100 letters written in English, the letter a, on an average, will show up 8.239% of times while b shows up 1.505% of times. Letter frequency (in percentage) for other letters is as shown below.

occurance_english = {
    'a': 8.2389258,    'b': 1.5051398,    'c': 2.8065007,    'd': 4.2904556,
    'e': 12.813865,    'f': 2.2476217,    'g': 2.0327458,    'h': 6.1476691,
    'i': 6.1476691,    'j': 0.1543474,    'k': 0.7787989,    'l': 4.0604477,
    'm': 2.4271893,    'n': 6.8084376,    'o': 7.5731132,    'p': 1.9459884,
    'q': 0.0958366,    'r': 6.0397268,    's': 6.3827211,    't': 9.1357551,
    'u': 2.7822893,    'v': 0.9866131,    'w': 2.3807842,    'x': 0.1513210,
    'y': 1.9913847,    'z': 0.0746517
}

This Letter Frequency analysis is a rudimentary way for language identification in which we see if the current letter frequency distribution of a text matches the average letter frequency distribution of the English language. ETAOIN SHRDLU is the approximate order of frequency of the 12 most commonly used letters in the English language.

The following chart shows Letter Frequency analysis for decrypted plain texts with encryption keys from 79 to 84.

In the illustration above, we could clearly see how well the Letter Frequency distribution for encryption key 82 fits the distribution of the English language. Now that our hypothesis holds true, we need a way to quantify this measure and we call if the Fitting Quotient.

Fitting Quotient

Fitting Quotient is the measure that suggests how well the two Letter Frequency Distributions match. Heuristically, we define the Fitting Quotient as the average of the absolute difference between the frequencies (in percentage) of letters in text and the corresponding letter in the English Language. Thus having a smaller value of Fitting Quotient implies the text is closer to the English Language.

Python-based implementation of the, above defined, Fitting Quotient is as shown below. The function first computes the relative frequency for each letter in text and then takes an average of the absolute difference between the two distributions.

dist_english = list(occurance_english.values())

def compute_fitting_quotient(text: bytes) -> float:
    """Given the stream of bytes `text` the function computes the fitting
    quotient of the letter frequency distribution for `text` with the
    letter frequency distribution of the English language.

    The function returns the average of the absolute difference between the
    frequencies (in percentage) of letters in `text` and the corresponding
    letter in the English Language.
    """
    counter = Counter(text)
    dist_text = [
        (counter.get(ord(ch), 0) * 100) / len(text)
        for ch in occurance_english
    ]
    возвращаться сумма([abs(a - b) for a, b in zip(dist_english, dist_text)]) / длина (расстояние_текста)

Расшифровка

Теперь, когда у нас есть все, что нам нужно, чтобы напрямую получить простой текст из заданного зашифрованного текста, мы заключаем его в функцию, которая перебирает все возможные ключи шифрования в диапазоне [0, 256), расшифровывает зашифрованный текст, вычисляет подходящее частное для обычного текста и возвращает тот, который минимизирует частное как исходное сообщение. Реализация этой логики дешифрования на основе Python показана ниже.

def decipher(text: bytes) -> Tuple[bytes, int]:
    """The function deciphers an encrypted text using Single Byte XOR and returns
    the original plain text message and the encryption key.
    """
    original_text, encryption_key, min_fq = None, None, None
    for k in range(256):
        
        _text = single_byte_xor(text, k)
        
        
        _fq = compute_fitting_quotient(_text)
        
        
        
        if min_fq is None or _fq < min_fq:
            encryption_key, original_text, min_fq = k, _text, _fq

    
    return original_text, encryption_key

Этот подход также был протестирован на 100 случайных английских предложениях со случайными ключами шифрования, и было обнаружено, что этот метод дешифрования показал себя хорошо для всех образцов. Подход потерпит неудачу, если предложение очень короткое или содержит много символов. Исходный код всего процесса расшифровки доступен в блокноте Jupyter по адресу arpitbhayani.me/decipher-single-byte-xor.

Если вам понравилось то, что вы прочитали, рассмотрите возможность подписки на мой еженедельный информационный бюллетень на arpitbhayani.me/информационный бюллетень где раз в неделю я пишу эссе о внутреннем устройстве языков программирования, или глубоко погружаюсь в какой-нибудь сверхумный алгоритм, или просто даю несколько советов по созданию хорошо масштабируемых распределенных систем.

Вы всегда можете найти меня, просматривая твиттер @arpit_bhayani.