SHA-512 cannot be really run on a 32-bit ARM microcontroller since it uses the 64-bit constants, but since SHAKE-256 uses only 32-bit values, can it be run on a microcontroller with 32-bit registers?

  • 5
    $\begingroup$ Do you really know how to implement 64-bit registers on 32-bit? It has even 8-bit implementations Efficient Implementation of the SHA-512 Hash Function for 8-bit AVR Microcontrollers $\endgroup$ – kelalaka Apr 18 at 16:12
  • 2
    $\begingroup$ FWIW, SHAKE also uses 64 bit arithmetic; like all Keccak-based standards, it uses a Keccak[1600] sponge, which uses 25 lanes of 64 bits. $\endgroup$ – Ruben De Smet Apr 19 at 7:20
  • 4
    $\begingroup$ ARM microcontrollers are Turing-complete (except for finite RAM), and can compute anything that's computable on larger machines. Most ISAs, including ARM have instructions that help handling integers wider than one register, when any special help is needed (e.g. add-with-carry). For 64-bit rotates, it might cost 4 ARM instructions (2 per half). $\endgroup$ – Peter Cordes Apr 19 at 9:41
  • 1
    $\begingroup$ "SHA512 cannot be really run on a 32bit ARM microcontroller" is not correct. I've implemented 32-bit integer support for a 8 bit microcontroller using 16 bit constructs. 32 bit is just the main register size in your case. In principle if a machine is Turing complete, it can perform any deterministic operation given enough time / memory. If you want 64 bit computations to be run then you can. How much overhead this requires depends on the function, the implementation and of course the platform. Shifts are easy, signed addition harder etc. $\endgroup$ – Maarten Bodewes Apr 19 at 11:05
  • 2
    $\begingroup$ @MaartenBodewes: actually, the ARM has an "ADC" (add with carry) instruction; that means you can do a 64 bit add with just an ADD/ADC instruction pair. 64 bit shifts/rotates are somewhat harder (in that it involves masking, etc), but still not that difficult... $\endgroup$ – poncho Apr 19 at 12:50

SHA512 cannot be really run on a 32bit ARM microcontroller since it uses the 64bit constants,

Sure it can; a 32 bit ARM microcontroller can do the 64 bit additions (by performing the addition in 2 32 bit steps and including the carry from one to the other); it can also perform the 64 bit shifts/rotates required by breaking up the operation into multiple steps.

Now, it won't be quite as efficient as it would be if the processor handled 64 bit operations natively, but that's quite different from saying it can't do it at all.

since SHAKE256 uses only 32-bit values, can it be run on a microcontroller with 32bit registers?

Again, the microcontroller is quite capable of performing all the operations required.

What I don't know (and is not immediately obvious) is which would perform faster on an ARM; SHA-512 or SHAKE256 (and that might depend on the size of the input...)

  • $\begingroup$ as I see, everything is possible, but is it worth doing shake256 on 32bit ARM device? or SHAKE128 is the max one should consider for these bit values $\endgroup$ – user89628 Apr 18 at 21:06
  • 2
    $\begingroup$ @user89628: the only difference between SHAKE128 and SHAKE256 is the rate/capacity (that is, SHAKE128 devotes less of the permutation to internal state); other than SHAKE256 being somewhat less efficient (because less input can be handled per permutation during the absorb phase, and less output is generated per permutation during the squeeze phase), there is no difference $\endgroup$ – poncho Apr 18 at 21:24

Adding information to the answer of poncho.

The predominant factor that slows down the hashing operation for SHA512 is the amount of clock cycles required to perform a compression function. For SHAKE256, this is the Keccak permutation.

For SHA512, the input string is preprocessed before actually performing the compression functions. First, a "$1$" bit is padded to the input string $M$. A 128 bit number $L$ is used to represent the size of the pre-processed string (in bits). Finally, the padded string has a length of $M + 1 + K + L = k\cdot 1024$ bits, where $1024$ is the block size of SHA512. $K$ "$0$" bits are added in-between the "$1$" bit and the number $L$ such that the length of the processed string is a multiple of the block size ($1024$). This means that the amount of compression functions in function of the input string is equal to $$ P_{\text{SHA512}} = \left\lceil \frac{M + 128 + 1}{1024} \right\rceil $$ Thus SHA512 needs to perform an additional compression function every 895 bits.

SHAKE256 uses the Keccak construction, which has an internal state size of $1600$ bits. This state is divided into a rate $r$ and a capacity $c$. The rate size for SHAKE256 is $1088$ bits. Keccak uses a sponge construction. This construction has two states: the absorbing state and the squeezing state, where data is XORed into the rate $r$ and data is XORed out of the rate $r$ respectively. An input string is also preprocessed, where "$1111$" is padded to the input string (for SHAKE256).

In the absorbing state, every time the rate $r$ is filled with the input string, a Keccak permutation is performed. This is done until the whole processed input string is XORed into the state. Then, an additional Keccak permutation is calculated when switching from the absorbing state to the squeezing state. In the squeezing state, every time the rate $r$ is squeezed out into an output string, a Keccak permutation is performed. This results in the amount of permutations needed for SHAKE256 being $$ P_{\text{SHAKE256}} = \left\lfloor \frac{L+4}{1088} \right\rfloor + 1 + \left\lfloor \frac{Z}{1088} \right\rfloor $$

Where $L$ is the length of the preprocessed input string and $Z$ is the length of the output string. If we assume the extended output function of SHAKE256 is not used, then the last term of the addition is 0, since the output length is 512 bits. Thus, every 1084 bits an additional permutation is performed.

If we know the amount of cycles needed for each permutation/compression function, then we can calculate an estimate of the time required to perform a hash.

I performed this test on a Zolertia RE-Mote (using CC2538) which is an ARM Cortex-M3. For the compression function of SHA512 took $455.49$µs and the Keccak permutation took $679.38$µs.

Overall, SHA512 will be faster than SHAKE256, unless the input size is between 895 and 1084 bits. We can show this in a plot. However, this is an estimate and only applicable for the Zolertia RE-Mote.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.