Ketika kita berbicara tentang steganografi, orang-orang berpikir tentang teroris, pedofil, mata-mata, atau, paling banter, kriptoanarkis dan ilmuwan lainnya. Dan sungguh, siapa lagi yang mungkin membutuhkannya bersembunyi sesuatu dari mata luar? Apa manfaatnya bagi orang biasa?
Ternyata ada satu. Oleh karena itu hari ini kami akan mengompresi data menggunakan metode steganografi. Dan pada akhirnya, pembaca bahkan akan dapat menggunakan arsip foto berharga mereka dalam format JPEG untuk menambah jumlah gigabyte gratis pada sistem file.
Apa?
Jika pembaca ingat, steganografi adalah algoritma aneh yang memungkinkan untuk menyembunyikan keberadaan satu informasi di dalam informasi lainnya. Dalam bahasa yang lebih sederhana: gambar + file == kira-kira gambar yang sama, tetapi tidak sepenuhnya (bisa ada apa saja selain gambar, tetapi biasanya semuanya lebih jelas di dalamnya). Seharusnya tidak ada cara mudah untuk menentukan apakah ada sesuatu di dalam atau tidak.
Tetapi jika yang satu tidak dapat dibedakan dengan yang lainnya, apakah ada perbedaan sama sekali? Dari sudut pandang konsumen, pengguna tidak peduli dengan ketepatan matematis (dicerminkan oleh sekumpulan bit tertentu), hanya apa yang dirasakan olehnya.
Sebagai contoh, mari kita lihat tiga gambar seekor anjing lucu:
Hati-hati, JPEG!
Meskipun perbedaan ukurannya sangat besar, hanya sedikit orang yang akan memilih versi ketiga. Di sisi lain, perbedaan antara dua foto pertama tidak begitu mencolok, dan jumlah informasi di dalamnya (dari sudut pandang saya) bisa jadi sama.
Prinsip ini sendiri sudah lama dan telah dieksploitasi secara aktif oleh metode kompresi informasi yang hilang selama bertahun-tahun. Namun menghancurkan bukanlah membangun; kami tertarik pada sisi yang lebih maju dari permasalahan ini. Apakah mungkin untuk menyematkan informasi ukuran tambahan N ke file sehingga ukurannya bertambah M < N, tetapi perubahannya tidak terlihat oleh pengguna?
Tentu saja Anda bisa. Namun ada baiknya segera membuat beberapa reservasi:
- Pertama, metode tersebut harus bersifat universal dan memberikan hasil positif pada sebagian besar data masukan. Artinya, rata-rata, untuk input acak, seharusnya terdapat penurunan aktual dalam jumlah informasi yang disimpan. βRata-rataβ berarti hal sebaliknya mungkin terjadi, namun tidak boleh mendominasi.
- Kedua, ukuran wadah yang dikompresi sebelum menyematkan informasi harus lebih besar daripada modifikasinya yang dikompresi dengan cara serupa. Sekadar menyematkan sekumpulan bit ke dalam gambar BMP menggunakan metode LSB bukanlah kompresi steganografi, karena, setelah dijalankan melalui semacam DEFLATE, gambar asli kemungkinan besar akan terlihat lebih kecil.
- Ketiga, hasilnya harus dilakukan dan dibandingkan dengan data yang telah dikompresi dengan metode klasik. Ini akan menghilangkan efek probabilistik dari perbedaan redundansinya dan memberikan kompresi yang lebih efisien dalam kasus umum.
Dimana?
Penggunaan steganografi menyiratkan bahwa, selain informasi terkompresi, kita memerlukan wadah untuk menyematkannya. Jumlah maksimum informasi yang disematkan sangat bergantung pada properti individual, namun jauh lebih mudah untuk menskalakannya dengan jumlahnya. Oleh karena itu, format wadah harus umum sehingga pengguna memiliki cukup wadah untuk mendapatkan manfaat dari proses βkompresiβ.
Dalam konteks ini, file grafik, audio, dan video adalah kandidat yang baik. Namun, karena beragamnya format, codec, dll., dalam praktiknya kita hanya mempunyai pilihan yang tidak begitu banyak.
Mengingat semua ini, pilihan saya jatuh pada JPEG. Hampir semua orang memilikinya, ini banyak digunakan baik untuk keperluan pribadi maupun bisnis, hampir menjadi format de facto untuk sebagian besar gambar.
Tergantung?
Berikutnya ada diagram dan deskripsi dekat dan teknis tanpa banyak penjelasan, sehingga bagi yang berminat dapat melewatinya dengan menggulir ke bagian βTeknologi Tinggiβ.
Fitur umum
Untuk menyematkan data di suatu tempat, Anda harus menentukan terlebih dahulu di mana. Terdapat sejumlah foto yang berbeda pada sistem file, dan pengguna mungkin hanya ingin menggunakan sedikit saja. Kami akan menyebut kumpulan wadah yang diinginkan sebagai perpustakaan.
Ini terbentuk dalam dua kasus: sebelum kompresi dan sebelum dekompresi. Dalam kasus pertama, Anda cukup menggunakan sekumpulan nama file (atau lebih baik lagi, ekspresi reguler untuk file tersebut), tetapi dalam kasus kedua, diperlukan sesuatu yang lebih andal: pengguna dapat menyalin dan memindahkannya ke dalam sistem file , sehingga mencegah mereka diidentifikasi dengan benar. Oleh karena itu, hashnya perlu disimpan (md5 sudah cukup) setelah semua modifikasi dilakukan.
Dalam hal ini, tidak ada gunanya melakukan pencarian awal menggunakan ekspresi reguler di seluruh sistem file, cukup menentukan direktori root tertentu. File arsip khusus akan disimpan di dalamnya, yang akan berisi hash tersebut, bersama dengan informasi meta lainnya yang diperlukan untuk pemulihan informasi terkompresi selanjutnya.
Semua ini berlaku sama untuk implementasi algoritma kompresi data steganografi apa pun. Proses kompresi dan pemulihan data itu sendiri bisa disebut packing dan unpacking.
F5
Sekarang sudah jelas apa yang kami lakukan dan mengapa, tinggal menjelaskan algoritma untuk mencapai tujuan tersebut. Mari kita ingat kembali proses pengkodean file JPEG (berkat wiki dari Perpustakaan Nasional Bauman):
Melihatnya, ada baiknya segera memberikan beberapa komentar:
- Ukuran file JPEG dapat dianggap optimal bahkan tanpa mencoba mengompresnya dengan semacam Winrar;
- Hanya informasi yang disimpan (yang merupakan keluaran dari transformasi kosinus diskrit, DCT) yang dapat dimodifikasi untuk memberikan setidaknya kinerja yang dapat diterima.
- Agar tidak kehilangan data pada skala industri yang terlihat oleh pengguna, perlu dilakukan modifikasi minimal pada setiap gambar;
Seluruh rangkaian algoritme cocok dengan kondisi ini, yang dapat Anda pahami sendiri . Yang paling canggih di antaranya adalah algoritma oleh Andreas Westfeld, bekerja dengan koefisien DCT dari komponen kecerahan (mata manusia paling tidak sensitif terhadap perubahannya). Tata letak umumnya saat bekerja dengan file JPEG yang ada ditampilkan sebagai berikut:
Blok F5 menggunakan teknik penyematan tingkat lanjut berdasarkan pengkodean matriks. Pembaca dapat mempelajari lebih lanjut tentang hal itu dan algoritma itu sendiri pada tautan di atas, namun kami terutama tertarik pada kenyataan bahwa dengan bantuannya Anda dapat membuat lebih sedikit perubahan ketika menyematkan jumlah informasi yang sama, semakin besar ukuran wadah yang digunakan. , dan untuk menjalankan Algoritme hanya perlu melakukan operasi pengkodean Huffman dan RLE (de) yang sederhana.
Perubahan itu sendiri dilakukan pada koefisien bilangan bulat dan dikurangi dengan mengurangi nilai absolutnya sebanyak satu, yang secara umum memungkinkan penggunaan F5 untuk kompresi data. Intinya adalah bahwa koefisien yang dikurangi dalam nilai absolut kemungkinan besar akan menempati lebih sedikit bit setelah pengkodean Huffman karena distribusi statistik nilai dalam JPEG.
Jika nol terbentuk (yang disebut reduksi), jumlah informasi yang disimpan akan dikurangi berdasarkan ukurannya, karena koefisien independen sebelumnya akan menjadi bagian dari urutan nol yang dikodekan RLE:
Modifikasi
Perlindungan dan kompresi data merupakan masalah ortogonal, sehingga permutasi kata sandi rahasia dari algoritma asli dapat diabaikan. Selain itu, kita perlu tahu persis bagaimana cara mengekstrak data, sehingga semua informasi yang diperlukan untuk ini (wadah mana yang digunakan, dalam urutan apa, dll.) harus dicatat dalam file terpisah dan dibuka untuk dibaca gratis oleh pengarsip.
Algoritme asli dirancang untuk mengirimkan pesan rahasia, sehingga hanya bekerja dengan satu wadah pada satu waktu, dengan asumsi bahwa pengguna sendiri yang akan memecahnya menjadi beberapa bagian jika perlu, jika ada. Selain itu, ketika tertanam secara terpisah di setiap wadah, Anda perlu mengetahui terlebih dahulu berapa banyak bit data yang akan dimasukkan ke dalam setiap wadah. Oleh karena itu, koefisien setiap elemen perpustakaan harus digabungkan menjadi satu abstrak besar dan dikerjakan sesuai dengan algoritma aslinya.
Karena F5 asli mengizinkan hingga 12% ukuran kontainer, modifikasi ini juga akan meningkatkan kapasitas maksimum: "hingga 12%" dari ukuran seluruh perpustakaan lebih besar dari atau sama dengan jumlah "hingga 12% " dari masing-masing elemennya.
Skema umum yang dikodifikasikan adalah sebagai berikut:
Algoritma itu sendiri
Sekarang saatnya menjelaskan algoritme itu sendiri dari awal hingga akhir, agar pembaca tidak bingung:
- Pengguna mendefinisikan data biner yang dapat dikompresi M dan perpustakaan L menggunakan ekspresi reguler dan direktori root pencarian;
- Dalam urutan kemunculannya di FS, elemen perpustakaan membentuk MC:
- Serangkaian koefisien C diterjemahkan dari data file;
- MC <- MC | C;
- Parameter k ditentukan berdasarkan ketimpangan yang mengerikan:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Diambil berikutnya
n = (1 << k) - 1bit paling tidak signifikan dari elemen bukan nol dari MC dan ditulis kea:- Fungsi hash ajaib dipertimbangkan
f, mewakili kata n-bitake k-bits; - Jika
s == 0, maka tidak perlu mengubah apa pun dan algoritme beralih ke koefisien berikutnya; - Kurangi nilai absolut dari koefisien yang bertanggung jawab
s-hei sedikit bicaraa; - Jika akibat reduksi terjadi reduksi (koefisiennya menjadi 0), maka ulangi langkah dari awal;
- Fungsi hash ajaib dipertimbangkan
- Semua koefisien dikodekan oleh RLE dan Huffman, ditulis ke file sumber;
- Parameter k ditulis ke file arsip;
- Hash MD5 dihitung dari setiap file L sesuai urutan lokasi aslinya dan ditulis ke file arsip.
Teknologi tinggi
Bentuk algoritma yang naif dan implementasi dalam bahasa tingkat tinggi lainnya (terutama dengan pengumpulan sampah) akan memberikan kinerja yang buruk, jadi saya mengimplementasikan semua kerumitan ini dalam C murni dan melakukan sejumlah optimasi baik dari segi kecepatan eksekusi dan memori (Anda tidak tahu berapa berat gambar-gambar ini tanpa kompresi bahkan sebelum DCT). Namun demikian, pada awalnya kecepatan eksekusi masih jauh dari yang diinginkan, jadi saya tidak akan menjelaskan keseluruhan proses dan metode yang digunakan.
Lintas platform dicapai dengan menggunakan kombinasi perpustakaan libjpeg, pcre dan tinydir, dan kami berterima kasih kepada mereka. Secara default, semuanya dikompilasi melalui normal make, jadi pengguna Windows ingin menginstal beberapa Cygwin untuk mereka sendiri, atau menangani Visual Studio dan perpustakaan mereka sendiri.
Implementasinya tersedia dalam bentuk utilitas konsol dan perpustakaan. Mereka yang tertarik dapat mengetahui lebih lanjut tentang penggunaan yang terakhir di readme di repositori di Github, tautannya akan saya lampirkan di akhir posting. Dan di sini kita beralih ke deskripsi dan demonstrasi karya tersebut.
Bagaimana cara menggunakannya?
Dengan hati-hati. Gambar bekas dapat dipindahkan, diganti namanya, dan disalin sesuai keinginan. Namun, Anda harus sangat berhati-hati dan tidak mengubah isinya dengan cara apa pun. Mengubah sedikit pun akan mengganggu hash dan membuat informasi tidak dapat dipulihkan.
Misalkan setelah kompilasi kita mendapatkan file executable f5ar. Anda dapat menganalisis ukuran perpustakaan untuk menghitung kemungkinan penggunaannya menggunakan bendera -a: ./f5ar -a [ΠΏΠ°ΠΏΠΊΠ° ΠΏΠΎΠΈΡΠΊΠ°] [Perl-ΡΠΎΠ²ΠΌΠ΅ΡΡΠΈΠΌΠΎΠ΅ ΡΠ΅Π³ΡΠ»ΡΡΠ½ΠΎΠ΅ Π²ΡΡΠ°ΠΆΠ΅Π½ΠΈΠ΅]. Pengemasan dilakukan oleh tim ./f5ar -p [ΠΏΠ°ΠΏΠΊΠ° ΠΏΠΎΠΈΡΠΊΠ°] [Perl-ΡΠΎΠ²ΠΌΠ΅ΡΡΠΈΠΌΠΎΠ΅ ΡΠ΅Π³ΡΠ»ΡΡΠ½ΠΎΠ΅ Π²ΡΡΠ°ΠΆΠ΅Π½ΠΈΠ΅] [ΡΠΏΠ°ΠΊΠΎΠ²ΡΠ²Π°Π΅ΠΌΡΠΉ ΡΠ°ΠΉΠ»] [ΠΈΠΌΡ Π°ΡΡ
ΠΈΠ²Π°], dan membongkar menggunakan ./f5ar -u [ΡΠ°ΠΉΠ» Π°ΡΡ
ΠΈΠ²Π°] [ΠΈΠΌΡ Π²ΠΎΡΡΡΠ°Π½ΠΎΠ²Π»Π΅Π½Π½ΠΎΠ³ΠΎ ΡΠ°ΠΉΠ»Π°].
Demonstrasi karya
Untuk menunjukkan keefektifan metode ini, saya mengunggah koleksi 225 foto anjing gratis dari layanan tersebut . Masing-masing memiliki kualitas yang sedikit lebih tinggi daripada foto pengguna biasa, tapi tetap saja. Masing-masing dikodekan ulang menggunakan libjpeg untuk menetralisir dampak fitur pengkodean perpustakaan pada ukuran keseluruhan. Untuk menunjukkan contoh terburuk dari data yang dapat dikompresi, file acak sepanjang 36 meter (sedikit lebih dari 5% dari total ukuran) yang terdistribusi secara seragam dihasilkan menggunakan dd.
Proses pengujiannya cukup sederhana:
$ 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/Atau tangkapan layar untuk penggemar
Seperti yang Anda lihat, dari data asli 633 + 36 == 669 megabyte di hard drive, kami mendapatkan 563 yang lebih bagus, sehingga memberi kami rasio kompresi ~1,188. Perbedaan radikal ini disebabkan oleh kerugian yang sangat kecil, serupa dengan yang diperoleh saat mengoptimalkan file JPEG menggunakan metode klasik (seperti tinyjpg). Secara alami, ketika menggunakan kompresi steganografi, informasi tidak hanya βhilangβ, tetapi digunakan untuk menyandikan data lain. Selain itu, jumlah koefisien yang βdioptimalkanβ karena penggunaan F5 jauh lebih sedikit dibandingkan dengan optimasi tradisional.
Apapun modifikasinya, sama sekali tidak terlihat oleh mata. Di bawah spoiler di bawah ini, pembaca dapat mengevaluasi perbedaannya baik secara langsung maupun dengan mengurangkan nilai komponen yang diubah dari aslinya (semakin redup warnanya, semakin kecil perbedaannya):
Tautan ke gambar yang tidak muat di habrastorage
Asli -
Diubah -
Perbedaan -
Alih-alih sebuah kesimpulan
Saya harap saya dapat meyakinkan pembaca bahwa cara-cara seperti itu mungkin dan mempunyai hak untuk hidup. Namun, membeli hard drive atau saluran tambahan (untuk transmisi jaringan) mungkin tampak seperti pilihan yang lebih sederhana daripada mencoba menghemat uang dengan cara ini. Di satu sisi, hal ini benar; pengembangan ekstensif seringkali lebih sederhana dan lebih dapat diandalkan. Namun di sisi lain, kita tidak boleh melupakan intensnya. Lagi pula, tidak ada jaminan bahwa besok Anda akan dapat datang ke toko dan membeli hard drive seribu terabyte lagi, tetapi Anda selalu dapat menggunakan hard drive yang sudah Anda miliki di rumah.
->
Sumber: www.habr.com