Підписи Вінтерніца на Solana

На відміну від підписів RSA або ECDSA, які покладаються на математичні проблеми, такі як факторизація цілих чисел або дискретні логарифми — обидва вразливі до квантових атак, підписи Вінтерніца отримують свою безпеку виключно з односторонньої властивості криптографічних хеш-функцій.

Ця фундаментальна відмінність робить їх наріжним каменем постквантової криптографії.

Що таке підпис Вінтерніца

Одноразові підписи Вінтерніца (WOTS) еволюціонували з новаторської роботи Леслі Лампорта у 1970-х роках. Лампорт продемонстрував, що можна створювати цифрові підписи, використовуючи лише криптографічну хеш-функцію, без необхідності складних математичних припущень.

Оригінальна схема Лампорта підписувала один біт, використовуючи два секретні значення. Щоб підписати біт b, ви розкриваєте прообраз хеш-значення H₀ (якщо b=0) або H₁ (якщо b=1). Безпека повністю залежала від обчислювальної неможливості знаходження прообразів хешів: по суті, роботи у зворотному напрямку від виходу хешу для знаходження його входу.

Однак підписи Лампорта були надзвичайно неефективними. Підписання повідомлення n-bit вимагало 2n секретних значень і створювало підписи з 2n значень. Для повідомлення розміром 256 біт це означало управління 512 секретними значеннями та генерування підписів з 512 значень.

Роберт Вінтерніц зрозумів у 1990-х роках, що замість підписання окремих бітів у системі з основою 2, можна підписувати більші "цифри" у системах з вищими основами, такими як основа 16 або основа 256. Ця інновація різко зменшила розміри як ключа, так і підпису, зберігаючи ті самі гарантії безпеки.

Математичні основи

Параметр Вінтерніца та представлення основи

Ключовим параметром у підписах Вінтерніца є w, який визначає, як ми групуємо біти повідомлення:

• Основа: b = 2^w
• Діапазон цифр: Кожна цифра представляє w бітів і може мати значення від 0 до 2^w - 1

Поширені варіанти параметрів:

• w = 1: Кожна позиція представляє 1 біт (значення 0 або 1), еквівалентно підписам Лампорта в системі числення з основою 2
• w = 4: Кожна позиція представляє 4 біти (значення 0-15), представлення з основою 16
• w = 8: Кожна позиція представляє 8 бітів (значення 0-255), представлення з основою 256

Більші значення w створюють менші підписи, але вимагають більше обчислень для забезпечення безпеки. Цей компроміс є фундаментальним для розуміння характеристик продуктивності WOTS.

Хеш-ланцюги

Підписи Вінтерніца використовують хеш-ланцюги — послідовності повторних застосувань хеш-функції, починаючи з секретного значення: H⁰(s) = s, H¹(s) = H(s), H²(s) = H(H(s)), ..., Hⁱ(s) = H(H^(i-1)(s))

Властивість безпеки є асиметричною: маючи Hⁱ(s), обчислення будь-якого Hʲ(s), де j > i є легким (просто хешуйте j-i більше разів), але обчислення будь-якого Hʲ(s), де j < i є обчислювально неможливим, оскільки це вимагало б інвертування хеш-функції.

Механізм контрольної суми

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

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

Процес генерації ключа

Для довжини повідомлення n бітів з параметром Вінтерніца w:

1. Розрахунок довжини підпису: Спочатку визначте, скільки "фрагментів" вам знадобиться для представлення будь-якого повідомлення. Якщо ваші повідомлення мають довжину 256 бітів і ви обираєте параметр Вінтерніца w = 4, вам знадобиться загалом 64 фрагменти: l₁ = ⌈n/w⌉. Використовуючи формулу l₂ = ⌊log₂(l₁ × (2^w - 1))/w⌋ + 1 ми потім знаходимо, що для w = 4, де максимальна контрольна сума становить 960, l₂ = 3 і розмір підпису буде l = l₁ + l₂

Під час генерації ключа ви не знаєте, яким буде контрольна сума, оскільки ви ще не вибрали повідомлення для підпису, але все одно вам потрібні l₂ компоненти приватного ключа, зарезервовані для контрольної суми.

2. Створіть випадкові початкові точки: згенеруйте одне випадкове секретне значення для кожного хеш-ланцюжка, який вам знадобиться. Ці випадкові значення стають компонентами вашого приватного ключа. Розглядайте кожне з них як "початкову точку" окремого хеш-ланцюжка: sk = (sk₁, sk₂, ..., skₗ)

3. Для кожного компонента приватного ключа застосовуйте хеш-функцію повторно, доки не хешуєте його максимально можливу кількість разів (2^w - 1):pk = (H^(2^w-1)(sk₁), H^(2^w-1)(sk₂), ..., H^(2^w-1)(skₗ))

Процес підписання

Щоб підписати повідомлення M:

1. Перетворіть повідомлення на базове представлення: M → (m₁, m₂, ..., m_l₁) де кожен mᵢ ∈ [0, 2^w - 1]

2. Обчисліть контрольну суму: c = Σ((2^w - 1) - mᵢ) for i = 1 to l₁ і перетворіть c на базове представлення: c → (c₁, c₂, ..., c_l₂)

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

3. Згенеруйте підпис: де базове представлення вказує кількість разів, яку потрібно хешувати приватний ключ.

Процес перевірки

Щоб перевірити підпис σ на повідомленні M з публічним ключем pk:

1. Перерахуйте представлення повідомлення: M → (m₁, m₂, ..., m_l₁)

2. Перерахуйте контрольну суму: c = Σ((2^w - 1) - mᵢ) → (c₁, c₂, ..., c_l₂)

3. Для кожного компонента підпису хешуйте решту разів:

   • Для частин повідомлення: перевірте H^((2^w-1)-mᵢ)(σᵢ) = pkᵢ
   • Для частин контрольної суми: перевірте H^((2^w-1)-cⱼ)(σ_(l₁+j)) = pk_(l₁+j)

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

Security

Обмеження одноразового використання

Підписи Вінтерніца є одноразовими підписами (OTS): їх можна безпечно використовувати лише один раз для кожної пари ключів.

Атака працює наступним чином: коли ви підписуєте кілька повідомлень одним приватним ключем, ви розкриваєте проміжні значення у ваших хеш-ланцюгах.

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

Постквантова безпека

Підписи Вінтерніца отримують свою безпеку виключно з стійкості хеш-функцій до пошуку прообразу. Квантові комп'ютери не можуть ефективно інвертувати криптографічні хеш-функції, такі як SHA-256 або SHA-3, на відміну від квантових алгоритмів поліноміального часу (алгоритм Шора), які зламують RSA та ECDSA.

Використання SHA-256 з відповідними параметрами забезпечує 128 бітів постквантової безпеки, що робить ці підписи придатними для довгострокових криптографічних застосувань навіть у постквантовому світі.

Winternitz Signatures on Solana

Поточна криптографічна основа Solana повністю покладається на підписи Ed25519, які вразливі до квантових атак через алгоритм Шора.

Коли квантові комп'ютери стануть практичними, кожен гаманець, програмний авторитет і транзакція на Solana стануть підробленими.

Постквантову міграцію неможливо здійснити за одну ніч. Системи потрібно проєктувати вже сьогодні з урахуванням квантової стійкості, створюючи гібридні підходи, які працюють як у передквантовому, так і в постквантовому світах.

Хоча базовий рівень Solana залишається вразливим до квантових атак, розробники можуть створювати квантово-стійкі додатки поверх нього, використовуючи підписи Вінтерніца.