Clone wiki

Challenge11 / Stage3

Stage 2

Reversing Overview

VirusTotal does not report the stage 2 shellcode as being known to any of its 41 AV agents.

Using Radare to view a disassembly (starting at offset 0x000000D4) of our stage 2 payload (MD5: 6cd807ebdc936f5123821f6d4f43fe81) along with /usr/src/sys/kern/syscalls.master, we note that:

  • the system call at line 0x103 is a call to FreeBSD function number 0x05
  • the system call at lines 0x143, 0x254, 0x3D3, 0x401, 0x5A0 and 0x682 are calls to FreeBSD function number 0x3
    • i.e. ssize_t read(int fd, void *buf, size_t nbyte) (see read manpage).
  • the system call at lines 0x231 and 0x6CB are calls to FreeBSD function number 0x04
    • i.e. ssize_t write(int fd, const void *buf, size_t nbyte) (see write manpage)
  • the system call at line 0x3A4 is a call to FreeBSD function number 0x1DD
  • the system call at line 0x5FF is a call to FreeBSD function number 0x49
  • the system call at line 0x615 is a call to FreeBSD function number 0x6

Additionally, we note that (see stage2_unpacker.log ):

  • a file descriptor to /dev/urandom is opened at 0x103 (see stage2_unpacker.log ) and then 48 bytes are read from this file descriptor at 0x143 (see stage2_unpacker.log ).
  • at 0x231 (see stage2_unpacker.log ), a packet is written back to 10.0.0.2. As our Python-based emulator does not write the same packet back as we expect from inspecting fc_0.pcap , we suspect that the packet contents might be dependent upon the 48 byte string/key generated at 0x143?

In attempting to determine the relationship between our 48 byte /dev/urandom key and the contents of packet #24 (of fc_0.pcap ), we aim at reversing the functions at 0xD5D and 0x1026. Where possible, we attempt to verify our hypotheses by testing the expected behaviours of our reversed functions (see test/big_int_zadd.py , test/big_int_add.py , test/big_int_sub.py , test/big_int_lsl.py and test/big_int_asr.py ).

These functions are built from the following (sub-function) primitives:

  • big_int_zadd (offset 0xB44)
  • big_int_add (offset 0xB5F)
  • big_int_sub (offset 0xB70)
  • big_int_lsl (offset 0xB81)
  • big_int_asr (offset 0xB8A)

Further examination of 0xD5D reveals the following interesting code sequences (here we switch to using the demo version of IDA Pro on a compiled version of honeynet_stage2_payload.S - this file has been created by editing the output of x86dis): 0xd60-detail.png

which is contained at the exit point of a larger loop. This leds us to suspect that this routine might be calculating the GCD of two numbers? Following this lead, we discover that this routine is mostly the binary extended GCD algorithm (reference: algorithm 14.61 in section 14.4.3 of Handbook of Applied Cryptography).

If we view the function as terminating at address 0xF43 then the function may be described using the following Python code (see test/big_int_gcd.py ):

def extended_binary_gcd(x, y, div2 = lambda p: p >> 1):
  g = 1
  while (x % 2 == 0) and (y % 2 == 0):
    x, y, g = div2(x), div2(y), 2*g
  u, v, A, B, C, D = x, y, 1, 0, 0, 1
  while u != 0:
    while (u % 2 == 0):
      u = div2(u)
      if (A - B) % 2 == 0:
        A, B = div2(A), div2(B)
      else:
        A, B = div2(A+y), div2(B-x)
    while (v % 2 == 0):
      v = div2(v)
      if (C - D) % 2 == 0:
        C, D = div2(C), div2(D)
      else:
        C, D = div2(C+y), div2(D-x)
    if u >= v:
      u, A, B = u - v, A - C, B - D
    else:
      v, C, D = v - u, C - A, D - B
  a, b = C, D  
  return a, b, g*v

Thus we are left with determining the purpose of the following code: 0xd60-return.png

Here we reverse it as Python code (see test/big_int_gcd.py ):

  
def simulate_0xd5d(x, y, div2 = lambda p: p >> 1):
  a, b, d = extended_binary_gcd(x, y, div2)
  return b % x

From which, we determine that function 0xD5D returns the multiplicative inverse of y, modulo x (whenever gcd(x, y) = 1 that is!).

Function 0xBA3 ends up being quite a challenge to reverse! We first observe the relatively simple flow-graph structure (i.e. a loop with some straight line code interleaved with a conditional by-pass):

0xba3-reversed.png

The difficulty here is in attempting to understand the odd looking big int manipulations. The key insight here is to note the big int digit indexing and how they are being used as part of a pair of aggregate sums.

Using the invaluable Handbook of Applied Cryptography to locate potential algorithm candidates (by matching such algorithmic features), we hypothesize that we are dealing with Montgomery multiplication (reference: algorithm 14.36 of Handbook of Applied Cryptography).

Checking known input values (obtained by hooking the stage 2 payload to extract big int addresses) against the argument relationships implied by the Montgomery multiplication hypothesis, we have that:

  • function argument 0 to big_int_mult points (@0x284AD000) to the integer 64 871953 055083 132442 586738 160300 545132 676055 315639 670194 672701 161688 976212 780255 925431 194294 264487 036940 900075 456699 (= arg0)
  • function argument 1 to big_int_mult is the value 0x5177438D (= arg1)

Using Sage, we are able to verify:

arg0 = ZZ("64 871953 055083 132442 586738 160300 545132 676055 315639 670194 672701 161688 976212 780255 925431 194294 264487 036940 900075 456699")
arg1 = 0x5177438D

gcd(arg0, 2 ^ 32) == 1 and inverse_mod(arg0, 2 ^ 32) == -arg1 % 2 ^ 32

Thus supporting our Montgomery multiplication hypothesis (see test/big_int_mult.py for testing support).

Function 0x1026 contains big int multiplication (i.e. big_int_mult) within a loop and so is an obvious candidate function for an implementation of exponentiation:

0x1026-reversed.png

Based on this hypothesis, we note the following:

  • the code has a close similarity to left-to-right binary exponentiation (see algorithm 14.79 of Handbook of Applied Cryptography)
  • the odd looking EAX manipulations are not readily explained
  • the presence of the function arguments [ESP+0x40]: long (= 0x5177438D), [ESP+0x3C]: big_int (= 0x284AD038), [ESP+0x38]: big_int (= 0x284AD06C) are not readily explained.

At this point, we note that Montgomery exponentiation is a combination of left-to-right exponentiation and Montgomery multiplication (see introductory remarks to Montgomery exponentiation in Handbook of Applied Cryptography). An inspection of algorithm 14.94 in Handbook of Applied Cryptography now reveals that Montgomery exponentiation may sometimes be implemented with R mod m and R2 mod m provided as inputs. Bingo! We now have a viable candidate implementation for function 0x1026.

Checking known input values (obtained by hooking the stage 2 payload) against the argument relationships implied by the Montgomery exponentiation hypothesis, we have that:

  • function argument 1 to big_int_exp points (@0x284AD0A0) to the integer 28 874886 502820 635270 988382 873765 249080 724636 489175 670968 600351 015660 554179 871058 627909 746857 890394 896866 174667 024027 (= arg1)
  • function argument 3 to big_int_exp points (@0x284AD000) to the integer 64 871953 055083 132442 586738 160300 545132 676055 315639 670194 672701 161688 976212 780255 925431 194294 264487 036940 900075 456699 (= arg3)
  • function argument 4 to big_int_exp is the value 0x5177438D (= arg4)
  • function argument 5 to big_int_exp points (@0x284AD038) to the integer 48 278221 289446 497153 985279 131305 391627 351416 666292 194983 419892 645878 312893 637591 542762 632453 148128 123663 310366 845725 (= arg5)
  • function argument 6 to big_int_exp points (@0x284AD06C) to the integer 18 445926 386052 090268 064989 491764 773422 295975 643163 069463 814572 836720 894822 197691 261471 373323 908356 528789 697097 845918 (= arg6)

Using Sage, we are able to verify:

arg1 = ZZ("28 874886 502820 635270 988382 873765 249080 724636 489175 670968 600351 015660 554179 871058 627909 746857 890394 896866 174667 024027")
arg3 = ZZ("64 871953 055083 132442 586738 160300 545132 676055 315639 670194 672701 161688 976212 780255 925431 194294 264487 036940 900075 456699")
arg4 = 0x5177438D
arg5 = ZZ("48 278221 289446 497153 985279 131305 391627 351416 666292 194983 419892 645878 312893 637591 542762 632453 148128 123663 310366 845725")
arg6 = ZZ("18 445926 386052 090268 064989 491764 773422 295975 643163 069463 814572 836720 894822 197691 261471 373323 908356 528789 697097 845918")

gcd(arg3, 2 ^ 32) == 1 and inverse_mod(arg3, 2 ^ 32) == -arg4 % 2 ^ 32 and arg5 == (2 ^ (32 * 0xd)) % arg3 and arg6 == (2 ^ (32 * 0xd * 2)) % arg3

Thus supporting our Montgomery exponentiation hypothesis (see test/big_int_exp.py for testing support).

Looking at the function 0x760 we note:

  • the unusual constants 0x34D34D34, 0xD34D34D3 and 0x4D34D34D
  • the following curious code sequence: 0x760-detail.png
    • as best we can determine, this code sequence appears to be related to Von Neumann's middle square method for generating pseudorandom sequences of numbers?

A Google now reveals the Rabbit stream cipher (see equation 6, section 2.4 of The Stream Cipher Rabbit for a plausible match to the above noted code). Examining the reference implementation of this cipher (see rabbit.c), we find a close correlation between the assembler for function 0x760 and C source code function RABBIT_next_state.

Based on these observations, we now believe that the function at:

  • offset 0x760 is RABBIT_next_state in rabbit.c
  • offset 0x8E8 is the encryption basic block (e.g. see ENCRYPT_process_bytes in rabbit.c)
  • offset 0xA9D is ENCRYPT_process_bytes in rabbit.c
  • offset 0x940 is ENCRYPT_keysetup followed by ENCRYPT_ivsetup in rabbit.c.

Our main function (at offset 0xD4) is now mostly straightforward to reverse:

0xd4-reversed-top.png

0xd4-reversed-bottom.png

However, the code at 0x430 to 0x58C warrants further attention. After reading in and decrypting a packet of data, the packet contents are processed through this block of code to produce a 4 byte result. This 4 byte result is then compared against a 4 byte value read (and decrypted) from the network socket.

As this 4 byte value is the result of processing packet data (that we latter call!), we hypothesize that this code is calculating some form of checksum. Using our test harness (see test/adler32.py ), we compute results for known inputs. Then, via a web site such as nitrxgen.net (you may experience loading issues here?) or fileformat.info, we process the known input through a series of standard checksum and hashing algorithms. A visual check of the results (looking for 32 bit results!) now suggests that this code implements the Adler32 checksum (see test/adler32.py ).

This ability to calculate and verify the downloaded code's checksum provides us with an opportunity to verify if our attempts at decrypting the stage 3 payload have succeeded or not. However, as the Rabbit stream cipher is setup with a 16 byte key and 8 byte initialisation vector (i.e. 2192 possible values), a brute force attempt at guessing key/IV combinations is unlikely to succeed (though that doesn't mean we shouldn't try this type of attack - we might be lucky!).

Finally, we note that offsets 0x1198 to 0x13F0 are not used by the stage 2 payload. Thus we can currently offer no explanation as to their purpose. All other bytes within the stage 2 payload have been accounted for.

Analysis

Phase 1 of Stage 2: Rabbit Initialisation

From reversing our main stage 2 function (at offset 0xD4), we find that:

  • the big int at 0x284AD000 (i.e. p = 64 871953 055083 132442 586738 160300 545132 676055 315639 670194 672701 161688 976212 780255 925431 194294 264487 036940 900075 456699) is a prime number that is used in a variety of modulus calculations
  • a random odd big int (i.e. r) in the range [1, 2383) is generated (this value is private and we will need to calculate it)
  • the big int at 0x284AD0A0 (i.e. g = 28 874886 502820 635270 988382 873765 249080 724636 489175 670968 600351 015660 554179 871058 627909 746857 890394 896866 174667 024027) is of order q in the multiplicative group ZZ*p (where p = 2q + 1)
  • at offset 0x1C4, we call big_int_gcd to calculate the multiplicative inverse of r modulo p-1 (i.e. d = r-1 mod p-1)
  • at offset 0x20F, we call big_int_exp to calculate the big int gr mod p, which we then share with 10.0.0.2 via a network write
  • the packet data (i.e. pkt) received from 10.0.0.2 is interpreted as a big int and then we call big_int_exp to calculate the big int value pktd mod p. This value is subsequently taken by 10.0.0.1 to be the decrypted message (i.e. msg) from 10.0.0.2.

As 10.0.0.1 decrypts 10.0.0.2's encrypted packet by exponentiating it to r's multiplicative inverse (modulo p), we do not have an instance of ElGamal or Diffie-Hillman being used here (since these would both use multiplication).

In attempting to understand how 10.0.0.2 processes the received big int gr mod p, we have two possible scenarios:

  • 10.0.0.2 calculates a discrete logarithm to retrieve the value r, followed by some other calculation to get pkt
  • 10.0.0.2 simply raises gr mod p to some exponent value (i.e. x) to get pkt.

As:

  • an exponentiation calculation is, compared to a discrete logarithm calculation, computationally easier to perform (a view supported by limited empirical testing)
  • and the time between packet's #24 and #25 is 3.32 * 10-4 seconds

we shall assume that 10.0.0.2 actually performs an exponential calculation. This implies that, at some time prior to 10.0.0.1 being exploited(?), 10.0.0.2 had precomputed x = logg(msg) mod p (where msg is the actual message that 10.0.0.2 wishes to communicate with 10.0.0.1). This leads us to believe that the following sequence of behaviours is being performed:

stage3-part1.png

Note:

  • that the function at 0xD4 displays secure coding features (i.e. sensitive variables are zeroed).

Post-challenge Note:

Phase 2 of Stage 2: Loading of Stage 3

Up until packet #27, all network data has been accounted for. Packet #28 is a write containing 0x00000000 sent to 10.0.0.2. Preceding this write, the code performs 3 reads from the network socket:

  • the first reads in the stage 3 payload
  • the second reads in an expected checksum of the stage 3 payload
  • the third reads in the offset at which to start executing the stage 3 payload.

Based on this behaviour, we believe that all these reads target the buffered contents of packet #27. Thus, we arrive at the following sequence diagram:

stage3-part2.png

Note:

  • based on the buffered read behaviour of packet #27, we hypothesise that offsets 0x18-0x1B of packet #25's decrypted contents contains the value 0x0000047E (= size(packet #27) - 4 - 2 = 1156 - 4 - 2) stored in byte little endian format
  • that the function at 0xD4 displays secure coding features (i.e. sensitive variables are zeroed and then pro-actively checked, via a packet write).

Cracking Stage 3 Encryption

Note: all computation in this section was performed on a 16 core, 2.4GHz Intel Xeon PowerMac, with additional support from the University of Huddersfield's HPC grid.

Discrete Logarithm Attack

Our aim here is to recover the value r (an unknown random odd number in [1, 2383)), where pkt24 = gr mod p (here packet #24 is interpreted as the big int pkt24).

Now, p is a safe prime - i.e. we have a prime q such that p = 2q+1. Moreover, gq = 1 mod p and so g is a quadratic residue modulo p.

If we first calculate an a such that a2 = g mod p, then a will be a generator for the multiplicative group ZZ*p (i.e. |a|p = 2q = p-1).

Now, pkt24 = gr mod p and g = a2 mod p. Thus, pkt24 = a2r mod p. Hence, we can now calculate the value r by calculating (loga(pkt24) mod p-1)*2-1 mod p = (loga(pkt24) mod p-1)*(q+1) mod p.

The following Sage code supports these claims:

p = ZZ("64 871953 055083 132442 586738 160300 545132 676055 315639 670194 672701 161688 976212 780255 925431 194294 264487 036940 900075 456699")
q = (p-1) // 2
g = ZZ("28 874886 502820 635270 988382 873765 249080 724636 489175 670968 600351 015660 554179 871058 627909 746857 890394 896866 174667 024027")
pkt24 = ZZ("57 862149 747092 325030 167062 717207 431168 694932 216310 538267 343292 342318 477158 898286 092297 346029 386203 435452 141910 116025")

assert power_mod(g, q, p) == 1
print "g^q = 1 mod p"

assert inverse_mod(2, p) == q+1
print "2^-1 = q+1 mod p"

a = mod(g, p).sqrt()
print "a^2 = g mod p"

Our attack now focuses on calculating logarithms to the base a (modulo p-1).

As p has 117 decimal digits, we can not expect the Pohlig-Hellman algorithm to deliver a result within the challenge time bounds (e.g. see section 3.6.4 of Handbook of Applied Cryptography, where the running time is estimated to be O(sqrt(q)) group multiplications).

The GDLog implementation, of the General Number Field Sieve algorithm, reports example discrete logarithm factorisations involving 100 decimal digit prime moduli within a 1 week time period, and so appears to be more suitable for our purposes here (see discrete logarithm records for similar results). The use of the General Number Field Sieve to calculate discrete logarithms for primes on this size is further supported by the notes in section 3.12 of the Handbook of Applied Cryptography.

Unfortunately, the GDLog implementation that we used ran for a long period of time (i.e. around 2-3 weeks of computing time). We suspect that this was due to GDLog's default polynomial selection being rather less than optimal (at times, we were even concerned that we were observing divergent behaviour with the default polynomials!). Due to the challenge time bounds, we were unable to fully verify these suspicions (e.g. see Polynomial Selection for the Number Field Sieve Integer Factorisation Algorithm by B.A.Murphy, Polynomial Selection for the Number Field Sieve by S.Bai and Projections for GNFS polynomials for further information regarding polynomial selection).

We attempted to tackle these time issues by throwing the University of Hudderfield's HPC cluster at the problem! Unfortunately, whilst we managed to extract over 10 million relations and ideals (which proved to be too small!), the data itself needed a significant amount of scrubbing (this was in part due to the way we collected the data from the HPC cluster and in part due to the lack of input sanitation performed within the GDLog code) - ultimately, this significantly delayed our cracking efforts!

Note: 9 days after the challenge deadline, gdlog returned 10 607833 713671 622331 958593 898979 290746 974713 429220 998127 451286 349297 232203 445447 007724 535020 385315 291415 382670 421464 as its result and reported that this was in fact incorrect. Post-competition analysis shows that I introduced a copying error whilst moving code to the Huddersfield HPC. This resulted in sieved relations being messed up with ensuing chaos!

Had GDLog completed correctly, we would have expected an x such that x = loga pkt24 mod q (this is based on gdlog's README).

In the following, let y = loga pkt24 mod 2 (Note: y can only be 0 or 1 here!).

Using the Chinese Remainder Theorem, we can now deduce that z = loga pkt24 mod (p-1), where 2*q = p-1 and z = (x*2*(2-1 mod q) + y*q*(q-1 mod 2)) mod (p-1) = (x*2*(2-1 mod q) + y*q) mod (p-1).

Hence we have that az = pkt24 mod p.

Since 2*r = z, we have that 2 | z and so, 2 | (x*2*(2-1 mod q)) (which is trivially so) and 2 | y*q.

By substituting possible values for y, we have that 2 | 0 (when y=0) or 2 | q (when y=1). As q is odd, then we must have that y=0.

Thus, we derive that r = x*(2-1 mod q) mod (p-1).

Brute Force Attack

If our aim is to decrypt the stage 3 payload, then all we really need to do is to (somehow!) determine the Rabbit IV and key values (actually, we just need to determine the key stream, but here we'll conveniently ignore this fact as it doesn't appear to help!).

As our stage 3 payload has its Rabbit decrypted contents checksummed (using Adler 32) against a 4 byte value read (and Rabbit decrypted) from the network socket. And, 2 bytes are read (and Rabbit decrypted) from the network socket to determine a jump offset into our stage 3 payload (thus, this value is constrained to be in the range [0, 1150)). We have potential matching criteria for generating candidate Rabbit IV/key values via a brute force search.

From Stream Cipher Attacks, Rabbit has no currently reported cryptographic weaknesses, thus brute forcing our Rabbit IV/key space appears to be our only viable option.

From reversing our stage 2 payload, we suspect that our attacker is capable of calculating discrete logarithms to base g, modulo p (as 10.0.0.2 needs to know the value x in order to transmit, via an exponentiation calculation, msg = gx mod p to 10.0.0.1). As our Rabbit IV/key space has 2192 possible values (i.e. it's huge!), we deduce that calculating discrete logarithms is a more effective looking attack strategy.

Extracting the Stage 3 Payload

Note: the following extraction was performed using the results of Ruud Schramp's discrete logarithm calculation.

Using PyDBG and Scapy Python code (running within a VMWare Windows XP SP2 virtual machine) we can now automatically extract our stage 3 payload (saved as honeynet_stage3_payload.bin - MD5: e51269b54dd38f27d0b93e70ecec5b3f).

See stage2_to_3_unpacker.py for a copy of this extraction code and stage2_to_3_unpacker.log for the logged output in running this code.

Reversed Stage 2 Data Structures

Big Integer Representation

big_int.png

So, for example, the following 2 digit big int in memory:

0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07

would be read as the sequence of bytes (in byte-big endian format):

0x03 0x02 0x01 0x00 0x07 0x06 0x05 0x04

and so be interpreted as the integer:

216736831696667908.

The following Sage code implements conversion between big int hex string's and int's:

def to_bytestream(hex_str, n):
    assert(len(hex_str) == 8*n)
    bytestrm = []
    for d in range(0, len(hex_str), 8):
        digit = []
        for i in range(0, 8, 2):
            digit = [hex_str[d:d+8][i:i+2]] + digit
        bytestrm.append(join(digit, ""))
    return join(bytestrm, "")
    
def bigint_to_int(bigint, n):
    return int(to_bytestream(bigint, n), 16)
    
def int_to_bigint(i, n):
    hexstr = hex(i)
    hexstr = "0"*((8 - (len(hexstr) % 8)) % 8) + hexstr
    padded_hexstr = "00"*4*(n - (len(hexstr) // 8)) + hexstr
    return to_bytestream(padded_hexstr, n)

Structure of Decrypted Packet #25

packet25.png

Reversed Stage 2 Functions

big_int_zadd (offset 0xB44)

This function adds two big int's together (with second argument 0-extended)

  • the big int's consist of an arg0 (i.e. first stack argument to function call) length list of base 65356 digits (digits stored little-endian)
  • EAX points to a big int value (i.e. big_int(*EAX))
  • second big int value has ECX as digit 0 and EDX as digit 1 (padding to end of list representation), this bit int is then 0-extended (i.e. big_int([ECX, EDX]) == big_int([ECX, EDX, 0x0, ...]))
  • big_int(*EAX) = big_int(*EAX) + big_int([ECX, EDX])
  • see test/big_int_zadd.py

big_int_add (offset 0xB5F)

This function adds two big int's together

  • the big int's consist of a ECX length list of base 65356 digits (digits stored little-endian)
  • EAX and EDX points to the respective big int values (i.e. big_int(*EAX) and big_int(*EDX))
  • big_int(*EAX) = big_int(*EAX) + big_int(*EDX)
  • see test/big_int_add.py

big_int_sub (offset 0xB70)

This function subtracts two big int's together

  • the big int's consist of a ECX length list of base 65356 digits (digits stored little-endian)
  • EAX and EDX points to the respective big int values (i.e. big_int(*EAX) and big_int(*EDX))
  • big_int(*EAX) = big_int(*EAX) - big_int(*EDX)
  • see test/big_int_sub.py

big_int_lsl (offset 0xB81)

This function is a logical bit-shift left of a big int

  • the big int consists of a EDX length list of base 65356 digits (digits stored little-endian)
  • EAX points to the respective big int value (i.e. big_int(*EAX))
  • big_int(*EAX) = 1 << big_int(*EAX) (0 is copied in from the right during the shift)
  • see test/big_int_lsl.py

big_int_asr (offset 0xB8A)

This function is an arithmetic bit-shift right of a big int (with initial bit taken from sign of big_int(*EAX))

  • the big int consists of a EDX length list of base 65356 digits (digits stored little-endian)
  • EAX points to the respective big int value (i.e. big_int(*EAX))
  • big_int(*EAX) = big_int(*EAX) >> 1 (the big integer's sign bit is copied in from the left during the shift)
  • see test/big_int_asr.py

big_int_gcd (offset 0xD5D)

When gcd(x, y) = 1, this function calculates the multiplicative inverse of an big int (relative to a big int modulus). This calculation is achieved via the use of an extended binary GCD algorithm (see algorithm 14.61 of the Handbook of Applied Cryptography).

  • function argument 0 is a pointer to the big int result (i.e. y-1 mod x)
  • function argument 1 is a pointer to the big int value x
  • function argument 2 is a pointer to the big int value y
  • function argument 3 is the number of digits present in our big int's (here this value is typically 0xD)
  • see test/big_int_gcd.py

The following Sage code can be used to calculate these arguments:

def big_int_gcd_args(x, y, n):
    assert(gcd(x, y) == 1)
    
    return { '*arg0': inverse_mod(y, x), '*arg1': x, '*arg2': y, 'arg3': n }

big_int_mult (offset 0xBA3)

This function implements Montgomery multiplication for a pair of big int's (see algorithm 14.36 of the Handbook of Applied Cryptography). In the following, we assume that b = 232, R = bn and gcd(m, b) = 1:

  • register EAX is a pointer to the big int result (i.e. x * y * R-1 mod m)
  • register ECX is a pointer to the big int value x
  • register EDX is a pointer to the big int value y
  • function argument 0 is a pointer to the big int modulus value m
  • function argument 1 is a the long value -m-1 mod b
  • function argument 2 is long value n (i.e. the number of digits present in our big int's - typically 0xD here)
  • see test/big_int_mult.py

The following Sage code can be used to calculate these arguments:

def big_int_mult_args(x, y, m, n):
    b = 2^32
    R = b^n

    assert(gcd(m, b) == 1)

    return { '*eax': (x * y * inverse_mod(R, m)) % m, '*ecx': x, '*edx': y, '*arg0': m, 'arg1': -inverse_mod(m, b), 'arg2': n }

big_int_exp (offset 0x1026)

This function implements Montgomery exponentiation for a pair of big int's (see algorithm 14.94 of the Handbook of Applied Cryptography). In the following, we assume that b = 232, R = b32 * l and gcd(m, R) = 1:

  • function argument 0 is a pointer to the big int result (i.e. x * y mod m)
  • function argument 1 is a pointer to the big int value x
  • function argument 2 is a pointer to the big int value y
  • function argument 3 is a pointer to the big int modulus value m
  • function argument 4 is the long value -m-1 mod b
  • function argument 5 is a pointer to the big int value R mod m
  • function argument 6 is a pointer to the big int value R2 mod m
  • function argument 7 is the long value l (i.e. the number of digits present in our big int's - typically 0xD here)
  • see test/big_int_exp.py

The following Sage code can be used to calculate these arguments:

def big_int_exp_args(x, y, m, l):
    b = 2^32
    R = b^(32*l)

    assert(gcd(m, b) == 1)

    return { '*arg0': (x * y) % m, '*arg1': x, '*arg2': y, '*arg3': m, 'arg4': -inverse_mod(m, b), '*arg5': R % m, '*arg6': R^2 % m, 'arg7': l }

RABBIT_next_state (offset 0x760)

This function is RABBIT_next_state in rabbit.c, with:

RABBIT_encrypt (offset 0x8E8)

This function is the encryption basic block (e.g. see ENCRYPT_process_bytes in rabbit.c) with:

  • EAX pointing to a RABBIT_ctx struct (see ecrypt-sync.h)
  • EDX pointing to a message block

RABBIT_process_bytes (offset 0xA9D)

This function is ENCRYPT_process_bytes in rabbit.c, with:

  • argument 0 pointing to a ENCRYPT_ctx struct (see ecrypt-sync.h)
  • argument 1 pointing to our message
  • argument 2 containing our messages length

RABBIT_setup (offset 0x940)

This function is ENCRYPT_keysetup followed by ENCRYPT_ivsetup (see rabbit.c), with:

  • argument 0 pointing to a ENCRYPT_ctx struct (see ecrypt-sync.h) and is arg0 for both ENCRYPT_keysetup and ENCRYPT_ivsetup
  • argument 1 pointing to a 0x10 byte key and is arg1 to ENCRYPT_keysetup
  • argument 2 pointing to an 0x8 byte initialisation vector and is arg1 to ENCRYPT_ivsetup

Updated