<OriansJ`>and yes mes-m2 isn't done (entirely my fault) <OriansJ`>mostly because I figure having an easy to debug Lisp interpreter that M2-Planet can build and iterating towards running MesCC seemed preferable to getting Mes.c to be built by M2-Planet (So many C macros and months spent just getting it into shape for GCC to build it) <OriansJ`>anyone have tricks to minimize compute times for crc32 preimage attacks? <OriansJ`>The idea hopefully being that is compute expensive but possible. So that we can throw compute to figure out the crc32/crc64 values that make the stage0 elf binaries easier to catch manipulation (as the crc32/crc64 values is in the binary and calculating a replacement should be significantly more cycles than it would take to honestly just do what is required of it) <OriansJ`>as there are only 2^32 crc32 values possible; let us see how long it takes to bruteforce generating hex0_x86 with its own crc32 value in the ELF padding <OriansJ`>I had to handroll a C version of crc32 to get anything approaching reasonable crunching speed as the debian perl version is just so freaking slow <OriansJ`>my naive version is faster for sub 100MB input files after which the perl version starts being faster <OriansJ`>probably because I am doing something stupid ***Server sets mode: +cnt
<bauen1>OriansJ`: i'm not really sure, but embedding a checksum and self-checking the memory against it will work, but would also hinder maintenance of any form <bauen1>OriansJ`: for now the other ways of defeating (my) backdoor(s) seem to be better <OriansJ`>bauen1: well hex0 binaries don't need maintenance. They can be written once and ignored forever but making life harder for attackers is definitely something worth wasting some time on <OriansJ`>in fact it is assumed that anyone can create their own hex0 binary and should (that way the entire bootstrap is just source) <bauen1>same deal with hex2, but the "table" is in fact just an 8 bytes scratch buffer <bauen1>or not, it stores the label at the end of its own memory without bounds checking <bauen1>OriansJ`: would you accept a PR that modifies hex0-seed to be a bit shorter (and match the text representation to the ones defined in cc_amd64 ? ***nckx is now known as guix-vits
***guix-vits is now known as nckx
<mihi>OriansJ`, it hurts if you call a CRC preimage an "attack". CRC was designed with error correction in mind. But with today's "optimized" table based implementations, the actual algorithm is hidden so well that you cannot see how you can do a CRCn preimage "attack" in O(n) for any CRC function any more... <mihi>Back to the fundamentals: an unoptimized CRC implementation consists of 3 steps: <mihi>S1: Convert the input bytes into an input bit stream, by defining some bit order and optionally flipping some of the bits. The exact way depends on the CRC implementation, but it is trivially reversible. <mihi>S2: Perform a GF2 polynom division (which is just a fancy way of saying "some XORs and some shifts") on the input bitstream to obtain a checksum bitstream (n bits long). This is the interesting step we have to focus on. <mihi>S3: Perform output bit translation/ordering and some flipping to get the byte representation. This is also trivially reversible. <mihi>Some interesting features of this (useful for us): <mihi>P1: if the input bitstream is all zeroes, the crc bitstream is all zeroes too <mihi>P2: If you concatenate the crc bitstream to its input bistream (valid CRC), and treat everything as one input bitstream, its CRC is zero. This is also true in reverse, if you start with an input bitstream that has CRC zero and strip off the last n bytes, they will be the crc of the first x-n bytes. <mihi>P3 (the most interesting one): If you take any input bitstream and XOR it with a (shifted anywhere) representation of its polynomial, the CRC will stay the same <mihi>So, to create a preimage, first do step 1 on the input and reverse step 3 on the desired CRC value. perform step 2 on the bitstream to get its current CRC and concatenate it to the bitstream. <mihi>Now compare the bits from the end with the desired crc bitstream and XOR the generator polynomial wherevery you have a difference. <mihi>Once you've done this, you cut off the last n bits again (which are your desired CRC) and reverse step 1 to get the bytes. <mihi>If you want the change anywhere which is not at the end of the file, you'd have to repeat the XORing a bit more (needing O(b) steps where b is the number of bits you want to shift your change to) <mihi>I know this is very compact; in case you have any questions, either read the Wikipedia article I linked or ask here :) ***luizhenrique is now known as LHLaurini
***`Lion_ is now known as `Lion
***Server sets mode: +cnt
<bauen1>OriansJ`: oh and also would you accept a pr that modifies hex1 and hex2 (and whatever else i find) to ensure they never write/read outside of "allocated" memory (as in obtained by sbrk or loaded explicitely using program load headers) <bauen1>and i think that in the amd64 hex0 the usage of `LOADI32_R..` is slightly misleading (or it's definition in cc_amd64 is), depending on the source it is e.g. 49C7C6 <imm32> or e.g. B8 <imm32> <bauen1>49C7C6 <imm32> is actually a sign extending immediate load, but B8 <imm32> loads the lower half of the register and zeros the upper half (at least on recent processors) <bauen1>There are quite a few cases where B8 <imm32> can be used and is the expected behaviour, but some cases e.g. `LOADI32_R15 -1` (from hex0_amd64.hex0) expect the behaviour of 49C7C6 <imm32> ***Server sets mode: +cnt
***Server sets mode: +cnt