înregistrare Logare
Puncte:2
elonnoe avatar Crypto

Avantajul Adversary față de o funcție simplă?

drapel ng
elonnoe

Atacatorul trebuie să câștige jocul următor distingând că ieșirea a fost actualizată de o anumită funcție sau nu?

  1. Atacatorul solicită un oracol pentru ieșire.

  2. Oracle generează noi 4 octeți aleatori $a$, $b$, $c$, și $d$ și un bit aleatoriu $x$.

  3. dacă $x=0$, Oracle scoate valori ale $a$, $b$, $c$, și $d$.

  4. dacă $x=1$, mai întâi actualizează valorile folosind următoarele ecuații (aplicate secvențial) și apoi emite valorile actualizate ale $a$, $b$, $c$, și $d$. $$\begin{align} a &= (a + dc) \bmod 256;\ b &= (b + ad) \bmod 256;\ c &= (c + ba) \bmod 256;\ d &= (d + cb) \bmod 256;\ \end{align}$$

  5. Scopul atacatorului este să constate că rezultatul a fost rezultatul pasului 3 sau 4?

* Atacatorul poate face interogări infinite.

Exemplu: dacă a=0, b=0, c=1, d=1 și x=1 la pasul 2, atunci iese Oracle 1,1,2,3.

113
2 + 7
ShAr avatar
drapel cn
ShAr
Care este obiectivul atacatorului? Care este profitul/câștigul sau utilitatea fn?
0
Răspunde
elonnoe avatar
drapel ng
elonnoe
@ShAr a actualizat întrebarea.
0
Răspunde
ShAr avatar
drapel cn
ShAr
Am răspuns, dar cred că acest Q este mai potrivit în informatică sau în teoria jocurilor/numerele pentru operațiunile de mod dacă există. Oricum, aceasta este doar o opinie care nu votează nimic
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
Declarația problemei de la 4 este neclară dacă ecuațiile sunt aplicate secvenţial sau ca un bloc, de ex. dacă la pasul 2 a=0, b=0, c=1, d=1, x=1 iese oracolul 1,1,2,3 sau 1,0,1,1? Prima lectură ușurează problema: ce aduce fiecare schimbare în distribuția a ceea ce modifică? A doua lectură este mai interesantă. Sugestie: explorați ce se întâmplă pentru bitul de ordin scăzut, apoi pentru al doilea. Este suficient pentru a câștiga jocul, dar nu a obține cel mai bun avantaj. Pentru a medita: $(\mathbb Z_{2^k},+,\cdot)$ este un câmp numai când $k=0$. Dacă vrei ajutor, spune-ne ce ai făcut, unde ești blocat!
1
Răspunde
elonnoe avatar
drapel ng
elonnoe
@fgrieu Am actualizat întrebarea pentru a răspunde la întrebarea dvs. Am calculat frecvența fiecărei valori posibile pentru fiecare octet de ieșire și bitul cel mai puțin semnificativ al fiecărui octet de ieșire, dar nu am putut găsi niciun model în el. Deoarece atacatorul nu are control asupra octeților de intrare și Oracle generează octeți noi aleatori de fiecare dată când este interogat, rezultatul pasului 4 apare aleatoriu!!!.
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
Acest lucru este corect: cu ecuațiile aplicate secvențial, nu există nicio modalitate de a distinge 3 de 4. Asta pentru că fiecare dintre cele patru modificări lasă distribuția $(a,b,c,d)$ uniformă (argument: în orice grup cu legea $\boxplus$, este suficient ca $u$ să fie uniform aleatoriu și independent de $v$ pentru ca $u\boxplus v$ să fie uniform aleatoriu). Nu este așa pentru `(a,b,c,d)=((a+d*c)%256,(b+a*d)%256,(c+b*a)%256,(d+c* b)%256)` în sensul pe care îl are în Python, care este în cazul în care sugerez să examinăm ce se întâmplă cu biții mici, apoi cei doi biți de ordin inferior.
0
Răspunde
elonnoe avatar
drapel ng
elonnoe
@fgrieu multumesc pentru ajutor. Eram blocat, dar acum înțeleg motivul de bază.
0
Răspunde
Puncte:3
avatar Crypto
drapel us
Mikero

Lăsa $f(a,b,c,d)$ denotă transformarea ta în pasul 4. Este compoziția secvențială a acestor 4 pași:

  1. $(a,b,c,d) \mapsto (a+dc \bmod 256,b,c,d)$
  2. $(a,b,c,d) \mapsto (a,b+ad \bmod 256,c,d)$
  3. $(a,b,c,d) \mapsto (a,b,c+ba \bmod 256,d)$
  4. $(a,b,c,d) \mapsto (a,b,c,d+cb \bmod 256)$

Rețineți că fiecare pas este inversabil. De exemplu, primul pas este inversabil ca $(a',b,c,d) \mapsto (a'-dc \bmod 256,b,c,d)$. Prin urmare, întreaga transformare $f(a,b,c,d)$ este inversabilă.

Din moment ce distribuția s-a încheiat $(a,b,c,d)$ este iniţial uniformă şi $f$ este inversabilă, distribuția activă $f(a,b,c,d)$ este si uniforma. Asta înseamnă: indiferent de $x=0$ sau $x=1$, ieșirea este uniformă, deci un distinctor nu are niciun avantaj să ghicească $x$.

0 + 2
fgrieu avatar
drapel ng
fgrieu
Da. Cazul în care transformarea este $a'=(a+dc)\bmod256$, $b'=(b+ad)\bmod256$, $c'=(c+ba)\bmod256$, $d'=( d+cb)\bmod256$ urmat de $a=a'$, $b=b'$, $c=c'$, $d=d'$ este mai dificil/interesant. Acum există un avantaj deloc neglijabil de calculat.
0
Răspunde
crypt avatar
drapel cn
crypt
deci este valabil pentru orice f inversabil?
0
Răspunde
Puncte:0
ShAr avatar Crypto
drapel cn
ShAr

  • Probabilitatea de a câștiga din prima probă = 0,5 (ghicire pură presupunând valori aleatoare ale X uniforme 0 sau 1)

  • Probabilitatea de a câștiga la a 2-a probă, având în vedere că știe rezultatul primei probă= 1 - prob[((a=a+dc)mod256) AND ((b=b+ad) mod256) AND ((c=c+ba) mod256) AND ((d=d+cb) mod256)]

Pentru început, pentru ca aceste formule să fie â¥256 (atinge aceeași valoare prin operația de mod), cel puțin 3 din cele 4 valori trebuie să fie â¥128

De fapt, ele trebuie să conțină (nu doar să fie mai mari sau egale) suficiente puteri de 2 (dc=nâ¢256, ad=mâ¢256, ab=kâ¢256, cb=lâ¢256)

.... si asa mai departe, totusi ma gandesc sa merg mai departe verifica daca valorile trebuie stocate intr-un octet; adică implicit a,b,c,d < 256?

»»» În cazul pasului 2 se repetă la fiecare încercare, atunci cred că singurul mod în care adversarul câștigă din cunoașterea funcției (schimba probabilitatea de câștig la mai mult de 0,5 ghicire pură) este dacă formulele date nu sunt aleatoare uniforme. , adică dacă puteți dovedi că a,b,c,d modificați sunt înclinați spre mai multe 1 sau mai multe 9, probabil că probabilitatea de a câștiga ar trebui să crească cu scăderea gradul de Aleatorie.

0 + 5
fgrieu avatar
drapel ng
fgrieu
Probabilitatea de a câștiga depinde de modul în care citim enunțul problemei pentru pasul 4 și de strategia folosită de adversar (de stabilit). Cu aceste două lucruri rezolvate, deoarece încercările sunt independente, probabilitatea de a câștiga nu poate depinde de numărul de încercare, așa cum se afirmă în răspunsul curent.
0
Răspunde
ShAr avatar
drapel cn
ShAr
Într-adevăr, dacă ai făcut 2 încercări succesive și ai descoperit că rezultatul este diferit, poți avea 100% câștig spunând X=1, ceea ce înseamnă că adversarul a avut un avantaj cel puțin în acest caz, cunoscând jocul care stau la baza fn
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
Pasul 2 este efectuat și generează proaspăt a, b, c, d, x, înainte de pasul 3 sau pasul 4 de fiecare dată când acestea sunt atinse. Astfel, știind că două ieșiri sunt diferite, nu este suficient pentru a concluziona cu x în prima sau a doua ieșire. În general, nu are rost să comparăm rezultatele diferitelor experimente, deoarece acestea sunt independente. Întrebarea este despre conceperea unei strategii care să ofere un avantaj, și care va fi la fiecare experiment, în mod independent. După cum explic în comentariu la Q, acest lucru este posibil sau nu, în funcție de modul în care citim pasul 4 și există două moduri.
0
Răspunde
ShAr avatar
drapel cn
ShAr
Aha Ok, scuze, m-am gândit (rezolvat pe baza faptului că) pasul 2 se face o singură dată ca o sămânță pentru un generator de numere aleatorii
0
Răspunde
elonnoe avatar
drapel ng
elonnoe
@ShAr nu, pasul 2 este efectuat din nou pentru fiecare interogare nouă.
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

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.