Cryptographic hash generated using data parallel instructions

Patent metadata

Field	Value
Publication number	US-10833847-B2
Application number	US-201815902820-A
Country	US
Kind code	B2
Filing date	Feb 22, 2018
Priority date	Feb 28, 2017
Publication date	Nov 10, 2020
Grant date	Nov 10, 2020

Abstract

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.

First claim

What is claimed is:

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.

Assignees

• Google Llc

Inventors

• Wassenberg Jan
• Alakuijala Jyrki Antero

Classifications

• G06F9/3887

  controlled by a single instruction for multiple data lanes [SIMD] · CPC title

• H04L9/0643 Primary

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title

• H04L9/34

  Bits, or blocks of bits, of the telegraphic message being interchanged in time {(for speech signals H04K1/06)} · CPC title

• H04L9/3242

  involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC · CPC title