NilFoundation / crypto3-hash

Hashing for =nil; Crypto3 cryptography suite
MIT License
7 stars 9 forks source link

Fix per-bit accumulator consumption #135

Open x-mass opened 7 months ago

x-mass commented 7 months ago

For now hash accumulator interface makes an illusion that it could consume value_seen param (an amount of bits to be consumed from passed data) (methods 1, 2).

Why this happens?

Let's consider the case with SHA3 hash. Say, we have full 0x61 byte (aka 0b01100001) input stream. As stated in specification, SHA3 (underlying Keccak) interprets it as little bit value (least significant bit first). Currently our implementation handles it the following way: add reversed-bit padding, before permutation change data endianness, and read from the right side. I.e., 0x610...0 is input data, padding is added as 0x61060...080 (SHA3 uses 0110*1 padding), then endianness is changed as 0x80...0661 (aka 0b01100001'0...0 -> 0b01100001'00000110'0...0'10000000 -> 0b10000000'0...0'00000110'01100001).

Now, say, we want to add only 6 bits from 0x61 (aka 0b100001, since Keccak uses little bit and counts bits from the least significant). To fit this into our implementation, we need to handle data as 0x21 and to insert few bits of padding to this unfinished byte. I.e., 0x210...0 -> 0xA1010...80 -> 0x80...01A1 (aka 0b00100001'0...0 -> 0b10100001'00000001'0...0'10000000 -> 0b10000000'0...0'00000001'10100001). For now, padding insertion works just fine, since it uses little bit injector. But data consumption does not work as expected, since it interprets values as big bit values (6 bits of 0x61 are 0b011000, not 0b100001).

@x-mass, we do even have tests for this, what are you complaining about?

All sha3_*_accumulator* tests (send blocks to accumulator) inserts incomplete block only as the last one. Thus, it uses this std::move for all blocks except the last one, and the next std::move for the last block (it does not even increase cached_bits value). If the state is empty by the time tests are putting data to accumulator (as here), accumulator use optimization and inserts full word as is. It takes place inside this test, for example.

All sha3_*_preprocessor* tests (send values to accumulator) inserts only 8 bit values, that leads to injecting full bytes as is.

Even if we leave only parts with injector (no direct assignment or std::move to cache), some SHA3 tests fail. Obviously, we should be able to disregard the optimization parts without any side effects.

How to fix?

?

Goals: