Mike CvetFollowBetter Programming--ListenShareMy first hobby project for learning Rust was implementing cryptographic Hash algorithms [MD5, SHA-2, SHA-3]. The latter, SHA-3, was the most challenging implementation.That was due to a) substantial differences in algorithm design from the more familiar MD5 and SHA predecessors and b) fewer and less intuitive reference implementations and algorithm explanations. In this article, I’ll briefly summarize some high-level differences between SHA-3 and earlier algorithms and then walk through its implementation.The high-level structure of MD5, SHA-1, and SHA-2 is fairly similar; these algorithms are based on the Merkle-Damgård Construction. This is a specific methodology for sequentially chaining chunks of the input message together through a one-way compression Function (which may be a composite of several different operations). These are also often built from block ciphers.From ten thousand feet, these algorithms look like this:The compression function performs a series of nonlinear bitwise mixing of state, constant values, and message input bits. Here’s an example from part of SHA-2’s compression function:This hash construction technique suffers from a variety of vulnerabilities, and the approach taken in SHA-3 is different.SHA-3 was released by NIST in 2015 and is based on a hash algorithm called Keccak, introduced in 2012. I’ll use these terms interchangeably below. Rather than relying on the Merkle-Damgård process, SHA-3 / Keccak uses a technique called sponge construction.From ten thousand feet, it looks roughly like this:I won't try to cover many complex properties of this approach here. A couple of high-level points are:I’ll walk through how SHA-3 works in more detail below.Padding is straightforward in SHA-3 and resembles approaches to padding in earlier hash algorithms. The goal of padding is to extend the length of the input message to a multiple of the “rate,” a value defined in this table as r , allowing for easy chunking.A 0x06 must be appended right after the message, even if the message is already a multiple of r. Zero or more zero bytes are added until the Array length is 1 byte less than a multiple of r, and then a 0x80 is concatenated as the last byte.In the special case where the input message length is equal to r — 1, these two delimiters are concatenated together as 0x06 | 0x80 in a single byte.You can see this implementation here in Rust.One interesting note, however, is that the SHA-3 specification introduces a slight change from the Keccak algorithm specification — in the padding definition. The Keccak algorithm appends 0x01 right after the message:The SHA-3 specification changed the initial 0x1 to 0x6. This means that even though SHA-3 is based on Keccak, the Keccak hash of a message will result in a different digest output than SHA-3. The difference here is just three bits in the padding, but the digest value will be completely different due to the avalanche effect.The algorithm specification defines the state array as a three-dimensional array of bits, depending on the configuration and value of parameter w, ranging from 25 to 1600 total bits.This state modeling wasn’t particularly helpful for me; it was much easier to think about the state as a 5x5 array of 64-bit integers (u64), which captured the maximal state size of 1600 bits. Unlike other hash algorithms, the state isn’t initialized to a set of magic numbers but just to zero.The input message is chunked into 512-bit blocks, which is equivalent to 8 u64. Each of these integers is then “absorbed” into the state, which means XOR-ing the inbound integer into a corresponding location in the state.After each block of eight u64 chunks is absorbed, the state is permuted.The permutation step is 24 rounds of execution of five functions on the state data. Each round results in an irreversible intermediate permutation of bits in the state.Each of these functions performs a mutation on some plane of the state array. For example, the effect of rho is illustrated here, visualizing a “sheet” or column of full integers in the state, using the 3D state modeling from earlier:This particular function performs an integer rotation on each u64 in the state array, where the rotation offsets are defined in the Keccak summary. This particular function is coupled with pi, which rotates the placement of each u64 in the state array. It’s a little like rotating a Rubik’s Cube.I’ve taken care to describe and cite the specific implementation details of each of these functions (theta, rho, pi, chi, iota) in code for those interested.The final step is extracting the contents of the state array into an output byte vector before base-64 encoding. I found the Keccak pseudocode unintuitive; the NIST pseudocode under “sponge construction” was clearer.Earlier on, I outlined the general differences between this approach and older hash function techniques for extracting digest values from the hash state. The output bytes are pulled in batches from the beginning of the state array (as in state[0][0]). After reaching a certain length, the rest of the state is discarded, and the entire array goes through another round of 24 permutations.The final step is encoding the bytes in base 64.For readers looking for a plain walkthrough or readable implementation of SHA-3, hopefully, you found this useful.As for Rust itself, here are a few thoughts:----Better ProgrammingI’m a DE at LinkedIn, helped build Twitter, was an early engineer at a couple startups with successful exits, and used to build native code debuggers for LinuxMike Cvet--1Sergei SavvovinBetter Programming--12Dmitry KruglovinBetter Programming--32Mike CvetinBits and Pieces--Rico FritzscheinLevel Up Coding--24Arslan MirzainLevel Up Coding--3The Coding DiariesinThe Coding Diaries--114Bartłomiej ŻylińskiinSoftwareMill Tech Blog--Ignacio de Gregorio--32SotoEstevezinBetter Programming--HelpStatusWritersBlogCareersPrivacyTermsAboutText to speechTeams