Рейтинг:15

Доказуемо честная колода карт, используемая клиентом и сервером

флаг cn

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

Я думал о следующем решении с использованием криптографии и хотел получить отзывы, будет ли оно приемлемо для производственной системы, а если нет, то почему бы и нет:

Шаг 1) Сервер тайно перетасовывает колоду карт в каком-то порядке, скажем следующее (мы опускаем масть для простоты): [3, 9, 2, ..., A]

Затем он создаст следующее сообщение M:
M = "Перетасовка карт: [3, 9, 2, ..., A]. Случайное число: A96A...QT3"

Случайное число — это случайное число, которое сервер генерирует внутри себя и хранит в секрете до завершения игры. Его длины будет достаточно, чтобы предотвратить взлом хэша клиентом методом грубой силы (скажем, его длина составляет 512 символов).

Теперь сервер будет хешировать M, используя sha-256 или какой-либо другой надежный алгоритм хеширования, например: hash(M)

Шаг 2) Перед началом игры сервер отправляет этот хеш (M) клиенту, который клиент сохраняет. Клиент не может узнать M из того, что я могу собрать.

Шаг 3) Игра начинается, карты раздаются в перетасованном порядке, игрок принимает решения, и игра, наконец, завершается.

Шаг 4) Теперь клиент хочет знать, что игра была честной, т.е. сервер не обманывал, меняя карты во время раздачи. Теперь сервер отправляет сообщение «M» клиенту в виде открытого текста, чтобы показать это.

Шаг 5) Клиент запускает hash(M) и видит, что он совпадает с его hash(M), полученным на шаге 1.

Является ли это честным способом доказать, что игра была честной, без возможности мошенничества со стороны клиента или сервера, исключая возможность того, что само перемешивание не было случайным? Если бы сервер менял исходные карты во время раздачи, то клиент увидел бы это на шаге 5 (либо порядок явно отличался бы от клиента, либо хэш сообщения, отправленного на шаге 4). будет отличаться от отправленного на шаге 2). Кроме того, за раздачу отправляется только один хэш, поэтому сервер не может генерировать большое количество хэшей и отправлять их по отдельности, а затем выбирать лучший в ходе раздачи.

marstato avatar
флаг sa
Что вы будете делать, если клиент обнаружит, что исходный хеш и хэш клиент-компьютер не равны?
флаг in
@marstato: Тогда вы знаете, что сервер вас обманул, и (надеюсь) вы можете подать возвратный платеж или что-то в этом роде. Но если вы использовали биткойны для оплаты, вам может не повезти.
marstato avatar
флаг sa
@ Кевин, ты имеешь в виду вернуть деньги парням, которые управляют мошенническим сервером?
user4779 avatar
флаг cn
@marstato Я бы просто перестал играть в эту игру. У сервера плохая репутация, и ему трудно привлекать новых клиентов.
флаг in
@marstato: Нет, с вашей кредитной картой, как и с любой другой мошеннической транзакцией. Я никогда не слышал о регистрации возвратного платежа с продавцом. Насколько я знаю, это просто не вещь.
Hagen von Eitzen avatar
флаг rw
Если размер хеша слишком мал, сервер может начать с двух перетасовок, отличающихся только двумя последними картами, и искать коллизию между этими хэшами при изменении случайных дополнительных битов (парадокс дня рождения).С двумя такими подготовленными колодами сервер может сжульничать со ставкой «все или ничего» на порядок последних двух карт… Поэтому клиент должен внести какой-то случайный вклад, чтобы колода по крайней мере гарантированно не была старательно готовый
user4779 avatar
флаг cn
@Хаген фон Эйцен А? Я думал, что у ша-256 не было известных столкновений. Кроме того, то, что вы говорите, нарушит эффект лавины.
Toby Speight avatar
флаг in
Сколько карт в колоде? Всего одна колода из 52 карт или существенно больше?
Рейтинг:22
флаг es

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

Вы можете сжать это еще больше, объявив 128-битное «начальное число» вместо перечисления всех отдельных позиций карты, а затем используя детерминированное перемешивание на основе этого семени перетасовать карты.

Если вы сделаете это, используя метод перетасовки, указанный выше, вам не нужно будет использовать ослепляющий фактор. Это связано с тем, что по определению CSPRNG может выдержать «тест следующего бита». Знание некоторых выходных данных CSPRNG не облегчит перебор начального числа или не даст никакого преимущества в угадывании следующих карт в колоде.

Следовательно, $ обязательство = хэш (\ texttt {128-битное начальное число}) $.

Обратите внимание, что действительно случайное перемешивание будет иметь $log_2(52!)\примерно225$ битов энтропии, которая больше, чем энтропия семени. Однако было бы невозможно даже определить единственный результат перетасовки, который был бы недостижим (из прибл. $2^{225}$ возможные перетасовки), и поэтому было бы не лучше, если бы начальное число было больше 128 бит.

Jacob Raihle avatar
флаг us
Разве детерминированное перемешивание, основанное на 128-битном начальном числе, не сделает невозможным достижение подавляющего большинства возможных (~ 225-битных) перемешиваний? Большинство возможных перетасовок в любом случае не сработают, учитывая их количество, но это похоже на то, что может раздражать кого-то, кто беспокоится о честности перетасовки.
knaccc avatar
флаг es
@JacobRaihle С 128-битным начальным числом было бы невозможно даже определить единственный результат перетасовки, который был бы недоступен (из возможных перетасовок примерно $ 2 ^ {225} $). Следовательно, это будет беспокоить людей так же, как и то, что есть шанс, что кто-то сможет взломать то же самое 128-битное начальное число.
флаг ma
Я думаю, что ослепляющий фактор - хорошая идея. Если сырая колода была хэш-коммитирована, то если в какой-то момент игроку откроется большая часть карт, он сможет брутфорсить оставшиеся карты.
knaccc avatar
флаг es
@Наюки, это отличный момент. Я изменил ответ, чтобы указать, что семя необходимо для схемы, предложенной в вопросе. Однако в этом нет необходимости при использовании детерминированного начального числа перетасовки, поскольку это будет равносильно возможности определить некоторые знания начального числа CSPRNG на основе вывода CSPRNG.
Jack Aidley avatar
флаг cn
Предположение, что огромное, подавляющее большинство возможных перетасовок не имеет значения, звучит как ошибка, которая обойдется онлайн-казино в кучу денег. Даже самый маленький сигнал может изменить баланс вероятностей.
knaccc avatar
флаг es
@JackAidley, вы используете ту же логику, которая заставляет людей беспокоиться о том, что их случайно выбранный ключ биткойн-кошелька может быть взломан. Небольших сигналов не бывает по той же математической причине, по которой знание хэш-фиксации не является слабым сигналом о начальном значении. Технически верно, что вы можете преуспеть в грубой силе, но вы должны поверить, что это астрономически маловероятно.
Jack Aidley avatar
флаг cn
@knacc Вам не нужно ничего форсировать, вам просто нужно, чтобы вероятность того, что карта X последует за картой Y, была не совсем 1/52. В то время как 128-битная версия значительно усложнит обнаружение, с деньгами на кону любой дефект будет использован. Это действительно произошло с онлайн-казино, которые в прошлом не использовали надлежащие алгоритмы перетасовки, хотя, по общему признанию, не на уровне 128 бит.
knaccc avatar
флаг es
@JackAidley со знанием хэш-обязательства, также технически верно, что после раздачи нескольких карт (для учета проблем хеш-коллизии) вы можете со 100% уверенностью сказать, какими будут все оставшиеся карты в тасовке.Однако, как только вы начинаете на самом деле измерять астрономическую природу задействованного грубого форсирования, картина выглядит совершенно по-другому.
Рейтинг:21
флаг ar

Расширить ответ knaccc, можно даже использовать схемы фиксации, чтобы доказать (до определенного момента), что сервер не обманывал во время перетасовки, например. как это:

  1. Сервер выбирает случайное 128-битное число $х$ и 128-битный коэффициент ослепления $r_x$, и отправляет обязательство $c_x = H(x \,||\, r_x)$ клиенту.
  2. Клиент выбирает случайное 128-битное число $у$ и отправляет на сервер. (Здесь никаких обязательств не требуется.)
  3. Хэши сервера $х$ и $у$ вместе, чтобы получить 128-битное начальное число $s = H(x \,||\, y)$.
  4. Сервер использует $s$ в качестве начального числа для детерминированного ГПСЧ и использует вывод ГПСЧ для детерминированного перемешивания колоды.
  5. Игра ведется перетасованной колодой.
  6. В конце игры сервер показывает $х$ и $r_x$, позволяя клиенту убедиться, что колода была перетасована правильно (и не была изменена после перетасовки).

Обратите внимание, что сервер может по-прежнему мошенничают, просматривая перетасованную колоду после шага 4 и прерывая игру (например, делая вид, что соединение было разорвано), если колода ему не нравится. Таким образом, клиент должен с подозрением относиться к серверам, которые часто обрывают соединения между шагами 2 и 5 или даже во время игры на шаге 5. В идеале клиент должен иметь способ попросить сервер возобновить прерванную игру в любой момент. и клиент должен быть очень подозрительно относятся к серверам, которые отказываются это делать.

(Надежная реализация такого механизма возобновления работы таким образом, чтобы он работал, даже если сервер выходит из строя и забывает состояние игры, кажется выполнимым, но, вероятно, выходит за рамки этого ответа. Задайте новый вопрос, если вам интересно.)

Также обратите внимание, что ослепляющее значение $r_x$ на самом деле не нужно здесь, так как $х$ сам по себе уже обладает достаточной энтропией, чтобы сделать грубое форсирование обязательства невозможным. На самом деле, возможно, было бы немного безопаснее опустить $r_x$ и просто сделай $х$ сам 256 вместо 128 бит.

Битовая длина $у$ и $s$ также можно увеличить при желании; 128 бит — это безопасный и практичный минимум. Нет смысла делать $s$ длиннее, чем общая длина $х$ и $у$ вместе, однако.

Toby Speight avatar
флаг in
Это хорошо — это помогает решить проблему в вопросе (аккуратно скрытом за счет доверенного алгоритма хеширования) о возможности того, что сервер может генерировать коллизии хэшей, если он может совершенно свободно выбирать собственное начальное число.

Ответить или комментировать

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