Решение (несложных) криптографических задач на языке Haskell

Вторая инкарнация вводного курса по криптографии на Coursera порадовала тем, что в ней для решения задач можно было пользоваться произвольным языком программирования. Ну и поскольку мои познания в криптографии ограничивались тем, что я прочитал в рассказах «Золотой жук» Эдгара По и «Пляшущие человечки» Артура Конан-Дойля, то я с удовольствием прослушал все лекции, порешал задачи и поучаствовал в жизни тамошнего форума.

За шесть недель курса почтенным слушателям было предложено шесть задач на программирования по следующим темам:

1. Поточные шифры.
2. Блочные шифры.
3. Аутентификация сообщений.
4. Аутентификация шифровок.
5. Обмен ключами.
6. Шифрование при помощи открытых ключей.

Все представленные программные задачи были мной решены при помощи прекрасного языка функционального программирования Haskell. Для этих целей пришлось накодировать несколько вспомогательных модулей, а также две задачи были решены в полуавтоматизированном режиме (режим «автоматизированного криптоанализа»). Далее в этой заметке я приведу сначала описание вспомогательных модулей, а потом описание функций для решения задач. Самих ответов я приводить не буду, чтобы не нарушать так называемый «Кодекс чести». И если вы планируете самостоятельно проходить этот курс, то рекомендую вам не читать дальнейший текст.

Вспомогательные модули

Само собой разумеется, что в отдельные модули, не относящиеся к решению конкретной задачи, желательно выносить программные сущности, которые, как предполагается, будут использоваться при решении нескольких задач. В процессе прослушивания курса и решения задач стало ясно, что к таким вспомогательным задачам относятся: группировка последовательностей, всевозможные функции с операцией XOR (исключающее ИЛИ), а также функции для реализации модульной арифметики.

Рассмотрим всё это подробнее.

Группировка последовательностей

Очень часто в практических задачах встречается необходимость разбить список на подсписки, длина каждого из которых определена и равна заданному n. Например, это может понадобиться при преобразовании списка к матрице. Очень странно, почему этой функциональности нет в стандартной поставке языка. Но это и не беда, сделаем это сами.

Лучше всего, каноничней, определить класс типов, значения которых можно подвергать группировке. Это просто:

class Groupable a where
  groups :: Integral b => b -> a -> [a]

Здесь метод groups получает на вход длину подгруппы (подсписка) и значение-контейнер, которое надо разделить на подгруппы, а возвращает список подгрупп. Самым первым экземпляром этого класса определим экземпляр для типа [a] (то есть для списка), но никто и ничто не удержит нас от определения экземпляров и для других типов. Ну, собственно, экземпляр для списка определяется несложно:

instance Groupable [a] where
  groups i s | null s = []
             | otherwise  = let (h, t) = splitAt (fromIntegral i) s
                            in   h : groups i t

Работу этого метода можно проиллюстрировать следующей диаграммой:

Но в дальнейшем нам придётся работать с байтовыми строками, в том числе и ленивыми, поскольку многие готовые криптографические библиотеки используют именно их. Поэтому сразу определим экземпляры и для байтовых строк. В первую очередь для этого надо подключить соответствующие модули (это в обязательном порядке необходимо сделать непосредственно после декларации модуля):

import qualified Data.ByteString      as BS
import qualified Data.ByteString.Lazy as BSL

Ну и определение экземпляров совершенно такое же, как и для списка, только при этом для функций null и splitAt надо использовать квалифицированные вызовы:

instance Groupable BS.ByteString where
  groups i s | BS.null s = []
             | otherwise = let (h, t) = BS.splitAt (fromIntegral i) s
                           in   h : groups i t

instance Groupable BSL.ByteString where
  groups i s | BSL.null s = []
             | otherwise  = let (h, t) = BSL.splitAt (fromIntegral i) s
                            in   h : groups i t

Всякий программист, посмотревший на представленные три определения экземпляров, сразу же захочет слить их в один, поскольку определения ну вообще ничем не отличаются. К сожалению, в стандартном языке Haskell сделать это невозможно, так что придётся довольствоваться этим. И такая ситуация, кстати, встречается очень часто именно при определении экземпляров.

Операция XOR

Операция XOR (или сложение по модулю 2) — это самый базовый примитив криптографии, поскольку данная операция очень удобна в силу своего фундаментального свойства: она обратима, причём обратной операцией является она же. Данное свойство выражается просто: (a ⊕ b) ⊕ b = a, то есть, что то же — x ⊕ x = 0, x ⊕ 0 = x. Данная операция используется просто повсеместно в криптографии, поэтому для нас будет важным закодировать её и дополнительные функции.

Надо отметить, что в стандартном модуле Data.Bits уже есть функция для осуществления операции XOR. Однако категорически странно то, что она не определена для типа Char, а именно с этим типом мы будем работать на протяжении всего курса. Поэтому нам надо будет определить такую функцию самостоятельно, получив нужные определения из имеющихся модулей:

import Data.Bits (xor)
import Data.Char (chr, ord, digitToInt, intToDigit)
import Data.Function (on)

charXOR :: Char -> Char -> Char
charXOR = (chr .) . (xor `on` ord)

Определение функции charXOR надо читать следующим образом. Она принимает на вход два символа, применяет к ним стандартную функцию ord (получение кода символа), XOR-ит оба кода, после чего преобразует полученный в результате код обратно в символ при помощи стандартной функции chr. Точка в скобках после функции chr требуется из-за того, что у функции два аргумента (см. статью Дениса Москвина «Сечения композиции как инструмент бесточечного стиля»).

Далее, собственно функция для кодирования заданной строки при помощи цикличного применения к ней пароля с посимвольным сложением по модулю 2. Вот её определение:

decode :: String -> String -> String
decode txt pwd = zipWith charXOR txt $ cycle pwd

Ничего сложного, как обычно на языке Haskell. Берём пароль pwd, конкатенируем его самого с собою бесчисленное количество раз при помощи стандартной функции cycle, а потом сшиваем две строки при помощи функции zipWith и оператора сшивания charXOR, который мы определили чуть ранее. Функция zipWith сама ограничит свой результат длиной текста txt, так что бесконечная конкатенация пароля к самому себе тут ограничивается обычными в языке Haskell ленивыми вычислениями.

Ну и примерно вот так выглядит работа этой функции:

Постоянно в области криптографии используется так называемое шестнадцатеричное представление строк. Это просто — каждый байт строки представляется в виде двухзначной шестнадцатеричной цифры. В итоге строка из n символом (байт) представляется в виде 2 * n символов. Несколько задач в рассматриваемом курсе были основаны на таком представлении строк, поэтому пришлось реализовать несколько примитивных функций, которые с таким представлением работают — конвертируют туда-обратно. Вот они:

fromHex :: String -> String
fromHex []        = []
fromHex (c1:c2:s) = chr (digitToInt c1 * 16 + digitToInt c2) : fromHex s

toHex :: String -> String
toHex [] = []
toHex (c:s) = hex (o `div` 16) : (hex (o `mod` 16) : toHex s)
  where
    o = ord c
    hex i | i >=0   && i <= 9  = chr (i + 48)
          | i >= 10 && i <= 15 = chr (i + 87)
          | otherwise          = ' '

intToHex :: (Integral a) => a -> String
intToHex n = if odd $ length result
               then '0' : result
               else result
  where
    result      = reverse $ intToHex' n
    intToHex' n = let (q, r) = quotRem n 16
                  in  intToDigit (fromEnum r) : (if q == 0
                                                   then ""
                                                   else intToHex' q)

Функция fromHex получает на вход шестнадцатиричное представление строки и возвращает обычную строку. Функция toHex делает обратную операцию, так что s ≡ fromHex $ toHex s ≡ toHex $ fromHex s, или, что то же, id ≡ fromHex . toHex ≡ toHex . fromHex. Ну а функция intToHex просто возвращает шестнадцатеричное представление числа, причём предваряет его лидирующим нулём, если длина получившейся строки нечётна. Она потребуется нам для решения одной из задач.

Модульная арифметика

Следующей важной областью является модульная арифметика (или, иначе, арифметика вычетов). В криптографии она занимает значительное место в виду того, что многие современные криптографические схемы оперируют гигантскими числами, операции с которыми проводятся по модулю какого-нибудь основания. Модульная арифметика позволяет реализовывать многие целочисленные алгоритмы достаточно эффективным образом.

Для начала секция импорта:

import Control.Applicative ((<$>), (<*>))
import Data.List (nub, sort)
import Data.Maybe (isJust, listToMaybe, maybeToList, mapMaybe)

Одним из базовых алгоритмов в арифметике вычетов является алгоритм Евклида. Все мы знакомимся с ним в школе во время изучения такого понятия, как НОД — наибольший общий делитель. Этот алгоритм позволяет эффективно найти НОД двух чисел. Однако он же при небольшом расширении позволяет решить уравнение ax + by = d для заданных a, b и d. В случае применения модульной арифметики в криптографии этот алгоритм используется для нахождения обратного значения для заданного числа x по заданному же модулю n, то есть находит такой y, что (x * y) `mod` n = 1.

Определение этой функции выглядит достаточно императивно, зато в полном соответствии со словесным описанием алгоритма:

euclid :: Integral a => a -> a -> Maybe (a, a)
euclid a b | d /= 1    = Nothing
           | x >= 0    = Just (x, y)
           | otherwise = Just (x + b, -y)
  where
    (d, x, y) = go a b 0 1 1 0

    go a 0 _  _  x2 y2 = (a, x2, y2)
    go a b x1 y1 x2 y2 = go b r (x2 - q * x1) (y2 - q * y1) x1 y1
      where
        (q, r) = a `quotRem` b

При помощи этой функции мгновенно ищется обратное значение для заданного числа, если оно, конечно, имеется:

inverse :: Integer -> Integer -> Maybe Integer
inverse = (fmap fst .) . flip euclid

Далее для работы необходима функция, которая возвращает множество всех таких чисел в кольце по вычету n, у которых есть обратные элементы. Эта функция также легко определяется через уже имеющиеся:

zStar :: Integer -> [Integer]
zStar n = filter (isJust . inverse n) [0..(n - 1)]

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

power :: (Integral a, Integral b) => a -> a -> b -> a
power n x e | e == 0         = 1
            | e `mod` 2 == 0 = power n x (e `div` 2) ^ 2 `mod` n
            | otherwise      = x * power n x (e - 1) `mod` n

Эта функция важна для поиска дискретного логарифма, который используется в алгоритме Диффи-Хеллмана.

Как видно, здесь используется двоичное разложение степени, в которую возводится число. Производится постепенное вычисление степени с постоянным нахождением вычета по заданному модулю. Это не позволяет результату, в том числе и промежуточному, выйти из кольца.

Решение задач

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

Поточные шифры

В первой задаче всем желающим было предложено самостоятельно изучить вопрос о том, почему нельзя использовать один и тот же пароль в потоков шифре более одного раза. Проблема «one-time pad» в самом её реальном проявлении. В качестве условия были даны 10 зашифрованных простым применением операции XOR к строкам текстов, а также одиннадцатый зашифрованный текст, который надо было расшифровать и предоставить ответ. Зашифрованные тексты были представлены в шестнадцатеричной форме. Что-то вроде такого:

ciphertext  1 = "315c4eeaa8b5f8aaf917..."

Итого: функция ciphertext принимает на вход числа от 1 до 10 и возвращает соответствующий зашифрованный текст из условия задачи.

Перед тем, как приступить к реализации модуля, была проведена оценка того, сколько времени и сил потребуется для осуществления полного перебора ключей для расшифровки. Если принять во внимание только базовые 10 зашифрованных сообщений, то перебор осуществлялся бы среди ~10¹⁹⁵ вариантов ключа. Если же принять во внимание и целевой зашифрованный текст — то только среди ~10⁵⁴. Однако мне не хотелось ждать так долго (наверное, и не дождался бы, всё-таки даже время жизни Вселенной в фемтосекундах меньше). Так что после получения таких оценок было принято решение решать задачу в автоматизированном режиме криптоанализа.

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

Для этих целей были заведены функции phrase и key, а также функция target. Функция phrase соответствовала уже рассмотренной функции ciphertext, только по номеру возвращала расшифрованный вариант. Функции key и target возвращали ключ шифрования и расшифрованный целевой текст. Они постоянно дописывались в процессе криптоанализа — как только появлялся очередной символ ключа, все функции дополнялись, пока весь процесс расшифровки не был закончен.

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

Для автоматизированного криптоанализа были написаны три функции:

texts :: [String]
texts = map (fromHex . ciphertext) [1..10] ++ [fromHex target]

try :: Int -> String
try n = take (length $ phrase n) $ decode (fromHex $ ciphertext n) (phrase n)

main' :: [String]
main' = map (take (length key) . (`decode` key)) texts

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

С самого начала было замечено, что несколько базовых шифровок начинаются с одной и той же последовательности байтов: "234c02ec". Какая самая частая последовательность из четырёх символов, встречающаяся в начале английских предложений? Правильно — «The ». Собственно, резонно предположить, что указанное начало фразы — это именно определённый артикль, начинающийся с заглавной буквы. Пишем:

phrase 3 = "The "

и применяем:

> try 3

в результате чего получаем:

"f9n137"

Это первые четыре символа ключа, которые мы вносим в определение функции key. Ну и функция main' используется для расшифровки всех одиннадцати зашифрованных сообщений при помощи уже известного ключа. Она выводит на экран дешифровки, при просмотре которых можно делать выводы о следующих символах в некоторых фразах. Ну и пошло-поехало: «There ...», «You don't ...», «The ciphertext...» и т. д. В конце концов, после нескольких десятков итераций удалось расшифровать весь текст.

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

main :: [[Char]]
main = map ((c, s) -> decode s [c]) $ zip (fromHex target) possibleKey'

Эта функция возвращает список списков символов, причём каждый такой список символов — это набор возможных символов на данной позиции расшифрованного целевого сообщения. То есть, первый список символов в этом списке — это все возможные символы на первой позиции целевого сообщения. Именно результат перемножения длин всех списков в результате работы этой функции и дал степень десятки 54 в количестве вариантов ключа. Но, к слову, на некоторых позициях оказалось ровно по одному варианту. Вот результат:

["89TZYBAFGDE",
 "wediho",
 "! edz",
 "(! '135476kbd",
 "stgde",
 "mhideb",
 "4,zxcd",
 ",xyur",
 "utwvsriheb10(",
 "'.0stu",
 "2! ed",
 "cmj7",
 "dez",
 "rsdefl",
 "eljhirs4201",
 "psa8.",
 "ogqpr",
 "mbde?",
 "t' !64",
 "yxzedih",
 "srih",
 ")(47;:",
 "' ",
 "WVPGD",
 "hiprs",
 ";2'zxysolmfde",
 "!(76niuwv",
 "af '98;576",
 "tuj3",
 "sbc",
 "3ixy",
 "gni?9",
 "?ng",
 " !h",
 "wa",
 ";89) 'zf",
 "rs)",
 "t",
 "rsmbcde0",
 "e",
 "a",
 "m",
 "w)(' ",
 "cbd",
 "nirpq!(",
 "p",
 "hi",
 "e",
 "sred",
 "d-,3",
 "z1' ",
 "4vwtuqnoi",
 "zedb",
 "vq,",
 "'?1ed",
 "(urfd",
 "67 ",
 "ur",
 "srt",
 "?-eb",
 "zs '",
 "to",
 "oihw2",
 "67?,-rspqtue",
 "76 -,ut",
 "-lk",
 "bedsp'?0",
 "yx",
 "oyz-' 9;6",
 "8?xyzjme",
 "ho",
 "54sruedm",
 "utedb76",
 "( '",
 "tba,",
 "ihow",
 "54amlwv",
 "qyon",
 "bu' !67",
 ";:xonc",
 "zxyn",
 "yxzutcb9! ",
 "' !.6?debsz"]

Тем не менее, можно было бы применить частотный анализ для обработки этого списка, особенно если взять 3-граммы (как мне кажется). Но реализацию этой задачи оставляю на усмотрение вдумчивого читателя.

Блочные шифры

Во второй задаче слушателям просто предложили расшифровать четыре строки, зашифрованные по стандарту AES. Были даны и ключи, и режимы шифрования, и сами шифровки. Надо было просто взять и расшифровать их. И, несмотря на то, что рекомендовалось самостоятельно реализовать алгоритм шифровки и дешифровки, в самой лекции подробностей о стандарте не давалось, а читать многие страницы спецификации как-то не входило в планы. Поэтому был выбран простой пусть — использование готовой библиотеки. Благо, что для языка Haskell есть модуль Codec.Crypto.AES, который находится в библиотеке с незамысловатым названием AES. Поэтому:

> cabal update
...

> cabal install AES
...

После этого в свой модуль можно подключать необходимый модуль:

import qualified Codec.Crypto.AES as AES

Печаль с этим модулем заключается в том, что он использует тип ByteString, причём печаль даже не в этом (это прекрасный тип), а в том, что в одной и той же функции используется как обычная реализация этого типа, так и ленивая, так что надо подключать оба модуля и внимательно следить за преобразованием строк из задания.

import qualified Data.ByteString as BS
import qualified Data.ByteString.Lazy as BSL

Ну там было подключено ещё несколько модулей, в том числе и реализованные ранее модули Xoring и Groupable. Также чуть ли не один в один из задачи были перенесены в виде функций key, cipher, iv и mode все исходные данные. Все эти функции получают на вход число от 1 до 4, а возвращают строку, содержащую соответственно ключ, зашифрованный текст, IV и режим работы алгоритма. Причём для последнего пришлось реализовать экземпляр класса Eq, поскольку в главной функции для решения значения этого типа сравнивались между собой, а автору модуля Codec.Crypto.AES почему-то было лениво написать deriving Eq при определении типа Mode.

И вот главная функция:

main :: IO ()
main = mapM_ (putStrLn . (i -> if mode i == AES.CBC
                                  then unpadding $ decrypt i
                                  else decryptCTR i))
             [1..4]
  where
    decrypt i   = AES.crypt (mode i) (key i) (iv i) AES.Decrypt (cipher i)
    unpadding s = toString $ BSL.take (BSL.length s - fromIntegral (BSL.last s)) s

Она просто выводит на экран подряд четыре строки, полученные в результате дешифровки. Поскольку в задании используется два режима шифрования, то эти режимы проверяются для каждого задания, в результате чего вызывается правильный метод дешифровки. Для режима CBC дешифровка производится тут же, после чего удаляются служебные биты, добавленные к расшифрованному тексту для выравнивания. Для режима CTR вызывается следующая функция:

decryptCTR :: Int -> String
decryptCTR i = decryptCTR' (key i) (iv i) (cipher i)

decryptCTR' :: BS.ByteString -> BS.ByteString -> BSL.ByteString -> String
decryptCTR' key iv c
  = toString $
      BSL.concat $
      map ((i, ct) -> AES.crypt AES.CTR key (createIV iv i) AES.Decrypt ct) $
                         zip [0..] $
                         groups 16 c
  where
    createIV iv i = BS.snoc (BS.init iv) (BS.last iv + fromIntegral i)

Основная функция decryptCTR является просто обёрткой над функцией decryptCTR', которая передаёт по 16 бит в функцию crypt из установленного модуля. Именно так, поскольку в режиме CTR эта функция из установленного модуля принимает только по 16 байт.

Ну и функция преобразования из типа ByteString в тип String проста:

toString :: BSL.ByteString -> String
toString = map (chr . fromIntegral) . BSL.unpack

Решение задачи № 2 готово.

Аутентификация сообщений

В третьей задаче необходимо было реализовать алгоритм аутентификации длинных файлов. Некто задумал создать некий ресурс для скачивания то ли фильмов, то ли музыки. Соответственно, у этого некто есть желание сделать так, чтобы пользователь, скачавший видео-файл, был уверен, что файл корректен, в нём все биты аутентичны. Для этого можно воспользоваться простым методом хэширования, например, — алгоритмом SHA. Однако это обозначает, что аутентификация файла может быть произведена только после полного скачивания оного. Это неприятно, поскольку пользователи скачивают файл для просмотре он-лайн, а это значит, что аутентификация должна производиться по мере скачивания.

Преобразовать стандартный алгоритм SHA для осуществления данной цели несложно. Надо разбить файл на кусочки по 1 Кб и получить значение хэш-функции для последнего кусочка (который может быть меньше, чем 1 Кб). Затем полученную хэш-функцию последнего кусочка присоединить к предпоследнему кусочку файла и для этой последовательности байтов снова подсчитать значение хэш-функции. И так далее. Когда мы получим значение хэш-функции для самого первого кусочка длиной 1 Кб, в нём будет содержаться аутентификационная информация для всех остальных кусочков и их хэш-функций.

В итоге сервис отдаёт нам хэш-функцию для первого кусочка файла длиной 1 Кб с добавленной к нему хэш-функцией второго кусочка и т. д. Получив эти данные, мы можем убедиться в аутентичности первого 1 Кб данных, начать воспроизводить видео, а по мере скачивания постепенно убеждаться в аутентичности всех остальных кусочков.

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

Опять же, в составе библиотек для языка Haskell уже есть модуль Data.Digest.Pure.SHA из пакета SHA, который позволяет вычислить хэш-функцию для заданной последоствальности байтов. Этим модулем мы и воспользуемся, предварительно установив библиотеку:

> cabal update
...

> cabal install SHA
...

Всё готово, и вот полное решение:

import qualified Data.ByteString.Lazy as BSL
import qualified Data.Digest.Pure.SHA as SHA

import Groupable

main :: FilePath -> IO ()
main fn = do cnt <- BSL.readFile fn
             let chunks = reverse $ groups 1024 cnt
             print $
               snd $
               foldl createSHA (SHA.sha256 $ head chunks) $
               tail chunks

createSHA sha b = SHA.sha256 $ BSL.append b $ SHA.bytestringDigest sha

Здесь функция main принимает на вход имя файла и печатает на экране значение хэш-функции для него. Работа ведётся со значениями типа ByteString, поэтому для начала файл полностью загружается в память (с учётом ленивости языка, конечно), затем мы получаем при помощи реализованной ранее функции groups список списков байтов длиной по 1 Кб, обращаем его задом наперёд и сворачиваем при помощи функции createSHA.

Эта функция возвращает подсчитанный хэш-код для очередного кусочка файла (задаётся вторым аргументом). Этот хэш-код считается при помощи функции sha256 из упомянутого модуля. Функция bytestringDigest из этого же модуля просто преобразует хэш-код из внутреннего представления в тип ByteString. После свёртки мы просто выводим подсчитанный хэш-код на экран. Вот и всё.

Аутентификация шифровок

Четвёртая задача показывала, что нельзя самостоятельно реализовывать системы шифрования, даже если есть уверенность в полном понимании алгоритма — ведь любая, совершенно любая оплошность (типа, например, различие времени подсчёта того или иного значения, которое замеряется злоумышленниками с точностью до наносекунд) может стать причиной взлома шифра, даже если сам шифр не поддаётся такому простому взлому.

Итак, вот уже знакомый нам стандарт AES. У него есть режим шифрования CBC, в котором используются так называемые «набивочные байты» — если очередной блок шифруемого текста не кратен 16, то остаток до 16 набивается специальными байтами. Так вот некий сайт принимает зашифрованное сообщение. И если оно не проходит проверку на аутентичность (неправильный байт набивки), то сервер возвращает ошибку 403. А если набивочный байт корректен, то сервер, как это ни странно, возвращает ошибку 404. Это распространённая оплошность в системах шифрования — имя ей Padding Oracle.

Данную задачу мы будем решать в автоматизированном режиме криптоанализа. Для этого надо последовательно пробежаться по каждому байту в зашифрованном сообщении и попытаться сделать для него предположение о том, какой для этого байта может быть набивочный байт. Пробегаться мы будем непосредственно при помощи функции main, которой будем передавать номер байта (с конца), который мы хотим проверить. Вот определение этой функции:

main :: Int -> IO ()
main n = do rsp <- mapM (HTTP.simpleHTTP . HTTP.getRequest) $ makeTargetURL n [0..255]
            print $
              fst $
              head $
              filter ((== 404) . snd) $
              zip (map chr [0..255]) $
              map (rspCodeToInt . either undefined HTTP.rspCode) rsp

Здесь при помощи функции makeTargetURL мы создаём 256 вариантов URL Для атаки, после чего засылаем к серверу запросы. Получаем их, преобразуем в число (собственно, этого можно было и не делать, но так, вроде бы, красивее), сцепляем с номерами байтов, чтобы не забыть, какому байту соответствовал ответ сервера 404, после чего фильтруем список ответов как раз на поиск ответа 404. Как только он найден (а он находится по условиям задачи один и только один раз), мы его достаём из списка (head), после чего достаём из пары байт (fst) и выводим его на экран (print).

Интерес представляет определение функции makeTargetURL. Она специальным образом вставляет в шифровку под названием targetCP набивочный байт. Алгоритм вставки определяется стандартом AES для режима CBC (и вот тут пришлось немного почитать стандарт, хотя при выполнении задачи № 2 этого делать не хотелось). Вот её определение:

makeTargetURL :: Int -> [Int] -> [String]
makeTargetURL n = map (x -> targetURL ++ (headOfCP' ++ toHex (xorStrings (fromHex tailOfCP') $
                         xorStrings (chr x : decrypted) (fromHex padding'))) ++ tailOfCP)
  where
    padding'               = padding n
    (headOfCP,  tailOfCP)  = splitAt (length targetCP - 32) targetCP
    (headOfCP', tailOfCP') = splitAt (((-) `on` length) headOfCP padding') headOfCP

Осталось дать определения двум служебным функциям:

rspCodeToInt :: Num a => (a, a, a) -> a
rspCodeToInt (x, y, z) = 100 * x + 10 * y + z

padding :: Int -> String
padding n = toHex $ replicate n $ chr n

После этого всё готово для атаки. Начинаем с того, что запускаем функцию main с параметром 1. Программа долго думает (она получает 256 ответов от сервера через сеть), после чего выводит на экран:

't'

Собственно, сразу же можно сделать оптимизацию криптоанализа, поскольку ясно, что это — набивочный байт, а поскольку его код равен 9, то их будет ровно 9. Так что следующий запуск функции main надо осуществлять с параметром 10. Опять ожидание, после которого на экране появляется символ «e». Ну и т. д.

Единственное, что необходимо отметить, так это то, что криптоанализ необходимо производить секциями по 16 байт. Это значит, что константная функция targetCP определена специальным образом:

targetCP :: String
targetCP = "f20bdba6ff29eed7b046d1df9fb70000" ++
           "58b1ffb4210a580f748b4ac714c001bd" ++
           "4a61044426fb515dad3f21f18aa577c0" ++
           "bdf302936266926ff37dbf7035d5eeb4"

После того, как мы расшифровали последние 16 байт сообщения, мы комментируем четвёртую секцию в определении этой функции и начинаем снова с 0 в качестве параметра функции main. Ну и наращивание функции decrypted также производится постепенно. Определение этой функции здесь не привожу, чтобы не раскрывать решение.

Обмен ключами

В задаче № 5 осуществляется подсчёт дискретного логарифма. Дискретный логарифм используется в протоколе Диффи-Хеллмана для обмена ключами в открытом канале связи. Суть — использование вычислительной сложности поиска дискретного логарифма. Однако в некоторых случаях дискретный логарифм можно найти довольно просто. Например, использование атаки типа «Встреча посередине» (Meet in the middle attack).

Пусть есть довольно большое простое число p. И пусть есть число g, входящее во множество чисел, имеющих обратный элемент в кольце вычетов для p. И пусть у нас есть число h = g^x. Задачей является нахождение этого показателя степени x. Мы знаем, что 1 < x < 2⁴⁰, и простой перебор дал бы нам необходимость искать среди 2⁴⁰ вариантов. Но мы можем категорически сократить множество вариантов для перебора до 2²⁰.

Пусть B = 2²⁰. В этом случае можно записать x = x₀B + x₁. Затем мы имеем: h = g^x = g^{x₀B + x₁} = (g^B)^{x₀ * gx₁}. Далее если переместить один из множителей через знак равенства, то получаем: h/g^x₁ = (g^B)^x₀.

Последнее выражение и есть база для проведения атаки — в нём необходимо осуществить только 2²⁰ переборов. Алгоритм простой:

• Построить хэш-таблицу, в которой будут храниться значения h/g^x₁.
• Осуществить перебор всех значений (g^B)^x₀ для поиска в хэш-таблице (в качестве значения). Если такое значение найдено, что по нему и его номеру строится результат при помощи формулы x = x₀B + x₁.

Вот и всё. Реализация этого алгоритма на основе уже написанного модуля Modulo не занимает много строк:

hashTable :: Map.Map Integer Integer
hashTable = Map.fromList $
              map (i -> (fromJust $
                            fmap (`mod` p) $
                            (*) <$> Just h <*> inverse p (power p g i), i))
                  [0..b]

solve :: Integer
solve = ((x0, Just x1) -> x0 * b + x1) $
          head $
          filter (isJust . snd) $
          map (i -> (i, Map.lookup (rightSide i) hashTable)) [0..b]
  where
    rightSide = power p (power p g b)

Как видно, функция hashTable строит хэш-таблицу, а функция solve решает задачу. Тут осуществляется два перебора по 2²⁰. Если запустить функцию solve в режиме интерпретации, то вычисление займёт довольно много времени, так что рекомендуется откомпилировать программу с параметром компиляции -O2 (усиленная оптимизация). Это позволит найти ответ примерно за минуту.

Шифрование при помощи открытых ключей

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

Например, если некто решил реализовать шифрование при помощи выбора двух простых чисел p и q в районе некоторого довольно большого числа R. В этом случае факторизация их произведения займёт очень немного времени. Пусть, скажем, |p — q| < 2N^1/4. Пусть A является средним арифметическим простых чисел p и q. Поскольку оба они нечётные, то A является целым числом. Исходное условие даёт нам ключ к атаке: |A — sqrt(N)| < 1. Всё, что нам остаётся сделать, это округлить число sqrt(N), получив при этом A. Дальнейшее вычисление простых чисел p и q остаётся делом техники:

firstTask :: Integer
firstTask = a - x
  where
    a = numericSqrt n1
    x = numericSqrt (a^2 - n1)

Во второй задаче по условию |p — q| < 2¹¹N^1/4, но и это не проблема:

secondTask :: Integer
secondTask = fst $ head $ dropWhile ((p, q) -> p * q /= n2) $ map factors [n2sqrt .. n2sqrt + 2^20]
  where
    factors i = (i - diff i, i + diff i)
    n2sqrt    = numericSqrt n2
    diff i    = numericSqrt (i^2 - n2)

Третья задача выглядит сложнее, но ежели подумать, но не намного. Здесь |3p — 2q| < N^1/4. Если привести это дело к среднему арифметическому, как в первой задаче, то решение будет найдено тут же (и даже без перебора, как во второй задаче):

thirdTask :: Integer
thirdTask = (a - x) `div` 6
  where
    a = 2 * numericSqrt (6 * n3) - 1
    x = numericSqrt (a^2 - 24 * n3)

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

Четвёртая задача требует расшифровать шифровку, полученную методом RSA, при одном известном показателе степени и простых числах из первой задачи. Собственно, тут решать нечего — находим второй показатель степени, возводим шифровку в степень найденного показателя по модулю известного числа (оба множителя этого числа известны), а потом просто переводим это огромное число в шестнадцатеричную строку. Ну и, наконец, из шестнадцатеричной строки в обычную, печатая результат на экране:

fourthTask :: String
fourthTask = tail $ dropWhile (/= 'NUL') $ fromHex $ intToHex $ power n1 ct d
  where
    a      = numericSqrt n1
    x      = numericSqrt (a^2 - n1)
    (p, q) = (a - x, a + x)
    phi    = (p - 1) * (q - 1)
    d      = fromJust $ inverse phi e

Осталось дать определения двум служебным функциям numericSqrt и getRoot, через которую выражается первая. Эти функции нужны для численного поиска корней, причём в целях числах. Вот они:

numericSqrt :: Integer -> Integer
numericSqrt n = getRoot (0, n) 2 n

getRoot :: (Integer, Integer) -> Integer -> Integer -> Integer
getRoot (mn, mx) e n | mn  == mx = mn
                     | mid == mn = mid + 1
                     | mid == mx = mid
                     | otherwise = case (mid^e) `compare` n of
                                     EQ -> mid
                                     LT -> getRoot (mid, mx) e n
                                     GT -> getRoot (mn, mid) e n
  where
    mid = (mn + mx) `div` 2

Ну вот, собственно, и всё.

Заключение

Хочу поблагодарить всех читателей, осиливших данную заметку. Если кто-то сможет после этого оставить комментарий к статье — всегда милости прошу.

Замечания к представленному решению:

1. Необходимо подумать, как можно слить три практически идентичных определения экземпляров класса Groupable в одно. Сделать и это при помощи Template Haskell или ещё как-то мудрёно — надо провести исследование.
2. Функции fromHex, toHex и intToHex из модуля Xoring надо бы переопределить при помощи использования примитивов для организации рекурсии над списками.
3. Для автоматической расшифровки первого задания можно воспользоваться техникой частотного анализа по 3-граммам. Для этого необходимо собрать значительный корпус текстов на тему криптографии, построить на его основе набор 1-, 2- и 3-грамм, провести сопоставление. Это можно сделать, в том числе, и при помощи описанного мной ранее инструментария для построения N-грамм.
4. Вполне можно реализовать полностью автоматическую дешифровку в задаче № 4, поскольку для всех байтов шифровки можно произвести подмену набивочного байта. Для того чтобы это сделать, необходимо довольно непростым образом осуществить разбиение шифровки и дешифрованного сообщения на группы из 16 байтов, после чего комбинировать их друг с другом.

Остаётся перечислить все модули, описанные в данной статье, а также ссылки на них:

• Модуль Groupable — описание класса типов и трёх его экземпляров, позволяющих производить разбиение заданного контейнерного значения на подгруппы.
• Модуль Xoring — набор функций для работы с операцией XOR (символы и строки).
• Модуль Modulo — набор некоторых функций для выполнения операций в модульной арифметике.
• Модуль XORCipher — модуль для решения задачи № 1, содержащий также дополнительные функции для криптоанализа.
• Модуль AESCipher — модуль для решения задачи № 2.
• Модуль SHACR — модуль для решения задачи № 3.
• Модуль PaddingOracle — модуль для решения задачи № 4.
• Модуль Modulo — модуль для решения задачи № 5.
• Модуль RSA — модуль для решения задачи № 6.

И напоследок ссылка на интеллект-карту, которая составлена мной по результатам обучения. Интеллект карта в формате XMind, так что кому интересно — берите.

Мои предыдущие статьи на Хаброхабре про язык Haskell:

• Генерация естественно-языковых фраз при помощи языка Haskell на основе порождающих грамматик и расширенных цепей Маркова
• Реализация конструирования N-грамм и генерации псевдо ЕЯ-текста на их основе на языке Haskell
• Фреймворк для генерации рекурсивных сказок на языке Haskell
• Утилита для работы с N-граммами

Автор: Darkus