Занятие 8

Занятие 8: Хэш-функции и их применение.¶

Цели работы¶

Определение Хэш-функции.
Проверка целостности файлов.
Хранение паролей.
Поиск подстроки в строке алгоритмом Рабина—Карпа.

Хэш-функция¶

Хэш-функция — эта функция, которая преобразует строку (последовательность символов) в число. Основным требованием к хэш-функции является требование равномерного распределения значений. Отсюда и название — хэширование (hashing от англ. «перемешивание»).

Вторым требованием к Хэш-функции является уникальность значений функции для всех значений аргумента. На практике возможно соответствие значения функции нескольким значениям аргумента — так называемая коллизия.

Важным свойством с точки зрения приложений кибербезопасности Хэш-функции является невозможность восстановления значения аргумента по известному значению функции за разумное время.

Библиотека hashlib¶

Для вычисления хэш-функции в python используются функции библиотеки hashlib. Например, код ниже вычисляет хэш-функцию строки Hello world! с помощью алгоритма SHA. Запустите код в ячейке ниже:

In [ ]:

import hashlib
m = hashlib.sha256()
m.update(b"Hello world!")
print(m.hexdigest())

Применение Хэш-функции¶

Проверка целостности файлов¶

Одно из распространенных применений Хэш-функции — это подтверждение целостности файлов при передаче их по каналам связи/скачивания с веб-ресурсов. Если значение Хэш-функции полученного по сети файла совпадает с эталонным значением, значит файл передан без искажений. Код в ячейке ниже осуществляет чтение файла и вычисление MD5 значения Хэш-функции:

import hashlib
md5_hash = hashlib.md5()
with open("file.txt", "rb") as f:
    while True:
        data = f.read(2048)
        if not data:
            break
        md5_hash.update(data)
print(md5_hash.hexdigest())

Задание 1 — создайте текстовый файл и вычислите его md5 хэш с помощью примера кода выше.

In [ ]:

Хранение паролей¶

Другим распространенным применением Хэш-функции является безопасное хранение паролей. В этом случае хранят не сами пароли, которые пользователь ввел, например, при регистрации на сайте, а результат вычисления их хэш-функции.

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

Для генерации хэша пароля можно использовать функцию pbkdf2_hmac() из библиотеки hashlib. Функция pbkdf2_hmac() принимает пять параметров:

hash_name: алгоритм хеш дайджеста для HMAC;
password: пароль, превращенный в ключ;
salt: случайно сгенерированная соль;
iterations: итерации в вычислении (чем больше, тем длиннее вычисления);
dklen: длина ключа вывода (не обязательно).

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

Пример кода генерации соли:

import os
salt = os.urandom(32)

Параметр 32 является размером, возвращаемым в байтах.

Ниже пример кода генерации хэш-функции от пароля:

import hashlib
import os

salt = os.urandom(32)
password = 'QWasZX12'
hash_pass = hashlib.pbkdf2_hmac('sha256', password.encode('utf-8'), salt, 100000)

Использованы следующие параметры функции hashlib.pbkdf2_hmac:

'sha256' — алгоритм хеширования
password.encode('utf-8') — пароль в виде байтов
salt — Соль
число итераций алгоритма хэширования, затрудняющее подбор пароля

Для последующего сравнения введенного пользователем пароля необходимо хранить в базе данных хэш и соль.

Задание 2 — Реализуйте пользовательский ввод пароля и сравнение с сохраненным эталоном.

In [ ]:

Поиск подстроки в строке алгоритмом Рабина—Карпа¶

В осеннем семестре рассматривался "наивный" алгоритм поиска подстроки в строке с квадратичным временем исполнения в наихудшем случае $O(n^{2})$, который заключался в последовательном наложении подстроки p на строку s.

На этом занятии будет рассмотрен алгоритм поиска подстроки p в строке s с линейным временем выполнения $O(n)$ — алгоритм Рабина—Карпа, основанный на применении Хэш-функции.

Алгоритм основан на том факте, что если строка-образец p (длины m) и подстрока длины m символов, начинающаяся с позиции i строки s совпадают, то должны совпадать и их хэш-функции. Если же строки разные, то и их хэш-функции почти наверняка отличаются. Одинаковые хэш-функции для разных строк должны встречаться настолько редко, что можно допустить время $O(m)$ на явную проверку идентичности строк при совпадении хэш-функций. Это сводит сложность поиска подстроки в строке к вычислениям $n-m+2$ значений хэш-функции плюс небольшое число сравнений сложности $O(m)$ строк с одинаковыми значениями хэш-функций.

Надлежащий выбор хэш-функции позволит тратить на ее вычисление для разных отрезков строки s время, меньшее $O(m)$. Таким правильным выбором является хеш-функция m символов строки s, начинающихся с символа j: $$H(s, j) = (\sum_{i=0}^{m-1} \alpha^{m-(i+1)}\times ord(s_{i+j})) mod{q},$$ где $ord(c)$ — ANSI-код символа c, q — простое число, а $\alpha$ — число от 0 до q-1.

Удобство выбора именно такой хэш-функции заключается в том, что $H(s, j+1)$ (т.е. хэш-функция от подстроки s длины m, сдвинутой на 1 символ) равна: $$H(s, j+1) = (\alpha(H(s, j)-\alpha^{m-1}ord(s_j)) + ord(s_{j+m})) mod {q}.$$ Другими словами, если нам уже известна хэш-функция $H(s, j)$ для подстроки, начинающейся в позиции j, то хэш-функцию подстроки с позиции j+1 можно вычислить выполнив две операции умножения, одну операцию сложения, одну операцию вычитания и одну операцию вычисления остатка от деления.
Одним из возможных эффективных методов выбора пары $\alpha$ и q следующий: $\alpha = 2,$ q — случайное число из диапазона $[2...n^3]$.

Возможная реализация алгоритма Рабина-Карпа на Python выглядит следующим образом (принимает на вход строку s и образец p, возвращает индекс начала искомого образца в строке, либо -1, если образец не найден):

def rabin_karp(s, p):
    n = len(s)
    m = len(p)
    hash_p = hash_func(p);
    for i in range(n-m+1):
        hash_s = hash_func(s[i:i+m])
        if hash_s == hash_p:
            if s[i:i+m] == p:
                return i
    return -1

Задание 3 — Реализуйте функцию hash_func() в соответствии с описанием выше и скорректируйте код функции rabin_karp(s, p) из примера выше, чтобы получить работающую реализацию алгоритма Рабина-Карпа. Продемонстрируйте ее работу.

In [ ]: