This post has been translated into Estonian by Sonja Kulmala.

Kaspersky Lab recently published a blog post Rare implementation of RC5/RC6 in ‘ShadowBrokers’ dump connects them to Equation malware in which they analyze the RC6 block cipher implementation used in the recent ShadowBrokers release and compare it to the earlier Equation Group malware they found. They conclude that since all of the implementations they examined contain an RC6 constant in its negated form, it must be from the same authors since that’s so unusual. Their analysis is wrong.

I don’t mean that their conclusion is wrong. They’re probably right. This is probably the same code. But their analysis is definitely wrong.

Update: I’m not the first one to notice this.

Kaspersky’s main claim is that since on some platforms (although they don’t say which; and this isn’t true on almost anything newer than the Z80), addition is faster than subtraction and therefore the source code for RC6 should contain the addition of a particular constant, Q32, in the key expansion routine. What they found in both the ShadowBrokers dump and the earlier Equation Group malware was an RC6 implementation that was subtracting -Q32 rather than adding Q32. To Kaspersky, this is the smoking gun linking the two.

Consider a typical implementation of RC6. (By typical, I mean I googled for RC6 source code and selected the first implementation I found that was obviously standalone.) On lines 78–80, we see the loop in the key expansion code that Kaspersky focuses on, reproduced here.

for(i=1; i<2*rounds+4; ++i){
	s->S[i] = s->S[i-1] + Q32;
}

Q32 is the constant in question and it is defined on line 37 as 0x9E3779B9, which is the standard form that appears in Ron Rivest’s original paper.

From a very quick analysis of the ShadowBrokers binaries, it’s clear that many of these programs were compiled using a Red Hat version of GCC 3.4.x or GCC 4.0.0. Somewhat bizarrely, the same binary will incorporate objects from several compilers. For example, BANANAGLEE/BG2100/Install/LP/bg_redirector-2140 which I previously examined, appears to contain objects compiled using four different versions of GCC.

$ strings bg_redirector-2140 |grep GCC|sort -u
GCC: (GNU) 3.4.3
GCC: (GNU) 4.0.0 20050314 (Red Hat 4.0.0-0.34)
GCC: (GNU) 4.0.0 20050518 (Red Hat 4.0.0-7)
GCC: (GNU) 4.0.0 20050525 (Red Hat 4.0.0-9)

Based on the dates and GCC versions, I installed CentOS 4.1 (which is based on Red Hat) in a VM. I downloaded the RC6 implementation linked above and compiled it with GCC 3.4.3 20050227 (Red Hat 3.4.3-22.1) which came with the OS. It’s not quite the same version of GCC, but it’s close enough. Looking at either the assembly produced by GCC or by running objdump on the object file, we see a subtraction of 0x61C88647 rather than an addition of 0x9E3779B9. And this holds true for all optimization levels (-O0 through -O3 and -Os).

Output of compiling rc6.c on CentOS

Since the compiler itself is responsible for producing the subtraction instruction, its presence does not conclusively demonstrate that the Equation Group malware and the code released by the ShadowBrokers were written by the same group.

Update 2: More evidence that Kaspersky is wrong in their analysis comes from looking at some of the other architectures. For example, in the MIPS version of SecondDate, the constant 0x9E3779B9 is used with addu (note the value stored into $a1).

Rc6_expandKey:
                lui     $v0, 0xB7E1      # Load Upper Immediate
                move    $t6, $a1
                li      $v0, 0xB7E15163  # Load Immediate
                lui     $a1, 0x9E37      # Load Upper Immediate
                move    $a3, $a0
                addiu   $sp, -0x10       # Add Immediate Unsigned
                sw      $v0, 0($t6)      # Store Word
                li      $t5, 1           # Load Immediate
                li      $a1, 0x9E3779B9  # Load Immediate
                addiu   $a0, $t6, 4      # Add Immediate Unsigned

loc_9B98:                                # CODE XREF: Rc6_expandKey+3Cj
                lw      $v0, -4($a0)     # Load Word
                addiu   $t5, 1           # Add Immediate Unsigned
                sltiu   $v1, $t5, 0x2C   # Set on Less Than Immediate Unsigned
                addu    $v0, $a1         # Add Unsigned
                sw      $v0, 0($a0)      # Store Word
                bnez    $v1, loc_9B98    # Branch on Not Zero
                addiu   $a0, 4           # Add Immediate Unsigned

In the PPC version of SecondDate, 0x9E3779B9 is used with addis/addi.

loc_98AC:
                slwi      r7, r6, 2     # Shift Left Immediate
                addi      r6, r6, 1     # Add Immediate
                add       r9, r7, r4    # Add
                lwz       r10, -4(r9)   # Load Word and Zero
                addis     r8, r10, 0x9E37 # Add Immediate Shifted
                addi      r0, r8, 0x79B9 # Add Immediate
                stwx      r0, r7, r4    # Store Word Indexed
                bdnz      loc_98AC      # CTR--; branch if CTR non-zero

In the ARM version of BSecondDateCommon, 0x9E3779B9 is used with add.

loc_117BC:
                LDR             R2, [R1]
                LDR             R3, =0x9E3779B9
                ADD             R0, R0, #1
                CMP             R0, #0x2C ; ','
                ADD             R3, R2, R3
                STR             R3, [R1,#4]!
                BNE             loc_117BC
                MOV             R4, #0

On x86, for some reason, GCC decides to go with a subtraction. On other architectures, it doesn’t.