Можно ли использовать функцию HMAC в качестве генератора случайных чисел и насколько хорошо?

Question

[Егор Медко]

Заинтересовался тем как работает bitcoin-кран-казино - сайт freebitco.in. Почитал про их систему честной игры. Ну типа число которое выпадет генерируется на основе двух строк - server seed и client seed, и нам даётся хэш сида сервера. Процедура получения выпадающего числа там описывается так:
1. Создаётся две строки :
STRING1 = "[NONCE]:[SERVER SEED]:[NONCE]"
STRING2 = "[NONCE]:[CLIENT SEED]:[NONCE]"
Пример :
STRING1 = "438088:cg6s6edldjfe7r875cm6od916zvwp8nz8w8rx2jxx0u2utnn0wty7d9bn8zg5kul:438088"
STRING2 = "438088:Ydbkf5diyLE1FdsN:438088"
2. Затем используется алгоритм HMAC с типом хэширования SHA512 для хэширования STRING1 со STRING2 в качестве секретного ключа, что даёт результат в виде шестнадцатеричной строки из 128 символов.
3. Берутся первые 8 символов строки и конвертируются в десятичную систему.
4. Полученное число делится на 429496.7295 и округляется до ближайшего целого числа.
5. Максимальным возможным числом является 10000.

NONCE это счётчик, который у всех разный и каждый раз увеличивается на 1, так что он может просто храниться в базе у организаторов и подставляться в ключ.

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

Дополнение: в client seed оказывается можно ввести строку любой длины (у меня получилось 64 символа) с алфавитом в 62 знака, и server seed для каждого профиля предположительно разный, с учётом того что бесплатно сатоши можно получать раз в час, это нужны астрономические мощности для нахождения таких сидов сервера.
Так что вряд ли наверное есть такие сиды для которых не будет максимального выйгрыша (при таком-то количестве вариантов), остаётся только вопрос по равномерному распределению чисел - есть ли такая теоретическая информация об функции HMAC или нужно писать программу для выпавших сидов сервера и смотреть распределение? Ну и ещё из варианта обмана пользователей остаётся только коллизия хэша, но это уже недостижимо...

Вообщем буду рад всем кто чем-то поможет или поделится какими-либо рассуждениями по данному вопросу.

Answer 1

[pestunov]

HMAC - это не функция, а схема использования хеш-функции. Поэтому ответ на вопрос зависит от того, какую хеш-функцию используют организаторы казино. Если это современная известная хеш-функция, на которую нет известных опубликованных атак быстрее полного перебора или известных коллизий, то она выдает равномерно распределенные выходы при любых входных данных, даже если они различаются минимально (скажем, на 1 бит). И эти псевдослучайные числа неотличимы от истинно случайных никакими известными способами. Такими функциям, например, являются SHA-3 (Keccak) или SHA2^2 из Биткоина. Российский ГОСТ "Стрибог" пока тоже неуязвим.

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

Так что главный вопрос - какая хеш-функция используется в этом HMACe. Если новая (особенно госстандарт SHA-3 или "Стрибог"), то махинации невозможны, если в программном коде нет каких-нибудь косяков или утечек.

Comments

[Егор Медко]

Благодарю за развёрнутый ответ. Как я и писал, там написано используется функция HMAC-SHA512, я так понял SHA512 это и есть исользуемая хэш-функция.

[pestunov]

Егор Медко, sha512 относится к семейству sha2. Уязвимости найдены только для ее упрощенных версий, поэтому можно считать, что проблем с HMACом на ее основе не должно быть.

Answer 2

[HolySpring]

Если основной seed разворачивается в обратном порядке и путём простых вычислений получается число которое выпало, тогда можно утверждать что seed hash генерируется таким образом что его можно спокойно просчитать методом более заумных вычислений имея на руках всего лишь seed hash-256, client seed и nonce.

Всё дело в цифрах, о которых большинство просто не догадывается.

У тебя есть число, поскольку это пример и мы один ролл использовали чтобы понять систему.

На многочисленных алгоритмах генерации в hash это число будет выглядеть по-разному, но на определённых алгоритмах это число генерируется в один и тот же hash.

Получается казалось бы возьми seed hash-256, client seed, nonce, и генерируй себе в sha-512, а затем возьми из полученной строки в начале всего лишь 8 шестнадцатиричных символов, переведи в десятичное значение и да будет точно так же как и с основным seed, но не тут то было.

Совершенно другие цифры, а в цифрах и заключается всё.

Путаница происходит лишь из-за того что уже полученный hash из числа пропускают через определённый список алгоритмов.

Таким образом, где-то там на глубине матричной Марианской впадины, сам по себе сгенерированный seed hash-256 когда-то был какими-то символами, либо цифрой, а может и двумя или вообще тремя.

Так же с client seed, а nonce он и в Африке виден всем.

Получается, прежде чем вычитать и умножать, либо складывать и делить что-то, нужно это что-то достать из той самой Марианской впадины.

А как это сделать?

Для начала, имея хоть какую-то информацию типа seed hash-256 и client seed, нужно определить через какие алгоритмы эти данные прошли прежде чем стать самими собой.

Зная эту информацию можно в обратном порядке выйти на число которое возможно что-то даст :)

Затем эти числа сопоставляются и вычисляются.

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