Kur flasim për steganografinë, njerëzit mendojnë për terroristët, pedofilët, spiunët ose, në rastin më të mirë, kriptoanarkistët dhe shkencëtarët e tjerë. Dhe me të vërtetë, kujt tjetër mund të ketë nevojë fsheh diçka nga sytë e jashtëm? Cili mund të jetë përfitimi i kësaj për një person të zakonshëm?
Rezulton se ka një. Kjo është arsyeja pse sot ne do të kompresojmë të dhënat duke përdorur metodat e steganografisë. Dhe në fund, lexuesi madje do të jetë në gjendje të përdorë arkivat e tij të çmuara të fotografive në JPEG për të rritur numrin e gigabajteve falas në sistemin e skedarëve.
Çfarë?
Nëse lexuesi e mban mend, steganografia është algoritme kaq të çuditshme që bëjnë të mundur fshehjen e pranisë së një informacioni brenda një tjetri. Në një gjuhë edhe më të thjeshtë: foto + skedar == përafërsisht e njëjta foto, por jo plotësisht (në vend të fotografive mund të ketë gjithçka, por zakonisht gjithçka është më e qartë në to). Nuk duhet të ketë një mënyrë të lehtë për të përcaktuar nëse ka diçka brenda apo jo.
Por nëse njëra nuk mund të dallohet nga tjetra, a ka ndonjë ndryshim fare? Nga këndvështrimi i konsumatorit, përdoruesi nuk kujdeset për saktësinë matematikore (të reflektuar nga një grup i caktuar bitash), vetëm për atë që perceptohet prej tij.
Për shembull, le të shohim tre imazhe të një qeni të lezetshëm:
Kujdes, JPEG!
Pavarësisht ndryshimit të madh në madhësi, pak njerëz do të zgjedhin versionin e tretë. Nga ana tjetër, ndryshimi midis dy fotografive të para nuk është aq i dukshëm, dhe sasia e informacionit në to (nga këndvështrimi im) mund të jetë e barabartë.
Ky parim në vetvete është tashmë i vjetër dhe është shfrytëzuar në mënyrë aktive nga metodat e kompresimit të informacionit me humbje për shumë vite. Por thyerja nuk është ndërtim; ne jemi të interesuar në anën më të avancuar të çështjes. A është e mundur të futni informacion shtesë për madhësinë N në skedar në mënyrë që madhësia e tij të rritet me M < N, por ndryshimet nuk ishin të dukshme për përdoruesin?
Natyrisht ju mund të. Por ia vlen të bëni disa rezervime menjëherë:
- Së pari, metoda duhet të jetë universale dhe të japë një rezultat pozitiv në shumicën e të dhënave hyrëse. Kjo do të thotë, mesatarisht, për një hyrje të rastësishme, duhet të ketë një rënie aktuale në sasinë e informacionit të ruajtur. "Mesatarisht" do të thotë që mund të ndodhë e kundërta, por nuk duhet të mbizotërojë.
- Së dyti, madhësia e kontejnerit të ngjeshur përpara futjes së informacionit duhet të jetë më e madhe se modifikimi i tij i ngjeshur në një mënyrë të ngjashme. Thjesht futja e një grupi pjesësh në imazhet BMP duke përdorur metodën LSB nuk është ngjeshje steganografike, pasi, pasi të jetë ekzekutuar përmes një lloj DEFLATE, imazhi origjinal ka shumë të ngjarë të jetë dukshëm më i vogël.
- Së treti, rezultati duhet të kryhet dhe të krahasohet në lidhje me të dhënat e kompresuara tashmë me metoda klasike. Kjo do të heqë efektin probabilistik të ndryshimeve në tepricën e tyre dhe do të sigurojë kompresim më efikas në rastin e përgjithshëm.
Ku?
Përdorimi i steganografisë nënkupton që, përveç informacionit të ngjeshur, do të na duhen kontejnerë në të cilët do të futet. Sasia maksimale e informacionit të ngulitur varet kryesisht nga vetitë individuale, por është shumë më e lehtë të shkallëzohet me numrin e tyre. Prandaj, formati i kontejnerit duhet të jetë i zakonshëm në mënyrë që përdoruesi të ketë mjaftueshëm prej tyre për të marrë ndonjë përfitim nga procesi i "ngjeshjes".
Në këtë kontekst, skedarët grafikë, audio dhe video janë kandidatë të mirë. Por, për shkak të shumëllojshmërisë së formateve të ndryshme, kodekëve, etj., në praktikë na mbetet një zgjedhje nga jo aq shumë opsione.
Duke marrë parasysh të gjitha këto, zgjedhja ime ra në JPEG. Pothuajse të gjithë e kanë, përdoret gjerësisht si për qëllime personale ashtu edhe për biznes, duke qenë pothuajse formati de facto për shumicën e imazheve.
Varet?
Më tej ka diagrame dhe përshkrime të afërta dhe teknike pa shumë shpjegime, kështu që të interesuarit mund t'i kalojnë ato duke lëvizur te seksioni "Teknologjitë e larta".
Karakteristikat e përbashkëta
Për të futur të dhëna diku, së pari duhet të përcaktoni se ku. Mund të ketë një numër fotografish të ndryshme në sistemin e skedarëve, nga të cilat përdoruesi mund të dëshirojë të përdorë vetëm disa. Ne do ta quajmë një grup të tillë të dëshiruar të kontejnerëve një bibliotekë.
Formohet në dy raste: para ngjeshjes dhe para dekompresimit. Në rastin e parë, thjesht mund të përdorni një grup emrash skedarësh (ose më mirë akoma, një shprehje e rregullt për ta) skedarësh, por në të dytën, kërkohet diçka më e besueshme: përdoruesi mund t'i kopjojë dhe zhvendosë ato brenda sistemit të skedarëve , duke penguar kështu identifikimin e saktë të tyre. Prandaj, është e nevojshme të ruhen hash-et e tyre (md5 mjafton) pasi të jenë bërë të gjitha modifikimet.
Në këtë rast, nuk ka kuptim të kryeni kërkimin fillestar duke përdorur një shprehje të rregullt në të gjithë sistemin e skedarëve; mjafton të specifikoni një direktori të caktuar rrënjësore. Në të do të ruhet një skedar i posaçëm arkiv, i cili do të përmbajë ato hash, së bashku me meta-informacione të tjera të nevojshme për rikuperimin e mëvonshëm të informacionit të ngjeshur.
E gjithë kjo vlen njëlloj për çdo zbatim të çdo algoritmi të kompresimit të të dhënave steganografike. Vetë proceset e ngjeshjes dhe rikuperimit të të dhënave mund të quhen paketim dhe shpaketim.
F5
Tani që është bërë e qartë se çfarë po bëjmë dhe pse, mbetet të përshkruajmë algoritmin për arritjen e qëllimit. Le të kujtojmë procesin e kodimit të një skedari JPEG (falë wiki-t të Bibliotekës Kombëtare Bauman):
Duke e parë atë, është më mirë të bëni menjëherë disa komente:
- Madhësia e një skedari JPEG mund të konsiderohet optimale pa u përpjekur as ta kompresoni atë me një lloj Winrar;
- Vetëm informacioni i ruajtur (ai që del nga transformimi diskret kosinus, DCT) mund të modifikohet për të siguruar të paktën performancë të pranueshme.
- Për të mos humbur të dhënat në një shkallë industriale të dukshme për përdoruesin, është e nevojshme të bëni një minimum modifikimesh për çdo imazh individual;
Një familje e tërë algoritmesh i përshtatet këtyre kushteve, me të cilat mund të njiheni . Më i avancuari prej tyre është algoritmi nga Andreas Westfeld, duke punuar me koeficientët DCT të komponentit të shkëlqimit (syri i njeriut është më pak i ndjeshëm ndaj ndryshimeve të tij). Paraqitja e tij e përgjithshme kur punoni me një skedar ekzistues JPEG shfaqet si më poshtë:
Blloku F5 përdor një teknikë të avancuar të ngulitjes bazuar në kodimin e matricës. Lexuesi mund të mësojë më shumë rreth tij dhe vetë algoritmit në lidhjen e mësipërme, por ne jemi kryesisht të interesuar për faktin që me ndihmën e tij mund të bëni sa më pak ndryshime kur futni të njëjtën sasi informacioni, sa më e madhe të jetë madhësia e kontejnerit të përdorur. , dhe për kryerjen e algoritmit duhet vetëm të kryejë operacione të thjeshta (de)kodimi Huffman dhe RLE.
Vetë ndryshimet bëhen në koeficientët e numrave të plotë dhe zvogëlojnë vlerën e tyre absolute me një, gjë që lejon, në përgjithësi, përdorimin e F5 për kompresimin e të dhënave. Çështja është se koeficienti i reduktuar në vlerë absolute ka shumë të ngjarë të zërë më pak bit pas kodimit të Huffman për shkak të shpërndarjes statistikore të vlerave në JPEG.
Në rastin e formimit të një zero (i ashtuquajturi reduktim), numri i informacionit të ruajtur do të zvogëlohet për nga madhësia e tij, pasi koeficienti i mëparshëm i pavarur do të bëhet pjesë e sekuencës së koduar RLE të zerove:
modifikim
Mbrojtja dhe kompresimi i të dhënave janë probleme ortogonale, kështu që ndryshimi i fjalëkalimit sekret nga algoritmi origjinal mund të neglizhohet. Për më tepër, ne duhet të dimë saktësisht se si të nxjerrim të dhënat, kështu që të gjitha informacionet e nevojshme për këtë (cilat kontejnerë janë përdorur, në çfarë rendi etj.) duhet të regjistrohen në një skedar të veçantë dhe të jenë të hapura për lexim falas nga arkivuesi.
Algoritmi origjinal është krijuar për të transmetuar mesazhe sekrete, kështu që funksionon me vetëm një kontejner në të njëjtën kohë, duke supozuar se vetë përdoruesi do ta ndajë atë në pjesë nëse është e nevojshme, nëse ka. Për më tepër, kur futet në mënyrë të pavarur në çdo kontejner, do t'ju duhet të dini paraprakisht se sa pjesë të të dhënave duhet të vendosni në secilin. Prandaj, koeficientët e secilit element të bibliotekës duhet të kombinohen në një abstrakt të madh dhe të punohen me të sipas algoritmit origjinal.
Meqenëse F5 origjinale lejon deri në 12% të madhësisë së kontejnerit, ky modifikim do të rrisë gjithashtu kapacitetin maksimal: "deri në 12%" e madhësisë së të gjithë bibliotekës është më e madhe ose e barabartë me shumën "deri në 12%. "nga secili element i tij.
Skema e përgjithshme e kodifikuar është si më poshtë:
Vetë algoritmi
Tani është koha për të përshkruar vetë algoritmin nga fillimi në fund, në mënyrë që të mos e mbani lexuesin në errësirë:
- Përdoruesi përcakton të dhënat binare të kompresueshme M dhe bibliotekën L duke përdorur një shprehje të rregullt dhe një direktori rrënjësore kërkimi;
- Sipas renditjes që shfaqen në FS, elementët e bibliotekës formojnë MC:
- Një seri koeficientësh C deshifrohen nga të dhënat e skedarit;
- MC <- MC | C;
- Parametri k përcaktohet bazuar në pabarazinë e tmerrshme:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Marrë në vazhdim
n = (1 << k) - 1pjesët më pak të rëndësishme të elementeve jozero nga MC dhe të shkruara nëa:- Funksioni magjik hash merret parasysh
f, që përfaqëson një fjalë n-bitanë k-bits; - Nëse
s == 0, atëherë nuk ka nevojë të ndryshohet asgjë dhe algoritmi kalon në koeficientët e ardhshëm; - Zvogëloni vlerën absolute të koeficientit përgjegjës për
s-hej pak në fjalëa; - Nëse si rezultat i zvogëlimit ndodh një reduktim (koeficienti bëhet 0), atëherë përsërisni hapin nga fillimi;
- Funksioni magjik hash merret parasysh
- Të gjithë koeficientët janë të koduar nga RLE dhe Huffman, të shkruara në skedarët burim;
- Parametri k është shkruar në skedarin e arkivit;
- Një hash MD5 llogaritet nga çdo skedar L në rendin e vendndodhjes së tyre origjinale dhe shkruhet në skedarin e arkivit.
Teknologji e larte
Forma naive e algoritmit dhe zbatimet në gjuhë të tjera të nivelit të lartë (veçanërisht me mbledhjen e mbeturinave) do të jepte performancë të tmerrshme, kështu që unë i zbatova të gjitha këto kompleksitete në C të pastër dhe kryeva një sërë optimizimesh si për sa i përket shpejtësisë së ekzekutimit ashtu edhe memorie (nuk e keni idenë se sa peshojnë këto foto pa kompresim edhe para DCT). Por edhe kështu, në fillim shpejtësia e ekzekutimit la shumë për të dëshiruar, kështu që nuk do të përshkruaj të gjithë procesin dhe metodat e përdorura.
Ndër-platforma arrihet duke përdorur një kombinim të bibliotekave libjpeg, pcre dhe tinydir, për të cilat i falënderojmë. Si parazgjedhje, gjithçka përpilohet në mënyrë normale make, kështu që përdoruesit e Windows duan të instalojnë disa Cygwin për vete, ose të merren vetë me Visual Studio dhe bibliotekat.
Zbatimi është i disponueshëm në formën e një programi të konsolës dhe bibliotekës. Të interesuarit mund të mësojnë më shumë rreth përdorimit të kësaj të fundit në readme në depo në Github, lidhjen të cilës do t'i bashkëngjis në fund të postimit. Dhe këtu kalojmë në një përshkrim dhe demonstrim të veprës.
Si të përdorni?
Me kujdes. Imazhet e përdorura mund të zhvendosen, riemërohen dhe kopjohen sipas dëshirës. Sidoqoftë, duhet të jeni jashtëzakonisht të kujdesshëm dhe të mos ndryshoni përmbajtjen e tyre në asnjë mënyrë. Ndryshimi i një biti do të prishë hash-in dhe do ta bëjë të pamundur rikuperimin e informacionit.
Supozoni se pas kompilimit marrim skedarin e ekzekutueshëm f5ar. Ju mund të analizoni madhësinë e bibliotekës për të llogaritur mundësitë e përdorimit të saj duke përdorur flamurin -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. Paketimi bëhet nga ekipi ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], dhe shpaketimi duke përdorur ./f5ar -u [файл архива] [имя восстановленного файла].
Demonstrimi i punës
Për të treguar efektivitetin e metodës, ngarkova një koleksion prej 225 fotografish absolutisht falas të qenve nga shërbimi . Secila prej tyre ka një cilësi pak më të lartë se fotot e përdoruesve të zakonshëm, por gjithsesi. Secila prej tyre u rikodua duke përdorur libjpeg për të neutralizuar ndikimin e veçorive të kodimit të bibliotekës në madhësinë e përgjithshme. Për të treguar shembullin më të keq të të dhënave të kompresueshme, u krijua një skedar i rastësishëm 36 metra (pak më shumë se 5% e madhësisë totale) i shpërndarë në mënyrë uniforme duke përdorur dd.
Procesi i testimit është mjaft i thjeshtë:
$ ls
binary_data dogs f5ar
$ du -sh dogs/
633M dogs/
$ du -h binary_data
36M binary_data
$ ./f5ar -p dogs/ .*jpg binary_data dogs.f5ar
Reading compressing file... ok
Initializing the archive... ok
Analysing library capacity... done in 16.8s
Detected somewhat guaranteed capacity of 48439359 bytes
Detected possible capacity of upto 102618787 bytes
Compressing... done in 32.6s
Saving the archive... ok
$ ./f5ar -u dogs/dogs.f5ar unpacked
Initializing the archive... ok
Reading the archive file... ok
Filling the archive with files... done in 1.2s
Decompressing... done in 17.5s
Writing extracted data... ok
$ sha1sum binary_data unpacked
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 binary_data
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 unpacked
$ du -sh dogs/
563M dogs/Ose një pamje nga ekrani për fansat
Siç mund ta shihni, nga 633 + 36 == 669 megabajt origjinale të të dhënave në hard disk, përfunduam me një 563 më të bukur, duke na dhënë një raport kompresimi prej ~1,188. Ky ndryshim radikal shpjegohet me humbje jashtëzakonisht të vogla, të ngjashme me ato të marra gjatë optimizimit të skedarëve JPEG duke përdorur metoda klasike (si p.sh. tinyjpg). Natyrisht, kur përdoret kompresimi steganografik, informacioni nuk "humbet" thjesht, por përdoret për të koduar të dhëna të tjera.Për më tepër, numri i koeficientëve të "optimizuar" për shkak të përdorimit të F5 është shumë më i vogël se sa me optimizimin tradicional.
Çfarëdo modifikimi që ka, ato janë absolutisht të padukshme për syrin. Nën spoilerin më poshtë, lexuesi mund të vlerësojë ndryshimin si me sy ashtu edhe duke zbritur vlerat e përbërësit të ndryshuar nga origjinali (sa më e heshtur të jetë ngjyra, aq më i vogël është ndryshimi):
Lidhje me imazhe që nuk përshtaten në habrastorage
Origjinali -
Ndryshuar -
ndryshim -
Në vend të një përfundimi
Shpresoj se kam qenë në gjendje ta bind lexuesin se metoda të tilla janë të mundshme dhe kanë të drejtën e jetës. Megjithatë, blerja e një hard disk ose një kanali shtesë (për transmetimin e rrjetit) mund të duket si një opsion shumë më i thjeshtë sesa të përpiqeni të kurseni para në këtë mënyrë. Nga njëra anë, kjo është e vërtetë; zhvillimi i gjerë është shpesh më i thjeshtë dhe më i besueshëm. Por nga ana tjetër, nuk duhet të harrojmë për intensitetin. Në fund të fundit, nuk ka asnjë garanci që nesër do të keni mundësi të vini në dyqan dhe të blini vetë një hard disk një mijë terabyte, por gjithmonë mund t'i përdorni ato që keni tashmë të shtrirë në shtëpi.
->
Burimi: www.habr.com