Cryptographic hash generated using data parallel instructions
A fast cryptographic hash of an input file using multiplication and permutation operations in a parallel processing environment. An example method includes updating an internal state for each of a plurality of packets, the packets being read from an input file. Updating the state for a packet can include injecting the packet into an internal state, mixing the bits of the internal state using multiplication, and shuffling the result of the multiplication so that bits with highest quality are permuted to locations that will propagate most widely in a next multiplication operation. The method also includes performing a reduction on the internal state and repeating the update of the internal state, the reduction, and the injecting a second time. The method may further include finalizing the internal state and storing a portion of the final internal state as a cryptographic hash of the input file.
1. A computer system comprising:
at least one processor; and
memory storing instructions that, when executed by the at least one processor, causes the computer system to perform operations including:
reading an input file into an input buffer;
blocking the input buffer into packets;
repeating, two times:
for each of the packets, updating an internal state comprising bits using the packet by:
injecting the packet into the internal state,
mixing the bits of the internal state using multiplication, and
shuffling the mixed bits of the internal state so that bits with highest quality are permuted to locations that will propagate most widely in a next multiplication operation;
performing a reduction on the internal state; and
injecting a dithering variable into the internal state;
finalizing the internal state; and
storing a portion of the finalized internal state as a cryptographic hash of the input file.
2. The system of claim 1 , wherein the mixing by multiplication is performed on 256 bits in parallel using four Single Instruction Multiple Data (SIMD) vector lanes.
3. The system of claim 2 , wherein the shuffling causes bytes with highest quality to be permuted to low order bytes of a SIMD vector lane and remaining bytes to be permuted to high order bytes of the SIMD vector lane.
4. The system of claim 2 , wherein the shuffling interleaves neighboring vector lanes so that at least some highest quality bytes from a first lane of the neighboring vector lanes and at least some highest quality bytes from a second lane of the neighboring vector lanes are moved to a location in the first lane.
5. The system of claim 1 , wherein an optimization algorithm selects an order of the shuffling.
6. The system of claim 1 , wherein the reduction on the internal state includes a modular reduction.
7. The system of claim 1 , wherein the reduction on the internal state includes discarding at least one vector lane of the internal state.
8. The system of claim 1 , wherein the dithering variable is a constant.
9. The system of claim 1 , wherein the dithering variable is a counter.
10. The system of claim 1 , wherein the dithering variable is a combination of a constant and a counter.
11. The system of claim 1 , wherein the portion stored as the cryptographic hash is the entire finalized internal state.
12. The system of claim 1 , wherein the portion stored as the cryptographic hash is a portion in a lower lane of a 4-lane Single Instruction Multiple Data (SIMD) processor.
13. The system of claim 1 , wherein the instructions cause the computer system to perform further operations including, when the input file exceeds a size of the input buffer:
repeating the reading, the blocking, and the repeating with portions of the input file until reaching an end of the input file,
wherein finalizing the internal state occurs after reaching the end of the input file.
14. The system of claim 1 , wherein when the input file is not a multiple of 32 bytes, the instructions cause the computer system to perform further operations including, for a last packet:
determining a quantity of bytes to be padded in the last packet;
determining a value of a number of bytes at a particular position, the number being equal to the quantity; and
loading the value of the number of bytes to a location of the bytes to be padded.
15. The system of claim 1 , wherein when the input file is not a multiple of 32 bytes, the instructions cause the computer system to perform further operations including:
determining a quantity of bytes to be padded; and
injecting the quantity with the packet into the internal state.
16. A method comprising:
repeating, two times:
updating an internal state comprising bits for each of a plurality of packets, the packets being read from an input file, the updating including:
injecting the packet into the internal state,
mixing the bits of the internal state by multiplying one portion of the internal state by another portion of the internal state, and
shuffling the mixed bits of the internal state so that bits with highest quality are permuted to locations that will propagate most widely in a next multiplication operation, and
performing a reduction on the internal state;
finalizing the internal state; and
storing a portion of the final internal state as a cryptographic hash of the input file.
17. The method of claim 16 , further comprising, as part of the repeating two times, injecting a dithering variable into the internal state after performing the reduction.
18. The method of claim 17 , wherein the dithering variable is a constant.
19. The method of claim 17 , wherein the dithering variable is a counter.
20. The method of claim 17 , wherein the dithering variable is a combination of a constant and a counter.