3
$\begingroup$

SHA-2 makes use of non-ARX non-linear operators such as the Choice and Majority functions:

\begin{align} \mathsf{Ch}(E,F,G) &= (E \wedge F) \oplus (\neg E \wedge G)\\ \mathsf{Ma}(A, B, C) &= (A \wedge B) \oplus (A \wedge C) \oplus (B \wedge C) \end{align}

Why is it considered an ARX cipher the same way other primitives such as ChaCha or Blake? If anything, the greater diversity in SHA-2 makes it more secure - perhaps the NSA knew something in 2000 we still don't?

$\endgroup$
4
  • 1
    $\begingroup$ Can you list where is it called ARX other than this crypto.stackexchange.com/q/15953/18298 $\endgroup$
    – kelalaka
    Oct 31, 2023 at 8:05
  • 3
    $\begingroup$ Did you know that you can actually convert images to Latex using ChatGPT nowadays? Otherwise we've got MathJax information on Meta. Please use that instead of posing images. $\endgroup$
    – Maarten Bodewes
    Oct 31, 2023 at 11:19
  • $\begingroup$ @MaartenBodewes I tried ChatGPT 3.5 but there is no upload choice. Tried with Bard and it failed on the $\mathsf{Ch}$ and produce incorrect on the $\mathsf{Ma}$ $\endgroup$
    – kelalaka
    Nov 1, 2023 at 17:54
  • $\begingroup$ @kelalaka Oh, yeah, sorry. I find it important enough to have a subscription for ChatGPT 4, but at 20 dollar a month I guess not everybody may want to spend that. $\endgroup$
    – Maarten Bodewes
    Nov 1, 2023 at 21:46

3 Answers 3

3
$\begingroup$

The answer depends on the definition of what is an “ARX” algorithm.

According to the first approach, if some cryptographic algorithm (namely, a permutation or transformation) uses (modular) additions, rotations and bitwise XORs, it is automatically “ARX”, independently of whether it uses other logical functions or table lookups. For example, this post contains the following text:

many designers specify their primitives directly in pseudocode similarly including bitwise Boolean instructions and (cyclic) shifts, but on top of that also additions. These additions are modulo $2^n$ with $n$ a popular CPU word length such as 8, 32 or 64. Such primitives are dubbed ARX that stands for “addition, rotation and exclusive-or (XOR)”. The ARX approach is widespread and adopted by popular designs MD4, MD5, SHA-1, SHA-2, Salsa, ChaCha, Blake and Skein.

According to the second approach, a cryptographic algorithm is “ARX” if and only if it is based on the combination of (modular) additions, rotations and bitwise XORs (and nothing more.) For example, this article contains the following text (note the word “only”):

Many modern block ciphers and hashes are ARX algorithms—their round function involves only three operations: (A) modular addition, (R) rotation with fixed rotation amounts, and (X) XOR. Examples include ChaCha20, Speck, XXTEA, and BLAKE.

This approach implies that SHA-2 is not ARX.

$\endgroup$
0
2
$\begingroup$

SHA2 and MD5 predate most ARX designs. It probably inspired ARX designs. It is all based on same idea of mixing different operations to get non-linearity. Some consider RC6 and IDEA to be ARX. Some even consider Simon to be ARX which does not have addition. Strictly speaking TEA is not ARX, because it uses shifts instead of rotations.

I don't think NSA knew something special. They just based it on MD5. They also designed Speck which is classical ARX.

$\endgroup$
3
  • 2
    $\begingroup$ "It probably inspired ARX designs." - probably not; I expect it was independently discovered multiple times. If someone just looks at a common microprocessor instruction set and asks "what are the cheap operations that has some cryptographical strength", well, ARX is a natural answer. In my misspent youth, I worked out my own homebrew cipher, I basically come up with an ARX design, even though I was unfamiliar with the internals of MD5 and SHA1. $\endgroup$
    – poncho
    Oct 31, 2023 at 12:36
  • $\begingroup$ x + x == x << 1. rotr(rotr(x, 1) + rotr(x, 1), 1) == x >> 1. So shifts are also ARX. $\endgroup$
    – Myria
    Oct 31, 2023 at 22:52
  • $\begingroup$ @Myria Well one could say ARX do not exists as addition is just ANDs and XORs. So every ARX has AND and OR or NAND or NOR on a low level. $\endgroup$
    – LightBit
    Nov 1, 2023 at 8:07
1
$\begingroup$

It really depends on your definition of "ARX". The only things in SHA-2 that are not ARX on their surface are AND, NOT, and shift. However, we can define these in terms of ARX operations.

NOT is the easiest (using 32-bit; i.e. SHA-256):

~x == x ^ 0xFFFFFFFF

Non-cyclic shifting takes advantage of modular addition discarding the high bit:

x << 1 == x + x

x >> 1 == ROTR(ROTR(x, 1) + ROTR(x, 1), 1)

AND is the complicated one. One way to do this is to realize how addition is the combination of AND and XOR:

(x ^ y) + ((x & y) << 1) == x + y

Solving for x & y, we get this:

x & y & 0x7FFFFFFF == ((x + y) - (x ^ y)) >> 1

The high bit of the AND result got discarded; we'll handle that at the end.

We can then use the identity -x = ~x + 1 for two's-complement arithmetic to define subtraction:

x & y & 0x7FFFFFFF == ((x + y) + (x ^ ~y) + 1) >> 1

Now we need the high bit of x & y. To do that, add the two bits and use bit 1 of the result as their AND. Shift back in place and add it to make the final result.

x & y = (((x + y) + (x ^ ~y) + 1) >> 1) + (((x >> 31) + (y >> 31) >> 1) << 31)

This completes everything needed for SHA-2 in terms of additions, rotates and XORs.

$\endgroup$
2
  • $\begingroup$ This way you could probably bitslice AES and define it as ARX. $\endgroup$
    – LightBit
    Nov 1, 2023 at 8:11
  • 2
    $\begingroup$ @LightBit This is more about Functional completeness. $\endgroup$
    – kelalaka
    Nov 1, 2023 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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