iOS Question [SOLVED] DEFLATE Compression

[Star-Dust]

I should compress strings specifically with the Deflate compression algorithm.
You know how it can be done on B4i or Obj-C

P.S: I anticipate the questions ... unfortunately I just need the deflate algorithm and nothing else

 

[OliverA]

Dumb question: Why is the data compressed? Did you enable compression in the negotiations of the connection with the client (I'm guessing here this has something to do with your iHttpServer)? How?

 

[Star-Dust]

Dumb question: Why is the data compressed? Did you enable compression in the negotiations of the connection with the client (I'm guessing here this has something to do with your iHttpServer)? How?

IHttpServer currently does not negotiate with compression for the reason that I cannot decompress browser messages.

To understand the problem I sniffed the communication between jServer and the Browser. JServer accepts deflate compression when negotiating the protocol with the HandShake.

The compressed data is what I put in post # 5. I can read them in clear text because the SW sniffer allows me to also have the decompression of the data sent. So I have the data both in clear and compressed.

I'm trying to understand what compression jServer uses with the Browser when communicating so I can apply this compression to my iHttpServer.

 

[OliverA]

Are you sure deflate is being negotiated? According to this https://github.com/eclipse/jetty.project/issues/288, deflate has been dropped in Jetty

 

[Star-Dust]

Are you sure deflate is being negotiated? According to this https://github.com/eclipse/jetty.project/issues/288, deflate has been dropped in Jetty

Yes, the HandShake is identical.

I did further tests. This is the compressed string sniffed by the jServer

aa 56 4a 49 2c 49 54 b2 8a ae 56 ca 4c 51 b2 52 4a 2a c9 2b 4e cd 4b 51 d2 51 4a 2d 4b cd 2b 01 8a 24 e7 64 26 67 2b d5 c6 02 45 4a 2a 0b 52 81 22 c5 a9 25 8e a5 25 f9 b9 89 25 99 c9 ae 20 55 c5 4a b5 00 00

This is the same string compressed with Deflate, produced by an online tools

ab 56 4a 49 2c 49 54 b2 8a ae 56 ca 4c 51 b2 52 4a 2a c9 2b 4e cd 4b 51 d2 51 4a 2d 4b cd 2b 01 8a 24 e7 64 26 67 2b d5 c6 02 45 4a 2a 0b 52 81 22 c5 a9 25 8e a5 25 f9 b9 89 25 99 c9 ae 20 55 c5 4a b5 00

As you can see the Header changes, instead of AA is AB, also because the resultant is a longer Byte and therefore changes the header

If I pass the sniffed string to the online tools it fails to decompress it, but if in the sniffed string I change the first byte, the header, to AB then it manages to decompress it.

Both CompressedStreams.DecompressBytes and java.util.zip.Inflater do not uncompress either string

 

[Sandman]

This isn't really my expert area, but I remembered me pounding my head into the wall a couple of years back as I was making a bash script, piping things in multiple steps. And the end result wasn't at all what I expected. Turns out that one of the commands took the liberty of adding a newline at the end of its output, which messed up the process and my day.

So my naïve suggestion is to perhaps make sure that you and Erel actually are working on identical input? It's so easy to miss a newline last in the file, which in turn might make the output data one byte longer than expected.

Also: Erels CyberChef screenshot says "Dynamic Huffman Coding", yours say "Fixed Huffman Coding".

 

[Star-Dust]

In java I solved it using java.util.zip.Inflater. Correctly it gave error for the header, in fact to be recognized as inflate the byte array must start with two specific Hex bytes 78,9C (decimal 120,156).

I put them at the beginning of the array and it works in Java.

Deflate.DecompressBytes doesn't work ... so in fact for B4i I'm still on the high seas.

 

[Star-Dust]

This isn't really my expert area, but I remembered me pounding my head into the wall a couple of years back as I was making a bash script, piping things in multiple steps. And the end result wasn't at all what I expected. Turns out that one of the commands took the liberty of adding a newline at the end of its output, which messed up the process and my day.

So my naïve suggestion is to perhaps make sure that you and Erel actually are working on identical input? It's so easy to miss a newline last in the file, which in turn might make the output data one byte longer than expected.

Also: Erels CyberChef screenshot says "Dynamic Huffman Coding", yours say "Fixed Huffman Coding".

The input is the same, but from the last test I think I understand that it depends on the algorithm. Adding in the right header zip.inflater decompresses correctly.

As for Erel's test, you are right he used dynamic encoding, whereas websocket appears to use Fixed encoding. I delete the post

 

[Star-Dust]

In java I solved it using java.util.zip.Inflater. Correctly it gave error for the header, in fact to be recognized as inflate the byte array must start with two specific Hex bytes 78,9C (decimal 120,156).

I put them at the beginning of the array and it works in Java.

Deflate.DecompressBytes doesn't work ... so in fact for B4i I'm still on the high seas.

Update: It seems that in iOs the addition of these header bytes should be avoided. See here

After several compression / decompression comparisons between the CompressedStreams class and the various tools I have come to the final conclusion. That CompressedStreams also requires the 78.9C header which must be added if it is not there.

But CompressedStreams version B4i unlike that B4J and B4a requires at the end of the sequence of the compressed bytes an additional 4-byte queue for data verification or CRC.
In the websocket protocol they are not transmitted, so to make the strings received from the Browser compatible with CompressedStreams, this queue of 4 verification data must be added.

In the various websocket documentations it is not specified, I guess, it is because the decompression algorithm of the other platforms does not require it.

Now don't ask me how it's calculated that I don't even know yet. Now I need a good decryptor mathematician ...

+---+---+
|CMF|FLG| (2 bytes - Defines the compression mode - More details below)
+---+---+---+---+
| DICTID | (4 bytes. Present only when FLG.FDICT is set.) - Mostly not set
+---+---+---+---+
|...compressed data...| (variable size of data)
+---+---+---+---+
| ADLER32 | (4 bytes of checksum)
+---+---+---+---+

 

[agraham]

From the title it looks like an ADLER32 hash in which case the algorithm is here
Adler-32 - Wikipedia

 

[Star-Dust]

From the title it looks like an ADLER32 hash in which case the algorithm is here
Adler-32 - Wikipedia

Yes, I found it, but unfortunately it is an uncompressed checksum of the original data, so I can't get it.

I am studying another way. The header indicates if there is the checsum in the flag. I am trying to modify the FLAG and maybe it will work

 

[agraham]

unfortunately it is an uncompressed checksum of the original data

Ah! I missed that

 

[Star-Dust]

Header 78 9C indicates that there is no checksum:

bits 0 to 4 FCHECK (check bits for CMF and FLG)
bit 5 FDICT (preset dictionary)
bits 6 to 7 FLEVEL (compression level)

The dictionary is a sequence of bytes which are initially fed to the compressor without producing any compressed output. DICT is the Adler-32 checksum of this sequence of bytes

9C = 10011100
10= FLevel
0 = FDIC (CheckSUM)
11100=FCHECK (value must be such that CMF and FLG, when viewed as a 16-bit unsigned integer stored in MSB order is a multiple of 31.)

So correctly the java decompressor interprets the header without a checsum request, while the iOs decoder interprets whatever the bit is as if the checksum is required.

Someone else has already faced this problem

Zlib for Mono/.Net without a known Checksum

I need to implement a special ZLib implementation which should run under .Net and Mono. The data /string messages are received via a socket and thus the checksum is missing. This is about raw strin...

stackoverflow.com

 

[Star-Dust]

At this point there seems to be no way out, not being able to retrieve the checksum and taking into account that CompressedStreams requires it.

Also considering that I have studied and studied and re-studied RFCs many times to understand the problem and having understood the coding algorithm, I try to create the decoding procedure based on this example code.

Huffman Coding Compression Algorithm | Techie Delight

Huffman coding (also known as Huffman Encoding) is an algorithm for doing data compression, and it forms the basic idea behind file compression. This post talks about the fixed-length and variable-length encoding, uniquely decodable codes, prefix rules, and Huffman Tree construction.

www.techiedelight.com

Obviously it is not complete but it leads the way

 

[Sandman]

At this point there seems to be no way out

This is how Apache does it, perhaps it can help?

httpd/modules/filters/mod_deflate.c at 7c5e4c9ab2861dd877156be38edc1d110d234f68 · apache/httpd

Mirror of Apache HTTP Server. Issues: http://issues.apache.org - apache/httpd

github.com

And here's where deflate is mentioned in the Cherokee source:

Build software better, together

GitHub is where people build software. More than 225 million people use GitHub to discover, fork, and contribute to over 800 million projects.

github.com

I imagine there are lots of other webservers that you could take inspiration from also:

Comparison of web server software - Wikipedia

en.m.wikipedia.org

 

[Star-Dust]

Thanks I will watch them.

I have already started to implement the Delfate algorithm, the code works but still missing the creation of the dictionary which do not go found documentation. Of course, if a ready-made library worked, I would save time.

But I'll come back to this in a few days, I stopped work to fix this and now I have to recover

 

[OliverA]

The kicker is that compression, as much as of is desirable for reducing network traffic, also introduces security issues, even with encrypted data.

A brief analysis of data compression security issues

By Vinicius Oliveira

sidechannel.tempestsi.com

 

[Star-Dust]

The kicker is that compression, as much as of is desirable for reducing network traffic, also introduces security issues, even with encrypted data.

A brief analysis of data compression security issues

By Vinicius Oliveira

sidechannel.tempestsi.com

It would be interesting to know how they recover the original data from the packet size only. I can't even use legitimate means

 

[Star-Dust]

SolvedI found a solution in B4X that works on all platforms.
fixed Huffman (fixed Huffman coding) RFC 1951 sez. 3.2.6.

[B4X] fixed Huffman coding - RFC 1951 sez. 3.2.6. (Deflate)

Sometimes you have communication problems such as with webSocket communications that don't use zlib (RFC 1950), which includes a 2-byte header + trailing Adler-32 checksum. The WebSocket permessage-deflate (RFC 7692) requires raw DEFLATE (RFC 1951), i.e. the compressed stream without any...

www.b4x.com