4

The below code snippets are some kind of bignum multiplications involving 2048bit numbers, possibly in the context of RSA decryption.

  • Does any one recognize this pattern?
  • Is it maybe some kind of Montgomery multiplication (unlikely) ?
  • Or some RSA obfuscation that someone recognizes?

There are 2 multiplication loops. I marked them with loop1 and loop2. loop1 does the partial multiplication and addition I would expect. But how does the second loop make sense mathematically? It uses a seperate vector to multiply with. Does this accumulate into a modulo operation?

I converted the IDA compilation to a more readable representation below, the original is at the end. Can anyone recognize a pattern?

struct mod {
  int len;
  uint32_t _pad0[64]; /* 4 */
  uint32_t r[64];     /* 4 + (256*1) :offset-260  */
  uint32_t _pad2[64]; /* 4 + (256*2) :offset-516  */
  uint32_t _pad3[64]; /* 4 + (256*3) :offset-772  */
  uint32_t _pad4[64]; /* 4 + (256*4) :offset-1028 */
  int fac;            /* 4 + (256*5) :offset-1284 */
};

#define align8(c) (((uint64_t)(c)) & (~0x7ULL))

int64_t some_kind_of_mult(int32_t *acc , int32_t *a , int32_t *b, struct mod *n)
{
  int i0, i1, i2, j0 ;
  uint32_t top;
  uint64_t c0 = 0, c1 = 0, v0, v1, v2, v3, c01, c01_h;
  intt64_t m1, res, topc0 = 0;

  memset(acc,0,256);
  res = 0;
  l = n->len;

  if ( !l )
    return res;

  top = topc0 = 0;

  for (i0 = 0; i0 < l; i0++)
  {
      /* loop1: multiply a[0..l] with partial b[i0], accumulate resule in acc[0..l] */
      for (c1=0, i1=0; i1 < l; i1++)
      {
          v1 = ((uint64_t)a[i1] * (uint64_t)b[i0]) + acc[i1] + c1;
          acc[i1] = v1;
          c1 = v1 >> 32;
      }

      top = (uint32_t)c1 + topc0;
      c01 = c1 + topc0;

      m1 = (uint32_t)(acc[0] * n->fac);
      c2 = (m1 * (uint64_t)(n->r[0]) + acc[0]) >> 32;

      /* loop2: do some acc[0..l] postprocessing involving some acc[i2-1] = .. acc[i2] ... calculcation */
      for (i2 = 1; i2 < l; i2++)
      {
          v2 = acc[i2] + c2 + (m1 * n->r[i2]);
          acc[i2-1] = v2;
          c2 = (v2 >> 32);
      }

      acc[l-1] = top + c2;
      topc0 = (c01 >> 32) + ((top + c2) >> 32);
  }

  if ( !topc0 && l-1 >= 0 )
  {
      res = l-1;
      if ( acc[l-1] < n->r[l-1] )
        /* possible error in IDA function */
        return res;
      if ( *v28 <= v29 )
        /* possible error in IDA function */
        JUMPOUT(loc_BC46E10);
  }

  res &= 0xffffffff00000000ULL;;
  /* loop3: some final substraction on acc[0-l] */
  for (j0 = 0; j0 < l; j0++)
  {
      v3 = acc[j0] - (uint64_t)n->r[j0] - (uint32_t)res;
      acc[j0] = v3;
      res = -(v3 >> 32);
  }

  return res;
}

Here is the original IDA decompile:

 int64 fastcall sub_BC46730(_DWORD *a1, int64 a2, int64 a3, int64 a4)
{
    _DWORD *v4; // r9@1
    signed __int64 v5; // rdi@1
    __int64 v6; // rbp@1
    __int64 result; // rax@1
    unsigned int v8; // ecx@1
    unsigned int v9; // er13@1
    __int64 v10; // r10@2
    unsigned __int64 v11; // rdi@3
    __int64 v12; // r8@3
    unsigned __int64 v13; // rax@4
    unsigned __int64 v14; // rax@4
    __int64 v15; // r14@5
    unsigned __int64 v16; // r11@5
    __int64 v17; // rax@5
    unsigned __int64 v18; // r11@5
    __int64 v19; // r8@5
    unsigned __int64 v20; // r15@5
    signed __int64 v21; // rdi@6
    _DWORD *v22; // rcx@6
    __int64 v23; // rax@7
    unsigned __int64 v24; // rax@7
    unsigned __int64 v25; // rax@7
    __int64 v26; // rsi@9
    unsigned __int64 v27; // rcx@11
    unsigned int *v28; // rdi@14
    unsigned int v29; // ebx@14
    __int64 v30; // [sp+0h] [bp-40h]@2
    int v31; // [sp+8h] [bp-38h]@2
    int v32; // [sp+Ch] [bp-34h]@2
    v4 = a1;
    v5 = (signed __int64)(a1 + 2);
    v6 = a4;
    *(_QWORD *)(v5 - 8) = 0LL;
    *(_QWORD *)(v5 + 240) = 0LL;
    result = 0LL;
    memset(
        (void *)(v5 & 0xFFFFFFFFFFFFFFF8LL),
        0,
        8 * ((unsigned __int64)((unsigned int)v4 - (v5 & 0xFFFFFFF8) + 256) >> 3));
    v8 = 0;
    v9 = *(_DWORD *)v6;
    if ( *(_DWORD *)v6 )
    {
        v10 = 0LL;
        v31 = *(_DWORD *)(v6 + 1284);
        v32 = v9 - 1;
        v30 = v9 - 1;
        do {
            v11 = 0LL;
            v12 = 0LL;
            /* loop1: */
            do {
                v13 = *(_DWORD *)(a2 + v11) * (unsigned __int64)*(_DWORD *)(a3 + 4 * v10) + v4[v11 / 4] + v12;
                v4[v11 / 4] = v13;
                v11 += 4LL;
                v14 = v13 >> 32;
                v12 = (unsigned int)v14;
            } while ( v11 != 4 * v30 + 4 );
            v15 = (unsigned int)v14 + v8;
            v16 = v14 + v8;
            v17 = *v4;
            v18 = v16 >> 32;
            v19 = (unsigned int)(v17 * v31);
            v20 = (v19 * (unsigned __int64)*(_DWORD *)(v6 + 260) + v17) >> 32;
            if ( v9 <= 1 )
                goto LABEL_16;
            v21 = v6 + 264;
            v22 = v4;
            /* loop2: */
            do
            {
                v23 = v22[1];
                v21 += 4LL;
                ++v22;
                v24 = v23 + v20 + v19 * *(_DWORD *)(v21 - 4);
                *(v22 - 1) = v24;
                v25 = v24 >> 32;
                v20 = (unsigned int)v25;
            }
            while ( v21 != v6 + 4LL * (v9 - 2) + 268 );
            ++v10;
            v4[v30] = v15 + v25;
            v8 = v18 + ((v15 + v25) >> 32);
        }
        while ( v9 > (unsigned int)v10 );
        v26 = 0LL;
        if ( !v8 && v32 >= 0 )
        {
            result = v32;
            v28 = &v4[v32];
            v29 = *(_DWORD *)(4LL * v32 + v6 + 260);
            if ( *v28 < v29 )
                return result;
            if ( *v28 <= v29 )
            LABEL_16:
                JUMPOUT(loc_BC46E10);
        }
        LODWORD(result) = 0;
        do
        {
            v27 = v4[v26] - (unsigned __int64)*(_DWORD *)(v6 + 4 * v26 + 260) - (unsigned int)result;
            v4[v26++] = v27;
            result = (unsigned int)-HIDWORD(v27);
        }
        while ( v9 > (unsigned int)v26 );
    }
    return result;
}
  • 1
    The way I'd go about solving this would be by thoroughly reverse engineering this attached code. I know, we're in RE.SO so that ought to be a weird answer. I could do that for you, but where's the fun in that?! Voting to close, please ask specific questions showing your effort and describe specific challenged you've encountered. – NirIzr Jun 8 '18 at 3:18
  • @NirIzr: I rephrased it a bit. – Konrad Eisele Jun 8 '18 at 7:32
  • Thanks, it does look better but still feels like "here's a chunk of code, please RE it for me". Decompilation output isn't too good in this case and it may be confusing you. I honestly suggest you go through the process of writing this as C code. You'll see this is hardly as complex as it currently seem. – NirIzr Jun 8 '18 at 17:45
  • @NirIzr: Did like you suggested. Can you spot some mathematical construct? – Konrad Eisele Jun 8 '18 at 21:29
  • @NirIzr: I think I found what it is (see posted answer). It is a CIOS Montgomery implementation. – Konrad Eisele Jun 9 '18 at 7:10
4

The structure seems to resemble a Montgomery CIOS implementation

CIOS Montgomery

From the paper on Researchgate: Coarsely Integrated Operand Scanning

More references on CIOS Montgomery: https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf

  • could you add some links/references? e.g. where is the screenshot from? – Igor Skochinsky Jun 9 '18 at 13:45
  • 2
    @IgorSkochinsky: Added the reference. – Konrad Eisele Jun 9 '18 at 14:45

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.