înregistrare Logare
Puncte:0
avatar Crypto

Înmulțirea matriceală a rezumatelor hash admite manipularea rezultatului?

drapel in
infogulch

Luați o secvență de buffer-uri de octeți, hash fiecare dintre ele, interpretați digesturile hash ca matrici pătrate cu elemente int fără semn de 8 biți și (matrice) înmulțiți-le în ordine. Definiți matricea finală să fie „hash” al listei de elemente.

Această definiție are câteva proprietăți utile. În special, proprietatea asociativă a înmulțirii matricei permite calcularea hash-ului listă al concatenării a două liste prin calcularea hash-ului fiecărei liste în mod independent și apoi reducerea acestora prin multiplicare pentru a obține hash-ul listă final. Acest lucru funcționează cu orice partiționare arbitrară. Non-comutativitatea prevede că diferitele comenzi ale elementelor creează un hash diferit pentru listă, așa cum s-ar aștepta pentru o listă.

(Explorez această definiție mai detaliat, incluzând exemple de cod de lucru într-un caiet python jupyter pe care l-am publicat intitulat Merklist. De asemenea, vă puteți juca singur cu el Google Colabși adăugați adnotări hypothes.is pe postare pentru feedback general. Pot ridica detalii de acolo la această întrebare dacă este necesar.)

Întrebare

  1. Este această definiție rezistentă la atacurile preimagine? Altfel spus, este posibil să se selecteze o secvență de elemente care are ca rezultat un hash arbitrar în lista țintă?

Rețineți că elementele trebuie să existe, astfel încât digerările de elemente care intră în list-hash au rezistență preimagine bazată pe funcția hash de bază (pe care putem presupune că este valabilă în domeniul de aplicare al acestei întrebări). Deci, într-adevăr întrebarea devine: Ordinea sau prezența acestor resume hash poate fi folosită pentru a modifica în mod arbitrar conținutul matricei finale? De exemplu, puteți genera o secvență de elemente care produce o listă-hash care este matricea zero? (Lovirea unei matrice zero înseamnă terminarea jocului, afaict.)

Am făcut câteva căutări și nu am găsit răspunsuri la niciuna dintre aceste întrebări, deși bănuiesc că s-ar putea datora atât ignoranței mele cu privire la terminologia corectă, cât și inexistenței răspunsurilor.

83
1 + 9
poncho avatar
drapel my
poncho
BTW: Tocmai am încercat; când am analizat împreună o secvență de aproximativ 3000 de preimagini diferite (nu alese cu răutate), rezultatul a fost matricea total-zero.
0
Răspunde
drapel in
infogulch
Puiete, se pare că „nu și-a făcut temele” se afișează. Cat de rusinos Cred că va trebui să încerc din nou cu $GF(256)$ și poate să-l testez puțin mai atent.
0
Răspunde
poncho avatar
drapel my
poncho
Bănuiesc că, în timp ce $GF(256)$ ar fi considerabil mai bine, chiar și atunci, dacă trebuie să excludeți matricele neinversabile, o serie suficient de mare va ajunge totuși ca toate 0 - ar putea fi nevoie de un milion de elemente, mai degrabă decât doar 3.000.
0
Răspunde
drapel in
infogulch
Crezi? Simt că dacă intrările de candidați sunt limitate la matrici inversabile, doar asta ar trebui să o rezolve. Luați acest exemplu: $X A B C C^{-1} B^{-1} A^{-1}$; acest lucru ar trebui să rezulte întotdeauna în $X$ din nou, indiferent cât de lungă este secvența inițială $ABC$. De exemplu, dacă nu ar fi, atunci una sau mai multe dintre matrice nu ar fi inversabile prin definiție. Nu? Simt că cea mai mare problemă va fi găsirea unei matrice inversabile pentru fiecare intrare posibilă într-un timp rezonabil.
0
Răspunde
drapel in
infogulch
@poncho Tocmai l-am încercat cu elemente de matrice $GF(256)$ și încă pare bine după 10M de intrări. În curând voi posta o altă întrebare ca aceasta, dar cu formula $GF(256)$ în schimb.
0
Răspunde
poncho avatar
drapel my
poncho
Dacă utilizați $GF(256)$, atunci o matrice aleatorie are aproximativ $1/256$ de a fi singulară; suspiciunea mea că, cu un lanț lung, numărul de matrici singulare care apar aleatoriu va reduce treptat rangul, ducând în cele din urmă la un rang de 0 (matricea tuturor 0-urilor). Totuși, nu am un model bun despre cât de curând s-ar întâmpla asta...
0
Răspunde
drapel in
infogulch
Da, ai dreptate. Pentru a mă asigura că nu sunt admise matrice singulare, folosesc eșantionarea de respingere într-o buclă atunci când calculez „hash-ul matricei” a unui element, așa cum ați sugerat mai înainte.
0
Răspunde
poncho avatar
drapel my
poncho
Evident, dacă te restrângi la elemente inversabile, ei bine, acestea formează un grup și, prin urmare, nu vei ajunge niciodată într-o stare restricționată (cum ar fi matricea all-0). Ar putea exista trucuri subtile pe care le-ați putea folosi din teoria grupurilor pentru a găsi o coliziune; totusi asta nu este deloc evident...
0
Răspunde
drapel in
infogulch
@poncho Am publicat o versiune nefinalizată folosind $GF(256)$ într-o postare nouă, dacă ești interesat: https://blog.infogulch.com/2021/07/15/Merklist-GF.html În schimb, folosește Julia de python pentru că am vrut să încerc pe Julia. Îl puteți deschide pentru a edita live online. Vreau să adaug un addendum la postarea mea originală, subliniind problema pe care ați găsit-o.
0
Răspunde
Puncte:1
poncho avatar Crypto
drapel my
poncho

De exemplu, puteți genera o secvență de elemente care produce o listă-hash care este matricea zero?

Da; Cea mai evidentă modalitate este de a găsi un buffer care face hash la o matrice cu toate $n^2$ elemente de matrice chiar; replicați acel tampon de 8 ori și veți obține un produs care are toate zerouri.

Acest lucru necesită o așteptare $2^{n^2}$ lucrează pentru a găsi un astfel de tampon; pentru $n=8$, acest lucru este plauzibil.

Probabil ar putea fi îmbunătățit; privind perechile de matrici neinversibile, ar părea plauzibil ca, cu mult mai puțină muncă decât $2^{64}$, puteți găsi două al căror produs are toate elementele egale (și în acest caz s-ar aplica observația de mai sus).

0 + 3
drapel in
infogulch
Asta are mult sens.Pentru a clarifica, acest lucru este cauzat de alegerea mea de inel (256) care are factori de 2? Credeți că acest lucru ar putea fi îmbunătățit prin alegerea unui inel principal (să zicem, 257)?
0
Răspunde
poncho avatar
drapel my
poncho
@infogulch: sau $GF(2^8)$? Ei bine, ar ajuta, dar nu atât de semnificativ; încă mai are o probabilitate bună (probabilitate circa 1/256 per încercare) de a găsi matrici neinversibile; pare plauzibil că le-ați putea lipi împreună pentru a găsi produse cu rang în scădere, rezultând matricea totală 0. De fapt, răspunsul meu inițial urma să fie acesta, până când mi-am dat seama că răspunsul „toți lsbits 0” era considerabil mai ușor de justificat. Totuși, dacă ați folosit un câmp precum $GF(256)$ sau $GF(257)$ și ați sărit în mod deliberat (folosind eșantionarea de respingere) matrici neinversibile, ar putea funcționa
1
Răspunde
drapel in
infogulch
Mulțumim pentru indicatorul către câmpurile Galois și matricele inversabile. Am considerat că matricele inversabile ar putea fi plăcute, dar probabil că acestea sunt o cerință pentru ca acest lucru să funcționeze și să nu ducă la cazuri degenerate precum o matrice zero.
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.