stringtranslate.com

Доказуемая безопасность

Доказуемая безопасность относится к любому типу или уровню компьютерной безопасности , которая может быть доказана. Она используется по-разному в разных областях.

Обычно это относится к математическим доказательствам , которые распространены в криптографии . В таком доказательстве возможности злоумышленника определяются состязательной моделью (также называемой моделью злоумышленника): цель доказательства — показать, что злоумышленник должен решить основную сложную проблему , чтобы взломать безопасность моделируемой системы. Такое доказательство обычно не рассматривает атаки по сторонним каналам или другие атаки, специфичные для реализации, поскольку их обычно невозможно смоделировать без реализации системы (и, таким образом, доказательство применимо только к этой реализации).

За пределами криптографии этот термин часто используется в сочетании с безопасным кодированием и безопасностью по проекту , оба из которых могут полагаться на доказательства, чтобы показать безопасность определенного подхода. Как и в случае с криптографической настройкой, это включает в себя модель злоумышленника и модель системы. Например, код может быть проверен на соответствие предполагаемой функциональности, описанной моделью: это можно сделать с помощью статической проверки . Эти методы иногда используются для оценки продуктов (см. Общие критерии ): безопасность здесь зависит не только от правильности модели злоумышленника, но и от модели кода.

Наконец, термин «доказуемая безопасность» иногда используется продавцами программного обеспечения безопасности , которые пытаются продать такие продукты безопасности, как брандмауэры , антивирусное программное обеспечение и системы обнаружения вторжений . Поскольку эти продукты обычно не подлежат проверке, многие исследователи безопасности считают, что такие заявления являются продажей змеиного масла .

В криптографии

В криптографии система имеет доказуемую безопасность , если ее требования безопасности могут быть формально заявлены в состязательной модели, в отличие от эвристики, с четкими предположениями, что у противника есть доступ к системе, а также достаточно вычислительных ресурсов. Доказательство безопасности (называемое «редукцией») заключается в том, что эти требования безопасности выполняются при условии, что предположения о доступе противника к системе удовлетворены и некоторые четко заявленные предположения о сложности определенных вычислительных задач выполняются. Ранний пример таких требований и доказательств был дан Голдвассером и Микали для семантической безопасности и конструкции, основанной на проблеме квадратичного остатка . Некоторые доказательства безопасности находятся в заданных теоретических моделях, таких как модель случайного оракула , где реальные криптографические хеш-функции представлены идеализацией.

Существует несколько направлений исследований в области доказуемой безопасности. Одно из них — установить «правильное» определение безопасности для заданной, интуитивно понятной задачи. Другое — предложить конструкции и доказательства, основанные на общих предположениях, насколько это возможно, например, на существовании односторонней функции . Основная открытая проблема — установить такие доказательства, основанные на P ≠ NP , поскольку существование односторонних функций, как известно, не следует из гипотезы P ≠ NP .

Споры

Несколько исследователей обнаружили математические ошибки в доказательствах, которые использовались для заявлений о безопасности важных протоколов. В следующем частичном списке таких исследователей их имена сопровождаются сначала ссылкой на оригинальную статью с предполагаемым доказательством, а затем ссылкой на статью, в которой исследователи сообщили о недостатках: В. Шуп; [1] [2] А. Дж. Менезес; [3] [4] А. Джа и М. Нанди; [5] [6] Д. Галиндо; [7] [8] Т. Ивата, К. Охаши и К. Минемацу; [9] [10] М. Нанди; [11] [12] Х.-С. Корон и Д. Наккаче; [13] [14] Д. Чакраборти, В. Эрнандес-Хименес и П. Саркар; [15] [16] П. Гажи и У. Маурер; [17] [18] С.А. Какви и Э. Килц; [19] [20] и Т. Холенштейн, Р. Кюнцлер и С. Тессаро. [21] [22]

Коблиц и Менезес писали, что доказуемые результаты безопасности для важных криптографических протоколов часто имеют ошибки в доказательствах; часто интерпретируются вводящим в заблуждение образом, давая ложные заверения; как правило, полагаются на сильные предположения, которые могут оказаться ложными; основаны на нереалистичных моделях безопасности; и служат для отвлечения внимания исследователей от необходимости «старомодного» (нематематического) тестирования и анализа. Их серия статей, подтверждающих эти утверждения [23] [24], была спорной в сообществе. Среди исследователей, которые отвергли точку зрения Коблиц-Менезеса, был Одед Голдрайх , ведущий теоретик и автор книги «Основы криптографии» . [25] Он написал опровержение их первой статьи «Еще один взгляд на „доказуемую безопасность“» [26] , которую он назвал «О постмодернистской криптографии». Голдрайх писал: «... мы указываем на некоторые фундаментальные философские недостатки, лежащие в основе указанной статьи, и на некоторые из ее заблуждений относительно теоретических исследований в области криптографии за последнюю четверть века». [27] : 1  В своем эссе Голдрайх утверждал, что строгая методология анализа доказуемой безопасности является единственной, совместимой с наукой, и что Коблиц и Менезес являются «реакционерами (т. е. они играют на руку противникам прогресса)». [27] : 2 

В 2007 году Коблиц опубликовал статью «Непростые отношения между математикой и криптографией» [28] , в которой содержались некоторые спорные утверждения о доказуемой безопасности и других темах. Исследователи Одед Голдрайх, Боаз Барак, Джонатан Кац , Хьюго Кравчик и Ави Вигдерсон написали письма в ответ на статью Коблица, которые были опубликованы в выпусках журнала за ноябрь 2007 года и январь 2008 года. [29] [30] Кац, который является соавтором высоко оцененного учебника по криптографии, [31] назвал статью Коблица «снобизмом в чистом виде»; [29] : 1455  , а Вигдерсон, который является постоянным членом Института перспективных исследований в Принстоне, обвинил Коблица в «клевете». [30] : 7 

Иван Дамгард позже написал доклад с изложением позиции на ICALP 2007 по техническим вопросам, [32] и был рекомендован Скоттом Ааронсоном как хороший глубокий анализ. [33] Брайан Сноу , бывший технический директор Управления по обеспечению информации Агентства национальной безопасности США , рекомендовал доклад Коблица-Менезеса «Дивный новый мир безрассудных предположений в криптографии» [34] аудитории на конференции RSA 2010 Cryptographers Panel. [35]

Практико-ориентированная доказуемая безопасность

Классическая доказуемая безопасность в первую очередь направлена ​​на изучение взаимосвязи между асимптотически определенными объектами. Вместо этого, ориентированная на практику доказуемая безопасность касается конкретных объектов криптографической практики, таких как хэш-функции, блочные шифры и протоколы, поскольку они развертываются и используются. [36] Ориентированная на практику доказуемая безопасность использует конкретную безопасность для анализа практических конструкций с фиксированными размерами ключей. «Точная безопасность» или « конкретная безопасность » — это название, данное доказуемым сокращениям безопасности, где безопасность количественно определяется путем вычисления точных границ вычислительных усилий, а не асимптотической границы, которая гарантированно сохраняется для «достаточно больших» значений параметра безопасности .

Ссылки

  1. ^ Белларе, Михир; Рогауэй, Филлип (1995). «Оптимальное асимметричное шифрование». Достижения в криптологии — EUROCRYPT'94 . Конспект лекций по информатике. Том 950. С. 92–111. doi : 10.1007/BFb0053428 . ISBN 978-3-540-60176-0.
  2. ^ Шуп, Виктор (2002), «OAEP пересмотрен», Журнал криптологии , 15 (4): 223–249, doi : 10.1007/s00145-002-0133-9 , S2CID  26919974
  3. ^ Кравчик, Хьюго (2005). "HMQV: Высокопроизводительный безопасный протокол Диффи-Хеллмана". Достижения в криптологии – CRYPTO 2005. Конспект лекций по информатике. Том 3621. С. 546–566. doi : 10.1007/11535218_33 . ISBN 978-3-540-28114-6.
  4. ^ Менезес, Альфред Дж. (2007), «Еще один взгляд на HMQV», Журнал математической криптологии , 1 : 47–64, doi : 10.1515/JMC.2007.004 , S2CID  15540513
  5. ^ Белларе, Михир; Пьетрзак, Кшиштоф; Рогавэй, Филлип (2005). «Улучшенный анализ безопасности для MAC-адресов CBC». Достижения в криптологии – CRYPTO 2005. Конспект лекций по информатике. Том 3621. С. 527–545. doi : 10.1007/11535218_32 . ISBN 978-3-540-28114-6.; и Пьетрзак, Кшиштоф (2006), «Жесткая граница для EMAC», Автоматы, Языки и Программирование , Конспект лекций по информатике, т. 4052, стр. 168–179, doi :10.1007/11787006_15, ISBN 978-3-540-35907-4
  6. ^ Джа, Эшвин; Нанди, Мридул (2016), «Пересмотр структурных графов: приложения к CBC-MAC и EMAC», Журнал математической криптологии , 10 (3–4): 157–180, doi :10.1515/jmc-2016-0030, S2CID  33121117
  7. ^ Бонех, Дэн; Франклин, Мэтью (2003), «Шифрование на основе идентификации с помощью спаривания Вейля», SIAM Journal on Computing , 32 (3): 586–615, doi :10.1137/S0097539701398521
  8. ^ Галиндо, Дэвид (2005), «Повторный взгляд на шифрование на основе идентичности Боне-Франклина», Автоматы, языки и программирование, Конспект лекций по информатике, т. 3580, стр. 791–802, doi : 10.1007/11523468_64, hdl : 2066/33216 , ISBN 978-3-540-27580-0, S2CID  605011
  9. ^ МакГрю, Дэвид А.; Виега, Джон (2004), «Безопасность и производительность режима Галуа/счетчика (GCM) операций», Progress in Cryptology - INDOCRYPT 2004 , Lecture Notes in Computer Science, т. 3348, стр. 343–355, doi :10.1007/978-3-540-30556-9_27, ISBN 978-3-540-24130-0
  10. ^ Ивата, Тетсу; Охаши, Кейсуке; Минемацу, Казухико (2012). «Взлом и восстановление доказательств безопасности GCM». Достижения в криптологии – CRYPTO 2012. Конспект лекций по информатике. Том 7417. С. 31–49. doi : 10.1007/978-3-642-32009-5_3 . ISBN 978-3-642-32008-8.
  11. ^ Ристенпарт, Томас; Рогауэй, Филлип (2007), «Как обогатить пространство сообщений шифра», Быстрое программное шифрование , Конспект лекций по информатике, т. 4593, стр. 101–118, doi : 10.1007/978-3-540-74619-5_7 , ISBN 978-3-540-74617-1
  12. ^ Нанди, Мридул (2014). «XLS не является сильной псевдослучайной перестановкой». Достижения в криптологии – ASIACRYPT 2014. Конспект лекций по информатике. Том 8874. С. 478–490. doi : 10.1007/978-3-662-45611-8_25 . ISBN 978-3-662-45607-1.
  13. ^ Белларе, Михир; Гаррей, Хуан А.; Рабин, Таль (1998). «Быстрая пакетная проверка для модульного возведения в степень и цифровых подписей». Достижения в криптологии — EUROCRYPT'98 . Конспект лекций по информатике. Том 1403. С. 236–250. doi : 10.1007/BFb0054130 . ISBN 978-3-540-64518-4.
  14. ^ Корон, Жан-Себастьян; Наккаш, Дэвид (1999), Криптография с открытым ключом , Lecture Notes in Computer Science, т. 1560, стр. 197–203, doi :10.1007/3-540-49162-7, ISBN 978-3-540-65644-9, S2CID  11711093
  15. ^ МакГрю, Дэвид А.; Флурер, Скотт Р. (2007), «Безопасность режима работы расширенной кодовой книги (XCB)», Избранные области криптографии , Конспект лекций по информатике, т. 4876, стр. 311–327, doi : 10.1007/978-3-540-77360-3_20 , ISBN 978-3-540-77359-7
  16. ^ Чакраборти, Дебруп; Эрнандес-Хименес, Висенте; Саркар, Палаш (2015), «Еще один взгляд на XCB», Криптография и связь , 7 (4): 439–468, doi :10.1007/s12095-015-0127-8, S2CID  17251595
  17. ^ Белларе, Михир; Рогауэй, Филлип (2006). «Безопасность тройного шифрования и структура для кодовых игровых доказательств». Достижения в криптологии — EUROCRYPT 2006. Конспект лекций по информатике. Том 4004. С. 409–426. doi : 10.1007/11761679_25 . ISBN 978-3-540-34546-6.
  18. ^ Gaži, Peter; Maurer, Ueli (2009). «Cascade Encryption Revisited». Advances in Cryptology – ASIACRYPT 2009. Lecture Notes in Computer Science. Vol. 5912. pp. 37–51. doi : 10.1007/978-3-642-10366-7_3 . ISBN 978-3-642-10365-0.
  19. ^ Корон, Жан-Себастьян (2002). «Оптимальные доказательства безопасности для PSS и других схем подписи». Достижения в криптологии — EUROCRYPT 2002. Конспект лекций по информатике. Том 2332. С. 272–287. doi : 10.1007/3-540-46035-7_18 . ISBN 978-3-540-43553-2.
  20. ^ Kakvi, Saqib A.; Kiltz, Eike (2012). «Оптимальные доказательства безопасности для полного доменного хэша, пересмотр». Advances in Cryptology – EUROCRYPT 2012. Lecture Notes in Computer Science. Vol. 7237. pp. 537–553. doi : 10.1007/978-3-642-29011-4_32 . ISBN 978-3-642-29010-7.
  21. ^ Coron, Jean-Sébastien; Patarin, Jacques; Seurin, Yannick (2008). «Модель случайного оракула и модель идеального шифра эквивалентны». Advances in Cryptology – CRYPTO 2008. Lecture Notes in Computer Science. Vol. 5157. pp. 1–20. doi : 10.1007/978-3-540-85174-5_1 . ISBN 978-3-540-85173-8.
  22. ^ Холенстейн, Томас; Кюнцлер, Робин; Тессаро, Стефано (2011), «Эквивалентность модели случайного оракула и модели идеального шифра, пересмотренный вариант», Труды сорок третьего ежегодного симпозиума ACM по теории вычислений , стр. 89–98, arXiv : 1011.1264 , doi : 10.1145/1993636.1993650, ISBN 9781450306911, S2CID  2960550{{citation}}: CS1 maint: дата и год ( ссылка )
  23. ^ Коблиц, Нил; Менезес, Альфред (2019). «Критические перспективы доказуемой безопасности: пятнадцать лет статей «Другой взгляд»». Успехи в области математики коммуникаций . 13 (4): 517–558. doi : 10.3934/amc.2019034 .
  24. ^ Все эти статьи доступны в разделе «Другой взгляд на доказуемую безопасность» . Получено 12 апреля 2018 г.
  25. ^ Голдрайх, Одед (2003). Основы криптографии . Издательство Кембриджского университета. ISBN 9780521791724.
  26. ^ Коблиц, Нил; Менезес, Альфред Дж. (2007), «Еще один взгляд на «доказуемую безопасность»", Журнал криптологии , 20 (1): 3–37, doi : 10.1007/s00145-005-0432-z , S2CID  7601573
  27. ^ ab "О постмодернистской криптографии" . Получено 12 апреля 2018 г. .
  28. ^ Коблиц, Нил (2007), «Непростые отношения между математикой и криптографией» (PDF) , Notices Amer. Math. Soc. , 54 (8): 972–979
  29. ^ ab "Письма в редакцию" (PDF) , Notices Amer. Math. Soc. , 54 (12): 1454–1455, 2007
  30. ^ ab "Письма в редакцию" (PDF) , Notices Amer. Math. Soc. , 55 (1): 6–7, 2008
  31. ^ Кац, Джонатан; Линделл, Йехуда (2008). Введение в современную криптографию . Chapman & Hall/CRC. ISBN 9781584885511.
  32. ^ Дамгард, И. (2007). ««Корректура» некоторых вопросов криптографии». Автоматы, языки и программирование . Конспект лекций по информатике. Том 4596. С. 2–11. doi :10.1007/978-3-540-73420-8_2. ISBN 978-3-540-73419-2. препринт {{cite book}}: Внешняя ссылка в |postscript=( помощь )CS1 maint: постскриптум ( ссылка )
  33. ^ "Shtetl-Optimized". scottaaronson.com . Сентябрь 2007 г.
  34. ^ Коблиц, Нил; Менезес, Альфред Дж. (2010), «Дивный новый мир безрассудных предположений в криптографии» (PDF) , Notices Amer. Math. Soc. , 57 : 357–365
  35. ^ "RSA Conference 2010 USA: The Cryptographers Panel". YouTube . Архивировано из оригинала 2021-12-22 . Получено 9 апреля 2018 г.
  36. ^ Рогауэй, Филлип. "Практически ориентированная доказуемая безопасность и социальное построение криптографии". Неопубликованное эссе, соответствующее приглашенному докладу на EUROCRYPT 2009. Препринт от 6 мая 2009 г. {{cite journal}}: Внешняя ссылка в |postscript=( помощь )CS1 maint: постскриптум ( ссылка )