Advanced Encryption Standard

Advanced Encryption Standard (AES, „Подобрен стандарт за шифриране“) е стандарт за шифриране, приет през 2002 година от американския Национален институт за стандарти и технология. Към 2009 година това е един от най-широко използваните криптографски алгоритми. Стандартът включва приложение на алгоритъма Рейндал, разработен през 1998 година от белгийските криптографи Винсент Реймен и Жоан Дамен, като използва шифроващи ключове с три дължини: 128, 192 или 256 бита.

Дължината на шифриращия ключ определя броя повторения на криптирането, тоест броя трансформации необходими за превръщането на входа, наречен „plaintext“ (просто текст) , в изходния резултат наречен “ciphertext” (шифрован текст). За различните дължини на ключовете повторенията са:

10 цикъла за 128-битов ключ.
12 цикъла за 192-битов ключ.
14 цикъла за 256-битов ключ.

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

Байтовете на входното съобщение ("plaintext") се записват в матрица, най-често именована "state" ("статус", "положение"). Върху тази матрица се извършват криптиращите трансформациите на алгоритъма Рейндал.

Криптиращ алгоритъм (128-битова версия)

Криптиране с 128-битов ключ се реализира чрез следният алгоритъм:

PROCEDURE Cipher128(in[16]:byte, out[16]:byte, w[44]:word)
BEGIN
  state[4,4]:byte
  state = in
  AddRoundKey(state, w[0, 3])
  FOR round = 1 to 10
    SubBytes(state)
    ShiftRows(state)
    MixColumns(state)
    AddRoundKey(state, w[round*4, (round+1)*4-1])
  END FOR
  SubBytes(state)
  ShiftRows(state)
  AddRoundKey(state, w[40, 43])
  out = state
END PROCEDURE

Процедурата Key Expansion

Думите в масива w (key schedule) се генерират по следният начин:
//всяка дума се състои от 4 байта, пример: w[0] = 0f 15 71 c9
Първите четири думи (w[0] до w[3]) взимат стойността на криптиращия ключ. За да се изчисли w[i] се използват операции от Rijndael key schedule:

FOR i = 4 to 43
  temp = w[i-1] 
  IF i = 4, 8, 12, 16, ... , 40 THEN //кратно на 4
    Извършва се операция Rotate върху temp
    Всеки байт се изменя (използвайки процедурата SubBytes) 
    temp=temp XOR Rcon[i] // всеки байт от temp се събира побитово с константна стойност от Rcon  
  END IF
  w[i] = w[i-4] XOR temp 
END FOR

Процедурата SubBytes

При тази процедура, всeки байт от state се изменя по следния начин (Rijndael S-box):

FOR i=0 to 7 
  //промяна за всеки бит от даден байт на state
  B[i]= B[i] XOR B[(i+4) MOD 8] XOR B[(i+5) MOD 8] XOR B[(i+6) MOD 8] XOR B[(i+7) MOD 8] + C[i] 
  //C = 63 hex. 
END FOR

Процедурата ShiftRows

Тази процедура променя редовете на state матрицата. Най-горният ред остава непроменен, байтовете на следващия се преместват с една позиция наляво, на по-долния с две позиции, а на последния байтовете се изместват с три позиции наляво.

Процедурата MixColumns

Колоните на state матрицата се разбъркват по следния начин:
B[0,c] =2 * B[0,c] XOR 3 * B[1,c] XOR B[2,c] XOR B[3,c] B[1,c] = B[0,c] XOR 2 * B[1,c] XOR 3 * B[2,c] XOR B[3,c] B[2,c] = B[0,c] XOR B[1,c] XOR 2 * B[2,c] XOR 3 * B[3,c] B[3,c] = 3 * B[0,c] XOR B[1,c] XOR B[2,c] XOR 2 * B[3,c]

Процедурата AddRoundKey

Извършва се XOR между четирите колони на state и четири 32-битови думи от key schedule.
B[0,c]=B[0,c] XOR w[k,c] B[1,c]=B[1,c] XOR w[k+1,c] B[2,c]=B[2,c] XOR w[k+2,c] B[3,c]=B[3,c] XOR w[k+3,c]

Декриптиране

Декриптирането представлява извършване на криптиращите операции в обратен ред:

PROCEDURE InvCipher128 (in[16]:byte,out[16]:byte,w[44]:word)
BEGIN
  state[4,4]:byte
  state = in
  AddRoundKey(state, w[40, 43])
  FOR round = 9 downto 1
    InvShiftRows(state)
    InvSubBytes(state)
    AddRoundKey(state, w[round*3, (round+1)*3-1]) InvMixColumns(state)
  END FOR
  InvShiftRows(state)
  InvSubBytes(state)
  AddRoundKey(state, w[0, 3])
  out = state
END PROCEDURE

Всяка от Inv… функциите отговаря на обърната криптираща функция. Например InvMixColumns ще има следните преобразувания върху state:
B[0,c] = 0x0e * B[0,c] XOR 0x0b * B[1,c] XOR 0x0d * B[2,c] XOR 0x09 * B[3,c] B[1,c] = 0x09 * B[0,c] XOR 0x0e * B[1,c] XOR 0x0b * B[2,c] XOR 0x0d * B[3,c] B[2,c] = 0x0d * B[0,c] XOR 0x09 * B[1,c] XOR 0x0e * B[2,c] XOR 0x0b * B[3,c] B[3,c] = 0x0b * B[0,c] XOR 0x0d * B[1,c] XOR 0x09 * B[2,c] XOR 0x0e * B[3,c]

Примерна реализация на Java Script

/**
 * @source http://people.eku.edu/styere/Encrypt/JS-AES.html#subbytes
 */


// do encrytion
function aes_encrypt(message,crypt_key)
{
   var w = new Array( 44 );// subkey information
   var state = new Array( 16 );// working state
   var round;
   msg=get_value(message,true);
   key=get_value(crypt_key,false);
   // expand the key
   w = key_expand( key );
   state = transpose( msg );
   state = AddRoundKey(state, w, 0);

   for( round=1; round<10; round++ )
   {
      state = SubBytes(state, S_enc);
      state = ShiftRows(state);
      state = MixColumns(state);
      state = AddRoundKey(state, w, round*4*4);
   }
   SubBytes(state, S_enc);
   //accumulate_array( "After SubBytes", state );
   ShiftRows(state);
   //accumulate_array( "After ShiftRows", state );
   AddRoundKey(state, w, 10*4*4);
   //accumulate_array( "Output", state );

   // process output
   AES_output = transpose( state );
   return format_AES_output();
} 

//expand keys
function key_expand( key )
{
   var temp = new Array(4);
   var i, j;
   var w = new Array( 4*11 );

   for( i=0; i<16; i++ )
   {
      w[i] = key[i];
   }
   i = 4;
   while ( i < 44 )
   {
      for( j=0; j<4; j++ )
         temp[j] = w[(i-1)*4+j];
      if ( i % 4 == 0)
      {
         temp = RotWord( temp );
         temp = SubWord( temp );
         temp[0] ^= Rcon( i>>>2 );
      }

      // word = word ^ temp
      for( j=0; j<4; j++ )
         w[i*4+j] = w[(i-4)*4+j] ^ temp[j];
      i++;
   }
   return w;
}
// insert subkey information
function AddRoundKey( state, w, base )
{
   var col;
   for( col=0; col<4; col++ )
   {
      state[I(0,col)] ^= w[base+col*4];
      state[I(1,col)] ^= w[base+col*4+1];
      state[I(2,col)] ^= w[base+col*4+2];
      state[I(3,col)] ^= w[base+col*4+3];
   }
   return state;
}

// do S-Box substitution
function SubBytes(state, Sbox)
{
   var i;
   for( i=0; i<16; i++ )
      state[i] = Sbox[ state[i] ];
   return state;
}
...

Можете да видите целият код тук.

Сигурност

До май 2009 г., единствените успешни публикувани атаки срещу пълния AES базирани на информацията придобита от физическата реализация на криптографията срещу някои конкретни имплементации. Националната агенция за сигурност (NSA) разгледа всички финалисти за AES, включително Rijndael, и заяви, че всички от тях са достатъчно сигурни за правителствено некласифицирани данни на САЩ.През юни 2003 г. правителството на САЩ съобщи, че AES би могъл да се използва за защита на класифицирана информация:

Дизайнът и силата на всички ключови дължини на алгоритъма AES (т.е., 128, 192 и 256) са достатъчни за защита на класифицирана информация до ниво тайни. Строго секретната информация ще изисква използването на 192 или 256 дължина на ключа. Внедряването на AES в продукти, предназначени за защита на националните системи за сигурност и / или информация, трябва да бъде преразгледани и сертифицирани от NSA преди тяхното придобиване и използване.

AES има 10 цикъла за 128-битови ключове, 12 цикъла за 192-битови ключове, и 14 цикъла за 256--битови ключове. До 2006г., най-добрите познати атаки бяха върху 7 цъкъла на 128-битовите ключове, 8 цикъла за 192-битови ключове и 9 цикъла за 256-битови ключове.

Известни атаки

За криптографите, криптографската "пукнатина" е нещо по-бързо от грубата сила (brute force). Извършвайки един метод за декриптирането на всеки ключ (виж Криптоанализ).Това включва резултати, които са технически невъзможни при сегашната технология. Най-големямата публично известна brute force атака срещу всеки блок-шифър на криптиране е срещу 64-битовия RC5 ключ от distributed.net през 2006 година.

AES има доста прост алгебричен вид. През 2002 г., теоретична атака, наречена "XSL Атака", представена от Никола Куртоа и Йозеф Пйепзик, те искали да покажат слабост в алгоритъма на AES поради своя прост вид. След това, други документи показват, че атаката както е била първоначално представена е неприложима; (виж XSL атака срещу блок шифри).

По време на процеса AES, разработчиците на конкурентни алгоритми базирани на алгоритъма Рейндал, “... загрижени сме относно използването… в критични за сигурността приложения.” Въпреки това, през октомври 2000г. в края на избирателния процес за AES, Брус Шнайдер, разработчик на конкурентния алгоритъм Twofish, писа: “Не вярвам, че някой ще открие начин за разчитане на Рейндал трафика.”

На 1 юли 2009г., Брус Шнайдер пише за related-key attack върху 192-битовата и 256-битовата версия на AES, открити от Алекс Бирюков и Дмитри Ковратович, които манипулират донякъде простата AES ключова схема и има сложност от 2119. През декември 2009г. беше подобрен до 299.5. Това е продължението на атаката открита по рано през 2009г. от Алекс Бирюков, Дмитри Ковратович и Ивица Николич, със сложност от 296 за един от всички 235 ключа.

Друга атака за която Брус Шнайдер пише на 30 юли 2009г. излезна като предпечат на 3 август 2009г. Тази нова атака от Алекс Бирюков, Ор Дънкелман, Нейтън Келър, Дмитри Ковратович и Ади Шамир е срещу AES-256 която използва само два свързани ключа и 239 нужно време за откриването на пълния 256-битов ключ от версията с 9 цикъла, или 245 нужно време за версията с 10 цикъла със по силен вид на свързаният помощен ключ за атака, или 270 нужно време за версията с 11 цикъла. 256-битовия AES използва 14 цикъла, така че тези атаки всъщност не са много ефективни срещу пълния AES.

През ноември 2009г., първата отличителна атака срещу съкратената версия на AES-128 от 8 цикъла беше пусната като предпечат. Тази атака е подобрение на на отскока или започващи-от-средата атаки за сходните на AES премутации, които целят два последовалени кръга от пермутации на така нареченото приложение (Super-Sbox). То работи върху версията с 8 цикъла на AES-128, сложност от време 248 и паметна сложност от 232.

През юли 2010 Vincent Rijmen публикува иронична статия “chosen-key-relations-in-the-middle” атаки върху AES-128.

Първата key-recovery атаки върху пълния AES се дължи на Андрей Богданов, Дмитри Ковратович и Кристиян Рехбергер, и беше публикувана през 2011г. Атаката е базирана на bicliques и е по бърза от brute-force с коефициент от около 4. Нужни са 2126.1 операции за извлияането на AES-128 ключа. За AES-192 и AES-257, съответно 2189.7 и 2254.4 нужни операции.

Side-channel атаки

Side-channel атаките не атакуват основния шифър които не са свързани със сигурността на самия шифър, а по-скоро атакува реализацията на шифъра върху системи от които по невнимание изтича информация. Има няколко такива атаки върху конкретни имплементации на AES. През април 2005г. D.J. Bernstein обяви cache-timing атака която той използва за да “счупи” сървър използващ OpenSSL’s AES криптиране. Атаката изисквала 200 милиона избрани обикноевни текстове. Този сървър е бил проектиран да осигурява колкото се може повече информация за времето (сървърът изпраща обратно броя на машинните цикли взети от криптиращата операция); все пак, както Bernstein отбелязва, “намалянето на прецизността на сървърните времеви отпечатъци, или елиминрането им от отговори от сървъра, не спира атаката: клиентът използвайки двупосочни тайиминги базирани на локалнo клокване, и компенсиране за увеличеният шум осреднявайки голям брой проби.

През октомври 2005г., Дъг Арн Освик, Ади Шамир и Еран Трумър представиха доклад демонстрирайки няклко cache-timing атаки срещу AES. Една атака беше в състояние да получи цял AES ключ след само 800 операции, за времето от 65 милисекунди. Тази атака изисква атакуващият да бъде способен да използва програми на същата система или платформа на която се използва AES.

Пез декември 2009г., Ендре Бангертер, Дейвид Гулаш и Стефан Крен публикуват доклад който описва практическоти подход за “near real time” получаване на тайните ключове от AES-128 без нуждата от шифрован текст или други текстове. Този подход също работи и върху AES-128 имплементации които използват компресирани таблици, като OpenSSL. Като някои по-ранни атаки, тази изисква възможността да се използва непривилегирован код на системата изпълняваща AES криптирането, което може да бъде постигнато с инфектирането със зловреден софтуер доста по лесно от придобиването на root акаунт.

Производителност

Високата скорост и ниските изисквания към RAM-та са критерии за процеса на подбор на AES. По такъв начин AES работи добре на голямо разнообразие от софтуер, от 8 битови смарт карти до високо-производителни компютри. На процесор Pentium Pro, AES криптиране изисква 18 електронни импулса на Централния процесор, което е еквивалентно на производителност на 11 MiB/сек за процесор 200MHz. За сравнение на процесор Pentium M 1.7 GHz производителността му е около 60 MiB/сек. На процесорите Intel Core i3/i5/i7 поддържат AES - NI (AES – New Instructions), с разширен набор от инструкции, чиято производителност може да бъде над 700 MiB/ сек на всяка нишка.

Тестови вектори

В информатиката и инженерството тестовите вектори са набор от въведени данни с цел проверка на системата. Тест векторите са поредица от известни шифри за даден код и ключ. Националния институт за стандарти и технологии разпределя компетенцията на AES тест векторите катоAES Known Answer Test (KAT) Vectors (in ZIP format).

Инструменти за криптиране

http://aes.online-domain-tools.com/
http://www.tools4noobs.com/online_tools/encrypt/
http://www.bierkandt.org/encryption/symmetric_encryption.php

Източници

^[1]

↑ http://people.eku.edu/styere/Encrypt/JS-AES.html#subbytes

Шаблон:Математика-мъниче

Тази страница частично или изцяло представлява превод на страницата Advanced Encryption Standard в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[1] ttp://people.eku.edu/styere/Encrypt/JS-AES.html#subbytes

[1]