Минуле і майбутнє нашої безпеки: від дверного замка до кредитної картки

Що станеться з самою концепцією приватних даних, коли квантові комп'ютери зроблять шифрування безглуздим?

Технології можуть загрожувати нашій безпеці? У сучасному суспільстві ризику це ні для кого вже не новина. Але технології також і фундамент цієї безпеки. І це серйозно: наше суспільство без них просто немислимо. І ось тонкий баланс цих двох сторін технологій і визначає наше життя, надаючи нам інструментарій як для того, щоб убезпечити себе, так і для того, щоб загрожувати іншим. У цій статті я постараюся показати, як працює цей ансамбль, на прикладі двох найбільш знайомих нам артефактів безпеки - кредитної картки і дверного замка.

Почну з пояснення «магії» безпеки сучасної електронної комерції. Далі пройду крізь дивовижну історію створення і злому «абсолютно безпечного замку» в Англії два століття тому. А потім повернуся в наші дні і розгляну, що з себе зараз представляють схожі ризики, такі як «закон Мура» або квантовий комп'ютер, для сучасної електронної безпеки. Зрештою, порівнюючи ці ризики з історією злому «досконалого» дверного замка, я спробую показати які загрози, але також і можливості надає нам майбутній розвиток обчислювальної техніки.

Безтурботні фокуси е-комерції

Оплата покупок карткою по інтернету чимось нагадує картковий фокус. Не тільки тим, що ми, прості обивателі, ніяк не можемо зрозуміти, як же насправді влаштовані обидва цих явища, - в інтернет-оплатах і карткових фокусах ще й дуже схожий принцип роботи. Всього в три кроки. Слідкуйте уважно. Спочатку ви витягуєте будь-яку карту з колоди або вводите за запитом продавця дані свого рахунку. Потім ховаєте вибрану карту від фокусника або шифруєте введені дані у себе на комп'ютері (останнє, насправді, ви робите не самі - це відбувається автоматично). І ось у результаті деяких «магічних» трюків - вуаля! - фокусник знову знаходить цю карту, тільки у себе. А в разі інтернет оплати - за допомогою математичних алгоритмів продавець прочитує шифр і дізнається дані вашого рахунку для оплати. Така ось математична магія. Французький математик XVII століття П "єр Ферма. На його Малій теоремі (і, зокрема, методі розкладання на множники непарного цілого числа n) працює сучасний алгоритм RSA в шифруванні «відкритого ключа». Більше про «математичну магію» можна прочитати тут: https://math.berkeley.edu/~frenkel/RSA.pdf.

Але якщо продавцю, як заправському фокуснику, це було так легко зробити, чому тоді якась третя зловмисна сторона не може теж декодувати ваш шифр, тим самим отримавши доступ до ваших засобів на рахунку? Вся справа в спеціальних математичних процедурах шифрування «відкритим ключем».

На початку інтернет-покупки кожен покупець отримує від продавця якийсь публічний ключ, з яким він може зашифрувати дані свого рахунку для здійснення оплати. Для простоти представимо цей ключ у вигляді товстого телефонного довідника. Для шифрування якогось повідомлення (скажімо «ВІЗА») все, що нам потрібно, це почергово зайти на перші сторінки довідника з літерами В, І, З, А і виписати там перші зазначені телефонні номери прізвищ на В (Васильєв - 04599), І (Іванов - 03577), З (Зінов'єв - 09384), А (Антонов - 05398). В результаті виходить якийсь довгий цифровий шифр (04599035770938405398), який представляє наше конфіденційне слово ВІЗА. Те ж саме при інтернет-оплаті робить спочатку і наш комп'ютер з даними рахунку за допомогою публічного ключа. В обох випадках виходить якийсь набір символів, набагато довший, ніж початкове повідомлення. Його ми і відправляємо продавцю.

Звичайно, зловмисники можуть перехопити наше повідомлення, більше того вони можуть мати навіть той же телефонний довідник (публічний ключ), так як він надається продавцем абсолютно відкрито. Але що вони робитимуть з цим довідником? Адже інформація в ньому відсортована за прізвищами, у нас же в шифрі стоять вже телефонні номери. Виходить, для того, щоб дізнатися кожен зашифрований символ, зловмисникам потрібно буде перелистувати цілий довідник у пошуках збігу потрібного номера. Це дуже багато роботи. У конкретних цифрах: злом одного публічного ключа, що складається з 155-символів, займає в одного суперкомп'ютера або 290 персональних комп'ютерів, об'єднаних через інтернет, близько 4 місяців. І така довжина для публічного ключа далеко не межа. Так що вигідніше вже зламувати замки в офлайні.

Але що ж робить продавець? Як він може швидко і без зусиль прочитати наш складний шифр? Для цього у нього є інший - закритий - ключ або, користуючись нашою метафорою, особливий довідник, складений з пронумерованих особливим чином телефонних номерів. За допомогою такого довідника зовсім нескладно знайти потрібні символи, що стоять за нашим кодом. В результаті за допомогою свого закритого ключа продавець отримує наші дані для оплати. І фокус відбувся.

Виходить, що інтернет повністю безпечне місце для торгівлі? Не зовсім. Зловмисники можуть вас обдурити не безпосередньо, а підстерегти ще на вашому комп'ютері при введенні незашифрованих даних рахунку, або роздобути їх, прикинувшись чесними продавцями. Так що варто завжди бути напоготові. Але, загалом-то, так, інтернет таки досить безпечне місце для торгівлі. Не будь він таким, теперішня електронна комерція так не процвітала б.

Так, що там е-комерція! Практично весь публічний обмін інформацією по інтернету - від відсилання листа до встановлення надійного зв'язку з веб-сервером - побудований на технології «відкритого ключа». По суті, вона є технологічним гарантом безпеки в такому дикому рі як сучасна глобальна мережа. І ми не раз на день безтурботно передаємо свої дані в руки «відкритого ключа», навіть не віддаючи собі в цьому звіт. І правда, адже що може трапитися?

Замок, який змінив світ

Безтурботності, з якою ми посилаємо і зберігаємо свої найбільш конфіденційні дані, наші предки могли б тільки позаздрити. І це не дивно, адже довгий час словосполучення «безпечний замок» було буквально оксюмороном - як «теплий лід».

Самі замки були винайдені досить давно, більше 4 тисяч років тому, в Месопотамії, коли місцеві жителі перейшли до осілості, і у великих поселеннях виникла нудність населення разом з приватною власністю і майновим розшаруванням. Словом, це була технологічна відповідь на потребу багатих жителів ховати своє (награбоване) майно від бідних. Просто тому, що зберігати це все під давніми засовами і щеколдами було небезпечно. Але й замкові конструкції Месопотамії були досить нехитрими. Зазвичай, якийсь ключ з потрібним виступом-борідкою піддівав замковий механізм і тим самим відкривав замок.

Римляни трохи ускладнили механізм: використовували в замку замість дерева метал і застосували в конструкції борідки різноманітні форми, щоб замковий механізм піддівався саме конкретним ключем з потрібною формою борідки. У такому вигляді основний механізм проіснував усе Середньовіччя і зберігся до кінця XVIII століття. А разом з ним збереглися і всі його недоліки. Схема механізму стародавнього замку. Такі застосовувалися 4 тисячі років тому в Месопотамії.

Було кілька основних способів зламати замок на «бородочному» механізмі. Перший і найпростіший - це просто купити зв'язку вживаних ключів. Справа в тому, що навіть після ускладнення римлянами форми борідок вони не відрізнялися особливою різноманітністю. Крім того, самі ремісники, що виготовляли широко затребувані замки, намагалися спростити собі життя і робили за раз однакові партії замкових механізмів. Результат - очевидний. Відповідною зв'язкою з двох десятків старих ключів можна було відкрити практично кожні двері в будь-якому англійському місті XVIII століття.

Але навіть якщо на шляху зловмисників вставала рідкісна незвичайна форма борідки, замок завжди можна було зламати іншим способом. Вставити в нього болванку ключа, попередньо оброблену воском, і під натиском дати замковому механізму пропечататися на ньому. За відбитком робився потрібний ключ - і справа в капелюсі!

Найважливіша структурна проблема безпеки полягала в самих замкових майстрах. Знання конструкції того чи іншого замкового механізму було покрито практично магічною таємницею. І не дивно: адже воно давало необмежену можливість для злому. Тому, звертаючись до того чи іншого замкових справ майстру потрібно було мати не тільки гроші, але і довіру. Адже майстру не потрібно навіть самому зламувати ваші двері, він міг просто розповісти кому потрібно, як працює ваш замковий механізм, і на наступний день ви вже були пограбованим. Відкриває замок за допомогою ключа з боріддям.

І ось у такій ситуації принципової небезпеки наприкінці 18 століття виявляється раннє індустріальне англійське суспільство. Ситуація досить гаряча. Оскільки з одного боку завдяки інтенсивному фабричному капіталістичному розвитку виділяється заможний шар буржуа, зацікавлений у безпеці для себе і свого майна. Але з іншого боку внаслідок тих же процесів велика частина країни скочується в жебрацтво і серед жебраків є чимало таких, що зацікавлені в добре заможних сусідів. Між 1750-ми і 1790-ми роками статистики неухильно реєструють збільшення числа пограбувань, буржуазна преса б'є в набат. Не дивно, що коли на сцені в кінці століття з'являється обдарований молодий інженер Джозеф Брама зі своїм «абсолютно безпечним замком», громадськість сприймає його як спасителя.

Підхід Брами був дійсно оригінальним. Замість звичайного ключа з борідкою, що піддягає замковий механізм, він запропонував повністю нову на той час схему - тумблерний замок. Ідея полягала в тому, щоб дозволити привести в дію замковий механізм тільки в тому випадку, коли спеціальні тумблери-анджелелківці, заховані в глибині замка будуть правильно затиснуті ключем. Виходить, що хоч і ключ від замку Брами нагадував свого «бородатого» попередника хитромудрою формою, він не міг просто піддіти і відкрити замковий механізм так само, як «бородач». Відкривання могло відбутися тільки в тому випадку, якщо форма ключа підійшла до тумблерів, інакше замковий механізм залишався заблокованим від будь-яких піддягань. Патентна схема тумблерного замку Брами.

Застосування в замку тумблерів значно збільшувало можливість комбінацій (у запатентованому Брама замку було 18 тумблерів, що давало 470 мільйонів можливих комбінацій) і само собою розв'язувало проблему однакових ключів. Але, крім того, з тумблерним принципом також усувалася загроза з боку виробника замку. Замковий механізм був настільки складним і давав так багато комбінацій, що простого ремісничого секрету з піддягання замку правильною борідкою вже не було достатньо. Ти або маєш потрібний ключ, або ні. Усе це дозволило Брамі стати піонером фабричного виготовлення стандартизованих замків. Індивідуальні замовлення ремісникам, яким ти містично довіряєш таємницю свого будинку, відійшли в минуле. Замість цього прийшло масове серійне виробництво, що забезпечувало споживачеві анонімність і безпеку за прийнятну ціну.

Сказати, що винахід Брами був важливим для буржуазного суспільства ранньоіндустріальної Британії, - не сказати нічого. Воно було плоть від плоті самого цього суспільства. Воно дозволяло британській буржуазії нарешті реалізувати ті сподівання про безпеку та ізольованість від натовпу, які вона вже виношувала, щонайменше, півстоліття. За вхідними дверима в будинок пішли всілякі замки і замочки для шаф, шкатулок і кімнат. Замок підкреслював приватну сферу і виступав її гарантом. А винахід Брами став чимось типу національного надбання георгіанської та вікторіанської Британії. Сам інженер був настільки впевнений у своєму винаході, що після його патентування публічно описав принцип дії механізму замку. Більш того, через кілька років він створив спеціальну демонстраційну колодку на своєму замку і виклав її у себе перед будинком, пропонуючи 200 гінею (або близько 20 тис. фунтів за нинішнім курсом) всякому, хто зможе зламати його. Багато хто намагався, але ніхто не міг. Той самий замок, за злом якого було обіцяно 200 гіней.

За замком Брами на початку XIX століття послідували й інші конструкції замків на оступелювачах. Один з найбільш примітних з них - детекторний замок Чабба, який блокувався при спробі його зламати. Саме цей замок демонструвався на Всесвітній промисловій виставці в Лондоні 1851 року, коли її відвідав тоді ще нікому не відомий американець Альфред Хоббс.

Хоббс був агентом з продажу замків однієї нью-йоркської компанії і основним методом продажів для нього був злом замків конкурентів. Що він успішно і зробив із замком Чабба - той був зламаний ним за півгодини. Як так вийшло? Справа в тому, що Хоббс зовсім по-іншому підійшов до справи злому. Він не став, як його попередники до нескінченності підбирати потрібний ключ або пробувати якось піддіти замковий механізм. Замість цього Хоббс придумав один простий, але абсолютно новий на той час інструмент - відмичку. Вона складалася з двох частин. Одна частина відмички дозволяла йому швидко і акуратно розібратися у внутрішній будові замку і затиснути потрібні тумблери. І тільки після того, як це зроблено, в справу вступала інша частина відмички, яка як простий важіль повертала знятий з блокування замковий механізм.

Так почався Великий Замковий Розгром (The Great Lock Debacle) 1851 року, як його тоді охрестила преса. Раптово виявилося, що вся та безпека, якій вже близько 60 років хизувалася Британія, практично нічого не варта в руках одного американця. Але буржуазна громадськість просто так не здалася. Надії були кинуті на абсолютно безпечний замок Брами, який, як і раніше, невзламаним стояв біля дверей будинку свого вже покійного творця. І Хоббс прийняв цей виклик.

Йому було дано 30 днів на злом і безперешкодний доступ до замку. Демонстраційний замок Брами з 18 тумблерами хоч і не був забезпечений функцією заклинювання як детекторний замок Чабба, але мав структуру істотно складніше. Тому Хоббсу не вдалося його зламати ні за півгодини, ні за годину і ні за день. Але прокорпівши над замком 51 годину чистого часу протягом 16 днів Хоббс все-таки вивідав його слабкість за допомогою відмичок і, зрештою, зламав його. А після цього він вже за десятки хвилин зламував його ще й ще для демонстрації скептичній публіці. Це був розгром. Розгром не тільки британської національної гідності, але й ідеї «досконалої безпеки», за якою могла ховатися від соціальних лих індустріалізації буржуазія.

Але найцікавіше в цій ситуації в тому, що конструкція механічних замків відтоді не сильно змінилася. І ми досі користуємося тим самим базовим тумблерним принципом, який винайшов Джозеф Брама. Тому не дивно, що в інтернеті можна наткнутися на безліч відео про побутові способи швидкого злому замків. Як і наприкінці XVIII століття, наші замки не більше ніж порожній символ фізичної безпеки.

Загрози завтрашнього дня

Але чи варто боятися схильності наших механічних замків злому? Адже сьогодні, як і в першій половині XIX століття, ми живемо в прекрасну епоху досконалої безпекової техніки. Просто, місце невзламуваного пристрою безпеки у нас тепер займає електронний «відкритий ключ», а не механічний тумблерний замок. Наші гроші, особисте листування та інші конфіденційні дані вже давно знаходяться на його піклуванні. А обладнавши їм ще й наше житло, ми могли б убезпечити і безпосередньо себе фізично.

Але перш, ніж ви серйозно задумаєтеся про встановлення на дверях електронного замка (який теж має масу підводних каменів), я б хотів звернути вашу увагу на дещо інше. А саме на відносність всякої «досконалої безпеки», яку ми як урок можемо винести з історії Великого Замкового Разгрому. Як і в середині XIX століття, ми просто маємо справу з певним співвідношенням протиборчих технологій захисту і злому. І зараз їх стан такий, що електронний ключ забезпечує нам практично повну безпеку, якщо ми самі будемо досить обережними і не видамо злодіям свою інформацію якимось іншим способом. Але наскільки довго проіснує такий стан речей? Це відкрите питання.

Перший і найбільш явний виклик «відкритому ключу» кидає широко відомий «закон Мура». Він діє досі з середини 1960-х: обчислювальні потужності подвоюються приблизно кожні 18 місяців. А це означає, повертаючись до нашої метафори, що зловмисник може все швидше переглядати той же телефонний довідник для вираховування нашого повідомлення, зашифрованого по ньому. І 4 місяці, потрібні на обчислення суперкомп'ютером «відкритого ключа» з 155 символів, через якихось півтора року перетворяться на 2 місяці. Потім в один місяць і так далі.

Звичайно, цей темп достатньо черепашок, щоб представляти собою негайну загрозу для електронної комерції. Але все ж така динаміка змушує корпорацію RSA Security, яка розробляє найбільш поширений з «відкритих ключів», RSA, говорити про необхідність подовження своїх ключів. За їх словами, 1024-бітні RSA-ключі, які тепер повсюдно використовуються, давно вже можуть бути принципово вирахованими. Отже, варто переходити на більш надійні 2048-бітні ключі. Потрібно відзначити, що оцінки з приводу можливості вираховування ключів певною мірою розходяться, і деякі експерти більш спокійні в прогнозах, говорячи про 2015 - 2020 роки як про можливий діапазон розкриття 1024-бітного ключа. Але всі вони при цьому сходяться в одному: технічний прогрес обчислювальної техніки вимагає поступового подовження «відкритих ключів».

На щастя, на загрозу все більш швидкого пролистування довідника можна відповісти все більш товстими його виданнями. Так, збільшення публічної частини відкритого ключа в 2 рази означатиме для його пересічних користувачів збільшення зусиль на шифрування послання десь в 3,5 рази, а на дешифрування - в 7 разів. Але, благо, ресурси - спасибі «закону Мура» - для цього є. А ось потенційним зловмисникам тут не позаздриш. Збільшення ключа в два рази (наприклад, з 1024 на 2048 біта) означатиме ускладнення вираховування зашифрованої інформації по ньому в 232 рази. Тобто замість перегляду одного телефонного довідника потрібна буде обробка немислимої їх бібліотеки більш ніж з 4 мільярдів томів (для порівняння, найбільші бібліотеки в світі мають книжкові фонди не більше ніж у 150 млн. примірників). Звичайно, «закон Мура», завдяки експоненційному зростанню, зміг би забезпечити переробку і такої громади інформації. Але для цього потрібен час. Тому якщо він і далі буде діяти як зараз, то перші обчислення 2048-бітного коду зможуть з'явитися тільки з 2045 року, а то і з 2050.Лов Кумар Гровер.

Тож від простого вираховування потрібної комбінації ключа ми, як і буржуа вікторіанської Британії, нехай і тимчасово, але надійно захищені. Появі більш потужних комп'ютерів або більш спритних зломщиків ми завжди можемо протиставити збільшення бітів коду або тумблерів замку. Але що якщо і у нас знайдеться така людина, як Хоббс, який переверне всю систему злому вгору ногами і замість довгого підбору потрібної комбінації, запропонує набагато більш швидкий і витончений підхід? В принципі, така людина вже з'явилася. Його звуть Лов Кумар Гровер.

У 1996 році він, тоді ще мало кому відомий індійсько-американський математик і дослідник в Bell Labs, запропонував абсолютно новий підхід до вирішення завдання перебору, так званий квантовий алгоритм Гровера. Такий алгоритм повноцінно можна здійснити тільки на квантовому комп'ютері. І ось тут починається справжнісінька магія. На відміну від звичайного комп'ютера, де біт інформації може приймати значення або 0, або 1, кубіти квантового комп'ютера засновані на ефектах квантової невизначеності, відразу мають значення і 0, і 1. Або іншими словами вони перебувають у стані суперпозиції. Але тільки до тих пір, поки їх не будуть вимірювати. Як тільки це станеться, кубіт довільно прийме одне з двох значень - 0 або 1 - і суперпозиція зникне.

Користуючись цим принципом, наш зловмисник, замість того, щоб самому за допомогою звичайного комп'ютера перебирати всі можливі комбінації перехопленого шифра в сторінках довідника, може створити особливого квантового читача. Цей читач, перебуваючи в стані квантової суперпозиції, читатиме всі сторінки одночасно. Проблема, однак, полягає в тому, що як тільки зловмисник зробить такому квантовому читачеві запит, читач видасть йому довільний ключ, який з вкрай малою ймовірністю буде підходити для дешифрування повідомлення. Алгоритм Гровера ж дозволяє вирішити цю проблему. Завдяки математично особливим квантовим запитам до читача він ніби зрушує його відповіді все більш близько до шуканого значення. В результаті, після порівняно невеликого числа повторень таких операцій (за O (^ N) кроків, в той час як простий перебір вимагав би O (N) кроків) відповіді квантового читача після прямих звернень до нього стануть настільки близькими до шуканої величини, що їх можна буде прийняти з великою ймовірністю за цю величину. На практиці це означає, що квантовий комп'ютер з алгоритмом Гровера може вирахувати шифр «відкритого ключа» за той самий час, що знадобитися звичайному комп'ютеру для шифрування повідомлення тим самим «відкритим ключем».

Єдине, що рятує нас від повного розкриття всіх наших секретів вже тут і зараз - від умовного Великого Криптографічного Розгрому - це те, що досить потужний квантовий комп'ютер для злому існуючих відкритих ключів ще не розроблений. Але прогрес у цій сфері рухається швидко. Не так давно, в 2012 році, алгоритм Гровера був впер "