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

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

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

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

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

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

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

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

Споры

Некоторые исследователи обнаружили математические ошибки в доказательствах, которые использовались для заявлений о безопасности важных протоколов. В следующем частичном списке таких исследователей за их именами следует сначала ссылка на исходную статью с предполагаемым доказательством, а затем ссылка на статью, в которой исследователи сообщили о недостатках: V. Shoup;[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 Conference 2010 Cryptographers Panel.[35]

Доказуемая безопасность, ориентированная на практику

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

Рекомендации

  1. ^ Белларе, Михир; Rogaway, Филипп (1995), «Оптимальное асимметричное шифрование», Достижения в криптологии - Eurocrypt '94, Конспект лекций по информатике, 950: 92–111, Дои:10.1007 / BFb0053428, ISBN  978-3-540-60176-0
  2. ^ Шоуп, Виктор (2002), «Пересмотр ОАЭП», Журнал криптологии, 15 (4): 223–249, Дои:10.1007 / s00145-002-0133-9
  3. ^ Кравчик, Хьюго (2005), «HMQV: высокопроизводительный безопасный протокол Диффи-Хеллмана», Достижения в криптологии - Crypto 2005, Конспект лекций по информатике, 3621: 546–566, Дои:10.1007/11535218_33, ISBN  978-3-540-28114-6
  4. ^ Менезес, Альфред Дж. (2007), «Другой взгляд на HMQV», Журнал математической криптологии, 1: 47–64, Дои:10.1515 / JMC.2007.004
  5. ^ Белларе, Михир; Петрзак, Кшиштоф; Rogaway, Phillip, "Улучшенный анализ безопасности для MAC CBC", Достижения в криптологии - Crypto 2005: 527–545, Дои:10.1007/11535218_32; и Петрзак, Кшиштоф (2006), «Тесная граница для EMAC», Автоматы, языки и программирование. Часть II - ICALP 2006, Конспект лекций по информатике, 4052: 168–179, Дои:10.1007/11787006_15, ISBN  978-3-540-35907-4
  6. ^ Джа, Ашвин; Нанди, Мридул (2016), «Пересмотр структурных графов: приложения к CBC-MAC и EMAC», Журнал математической криптологии, 10 (3–4): 157–180, Дои:10.1515 / jmc-2016-0030
  7. ^ Бонех, Дэн; Франклин, Мэтью (2003), «Шифрование на основе личности из пары Вейля», SIAM Журнал по вычислениям, 32 (3): 586–615, Дои:10.1137 / S0097539701398521
  8. ^ Галиндо, Дэвид (2005), «Возвращение к шифрованию на основе идентичности Боне-Франклина», Автоматы, языки и программирование - ICALP 2005, Конспект лекций по информатике, 3580: 791–802, Дои:10.1007/11523468_64, ISBN  978-3-540-27580-0
  9. ^ МакГрю, Дэвид А .; Вьега, Джон (2004), «Безопасность и производительность режима Галуа / счетчика (GCM)», Прогресс в криптологии - Indocrypt 2004, Конспект лекций по информатике, 3348: 343–355, Дои:10.1007/978-3-540-30556-9_27, ISBN  978-3-540-24130-0
  10. ^ Ивата, Тецу; Охаши, Кейсуке; Minematsu, Kazuhiko (2012), "Взлом и восстановление доказательств безопасности GCM", Достижения в криптологии - Crypto 2012, Конспект лекций по информатике, 7417: 31–49, Дои:10.1007/978-3-642-32009-5_3, ISBN  978-3-642-32008-8
  11. ^ Ристенпарт, Томас; Rogaway, Phillip (2007), «Как обогатить пространство сообщений шифра», Быстрое программное шифрование - FSE 2007, Конспект лекций по информатике, 4593: 101–118, Дои:10.1007/978-3-540-74619-5_7, ISBN  978-3-540-74617-1
  12. ^ Нанди, Мридул (2014), «XLS не является сильной псевдослучайной перестановкой», Достижения в криптологии - Asiacrypt 2014, Конспект лекций по информатике, 8874: 478–490, Дои:10.1007/978-3-662-45611-8_25, ISBN  978-3-662-45607-1
  13. ^ Белларе, Михир; Garray, Juan A .; Рабин, Таль (1998), «Быстрая проверка пакетов для модульного возведения в степень и цифровых подписей», Достижения в криптологии - Eurocrypt '98, Конспект лекций по информатике, 1403: 236–250, Дои:10.1007 / BFb0054130, ISBN  978-3-540-64518-4
  14. ^ Корон, Жан-Себастьен; Наккаш, Дэвид (1999), "О безопасности проверки RSA", Криптография с открытым ключом - PKC '99, Конспект лекций по информатике, 1560: 197–203, Дои:10.1007/3-540-49162-7, ISBN  978-3-540-65644-9
  15. ^ МакГрю, Дэвид А .; Флюрер, Скотт Р. (2007), "Безопасность режима работы расширенной кодовой книги (XCB)", Избранные области криптографии - SAC 2007, Конспект лекций по информатике, 4876: 311–327, Дои:10.1007/978-3-540-77360-3_20, ISBN  978-3-540-77359-7
  16. ^ Чакраборти, Дебруп; Эрнандес-Хименес, Висенте; Саркар, Палаш (2015), «Еще один взгляд на XCB», Криптография и коммуникации, 7 (4): 439–468, Дои:10.1007 / s12095-015-0127-8
  17. ^ Белларе, Михир; Rogaway, Phillip, "Безопасность тройного шифрования и структура для основанных на коде игровых доказательств", Достижения в криптологии - Eurocrypt 2006: 409–426, Дои:10.1007/11761679_25
  18. ^ Гажи, Петр; Маурер, Ули (2009 г.), «Новый взгляд на каскадное шифрование», Достижения в криптологии - Asiacrypt 2009, Конспект лекций по информатике, 5912: 37–51, Дои:10.1007/978-3-642-10366-7_3, ISBN  978-3-642-10365-0
  19. ^ Корон, Жан-Себастьян (2002), «Оптимальные доказательства безопасности для PSS и других схем подписи», Достижения в криптологии - Eurocrypt 2002, Конспект лекций по информатике, 2332: 272–287, Дои:10.1007/3-540-46035-7_18, ISBN  978-3-540-43553-2
  20. ^ Какви, Сакиб А .; Килтц, Эйке (2012 г.), «Оптимальные доказательства безопасности для полного хэша домена, еще раз», Достижения в криптологии - Eurocrypt 2012, Конспект лекций по информатике, 7237: 537–553, Дои:10.1007/978-3-642-29011-4_32, ISBN  978-3-642-29010-7
  21. ^ Корон, Жан-Себастьен; Патарен, Жак; Сёрин, Янник (2008), «Модель случайного оракула и модель идеального шифра эквивалентны», Достижения в криптологии - Crypto 2008, Конспект лекций по информатике, 5157: 1–20, Дои:10.1007/978-3-540-85174-5_1, ISBN  978-3-540-85173-8
  22. ^ Холенштейн, Томас; Кюнцлер, Робин; Тессаро, Стефано (2011 г.), «Повторение эквивалентности модели случайного оракула и идеальной модели шифра», STOC '11 Материалы 43-го ежегодного симпозиума ACM по теории вычислений: 89–98, arXiv:1011.1264, Дои:10.1145/1993636.1993650, ISBN  9781450306911
  23. ^ «Критические взгляды на доказуемую безопасность: пятнадцать лет публикаций« Другой взгляд »». Успехи в математике коммуникации. 13: 517–558. 2019. Дои:10.3934 / amc.2019034.
  24. ^ Все эти документы доступны на «Еще один взгляд на доказуемую безопасность». Получено 12 апреля 2018.
  25. ^ Гольдрайх, Одед (2003). Основы криптографии. Издательство Кембриджского университета. ISBN  9780521791724.
  26. ^ Коблиц, Нил; Менезес, Альфред Дж. (2007), «Другой взгляд на» доказуемую безопасность"", Журнал криптологии, 20 (1): 3–37, Дои:10.1007 / s00145-005-0432-z
  27. ^ а б «О постмодернистской криптографии». Получено 12 апреля 2018.
  28. ^ Коблиц, Нил (2007), «Непростые отношения между математикой и криптографией» (PDF), Замечает амер. Математика. Soc., 54 (8): 972–979
  29. ^ а б «Письма в редакцию» (PDF), Замечает амер. Математика. Soc., 54 (12): 1454–1455, 2007
  30. ^ а б «Письма в редакцию» (PDF), Замечает амер. Математика. Soc., 55 (1): 6–7, 2008
  31. ^ Кац, Джонатан; Линделл, Иегуда (2008). Введение в современную криптографию. Чепмен и Холл / CRC. ISBN  9781584885511.
  32. ^ Дамгард, И. (2007). «Корректура» некоторых вопросов криптографии ». Автоматы, языки и программирование, 34-й международный коллоквиум, ICALP 2007, Вроцлав, Польша, 9–13 июля 2007 г. Труды. LNCS. 4596: 2–11. Дои:10.1007/978-3-540-73420-8_2. ISBN  978-3-540-73419-2. препринт
  33. ^ «Штетл-Оптимизированный». scottaaronson.com.
  34. ^ Коблиц, Нил; Менезес, Альфред Дж. (2010), «Дивный новый мир дерзких предположений в криптографии» (PDF), Замечает амер. Математика. Soc., 57: 357–365
  35. ^ "Конференция RSA 2010 США: Группа криптографов". Получено 9 апреля 2018.
  36. ^ Рогавей, Филипп. "Обеспечиваемая безопасность, ориентированная на практику и социальное построение криптографии". Неопубликованное эссе, соответствующее приглашенному докладу на EUROCRYPT 2009. 6 мая 2009 г.препринт