12
\$\begingroup\$

I have designed a simple random generator that cycles two numbers in a chaotic way using a multiply and modulus method. It works great for that.

If I were to use it as a cipher generator it would however be vulnerable to a known plaintext attack, given that an attacker can reverse engineer the seed from a series of random numbers in a computationally efficient manner.

To prove the cipher broken find a legal pair of seed values that generate 7 zeros in a row in the range [0;255], using as little power, CPU-time etc. as possible.

Here is the random generator written in JavaScript:

function seed(state1,state2){
    //Constants
    var mod1=4294967087
    var mul1=65539
    var mod2=4294965887
    var mul2=65537
    function random(limit){
        //Cycle each state variable 1 step
        state1=(state1*mul1)%mod1
        state2=(state2*mul2)%mod2
        //Return a random variable
        return (state1+state2)%limit
    }
    //Return the random function
    return random
}

//Initiate the random generator using 2 integer values,
//they must be in the ranges [1;4294967086] and [1;4294965886]
random=seed(31337,42)
//Write 7 random values in the range [0;255] to screen
for(a=0;a<7;a++){
    document.write(random(256)+"<br>")
}

I have made a tool for testing candidate number pairs, it can be found here.

For the next 3 days, no spoilers allowed, an answer must contain only a set of numbers, and it should of course be a different set from those posted by previous solvers. Thereafter you are encouraged to post code and explain your approach.

Edit, quarantine is over:
Answers should contain both a unique set of numbers and explanation and code to document the solving method.

Most elegant solution wins.

For the record:
Writing a program that can find a solution quickly is elegant.
Making a program that utilize the features of a GPU efficiently to do it even faster is elegant.
Doing the job on a piece of "museumware" is elegant.
Finding a solution method that can feasibly be utilized using only pen and paper is very elegant.
Explaining your solution in an instructive and easily understandable manner is elegant.

Using multiple or very expensive computers is inelegant.

\$\endgroup\$
  • \$\begingroup\$ Are you sure an answer exists for this? \$\endgroup\$ – Dogbert Feb 28 '11 at 0:10
  • \$\begingroup\$ Yes, there are ~256 of them. And I'm also sure that it's possible to find an answer in a few minutes, given a modern PC and the right programming. \$\endgroup\$ – aaaaaaaaaaaa Feb 28 '11 at 0:50
  • \$\begingroup\$ Just wondering, why are GPUs elegant but not multiple CPUs? \$\endgroup\$ – J B Mar 1 '11 at 14:07
  • \$\begingroup\$ Because they are harder to program efficiently than CPUs. You got to make sure that you are actually utilizing the GPU, no points for having most of the shaders idling because some other subsystem is bottlenecking. And of course you still got to implement an efficient algorithm to score the big points. \$\endgroup\$ – aaaaaaaaaaaa Mar 1 '11 at 15:32
  • \$\begingroup\$ If I submit my working code, it's almost as if I submitted a large bunch of seed pairs. Game end already? \$\endgroup\$ – J B Mar 3 '11 at 8:39
6
\$\begingroup\$

C++, 44014022 / 164607120

It is in C++, uses 1 GB of memory, and took about 45 seconds to find this first pair. I'll update the time once it finds them all.

Code below. It first finds all pairs that generate 4 zeros, then whittles those down by simple trial (see the check method). It finds pairs that generate 4 zeros by generating two large arrays, one which contains the first 4 low-order bytes of the state1 generator, and the second which contains the negative of the first 4 low-order bytes of the state2 generator. These arrays are then sorted and searched for a match, which corresponds to the overall generator outputting 4 zeros to start.

The arrays are too big to store in memory, so it does the work in batches sized to just fit in memory.

Looks like the complete run will take ~12 hours.

Edit: Improved the code so it only takes ~1 hour to get all possible seeds. Now it generates the tables into 256 different files, one for each first byte of output. We can then process each file independently so we don't have to regenerate data.

Edit: Turns out you can generate the 256 subtables individually instead of all at once, so no disk needed. Running time down to ~15 minutes using 256MB.

#include <stdio.h>
#include <stdint.h>
#include <algorithm>
using namespace std;

#define M1 65539
#define N1 4294967087
#define M2 65537
#define N2 4294965887
#define MATCHES 7

// M^-1 mod N                                                                                                                                                        
#define M1_INV 3027952124
#define M2_INV 1949206866

int npairs = 0;

void check(uint32_t seed1, uint32_t seed2) {
  uint32_t s1 = seed1;
  uint32_t s2 = seed2;
  for (int i = 0; i < MATCHES; i++) {
    s1 = (uint64_t)s1 * M1 % N1;
    s2 = (uint64_t)s2 * M2 % N2;
    if (((s1 + s2) & 0xff) != 0) return;
  }
  printf("%d %u %u\n", npairs++, seed1, seed2);
}

struct Record {
  uint32_t signature; // 2nd through 5th generated bytes                                                                                                             
  uint32_t seed;      // seed that generated them                                                                                                                    
};
// for sorting Records                                                                                                                                               
bool operator<(const Record &a, const Record &b) {
  return a.signature < b.signature;
}

int main(int argc, char *argv[]) {
  Record *table1 = (Record*)malloc((N1/256+1)*sizeof(*table1));
  Record *table2 = (Record*)malloc((N2/256+1)*sizeof(*table2));

  for (int i = 0; i < 256; i++) {  // iterate over first byte                                                                                                        
    printf("first byte %x\n", i);

    // generate signatures (bytes 2 through 5) for all states of generator 1                                                                                         
    // that generate i as the first byte.                                                                                                                            
    Record *r = table1;
    for (uint64_t k = i; k < N1; k += 256) {
      uint32_t sig = 0;
      uint32_t v = k;
      for (int j = 0; j < 4; j++) {
        v = (uint64_t)v * M1 % N1;
        sig = (sig << 8) + (v & 0xff);
      }
      r->signature = sig;
      r->seed = k;
      r++;
    }
    Record *endtable1 = r;

    // generate signatures (bytes 2 through 5) for all states of generator 2                                                                                         
    // that generate -i as the first byte.                                                                                                                           
    r = table2;
    for (uint64_t k = (-i & 0xff); k < N2; k += 256) {
      uint32_t sig = 0;
      uint32_t v = k;
      for (int j = 0; j < 4; j++) {
        v = (uint64_t)v * M2 % N2;
        sig = (sig << 8) + (-v & 0xff);
      }
      r->signature = sig;
      r->seed = k;
      r++;
    }
    Record *endtable2 = r;

    sort(table1, endtable1);
    sort(table2, endtable2);

    // iterate through looking for matches                                                                                                                           
    const Record *p1 = table1;
    const Record *p2 = table2;
    while (p1 < endtable1  && p2 < endtable2) {
      if (p1->signature < p2->signature) p1++;
      else if (p1->signature > p2->signature) p2++;
      else {
        check((uint64_t)p1->seed * M1_INV % N1, (uint64_t)p2->seed * M2_INV % N2);
        // NOTE: may skip some potential matches, if p1->signature==(p1+1)->signature or p2->signature==(p2+1)->signature                                            
        p1++;
      }
    }
  }
}
\$\endgroup\$
  • \$\begingroup\$ I didn't think a harddisk would be fast enough to be efficient for the task. Interesting. \$\endgroup\$ – aaaaaaaaaaaa Mar 4 '11 at 19:32

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.