![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
mns2012Отталкиваясь от материала предыдущих записей об энтропии и её оценках:
Как в анекдоте о программисте, который для того, чтобы объяснить сыну-первоклашке, что такое сложение, "для ровного счёта" взял 1024 предмета, мне проще всего в качестве функции привести пример аутентификационного ключа.
Предположим, что наш PNG-файл, изображающий капельки чернил, служит ключом для входа в информационную систему. Чем не функция?! Тем более, что я одним выстрелом поражаю две цели, кроме всего прочего демонстрируя, как случайность можно использовать для построения функции.
Спецификация может оказать сильное влияние на то, как мы должны охарактеризовать тот или иной исход. Например, если мой сосед говорит, что честно выиграл джекпот четыре раза подряд, я имею статистические основания усомниться в его искренности (если он, конечно, психически здоровый человек). С точки зрения теории вероятностей, ни один даже самый маловероятный результат нельзя исключать. Однако, с точки зрения статистики, в практических расчётах в каждой задаче существует предел чувствительности, ниже которого мы совершенно спокойно обнуляем вероятность крайне маловероятных событий. Об этом мы уже говорили подробно здесь.
2. Основы аутентификационного хэширования данных
Итак, предположим, что некий алгоритм преобразует наш файл изображений в (почти...) уникальный хэш, который и будет служить аутентификационным ключом. Одним из таких алгоритмов является SHA-256. Он обрабатывает данные блоками в 512 бит, используя преобразуя данные путём применения сложных комбинаций логических битовых операций. Этот алгоритм устойчив к коллизиям на практике. Изменение значения любого пикселя приведёт к изменению значения хэша.
Значения хэшей в 16-ричном формате, вычисленные:
Однако можно задать вопрос:
— Правда ли, что если хэширование производится с потерей информации, то при фиксированной длине хэша возможны ситуации, когда значение хэш-функции для различных значений аргумента (в нашем случае различных исходных файлов изображений) будет совпадать?
— Да. Эти совпадения носят название коллизий. Давайте поподробнее разберёмся с ними.
Что такое коллизия хэшей?
Коллизия — это равенство значений хэш-функции для двух разных аргументов:
Почему в общем случае нельзя утверждать, что коллизий нет?
Если хэш имеет фиксированную длину (например, 256 бит), а количество возможных входных данных — бесконечно (любые файлы, изображения и т.д.), то, в согласии с принципом Дирихле (в англоязычной литературе — the pigeonhole principle), неизбежно существуют коллизии: когда множество входов бесконечно, а множество возможных выходов конечно, разные входы обязательно совпадут по значению. Так что никакая хэш-функция конечной длины не может гарантировать отсутствие коллизий в принципе.
Когда можно утверждать, что коллизий не будет?
Только если все возможные входные данные конечны и их число меньше или равно числу возможных хэш-значений.
Например:
Вероятность коллизии
Для хэша длиной n бит возможны 2n разных значений. Если мы хэшируем случайные данные, вероятность коллизии можно оценить по известной задаче о вероятности совпадения дней рождения в группе людей, поскольку там тоже ищется вероятность коллизии (два человека родились в один и тот же день) при выборе k (число людей в группе) элементов из N (число дней в году). Как результат прямой аналогии между этими задачами, математическая модель у них одна и та же.
Вероятность коллизии хэшей составляет примерно:
P ≈ k2/2N.
при малых P.
Давайте убедимся, что это так.
1. Вероятность отсутствия коллизии обозначим Pуник.
Мы считаем вероятность того, что все k хэшей уникальны (то есть, что нет двух одинаковых).
Или в более компактной форме:
2. Вероятность коллизии P
Вероятность хотя бы одной коллизии P является дополнительным событием к Pуник:
3. Аппроксимация (приближение для малых P)
В криптографических задачах N очень велико N = 2n, тогда как обычно k≪N. В этом случае можно использовать аппроксимацию, которая ведет к формуле, указанной выше.
Мы используем следующее приближение для малых x: (1 - x) ≈ e-x. Перепишем Pуник с учётом этого выражения:
P ≈ k2/2N.
3. Итог
В следующей записи данного цикла мы займёмся разбором примера, в котором мы оценим значения энтропии и колмогоровской сложности программного кода аутентификационной хэш-функции.
пойдём далее и рассмотрим понятие спецификации.
1. Спецификация — формализованное описание
Возьмём те же PNG-файлы, с которыми мы работали раньше:
Брызги чёрной краски на белой бумаге.
Формат: PNG. Изображение чёрно-белое, глубина 8 бит/пиксель.
Размеры: 478 x 305 пикселей
Пример изображения со значением энтропии, близким к максимуму (цифровой шум).
Формат: PNG. Изображение чёрно-белое, глубина 8 бит/пиксель.
Размеры: 478 x 305 пикселей. Сгенерировано Gemini
Формат: PNG. Изображение чёрно-белое, глубина 8 бит/пиксель.
Размеры: 478 x 305 пикселей
Пример изображения со значением энтропии, близким к максимуму (цифровой шум).
Формат: PNG. Изображение чёрно-белое, глубина 8 бит/пиксель.
Размеры: 478 x 305 пикселей. Сгенерировано Gemini
Как в анекдоте о программисте, который для того, чтобы объяснить сыну-первоклашке, что такое сложение, "для ровного счёта" взял 1024 предмета, мне проще всего в качестве функции привести пример аутентификационного ключа.
Предположим, что наш PNG-файл, изображающий капельки чернил, служит ключом для входа в информационную систему. Чем не функция?! Тем более, что я одним выстрелом поражаю две цели, кроме всего прочего демонстрируя, как случайность можно использовать для построения функции.
- Отмечу попутно, что и здесь первичен дизайн, так как функция, даже использующая случайность, сама отнюдь не случайна. О методе аутентификации на основе случайности, которым пользовались в древнем мире, я уже рассказывал здесь.
Спецификация может оказать сильное влияние на то, как мы должны охарактеризовать тот или иной исход. Например, если мой сосед говорит, что честно выиграл джекпот четыре раза подряд, я имею статистические основания усомниться в его искренности (если он, конечно, психически здоровый человек). С точки зрения теории вероятностей, ни один даже самый маловероятный результат нельзя исключать. Однако, с точки зрения статистики, в практических расчётах в каждой задаче существует предел чувствительности, ниже которого мы совершенно спокойно обнуляем вероятность крайне маловероятных событий. Об этом мы уже говорили подробно здесь.
- Можно много говорить по поводу того, что биологическая эволюция (ох, уж мне эта эволюция, как же без неё-то?!) — неэргодический процесс, но
всё-таки совесть тоже надо иметьстатистика — упрямая вещь. - Тьмочисленные интернет-популяризаторы — кто по незнанию, а кто по лукавству — предпочитают не замечать различия постановок задач в статистике и в теории вероятностей. Одним из таких деятелей, довольно известных западной аудитории, является Нил де Грасс Тайсон, утверждающий здесь, что "кому-то ведь должен был выпасть счастливый билет". Он думал, наверное, что это прокатит как аргумент против тонкой настройки параметров вселенной, допускающей разумную жизнь.
Вот он, этот коварный тип гражданской наружности.
Здесь он объясняет мир: кому-то же должен был выпасть счастливый билет. Какая наивность или уж явное лукавство. Одно из двух!
Здесь он объясняет мир: кому-то же должен был выпасть счастливый билет. Какая наивность или уж явное лукавство. Одно из двух!
2. Основы аутентификационного хэширования данных
Итак, предположим, что некий алгоритм преобразует наш файл изображений в (почти...) уникальный хэш, который и будет служить аутентификационным ключом. Одним из таких алгоритмов является SHA-256. Он обрабатывает данные блоками в 512 бит, используя преобразуя данные путём применения сложных комбинаций логических битовых операций. Этот алгоритм устойчив к коллизиям на практике. Изменение значения любого пикселя приведёт к изменению значения хэша.
Значения хэшей в 16-ричном формате, вычисленные:
- для изображения клякс: e37ec384937d1aa6c358f9d04dd1060ce360acff2adb71b091fd526ba22dfe8e;
- для изображения шума: 9608cd25ad2e57f7371ed8c20ff68df39492d4661fdc59273808808964ee5f11.
- Односторонность (невозможно по значению хэша восстановить данные по той простой причине, что хэширование производится с потерей данных);
- При определённом умении хэшировать данные можно добиться крайне низкой вероятности того, что некто, используя другой графический файл, смог бы получить точно такое же значение хэш-функции. Об этом мы поговорим чуть ниже.
Однако можно задать вопрос:
— Правда ли, что если хэширование производится с потерей информации, то при фиксированной длине хэша возможны ситуации, когда значение хэш-функции для различных значений аргумента (в нашем случае различных исходных файлов изображений) будет совпадать?
— Да. Эти совпадения носят название коллизий. Давайте поподробнее разберёмся с ними.
Что такое коллизия хэшей?
Коллизия — это равенство значений хэш-функции для двух разных аргументов:
H(x1) = H(x2), при x1 ≠ x2.
Почему в общем случае нельзя утверждать, что коллизий нет?
Если хэш имеет фиксированную длину (например, 256 бит), а количество возможных входных данных — бесконечно (любые файлы, изображения и т.д.), то, в согласии с принципом Дирихле (в англоязычной литературе — the pigeonhole principle), неизбежно существуют коллизии: когда множество входов бесконечно, а множество возможных выходов конечно, разные входы обязательно совпадут по значению. Так что никакая хэш-функция конечной длины не может гарантировать отсутствие коллизий в принципе.
Когда можно утверждать, что коллизий не будет?
Только если все возможные входные данные конечны и их число меньше или равно числу возможных хэш-значений.
Например:
- Если вы хэшируете байты длиной ≤ 32 байта, а хэш — 256 бит (32 байта), и функция биективна — тогда теоретически можно построить безколлизионный хэш.
- Однако в реальности входные данные чаще всего гораздо больше.
Вероятность коллизии
Для хэша длиной n бит возможны 2n разных значений. Если мы хэшируем случайные данные, вероятность коллизии можно оценить по известной задаче о вероятности совпадения дней рождения в группе людей, поскольку там тоже ищется вероятность коллизии (два человека родились в один и тот же день) при выборе k (число людей в группе) элементов из N (число дней в году). Как результат прямой аналогии между этими задачами, математическая модель у них одна и та же.
Вероятность коллизии хэшей составляет примерно:
P ≈ k2/2N.
при малых P.
Давайте убедимся, что это так.
1. Вероятность отсутствия коллизии обозначим Pуник.
Мы считаем вероятность того, что все k хэшей уникальны (то есть, что нет двух одинаковых).
- Первый хэш (1): Может принять любое из N значений. Вероятность уникальности: N/N = 1.
- Второй хэш (2): Чтобы быть уникальным, он должен отличаться от первого. Доступно N - 1 значение. Вероятность: (N - 1) / N.
- Третий хэш (3): Должен отличаться от первых двух. Доступно N - 2 значений. Вероятность: (N - 2) / N
- ...
- k-й хэш (k): Должен отличаться от первых k-1 хэшей. Доступно N - (k - 1) значений. Вероятность: (N - k + 1) / N.
Вероятность того, что все k хэшей уникальны Pуник, есть произведение этих вероятностей:
Pуник = (N / N) * ((N - 1) / N) * ((N - 2) / N) * ... * ((N - k + 1) / N)
Или в более компактной форме:
Pуник = N * (N - 1) * (N - 2) * ... * (N - k + 1) / Nk
2. Вероятность коллизии P
Вероятность хотя бы одной коллизии P является дополнительным событием к Pуник:
P = 1 - Pуник = 1 - [(N * (N - 1) * (N - 2) * ... * (N - k + 1)) / Nk]
3. Аппроксимация (приближение для малых P)
В криптографических задачах N очень велико N = 2n, тогда как обычно k≪N. В этом случае можно использовать аппроксимацию, которая ведет к формуле, указанной выше.
Мы используем следующее приближение для малых x: (1 - x) ≈ e-x. Перепишем Pуник с учётом этого выражения:
Pуник = (1 - 1/N) * (1 - 2/N) * ... * (1 - (k - 1)/N) ≈ e-1/N * e-2/N * ... * e-(k - 1)/N
При умножении экспонент, показатели складываются:
Pуник ≈ e-[1/N + 2/N + ... + (k - 1)/N]
Суммируем показатели: 1 + 2 + ... + (k - 1). Это арифметическая прогрессия. Её сумма: S = (k - 1) * k / 2. Тогда:
Pуник ≈ e-[k * (k - 1)] / 2N.
Для очень больших k справедливо: k - 1 ≈ k. Тогда:
Pуник ≈ e- k2/2N.
Отсюда вероятность коллизии P:
P ≈ 1 - e-k2/2N.
Наконец, если k≪N, то выражение k2/2N мало. Тогда мы можем использовать приближение 1 - e-x ≈ x для малых x. Отсюда:
P ≈ k2/2N.
Ч.т.д.
Таблица 1 иллюстрирует, насколько быстро с ростом длины хэша убывает вероятность коллизий.
| Длина хэша n (бит) | Число возможных значений | Число хэшей, необходимое для 50%-й вероятности коллизии |
| 32 | 4.3×10⁹ | ~77×10³ |
| 64 | 1.8×10¹⁹ | ~5×10⁹ |
| 128 | 3.4×10³⁸ | ~2×10¹⁹ |
| 256 | 1.2×10⁷⁷ | ~10³⁸ |
Таблица 1. Вероятность коллизий как функция длины хэша
Из таблицы видно, что для 256-битовой хэш-функции (например, SHA-256) вероятность коллизии практически нулевая для любых реальных объёмов данных (человечество не сможет вычислить столько хэшей, чтобы достичь 1% вероятности).
3. Итог
- Коллизии теоретически неизбежны, если хэш имеет фиксированную длину и множество данных превышает мощность области значений хэш-функции.
- Гарантировать их отсутствие можно только для конечного и ограниченного множества входов.
- В практическом смысле, для хэшей ≥ 128 бит, вероятность коллизии настолько мала, что ею можно пренебречь. Bingo!
Может ли Шура Балаганов, утверждающий, что он честно взял джекпот четыре раза в жизни, оказаться кристально честным человеком? Может быть, и может, но не в нашей вселенной 😁. Так что Нил де Грасс Тайсон нервно курит под лестницей. Теперь он понимает, что такое спецификация и что необходимо объяснять феномен тонкой настройки. Счастливый билет космической лотереи больше не прокатит.
В следующей записи данного цикла мы займёмся разбором примера, в котором мы оценим значения энтропии и колмогоровской сложности программного кода аутентификационной хэш-функции.
