В GoVPN реализации именно так и делается тоже: создаётся участок забитый нулями, на него Salsa20 выхлоп натравливается, где из начала берутся данные для Poly1305, а нужная часть XOR-ится с plaintext-ом. Ну и дешифрование аналогично. Появляются нули, но так действительно проще. В целом начинаю понимать что действительно проще будет делать если итерироваться поблочно по выходам Salsa/ChaCha. Конкретно в Go библиотеке работа с блоками скрыта и там задаётся конкретная длина сколько надо сгенерировать байт.
PS: всё же не 32 байта, а 64 (полный блок) и на вход Poly1305 32 байт, вместо 16 подаётся в качестве ключа.
Всё же не очень понимаю где потеря производительности. То что выход Salsa/ChaCha имеет размер в 512 бит — действительно. Но это же не блочный шифр в котором нужно где-то выравнивать или дополнять. Все эти биты нужно XOR-ить с данными и раз уж мы получили какой-то выход, то можно было бы использовать сразу же. Если надо зашифровать 100 бит данных, то одна итерация Salsa/ChaCha даёт 512 бит из которых 256 бы пошли на Poly1305, а остальные 100 из оставшихся 256 на XOR с открытым текстом.
Да, с публичными ключами вы всё же правы. То что мы на вход для секретного подаём 256 бит энтропии не должно означать что эти же 256 бит останутся и в публичном ключе. 25519 как-раз гарантии даёт относительно 128-бит уровня brute force как минимум.
Не сложно запилить прямо в ядре? Вы учитываете и то что нужно вместо одной реализации писать две различные например чтобы поддерживать GNU/Linux и FreeBSD одновременно? Что проще поддерживать и администрировать: userpace демон требующий только TAP устройство или ядерные модули? О производительности надо париться когда она даёт о себе знать. Гигабиты гонять — проблема. Не у всех такие потребности. С таким же успехом можно было бы говорить и о том что на ассемблере гораздо производительнее софт без overhead-ов сторонних, но люди почему-то придумывают дополнительные абстракции, языки высокоуровневые. Стоимость разработки и поддержки ПО гораздо выше чем стоимость железа, как правило.
1, 2. Возможно вы и правы. Но ведь хуже же не будет. Это тот же самый «на всякий пожарный» что и игнорирование 256 бит после первых 256 бит из Salsa20 которое делают в SSH и TLS реализациях. Насколько понимаю никто не доказал что они реально могут повлиять на безопасность алгоритма, но на всякий пожарный откидывают, чтобы внутреннее состояние полностью сротировалось. Я не криптограф и не решился отбрасывать рекомендацию DH-EKE по такому генерированию ключей.
3. А мне вот кажется что коллизии там будут и гарантированно и достаточно много. Приватный ключ 25519 можно использовать и без установки трёх бит: то есть чистые 256 выхлопа PRNG, но ведь это тоже будет точкой на кривой. Так что любой рандом можно будет интерпретировать как точку на кривой.
DH-EKE точно так же является zero-knowledge протоколом (замечу что не я его изобрёл :-), он известен давно). PSK мне не надо передавать. Он используется в дебрях EKE нигде напрямую не передаваясь. В этом и суть DH-EKE. Пароль известный в полной мере и клиенту и серверу — не вариант. PAKE протоколы давно изобретены с приставкой augmented: когда серверй действительно не знает пароля клиента. SRP относится к таким.
В augmented PAKE протоколах пароль в чистом виде известен только клиенту. Сейчас EKE это не augmented схема: PSK известен в равной степени обоим. Поэтому и смотрим в сторону SRP.
PRNG нужен для создания сессионных ключей, которые действуют только на протяжении одной сессии. PSK используется только для аутентификации сторон на этапе рукопожатия.
1. Я брал классическое предположение что биты эллиптических кривых надо разделить на два. 256/2=128. 25519 это 256 бит, но несколько бит которого в приватном ключе явно устанавливаются в чётко заданные значения: раздел «Computing secret keys» на cr.yp.to/ecdh.html
2. Да, действительно выхлоп DH прогоняется через HSalsa: github.com/stargrave/govpn/blob/develop/handshake.go#L109
Я решил опустить эту мелочь из текста, хотя в коде делаю конечно же. Генерирование всё же результирующего секретного ключа из двух половинок передаваемых по каналу это сильно рекомендуемый совет уже из описания EKE протокола. Подчеркну: даже в EKE они говорят что не знают насколько это надо и полезно, лишь паранойя на всякий пожарный
3. Шум с точки зрения внешнего наблюдателя. Для нас это конечно же перемноженный приватный ключ (который является выхлопом PRNG (плюс заменённых нескольких бит)) относительно константной точки
1. Медленно. Не спорю. Вопрос насколько. В GoVPN я 100Mbps почти выжимаю на одном ядре процессора. На самом деле скорость куда сильнее теряется на одном только garbage collector Go. Задача была сделать reviewable, поддерживаемый простой код, портируемый. Завязываться на ядро: так это писать для каждой ОС совершенно независимую реализацию.
2. Если вам так критична скорость, то да. Производительность GoVPN удовлетворительна будет для большинства пользователей.
3. Salsa20 перевесила только одним: она есть по-умолчаню из коробки в golang.org/x/crypto. Но тут это не шибко принципиально. Про ChaCha20 я поэтому и упомянул. Заменить на ChaCha20 это поменять название библиотеки. Но порог безопасности Salsa20 и так настолько высок, а разница в производительности на фоне того же garbage collector так незначительна, что тут уж проще выбрать что есть «из коробки», так как портируемость и простота поддержки лучше
4. Вы не разобрались как это работает. Перехватив два шифротекста (сделанных одним ключём, одной PRNG последовательностью) и сделав XOR между ними мы получим XOR между двумя их открытыми текстами. Ни я, ни другие не говорят что вы сразу же получите на экране готовый к чтению открытый текст, но уже банальными методами простейшего криптоанализа, типа статистического, XOR открытых текстов тривиально достаётся особенно когда там человеческое письмо передаётся. Первое чему учит любая книга по прикладной криптографии это про одноразовые шифроблокноты, как идеальную систему шифрования, второе — как-раз что будет если послать два шифротекста одного ключа, третье — никогда не использовать выходы потоковых ключей дважды.
Под ARM 32bit он собирается. Сам ARM устройств не имею, но думаю что 10 мегабайт хватит, так как клиент и сервер бинарь скомпилированный и со сделанным strip занимает 2.7MiB.
Поддерживаю полностью! Мягко говоря, возмутил подобный перевод. В английском языке слово свободный и бесплатный это одно слово и именно поэтому Ричард Столлман постоянно добавляет «free as in freedom, not free as in beer». Для нашего языка это замечание не обязательно бы было. Автор, пожалуйста, исправьте перевод, так как Столлман никогда не говорил про бесплатные программы: свободные программы никто не мешает продавать и брать деньги и никто не вправе этого запрещать в мире СПО.
Да, привязка к скорости случайного доступа к памяти. scrypt делает тоже самое: память ему не нужна как таковая: её можно заменить вычислениями на CPU. Либо это будет очень медленно, либо гораздо быстрее при наличии памяти. Она сродни кэшированию промежуточных вычислений. После какого-то порога, связанного с парадоксами дней рождения, у нас будет очень высокая вероятность попадания в кэш хэш-значений: имея этот кэш у нас на каждой итерации большая вероятность найти коллизию и быстро решить задачу (найти необходимое количество коллизий).
Скорость между памятью у нас различалась максимум на порядок.
В данной статье речь про скорость оперативной памяти, а не размерах. Памяти может быть и много: вопрос стимости. Обычный ПК или обычный сервер *уже* (из коробки) имеют разницу в 2-3 порядка относительно обычного смартфона по процессору, а по памяти всего порядок.
Не очень понял про тысячу задач. Если мы возьмём алгоритм по перебору шифра: разница в производительности между процессорами обычного ПК/сервера и смартфона будем считать различается на три порядка. Допустимое максимальное время ожидания решение задачи это 10 секунд (из-за раздражения пользователя). То есть то что на сотовом выполняется 10 сек, на ПК будет выполнятся за 10 мс. Если использовать задачу с памятью, то разница будет в десять раз или меньше. Первую задачу можно распаралллеливать, а вторую можно считать что нет, предполагая что всё упрётся в шину памяти.
В первом случае само по себе PoW бесполезен так как для сервера это несущественные накладные расходы (10мс на одном ядре), а для смартфона слишком большой предел ожидания.
Имея много памяти мы упрёмся в шину и в процессор. Процессор легко докупить. Шину если только распараллеливать на NUMA. Можно, но дорого. Никто не будет тратить столько средства на такое железо так как наши потери от лавины PoW задач не пойдут ни в какое сравнение.
Это да. Но у хэша O(1). Безусловно как компромисс между скоростью и экономией памяти можно рассматривать. Чувствую что при одних значениях если данные памяти будут хорошо кэшироваться, то log(N) в быстрой памяти может быть быстрее.
Плюс размер дерева-поиска запросто будет достаточно малым чтобы уместиться в кэш процессора первого или второго уровней, тогда как чистый массив в три мегабайта уже наврядли.
Безусловно можно. В примере из статьи это более миллиона итераций: то есть придётся сделать более миллиона итераций поиска по массиву, читая его элементы последовательно. Это на порядки медленнее чем использование set (в Python) или словарей/хэшей. Да и, если уж нашлось три мегабайта памяти, то наверняка найдётся и чуть-чуть побольше. То есть овчинка выделки не стоит.
Компилятор, например GCC, очень хорошо умеет оптимизировать код по производительности. Учитывая SIMD расширения, кэши: не шибко сильный в ассемблере генерируемом программист не знает что конкретно будет делать процессор. Почти наверняка подобные циклы будут применять и предикаты и переименование регистров (а их везде по-разному), что, в зависимости от длины строк сравниваемых, на время выполнения может повлиять ещё как.
С точки зрения математики, логики, пример ваших циклов само собой будет занимать константное время. На практике оптимизация GCC для intel процессоров не даст желаемого результата (а может и даст иногда). HMAC позволяет где бы то ни было рандомизировать время сравнения. Это частая практика в местах применения криптографии, где никто не хочет тратить приличное количество человекочасов на проверки действительно ли такая-то версия GCC делает нужный по поведению код для заданной модели процессора.
Это ваше подразумевание того что является анонимностью и что вы хотите получить от этого понятия. В самом начале статьи я указал что я в ней подразумеваю под анонимностью. Невозможность детерминированно связать покупки с пользователем. Слепые подписи решают эту проблему? Конкретно мою названную — да: получив чек я не могу сказать чей он был изначально. Не ставится условий что банк при этом располагает базами данных о статистике, о поведении людей, о поведении и особенностях формирования цен и прочего. Это уже другие условия и другие задачи. Bitcoin например предполагает под анонимностью что в системе не фигурируют ФИО и другие подобные данные — мол все коммуникации между безликими публичными ключами. Конкретно в их контексте они тоже достигают своей интерпретации анонимности.
Я понимаю что я, как и вы, достраиваю свои дополнительные условия в рамках которых Bitcoin не анонимен. Также как и вы вводите фактически статистические утечки информации и особенности их «поведения» у людей. Право каждого безусловно. Но стоит оценить риски в том и в другом случае, к чему я и хотел подтолкнуть людей.
Ввод/ввывод в другие системы это тоже выход за рамки контекста, поиск обходных путей проблемы. Если об этом заходят думы, то значит люди вынуждены, потому-что без этого система позволит деанонимизировать. Допустим другие системы это решение проблем — с таким же успехом «размазывание» статистической информации при покупках в schneiercash чтобы не получалось как-либо связанных сумм (это же похоже на проблему задачи о ранце (knapsack problem)) тоже можно сделать.
А где границы и рамки того что десятки тысячи кошельков с привязанными к ним транзакциями и сопутствующей статистической информацией будут достаточны чтобы считать это например сложностью в 2**64 например? Думаю что можно попытаться математически попытаться привести подобные практики создания транзакций между N-ым количеством кошельков к проблеме равносильной перебору такого-то количества данных, ну как это происходит к RSA (который сводится к проблеме факторизации) или ElGamal в криптографии. Если такие работы будут и я детерминированно буду знать что мне достаточно будет заиметь столько-то пар ключей и совершить столько то транзакций между ними для достижения нужного мне предела brute force, то тогда здорово. Останется только вопрос ресурсозатрат на это и будет ли оно практично. Но пока таких математических документов нет. Понятие «замучаешься» должно отталкиваться например от того что это равносильно анализу требующему столько то ресурсов процессора и занимаемой памяти.
PS: всё же не 32 байта, а 64 (полный блок) и на вход Poly1305 32 байт, вместо 16 подаётся в качестве ключа.
Да, с публичными ключами вы всё же правы. То что мы на вход для секретного подаём 256 бит энтропии не должно означать что эти же 256 бит останутся и в публичном ключе. 25519 как-раз гарантии даёт относительно 128-бит уровня brute force как минимум.
3. А мне вот кажется что коллизии там будут и гарантированно и достаточно много. Приватный ключ 25519 можно использовать и без установки трёх бит: то есть чистые 256 выхлопа PRNG, но ведь это тоже будет точкой на кривой. Так что любой рандом можно будет интерпретировать как точку на кривой.
В augmented PAKE протоколах пароль в чистом виде известен только клиенту. Сейчас EKE это не augmented схема: PSK известен в равной степени обоим. Поэтому и смотрим в сторону SRP.
PRNG нужен для создания сессионных ключей, которые действуют только на протяжении одной сессии. PSK используется только для аутентификации сторон на этапе рукопожатия.
2. Да, действительно выхлоп DH прогоняется через HSalsa: github.com/stargrave/govpn/blob/develop/handshake.go#L109
Я решил опустить эту мелочь из текста, хотя в коде делаю конечно же. Генерирование всё же результирующего секретного ключа из двух половинок передаваемых по каналу это сильно рекомендуемый совет уже из описания EKE протокола. Подчеркну: даже в EKE они говорят что не знают насколько это надо и полезно, лишь паранойя на всякий пожарный
3. Шум с точки зрения внешнего наблюдателя. Для нас это конечно же перемноженный приватный ключ (который является выхлопом PRNG (плюс заменённых нескольких бит)) относительно константной точки
2. Если вам так критична скорость, то да. Производительность GoVPN удовлетворительна будет для большинства пользователей.
3. Salsa20 перевесила только одним: она есть по-умолчаню из коробки в golang.org/x/crypto. Но тут это не шибко принципиально. Про ChaCha20 я поэтому и упомянул. Заменить на ChaCha20 это поменять название библиотеки. Но порог безопасности Salsa20 и так настолько высок, а разница в производительности на фоне того же garbage collector так незначительна, что тут уж проще выбрать что есть «из коробки», так как портируемость и простота поддержки лучше
4. Вы не разобрались как это работает. Перехватив два шифротекста (сделанных одним ключём, одной PRNG последовательностью) и сделав XOR между ними мы получим XOR между двумя их открытыми текстами. Ни я, ни другие не говорят что вы сразу же получите на экране готовый к чтению открытый текст, но уже банальными методами простейшего криптоанализа, типа статистического, XOR открытых текстов тривиально достаётся особенно когда там человеческое письмо передаётся. Первое чему учит любая книга по прикладной криптографии это про одноразовые шифроблокноты, как идеальную систему шифрования, второе — как-раз что будет если послать два шифротекста одного ключа, третье — никогда не использовать выходы потоковых ключей дважды.
Скорость между памятью у нас различалась максимум на порядок.
Не очень понял про тысячу задач. Если мы возьмём алгоритм по перебору шифра: разница в производительности между процессорами обычного ПК/сервера и смартфона будем считать различается на три порядка. Допустимое максимальное время ожидания решение задачи это 10 секунд (из-за раздражения пользователя). То есть то что на сотовом выполняется 10 сек, на ПК будет выполнятся за 10 мс. Если использовать задачу с памятью, то разница будет в десять раз или меньше. Первую задачу можно распаралллеливать, а вторую можно считать что нет, предполагая что всё упрётся в шину памяти.
В первом случае само по себе PoW бесполезен так как для сервера это несущественные накладные расходы (10мс на одном ядре), а для смартфона слишком большой предел ожидания.
Имея много памяти мы упрёмся в шину и в процессор. Процессор легко докупить. Шину если только распараллеливать на NUMA. Можно, но дорого. Никто не будет тратить столько средства на такое железо так как наши потери от лавины PoW задач не пойдут ни в какое сравнение.
С точки зрения математики, логики, пример ваших циклов само собой будет занимать константное время. На практике оптимизация GCC для intel процессоров не даст желаемого результата (а может и даст иногда). HMAC позволяет где бы то ни было рандомизировать время сравнения. Это частая практика в местах применения криптографии, где никто не хочет тратить приличное количество человекочасов на проверки действительно ли такая-то версия GCC делает нужный по поведению код для заданной модели процессора.
Я понимаю что я, как и вы, достраиваю свои дополнительные условия в рамках которых Bitcoin не анонимен. Также как и вы вводите фактически статистические утечки информации и особенности их «поведения» у людей. Право каждого безусловно. Но стоит оценить риски в том и в другом случае, к чему я и хотел подтолкнуть людей.
Ввод/ввывод в другие системы это тоже выход за рамки контекста, поиск обходных путей проблемы. Если об этом заходят думы, то значит люди вынуждены, потому-что без этого система позволит деанонимизировать. Допустим другие системы это решение проблем — с таким же успехом «размазывание» статистической информации при покупках в schneiercash чтобы не получалось как-либо связанных сумм (это же похоже на проблему задачи о ранце (knapsack problem)) тоже можно сделать.
А где границы и рамки того что десятки тысячи кошельков с привязанными к ним транзакциями и сопутствующей статистической информацией будут достаточны чтобы считать это например сложностью в 2**64 например? Думаю что можно попытаться математически попытаться привести подобные практики создания транзакций между N-ым количеством кошельков к проблеме равносильной перебору такого-то количества данных, ну как это происходит к RSA (который сводится к проблеме факторизации) или ElGamal в криптографии. Если такие работы будут и я детерминированно буду знать что мне достаточно будет заиметь столько-то пар ключей и совершить столько то транзакций между ними для достижения нужного мне предела brute force, то тогда здорово. Останется только вопрос ресурсозатрат на это и будет ли оно практично. Но пока таких математических документов нет. Понятие «замучаешься» должно отталкиваться например от того что это равносильно анализу требующему столько то ресурсов процессора и занимаемой памяти.