RC6

RC6

Розробники	RSA Laboratories
Уперше оприлюднений	1998 р.
Раундів	20
Тип	Мережа Фейстеля

RC6 — симетричний блоковий криптографічний алгоритм, похідний від алгоритму RC5. Був створений Роном Рівестом, Меттом Робшау і Реєм Сіднеєм для задоволення вимог конкурсу Advanced Encryption Standard (AES). Алгоритм був одним з п'яти фіналістів конкурсу, був також представлений NESSIE і CRYPTREC. Є власницьким (пропрієтарним) алгоритмом, і запатентований RSA Security, одначе дія патентів сплила, і зараз алгоритм знаходиться у відкритому доступі. В той же час, "RC6" залишається зареєстрованою торговою маркою RSA.

Варіант шифру RC6, заявлений на конкурс AES, підтримує блоки довжиною 128 біт і ключі довжиною 128, 192 і 256 біт, але сам алгоритм, як і RC5, може бути налаштований для підтримки більш широкого діапазону довжин як блоків, так і ключів (від 0 до 2040 біт). RC6 дуже схожий на RC5 за своєю структурою і також досить простий у реалізації.

Є фіналістом AES, проте одна з примітивних операцій — операція множення, повільно виконується на певному обладнанні і ускладнює реалізацію шифру на ряді апаратних платформ і, що виявилося сюрпризом для авторів, на системах з архітектурою Intel IA-64 також реалізована досить погано. В даному випадку алгоритм втрачає одну зі своїх ключових переваг — високу швидкість виконання, що стало причиною для критики і однією з перепон для обрання як нового стандарту. Однак, на системах із процесором Pentium II, Pentium Pro, Pentium III, PowerPC та ARM алгоритм RC6 випереджає переможця — Rijndael.

Деталі RC6

Так само, як і RC5, RC6 — повністю параметризована сім'я алгоритмів шифрування. Для специфікації алгоритму з конкретними параметрами, прийнято позначення RC6-w/r/b, де

• W — довжина машинного слова в бітах.
• R — число раундів.
• B — довжина ключа в байтах. Можливі значення 0..255 байт.

Для того щоб відповідати вимогам AES, блочний шифр повинен працювати з 128-бітовими блоками. Так як RC5 — виключно швидкий блочний шифр, розширення його, щоб працювати з 128-бітовими блоками, привело б до використання двох 64-бітових робочих регістрів. Але архітектура і мови програмування ще не підтримують 64-бітні операції, тому довелося змінити проект так, щоб використовувати чотири 32-бітних регістри замість двох 64-бітних.

Розширення ключа

Генерація констант:

Так само, як і в RC5, в RC6 генерує дві псевдовипадкові величини, використовуючи дві математичні константи: експонента (e) і золотий перетин (f).

$~Q_{w}\leftarrow Odd((f-1)*2^{w})$

$~P_{w}\leftarrow Odd((e-2)*2^{w})$,

де $~Odd()$ — це округлення до найближчого непарного цілого. При w = 32 біта (у шістнадцятковому вигляді):

$~Q_{32}=9E3779B9$

$~P_{32}=B7E15163$

Процедура розширення ключа для RC6-w/r/b:

Таблиця ключів для шифру RC6 також ідентична таблиці шифру RC5. Відмінність полягає в тому, що більша кількість слів з масиву L отримано з наданого користувачем ключа для використання протягом шифрування і розшифровки.

Вхід:

• B-байтний ключ, заданий користувачем, попередньо перетворений в масив з $c$ слів $L[0,...,c-1]$.
• R — кількість раундів.

Вихід:

• W-бітна таблиця ключів $S[0,...,2r+3]$.

S[0] = Pw 
for i = 1 to 2r +3 do 
    S[i] = S[i-1] + Qw

A = B = i = j = 0

v = 3 * max {c, 2r +4} 
for s = 1 to v do 
    { 
        A = S[i] = (S[i] + A + B) <<< 3 
        B = L[j] = (L[j] + A + B) <<< (A + B) 
        i = (i +1) mod (2r +4) 
        j = (j +1) mod c 
    }

Шифрування і розшифрування

RC6 працює з чотирма w-бітними регістрами A, B, C і D, які містять вхідний вихідний текст і вихідний шифрований текст в результаті шифрування.

Шифрування / Розшифрування за допомогою RC6-w/r/b

Процедура шифрування:

Вхід:

• R кількість раундів
• W-розрядні ключі для кожного раунду S [0, …, 2r + 3]

Вихід:

• Шифрований текст зберігається в A, B, C і D

 
B = B + S[0] 
D = D + S[1] 
for i = 1 to r do 
{ 
t = (B (2B + 1)) <<< lg w 
u = (D (2D + 1)) <<< lg w 
A = ((A ⊕ t) <<< u) + S[2i] 
C = ((C ⊕ u) <<< t) + S[2i + 1] 
                (A, B, C, D) = (B, C, D, A)

} 
A = A + S[2r + 2] 
C = C + S[2r + 3]

Процедура розшифрування:

Вхід:

• Шифрований текст, збережений в A, B, C і D
• R кількість раундів
• W-розрядні ключі для кожного раунду S [0, …, 2r + 3]

Вихід:

• Вихідний текст зберігається в A, B, C і D

 
C = C - S[2r + 3] 
A = A - S[2r + 2]

for i = r downto 1 do 
{ 
(A, B, C, D) = (D, A, B, C) 
u = (D (2D + 1)) <<< lg w 
t = (B (2B + 1)) <<< lg w 
C = ((C - S[2i + 1]) >>> t) ⊕ u 
A = ((A - S[2i]) >>> u) ⊕ t 
} 
D = D - S[1] 
B = B - S[0]

Безпека

Варіант алгоритму RC6, який був заявлений на AES, як уже було сказано, підтримує блоки довжиною 128 біт і ключі довжиною 128, 192 і 256 біт, а також містить 20 раундів. Тобто RC6-128/20/b, де b = 128,192 або 256 біт. Щодо такого алгоритму ніяких атак не було виявлено. Були виявлені атаки тільки проти спрощених версій алгоритму, тобто алгоритму з зменшеною кількістю раундів.

Вважається, що найкращий варіант нападу на RC6, доступний для криптоаналітика, є повний перебір b-байтового ключа шифрування (або розширений ключовою масив S [0, …, 43], коли наданий користувачем ключ шифрування особливо довгий). Для повного перебору потрібно $min(2^{8b},2^{1408})$ операцій. Дон Копперсміт зауважив, що за рахунок значної пам'яті і попереднього обчислення можна організувати атаку «meet-in-the-middle», щоб відновити розширений ключовою масив S [0, …, 43]. Це вимагало б $2^{704}$ обчислень і таким чином необхідну кількість операцій дорівнювало $min(2^{8b},2^{704})$. Сучасніші атаки, такі як диференційний та лінійний криптоаналіз, здійсненні на версіях шифру з маленькою кількістю раундів, складно здійсненні для нападу на повний шифр RC6 з 20 раундами. Складність полягає в тому, що важко знайти хороші повторювані особливості або лінійні наближення, з якими могла б бути здійснена атака.

Цікава проблема — встановити відповідні цілі для безпеки проти цих сучасніших атак. Щоб досягти успіху, ці атаки типово вимагають великої кількості даних, і отримання $2^{a}$ блоків відомих або обраних пар зашифрованого \ відкритого тексту — завдання відмінне від спроби повернути один ключ з $2^{a}$ можливих. Варто зауважити, що з шифрами, що працюють зі швидкістю один терабіт в секунду (тобто, шифруючи дані зі швидкістю $10^{12}$ біт / сек), час, необхідний для 50 комп'ютерів, що працюють паралельно, щоб зашифрувати $2^{64}$ блоків даних, складає більше року; зашифрувати $2^{80}$ блоків даних — більше ніж 98 000 років, і зашифрувати $2^{128}$ блоків даних складає більше ніж $10^{19}$ років.

Хоча вимоги до даних для $2^{64}$ блоків для успішної атаки могли б бути розглянуті як достатні в практичних термінах, розробники прагнули забезпечувати набагато більший рівень безпеки.

Дослідження RC5 не проявили слабкостей в установці ключа. Це призвело до використання того ж процесу установки ключа і в RC6. Процес перетворення ключа, наданого користувачем, до таблиці ключів, здається, добре змодельований псевдовипадковий процес. Таким чином, у той час як немає доказів, що ніякі два ключі не призводять до однієї і тієї ж таблиці ключів, це, здається, дуже малоймовірно. Це можна оцінити як імовірність того, що існують два 256-бітових ключа, що призводять до однієї і тієї ж таблиці 44, 32-розрядних ключів, тобто приблизно $2^{2*256-44*32}=2^{-896}=10^{-270}$.

Ми можемо підсумувати наші вимоги на безпеці RC6 наступним чином:

— Найкраща атака на RC6 є повний перебір для забезпеченого користувачем ключа шифрування.

— Вимоги до даних, щоб організувати складніші атаки на RC6, такі як диференційний і лінійний криптоаналіз, перевищують доступні дані.

Важливим критерієм резерву безпеки є максимальне число раундів, при якому можлива атака. Це можливо для 12 -, 14 — і 15 — раундових варіантів RC6.

Шифр	Кількість раундів (b)	Тип атаки	Текст	Байти пам'яті	Операції
RC6-128/20/b	12	Статистичні відмінності	$2^{94}$	$2^{42}$	$2^{119}$
	14	Статистичні відмінності	$2^{118}$	$2^{112}$	$2^{122}$
	15 (256)	Статистичні відмінності	$2^{119}$	$2^{138}$	$2^{215}$

У четвертому стовпці «Текст» знаходиться інформація про кількість блоків незашифрованого і відповідних їм блокам зашифрованого тексту даними ключем. У п'ятому стовпці «Байти пам'яті» записано максимальна кількість байтів пам'яті, які потрібні в довільній точці здійснення атаки. У шостому стовпці «Операції» зазначено очікуване число операцій, які потрібно зробити для здійснення атаки.

Оцінка апаратних засобів

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

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

З 20 раундами на блок час шифрування приблизно дорівнює 100 наносекунд для кожного блоку, забезпечуючи передбачувану швидкість передачі даних приблизно 1.3 Гбіт / сек.

Виконання

Як випливає з опису алгоритму, RC6 — дуже компактний. Дійсно, реалізація алгоритму RC6 на Асемблері для мікропроцесора Intel Pentium Pro може бути здійснена в менш ніж 256 байтах коду для кожної з задач:

1. Установки ключа,
2. Блоку шифрування,
3. Блоку дешифрування.

На відміну від багатьох інших алгоритмів шифрування RC6 не використовує довідкові таблиці під час шифрування. Це означає, код RC6 і дані можуть міститися в сучасній кеш пам'яті і тим самим економити місце в пам'яті.

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

Гнучкість та напрямки розвитку

Як ми вже помітили, RC6 надає користувачеві велику гнучкість щодо розміру ключа шифрування, числа раундів і розміру слова основного обчислювального модуля.

У той час як RC6, представлений для розгляду на AES, базується на використання 32-розрядних слів (розмір блоку 128 біт), майбутня потреба ринку потребує розширення RC6 для інших розмірів блоку. Найбільшу важливість представляють розміри блоку в 256 біт, які використовували б розмір слова 64 біт і продуктивність, пропоновану наступним поколінням системної архітектури. Також зазначимо, що структура RC6 дозволяє експлуатувати певний ступінь паралелізму в підпрограмах розшифровки і шифрування. Наприклад, обчислення t і u в кожному раунді може бути обчислено паралельно, як і поновлення A і C. Оскільки процесори розвиваються в напрямку збільшення кількості внутрішнього паралелізму (наприклад, з переміщенням до суперскалярної архітектурі), реалізації RC6 повинні продемонструвати велику продуктивність.

Ліцензування

Оскільки RC6 не був обраний як AES, то немає гарантій, що його використання є вільним. З січня 2007 вебсторінка офіційного сайту RSA Laboratories, розробника RC6, містить наступне:

«We emphasize that if RC6 is selected for the AES, RSA Security will not require any licensing or royalty payments for products using the algorithm» ("Ми підкреслюємо, що якщо RC6 буде обраний як AES, то RSA Security не вимагатиме жодних ліцензійних чи авторських відрахувань за продукти, що використовують алгоритм").

Виділене слово «якщо» означає, що RSA Security Inc. тепер може вимагати ліцензійні та авторські платежі за будь-який продукт, який використовує алгоритм RC6. RC6 є запатентованим алгоритмом шифрування (U.S. Patent 5 724 428 і U.S. Patent 5 835 600).

Джерела

• R.L. Rivest, M.J.B. Robshaw, R.Sidney, and Y.L. Yin. ~ rivest/rc6.pdf The RC6 Block Cipher [Архівовано 2 грудня 2008 у Wayback Machine.]. v1.1, August 1998.
• J. Beuchat FPGA Implementations of the RC6 Block Cipher.

Посилання

• # RC6 SCAN's entry on RC6 [Архівовано 28 січня 2012 у WebCite]
• RSA Security's RC6 page
• Специфікація алгоритму RC6^{[недоступне посилання з лютого 2019]}