Results 1 to 11 of 11

Thread: Can compression ALGORITHM be reversed engineered from input & it's compressed file ?

  1. #1
    Member
    Join Date
    Apr 2012
    Location
    London
    Posts
    265
    Thanks
    13
    Thanked 0 Times in 0 Posts

    Can compression ALGORITHM be reversed engineered from input & it's compressed file ?

    How easy with quantum computation ? Can it be prevented ?

  2. #2
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,572
    Thanks
    783
    Thanked 687 Times in 372 Posts
    it's so easy that noone bothers to implement that. you may be first

  3. #3
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    1) It may be possible to guess a known compression method from compressed data.
    There're even "recompression" programs (precomp etc) which make use of this to undo existing compression and apply something better.
    But even simple detection can be pretty hard (for example, lzham streams are encoded for specific window-size value - basically its necessary
    to try multiple codec versions and all possible window-size-log values to attempt decoding).

    2) For some data samples (where the structure is easy to understand and predict from small substrings of data) and static bitcode algorithms
    it may be possible to reverse-engineer an unknown compression method - though even this requires luck and a lot of work.

    3) Universal automatic solution to this task should be equivalent to Kolmogorov compression, and also breaking all cryptography etc.
    According to my estimations in some previous related threads here (based on Planck length and time), even the impossibly perfect quantum computers
    would just add ~150 bits to the key size that can be realistically bruteforced.
    So I'd say that a _new_ adaptive AC-based compression method can't be reverse-engineered from the data.

  4. #4
    Member
    Join Date
    Feb 2020
    Location
    here
    Posts
    18
    Thanks
    6
    Thanked 0 Times in 0 Posts

    Talking

    quantum computing is term for selling more oil and gas as usually
    ordinary computer has one pseudo random number generator(prng)
    quantum computer has n-th true random number generators, where n is quantity of cubits...
    in gaussian distribution it has 0-bits of advantages over ordinary bruteforce...but in human associative style of actions it may be useful may be not
    it is nice to play cossacks with 8 000 units acting independently, that's all for what quantum computing is invented
    for your task in common case set of functions mapping one file to smaller file through instruction sets is countable but very big, that's why this task likes chess game is unsolved for a long time may be till the end of humanity for ia-32 and amd64!i'm sorry can not solved in one defined way but many algorithms and many programs you can get as hex-ray c-style decompiler

  5. #5
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    > it has 0-bits of advantages over ordinary bruteforce

    Well, the main idea of quantum computing is to use elementary particles and laws of physics for computing.
    But even normal electronics have some non-zero probability of errors, and require more and more compensation is circuit design (parity checks, ECC etc).
    And quantum logic has tens of percents of error probability per operation, so it was necessary to invent a whole new type of algorithms as a workaround.
    Still, there's a potential for higher density and parallelism than what we can have with further evolution of semiconductor electronics.

  6. #6
    Member
    Join Date
    Apr 2012
    Location
    London
    Posts
    265
    Thanks
    13
    Thanked 0 Times in 0 Posts
    How many input and compressed file sets would you need to be able reverse engineer ?

    You may also want to design your special input files set !

  7. #7
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    You're talking about this: https://en.wikipedia.org/wiki/Chosen-plaintext_attack
    With billions of samples it should be possible to reverse-engineer normal compression algorithms,
    but its a known case in cryptography, so adding encryption after compression would still beat this type of attacks.

  8. #8
    Member
    Join Date
    Apr 2012
    Location
    London
    Posts
    265
    Thanks
    13
    Thanked 0 Times in 0 Posts
    >>You're talking about this: https://en.wikipedia.org/wiki/Chosen-plaintext_attack
    With billions of samples it should be possible to reverse-engineer normal compression algorithms

    With AI this can be much less than billion ?

    >>but its a known case in cryptography, so adding encryption after compression would still beat this type of attacks.

    Again with quantum AI can reverse engineer despite encryption of compressed output ?

  9. #9
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    > With AI this can be much less than billion ?

    No, unless we're talking about detecting a specific version of a known algorithm, or parameters.

    We basically need to extract the algorithm description from sample comparison...
    at the very least we need to test every path through the algorithm (unique combination of taken branches).

    I guess you can find some complexity estimations for https://en.wikipedia.org/wiki/Fuzzing
    since it does something similar.

    > Again with quantum AI can reverse engineer despite encryption of compressed output ?

    As I said, quantum computing is not magical, its just computing based on elementary particles and physical laws.
    But even if we can test 2^100 keys in parallel, its still only equivalent to reducing the key size by 100 bits...
    which doesn't change anything if full key has 1024 bits.

    Also the actually existing "quantum" hardware is still slower than modern electronics.

  10. #10
    Member
    Join Date
    Apr 2012
    Location
    London
    Posts
    265
    Thanks
    13
    Thanked 0 Times in 0 Posts
    With a few deliberate specific crafted inputs differing from each other in smallest possible adjacent next ( e.g. differ by just 1 single bit only ...etc ) AI neural network may extract some meaningful underlying salient patterns ( in total intelligibible manner to us human ) despite decryptions , which AI Neural Networks are most adapt at ) ?

  11. #11
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    AI/ML/NN are totally useless for cryptography (too slow and inefficient).

Similar Threads

  1. Request on gamedata compressed file
    By theruler in forum Data Compression
    Replies: 0
    Last Post: 29th May 2016, 20:58
  2. Replies: 3
    Last Post: 14th April 2015, 00:49
  3. How to expand .ff compressed files using Precomp & Fsum???
    By Manjunath in forum The Off-Topic Lounge
    Replies: 21
    Last Post: 7th September 2014, 13:47
  4. Best Compression Algorithm for a File Hosting service?
    By Accident in forum Data Compression
    Replies: 4
    Last Post: 27th November 2011, 13:10
  5. BWT with compressed input data
    By Shelwien in forum Data Compression
    Replies: 3
    Last Post: 29th May 2009, 15:16

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •