Тут условия несколько мягче, так как не любая коллизия из 120 значений фатальна, а только коллизия с настоящей суммой. Примерно 1 на 36 миллионов для 5 долей и 1 на 850 тысяч при 7 долях. Это уже не production ready.
Корректность алгоритма не гарантирована во всех случаях.
У меня есть проверка на то, что если контрольная сумма совпадет в разных позициях, то разделить не получится (нужно будет попробовать заново). Соответственно корректность гарантирована.
В отношении plausible denial, кстати, т. н. coercer легко докажет, что группа поделила между собой секрет, если прихватит весь кворум с долями. И контрольная сумма ему будет весьма кстати. Я б сказал даже, что лучшего доказательства не придумать.
Есть два отрицания
— отрицание, что передо мной доля: chipndale+, ssss- (отрицать, что 1-b3993… НЕ ДОЛЯ НОМЕР ОДИН не получится)
— принятие, что это доля. Собирание из этой доли и ложной доли X, секрета S' chipndale-, ssss+
Пишут, что для того, чтобы нельзя было предсказуемо манипулировать значением всего секрета, манипулируя значением своих долей.
Понятно. В chipndale модификация доли приводит к неверной хеш-сумме и к невозможности восстановления, а значит с этой точки зрения диффузия не нужна.
Комбинаторный брутфорс для восстановления порядка не выглядит как что-то масштабируемое. Уже начиная с десятков шар пойдут какие-то дикие значения факториалов
Да, мой алгоритм рассчитан на 5 долей максимум с возможностью расширения до 7 с обратной совместимостью. Это цена того, что координата X не хранится отдельно.
при большом числе вариантов начинает стрелять вероятность коллизии 32битного хэша
Да, чтобы построить коллизию нужно перебрать ~sqrt(hashSize) значений, то есть sqrt(2**32) = 2**16 = 65536. Это называется парадоксом дней рождения.
Для maxShares=5 число переборов — 120, а значит вероятность коллизии при разделении секрета одна пятисоттысячная (согласно Вашей таблице).
YourChief
Просмотел код linux.die.net/man/1/ssss-split, алгоритмы похожи за исключением того, что
— я работаю в GF(256), а не в GF(2**degree).
— координата X хранится отдельно, от чего я хотел уйти как раз
— в алгоритме ssss-split есть опция предварительной «диффузии» секрета, чего нет у меня. Вот для чего она используется? Единственное что в голову приходит это то, что ты зная часть секрета и имея K-1 долей будешь так же знать части других долей.
Спасибо за статью!
В особенности технологии гомоморфного шифрование и доказательство с нулевым разглашением.
Но как быть с тем, что после того, как избиратель анонимно проголосовал, реал-тайм счетчик у одного кандидата увеличился?
Тем самым косвенно узнается за кого проголосовал избиратель.
Почем нужно считать обязательным требованием, что длина доли и секрета была одной и той же?
Все зависит от конкретной задачи.
В некоторых схемах к ключу добавляется проверочный код. То есть ключ определенной длины и к нему добавляется проверочный код, определенной длины. Поэтому, чтобы доли имели такую же структуру, нужно, чтобы длины были одинаковы. Пример — тот же самый bip39.
Надуманная проблема. Самая известная реализация схемы Шамира поддерживает секреты до 1024 бит: linux.die.net/man/1/ssss-split
К сожалению, данный алгоритм мне незнаком, как прочитаю код, дам оценку. Я думал над тем, чтобы работать с большим полем Галуа, но приятнее было работать с байтами и с числами до 256.
Секреты большего размера попросту нецелесообразны, ведь можно зашифровать большой массив данных симметричным шифром, ключ к которому разделён, и это будет быстро — порядка сотен мегабайт в секунду.
Согласен, я лишь описал то, что в моем алгоритме длина может быть сколь угодно большой.
Насчёт правдопободного отрицания — это ещё надо доказать, что имеющиеся доли статистически не связаны и похожи на равномерно-распределённую случайную величину.
Я могу нестрого доказать, что нет статистической зависимости:
1. Чтобы доля и ключ не имели зависимости, нужно чтобы вектор `cs` был произвольным(классическая схема Шамира).
2. Вектор `cs` = `csKey` + `csHash`
3. `csKey` генерируется произвольно
4. `csHash` генерируется на основании произвольного ключа `csKey` и секрета. Для «хороших» хешей нет статистической зависимости между прообразом и образом при разных ключах. Поэтом `csHash` можно считать произвольным.
А вот о недостатках вы не упомянули: почему-то ограничения реализации в 5 шар вы не записали в недостатки своей схемы.
Спасибо, добавил!
Как и отсутствие доказательства корректности и безопасности, отсутствие какого-либо аудита или peer review.
Буду признателен, если кто-то проведет ревью и укажет на уязвимости.
Я понял о чем Вы говорите, теоретически такое возможно хранить рациональное число в виде вектора (a,b), где а, b — целые.
И можно определить операции сложения, умножения и деления этих векторов.
Но тогда встает вопрос о бесконечной размерности чисел a,b (понимаю, что это уже другой вопрос)
Нет, так как я использую поле Галуа из 256 элементов, максимальное теоретическое число долей 256 — 2 = 254.
А практически для деления и восстановления секрета нужно maxShares! операций, что очень трудоемко, поэтому я ограничил maxShares 5.
Я делал оптимизацию в текущем стеке с минимальным воздействием на кодовую базу, а так же в приоритете была скорость реализации.
Далее оптимизировать уже не было смысла, так как есть другие узкие места.
вот тоже интересно, как будет такой кеш работать.
Наиболее классный вариант был бы, если бы он держал кеш до GOMEMLIMIT, а при переполнении удалял бы старые объекты.
Про тесты ни слова, потому что я взял одинаковый набор из головы для всех случаев.
Можно взять несколько наборов, но тогда непонятно какие лучше брать. В общем можно с наборами поиграться и взять средний в ответ.
У меня есть проверка на то, что если контрольная сумма совпадет в разных позициях, то разделить не получится (нужно будет попробовать заново). Соответственно корректность гарантирована.
Есть два отрицания
— отрицание, что передо мной доля: chipndale+, ssss- (отрицать, что 1-b3993… НЕ ДОЛЯ НОМЕР ОДИН не получится)
— принятие, что это доля. Собирание из этой доли и ложной доли X, секрета S' chipndale-, ssss+
Понятно. В chipndale модификация доли приводит к неверной хеш-сумме и к невозможности восстановления, а значит с этой точки зрения диффузия не нужна.
Да, мой алгоритм рассчитан на 5 долей максимум с возможностью расширения до 7 с обратной совместимостью. Это цена того, что координата X не хранится отдельно.
Да, чтобы построить коллизию нужно перебрать ~sqrt(hashSize) значений, то есть sqrt(2**32) = 2**16 = 65536. Это называется парадоксом дней рождения.
Для maxShares=5 число переборов — 120, а значит вероятность коллизии при разделении секрета одна пятисоттысячная (согласно Вашей таблице).
Просмотел код linux.die.net/man/1/ssss-split, алгоритмы похожи за исключением того, что
— я работаю в GF(256), а не в GF(2**degree).
— координата X хранится отдельно, от чего я хотел уйти как раз
— в алгоритме ssss-split есть опция предварительной «диффузии» секрета, чего нет у меня. Вот для чего она используется? Единственное что в голову приходит это то, что ты зная часть секрета и имея K-1 долей будешь так же знать части других долей.
В особенности технологии гомоморфного шифрование и доказательство с нулевым разглашением.
Но как быть с тем, что после того, как избиратель анонимно проголосовал, реал-тайм счетчик у одного кандидата увеличился?
Тем самым косвенно узнается за кого проголосовал избиратель.
Все зависит от конкретной задачи.
В некоторых схемах к ключу добавляется проверочный код. То есть ключ определенной длины и к нему добавляется проверочный код, определенной длины. Поэтому, чтобы доли имели такую же структуру, нужно, чтобы длины были одинаковы. Пример — тот же самый bip39.
К сожалению, данный алгоритм мне незнаком, как прочитаю код, дам оценку. Я думал над тем, чтобы работать с большим полем Галуа, но приятнее было работать с байтами и с числами до 256.
Согласен, я лишь описал то, что в моем алгоритме длина может быть сколь угодно большой.
Я могу нестрого доказать, что нет статистической зависимости:
1. Чтобы доля и ключ не имели зависимости, нужно чтобы вектор `cs` был произвольным(классическая схема Шамира).
2. Вектор `cs` = `csKey` + `csHash`
3. `csKey` генерируется произвольно
4. `csHash` генерируется на основании произвольного ключа `csKey` и секрета. Для «хороших» хешей нет статистической зависимости между прообразом и образом при разных ключах. Поэтом `csHash` можно считать произвольным.
Спасибо, добавил!
Буду признателен, если кто-то проведет ревью и укажет на уязвимости.
И можно определить операции сложения, умножения и деления этих векторов.
Но тогда встает вопрос о бесконечной размерности чисел a,b (понимаю, что это уже другой вопрос)
во втором методе — тоже
в третьем — тоже
в четвертом — тоже
А практически для деления и восстановления секрета нужно maxShares! операций, что очень трудоемко, поэтому я ограничил maxShares 5.
Далее оптимизировать уже не было смысла, так как есть другие узкие места.