C, PHP, VB, .NET

Дневникът на Филип Петров


* Блокови шифри – режими на работа

Публикувано на 31 март 2018 в раздел ОСУП.

Ще се спрем на един проблем свързан с криптирането на информация. Той е свързан с това, че ако използваме един и същи ключ за криптиране върху една и съща информация, при една и съща трансформация, винаги ще получаваме един и същи краен резултат – криптирана поредица от битове. Когато се извършва пренос на информация в интернет, ние имаме чести повторения на части от страници и дори цели страници. Това би могло да послужи като вид информация за това какво точно преглеждаме в даден момент от време.

Блоковите шифри са най-разпространения начин за криптиране на информация, която ще се пренася през интернет. Идеята при тях e поредицата от данни, които ще се криптират, да се „нацепи“ на малки парченца – блокове – и всеки един от тях да се криптира поотделно. Така става възможно отсрещната страна – която получава криптираната информация – да започне процеса на декриптиране още преди да е получила всички блокове. Това пести време и прави работата значително по-бърза. За някои услуги като например телефонни разговори, видеоконферентни връзки, онлайн радио и телевизия, т.н., където реално няма определен край на потока от данни, това е и единствен начин. Проблемът тук е, че както казахме, при един и същи детерминистичен алгоритъм за криптиране можем да имаме доста голямо количество от повторения на криптирани блокове (криптираните блоковете ще наричаме „шифри“).

За да се справим с този проблем се въвеждат допълнителни модификации като разширение на алгоритмите за криптиране. Ще ги наричаме „режими на работа“. Целта им е два блока с идентично съдържание ще бъдат криптирани по различен начин.

Режим ECB – да не се използва!

Нека първо покажем, че казаното в предишните параграфи е реален проблем. Electronic CodeBook е най-простият режим на работа и при него няма модификация на алгоритъма. Следва се стандартната схема на криптиране и декриптиране:

  • Криптиране: блокi -> алгоритъм_криптиране(блокi, ключ) -> шифърi
  • Декриптиране: шифърi -> алгоритъм_декриптиране(шифърi, ключ) -> блокi

Преди започване на процеса на криптиране, текстът (поредицата, която ще се криптира) трябва да бъде разширена до точно определен размер – общата големина трябва да е кратна на големината на един блок. За целта се извършва т.нар. „padding“ (добавят се празни символи).

Предимството на този режим е свързано с бързината на криптиране и декриптиране. Ако притежаваме няколко блока едновременно, няма проблем те да бъдат крипитрани/декриптирани паралелно, защото не зависят по никакъв начин един от друг. Освен това изгубването на битове информация в даден блок не повреждат другите блокове. Тоест ако имаме загуба на информация, незасегнатите блокове ще могат да бъдат декриптирани.

За да покажем защо този вид блоково криптиране в общия случай е неудачно, ще покажем един пример с криптиране на монохромна картинка. Нека вземем това лого на футболен клуб Славия:

Криптираме го и добавяме BMP хедър в началото на файла:

# openssl enc -aes-256-ecb -in slavia.bmp -out slaviaecb.bmp
enter aes-256-ecb encryption password: ******
Verifying - enter aes-256-ecb encryption password: ******
# dd if=slavia.bmp of=slaviaecb.bmp bs=1 count=54 conv=notrunc

Ако отворите криптирания файл с графичен редактор, ще има неприятна изненада:

Няма да можем да възстановим файла в оригиналния му вид само имайки криптираната му версия (без да притежаваме ключа), но получената информация все пак е значителна. Поради тази причина използването на режим ECB е крайно непрепоръчително във всички случаи. Не използвайте ECB никога!

Режим CTR

При режим Counter, или още Segment Integer Counter, се използва подобрение, с което се разрешава споменатия проблем. Идеята е ключа да не е един и същи, а да се променя с всеки следващ блок. Избираме си някой произволен и уникален (никога неизползван за криптиране на други блокове) текстови низ, който ще наречем nonce (number used once). Този nonce ще бъде изпращан заедно със криптираното съобщение – той не е секретен. Към него долепяме число от брояч, който ще наречем counter и е с първоначална стойност 1. Криптираме nonce+counter с ключа (който е таен!) и към резултата прилагаме операция XOR с първия блок, който искаме да криптираме. Продължаваме да правим същото за всеки следващ блок, като просто увеличаваме стойностите на counter.

  • Криптиране:
    • блок1 -> алгоритъм_криптиране(nonce+1, ключ) XOR блок1 -> шифър1
    • блокi -> алгоритъм_криптиране(nonce+i, ключ) XOR блокi -> шифърi
  • Декриптиране:
    • шифър1 -> алгоритъм_криптиране(nonce+1, ключ) XOR шифър1 -> блок1
    • шифърi -> алгоритъм_криптиране(nonce+i, ключ) XOR шифърi -> блокi

Тук използваме операция XOR, която има следните важни за нас свойства:

  • A XOR B = B XOR A;
  • (A XOR B) XOR C = A XOR (B XOR C);
  • A XOR 0 = A;
  • A XOR B XOR B = A.

Именно последните две свойства ни помага да кажем, че ако „блок XOR ключ = шифър“, то „шифър XOR ключ = блок“! В случая под „ключ“ се има предвид резултата от прилагането на алгоритъма за криптиране, както е показано по-горе. Целта е чрез употребата на брояча да се получават коренно различни шифри при криптирането на всеки следващ блок. Забележете, че използваме напълно идентичен алгоритъм и при криптиране, и при декриптиране – това е потениално различно спрямо режим ECB.

Криптирането и декриптирането в режим CTR могат да бъдат извършени в различни нишки, защото всички блокове се криптират независимо един от друг. Ето как ще изглежда нашето примерно изображение когато се криптира в режим CTR:

# openssl enc -aes-256-ctr -in slavia.bmp -out slaviactr.bmp
enter aes-256-ctr encryption password: ******
Verifying - enter aes-256-ctr encryption password: ******
# dd if=slavia.bmp of=slaviactr.bmp bs=1 count=54 conv=notrunc

Както виждате резултатът е напълно задоволителен. Ако променяте паролата, ще виждате леки промени по разположението на точките и промяна в цветовете им.

CTR е един от най-популярните режими за криптиране и причината за това е неговата паралелизация. Единственият му недостатък е свързан с реалната нужда от това един и същи nonce да не бъде употребяван за криптиране на две различни поредици с един и същи секретен ключ. Ако направим това, поредиците реално ще бъдат криптирани по един и същи начин, понеже и ключовете, и nonce, и counter ще съвпадат. Така ако в двете поредици имаме повторение на блокове (с един и същи номер!), техните шифри ще са идентични. Затова отношението към генерирането на nonce трябва да е отговорно и той да бъде генериран като произволна поредица от битове с максимално голяма ентропия – така ще сме сигурни, че възможността за повторение на nonce е сведена до минимум.

В този режим не се изисква padding – просто при последния блок се прави XOR докъдето стигат битовете. Ако бъдат загубени/променени битове от информация, засегнат остава само текущия блок.

Режим CBC

Идеята на режим Cipher-Block Chaining е всеки блок да зависи от съдържанието на предишния. За целта върху шифъра на блок (i+1) се прилага операция XOR с шифъра на блок (i). Само за първия блок пък се прави XOR с втори ключ, който се нарича „инициализиращ вектор“ (IV). Инициализиращият вектор реално изпълнява ролята на nonce от предишния пример с режим CTR (за режим CTR някои автори определят комбинацията от nonce и counter като IV). Аналогично на nonce, IV също не е таен, а се предава заедно с криптираното съобщение.

  • Криптиране:
    • блок1 -> алгоритъм_криптиране(блок1, ключ) XOR IV -> шифър1
    • блокi+1 -> алгоритъм_криптиране(блокi+1, ключ) XOR шифърi -> шифърi+1
  • Декриптиране:
    • шифър1 -> алгоритъм_декриптиране(шифър1, ключ) XOR IV -> блок1
    • шифърi+1 -> алгоритъм_декриптиране(шифърi+1, ключ) XOR шифърi -> блокi+1

По този начин обаче алгоритъмът за криптиране стана линеен – няма как да криптирате даден блок без преди това да сте криптирали неговия предишен. При процесът на декриптиране няма проблем с разпаралеляването, защото вие имате налични шифрите, с които се прави XOR. Ето картинката в CBC режим:

# openssl enc -aes-256-cbc -in slavia.bmp -out slaviacbc.bmp
enter aes-256-cbc encryption password: ******
Verifying - enter aes-256-cbc encryption password: ******
# dd if=slavia.bmp of=slaviacbc.bmp bs=1 count=54 conv=notrunc

Ако се изгубят битове информация, остават засегнати блока, в който са загубени битовете, и неговия следващ. Останалите блокове могат да бъдат възстановени. В режим CBC е задължително да се прави padding и това се счита за недостатък. Ако един единствен бит се инвертира, целият текущ блок се променя и се сменя един бит в следващия блок.

Изискването за уникалност на IV не е чак толкова строго, колкото го представихме за CTR, но въпреки това е важно да е максимално произволно (с добра ентропия), за да не се повтаря. Понеже всеки блок зависи от неговия предходен, поредиците, които криптираме, доста бързо започват коренно да се различават една от друга (още при наличието на първи различен бит), и дори да използваме едни и същи ключ и IV само еднаквите първи блокове ще могат да бъдат идентифицирани, но не и следващи.

CBC има един съществен недостатък. Проблемът е следният: ако два различни шифъра – например ci и cj – са идентични, тогава е вярно за техните блокове mi и mj, че:

 ci-1 XOR mi = cj-1 XOR mj => ci-1 XOR cj-1 = mi XOR mj

Това не е достатъчно само по себе си за намиране на mi или mj, но ако атакуващият знае съдържанието на едно от двете – например mi, – то той вече би могъл да намери другото, защото:

 mj = ci-1 XOR cj-1 XOR mi

Представете си например, че атакуващият анализира HTTPS трафик. Той знае, че съобщенията обикновено започват с „GET /index.php HTTP/1.1 Cookie=…“, тоест той може да каже, че знае некриптирания текст зад тези първи блокове. От тук насетне той се интересува да търси колизии на шифрираните блокове на които знае съдържанието със следващи шифрирани блокове. С достатъчно голям трафик, той евентуално може да натрупа достатъчно колизии, от които да декриптира поне част от секрет в съобщението. Например при шифри като 3DES и Blowfish, които използват 64 битови блокове е нужна поредица около 2^32 шифрирани блока, за да се получи колизия, а това не е много. В миналото при протоколите SSL 2.0, 3.0 и TLS 1.0, 1.1 са позволявали такива блокови шифри и съответно са атакуеми. С мониторинг на няколко стотици гигабайти трафик атаката става практична. Повече информация за нея може да намерите на https://sweet32.info. При AES се използва 128 битов блок, което прави атаката непрактична – нужният трафик е прекалено огромен.

Друго важно нещо свързано със CBC е, че е важно IV да е непредвидим. Ако IV е предвидим, това би направило CBC атакуем чрез т.нар. „chosen plaintext attacks“. При тях атакуващият не само знае шифрите и инициализиращите вектори, но самия той може да изпраща съобщения за шифриране. За повече информация вижте тук: https://defuse.ca/cbcmodeiv.htm. При TLS 1.0 и всички версии на SSL при CBC за IV на всяко следващо съобщение се е използвал последния шифър на предишното, което ги е правило предвидими.

Поради изложените проблеми в TLS 1.3 се приема, че CBC няма да се използва.

Режим PCBC

Propagating Cipher-Block Chaining е много близък до CBC, но с една разлика – той прави XOR не само с шифъра от предишния блок, но и със самия блок. Тоест:

  • Криптиране:
    • блок1 -> алгоритъм_криптиране(блок1, ключ) XOR IV -> шифър1
    • блокi+1 -> алгоритъм_криптиране(блокi+1, ключ) XOR шифърi XOR блокi > шифърi+1
  • Декриптиране:
    • шифър1 -> алгоритъм_декриптиране(шифър1, ключ) XOR IV -> блок1
    • шифърi+1 -> алгоритъм_декриптиране(шифърi+1, ключ) XOR шифърi XOR блокi -> блокi+1

Практическата разлика между CBC и PCBC е свързана с това, че изгубването на дори един бит информация води до невъзможност за декриптиране на цялата поредица от текущия блок нататък. Освен това не само процеса на криптиране е линеен, а също и процеса на декриптиране – вече не е възможно да декриптиране блок преди да сте декриптирали неговия предишен. Има интересен ефект, че ако два блока си разменят местата, те няма да могат да се декриптират, но това не засяга останалите във веригата.

Този режим на работа се използва много рядко. Няма да можем да покажем демонстрация с картинката, защото OpenSSL не поддържа този режим за AES (не е трудно да се направи, но тъй или иначе картинката ще бъде просто шум подобен на горния).

Режим CFB

Cipher Feedback e много близък с CBC. Единственото предимство при него спрямо CBC е, че не е нужно да се прави padding на съобщението, което се криптира – подобно на CTR, при последния блок се прави XOR докъдето стигнат битовете. При този режим на всяка стъпка се криптира не текущия, а предишния блок.

  • Криптиране:
    • блок1 -> алгоритъм_криптиране(IV, ключ) XOR блок1 -> шифър1
    • блокi+1 -> алгоритъм_криптиране(шифърi, ключ) XOR блокi+1 -> шифърi+1
  • Декриптиране:
    • шифър1 -> алгоритъм_криптиране(IV, ключ) XOR шифър1 -> блок1
    • шифърi+1 -> алгоритъм_криптиране(шифърi, ключ) XOR шифърi+1 -> блокi+1

Забележете, че този път не можем да имаме разлики между алгоритъма за криптиране и алгоритъма за декриптиране – те са един и същи алгоритъм и трябва да извършват работата си по идентичен начин. Криптирането е еднонишково, а декриптирането може да се разпаралелява. Изгубването на бит с информация прави текущия и всички следващи блокове невалидни.

Ето как би изглеждала картинката при CFB алгоритъм:

# openssl enc -aes-256-cfb -in slavia.bmp -out slaviapcfb.bmp
enter aes-256-cfb encryption password: ******
Verifying - enter aes-256-cfb encryption password: ******
# dd if=slavia.bmp of=slaviacfb.bmp bs=1 count=54 conv=notrunc

Режим OFB

Output Feedback режима е още една бихме казали не много популярна модификация. Подобна е на CFB, но при криптиране/декриптиране вместо XOR с предишния блок/шифър се прави XOR с текущия. Също няма нужда от padding. Ето как изглежда формалния запис:

  • Криптиране:
    • K1 = алгоритъм_криптиране(IV, ключ)
    • Ki+1 = алгоритъм_криптиране(Ki, ключ)
    • блок1 -> K1 XOR блок1 -> шифър1
    • блокi -> Ki XOR блокi -> шифърi
  • Декриптиране:
    • K1 = алгоритъм_криптиране(IV, ключ)
    • Ki+1 = алгоритъм_криптиране(Ki, ключ)
    • шифър1 -> K1 XOR шифър1 -> блок1
    • шифърi -> Ki XOR шифърi -> блокi

Единственото предимство спрямо CFB е, че при загуба на битове се губи само текущия блок/шифър. Поради тази причина е практически възможно да се направи по-лесно допълнителен „error correction“ и съответно да стане възможно възстановяването на информация. Както криптирането, така и декриптирането са еднонишкови – разпаралеляване е невъзможно. Отново наблягаме, че алгоритъма за криптиране и декриптиране са идентични. Недостатък при този режим е, че при повторение на IV се получават едни и същи блокове – изключително рядка ситуация ако се спазват строго правилата за генериране на IV (произволност с голяма ентропия).

Ето как изглежда картинката в OFB режим:

Заключение

Независимо кой режим използвате, винаги спазвайте правилото, че IV/nounce трябва да е произволна поредица с максимална ентропия.

Никога не използвайте режим ECB.

Колкото до другите, не може да се каже, че някой от тях е по-сигурен от останалите. В последните години спада използването на режим CBC (който беше най-популярния в миналото), защото при него има допълнително изискване за „непредсказуемост“, което другите нямат. Въпреки това ако спазвате правилата за генериране на IV, CBC е напълно сигурен режим. Другият проблем – с колизиите на шифри – не е сериозен при шифриране на неголеми обеми от информация и особено при алгоритми като AES, които са с 128 битови блокове, но въпреки това е недостатък. Друга причина за избягване на CBC/PCBC спрямо CTR, CFB и OFB e нуждата от padding на съобщението.

Колкото до правилата за IV, те са следните:

  • Винаги произволен;
  • Непредсказуем (тоест произволността да е с добра ентропия);
  • Не е тайна и не се разчита, че е тайна – само ключа е таен.

Имайте предвид, че тези режими гарантират конфиденциалност, но не и интегритет на данните! Ако се предава информация, която може да бъде злонамерено променяна по време на преноса, товя я прави уязвима на атаки като например bit flippering (подмяна на бит). Затова само криптирането не е достатъчно – трябва да се добавя и удостоверяване за интегритет, например чрез употреба на Message Authentication Code (MAC).

Следната таблица прави сравнение на алгоритмите:

 

 

Алгоритъм Паралелно
криптиране 
Паралелно
декриптиране
Padding Загуба на информация от блок засяга…
CTR Да Да Не Само текущия блок
CBC Не Да Да Текущия и следващия блок
PCBC Не Не Да Текущия блок и всички следващи
CFB Не Да Не Текущия блок и всички следващи
OFB Не Не Не Само текущия блок

 



Добави коментар

Адресът на електронната поща няма да се публикува


*