Puncte:2

Poly1305 reutilizarea r

drapel ru

Poly1305 folosește $r, r^2, r^3$ și $r^4$. înțeleg asta dacă $r$ este un generator al câmpului finit. Dar de atunci $r$ poate fi orice număr aleatoriu diferit de zero, exponenții săi nu vor fi distribuiți neuniform? Adică chiar dacă $r$ este ales cu aleatoriu uniform pe teren, $r^4$ nu este uniform pe teren. De ce nu este aceasta o slăbiciune?

Rețineți că lucrările lui Bernstein* folosesc scheme similare pentru orice câmp finit, folosind până la $r^8$, ceea ce înseamnă că sunt acceptabile pentru orice câmp finit.

* Secțiunea 4.2 din https://cr.yp.to/antiforgery/pema-20071022.pdf utilizări $r$ De 8 ori, fiecare cu un exponent mai mare.

Fractalice avatar
drapel in
Ce vrei să spui prin „până la r^8”?
drapel ru
@Fractalice Editat cu răspuns
Fractalice avatar
drapel in
Multumesc, vad de 8 ori dar tot nu vad acolo "fiecare cu un exponent mai mare".
Puncte:4
drapel in

Într-adevăr, modulo un prim, deja $r^2$ sunt neuniforme - doar jumătate din valori sunt posibile. În timp ce polinoamele calculate într-adevăr nu urmează distribuția uniformă, neuniformitatea este mărginită: fiecare valoare de ieșire a polinomului poate avea cel mult $L$ preimagini (rădăcini), unde $L$ este gradul său, egal cu numărul de blocuri. Înseamnă că probabilitatea poate crește de la 1 USD/R$ la $L/R$, Unde $R$ este numărul tuturor posibilelor $r$ (care este $2^{106}$ în Poly1305). Pentru a obține o probabilitate de succes care nu este neglijabilă, trebuie să încercați un fals cu un număr mare de blocuri.

Rețineți că rezultatul este mascat prin adăugare AES (niciodată). Acest lucru face ca predicția oarbă a MAC să fie inutilă. Cel mai puternic atac aici este o încercare de falsificare diferențială: dat fiind a (mesaj, nonce, etichetă) triplu, generează un alt triplu (mesaj', nonce, tag'). Același nonce elimină AES (niciodată) din consideraţia în diferenţă $(etichetă' - etichetă)$. Trebuie „doar” să prezicem poli(mesaj') - poli(mesaj) pentru orice mesaj și mesaj' la alegerea noastră. Ceea ce este greu, deoarece o diferență de polinoame neegale este încă un polinom diferit de zero de același grad sau mai mic, iar probabilitatea de a ghici rezultatul corect este mică.

Acest raționament funcționează pentru orice câmp finit.

Editați | ×: mulțumesc lui @poncho pentru că a observat o confuzie periculoasă între xor și adăugare peste GF(p)

Editați | ×: în https://cr.yp.to/antiforgery/pema-20071022.pdf , Bernstein introduce mai întâi un MAC bazat pe produs punct, adică. $MAC(m) = m_1r_1 + m_2 r_2 + ... + s$. The $n=8$ Acțiunile sunt alese doar pentru ilustrare, deoarece aceasta permite doar semnarea mesajelor de 8 blocuri. Din nou, acest lucru se face doar din motive educaționale și pentru a arăta construcții istorice „pure”. Mai târziu în ziar, el înlocuiește $r_i$ cu $r^i$: acest lucru permite evitarea generării și stocării pseudoaleatoare cu drepturi depline a multor $r$lui. În mod similar, complet aleatoriu $s$ poate fi înlocuit de ex. AES (nu o dată).

drapel cn
Poate doriți să mergeți mai mult în partea „orice câmp finit” a întrebării.
drapel ru
Mulțumiri. Poți clarifica puțin matematica? Înțeleg că spuneți: dacă am folosi 8 valori separate de $r$ (după cum arată cealaltă lucrare a lui Bernstein), ați avea o probabilitate de $1/R$ de a ghici $a$. Deoarece folosim doar un $r$ și îl folosim exponențiat $L = 8$, aveți o problemă $L/R$. De ce $L$ este exponentul _max_? M-aș aștepta să fie _suma_ a _toți_ exponenților (adică dacă max este $r^8$, $L = 15$).
drapel ru
„Într-adevăr, modulo a prim, deja $r^2$ sunt neuniforme - doar jumătate din valori sunt posibile” Acest lucru pare plauzibil, dar nu pot dovedi. Poți să arăți cum l-ai derivat?
poncho avatar
drapel my
@SRobertJames: ei bine, dintre valorile diferite de zero, jumătate sunt nereziduuri pătratice modulo $p = 2^{130}-5$; acestea sunt (prin definiție) valori care nu pot fi reprezentate sub forma $r^2 \bmod p$. Adică, nu există o valoare posibilă $r$ pentru care $r^2$ sunt acele valori și, prin urmare, au probabilitatea de a apărea 0.
poncho avatar
drapel my
„Rețineți că rezultatul este mascat (xored) de AES(nonce).”; de fapt, se adaugă. Un lucru pe care l-am observat cu ceva timp în urmă este că dacă înlocuiți această adăugare cu xor (cum ați scris), falsurile cu mare probabilitate sunt foarte posibile...
Fractalice avatar
drapel in
@poncho ai dreptate, captură bună! Dovada acoperă doar diferența GF(p), în timp ce cu xor AES(nonce) trebuie să luăm în considerare distribuția diferenței xor. Dar aveți în vedere un atac concret cu mare probabilitate pentru acest caz?
Fractalice avatar
drapel in
@SRobertJames polinomul calculat este de aproximativ $m_1 r^1 + m_2r^2 + ... + m_8 r^8$ ($m_i$ este blocul de mesaj $i$). Indiferent de câți termeni, are gradul 8, deci L = 8.
poncho avatar
drapel my
@Fractalice: da, am găsit o diferență (atât pentru mesaj, cât și pentru etichetă) care a reușit cu probabilitate fie 0,25, fie 0,5. A trecut ceva timp - voi vedea dacă pot să-l dezgrop...
Fractalice avatar
drapel in
@poncho văd, înmulțirea cu -1 mod $2^{130}-5$ este foarte aproape de xoring cu șirul de biți all-one. Deci am putea folosi valoarea maximă codabilă $c_1=2^{129}$ și negativul său $c_1'=2^{129}-5$. XOR pare să fie egal cu modulul $2^{130}-5$ cu mare probabilitate.
Fractalice avatar
drapel in
Dacă exponentul ar fi 131, nu va funcționa!

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.