CBC-MAC

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

Для обчислення CBC-MAC повідомлення ${\displaystyle m}$ користувач шифрує ${\displaystyle m}$ в режимі CBC з нульовим ініціалізаційним вектором. Наступне зображення є нарисом обчислення CBC-MAC повідомлення з блоків ${\displaystyle m_{1}\|m_{2}\|\cdots \|m_{x},}$ секретним ключем ${\displaystyle k}$ і PRP ${\displaystyle F:K\times X\to X}$ (блочним шифром):

Отримуємо PRF ${\displaystyle F_{CBC}:K\times X^{\leq L}\to X.}$

Безпека з повідомленнями встановленої і змінної довжини

Якщо використовний блочний шифр безпечний (тобто є псевдовипадковою переставкою), тоді CBC-MAC безпечний для повідомлень встановленого розміру.[1] Однак, не є безпечним для повідомлень змінної довжини. Отже, кожен окремий ключ треба використовувати для повідомлень встановленої і відомої довжини. Нападник, який знає правильну пару повідомлення-тег (тобто CBC-MAC) ${\displaystyle (m,}$ ${\displaystyle t)}$ і ${\displaystyle (m',}$ ${\displaystyle t')}$ може утворити третє повідомлення ${\displaystyle m''}$ чий CBC-MAC також буде ${\displaystyle t'}$. Це робиться простим XOR-енням першого блоку ${\displaystyle m'}$ з ${\displaystyle t}$ і тоді приєднанням ${\displaystyle m'}$ до ${\displaystyle m}$; тобто через утворення ${\displaystyle m''=m\|[(m_{1}'\oplus t)\|m_{2}'\|\dots \|m_{x}']}$.

Цю проблему не можна розв'язати через додавання блоку з розміром повідомлення наприкінці. Існує три головних способи зміни CBC-MAC так, щоб убезпечити його для повідомлень змінної довжини[1]^:33:

• Додавання довжини повідомлення в перший блок (англ. length-prepend CBC MAC). Це може бути проблематичним якщо довжина повідомлення не відома, коли почалось опрацювання.
• Використання різних ключів для повідомлень різних довжин (англ. input-length key separation).
• ECBC-MAC, XCBC-MAC.

Також, для захисту цілісності повідомлень змінної довжини, можна розглянути інші режими, наприклад, CMAC (фактично різновид XCBC-MAC) або HMAC.

ECBC-MAC

XCBC-MAC

${\displaystyle pad(b)={\begin{cases}b,&{\mbox{if }}|b|=n\\b10...0,&{\mbox{if }}|b|<n\end{cases}}}$

Переваги

• Робить найменшу кількість викликів блочного шифру для MAC такого типу
• Правильно обробляє повідомлення будь-якої довжини
• Блочний шифр викликається лише з одним ключем: ${\displaystyle k_{1}}$
• Блочний шифр викликається лише в напрямку шифрування
• Дозволяє обробку по ходу
• Легкий у втіленні, знайомий користувачам
• Вільний
• XCBC — це PRF (не тільки MAC)

  – Безпечна PRF завжди є MAC

  – Не використовується нонс/IV

  – Тегі коротші

  – Тегі можна обрізати

  – Інші застосування

  • Розділення ключа

  • PRG

  • Протоколи квитування (підтвердження) зв'язку

• Доведеннєво безпечний (припускаючи, що E є PRP)

Вади

• Обмежені можливості розпаралелювання (притаманно CBC-MAC)
• Довжина ключа ${\displaystyle k+2n}$

Порівняння різновидів CBC-MAC [2][3]

Ім'я	Домен	#E викликів	#E ключів	Довжина ключа	#E викликів до обробки
CBC-MAC	${\displaystyle (\{0,1\}^{n})^{m}}$	${\displaystyle |M|/n}$	${\displaystyle 1}$	${\displaystyle k}$	0
EMAC	${\displaystyle \{0,1\}^{*}}$	${\displaystyle 1+{\mathcal {d}}(|M|+1)/n{\mathcal {e}}}$	${\displaystyle 2}$	${\displaystyle 2k}$	0
RMAC	${\displaystyle \{0,1\}^{*}}$	${\displaystyle 1+{\mathcal {d}}(|M|+1)/n{\mathcal {e}}}$	${\displaystyle 1+\#M}$	${\displaystyle 2k}$	0
XCBC	${\displaystyle \{0,1\}^{*}}$	${\displaystyle 1+{\mathcal {d}}|M|/n{\mathcal {e}}}$	${\displaystyle 1}$	${\displaystyle k+2n}$	0
TMAC	${\displaystyle \{0,1\}^{*}}$	${\displaystyle 1+{\mathcal {d}}|M|/n{\mathcal {e}}}$	${\displaystyle 1}$	${\displaystyle k+n}$	0
XCBC+kst	${\displaystyle \{0,1\}^{*}}$	${\displaystyle 1+{\mathcal {d}}|M|/n{\mathcal {e}}}$	${\displaystyle 2}$	${\displaystyle k}$	3 або 4
TMAC+kst	${\displaystyle \{0,1\}^{*}}$	${\displaystyle 1+{\mathcal {d}}|M|/n{\mathcal {e}}}$	${\displaystyle 2}$	${\displaystyle k}$	2 або 3
OMAC	${\displaystyle \{0,1\}^{*}}$	${\displaystyle 1+{\mathcal {d}}|M|/n{\mathcal {e}}}$	${\displaystyle 1}$	${\displaystyle k}$	1

«#E викликів до обробки» — позначає кількість викликів блочного шифру в попередньому опрацюванні. Ці виклики можна робити без повідомлення. Для XCBC+kst і TMAC+kst за блочний шифр припускаємо AES.

kst — техніка розділення ключів (англ. key separation technique).

Примітки

1. M. Bellare, J. Kilian and P. Rogaway. The security of the cipher block chaining message authentication code. [Архівовано 5 лютий 2012 у Wayback Machine.] JCSS 61(3):362-399, 2000.
2. Kaoru Kurosawa, Tetsu Iwata. Two-key CBC MAC [Архівовано 9 травня 2012 у Wayback Machine.] стор. 3, 2002
3. Fast Software Encryption: 10th International Workshop, FSE 2003, Lund, Sweden, February 24-26, 2003 : Revised Papers, Том 10, стор. 143

Посилання

• XCBC: Версія CBC MAC для опрацювання повідомлень довільної довжини [Архівовано 4 червня 2011 у Wayback Machine.] на сайті NIST. (англ.)