Proposal: web-based random state scrambles for 3x3

[joey]

Only people in the same group, in the same competition though.

 

[Cride5]

Given a certain scramble/cube state, would it be possible for anyone who reverse-engineers cube explorer, and the pseudo random number generator being used to predict the next scramble (using a computer)?

Yes. Especially now that we have the source code. The problem is that while Mersenne Twister is very good once it's running, the scrambler starts it with System.currentTimeMillis() as seed. There are thus only 86.4 million possibilities per day. Encoding a scramble state in 9 bytes and its corresponding seed in 5, I could store all first scrambles and their seeds for a whole month in a 34 GB file. So I could prepare that before a competition, look at the first scramble of a round, look up its seed in my file, and use it to generate the next four scrambles.

This is a good point actually, and is quite a concern. If you were to know (for example) the hour in which the scrambles were being generated then that would only be 3.6 million cubes to check. It would be quite feasible to go to a competition with a database of scramble sequences. As soon as you have the first scramble in the sequence, then all subsequent scrambles can be worked out. NOTE: This is also a problem for the current random-moves generators used officially.

Anyway, Java implements a SecureRandom object which creates cryptographically secure random numbers. When setting the seed it uses hardware sampling to guarantee that there is an equal chance of entering every possible generator state on initialisation. For more information see:
http://www.javamex.com/tutorials/random_numbers/securerandom.shtml

Like the Mersenne Twister it also has a long enough period (2^160, ~10^48) to ensure all possible cube states are reachable. The problem, however is that the period isn't guaranteed. The 2^160 figure is for Sun's implementation of the SecureRandom class. The period may vary between JVMs, but I doubt it will be as low as 4.3 * 10^19.

So there are two options:
(1) Use only the SecureRandom generator
(2) Seed the Mersenne Twister with a number generated from SecureRandom

 

[qqwref]

to coin a phrase for the enjoyment of Lord Gottlieb

Am I supposed to be insulted by this? Because it's closer to "mystified".

1) NO corner should already be correctly positioned (relative to the center pieces on odd NxNXN cubes).

2) Now using any corner as reference(ignoring centers), this corner, and only this corner, can be viewed as solved relative to all the other corners. [...]

3) Testing with all the corner pieces as the solved reference (ignoring centers), NO edge piece should be solved relative to the position of that corner. This will reject all cases that have prebuilt C/E pairs. Also testing so that NO edge piece is correctly placed relative to the position of the centers(i.e. no edge may already be solved). Optionally, edge pieces could also be tested relative to each other (ignoring centers) so that any 2 that could be correctly positioned with a single center slice move could also be rejected.

This is ridiculous. There will be very few scrambles left after these tests, and those that ARE left will represent the most difficult (in some sense), not random ones. By generating random positions we are testing people on every type of scramble, not just ones that you think are difficult. Besides, these scrambles won't be equally difficult to every method like randomized ones will. I notice you include nothing about edge orientation, for instance, meaning ZZ solvers won't find these scrambles harder than normal. It is a fact that you cannot make scrambles hard for everyone.

4) Using CubeX to test the solution length, and only keep those that can be solved within the range 15f>x>19f. The actual scramble should be generated with the same program.

Do you mean this? Because there's no way that will generate a solution less than 20f for a scrambled position. I'll assume you mean CubeExplorer or something analogous. Anyway the range of 16f to 18f is arbitrary and silly. There is nothing wrong with a 15f* cube (it's not easier, generate a few), and there is nothing wrong with a 19f* cube (it's not harder, generate a few). Maybe the difference would matter if people solved cubes optimally (fewest moves?) but they don't and it doesn't. If you don't believe me that optimality means very little about solve difficulty, I can provide a 16f* cube whose optimal solution is a Fridrich solution.

Now this will produce a REAL scramble that has NOTHING already solved, and no cheap solution should even be possible. And it would be nice if these scrambles could be generated at the competition site, with a hardware reseeded rnd# just prior to the actual events.

The total# of these possible "Competition-Grade" scrambles would end up to be a small% of all possible random positions, but still way more than would ever be needed. Some distribution studies would be required before implementing, but I would much prefer something like this, over the random state, but-not-always-so-scrambled state, scramblers, we have now.

It is always scrambled, just not always equally difficult. You seem to think it's better to make "real" scrambles, but did you think about how much people already know about the scrambles? If this policy were to be instituted, people would be aware that scrambles are setup in a specific way, and would modify their methods accordingly. People would practice these kinds of scrambles, get used to very slightly more difficult first steps and learn special tricks for them, and after a while cubers would be getting FASTER averages on your "competition-grade" scrambles than on random scrambles. Whenever scrambles have to satisfy a restrictive property, you are giving competitors a lot of information about their scrambles before they see them, and that gives people an advantage compared to knowing nothing about a completely random mix.

 

[reThinking the Cube]

This is ridiculous. There will be very few scrambles left after these tests,

How many exactly is "very few"? Do you think you could solve those "very few" in your lifetime?

and those that ARE left will represent the most difficult (in some sense), not random ones. By generating random positions we are testing people on every type of scramble, not just ones that you think are difficult.

My opinion, is that a scramble should have as little as possible already in the solved state. I don't care about making the scrambles more difficult, or harder for anyone, but just want to reject those that are far too easy (random, but relatively unscrambled).

and that gives people an advantage compared to knowing nothing about a completely random mix.

Which would give people the most advantage, the ones I propose, or one of these?

What was the official WCA scramble for these solves?

1) Erik Akkersdijk 0.96 Netherlands, Geneva Open 2008
[F' U' F' R2 F2 R U2 R' U F U R2 U F' U2 F2 R' U R F' R U2 R2 U' F] - Edward Lin

2) Rowe Hessler 1.03 USA, Brown Cubing Day 2009
[R2 F2 U R'] - Kyle Barry

3) Lucas Garron 1.06 Germany, Stanford Fall 2009
[U' F R2 F' R'] - Ian Jones, David Shi

4) Cameron Almasi 1.15 USA, Stanford Fall 2009
[U' F R2 F' R'] - Ian Jones, David Shi

5) Dan Dzoan 1.33 USA, Stanford Fall 2009
[U' F R2 F' R'] - Ian Jones, David Shi

6) Andy Bridger 1.36 USA, Stanford Fall 2009
[U' F R2 F' R'] - Ian Jones, David Shi

7) Justin Adsuara 1.36 USA, Stanford Fall 2009
[U' F R2 F' R'] - Ian Jones, David Shi

8) Edouard Chambon 1.39 France, Geneva Open 2008
[F' U' F' R2 F2 R U2 R' U F U R2 U F' U2 F2 R' U R F' R U2 R2 U' F] - Edward Lin

9) Antoine Piau 1.46 France, World Championship 2009
[4-move solution (iirc)] - Dan Cohen

10) Tim Reynolds 1.46 USA, Brown Cubing Day 2009
[R2 F2 U R'] - Kyle Barry

11) David Shi 1.47 USA, Stanford Fall 2009
[U' F R2 F' R'] - Ian Jones, David Shi

12) Eric Limeback 1.52 Canada, Toronto Open Summer 2009
[could be solved by U2 R U R] - Justin Jaffray

13) Anthony Searle 1.55 Belize, Toronto Open Summer 2009
[could be solved by U2 R U R] - Justin Jaffray

14) John Tamanas 1.55 USA, Brown Cubing Day 2009
[R2 F2 U R'] - Kyle Barry

15) Michal Robaczyk 1.55 Poland, Polish Open 2009

16) Vicente Albíter Alpízar 1.55 Mexico, Mexican Open 2008

17) Javier París 1.63 Spain, MurciaOpen2008
[F' D2 L2 B' D' B R' D' R' U L' B' L2 U' L2 U2 R2 B2 R2 U2 B2 R2 D R2 D2]

18) Michal Pleskowicz 1.66 Poland, Polish Open 2009
[F' U F U2 R'] - Michal Pleskowicz

19) Arnaud van Galen 1.68 Netherlands, Geneva Open 2008
[F' U' F' R2 F2 R U2 R' U F U R2 U F' U2 F2 R' U R F' R U2 R2 U' F] - Edward Lin

20) Jai Gambhir 1.69 Canada, Toronto Open Summer 2009
[could be solved by U2 R U R] - Justin Jaffray

21) Erik Johnson 1.72 USA, US Nationals 2009

22) Justin Jaffray 1.72 Canada, Toronto Open Summer 2009
[could be solved by U2 R U R] - Justin Jaffray

23) Patrick Jameson 1.72 USA, Armonk Spring 2008
[probable solution was U R' U R' U2] - Tim Reynolds

24) Thomas Watiotienne 1.75 France, World Championship 2009
[4-move solution (iirc)] - Dan Cohen

25) Anton Rostovikov 1.77 Russia, World Championship 2009
[4-move solution (iirc)] - Dan Cohen

26) Thompson Clarke 1.77 Canada, Toronto Open Summer 2009
[could be solved by U2 R U R] - Justin Jaffray

27) Jacco Krijnen 1.80 Netherlands, Dutch Open 2009

28) Milán Baticz 1.80 Hungary, Silesia Open 2009
[R U R' F' L F L' U2 L' U2 L] - was solution, Milan Baticz

29) Michael Nguyen 1.86 USA, Stanford Fall 2009
[U' F R2 F' R'] - Ian Jones, David Shi

30) Phil Thomas 1.86 USA, Wisconsin Open 2008

31) Sebastián Pino Castillo 1.86 Chile, Bahia Summer 2010

32) Laetitia Lemoine 1.88 France, World Championship 2009
[4-move solution (iirc)] - Dan Cohen

33) Marwin-Peter Kurth 1.96 Germany, World Championship 2009
[4-move solution (iirc)] - Dan Cohen

34) Timothy Sun 1.96 USA, Xi'an Open 2009
.

 

[Cride5]

(2) Seed the Mersenne Twister with a number generated from SecureRandom

The scrambler applet has been updated to do this.

 

[Stefan]

REAL scramble that has NOTHING already solved

Contradiction right there.

Please keep that annoying argument in your threads, don't contaminate this one.

So there are two options:
(1) Use only the SecureRandom generator
(2) Seed the Mersenne Twister with a number generated from SecureRandom

I knew SecureRandom, but didn't know about its seeding. Quite cool. And it has the generateSeed() method for precisely your option 2:
http://java.sun.com/j2se/1.4.2/docs/api/java/security/SecureRandom.html#generateSeed(int)

 

[qqwref]

This is ridiculous. There will be very few scrambles left after these tests,

How many exactly is "very few"? Do you think you could solve those "very few" in your lifetime?

I don't know how many, but your conditions are quite restrictive, so I assume it's a very small fraction of the set of cube positions. Someone would need to compute this.

I don't care about making the scrambles more difficult, or harder for anyone, but just want to reject those that are far too easy (random, but relatively unscrambled).

But a huge proportion of the scrambles you are rejecting are NOT "far too easy" in any sense.

Which would give people the most advantage, the ones I propose, or one of these?
[2x2 stuff...]

3x3 is not 2x2.

 

[Cride5]

So there are two options:
(1) Use only the SecureRandom generator
(2) Seed the Mersenne Twister with a number generated from SecureRandom

I knew SecureRandom, but didn't know about its seeding. Quite cool. And it has the generateSeed() method for precisely your option 2:
http://java.sun.com/j2se/1.4.2/docs/api/java/security/SecureRandom.html#generateSeed(int)

Yup, It's pretty cool that this is provided in the standard Java library
I've used the following code to seed the MTRandom generator:

	byte[] seed = null;
	try{
		seed = SecureRandom.getInstance("SHA1PRNG").generateSeed(9);
	} catch(NoSuchAlgorithmException e) {
		seed = new SecureRandom().generateSeed(9);
	}

	return randomCube(new MTRandom(seed));

I chose a seed of 9 bytes (size 2^72), because it is the smallest sequence of bytes which is large enough to access all cube states. The code also prioritises the SHA1 pseudorandom generator, falling back to the system default if it isn't available.

 

[Cride5]

I'm still quite concerened about the other JavaScript scramblers we're using.

If I can find the time I might build a program to test/demonstrate the weakness. If it works, the program will take two parameters, a scramble generated from here:
http://www.worldcubeassociation.org...e.htm?size=4&num=5&len=40&col=yobwrg&multi=on
and time period in which the scramble was generated. It will then return the sequence of future scrambles. This should theoretically be possible.

I think it might be an idea to secure up these JavaScript generators. We can fix the limited state-size issue by simply including a Mersenne Twister library, such as the one here:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVASCRIPT/java-script.html

But the most concerning weakness is a bit harder to fix. JavaScript currently provides no library for generating cryptographically secure random numbers. There's a good discussion about it here:
http://news.ycombinator.com/item?id=748430
and also here:
http://stackoverflow.com/questions/...pts-random-implementation-in-various-browsers

I think a feasible option though, might be just to capture mouse movements and combine that with the current time to generate the numbers. There's a demonstration of it here:
http://tim.dierks.org/2007/03/secure-in-browser-javascript-password.html
.. with a criticism here:
http://www.webappsec.org/lists/websecurity/archive/2008-01/msg00111.html

It may not be perfect, but it would certainly be a big improvement over the current situation!

 

[brunson]

There are sources of true entropy available on the net. That would be a better source of a seed. Linux has a source of real entropy, but it's easily depleted. I used it as a seed in a pure python implementation of Marsaglia's CMWC4096. I posted the code here, but that was before pjk switched servers, so I think it's gone.

That was in response to a discussion we were having on the period of the Mersenne Twister being so much lower than the number of positions of the cube and whether it meant that we were only reaching 2^32 scrambles. CMWC4096 has a period of 2^131086, which is a bit of an overkill, especially considering it uses and array of up to 16 32 bit seeds (if I remember correctly).

I think the question boiled down to: is the MT implementation locked into a single cycle, where the seed just picks your starting position in the cycle. If I remember correctly, this stuff:

        private final static int N = 624;
        private final static int M = 397;
        private final static int MAGIC[] = { 0x0, 0x9908b0df };
        private final static int MAGIC_FACTOR1 = 1812433253;
        private final static int MAGIC_FACTOR2 = 1664525;
        private final static int MAGIC_FACTOR3 = 1566083941;
        private final static int MAGIC_MASK1   = 0x9d2c5680;
        private final static int MAGIC_MASK2   = 0xefc60000;
        private final static int MAGIC_SEED    = 19650218;
        private final static long DEFAULT_SEED = 5489L;

can be changed to generate different cycles, but most implementations hard code them, just like the implementation in your source.

 

[Portponky]

The period of MT is much bigger than the cube group size. There's nothing wrong with MT, it's a perfect random generator for our use. The only issue is it is probably quite easy to come up with a seed collision attack.

I don't think it's a good idea to change the coeficients it uses cause (a) it's open source anyway so that wouldn't prevent a seed attack, and (b) other numbers may be significantly worse.

 

[JBCM627]

qq has mentioned this before, but:
http://www.random.org/
This means you'll need an internet connection to generate scrambles, but if you don't have an internet connection, a number of these could still be stored in advance.

 

[Cride5]

qq has mentioned this before, but:
http://www.random.org/
This means you'll need an internet connection to generate scrambles, but if you don't have an internet connection, a number of these could still be stored in advance.

Lol ninja'd ... yea I was going to suggest the JavaScript scrambler could make calls to something like:
http://www.random.org/integers/?num=1&min=0&max=100&col=1&base=10&format=plain&rnd=new

... random.org does impose quota limits, but because only one seed is needed per page load this shouldn't be a problem. The only problem with this (as JBCM pointed out), is that it needs a connection.

 

[Herbert Kociemba]

Yup, It's pretty cool that this is provided in the standard Java library
I've used the following code to seed the MTRandom generator:

	byte[] seed = null;
	try{
		seed = SecureRandom.getInstance("SHA1PRNG").generateSeed(9);
	} catch(NoSuchAlgorithmException e) {
		seed = new SecureRandom().generateSeed(9);
	}

	return randomCube(new MTRandom(seed));

I chose a seed of 9 bytes (size 2^72), because it is the smallest sequence of bytes which is large enough to access all cube states. The code also prioritises the SHA1 pseudorandom generator, falling back to the system default if it isn't available.

I would prefer to seed the random generator only once for example when the program is starting. Reseeding after a few calls/ for every new cube is not recommended as far as I know (but I must admit I cannot explain why).

 

[Stefan]

... random.org does impose quota limits, but because only one seed is needed per page load this shouldn't be a problem. The only problem with this (as JBCM pointed out), is that it needs a connection.

If you're using it online, you do have a connection, and if you're using it offline, you did have a connection when you downloaded it. So we could implant a proper random seed at download (using let's say php instead of static html files). You and I downloading the same scrambler would get different seeds. Then when it's run, additionally use the system time to randomize further (don't want the downloaded scrambler generate the same scrambles over and over again).

Also, security restrictions could play a role. I'm not sure Javascript is allowed to connect to a server other than the one it came from. So asking random.org might not work because of that.

 

[JBCM627]

I would prefer to seed the random generator only once for example when the program is starting. Reseeding after a few calls/ for every new cube is not recommended as far as I know (but I must admit I cannot explain why).

I can't find much on it other than this article:

When adding entropy to a system, it is best to collect a lot of entropy and seed all at once, instead of seeding a little bit at a time. We will illustrate why by example. Suppose you seed a generator with one bit of entropy. An attacker has only one bit to guess, which can be done accurately after two outputs. If the attacker completely compromises the state after two outputs, and we then add another bit of entropy, he can once again guess the state easily.
If we add one bit 128 times, there is still very little security overall if the generator state is compromised. However, if you add 128 bits of entropy to the generator all at once, an attack should essentially be infeasible.

I'm not sure Javascript is allowed to connect to a server other than the one it came from. So asking random.org might not work because of that.

That is a good point... generally you can't httprequest data from another domain.

 

[Lars Petrus]

... random.org does impose quota limits, but because only one seed is needed per page load this shouldn't be a problem. The only problem with this (as JBCM pointed out), is that it needs a connection.

If you're using it online, you do have a connection, and if you're using it offline, you did have a connection when you downloaded it. So we could implant a proper random seed at download (using let's say php instead of static html files). You and I downloading the same scrambler would get different seeds. Then when it's run, additionally use the system time to randomize further (don't want the downloaded scrambler generate the same scrambles over and over again).

Also, security restrictions could play a role. I'm not sure Javascript is allowed to connect to a server other than the one it came from. So asking random.org might not work because of that.

A simpler approach is to have the user enter a string that's used as a part of the seed.

If we can trust the organizer to keep it secret, this is safe.

If we can't trust the organizer, there is no way to make this safe anyway.

 

[Cride5]

I would prefer to seed the random generator only once for example when the program is starting. Reseeding after a few calls/ for every new cube is not recommended as far as I know (but I must admit I cannot explain why).

Doh! What a stupid mistake :fp ...I wasn't intending on re-seeding it every time. In the process of fixing now. Thanks for pointing that out ... that really is a big facepalm for me!

 

[Portponky]

A simpler approach is to have the user enter a string that's used as a part of the seed.

This is the best solution by far.

 

[Cride5]

I would prefer to seed the random generator only once for example when the program is starting. Reseeding after a few calls/ for every new cube is not recommended as far as I know (but I must admit I cannot explain why).

Doh! What a stupid mistake :fp ...I wasn't intending on re-seeding it every time. In the process of fixing now. Thanks for pointing that out ... that really is a big facepalm for me!

OK this has been fixed and updated in the demo system. I would encourage folks to check the source to make sure there aren't any more silly errors like that.

A simpler approach is to have the user enter a string that's used as a part of the seed.

This is the best solution by far.

Yup, I would agree with this. I think seeding a JavaScript implementation of MT with the current system time, and a user input value (generated from random.org if possible) is probably the best security we could hope for.