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).
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.