Comments 18
Интересно, надо изучать. А можно ли ваш подход использовать для очень больших разделений? Например, где миллион(ы) долей и сотни тысяч минимальный порог?
В вычислительной технике работа с рациональными числами невозможна, потому что они представлены с определенной точностью и однозначно восстановить секрет не представляется возможным.
Лукавите где-то. Любое рациональное число можно представить в виде дроби a/b, где a — целое, b — натуральное. Взяв длинную арифметику для этих чисел получим произвольную точность.
В компьютерах числа представляются в виде мантиссы и порядка. Рациональное число 1/3 «точно» никак не сохранить.
Я абсолютно «точно» могу сохранить число 1/3 в виде пары чисел 1 и 3. И спокойно дописать всю нужную арифметику для таких пар.
Я понял о чем Вы говорите, теоретически такое возможно хранить рациональное число в виде вектора (a,b), где а, b — целые.
И можно определить операции сложения, умножения и деления этих векторов.
Но тогда встает вопрос о бесконечной размерности чисел a,b (понимаю, что это уже другой вопрос)
И можно определить операции сложения, умножения и деления этих векторов.
Но тогда встает вопрос о бесконечной размерности чисел a,b (понимаю, что это уже другой вопрос)
Совершенно тривиально решаемый вопрос, типы BigInt этот вопрос решают в очень больших пределах. Даже оставляя в стороне всякие numpy и BigInt в Rust'е, даже нативная реализация в питоне с этим умеет отлично работать.
a=1000
for b in range(0..1000):
a = a*1000
len(str(a))3004>>> str(a-1)[0:42]
'999999999999999999999999999999999999999999
>>> str(a//3)[0:42]
'333333333333333333333333333333333333333333'
>>> str(a+33)[-42:]
'000000000000000000000000000000000000000033'полностью a не привожу, чтобы не смущать читателя.
исправил данный абзац, спасибо
Один из методов — это хранить числа в формате с плавающей запятой.
Второй — в формате целых.
Третий — в формате с фиксированной запятой.
Четвёртый — в формате рационального числа. Вот, например: https://docs.rs/num-rational/0.4.0/num_rational/ и https://docs.rs/num-rational/0.4.0/num_rational/type.BigRational.html
в первом методе — невозможно сохранить число 1/3
во втором методе — тоже
в третьем — тоже
в четвертом — тоже
во втором методе — тоже
в третьем — тоже
в четвертом — тоже
Мне кажется, вы плохо понимаете, что такое рациональные числа. Рациональные числа — это числа, которые можно записать как два инта, поделенные друг на друга. Для них есть хорошо вычислимая арифметика и полная консистентность. Единственной проблемой их является возможность "убегания" размеров интов, но для этого BigInt тип и нужен — там используется арифметрика на произвольно больших int'ах (вплоть до запасов памяти компьютера).
Четвёртый метод позволяет хранить 1/3 в форме примерно 2-3 байт. В первом байте тип, во втором байте число 1, в третьем байте число 3.
Вот, например, реализация умножения: https://docs.rs/num-rational/0.4.0/src/num_rational/lib.rs.html#683
Я попытался вникнуть в Ваш пост, но в самом начале обозначены какие-то необоснованные на мой взгляд цели и проблемы.
Почему это нужно считать обязательным требованием?
Надуманная проблема. Самая известная реализация схемы Шамира поддерживает секреты до 1024 бит: linux.die.net/man/1/ssss-split
Секреты большего размера попросту нецелесообразны, ведь можно зашифровать большой массив данных симметричным шифром, ключ к которому разделён, и это будет быстро — порядка сотен мегабайт в секунду.
Не совсем понятно, можно ли раскрутить недостающий секрет по частям более эффективно, особенно учитывая что имеется «оракул» в виде контрольной суммы. Я с ходу не вижу простого варианта, но неясно, существует ли он.
По преимуществам Вашей схемы:
Можно просто в схеме Шамира использовать число долей 256, выдав на руки произвольные номера и приклеив x первым байтом. Насчёт правдопободного отрицания — это ещё надо доказать, что имеющиеся доли статистически не связаны и похожи на равномерно-распределённую случайную величину.
В чём преимущества-то тогда?
А вот о недостатках вы не упомянули: почему-то ограничения реализации в 5 шар вы не записали в недостатки своей схемы. Как и отсутствие доказательства корректности и безопасности, отсутствие какого-либо аудита или peer review.
Если вопрос стоит в защите каких-то серьёзных данных, я бы поостерёгся использовать доморощенную крипту, честно говоря.
длина доли и секрета была одной и той же
Почему это нужно считать обязательным требованием?
Для больших длин секретов приходилось бы искать большое простое число, заведомо большее длины секрета, чтобы секрет находился в этом поле.
Для секрета длиной 8 байт простое число должно быть не меньше 1,8e19.
Нахождения простого числа, большего заданного
задача нетривиальная. Да и работа с большими числами на практике сложная.
Надуманная проблема. Самая известная реализация схемы Шамира поддерживает секреты до 1024 бит: linux.die.net/man/1/ssss-split
Секреты большего размера попросту нецелесообразны, ведь можно зашифровать большой массив данных симметричным шифром, ключ к которому разделён, и это будет быстро — порядка сотен мегабайт в секунду.
Chipndale разделяет секрет по байтам, то есть секрет должен иметь длину, кратную байту. Так же секрет не может иметь длину меньше 8 байт, так как меньшее число байт является ненадежным секретом само по себе.
Не совсем понятно, можно ли раскрутить недостающий секрет по частям более эффективно, особенно учитывая что имеется «оракул» в виде контрольной суммы. Я с ходу не вижу простого варианта, но неясно, существует ли он.
По преимуществам Вашей схемы:
секрет и доли неразличимы по структуре, что позволяет правдоподобно отрицать существование реального секрета
Можно просто в схеме Шамира использовать число долей 256, выдав на руки произвольные номера и приклеив x первым байтом. Насчёт правдопободного отрицания — это ещё надо доказать, что имеющиеся доли статистически не связаны и похожи на равномерно-распределённую случайную величину.
Длины секретов могут быть любымиСм. начало комментария
Можно сколько угодно раз разделить секрет заново, так как «много» многочленов степениУ ssss так же
По долям, меньших, невозможно восстановить секрет, либо часть егоУ ssss так же
В чём преимущества-то тогда?
А вот о недостатках вы не упомянули: почему-то ограничения реализации в 5 шар вы не записали в недостатки своей схемы. Как и отсутствие доказательства корректности и безопасности, отсутствие какого-либо аудита или peer review.
Если вопрос стоит в защите каких-то серьёзных данных, я бы поостерёгся использовать доморощенную крипту, честно говоря.
Благодарю, что попытались вникнуть в мой пост!
Все зависит от конкретной задачи.
В некоторых схемах к ключу добавляется проверочный код. То есть ключ определенной длины и к нему добавляется проверочный код, определенной длины. Поэтому, чтобы доли имели такую же структуру, нужно, чтобы длины были одинаковы. Пример — тот же самый bip39.
К сожалению, данный алгоритм мне незнаком, как прочитаю код, дам оценку. Я думал над тем, чтобы работать с большим полем Галуа, но приятнее было работать с байтами и с числами до 256.
Согласен, я лишь описал то, что в моем алгоритме длина может быть сколь угодно большой.
Я могу нестрого доказать, что нет статистической зависимости:
1. Чтобы доля и ключ не имели зависимости, нужно чтобы вектор `cs` был произвольным(классическая схема Шамира).
2. Вектор `cs` = `csKey` + `csHash`
3. `csKey` генерируется произвольно
4. `csHash` генерируется на основании произвольного ключа `csKey` и секрета. Для «хороших» хешей нет статистической зависимости между прообразом и образом при разных ключах. Поэтом `csHash` можно считать произвольным.
Спасибо, добавил!
Буду признателен, если кто-то проведет ревью и укажет на уязвимости.
Почем нужно считать обязательным требованием, что длина доли и секрета была одной и той же?
Все зависит от конкретной задачи.
В некоторых схемах к ключу добавляется проверочный код. То есть ключ определенной длины и к нему добавляется проверочный код, определенной длины. Поэтому, чтобы доли имели такую же структуру, нужно, чтобы длины были одинаковы. Пример — тот же самый 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.
Буду признателен, если кто-то проведет ревью и укажет на уязвимости.
YourChief
Просмотел код linux.die.net/man/1/ssss-split, алгоритмы похожи за исключением того, что
— я работаю в GF(256), а не в GF(2**degree).
— координата X хранится отдельно, от чего я хотел уйти как раз
— в алгоритме ssss-split есть опция предварительной «диффузии» секрета, чего нет у меня. Вот для чего она используется? Единственное что в голову приходит это то, что ты зная часть секрета и имея K-1 долей будешь так же знать части других долей.
Просмотел код linux.die.net/man/1/ssss-split, алгоритмы похожи за исключением того, что
— я работаю в GF(256), а не в GF(2**degree).
— координата X хранится отдельно, от чего я хотел уйти как раз
— в алгоритме ssss-split есть опция предварительной «диффузии» секрета, чего нет у меня. Вот для чего она используется? Единственное что в голову приходит это то, что ты зная часть секрета и имея K-1 долей будешь так же знать части других долей.
Про диффузию есть вот такое мнение для чего она: crypto.stackexchange.com/a/15687
Пишут, что для того, чтобы нельзя было предсказуемо манипулировать значением всего секрета, манипулируя значением своих долей.
По поводу доказательства неотличимости от случайных данных. Тот факт, что на входе случайные данные и при преобразованиях используется какой-то другой случайный ввод не гарантирует что результат всех преобразований будет неотличим от случайной величины. Пример из практики: для схемы Curve25519 открытым ключом является одна координата точки, которая получается скалярным умножением элемента точки-генератора на совершенно случайную величину. Однако, наблюдение массы таких открытых ключей покажет, что эти числа являются квадратичным вычетом по модулю 2^255-19 в 100% случаев, в то время как действительно случайное число по такому простому модулю будет квадратичным вычетом только в 50% случаев. Даже в отношении оригинальной схемы Шамира я нигде не видел упоминаний гарантий насчёт real-or-random security. Не могу судить ни в пользу этого, ни против.
Вроде как это нормально — Шамир допускал разбиение на блоки поменьше, вплоть до 216. Правда, маленький размер модуля ограничивает число шар и с раздачей нескольких шар в одни руки (для разных весов) уже не поиграться. Однако, в Вашей схеме оно и не получится по причине ниже.
Пишут, что для того, чтобы нельзя было предсказуемо манипулировать значением всего секрета, манипулируя значением своих долей.
По поводу доказательства неотличимости от случайных данных. Тот факт, что на входе случайные данные и при преобразованиях используется какой-то другой случайный ввод не гарантирует что результат всех преобразований будет неотличим от случайной величины. Пример из практики: для схемы Curve25519 открытым ключом является одна координата точки, которая получается скалярным умножением элемента точки-генератора на совершенно случайную величину. Однако, наблюдение массы таких открытых ключей покажет, что эти числа являются квадратичным вычетом по модулю 2^255-19 в 100% случаев, в то время как действительно случайное число по такому простому модулю будет квадратичным вычетом только в 50% случаев. Даже в отношении оригинальной схемы Шамира я нигде не видел упоминаний гарантий насчёт real-or-random security. Не могу судить ни в пользу этого, ни против.
— я работаю в GF(256), а не в GF(2**degree).
Вроде как это нормально — Шамир допускал разбиение на блоки поменьше, вплоть до 216. Правда, маленький размер модуля ограничивает число шар и с раздачей нескольких шар в одни руки (для разных весов) уже не поиграться. Однако, в Вашей схеме оно и не получится по причине ниже.
— координата X хранится отдельно, от чего я хотел уйти как разКомбинаторный брутфорс для восстановления порядка не выглядит как что-то масштабируемое. Уже начиная с десятков шар пойдут какие-то дикие значения факториалов. Не говоря уже о том, что при большом числе вариантов начинает стрелять вероятность коллизии 32битного хэша:
Пишут, что для того, чтобы нельзя было предсказуемо манипулировать значением всего секрета, манипулируя значением своих долей.
Понятно. В chipndale модификация доли приводит к неверной хеш-сумме и к невозможности восстановления, а значит с этой точки зрения диффузия не нужна.
Комбинаторный брутфорс для восстановления порядка не выглядит как что-то масштабируемое. Уже начиная с десятков шар пойдут какие-то дикие значения факториалов
Да, мой алгоритм рассчитан на 5 долей максимум с возможностью расширения до 7 с обратной совместимостью. Это цена того, что координата X не хранится отдельно.
при большом числе вариантов начинает стрелять вероятность коллизии 32битного хэша
Да, чтобы построить коллизию нужно перебрать ~sqrt(hashSize) значений, то есть sqrt(2**32) = 2**16 = 65536. Это называется парадоксом дней рождения.
Для maxShares=5 число переборов — 120, а значит вероятность коллизии при разделении секрета одна пятисоттысячная (согласно Вашей таблице).
Тут условия несколько мягче, так как не любая коллизия из 120 значений фатальна, а только коллизия с настоящей суммой. Тем не менее:
Примерно 1 на 36 миллионов для 5 долей и 1 на 850 тысяч при 7 долях. Это уже не production ready. Но не верьте мне на слово — напишите тест, который прогоняет хотя бы полмиллиарда итераций и посмотрите, всегда ли ваше решение хотя бы отрабатывает корректно.
В отношении plausible denial, кстати, т. н. coercer легко докажет, что группа поделила между собой секрет, если прихватит весь кворум с долями. И контрольная сумма ему будет весьма кстати. Я б сказал даже, что лучшего доказательства не придумать. Оригинальная схема в этом отношении не позволяет ни о чём судить, т. к. из шар можно получить много секретов, добавляя разные неверные шары.
Я не вижу здесь реальных преимуществ по сравнению с оригинальной схемой.
Вместо этого я вижу проблемы:
In [18]: 1-float(fractions.Fraction(2**32-1,2**32)**(math.factorial(5)-1)) Out[18]: 2.770684626174358e-08 In [19]: 1-float(fractions.Fraction(2**32-1,2**32)**(math.factorial(7)-1)) Out[19]: 1.1732329252556184e-06
Примерно 1 на 36 миллионов для 5 долей и 1 на 850 тысяч при 7 долях. Это уже не production ready. Но не верьте мне на слово — напишите тест, который прогоняет хотя бы полмиллиарда итераций и посмотрите, всегда ли ваше решение хотя бы отрабатывает корректно.
В отношении plausible denial, кстати, т. н. coercer легко докажет, что группа поделила между собой секрет, если прихватит весь кворум с долями. И контрольная сумма ему будет весьма кстати. Я б сказал даже, что лучшего доказательства не придумать. Оригинальная схема в этом отношении не позволяет ни о чём судить, т. к. из шар можно получить много секретов, добавляя разные неверные шары.
Я не вижу здесь реальных преимуществ по сравнению с оригинальной схемой.
- Если нужен контроль целостности — использовать SSSS для разделения ключа симметричного шифра с MAC.
- Если нужна произвольная длина секрета — то же самое.
- Если нужно отрицание причастности доли к групповому секрету — шифровать саму долю. В любом случае, не в голом виде же её держать на компьютере?
Вместо этого я вижу проблемы:
- Мало долей, поиграться с весами не получится.
- Корректность алгоритма не гарантирована во всех случаях.
- Контрольная сумма добавляет проблем, и в то же время как код контроля целостности служить не может — слишком малый размер подписи.
Тут условия несколько мягче, так как не любая коллизия из 120 значений фатальна, а только коллизия с настоящей суммой. Примерно 1 на 36 миллионов для 5 долей и 1 на 850 тысяч при 7 долях. Это уже не production ready.
Корректность алгоритма не гарантирована во всех случаях.
У меня есть проверка на то, что если контрольная сумма совпадет в разных позициях, то разделить не получится (нужно будет попробовать заново). Соответственно корректность гарантирована.
В отношении plausible denial, кстати, т. н. coercer легко докажет, что группа поделила между собой секрет, если прихватит весь кворум с долями. И контрольная сумма ему будет весьма кстати. Я б сказал даже, что лучшего доказательства не придумать.
Есть два отрицания
— отрицание, что передо мной доля: chipndale+, ssss- (отрицать, что 1-b3993… НЕ ДОЛЯ НОМЕР ОДИН не получится)
— принятие, что это доля. Собирание из этой доли и ложной доли X, секрета S' chipndale-, ssss+
Sign up to leave a comment.
Chipndale: неявное разделение секрета