Комментарии 45
— Хватит использовать "сортировку пузырьком"!
— А что, её ещё кто-то использует?
Сортировка пузырьком очень хороша чтобы обучать студентов :-)
Там безумно много всяких вариантов реализации можно показать на конкретном простом примере.
Там безумно много всяких вариантов реализации можно показать на конкретном простом примере.
Я закончил универ лет двадцать назад. Мы тоже изучали "сортировку пузырьком". В IT-индустрии каждый год какие-то изменения, а в обучении студентов ничего не поменялось? Жёстко им будет впрыгивать со студентческой скамьи в профессию.
Мы на первом курсе изучали штук 10 разных алгоритмов сортировки чтобы понять как они работают и чтобы понять что такое О большое, о малое и вообще сложность алгоритмов. Мне кажется это как раз хорошо изучать на разных алгоритмах, которые вычисляют один и тот же результат разными способами.
Лет 10 назад рассказывали про разные методы сортировки и в каких случаях какие предпочтительнее. Подождём отзыв текущих студентов, и можно будет сравнить изменения.
Мои инсайдеры говорят, что разработчики математики не собираются выпускать третью часть, поэтому эта часть программы обучения будет актуальна всегда)
Другое дело, что просто свинство — учить современных студентов на мертвом (с точки зрения бизнеса) паскале, попутно используя windows xp с ms office 2003. И как раз тут произошел значительный прогресс за последние 20 лет.
Если еще чуть больше углубляться в возможные подлянки вузовских программ, то тут будет использование закрытого по вместо открытого при прочих равных — но это очень индивидуальный вопрос, зависящий от специализации и особенностей конкретного курса
Я думаю не стоит объяснять в каких случаях сортировка пузырьком быстрее квиксорта ;-)
Те же Curve25519 и Ed448-Goldilocks на порядок проще в использовании и надежнее, чем RSA, плюс куда как более короткий ключ при аналогичной или более высокой криптостойкости.
Реально не понимаю тех, кто продолжает RSA использовать.
Реально не понимаю тех, кто продолжает RSA использовать.
Несколько вариантов:
1) RSA есть по дефолту везде
2) не все настолько хорошо умеют в безопасность, чтобы знать, что что-то другое НАДО искать
3) не всем это на самом деле нужно
1) RSA есть по дефолту везде
2) не все настолько хорошо умеют в безопасность, чтобы знать, что что-то другое НАДО искать
3) не всем это на самом деле нужно
Паранойя, вероятно. Как сказано в статье, «математика, стоящая за ECC, настолько сложна, что очень немногие люди чувствуют себя достаточно уверенно, чтобы ...» лично проверить отсутствие бекдоров в чужой реализации. Ну а если не можешь сам проверить, что бекдоров нет, то следует предполагать, что они там есть.
Мне кажется, из статьи как раз следует, что проверить на бекдоры RSA гораздо сложнее, чем ECC. Хоть в ECC и сложная математика, но по сути всего две операции — умножение точки на скаляр и сложение двух точек. Да, там можно накосячить, но это гораздо проще вычислить, чем в RSA
В статье же про собственные реализации RSA. В своем RSA конечно могут быть баги, но там точно нет закладок от ЦРУ/ФСБ/…
Про бекдоры в RSA я, кстати, тоже писал ) habr.com/ru/post/248269
В основе RSA лежит настолько простые математические принципы, что их беглое изложение здесь заняло абзац. Все уязвимости алгоритма строятся на слабости выбора параметров. А в основе ECC лежит дикая магия с полями чисел, в которых over-дофига слабостей которые без вдумчивого выкуривания всего поля можно и не найти. RSA понятен и поэтому безопасен. Если в основе механизма безопасности лежит большой непонятный кусок магии, о котором можно судить только по заявлениям некоторых о его безопасности, то система не безопасна ни разу, а мы находимся во власти этих очень умных людей.
RSA похоронить не смогут, по крайней мере нужно не дать. Пусть всё работает на этих ваших ECC, но я должен иметь возможность закрыть нечто ценное тем, чему полностью доверяю.
RSA похоронить не смогут, по крайней мере нужно не дать. Пусть всё работает на этих ваших ECC, но я должен иметь возможность закрыть нечто ценное тем, чему полностью доверяю.
Разработчики, чьи приложения выступают как клиенты библиотек шифрования (то есть только используют шифрование, а не реализуют его), в любом случае не знают и не должны знать деталей внутренней реализации и причин уязвимости этих библиотек. Задача таких разработчиков — подключить стороннюю библиотеку и зашифровать свои данные с ее помощью, вот и все. По вашей логике все, что непонятно вам лично и не может быть непосредственно вами проверено (а это большинство систем в мире), вы считаете небезопасным?
По вашей логике все, что непонятно вам лично и не может быть непосредственно вами проверено (а это большинство систем в мире), вы считаете небезопасным?
Именно так. Когда мы говорим о безопасности Open Source, мы прежде всего говорим о том, что те кому важна безопасность в этом конкретном месте, прочитают и поймут код, соберут из него ПО и будут использовать. Остальное фикция и очковтирательство. Я не говорю, что лично проверяю всё подряд, но в критических местах НУЖНО понимать, что происходит на большинстве уровней. Да, прозрачность ПО не даёт почти ничего в сфере гражданских систем, поскольку большинство аппаратных платформ для этих систем не предоставляют железа без толстого слоя абстракции, и x86/amd64 тому превосходный пример, однако подкласс понятных (причём кристально понятных) систем и аппаратных платформ должен быть, и на таких и только на таких платформах и ПО, которые абсолютно предсказуемы на всех уровнях абстракции вплоть до состояния всех регистров на всех режимах своей работы, и можно строить системы с высоким уровнем безопасности. И RSA со своим уровнем предсказуемости обязан быть в этом стеке технологий…
«Бекдоры» есть в абсолютно любом алгоритме шифрования без вариантов. Они, конечно, могут быть имплантированы дополнительно, в том числе, сотрудниками ФСБ/ЦРУ/..., как вы говорите, однако даже написанный с самыми чистыми помыслами код имеет уязвимости на уровне математики (читать: вселенной). Только в этой статье имеется около десятка уязвимостей алгоритма RSA и способов обхода. Это математика, детка. Со временем, конечно, уязвимости проявят себя, если алгоритм (абсолютно любой алгоритм шифрования) будет актуальным достаточно долго. Наша задача — использовать алгоритм, уязвимости которого неизвестны врагам.
4) В эллиптические кривые злые русские могли подкинуть бэкдор
Тем не менее, злоумышленник может восстановить закрытый ключ, когда d меньше корня 4-й степени из N.
Более того, ЕМНИП примерно в 25-30% случаев цепной дробью можно получить d даже если оно не подверженно оригинальной границе Винера, несколько лет назад занимались этой темой и доказали экспериментально.
По уникальности p и q — может кто-то прокомментировать мнение англоязычных авторов? Вариантов p и q 10 в 300+ степени, нагенерировали их ну пусть триллион (10 в 12), одна база данных на такое количество чисел порядка 10 в 1024 займёт 128 тысяч террабайт, я уж не говорю об оперативности перебора всех вариантов из базы. Но самое интересное — 10 в 12 от 10 в 300+ — это не упомянутый в статье 1%, это просто ничтожнейшая из ничтожнейших долей. Поэтому вопрос — зачем пугать такой «уязвимостью»? Это примерно то же самое, что пугать возможностью взлома при помощи полного перебора (на который потребуется безумное количество триллионов времён жизни вселенной).
Вот очень хорошая статья на эту тему: «Mining Your Ps and Qs»
Смысл в том, что P и Q разных очень много, да. Но все пользуются одинаковыми алгоритмами и библиотеками чтобы их сгенерировать (и плохими генераторами случайных чисел). Иногда выходит что одно из двух чисел у одного ключа совпадают с одним из чисел другого. В результате можно через GCD найти оба ключа. Примерно это в статье и было проделано. Да, 1% — это не много, но по теории веротяности выходит многовато, в смысле должно быть меньше или не быть совсем (вариантов P и Q очень много). В статье говорится об >1% SSH ключей, это более 100 тыс. А вот 100 тыс ключей уже не выглядит маленьким числом.
Смысл в том, что P и Q разных очень много, да. Но все пользуются одинаковыми алгоритмами и библиотеками чтобы их сгенерировать (и плохими генераторами случайных чисел). Иногда выходит что одно из двух чисел у одного ключа совпадают с одним из чисел другого. В результате можно через GCD найти оба ключа. Примерно это в статье и было проделано. Да, 1% — это не много, но по теории веротяности выходит многовато, в смысле должно быть меньше или не быть совсем (вариантов P и Q очень много). В статье говорится об >1% SSH ключей, это более 100 тыс. А вот 100 тыс ключей уже не выглядит маленьким числом.
Спасибо, посмотрел коротко статью. Там всё сводится к заявлениям типа:
Что это за «long-tailed» распределения, я не понял, но очевидно одно — в ряде библиотек используется алгоритм, использующий лишь узкие области в доступном пространстве возможностей. Но что из этого следует? Из-за того, что кто-то по недоразумению вместо по возможности равномерного распределения использовал очевидно плохой вариант, под сомнение ставится всё шифрование на основе RSA. Упрощённо — кто-то где-то попал под поезд, так теперь давайте же запретим все поезда! А вот самолёты не будем, ведь это такая прибыльная область!
we would see a long-tailed distribution in their frequencies
Что это за «long-tailed» распределения, я не понял, но очевидно одно — в ряде библиотек используется алгоритм, использующий лишь узкие области в доступном пространстве возможностей. Но что из этого следует? Из-за того, что кто-то по недоразумению вместо по возможности равномерного распределения использовал очевидно плохой вариант, под сомнение ставится всё шифрование на основе RSA. Упрощённо — кто-то где-то попал под поезд, так теперь давайте же запретим все поезда! А вот самолёты не будем, ведь это такая прибыльная область!
НЛО прилетело и опубликовало эту надпись здесь
Именно так из звучит, и такую статью тоже написать не грех.
Очень много областей, где Си давно пора перестать использовать именно поэтому, но его продолжают там использовать, а когда в очередной раз приходит атакующий и все разламывает в клочья после получаса реверса — винят кого угодно, только не инструмент кривой.
Дали коновалам в руки скальпель, а теперь удивляются, что вся комната в крови…
Очень много областей, где Си давно пора перестать использовать именно поэтому, но его продолжают там использовать, а когда в очередной раз приходит атакующий и все разламывает в клочья после получаса реверса — винят кого угодно, только не инструмент кривой.
Дали коновалам в руки скальпель, а теперь удивляются, что вся комната в крови…
Инструмент используют люди. А люди устают, ошибаются, ленятся, срезают углы, забывают и т.п. Всегда. Если инструмент не учитывает эти особенности людей (а Си — хрестомайтийный пример подобного инструмента) — конец немного предсказуем.
НЛО прилетело и опубликовало эту надпись здесь
В системном программировании Си и плюсам пока особой альтернативы нет, согласен. Хотя Rust пытается конкурировать.
Но чтобы на Си писать нужно быть очень осторожным и понимать как ОС и компьютер работает с памятью, как минимум. А вот с этим уже проблемы часто и даже толковые программисты часто лепят уязвимости.
Тот же Rust пытается закрыть большую часть подобных ошибок уже на compile time. Это к разговору об инструментах.
Но чтобы на Си писать нужно быть очень осторожным и понимать как ОС и компьютер работает с памятью, как минимум. А вот с этим уже проблемы часто и даже толковые программисты часто лепят уязвимости.
Тот же Rust пытается закрыть большую часть подобных ошибок уже на compile time. Это к разговору об инструментах.
НЛО прилетело и опубликовало эту надпись здесь
Согласен, что Раст это не silver bullet. И синтаксис меня тоже убивает. Хотя шаблоны крестов, особенно когда наслаиваются друг на друга, тоже та еще жесть.
Но, на мой взгляд, это шаг в правильную сторону. Я сам больше Go предпочитаю и считаю его неплохим гибридом языков с GC и компилируемых в нативный код. Да, там можно прострелить себе ногу несколько легче чем в Расте, но зато он легко читаемый :) Ну и нативное concurrency решает.
Но, на мой взгляд, это шаг в правильную сторону. Я сам больше Go предпочитаю и считаю его неплохим гибридом языков с GC и компилируемых в нативный код. Да, там можно прострелить себе ногу несколько легче чем в Расте, но зато он легко читаемый :) Ну и нативное concurrency решает.
API, который стабилизируется, стабилизируется, да все за 9 лет никак не остановится.
А что мешает пользоваться тем, что стабильно?
И все. Хваленая безопасность закончилась.
Нет, не закончилась. Теперь совершенно точно известно, где ошибка работы с памятью невозможна, а где возможна.
НЛО прилетело и опубликовало эту надпись здесь
многие библиотеки используют небольшую публичную экспоненту и не делают простую проверку выравнивания при обработке подписей RSA.
Это же не недостаток RSA, а то как его используют. Это же относится и к другим алгоритмам.
Авторы преподнесли проблемы с имплементацией отдельных библиотек как проблемы с самим алгоритмом. Очень странно слышать такие вещи от людей которые пытаются учить людей криптографии.
RS/PS 256/512 отличные, широко используемые алгоритмы. Самая большая проблема это размер ключа. RSA жирный. Но за то в отличии от EDDSA/ECDSA он хорошо исследованный алгоритм. В отличии от NIST EC у RSA нет стрёмных никому не известных констант, а я говорю о NIST потому что в 90% случае вы будете использовать P256.
RSA жить и жить. Просто не надо пилить свою крипту. Пользуйтесь известными решениями.
Авторы преподнесли проблемы с имплементацией отдельных библиотек как проблемы с самим алгоритмом. Очень странно слышать такие вещи от людей которые пытаются учить людей криптографии.
В прикладной криптографии (которая внутри «разработки ПО», а не «математики») нет собой разницы между алгоритмом и реализацией алгоритма, потому что никаких других алгоритмов, кроме реализованных или самостоятельно разработчиком, или разработчиками библиотек, там нет. И атакуют там именно реализации.
Так вот с точки зрения прикладного криптографа RSA — действительно плохой алгоритм, потому что его практически невозможно «держать правильным образом», о чем авторы статьи и сообщают. И не только они, вот отличный пример того, как недостатки криптографических API приводят к тому, что 70% криптографического кода имеет серьезные проблемы, которые никто из разработчиков не в состоянии заметить.
Любые работающие технологии безопасности должны быть простыми как палка, и при этом стараться максимально усложнить свое неправильное использование (при помощи системы типов, статического анализа, или других инструментов), а нынешние (а тем более прошлые) реализации RSA в большинстве своем похожи скорее на OpenSSL, чем на упомянутый авторами libsodium.
>> с точки зрения прикладного криптографа RSA — действительно плохой алгоритм, потому что его практически невозможно «держать правильным образом»
А непонятный большинству алгоритм на эллиптических кривых, значит, можно «держать»? То есть автор статьи считает, что достаточно просто соблюдать рекомендации «умных людей» в отношении эллиптики, но вот в отношении RSA такие же рекомендации умных людей уже не считаются полезными. Получается, то в одном случае «держать» можно, а в другом аналогичном — нельзя. В чём же разница?
Наверное в том, что RSA привлекает больше внимания и у него находят больше уязвимостей. Но если вместо RSA будет что-то другое, то у него точно так же станут находить больше уязвимостей. И что тогда?
А непонятный большинству алгоритм на эллиптических кривых, значит, можно «держать»? То есть автор статьи считает, что достаточно просто соблюдать рекомендации «умных людей» в отношении эллиптики, но вот в отношении RSA такие же рекомендации умных людей уже не считаются полезными. Получается, то в одном случае «держать» можно, а в другом аналогичном — нельзя. В чём же разница?
Наверное в том, что RSA привлекает больше внимания и у него находят больше уязвимостей. Но если вместо RSA будет что-то другое, то у него точно так же станут находить больше уязвимостей. И что тогда?
В ECC тоже ищут много уязвимостей и всякие интересные штуки находят всемя от времени. Про симметричную криптографию можно сказать тоже самое, но это не значит что всё сломано.
Про RSA vs. ECC главная идея проста: есть очень много способов накосячить с RSA и не накосячить достаточно сложно, а вот с ECC накосячить способов меньше и это сделать сложнее.
Про RSA vs. ECC главная идея проста: есть очень много способов накосячить с RSA и не накосячить достаточно сложно, а вот с ECC накосячить способов меньше и это сделать сложнее.
>> есть очень много способов накосячить с RSA
Ну так а на что «умные люди»? Они дают рекомендации — туда не ходи, снег башка попадёт. Кто сам неграмотный — просто выполняет рекомендации. Но точно то же самое и с ECC — умные люди дают рекомендации и эти рекомендации выполняют разработчики. Возможно, количество рекомендаций для ECC раза в два-три меньше, но зато имеем простоту самого алгоритма RSA, доступную большинству разработчиков. ECC же гораздо сложнее, и без понимания этой сложности разработчики превращаются в простейших копировщиков, исполняющих совершенно непонятные им «рекомендации», которые по сути есть инструкции по копированию. То есть разработчики в данном случае по сути не нужны, ведь можно вообще не копировать, а взять готовое решение. Но чем это лучше готового решения на RSA? Готовое на RSA есть в открытом доступе и проверено массой грамотных участников процесса, точно так же, как и готовое на ECС. Но если всё же есть необходимость сделать самостоятельную версию, то сама сложность ECC не даёт вариантов — либо её понимаешь, либо по сути просто копируешь чужое, что не лучше скачивания готового. Но если у разработчика уровень достаточен для понимания ECC, то уж косяки в процессе подготовки данных для RSA он уж точно сможет заметить/понять. Если хотя бы погуглит на тему уязвимостей алгоритма — уже много проблем обойдёт. Ну а глубина понимания поможет дополнительно не накосячить.
В целом — ECC сложнее, что означает невозможность обнаружить косяк для большинства разработчиков, есть возможность лишь для тупого копирования (без понимания). RSA проще и косяки широко известны, что даёт возможность менее грамотному в плане математики разработчику избежать большинства ошибок. Оставшиеся уязвимости в силу их нетривиальности скорее всего равнозначны по уровню опасности и для грамотных математиков и для обычных разработчиков.
Вообще, посыл статьи неверный — некто увидел список уязвимостей и сравнил его со списком для другого алгоритма, и только на основании длины списков сделал вывод. При этом не учтена известность уязвимостей и простота их недопущения. Для RSA всё известно и просто, а для ECC всё туманно и мало кому известно.
Ну так а на что «умные люди»? Они дают рекомендации — туда не ходи, снег башка попадёт. Кто сам неграмотный — просто выполняет рекомендации. Но точно то же самое и с ECC — умные люди дают рекомендации и эти рекомендации выполняют разработчики. Возможно, количество рекомендаций для ECC раза в два-три меньше, но зато имеем простоту самого алгоритма RSA, доступную большинству разработчиков. ECC же гораздо сложнее, и без понимания этой сложности разработчики превращаются в простейших копировщиков, исполняющих совершенно непонятные им «рекомендации», которые по сути есть инструкции по копированию. То есть разработчики в данном случае по сути не нужны, ведь можно вообще не копировать, а взять готовое решение. Но чем это лучше готового решения на RSA? Готовое на RSA есть в открытом доступе и проверено массой грамотных участников процесса, точно так же, как и готовое на ECС. Но если всё же есть необходимость сделать самостоятельную версию, то сама сложность ECC не даёт вариантов — либо её понимаешь, либо по сути просто копируешь чужое, что не лучше скачивания готового. Но если у разработчика уровень достаточен для понимания ECC, то уж косяки в процессе подготовки данных для RSA он уж точно сможет заметить/понять. Если хотя бы погуглит на тему уязвимостей алгоритма — уже много проблем обойдёт. Ну а глубина понимания поможет дополнительно не накосячить.
В целом — ECC сложнее, что означает невозможность обнаружить косяк для большинства разработчиков, есть возможность лишь для тупого копирования (без понимания). RSA проще и косяки широко известны, что даёт возможность менее грамотному в плане математики разработчику избежать большинства ошибок. Оставшиеся уязвимости в силу их нетривиальности скорее всего равнозначны по уровню опасности и для грамотных математиков и для обычных разработчиков.
Вообще, посыл статьи неверный — некто увидел список уязвимостей и сравнил его со списком для другого алгоритма, и только на основании длины списков сделал вывод. При этом не учтена известность уязвимостей и простота их недопущения. Для RSA всё известно и просто, а для ECC всё туманно и мало кому известно.
Скажем так, писать самому алгоритмы криптографии «для прода» (если это не для образовательных целей) — очень и очень плохая идея, даже безумно плохая.
Ибо в абсолютно любом алгоритме будет куча подводных камней, о которые можно легко запнуться, даже если «погуглить» об известных проблемах. Одни только атаки по сторонним каналам чего стоят. Даже зная об их существовании и зная как от них защититься всё равно написать код который с их помощью сломать не выйдет черезвычайно сложно. Это про любой крипто-алгоритм.
Так что, по мне, аргумент «криптография должна быть простой чтобы кто угодно мог сам написать» не работает. Криптография — это сложно, там много тонкостей. Даже зная все эти тонкости реализовать безопасный алгоритм очень сложно.
Ибо в абсолютно любом алгоритме будет куча подводных камней, о которые можно легко запнуться, даже если «погуглить» об известных проблемах. Одни только атаки по сторонним каналам чего стоят. Даже зная об их существовании и зная как от них защититься всё равно написать код который с их помощью сломать не выйдет черезвычайно сложно. Это про любой крипто-алгоритм.
Так что, по мне, аргумент «криптография должна быть простой чтобы кто угодно мог сам написать» не работает. Криптография — это сложно, там много тонкостей. Даже зная все эти тонкости реализовать безопасный алгоритм очень сложно.
>> аргумент «криптография должна быть простой чтобы кто угодно мог сам написать» не работает
Так я и не доказывал ничего о таком аргументе. Я говорил о сравнительной ситуации для двух алгоритмов. Для обоих алгоритмов применимы все ваши слова, поэтому все ваши слова никак не относятся к сравнению. Да, в криптографии куча засад, но в статье-то речь про выбор между ECC и RSA, а не про «сложности вообще».
Так я и не доказывал ничего о таком аргументе. Я говорил о сравнительной ситуации для двух алгоритмов. Для обоих алгоритмов применимы все ваши слова, поэтому все ваши слова никак не относятся к сравнению. Да, в криптографии куча засад, но в статье-то речь про выбор между ECC и RSA, а не про «сложности вообще».
«потому что в 90% случае вы будете использовать P256.»
Ну и зачем использовать сомнительные NIST кривые, если есть хорошо изученная и проверенная Curve25519, с constant-timing реализацией, входящей в кучу библиотек, и становящаяся сейчас стандартом де-факто? При этом предельно простая в использовании — секретным ключом может быть совершенно любая последовательность из 32 байтов. Никаких специальных выравниваний, ограниченных диапазонов etc.
Вообще о ECC — весьма рекомендую почитать safecurves.cr.yp.to.
Ну и зачем использовать сомнительные NIST кривые, если есть хорошо изученная и проверенная Curve25519, с constant-timing реализацией, входящей в кучу библиотек, и становящаяся сейчас стандартом де-факто? При этом предельно простая в использовании — секретным ключом может быть совершенно любая последовательность из 32 байтов. Никаких специальных выравниваний, ограниченных диапазонов etc.
Вообще о ECC — весьма рекомендую почитать safecurves.cr.yp.to.
Один из плюсов RSA — широкая распространенность готовых функций для зашифровки текста открытым ключем и расшифровки закрытым.
Недавно искал как сделать тоже самое с DSA, ECDSA, ed25519. Не смог сходу найти. Буду признателен, если кто-нибудь подскажет как это сделать на go.
DSA и ed25519 нужны для цифровых подписей, а не для шифрования. Что касается шифрования, можете посмотреть нашу Go библиотеку, она шифрует схемой ECIES на основе Curve25519
НЛО прилетело и опубликовало эту надпись здесь
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Хватит использовать RSA