UMAC - UMAC

Bu maqola Kriptografiya bo'yicha mutaxassisning e'tiboriga muhtoj. Muayyan muammo: UMAC o'rtasidagi umumiy tushuncha va RFC 4418 UMAC algoritmi; Buni "MAC-da universal xeshlash" va "UMAC va do'stlar" ga bo'lish uchun kimdir kerak. Ga qarang munozara sahifasi tafsilotlar uchun. WikiProject kriptografiyasi mutaxassisni jalb qilishda yordam berishi mumkin. (2019 yil sentyabr)

Yilda kriptografiya, a asosida xabarni tasdiqlash kodi universal xeshlash, yoki UMAC, bir turi xabarni tasdiqlash kodi (MAC) xash funktsiyalari sinfidan qandaydir maxfiy (tasodifiy) jarayonga muvofiq xash funktsiyasini tanlashni va uni xabarga qo'llashni hisoblab chiqdi. Natijada olingan dayjest yoki barmoq izi ishlatilgan xash funktsiyasining identifikatorini yashirish uchun shifrlanadi. Har qanday MAC singari, u ikkalasini ham bir vaqtning o'zida tekshirish uchun ishlatilishi mumkin ma'lumotlar yaxlitligi va haqiqiyligi a xabar.

UMACning o'ziga xos turi, shuningdek, odatda oddiy deb nomlanadi UMAC, ko'rsatilgan RFC 4418, u tasdiqlanadigan kriptografik kuchga ega va odatda boshqa MAClarga qaraganda ancha kam intensiv hisoblanadi. UMAC dizayni 32-bitli arxitektura uchun optimallashtirilgan SIMD qo'llab-quvvatlash, har bir bayt uchun 1 CPU tsikli (cpb) bilan SIMD va 2 cbb bilan SIMD. 64-bitli arxitektura uchun optimallashtirilgan UMAC-ning yaqindan bog'liq varianti berilgan VMAC, loyiha sifatida IETFga taqdim etilgan (qoralama-krovetz-vmac-01) lekin hech qachon standartlashtirilgan RFCga aylanish uchun etarlicha e'tibor yig'ilmagan.

Fon

Umumjahon xeshlash

Aytaylik, xash funksiyasi H xashlash funktsiyalari sinfidan tanlangan bo'lib, u xabarlarni D formatiga qo'shadigan, mumkin bo'lgan xabar hazm qilishlar to'plami. Ushbu sinf deyiladi universal agar har qanday alohida xabarlar juftligi uchun ko'pi bilan | H | / | D | bo'lsa ularni D ning o'sha a'zosiga moslashtiradigan funktsiyalar.

Bu shuni anglatadiki, agar tajovuzkor bitta xabarni boshqasiga almashtirishni xohlasa va uning nuqtai nazari bo'yicha xash funktsiyasi butunlay tasodifiy tanlangan bo'lsa, UMAC uning modifikatsiyasini aniqlay olmaslik ehtimoli eng ko'p 1 / | D |

Ammo bu ta'rif etarlicha kuchli emas - agar mumkin bo'lgan xabarlar 0 va 1 bo'lsa, D = {0,1} va H identifikatsiya operatsiyasidan iborat emas, H universaldir. Ammo dayjest modulli qo'shilish bilan shifrlangan bo'lsa ham, tajovuzkor xabarni va dayjestni bir vaqtning o'zida o'zgartirishi mumkin va qabul qiluvchi farqni bilmaydi.

Kuchli universal xeshlash

Foydalanish uchun yaxshi bo'lgan H hash funktsiyalari sinfi tajovuzkor uchun to'g'ri hazm qilishni taxmin qilishni qiyinlashtiradi d soxta xabar f bitta xabarni ushlab turgandan so'ng a hazm qilish bilan v. Boshqa so'zlar bilan aytganda,

${ displaystyle Pr _ {h in H} [h (f) = d | h (a) = c] ,}$

juda kichik bo'lishi kerak, tercihen 1 / |D.|.

Qachonki xash funktsiyalari sinfini yaratish oson D. bu maydon. Masalan, agar |D.| bu asosiy, barcha operatsiyalar amalga oshiriladi modul |D.|. Xabar a keyin kod sifatida kodlanadi n- o'lchovli vektor tugadi D. (a₁, a₂, ..., a_n). H keyin | borD.|ⁿ⁺¹ a'zolari, har biriga mos keladigan (n + 1) - o'lchovli vektor tugadi D. (h₀, h₁, ..., h_n). Agar biz ruxsat bersak

${ displaystyle h (a) = h_ {0} + sum _ {i = 1} ^ {n} h_ {i} a_ {i} ,}$

buni isbotlash uchun ehtimolliklar va kombinatorika qoidalaridan foydalanishimiz mumkin

${ displaystyle Pr _ {h in H} [h (f) = d | h (a) = c] = {1 over | D |}}$

Agar biz barcha hazm qilishni to'g'ri shifrlasak (masalan, a bilan bir martalik pad ), tajovuzkor ulardan hech narsa o'rgana olmaydi va bir xil xesh funktsiyasidan ikki tomon o'rtasidagi barcha aloqa uchun foydalanish mumkin. Bu to'g'ri bo'lmasligi mumkin ECB shifrlash, chunki ehtimol ikkita xabar bir xil xash qiymatini hosil qilishi mumkin. Keyin qandaydir boshlash vektori ishlatilishi kerak, bu ko'pincha deb ataladi nonce. O'rnatish odatiy holga aylandi h₀ = f(nonce), qaerda f bu ham sirdir.

E'tibor bering, katta miqdordagi kompyuter kuchi tajovuzkorga umuman yordam bermaydi. Agar oluvchi o'zi qabul qiladigan soxta narsalarning miqdorini cheklasa (uni aniqlaganida uxlab), |D.| 2 bo'lishi mumkin³² yoki kichikroq.

Misol

Quyidagi C funktsiyasi 24 bitli UMAC hosil qiladi. Bu shunday deb taxmin qiladi sir 24 bitning ko'paytmasi, msg dan uzun emas sir va natija allaqachon 24 ta maxfiy bitni o'z ichiga oladi, masalan. f (nonce). nonce tarkibida bo'lishi shart emas msg.

/ * DUBIYALAR: Bu RFC (ehtimol uzoq) bilan hech qanday aloqasi yo'q ko'rinadi * aniqlik. Bu, ehtimol, umumiy UMAC kontseptsiyasi uchun misoldir. * 2007 yildagi kim (Nroets) misolda 3 baytni tanlagan? * * Biz buni strning yaxshiroq ta'rifi bilan birga ko'chirishimiz kerak. uni. ichiga xash * uni. xash. * /# uchar uint8_t ni aniqlangbekor UHash24 (uchar *msg, uchar *sir, hajmi_t len, uchar *natija){  uchar r1 = 0, r2 = 0, r3 = 0, s1, s2, s3, byteCnt = 0, bitCnt, bayt;    esa (len-- > 0) {    / * Har uch bayt uchun yangi sirni oling. * /    agar (byteCnt-- == 0) {      s1 = *sir++;      s2 = *sir++;      s3 = *sir++;      byteCnt = 2;       }    bayt = *msg++;    / * Msg ning har bir bayti sirlarning bittasi xashga kirishini nazorat qiladi.     *     * Men uning tartibini 24 yoshgacha saqlash haqida fikrga ega emasman, chunki 3 baytlik narsa bilan     * bu aniqlik bo'yicha faqat 0-23 tartibli polinominallarga ega. "Sek" kodi bir xil     * xatti-harakatlar, garchi biz hali ham har bir bit uchun juda ko'p ish qilmoqdamiz     */    uchun (uchar bitCnt = 0; bitCnt < 8; bitCnt++) {      / * Oxirgi bit maxfiy bit ishlatilishini nazorat qiladi. * /      agar (bayt & 1) {        r1 ^= s1; / * (sek >> 16) va 0xff * /        r2 ^= s2; / * (sek >> 8) & 0xff * /        r3 ^= s3; / * (sek) va 0xff * /      }      bayt >>= 1; / * keyingi bit. * /      / * va maxfiyni x (ya'ni 2) bilan ko'paytiring, chiqarib oling (XOR bo'yicha)         tartibini 24 (?!) * / gacha ushlab turish uchun kerak bo'lganda polinom.      uchar doSub = s3 & 0x80;      s3 <<= 1;      agar (s2 & 0x80) s3 |= 1;      s2 <<= 1;      agar (s1 & 0x80) s2 |= 1;      s1 <<= 1;      agar (doSub) {  / * 0b0001 1011 -> * /        s1 ^= 0x1B; / * x ^ 24 + x ^ 4 + x ^ 3 + x + 1 [16777243 - oddiy emas] * /      }    } / * xabardagi har bir bit uchun * /  } / * xabardagi har bir bayt uchun * /  *natija++ ^= r1;  *natija++ ^= r2;  *natija++ ^= r3;}

# uchar uint8_t ni aniqlang# almashtirishni aniqlang (x) ((x) & 0xff) << 24 | ((x) & 0xff00) << 8 | ((x) & 0xff0000) >> 8 | (x) & 0xff000000) >> 24)/ * Bu xuddi shu narsa, lekin guruhlangan (yaxshiroq yig'ish va narsalarni yaratish).   Bu hali ham yomon va hech kim nima uchun uni universal deb tushuntirmadi. * /bekor UHash24Ex (uchar *msg, uchar *sir, hajmi_t len, uchar *natija){  uchar bayt, o'qing;  uint32_t soniya = 0, ret = 0, tarkib = 0;  esa (len > 0) {    / * Uchtasini o'qing. * /    tarkib = 0;    almashtirish (o'qing = (len >= 3 ? 3 : len)) {      ish 2: tarkib |= (uint32_t) msg[2] << 16; / * FALLTHRU * /      ish 1: tarkib |= (uint32_t) msg[1] << 8;  / * FALLTHRU * /      ish 0: tarkib |= (uint32_t) msg[0];    }    len -= o'qing; msg += o'qing;    / * Har uch bayt uchun yangi sirni oling. * /    soniya = (uint32_t) sir[2] << 16 | (uint32_t) sir[1] << 8 | (uint32_t) sir[0];    sir += 3;    / * Ajoyib kompressor. * /    uchun (bitCnt = 0; bitCnt < 24; bitCnt++) {      / * Olib tashlash uchun qattiq ma'lumotga bog'liqlik: chiqish bog'liq       * oraliqda.       * CRC bayt jadvallari bilan haqiqatan ham ishlamaydi. * /      agar (bayt & 1) {        ret ^= soniya;      }      bayt >>= 1; / * keyingi bit. * /      / * Shift registri. * /      soniya <<= 1;      agar (soniya & 0x01000000)        soniya ^= 0x0100001B;      soniya &= 0x00ffffff;    } / * xabardagi har bir bit uchun * /  } / * xabardagi har 3 bayt uchun * /  natija[0] ^= ret & 0xff;  natija[1] ^= (ret >>  8) & 0xff;  natija[2] ^= (ret >> 16) & 0xff;}

NH va RFC UMAC

NH

Yuqoridagi funktsiyalar noma'lum^{[iqtibos kerak ]} kuchli universal xash-funktsiya oilasi foydalanadi n xash qiymatini hisoblash uchun ko'payadi.

NH oilasi ko'paytmalar sonini ikki baravarga qisqartiradi, bu taxminan amalda ikki baravar tezlashishga aylanadi.^[1] Tezlik uchun UMAC NH hash funktsiyali oilasini ishlatadi. NH foydalanish uchun maxsus ishlab chiqilgan SIMD va shuning uchun UMAC - bu SIMD uchun optimallashtirilgan birinchi MAC funktsiyasi.^[2]

Quyidagi xash oilasi ${ displaystyle 2 ^ {- w}}$-unversal:^[2]

${ displaystyle operator nomi {NH} _ {K} (M) = chap ( sum _ {i = 0} ^ {(n / 2) -1} ((m_ {2i} + k_ {2i}) { bmod {~}} 2 ^ {w}) cdot ((m_ {2i + 1} + k_ {2i + 1}) { bmod {~}} 2 ^ {w}) o'ng) { bmod { ~}} 2 ^ {2w}}$.

qayerda

• M xabari an kodi bilan kodlangan nning o'lchovli vektori w-bit so'zlar (m₀, m₁, m₂, ..., m_n-1).
• K oraliq kaliti an sifatida kodlangan n + 1ning o'lchovli vektori w-bit so'zlar (k₀, k₁, k₂, ..., k_n). A pseudorandom generator umumiy maxfiy kalitdan K hosil qiladi.

Amalda NH imzosiz butun sonlarda bajariladi. Barcha ko'paytmalar mod 2 ^w, barcha qo'shimchalar mod 2 ^w/ 2 va barcha yozuvlar yarim so'zlarning vektori (${ displaystyle w / 2 = 32}$-bit butun sonlar). Keyinchalik algoritm ishlatiladi ${ displaystyle lceil k / 2 rceil}$ ko'paytmalar, qaerda ${ displaystyle k}$ vektordagi yarim so'zlarning soni edi. Shunday qilib, algoritm kirish so'zi uchun bitta ko'paytmaning "tezligi" bilan ishlaydi.

RFC 4418

RFC 4418 uni yaxshi UMAC qilish uchun NHni o'rash uchun juda ko'p ishlaydi. UHASH ("Umumjahon Hash Funktsiyasi") umumiy tartibi o'zgaruvchan uzunlikdagi teglarni ishlab chiqaradi, bu uning xeshlashning barcha uchta qatlamida zarur bo'lgan takrorlanishlar soniga (va kalitlarning umumiy uzunliklariga) to'g'ri keladi. AES-ga asoslangan bir nechta qo'ng'iroqlar tugmachani chiqarish funktsiyasi barcha uchta xeshlar uchun kalitlarni taqdim etish uchun ishlatiladi.

• Qatlam 1 (1024 bayt bo'laklari -> 8 bayt xeshlar birlashtirilgan) tez bo'lgani uchun NH dan foydalanadi.
• Layer 2 asosiy modulli arifmetikani bajaradigan POLY funktsiyasidan foydalangan holda 16 baytgacha hamma narsani yig'adi, chunki kirish hajmi kattalashgan sari asosiy o'zgaradi.
• 3-qavat 16 baytlik satrni belgilangan 4 bayt uzunlikka xeshlaydi. Buni bitta takrorlash hosil qiladi.

Yilda RFC 4418, NH quyidagi shaklga keltirilgan:

Y = 0for (i = 0; i 
Ushbu ta'rif dasturchilarni yig'ish bo'yicha SIMD ko'rsatmalaridan foydalanishni rag'batlantirish uchun ishlab chiqilgan, chunki faqat to'rtta indeksli ma'lumotlar bir xil SIMD registrga kiritilmasligi mumkin va shuning uchun ommaviy ravishda ko'payish tezroq bo'ladi. Gipotetik mashinada bu shunchaki tarjima qilinishi mumkin edi:
Gipotetik yig'ilish
movq        $0,   regY  ; Y = 0movq        $0,   regI  ; i = 0pastadir:qo'shish         reg1, regM, regI ; reg1 = M + iqo'shish         reg2, regM, regIvldr.4x32   vec1, reg1       ; xotiradan * reg1-dan vec1-ga 4x32bit vallarni yuklangvldr.4x32   vec2, reg2vmul.4x64   vec3, vec1, vec2 ; vec3 = vec1 * vec2uaddv.4x64  reg3, vec3       ; gorizontal ravishda vec3 ni reg3 ga yig'ingqo'shish         regY, regY, reg3 ; regY = regY + reg3qo'shish         regI, regI, $8cmp         regI, regTjlt         pastadir
Shuningdek qarang



Poly1305 kuchli universal xeshga asoslangan yana bir tezkor MAC.
Adabiyotlar



^ Torup, Mikkel (2009). Lineer probirovka qilish uchun satrlarni aralashtirish. Proc. Diskret algoritmlar bo'yicha 20-ACM-SIAM simpoziumi (SODA). 655-664 betlar. CiteSeerX  10.1.1.215.4253. doi:10.1137/1.9781611973068.72. Arxivlandi (PDF) 2013-10-12 kunlari asl nusxasidan., 5.3-bo'lim
^ a b Qora, J .; Halevi, S .; Kravich, X.; Krovetz, T. (1999). UMAC: Xabarlarni tezkor va ishonchli tasdiqlash (PDF). Kriptologiya sohasidagi yutuqlar (CRYPTO '99). Arxivlandi asl nusxasi (PDF) 2012-03-10., 1-tenglama va shuningdek 4.2-bo'lim "NH ta'rifi".
Tashqi havolalar



Ted Krovetz. "UMAC: tezkor va ishonchli tarzda xabarlarni autentifikatsiya qilish".
"SSH transport qatlami protokolida UMAC-dan foydalanish: draft-miller-secsh-umac-01.txt". IETF. 2007-09-03.