Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 79
А я думал там только полезные доклады…
Полезность… она субъективна, так же как и интересность. По крайней мере я знаю конкретных людей, кому этот доклад полезен и интересен.
Вообще они ничего нового не рассказали.
На счет полиномиальности решения NPC задач. Даже если и найдут полиномиальный алгоритм, то это еще не факт, что он будет малой степени.
Есть случаи когда находят теоретическую оценку на алгоритм вроде O(n^32). Фактически даже для n = 3 такой алгоритм выглядит ужасающе.
На счет полиномиальности решения NPC задач. Даже если и найдут полиномиальный алгоритм, то это еще не факт, что он будет малой степени.
Есть случаи когда находят теоретическую оценку на алгоритм вроде O(n^32). Фактически даже для n = 3 такой алгоритм выглядит ужасающе.
для подавляющего большинства участников этой конференции такая информация звучит как в сотый раз реферат школьного уровня.
натурально — ничего нового не сказано.
натурально — ничего нового не сказано.
А причем тут дискретный логарифм и факторизация? Атаки, которые авторы приводят в пример это просто ошибки в реализации, причем не в части асимметричного шифрования. думаю все очень сильно притянуто за уши. Хотя посыл в целом верный. Давно пора на эллиптику переходить.
о которой пока тоже не особо-то известно.
там задача логарифмирования так же не доказана же.
там задача логарифмирования так же не доказана же.
Автор имел в виду что точно также как внезапно нашлись уязвимости в протоколе — могут найтись уязвимости в алгоритме.
Просто сравнение очень неудачное. RSA появился в 70-х годах. За условные 40 лет использования практически осуществимых уязвимостей не найдено. TLS 1.0 разработан в 1999 году, в том же году Брюс Шнайер предсказывал практические атаки на протокол(он об этом в своем блоге писал, после публикации атаки BEAST). Да, для реализации уязвимостей потребовалось более 10 лет, но эти уязвимости предсказывались специалистами. С RSA и DSA такого не было. Поэтому с авторами доклада не согласен.
Практически осуществимые варианты факторизации появлялись.
Когда эллиптикой стало возможно мочить 256битные числа за единицы минут — за RSA мне было по-настоящему страшно.
К счастью, пока, всё-таки, барьер в 768 взят в единичных вариантах, а не массовых.
Это, конечно, настораживает, что почти за 2 десятилетия (если не ошибаюсь, ECM появился в 87 году?) ничего более оптимального не появилось, но с тем же успехом может означать что лучше-то и нетути.
Когда эллиптикой стало возможно мочить 256битные числа за единицы минут — за RSA мне было по-настоящему страшно.
К счастью, пока, всё-таки, барьер в 768 взят в единичных вариантах, а не массовых.
Это, конечно, настораживает, что почти за 2 десятилетия (если не ошибаюсь, ECM появился в 87 году?) ничего более оптимального не появилось, но с тем же успехом может означать что лучше-то и нетути.
И все таки, согласись, что примерная оценка времени в 2^90, которую имеют самые быстрые субэкспоненциальные алгоритмы, для ключа RSA длиной в 1024 бит это с сегодняшним уровнем вычислительной техники еще далеко не угроза для асимметричной криптографии. А ведь еще есть солидный запас, практически все решения поддерживают длину ключа в 4096 бит.
Пока да. Главная проблема — это расслабон. Ну сменили 4k RSA на 384bit ECDSA, и опять дудим в трубочку.
Не могу сходу вспомнить по какому запросу гуглил, но была же табличка — товарищи снимали по сети доступные сертификаты, и считали НОД для них, тем самым смогли вскрыть значительное количество их ключей.
Самое же главное в этом — что подавляющее большинство ключей и сертификатов в Сети — всё еще 1к размером.
Не могу сходу вспомнить по какому запросу гуглил, но была же табличка — товарищи снимали по сети доступные сертификаты, и считали НОД для них, тем самым смогли вскрыть значительное количество их ключей.
Самое же главное в этом — что подавляющее большинство ключей и сертификатов в Сети — всё еще 1к размером.
Да тоже читал что то такое. Там вроде неправильно работал PRNG в UNIX системах. Но мы опять приходим к тому с чего начинали. Об атаках на сами криптопримитивы речи не идет. Все сводится к неправильным реализациям. Это беда конечно, но такое всегда было и всегда будет.
да, плюс роутеры, у которых просто нет нужного количества энтропии
По описанию похоже на www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf — Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices
Как-то я безнадёжно отстал, 512 бит похоже уже берётся за считанное время на домашних пеньках:
www.math.ttu.edu/~cmonico/software/ggnfs/
www.math.ttu.edu/~cmonico/software/ggnfs/
Согласен. Чаще всего ошибка таится в реализации. А для асимметрического протокола на трудноразрешимых задачах стойкость доказана практикой. Ну подойдет вычислительная мощность и что, на 1024 бита параметры увеличат и снова можно лет 50 пользоваться. А для эллиптических кривых так вообще есть куда расти в этом плане. Там, вроде как, проблема только при шифровании (биекция алфавита и точек), но пусть шифрование самих данных так и остается на симметричных протоколах с доказуемой стойкостью :)
Про уши точно подмечено)
Про уши точно подмечено)
удалено (не туда попал)
Соглашусь с NeverWalkAloner
То, что авторы протокола изменяют размер криптованного сообщения при незначительном изменении содержащихся в нем данных и открывает класс «Oracle» атак вида «а давайте вот сюда прибавим один байтик и посмотрим изменится ли размер ответа от сервера».
То, что авторы протокола изменяют размер криптованного сообщения при незначительном изменении содержащихся в нем данных и открывает класс «Oracle» атак вида «а давайте вот сюда прибавим один байтик и посмотрим изменится ли размер ответа от сервера».
Не увидел чего-то такого, что срывало бы покровы. Думал конкретика, а тут сплошное «могут появиться». Интересно, а они про квантовые компьютеры и связанные с этим проблемы криптографии слышали? Или это будет темой следующего доклада?
А на нём, вероятно, они расскажут, что алгоритм Шора…
Скорее всего на доклад нужно смотреть не в научном аспекте. Я бы изучил список приглашённых гостей и личности докладчиков (нет ли там кого-то от правительства / армии / спецслужб / казначейства). Такие страшилки, из разряда «существует ненулевая возможность, что кругом враги, давайте покупать пулемёт» — обычно только попытка вытрясти денег (в данном случае на лицензирование технологий и на их внедрение), либо артподготовка к последующей попытке вытрясти денег.
Большая часть её реализации запатентована компанией BlackBerry, и патентные проблемы заставили некоторых производителей отказаться от поддержки технологии.
Патентами покрыта реализация или алгоритм? Если запатентованы реализации (т.е. исходный код), то черт с ним, можно сделать новую реализацию уже имеющегося алгоритма. (Для ясности добавляю, что патенты на исходные коды ПО выдаются в очень немногих странах, в остальных исходники защищаются законодательством об авторских правах по тому же принципу, что и литературные произведения).
Т.е., если патенты на реализацию, а сам алгоритм извесен — наличие патентов не проблема.
Если патент получен на сам алгоритм, тогда выступление математиков выглядит не более как рекламная акция компании BlackBerry: «Ай-я-яй, что ж вы такие не хорошие, не пользуетесь технологиями, покрытыми нашими патентами».
Действительно, больше похоже на рекламу BlackBerry. Если задачу факторизации и научат решать за полиномиальное время, то к этому времени, вполне возможно все уже перейдут на квантовую передачу данных. В крайнем случае, вернёмся к шифрам Вернама;)
«Существует ненулевая вероятность того, что в будущем найдётся подобное решение, возможное за полиномиальное время, что сулит криптографический апокалипсис.»
Для чего, что произойдёт в будущем, нулевая вероятность?
Для чего, что произойдёт в будущем, нулевая вероятность?
А ничего, что OpenSSH уже два года использует по умолчанию ECDSA (на базе эллиптических кривых), а уж российские ГОСТы и уже более десяти лет как переведены на эллиптические рельсы?
Смешно читать этот текст…
Смешно читать этот текст…
По моему, бОльшие риски для криптографии связаны с развитием квантовых вычислений. Есть-ли сейчас какие-то криптографические технологии которые могут помочь против них?
только-шифровальный блокнот.
Шифровальный блокнот не поможет. Если шифрующая последовательность (ключ) повторится хотя бы несколько раз (может и двух хватит) то начнёт проявляться когерентность.
Спасение только в бесконечном ключе — но тогда ведь весь смысл возни с сертификатами пропадает.
Спасение только в бесконечном ключе — но тогда ведь весь смысл возни с сертификатами пропадает.
Думаю для квантового компьютера код длиной в биллионы знаков-обычное дело. Тем паче, если использовать на каждое слово свой код, то как алгаритм будет разбиратся, из множества противоречивых друг другу вариантов, правильный?
> Если шифрующая последовательность (ключ) повторится хотя бы несколько раз
… то это не одноразовый блокнот (One-time pad).
… то это не одноразовый блокнот (One-time pad).
А если найти сложные вычисления для квантого компьютера и на их основе создать ассиметричный алгоритм?
Есть ряд асимметричных алгоритмов основанных на принципиально других проблемах нежели факторизация и дискретный логарифм. Для таких задач пока неизвестны квантовые алгоритмы решения. Об одном из таких алгоритмов я когда то писал на хабре.
я думаю 1 моль вещества возмёт его и брутом.
Я думаю, 2^512 вариантов 512-битного ключа рассмеются в лицо 6*10^23 молекулам одного моля.
Квантовый компьютер использует квантовые состояния частиц, число которых растёт по экспаненте от числа состовляющих систему частиц. Так, что теоретически е^(6*10^23) это явно больше 2^512.
Я думал, речь о вычислениях на ДНК ( www.keldysh.ru/papers/2005/prep57/prep2005_57.html ), а не о мифических квантовых.
Просто никто не меряет мощность квантового в молях, это скорее свойство химических компов.
Квантовые считалки потребуют точной настройки каждой частицы, как и сейчас организованы процессоры, а не кучу-малу.
Просто никто не меряет мощность квантового в молях, это скорее свойство химических компов.
Квантовые считалки потребуют точной настройки каждой частицы, как и сейчас организованы процессоры, а не кучу-малу.
Согласен. Я говорил про теоретическую возможность данной технологии, а не про практическую возможность её реализации.
в общем, если предварительно настроить комп для вычисления (и потратить для этого 2^511 времени), результат будет моментально, да.
Всё зависит от квантового алгоритма. Если придумают квантовый алгоритм, чьё время вычисления падает по быстрорастущей функции(вроде логарифма или степенных функций, экспоненте), то время вычисления снизится до вполне приемлемых порядков. Как пример, квантовый алгоритм факторизация чисел(алгоритм Шора).
Сами же квантовые вычисления и помогут, см. квантовая криптография.
А что там сейчас с алгоритмом Шора и квантовыми вычислениями, на больших числах? Я слышал, что успешно разложили какое-то двухзначное число, на этом и остановились.
Новость вкратце: Если докажут, что P=NP, то нынешние алгоритмы криптографии будет возможно сломать. А пока-что ломают через баги в имплементации.
А, секунду… Тоесть и не новость вовсе?
А, секунду… Тоесть и не новость вовсе?
Если докажут, что P=NP, это будет означать, что быстрый алгоритм разложения произвольного числа на простые множители существует. Но сам по себе он от этого не найдется. Другое дело, что из доказательства P=NP, возможно, будет видно, в каком направлении копать, чтобы этот алгоритм найти. А может и не будет видно.
Само по себе доказательство может заключаться в обнаружении такого алгоритма.
А может и не заключаться… ;-)
Теорема о P=NP носит более общий характер, поэтому не может доказываться через нахождение такого алгоритма для частного случая.
Разумно.
Однако она может доказываться через нахождение полиномиального алгоритма для решения любой NP-полной задачи.
Кстати, нам и не нужно знать, что P=NP для того, чтобы сломать криптографию. Нам достаточно найти сам этот частный случай.
Вы правы, но ветка комментариев начиналась не с этого.
А мысль о том, что чтобы сломать конкретный криптографический алгоритм надо его сломать, мне кажется и так достаточно очевидной.
Понятно, что для того. чтобы опрокинуть алгоритм RSA, надо просто найти быстрый алгоритм разложения произвольного числа на простые множители, и черт с ними с P и NP.
А мысль о том, что чтобы сломать конкретный криптографический алгоритм надо его сломать, мне кажется и так достаточно очевидной.
Понятно, что для того. чтобы опрокинуть алгоритм RSA, надо просто найти быстрый алгоритм разложения произвольного числа на простые множители, и черт с ними с P и NP.
Нет. Если я не ошибаюсь, все эн-пэ-полные задачи эквивалентны. Быстрое решение одной из них означает быстрое решение остальных, и означает, что п равно нп
Если мне не изменяет память, не доказано, что задача факторизации или дискретного логарифмирования является NP-полной.
Общеизвестно, что в основе асиметричной криптографии лежит два ключа: один может зашифровать данные, другой используется для их расшифровки.
Не первый раз вижу это утверждение, но это же ерунда: для зашифрования используется закрытый ключ отправителя и открытый получателя, а для расшифрования используется закрытый получателя и открытый отправителя. Т.е. в обоих процессах используются и открытые, и закрытые ключи.
Неверно. (Такое ощущение, что вы путаете основы и базирующийся на них протокол Диффи-Хеллмана. Читайте матчасть.)
Вкратце: я зашифровываю вашим открытым ключом и отдаю вам. Только вы можете расшифровать своим закрытым ключом. Вы сможете прочитать содержимое, но не узнаете, кто отправил его.
В общем, есть два варианта:
— Я шифрую своим закрытым ключом — это моя подпись. С помощью моего открытого ключа (доступного всем) можно доказать, что сообщение создал (зашифровал) именно я, т.к. открытый ключ подошёл именно мой, а только у меня есть соответствующий закрытый ключ.
— Я шифрую вашим закрытым ключом — это я защищаю сообщение от кражи для передачи вам. Только вы, владелец закрытого ключа, сможете увидеть содержимое сообщения.
Часто подпись и защита от подсматривания используются вместе (причём подписывают не сообщение, а его хеш, и защищают не сообщение, а некий случайный ключ симметричного алгоритма, которым уже шифруют само сообщение), однако никто не обязывает вас одновременно защищать и подписывать. Для каждой из этих отдельных задач нужно ровно два ключа.
Вкратце: я зашифровываю вашим открытым ключом и отдаю вам. Только вы можете расшифровать своим закрытым ключом. Вы сможете прочитать содержимое, но не узнаете, кто отправил его.
В общем, есть два варианта:
— Я шифрую своим закрытым ключом — это моя подпись. С помощью моего открытого ключа (доступного всем) можно доказать, что сообщение создал (зашифровал) именно я, т.к. открытый ключ подошёл именно мой, а только у меня есть соответствующий закрытый ключ.
— Я шифрую вашим закрытым ключом — это я защищаю сообщение от кражи для передачи вам. Только вы, владелец закрытого ключа, сможете увидеть содержимое сообщения.
Часто подпись и защита от подсматривания используются вместе (причём подписывают не сообщение, а его хеш, и защищают не сообщение, а некий случайный ключ симметричного алгоритма, которым уже шифруют само сообщение), однако никто не обязывает вас одновременно защищать и подписывать. Для каждой из этих отдельных задач нужно ровно два ключа.
Пока что из всех криптоугроз для SSL самой близкой и серьёзной можно считать визит сотрудников несуществующего агентства в офис веризон или там геотраст с просьбой отдать им маленький файлик ca.key.
Не криптографистов, а криптографов.
Я даже подумал, что это Ализар написал :)
С точки зрения квантовых вычислений эллиптические кривые не сложнее факторизации.
пруф?
Та же самая проблема логарифмирования, просто немного другое поле, в котором нужно производить операции. А так — оригинальные алгоритмы Шора (1994) решают и дискретное логарифмирование, и разложение на множители.
www.math.uwaterloo.ca/~amchilds/teaching/w08/l03.pdf
arxiv.org/pdf/quant-ph/0301141v2.pdf
www.math.uwaterloo.ca/~amchilds/teaching/w08/l03.pdf
It is straightforward to use Shor’s algorithm to solve the discrete log problem for an elliptic curve over F_p in time poly(log p).… Thus, in practice, much smaller key sizes are used in elliptic curve cryptography than in factoring-based cryptography. Ironically, Shor’s algorithm takes a comparable number of steps for both factoring and discrete log (regardless of the group involved), with the caveat that group operations on an elliptic curve take more time to calculate than ordinary multiplication of integers.
arxiv.org/pdf/quant-ph/0301141v2.pdf
It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits.
Нас ждет очередная компания типа проблемы 2000-года, чтобы индустрия заработала бабла :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Эксперты призывают готовиться к криптоапокалипсису