Exetools  

Go Back   Exetools > General > General Discussion

Notices

Reply
 
Thread Tools Display Modes
  #1  
Old 07-01-2016, 22:29
dila dila is offline
Friend
 
Join Date: Jan 2010
Posts: 60
Rept. Given: 12
Rept. Rcvd 32 Times in 14 Posts
Thanks Given: 35
Thanks Rcvd at 74 Times in 20 Posts
dila Reputation: 32
Post Yet another key extraction challenge (C++)

The correct key will decrypt some fixed ciphertext into fixed plaintext. The known plaintext is apparently the digits of pi as hex digits.

Code:
#include <iostream>
#include <sstream>
#include <stdint.h>

int main(int argc, char* argv[])
{
  if (argc != 2) {
    std::cout << "Usage: " << argv[0] << " <key>" << std::endl;
    return 0;
  }

  uint64_t k;
  std::stringstream ss;
  ss << argv[1];
  ss >> std::hex >> k;
  if (!ss) {
    std::cout << "Invalid key!" << std::endl;
    return 0;
  }

  uint32_t s = 0;
  for (int i = 0; i < 10000; ++i) {
    s = s * 1664525 + 1013904223;
    int j = s % 64;
    uint64_t a = (k >> j) & 1;
    uint64_t b = (k & 1) << j;
    k ^= a ^ b;
  }

  uint64_t r = k ^ 0x1221777f1c3e4341;
  if (r == 0x3141592653589793) {
    std::cout << "Correct key!" << std::endl;
  } else {
    std::cout << "Wrong key!" << std::endl;
  }

  return 0;
}
Reply With Quote
  #2  
Old 07-15-2016, 05:03
ArC ArC is offline
VIP
 
Join Date: Jan 2003
Location: NTOSKRNL.EXE
Posts: 172
Rept. Given: 0
Rept. Rcvd 1 Time in 1 Post
Thanks Given: 5
Thanks Rcvd at 17 Times in 12 Posts
ArC Reputation: 1
The keys are 0x45584554CF4F4C52 and 0x455845544F4F4C53.


SPOILERS AHEAD


The key observation is that each round has the following transformation pattern:
Code:
0...0 -> 0...0       k_n -> k' (with k_n being the key for round n and k' := a ^ b in the original algorithm)
  0...0 -> 0...0       k_n -> k_{n+1} (with k_{n+1} := k_n ^ k')

1...0 -> 0...1
  1...0 -> 1...1

0...1 -> 1...0
  0...1 -> 1...1

1...1 -> 1...1
  1...1 -> 0...0
So in other words, after each round k_n(s_n) = k_n(0) (with s_n being the amount to shift for round n). k_{n-1} can be deduced from k_n(s_n) (or k_n(0)) and k_n(s_{n-1}) by matching the patterns outlined in the table above. For k_0 we can then match two patterns which is why there're two valid keys.

Some special care needs to be taken for rounds with zero shifts as these are effectively NOPs.
Reply With Quote
The Following 5 Users Say Thank You to ArC For This Useful Post:
Apuromafo (10-10-2016), cachito (07-17-2016), dila (10-13-2016), Kjacky (10-09-2016), ppp1999 (07-16-2016)
  #3  
Old 07-16-2016, 19:31
SMH17 SMH17 is offline
Friend
 
Join Date: Jul 2016
Location: Elysium
Posts: 34
Rept. Given: 0
Rept. Rcvd 0 Times in 0 Posts
Thanks Given: 12
Thanks Rcvd at 11 Times in 9 Posts
SMH17 Reputation: 0
Could you give a sample of the ciphertext encrypted?
Reply With Quote
  #4  
Old 07-16-2016, 20:43
Syoma Syoma is offline
reverse engineer
 
Join Date: May 2009
Posts: 338
Rept. Given: 35
Rept. Rcvd 77 Times in 50 Posts
Thanks Given: 15
Thanks Rcvd at 78 Times in 51 Posts
Syoma Reputation: 77
The ciphertext here is 0x3141592653589793 ^ 0x1221777f1c3e4341.
Forward step is k[i][j] = k[i][0] = k[i-1][j] ^ k[i-1][0], where j = gamma[i]. Simplify and you will see the bit 0 on the current step is result of comparison of bits on the previous step.
Reverse step was explained by @ArC: build the bitlogic operation table and use it to restore source bits. You need to know 2 steps to restore the bit value.
Reply With Quote
  #5  
Old 10-08-2016, 16:49
dila dila is offline
Friend
 
Join Date: Jan 2010
Posts: 60
Rept. Given: 12
Rept. Rcvd 32 Times in 14 Posts
Thanks Given: 35
Thanks Rcvd at 74 Times in 20 Posts
dila Reputation: 32
Congrats ArC for getting the key(s).

I forgot to post my solution program here before:

Code:
#include <iostream>
#include <sstream>
#include <stdint.h>
#include <vector>
#include <set>

int main(int argc, char* argv[])
{
  /* identity matrix */
  int bits[64][64] = {0};
  for (int i = 0; i < 64; ++i) {
    bits[i][i] = 1;
  }

  /* build the parity check matrix */
  uint32_t s = 0;
  for (int i = 0; i < 10000; ++i) {
    s = s * 1664525 + 1013904223;
    int j = s % 64;
    for (int i = 0; i < 64; ++i) {
      int t = bits[0][i];
      bits[0][i] ^= bits[j][i];
      bits[j][i] ^= t;
    }
  }

  /* right-hand side "known" vector */
  uint64_t r = 0x3141592653589793 ^ 0x1221777f1c3e4341;
  int rv[64] = {0};
  for (int i = 0; i < 64; ++i) {
    rv[i] = (r >> i) & 1;
  }

  /* initialize row permutation lookup table */
  int p[64] = {0};
  for (int i = 0; i < 64; ++i) {
    p[i] = i;
  }

  /* run gaussian elimination */
  std::set<int> bf;
  std::set<int> pbf;
  for (int i = 0; i < 64; ++i) {
    bool ok = false;
    for (int j = i; j < 64; ++j) {
      if (bf.find(p[j]) != bf.end()) {
        continue;
      }
      if (bits[p[j]][i]) {
        int t = p[i];
        p[i] = p[j];
        p[j] = t;
        ok = true;
        break;
      }
    }
    if (!ok) {
      /* system is singular */
      /* reduce it from an NxN system to a (N-1)x(N-1) system */
      pbf.insert(p[i]); /* brute force this bit later */
      bf.insert(i);
      continue;
    }
    for (int j = i+1; j < 64; ++j) {
      if (pbf.find(p[j]) != pbf.end()) {
        continue;
      }
      if (bits[p[j]][i]) {
        for (int k = 0; k < 64; ++k) {
          bits[p[j]][k] ^= bits[p[i]][k];
        }
        rv[p[j]] ^= rv[p[i]];
      }
    }
  }

  std::vector<int> bfv;
  bfv.insert(bfv.end(), bf.begin(), bf.end());

  /* back-substitute to solve */
  std::set<int> solved;
  int bf_max = 1 << bf.size();
  for (int bfc = 0; bfc < bf_max; ++bfc) {
    int v[64] = {0};
    for (size_t i = 0; i < bfv.size(); ++i) {
      v[bfv[i]] = (bfc >> i) & 1; /* insert the bits we are brute forcing */
      solved.insert(bfv[i]);
    }
    for (int i = 0; i < 64; ++i) {
      int j = 64 - i - 1;
      if (bf.find(j) != bf.end()) {
        continue; /* we are guessing this */
      }
      int s = -1;
      int t = rv[p[j]];
      for (int k = 0; k < 64; ++k) {
        if (bits[p[j]][k]) {
          if (solved.find(k) != solved.end()) {
            t ^= v[k];
          } else {
            s = k;
          }
        }
      }
      if (s != -1) {
        /* solved one bit */
        v[s] = t;
        solved.insert(s);
      }
    }

    /* copy the solution to an int */
    uint64_t sol = 0;
    for (int i = 0; i < 64; ++i) {
      sol |= (uint64_t(v[i]) << i);
    }

    /* run the original algorithm */
    uint64_t key = sol;
    uint32_t s = 0;
    for (int i = 0; i < 10000; ++i) {
      s = s * 1664525 + 1013904223;
      int j = s % 64;
      uint64_t a = (key >> j) & 1;
      uint64_t b = (key & 1) << j;
      key ^= a ^ b;
    }

    /* test the soluton */
    r = key ^ 0x1221777f1c3e4341;
    if (r == 0x3141592653589793) {
      std::cout << std::hex << sol << std::endl;
    }

    /* repeat to find all keys */
    solved.clear();
  }

  return 0;
}
Reply With Quote
The Following User Says Thank You to dila For This Useful Post:
Kjacky (10-09-2016)
Reply

Tags
c++, crackme

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
armadillo extraction error ES1 demystified bollygud General Discussion 9 02-27-2005 20:42


All times are GMT +8. The time now is 18:51.


Always Your Best Friend: Aaron, JMI, ahmadmansoor, ZeNiX, chessgod101
( 1998 - 2024 )