Comments 45
— Хватит использовать "сортировку пузырьком"!
— А что, её ещё кто-то использует?
Там безумно много всяких вариантов реализации можно показать на конкретном простом примере.
Я закончил универ лет двадцать назад. Мы тоже изучали "сортировку пузырьком". В IT-индустрии каждый год какие-то изменения, а в обучении студентов ничего не поменялось? Жёстко им будет впрыгивать со студентческой скамьи в профессию.
Мои инсайдеры говорят, что разработчики математики не собираются выпускать третью часть, поэтому эта часть программы обучения будет актуальна всегда)
Другое дело, что просто свинство — учить современных студентов на мертвом (с точки зрения бизнеса) паскале, попутно используя windows xp с ms office 2003. И как раз тут произошел значительный прогресс за последние 20 лет.
Если еще чуть больше углубляться в возможные подлянки вузовских программ, то тут будет использование закрытого по вместо открытого при прочих равных — но это очень индивидуальный вопрос, зависящий от специализации и особенностей конкретного курса
Я думаю не стоит объяснять в каких случаях сортировка пузырьком быстрее квиксорта ;-)
Реально не понимаю тех, кто продолжает RSA использовать.
1) RSA есть по дефолту везде
2) не все настолько хорошо умеют в безопасность, чтобы знать, что что-то другое НАДО искать
3) не всем это на самом деле нужно
RSA похоронить не смогут, по крайней мере нужно не дать. Пусть всё работает на этих ваших ECC, но я должен иметь возможность закрыть нечто ценное тем, чему полностью доверяю.
По вашей логике все, что непонятно вам лично и не может быть непосредственно вами проверено (а это большинство систем в мире), вы считаете небезопасным?
Именно так. Когда мы говорим о безопасности Open Source, мы прежде всего говорим о том, что те кому важна безопасность в этом конкретном месте, прочитают и поймут код, соберут из него ПО и будут использовать. Остальное фикция и очковтирательство. Я не говорю, что лично проверяю всё подряд, но в критических местах НУЖНО понимать, что происходит на большинстве уровней. Да, прозрачность ПО не даёт почти ничего в сфере гражданских систем, поскольку большинство аппаратных платформ для этих систем не предоставляют железа без толстого слоя абстракции, и x86/amd64 тому превосходный пример, однако подкласс понятных (причём кристально понятных) систем и аппаратных платформ должен быть, и на таких и только на таких платформах и ПО, которые абсолютно предсказуемы на всех уровнях абстракции вплоть до состояния всех регистров на всех режимах своей работы, и можно строить системы с высоким уровнем безопасности. И RSA со своим уровнем предсказуемости обязан быть в этом стеке технологий…
Тем не менее, злоумышленник может восстановить закрытый ключ, когда d меньше корня 4-й степени из N.
Более того, ЕМНИП примерно в 25-30% случаев цепной дробью можно получить d даже если оно не подверженно оригинальной границе Винера, несколько лет назад занимались этой темой и доказали экспериментально.
Смысл в том, что P и Q разных очень много, да. Но все пользуются одинаковыми алгоритмами и библиотеками чтобы их сгенерировать (и плохими генераторами случайных чисел). Иногда выходит что одно из двух чисел у одного ключа совпадают с одним из чисел другого. В результате можно через GCD найти оба ключа. Примерно это в статье и было проделано. Да, 1% — это не много, но по теории веротяности выходит многовато, в смысле должно быть меньше или не быть совсем (вариантов P и Q очень много). В статье говорится об >1% SSH ключей, это более 100 тыс. А вот 100 тыс ключей уже не выглядит маленьким числом.
we would see a long-tailed distribution in their frequencies
Что это за «long-tailed» распределения, я не понял, но очевидно одно — в ряде библиотек используется алгоритм, использующий лишь узкие области в доступном пространстве возможностей. Но что из этого следует? Из-за того, что кто-то по недоразумению вместо по возможности равномерного распределения использовал очевидно плохой вариант, под сомнение ставится всё шифрование на основе RSA. Упрощённо — кто-то где-то попал под поезд, так теперь давайте же запретим все поезда! А вот самолёты не будем, ведь это такая прибыльная область!
Очень много областей, где Си давно пора перестать использовать именно поэтому, но его продолжают там использовать, а когда в очередной раз приходит атакующий и все разламывает в клочья после получаса реверса — винят кого угодно, только не инструмент кривой.
Дали коновалам в руки скальпель, а теперь удивляются, что вся комната в крови…
Но чтобы на Си писать нужно быть очень осторожным и понимать как ОС и компьютер работает с памятью, как минимум. А вот с этим уже проблемы часто и даже толковые программисты часто лепят уязвимости.
Тот же Rust пытается закрыть большую часть подобных ошибок уже на compile time. Это к разговору об инструментах.
Но, на мой взгляд, это шаг в правильную сторону. Я сам больше Go предпочитаю и считаю его неплохим гибридом языков с GC и компилируемых в нативный код. Да, там можно прострелить себе ногу несколько легче чем в Расте, но зато он легко читаемый :) Ну и нативное concurrency решает.
API, который стабилизируется, стабилизируется, да все за 9 лет никак не остановится.
А что мешает пользоваться тем, что стабильно?
И все. Хваленая безопасность закончилась.
Нет, не закончилась. Теперь совершенно точно известно, где ошибка работы с памятью невозможна, а где возможна.
многие библиотеки используют небольшую публичную экспоненту и не делают простую проверку выравнивания при обработке подписей RSA.
Это же не недостаток RSA, а то как его используют. Это же относится и к другим алгоритмам.
Авторы преподнесли проблемы с имплементацией отдельных библиотек как проблемы с самим алгоритмом. Очень странно слышать такие вещи от людей которые пытаются учить людей криптографии.
RS/PS 256/512 отличные, широко используемые алгоритмы. Самая большая проблема это размер ключа. RSA жирный. Но за то в отличии от EDDSA/ECDSA он хорошо исследованный алгоритм. В отличии от NIST EC у RSA нет стрёмных никому не известных констант, а я говорю о NIST потому что в 90% случае вы будете использовать P256.
RSA жить и жить. Просто не надо пилить свою крипту. Пользуйтесь известными решениями.
Авторы преподнесли проблемы с имплементацией отдельных библиотек как проблемы с самим алгоритмом. Очень странно слышать такие вещи от людей которые пытаются учить людей криптографии.
В прикладной криптографии (которая внутри «разработки ПО», а не «математики») нет собой разницы между алгоритмом и реализацией алгоритма, потому что никаких других алгоритмов, кроме реализованных или самостоятельно разработчиком, или разработчиками библиотек, там нет. И атакуют там именно реализации.
Так вот с точки зрения прикладного криптографа RSA — действительно плохой алгоритм, потому что его практически невозможно «держать правильным образом», о чем авторы статьи и сообщают. И не только они, вот отличный пример того, как недостатки криптографических API приводят к тому, что 70% криптографического кода имеет серьезные проблемы, которые никто из разработчиков не в состоянии заметить.
![](https://habrastorage.org/webt/uu/68/gn/uu68gn0wcwbj8valzyl_uy7gceq.png)
Любые работающие технологии безопасности должны быть простыми как палка, и при этом стараться максимально усложнить свое неправильное использование (при помощи системы типов, статического анализа, или других инструментов), а нынешние (а тем более прошлые) реализации RSA в большинстве своем похожи скорее на OpenSSL, чем на упомянутый авторами libsodium.
А непонятный большинству алгоритм на эллиптических кривых, значит, можно «держать»? То есть автор статьи считает, что достаточно просто соблюдать рекомендации «умных людей» в отношении эллиптики, но вот в отношении RSA такие же рекомендации умных людей уже не считаются полезными. Получается, то в одном случае «держать» можно, а в другом аналогичном — нельзя. В чём же разница?
Наверное в том, что RSA привлекает больше внимания и у него находят больше уязвимостей. Но если вместо RSA будет что-то другое, то у него точно так же станут находить больше уязвимостей. И что тогда?
Про RSA vs. ECC главная идея проста: есть очень много способов накосячить с RSA и не накосячить достаточно сложно, а вот с ECC накосячить способов меньше и это сделать сложнее.
Ну так а на что «умные люди»? Они дают рекомендации — туда не ходи, снег башка попадёт. Кто сам неграмотный — просто выполняет рекомендации. Но точно то же самое и с ECC — умные люди дают рекомендации и эти рекомендации выполняют разработчики. Возможно, количество рекомендаций для ECC раза в два-три меньше, но зато имеем простоту самого алгоритма RSA, доступную большинству разработчиков. ECC же гораздо сложнее, и без понимания этой сложности разработчики превращаются в простейших копировщиков, исполняющих совершенно непонятные им «рекомендации», которые по сути есть инструкции по копированию. То есть разработчики в данном случае по сути не нужны, ведь можно вообще не копировать, а взять готовое решение. Но чем это лучше готового решения на RSA? Готовое на RSA есть в открытом доступе и проверено массой грамотных участников процесса, точно так же, как и готовое на ECС. Но если всё же есть необходимость сделать самостоятельную версию, то сама сложность ECC не даёт вариантов — либо её понимаешь, либо по сути просто копируешь чужое, что не лучше скачивания готового. Но если у разработчика уровень достаточен для понимания ECC, то уж косяки в процессе подготовки данных для RSA он уж точно сможет заметить/понять. Если хотя бы погуглит на тему уязвимостей алгоритма — уже много проблем обойдёт. Ну а глубина понимания поможет дополнительно не накосячить.
В целом — ECC сложнее, что означает невозможность обнаружить косяк для большинства разработчиков, есть возможность лишь для тупого копирования (без понимания). RSA проще и косяки широко известны, что даёт возможность менее грамотному в плане математики разработчику избежать большинства ошибок. Оставшиеся уязвимости в силу их нетривиальности скорее всего равнозначны по уровню опасности и для грамотных математиков и для обычных разработчиков.
Вообще, посыл статьи неверный — некто увидел список уязвимостей и сравнил его со списком для другого алгоритма, и только на основании длины списков сделал вывод. При этом не учтена известность уязвимостей и простота их недопущения. Для RSA всё известно и просто, а для ECC всё туманно и мало кому известно.
Ибо в абсолютно любом алгоритме будет куча подводных камней, о которые можно легко запнуться, даже если «погуглить» об известных проблемах. Одни только атаки по сторонним каналам чего стоят. Даже зная об их существовании и зная как от них защититься всё равно написать код который с их помощью сломать не выйдет черезвычайно сложно. Это про любой крипто-алгоритм.
Так что, по мне, аргумент «криптография должна быть простой чтобы кто угодно мог сам написать» не работает. Криптография — это сложно, там много тонкостей. Даже зная все эти тонкости реализовать безопасный алгоритм очень сложно.
Так я и не доказывал ничего о таком аргументе. Я говорил о сравнительной ситуации для двух алгоритмов. Для обоих алгоритмов применимы все ваши слова, поэтому все ваши слова никак не относятся к сравнению. Да, в криптографии куча засад, но в статье-то речь про выбор между ECC и RSA, а не про «сложности вообще».
Ну и зачем использовать сомнительные NIST кривые, если есть хорошо изученная и проверенная Curve25519, с constant-timing реализацией, входящей в кучу библиотек, и становящаяся сейчас стандартом де-факто? При этом предельно простая в использовании — секретным ключом может быть совершенно любая последовательность из 32 байтов. Никаких специальных выравниваний, ограниченных диапазонов etc.
Вообще о ECC — весьма рекомендую почитать safecurves.cr.yp.to.
Один из плюсов RSA — широкая распространенность готовых функций для зашифровки текста открытым ключем и расшифровки закрытым.
Недавно искал как сделать тоже самое с DSA, ECDSA, ed25519. Не смог сходу найти. Буду признателен, если кто-нибудь подскажет как это сделать на go.
Хватит использовать RSA