[Python, Программирование] Создание функции губки из MD5 (перевод)

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

news_bot ^® написал(а)
25-Май-2021 19:31

Цитировать

Привет, Хабр. В преддверии старта курса "Python Developer. Professional" подготовили перевод материала.

Во время своих исследований я столкнулся с термином «функция губки». Поиграв с ней и внедрив одну из них в свое ядро, я решил написать эту статью о том, как создать упрощенную версию. Чтобы свести низкоуровневый криптографический код к минимум, мы будем полагаться на хэш-функцию MD5. Пристегнитесь, разговор будет долгим.Начнем с простой концепции хэш-функции MD5 и будем, основываясь на ней, реализовывать общие функции, которые могут показаться черными ящиками. Каждый шаг будет небольшим, чтобы его можно было усвоить, при этом внося вклад в общее понимание темы. Если что-то кажется неясным, не стесняйтесь обсуждать это в комментариях. Эта статья организована так, что вы можете в любой момент сделать паузу и поиграться с концепциями самостоятельно, или ускорить прочтение, если захотите.Поскольку мы будем основываться на хэш-функции MD5, давайте выделим небольшой раздел, чтобы рассмотреть ее поподробнее. Мы будем смотреть на MD5, как на черный ящик, и игнорировать любые сложные детали ради краткости.Бэкграунд MD5MD5 – это криптографическая хэш-функция, которая отображает произвольный объем данных в 16 байт (или 128 бит). В период своего расцвета MD5 была идеальным вариантом хэширования паролей, проверки файлов на наличие повреждений и маркировки данных на предмет подделки. Позже в течение некоторого времени она считалась ненадежной, и ее не рекомендовалось использовать ни для чего, связанного с безопасностью. Тем не менее эта хэш-функция была хорошо известна и реализована практически для любого когда-либо известного вычислительного устройства. К счастью, в комплекте с Python поставляется набор хэш-функций в модуле hashlib. Так что давайте посмотрим, как она работает. In [3]:

md5(b"Test").hex()
md5(b"Test 123").hex()

Out [3]:

'0cbc6611f5540bd0809a388dc95a615b'

Out [3]:

'f3957228139a2686632e206478ad1c9e'

Как мы видим, входные данные разной длины сопоставляются с выходными данными фиксированного размера, а небольшие изменения входных значений приводят совершенно разным выходным. В целом, именно этого мы и ждали от хэш-функции. В этой статье мы будем использовать хэш-функцию MD5 для создания губки. Но прежде, чем мы начнем, надо бы разобраться с тем, что же такое функция губки.Функция губкиФункция губки – это криптографическая функция, которая может «впитывать» любое количество битов и «выжимать» их, как губка. Немного отличается от того, что мы наблюдали с MD5. В то время как MD5 будет выдавать только выходы фиксированного размера в 16 байт, губка может выдавать 1 байт, 26 байт, 5000 байт или вообще любое количество, которое вам понравится. Звучит забавно и потому может быть полезно для множества различных задач, поэтому займемся нечестивым программированием и превратим MD5 в губку.Губки завораживают. Их можно использовать в качестве хэш-функции, генератора случайных чисел, имитовставок или для шифрования данных. Можно сказать, что губки – это что-то вроде швейцарских ножей. ТеорияДля создания функции губки нужно внутреннее состояние (которое является просто буфером) и функция для псевдослучайного преобразования одного состояния в другое. Мы воспользуемся двумя свойствами хэша MD5. Наш буфер состояния будет 16 байтами выходных данных MD5, а функцией преобразования будет сама MD5.Губка скрывает большую часть своего внутреннего состояния. Как впитанные биты, так и выжатые биты – это лишь небольшая его часть, поэтому выходные данные никогда не показывают полное состояние функции.

Первый шаг – это инициализация состояния, то если либо 0, либо любое другое разумное значение по умолчанию.
Для каждого байта входных данных:
- Первый байт состояния совпадает с входным байтом.
- Состояние заменяется MD5.

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

Выводим первый байт состояния.
Преобразуем состояние с помощью MD5.

Внимание! Лучше не использовать эту практику для слишком чувствительных данных. Здесь представлена реализация доказательства концепции со сломанной функцией MD5, взятой за основу. Лучше выберите себе что-нибудь получше, например ChaCha20 или SHA-512. В целом, все, что нам нужно - большое состояние и функция преобразования, которая действительно хорошо его обрабатывает.

РеализацияТеперь, когда мы вкратце пробежались по теории, самое время перейти к реализации. Мы будем писать ее пошагово и осуществим каждую операцию, о которой упоминали выше. Первый шаг – функция преобразования.Функция преобразованияСледуя вышеизложенной теории, нам нужна функция преобразования, которая примет наше состояние и псевдослучайно сопоставит его с другим состоянием. В нашем случае хэш-функция MD5 выполнит всю тяжелую работу за нас. И под тяжелой работой я подразумеваю, что MD5 сделает за нас вообще практически все.Мы можем преобразовать текущее состояние, передав его в функцию MD5. Вот небольшая демонстрация.In [5]:

# Initial state
md5(b"").hex()
# Transform once
md5(md5(b"")).hex()
# Transform again
md5(md5(md5(b""))).hex()
# And so on...

Out [5]:

'd41d8cd98f00b204e9800998ecf8427e'

Out [5]:

'59adb24ef3cdbe0297f05b395827453f'

Out [5]:

'8b8154f03b75f58a6c702235bf643629'

Похоже, работает. Давайте инкапсулируем это все в метод класса Sponge. Каждый раз при впитывании или выжимании байта мы будем изменять состояние с помощью этого метода.In [6]:

class Sponge(Sponge):
def transform(self):
self.state = md5(self.state)

ИнициализацияКак говорилось ранее, состояние должно быть инкапсулировано, прежде чем мы начнем впитывать и выжимать какие-либо биты. Поскольку мы используем MD5, то хотим, чтобы наше состояние занимало 16 байт. К счастью, MD5 гарантирует, что независимо от значения, которое мы предоставляем, состояние в конечном итоге составит 16 байт. Таким образом, мы можем выбрать любое значение, включая пустую строку. Давайте рассмотрим этот вариант.In [7]:

class Sponge(Sponge):
def __init__(self):
self.state = b""
self.transform()

Посмотрим, все ли работает. После создания экземпляра класса Sponge, мы должны были получить преобразование пустой строки с помощью MD5 - d41d8cd98f00b204e9800998ecf8427e. In [8]:

s = Sponge()
s.state.hex()

Out [8]:

'd41d8cd98f00b204e9800998ecf8427e'

Впитывание байтаПомня логику из раздела теории, мы можем с легкостью написать код для впитывания одного байта. Мы заменим первый байт состояния на входной XOR первый байт, а затем преобразуем состояние.In [9]:

class Sponge(Sponge):
def absorb_byte(self, byte):
self.state[0] = byte ^ self.state[0]
self.transform()

Мы можем быстро проверить, что получаем различные состояния после впитывания различных данных. Давайте попробуем впитать [1,2] и [2,1] и понаблюдаем за разницей в состояниях.In [10]:

s = Sponge()
s.absorb_byte(1)
s.absorb_byte(2)
s.state.hex()

Out [10]:

'29a3a137fccfa18e5cfb5054b13aa412'

In [11]:

s = Sponge()
s.absorb_byte(3)
s.absorb_byte(4)
s.state.hex()

Out [11]:

'0291c72acd7e7da67bedcb15aa4733c6'

Впитывание буфераОбобщение этой концепции на буферы произвольных размеров тривиально. Нужно просто идти по буферу и впитывать байты один за другим. Такая абстракция весьма полезна, поскольку в реальном мире мы обычно работаем с буферами целиком, а не с отдельными байтами.In [12]:

class Sponge(Sponge):
def absorb(self, buffer):
for byte in buffer:
self.absorb_byte(byte)

Быстрая проверка логики: наше состояние должно отличаться от пустого состояния после впитывания байтов. Давайте быстренько проверим это, прежде чем пойдем дальше.In [13]:

s = Sponge()
s.absorb(b"Test")
s.state.hex()

Out [13]:

'28a7cbf238c85bad13cc0fc4933a68ae'

Выжимание байтаПоскольку нам не нужно смешивать входные данные, наша логика выжимания будет проще, чем логика впитывания. Вспоминая теорию, мы выведем первый байт и снова преобразуем состояние, чтобы получить один байт.In [14]:

class Sponge(Sponge):
def squeeze_byte(self):
byte = self.state[0]
self.transform()
return byte

Давайте попробуем создать несколько байтов, и посмотрим, сработает ли это.In [15]:

s = Sponge()
s.absorb(b"Test")
[s.squeeze_byte() for _ in range(5)]

Out [15]:

[40, 243, 39, 189, 220]

Выжимание буфераПереход от извлечения отдельных байтов к извлечению буферов – не слишком сложная задача. Мы используем списочное выражение, чтобы сократить количество кода.In [16]:

class Sponge(Sponge):
def squeeze(self, size):
buf = [self.squeeze_byte() for _ in range(size)]
return bytes(buf)

In [17]:

s = Sponge()
s.absorb(b"Test")
s.squeeze(5).hex()

Out [17]:

'28f327bddc'

Может показаться, что кода слишком мало, но здесь есть все, что нам нужно. Возможно, было бы полезно расширить функционал для удобства, но в 99% вариантов использования этих методов будет достаточно. Теперь начнем играться с нашей губкой.Варианты использованияВ самом начале мы упоминали, что функции губки отличаются широким спектром криптографических вариантов использования. В этом разделе я буду реализовывать их простыми способами, чтобы показать, насколько полезными могут быть губки.Хэш-функции Хэширование – самая простая вещь, которую можно реализовать с помощью губки. На самом деле мы уже видели, как это работает выше. Уточню, что мы можем создать хэш, впитывая все входные данные и выжимая фиксированное количество байтов.In [18]:

def sponge_hash(data):
s = Sponge()
s.absorb(data)
return s.squeeze(10).hex()
sponge_hash(b"123")
sponge_hash(b"Test 123")
sponge_hash(b"Test 113")

Out [18]:

'91e292b50acc3c838a0a'

Out [18]:

'b7a2027b77e56ca5d11f'

Out [18]:

'62eb28a8017c976f7ccc'

Как мы видим, результат соответствует нашим критериям хэш-функции. Входные данные разных размеров сопоставляются с выходными данными фиксированного размера, а небольшие изменения во входных данных приводят к совершенно разным хэшам. Вы можете заменить 10 любой другой длиной, чтобы изменить выходной размер хэша. В целом, более длинные хэши меньше подвержены коллизиям, но занимают больше места. Вы можете поэкспериментировать и выбрать подходящий размер хэша для вашего случая.Генератор случайных чиселГенерация случайных чисел (ГСЧ) также можно реализовать с помощью губки. Основная идея заключается в том, чтобы впитать зерно для ГСЧ, а затем выжать байты для нужного количества случайных чисел. В следующем примере я использую фиксированное начальное значение для генерации десяти 16-битных целых чисел без знака.In [19]:

import struct
s = Sponge()
s.absorb(b"Seeding the RNG")
def rng():
buf = s.squeeze(2)
return struct.unpack('H', buf)[0]
[rng() for _ in range(10)]

Out [19]:

[29342, 19407, 47040, 9984, 55893, 40500, 56312, 36293, 58610, 10880]

Если мы используем одно и то же зерно, то всегда получаем один и тот же результат. Может прозвучать нелогично для задачи генерации случайных чисел, но обычно нужно, чтобы была возможность воспроизвести случайный результат. Если этот вариант вам не подходит, вы можете получить зерно из действительно случайного источника или из чего-то, что регулярно меняется, например, текущее время. Все зависит от того, чего вы ждете от случайных чисел. Ниже я показал, как прочитать случайное зерно из /dev/urandom (https://en.wikipedia.org/wiki//dev/random).In [20]:

s = Sponge()
with open("/dev/urandom", "rb") as urandom:
s.absorb(urandom.read(64))
[rng() for _ in range(10)]

Out [20]:

[56437, 39690, 47308, 16515, 29378, 11318, 32523, 18419, 47972, 4874]

Идея: Вы можете впитывать значения при их генерации, что позволит периодически передавать ГСЧ новые зерна с помощью внешних источников.

ИмитовставкаМы можем использовать функцию губки для создания механизма, который может создавать и проверять подписи с помощью секретного ключа. Этот метод очень распространен в мобильных и веб-приложениях для хранения сеанса на клиенте без возможности в него вмешиваться. Если вы хотите узнать больше об этом варианте использовании, познакомьтесь с таким явлением, как веб-токены JSON. Чтобы создать подпись мы впитываем данные и секретный ключ. После этого можно выжать произвольное количество битов, которые можно использовать в качестве подписи.In [21]:

def sign(data, key):
s = Sponge()
s.absorb(data)
s.absorb(key)
return s.squeeze(5)
data = b"Hello world!"
key = b"password123"
signature = sign(data, key)
signature.hex()

Out [21]:

'480e4c2b9d'

Проверить подпись можно создав подпись самостоятельно и сравнив ее со сгенерированной подписью. Если они совпадают, то данные и подпись не изменились.In [22]:

def verify(data, sig, key):
correct = sign(data, key)
return sig == correct
verify(data, signature, key)

Out [22]:

True

Как и ожидалось, подпись успешно верифицирована. Давайте попробуем немного изменить данные и изменим два символа.In [23]:

data = b"Hello wordl!"
verify(data, signature, key)

Out [23]:

False

Точно также мы можем получить корректные данные и вместо этого подделать подпись. Проверка завершится ошибкой, показав, что и подпись, и данные защищены от повреждения и подделки.In [24]:

data = b"Hello world!"
signature = bytes.fromhex("481e4c2b9d")
verify(data, signature, key)

Out [24]:

False

Потоковый шифрПотоковый шифр позволяет нам шифровать и расшифровывать поток байтов с помощью одного секретного ключа. Его можно использовать, чтобы убедиться, что только вы или кто-то с секретным ключом, может расшифровать данные.In [25]:

def stream_cipher(data, key):
s = Sponge()
s.absorb(key)
output = bytearray(data)
for i in range(len(data)):
key = s.squeeze_byte()
output[i] ^= key
return output
data = b"Hello, world!"
encrypted = stream_cipher(data, b"password123")
encrypted.hex()

Out [25]:

'b571d4065c54547bdf1a002d8e'

Расшифровать потоковый шифр очень просто, и здесь вообще не нужен код. Простое шифрование уже зашифрованного значения с помощью правильного ключа приведет к расшифровке ваших данных. Давайте попробуем расшифровать наши данные с помощью правильных и неправильных паролей.In [26]:

stream_cipher(encrypted, b"password123")
stream_cipher(encrypted, b"password132")

Out [26]:

bytearray(b'Hello, world!')

Out [26]:

bytearray(b'\x12\x88\x98?\x9aESh\x9a\x96\x9d\x17\x1d')

Идея: вы можете объединить код имитовставки и потоковый шифр, чтобы создать зашифрованный и защищенный от подделки фрагмент данных. Называться это будет аутентифицированным шифрованием, которое обычно выполняется в реальных протоколах. Попробуйте реализовать AE и AEAD самостоятельно.Внимание: рекомендуется также включить IV/nonce в ваш ключ, чтобы убедиться, что один и тот же открытый текст шифруется в разные шифротексты.

Временный одноразовый парольВозможно, вы заметили, что в наши дни многие сервисы запрашивают у вас одноразовые токены при попытке аутентификации. Эти токены обычно отображаются в виде 6 цифр и истекают через ~30 секунд. С помощью губки мы можем с легкостью реализовать свою собственную версию. Вот как работают одноразовые токены:

У сервера и клиента есть заранее согласованный секретный ключ.
При проверке подлинности сервер просит клиента создать токен.
Клиент получает текущее время и секретный ключ, чтобы создать токен, и отправляет его на сервер.
Сервер самостоятельно создает токен по тому же ключу и тем же правилам.
Если токены совпадают, клиенту предоставляется доступ.

In [27]:

import time
key = b"Secret key 123"
def get_otp(key, period=10):
t = time.time()
value = int(t / period)
time_left = period - (t % period)
s = Sponge()
s.absorb(key)
s.absorb(str(value).encode('ascii'))
otp = [s.squeeze(1).hex() for _ in range(3)]
otp = ' '.join(otp)
return otp, int(time_left)
otp, time_left = get_otp(key)
f"OTP is '{otp}'."
f"Valid for {time_left} more seconds."

Out [27]:

"OTP is '7c 0b c8'."

Out [27]:

'Valid for 7 more seconds.'

Если код все еще валиден, то есть time_left еще не равен нулю, OTP будет считаться действительным.In [28]:

otp == get_otp(key)[0]

Out [28]:

True

Если мы подождем, пока закончится таймер, наш OTP больше валидироваться не будет.In [29]:

time.sleep(time_left + 1)
otp == get_otp(key)[0]

Out [29]:

False

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

Блочный шифрПотоковые шифры, использующие криптографические хэши, рискуют войти в цикл. Так происходит, когда вызов функции преобразования состояния в итоге возвращается к предыдущему состоянию. Чтобы справиться с этим, мы можем использовать блочный шифр.Основное отличие блочного шифра заключается в том, что вместо того, чтобы создать губку один раз и выжимать из нее байты для всего потока, мы впитываем счетчик вместе с ключом и однократно используемым числом (nonce), чтобы сгенерировать фиксированный блок байтов. Именно отсюда и вытекает название «блочный шифр».In [30]:

BLOCKSIZE = 10
def get_block(key, counter):
s = Sponge()
s.absorb(key)
s.absorb(str(counter).encode("ascii"))
return bytearray(s.squeeze(BLOCKSIZE))
def block_encrypt(data, key):
size = len(data)
result = b""
counter = 0
while data:
# Chop off BLOCKSIZE bytes from the data
data_block = data[:BLOCKSIZE]
data = data[BLOCKSIZE:]
# Generate a block cipher block
block = get_block(key, counter)
for i, byte in enumerate(data_block):
block[i] ^= byte
result += block
counter += 1
return result[:size]
data = b"Hello, world! Don't forget to stay hydrated."
encrypted = block_encrypt(data, b"test")
encrypted.hex()

Out [30]:

'eec587d16686e81d26ed800677e609a6d2fed11b7a27bbb233370cdba1d941cdc01d42c4c3e7ee90a09333c1'

Как и в случае с потоковым шифром, давайте попробуем расшифровать наши данные с помощью правильных и неправильных ключей.In [31]:

block_encrypt(encrypted, b"test")
block_encrypt(encrypted, b"TEST")

Out [31]:

b"Hello, world! Don't forget to stay hydrated."

Out [31]:

b'\xd1%\x17\xd9\xe0\x1bh\xaf~2\xc0\x9f\x8da\xb2\xe4\xa4\x05\x99\xc4\x82\xf7\x02\x0c\xed+\xa1\xf4\xefa?\x82l9Q\x05=B>p%\x9e\xa0q'

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

Материал подготовлен в рамках курса "Python Developer. Professional"

===========
Источник:
habr.com
===========
===========
Автор оригинала: Gokberk Yaltirakli
===========Похожие новости:

Теги для поиска: #_python, #_programmirovanie (Программирование), #_cryptography, #_python, #_md5, #_blog_kompanii_otus (
Блог компании OTUS
), #_python, #_programmirovanie (
Программирование
)

Профиль ЛС

Ответить на тему

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

Текущее время: 22-Ноя 13:48
Часовой пояс: UTC + 5