Challenges & "Remote Testing"

[Jackalgirl]

Howdy everyone,

We've recently had a pretty interesting discussion over in PeaceCrusader's thread about how to do a blinded test via the Internet.

In a nutshell, PC claims that a medium he knows will be able to accurately determine a series of two-digit numbers that have been determined randomly (in this case, 5 in all). His original description of the test was that he would choose five numbers, write them down in an envelope, and then leave the envelope at his home while travelling to the Phillipines to receive the medium's guesses. We explained that this was not a blinded test and wouldn't work.

I offered to roll up five two-digit numbers on two of my trusty 10-siders. To prevent against the possibility of me changing the numbers after PC returns and posts the medium's guesses, I offered to PM the results (right after I got them) to a trusted third party (in this case, Loss Leader). That way, if I changed them, it would be revealed when Loss Leader reposted the original numbers I'd sent them. PC accepted this.

But, of course, this doesn't control for a number of things: 1) LL and myself being in cahoots to change the numbers, 2) LL contacting PC or one of PCs friends and giving him the numbers behind his back, etc.

Dan O. popped in with a description of how to create an encrypted checksum. The ideas is that when you create such a "hash", there is no key; it is unencryptable. However, each possible string of numbers or characters produces one, and only one, hash per string. That is, if you change one thing -- a number, the addition of a space, etc -- a different hash will be produced. So he suggested I create a hash of the five numbers I'd rolled plus a series of words (to increase the complexity of the hash) and post it. When PC returns, I'll post the numbers-and-words string I created, and anyone who can make hashes (mmmm...hash...) can take that string, make a hash, and compare it to the one I'd originally posted to make sure it's the same.

I still emailed the numbers to LL as a backup to my own possible attempts at cheating, though.

Dan O. then posted the following...(continued in the next post).

 

[Jackalgirl]

There is one other basic problem with the protocol as specified. Even without LL posting the cipher, if PC were to successfully find the target numbers there would be other non-paranormal explanations (ie: what if LL were in cahoots with PC and sent him the numbers).

To solve this problem, Jackalgirl, and I will each create our own ordered set of 5 random numbers from 00 through 99. We will then create a text file containing our numbers followed by a list of 10 or more words . We will then post the commitment to our message which is the sha1 hash of the text file. The files will be locked and kept in a secure place. Other forum members that have the capability to produce a sha1 hash of a file may join in. Each member submitting a commitment will also choose one other forum member to hold a backup of the file and verify the commitment.

Jackalgirl will identify all the submitted verified commitments and create a document that lists the submitter, the backup and a blank table to list the numbers. At the bottom of the table will be a blank space to list the sums of the columns of digits. The sums will be single digits discarding any carry.

          subbmitted numbers           SHA-1 commitment
     a     b     c     d     e      submitted    verified
    ___________________________________________________________
A.                               -- SHA1(secret2.txt)= 92f55b32d370edd3879111075c32d3cbd02f4896
    _ _   _ _   _ _   _ _   _ _  -- Jackalgirl  Loss Leader
B.
    _ _   _ _   _ _   _ _   _ _  -- Dan O.     ??
C.
...

    ---   ---   ---   ---   ---      -------------------------
SUM _ _   _ _   _ _   _ _   _ _  --  Target Numbers

There needs to be at least 2 pairs of forum members submitting and verifying commitments. The files being committed should not all be exchanged using the same channel where an insider could view them (ie: avoid private messaging if possible).

The task of the test taker is to identify the target numbers that will be filled in after the test period is closed.

At the close of the testing period, after the test taker(s) have provided their answers, Jackalgirl will call for the submitters to post the full text of their numbers and word list. Jackalgirl will fill in the table, add the digits in each column and fill in the target numbers.

Note: this test may be opened to all forum members wether they claim to use paranormal resources or not.

So I have a some questions:

Am I correct in understanding that every participant will be generating a set of x numbers, where x is the agreed-upon number (such as 5, in PC's case)? What's the measure of success, in such a point? What if a group of people offer to join in and then cheat (by sending the numbers to the claimant)? How will that be monitored?

Do you, or does anyone, think that there is a way to set up such a test with rigorous-enough standards to be acceptable to the JREF (of course, we'd have to ask them, but I think most of the regulars here have read enough of the Challenge Apps to know how rigorous that standard is)? What would you do, if you were trying to design a test that could be done collaboratively, via the Internet, in this way?

 

[Thabiguy]

I hope you won't mind if I take the liberty to answer this, as I think I understand the scheme but also see some flaws in it.

Am I correct in understanding that every participant will be generating a set of x numbers, where x is the agreed-upon number (such as 5, in PC's case)? What's the measure of success, in such a point?

Yes, every participant pair (submitter+backup) would secretly generate 5 numbers and submit their hash. The no-carry sum of all secret numbers would be the set that the testee has to guess. It is again a set of 5 numbers, so the measure of success is the same as defined previously: all 5 out of 5, no transpositions, etc.

What if a group of people offer to join in and then cheat (by sending the numbers to the claimant)? How will that be monitored?

The scheme is designed to be resistant to this kind of cheating. Even if a (female) participant is in league with a (male) testee and shares her numbers with him, it won't help him, because the final numbers are determined by the sum of all the secret numbers. Revealing one set of numbers doesn't give the testee any useful information. Even if several participants share their numbers with the testee, he still won't know anything about the final numbers as long as at least one set of numbers remains secret. To compromise the secrecy of this scheme, every participant would have to be in league with the testee. When participants are openly allowed to join, it is assumed that such scenario would be unlikely.

Participants also cannot cheat by changing their chosen set of numbers, because then their published hash won't match.

The scheme, however, has other flaws. A major flaw is that it is wide open to sabotage. The testee can ask two of his friends to participate (as a submitter-backup pair). They will submit a hash of their numbers and then disappear. When the time comes to find out what the actual final numbers are, to verify the testee's prediction, they will be unreachable and thus their numbers, and the final sum, will remain unknown. It won't help to use the testee's prediction to deduce what their numbers would have to be and test their hash against that, because nobody knows what words they used to randomize their hash. - The test is sabotaged and the testee's claim remains unverified. This is, of course, a very favourable outcome for the testee.

Another reason why the scheme is unsuitable for paranormal testing is that it shifts the goalpost for the testee. If a testee claims to be able to read the numbers from your mind, his chance to prove that is taken away, because nobody knows the final set of numbers until after the test. Similarly, if a testee claims to be able to remotely view the numbers printed on participants' desks, he can't do that, as the final numbers are unknown.

One could say that the testee can read all the sets individually and then compute the final numbers himself, but this is a major goalpost shift: if there are N participants, he'll have to read N*5 numbers. Effectively, he's doing the test over and over again for each participant separately. And if you're having him do that, then all the stuff with adding the numbers together is unnecessary: you may just as well verify each guess separately, which eliminates the possibility of sabotage.

One kind of claim that won't be affected is when the testee claims to be able to predict the future and thus read the final numbers from the future. But then the entire scheme is unnecessary. It is much easier and much more secure to simply not generate the numbers until after the test. To demonstrate to online participants that no cheating has taken place, it is enough to choose a public lottery as a random number generator. Predicting natural events (weather-related, earthquakes and such) would be even more solid.

 

[ChaosEngineer]

Another risk of this particular set-up is that it might be possible to brute-force the solution. If we're looking at 10 digits, there are only 10 billion possible combinations and I think a computer could cycle through them in a reasonable amount of time. (The solution is to use a "salt"; some random data appended to the end of the 10 digit string.)

 

[Cuddles]

The ideas is that when you create such a "hash", there is no key; it is unencryptable.

I assume this was meant to say "undecryptable, it being encrypted already.

However, I don't think this would ever be acceptable to the JREF. As ChaosEngineer says, a string of numbers has very few combinations to check (relatively speaking). Adding extra characters to the string will make it take longer to work out, but how much longer? Given that there are a million dollars at stake, how could you rule out someone actually giving their computer a few months to work it out? There are hackers out there that can control hudreds of thousands of computers at a time. What if they decided to do a little distributred computing instead of spamming people? This sort of securtiy is OK for every day stuff because no-one can decrypt everything, especially since they won't even know where to look most of the time. However, if you put out a single code worth a million dollars you can guarantee that someone will find the time to break it.

 

[Davide]

Another risk of this particular set-up is that it might be possible to brute-force the solution. ...

Yes, it would be except that the proposed protocol is mor complex than simply hashing ten digits. To quote Jackalgirl quoting Dan O.,

...Jackalgirl, and I will each create our own ordered set of 5 random numbers from 00 through 99. We will then create a text file containing our numbers followed by a list of 10 or more words ....

It's the whole text file of number plus words that gets hashed. Finding a string of 5 two-digit followed by a list of 10 or more words that hashes to the correct result is extraordinarily hard.

Still the protocol is subject to the other problems Thabiguy pointed out, and they're pretty serious. I don't think we have a good answer yet. And I suspect that adding more crypto doodads isn't going to help, mostly because the protocol not only has to work, it has to be understandable enough for testees who don't have mathematics degrees to be comfortable using.

 

[Jackalgirl]

I assume this was meant to say "undecryptable, it being encrypted already.

You're quite right -- that's what I meant. My fingers decided to sabotage me. ; )

However, I don't think this would ever be acceptable to the JREF. As ChaosEngineer says, a string of numbers has very few combinations to check (relatively speaking). Adding extra characters to the string will make it take longer to work out, but how much longer? Given that there are a million dollars at stake, how could you rule out someone actually giving their computer a few months to work it out? There are hackers out there that can control hudreds of thousands of computers at a time. What if they decided to do a little distributred computing instead of spamming people? This sort of securtiy is OK for every day stuff because no-one can decrypt everything, especially since they won't even know where to look most of the time. However, if you put out a single code worth a million dollars you can guarantee that someone will find the time to break it.

What Davide said, above -- also, the hash isn't the string, encrypted. It's an encrypted checksum. I imagine that it would theoretically be possible to figure out what combination of characters and spaces could create a checksum, but at what point do we reach something that's impossible, even for (say) a distribued computer network to break in, say, two weeks' worth of time?

 

[Dan O.]

We can get a good feel for the probability if cracking a hash or encryption code by looking at existing distributed processing projects. One that I worked on has been trying to crack a 72 bit code for over 4 years now with 1000's of computers and they are less than 1/200th of the way through. They will burn up a million on electric bills alone before cracking that code.

Compare this to the combinations in the hash that I suggested. The 10 digit number is equivalent to about 33 bits. Assuming ones vocabulary contains around 1000 small words, a list of 10 words would add another 100 bits for a total of 133 bits. That means there are roughly 2^133 possible messages to try looking through for the one that matches the hash. This is a very big haystack.

This protocol that I developed was for one specific task and not meant as a general solution. I'm not sure that you would even want a remote testing protocol for the final MDC test but it should be quite suitable for a blinded self test before submitting for the MDC.

The problem of using lottery drawings as a target of the test should be obvious. If the claimant could pick the lottery numbers they wouldn't be interested in the measly $1M.

 

[Jackalgirl]

We can get a good feel for the probability...

Thank you very much for the numerical clarification!

This protocol that I developed was for one specific task and not meant as a general solution. I'm not sure that you would even want a remote testing protocol for the final MDC test but it should be quite suitable for a blinded self test before submitting for the MDC.

I agree with you wholeheartedly. Given that JREF is pretty good at finding local skeptics and mentions, in the rules, that they are willing to essentially "deputize" someone to act on behalf of JREF for a test/final test, I think it would be unlikely that this kind of effort would be necessary. But it's still useful, I think, just in case (and for playin' around).

The problem of using lottery drawings as a target of the test should be obvious. If the claimant could pick the lottery numbers they wouldn't be interested in the measly $1M.

Indeed!

 

[drkitten]

However, I don't think this would ever be acceptable to the JREF. As ChaosEngineer says, a string of numbers has very few combinations to check (relatively speaking). Adding extra characters to the string will make it take longer to work out, but how much longer? Given that there are a million dollars at stake, how could you rule out someone actually giving their computer a few months to work it out?

In simplest terms .... by doing it correctly.

I can probabilistically "guarantee" that no one will be able to reverse the hash within the expected lifetime of the planet Earth. I can probabilistically "guarantee" that no one will be able to reverse the hash within the expected lifetime of the Earth using a network of computers too large to fit (physically) within the Solar System and using more than the Sun's entire output to power that network.

To put it in perspective, this site reports on a major breakthrough against the SHA-1 hash algorithm that reduces the expected attack time for down to 4000 CPU years. Prior to this breakthrough -- or using other, similar, algorithms to which this would not apply -- the expected time to break such a hash would be about 1000 times greater.

Give me a network of a million computers, and I'll give you an answer sometime in 2011, but probably not sooner. Is that secure enough for you?

 

[Thabiguy]

The problem of using lottery drawings as a target of the test should be obvious. If the claimant could pick the lottery numbers they wouldn't be interested in the measly $1M.

This is good observation and a food for thought for any believer in common occurrence of paranormal prediction. However, it is not a problem for the test and does not make lottery drawings inappropriate as a source of randomness. If there is a person claiming to be able to predict the future and willing to be tested, it is irrelevant why they chose to be tested rather than use their powers to win the lottery. The quality of randomness and independence of a public lottery is not affected by reasoning behind the testee's decisions.

 

[Cuddles]

To put it in perspective, this site reports on a major breakthrough against the SHA-1 hash algorithm that reduces the expected attack time for down to 4000 CPU years. Prior to this breakthrough -- or using other, similar, algorithms to which this would not apply -- the expected time to break such a hash would be about 1000 times greater.

Give me a network of a million computers, and I'll give you an answer sometime in 2011, but probably not sooner. Is that secure enough for you?

Not even close. 4000 CPU years is nothing. The challenge has existed for around 40 years so far, so we could assume that any remote challenge would have a lifetime of at least a few years. As I said, there are people who have access to thousands, or even millions, of computers, legally or illegally and, as you say, they could break it in just a few years. 4000 years only seems a lot if you have lots of things to break. This sort of security is fine for emails and things, but if you put one single code out then it really isn't all that hard to break. It would take an effort, but how much effort is a million dollars worth? Also bear in mind, 10 years ago they thought the encryption around was adequate, but now new standards are obsolete before they are even introduced. Even if we assume that a code would be unbreakable with today's computers, unless a remote challenge was only available for a very limited amount of time there is no way to ensure it won't be broken in just a few years.

 

[petre]

I can't find a definitive source on CPU years, but I'm pretty sure 4000 CPUs would be enough to complete 4000 CPU years of work in about...I dunno...a year?

 

[drkitten]

Not even close. 4000 CPU years is nothing.

That's right. That's why I specified that I would use the harder -- unbroken -- system, the one that results in about 4 million CPU years. Give me a million computers and I can break it in four years (2011). (Actually, if you do the math, it would be about 8 million CPU years, so I wouldn't expect a result much before 2015.)

Of course, that's only with me using a 160-bit secure hash (like SHA-1). If I use a stronger/larger hash function (like SHA-512/384), I can make the system more or less arbitrarily secure. At a rough guess, SHA-512/385 would be about 2^160 times stronger than SHA-1, which means that instead of taking 4000 CPU years to break, it would take 4,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 CPU years. Give me a network of a trillion computers and I can break it in "only" 4,000,000,000,000,000,000,000,000,000,000,000,000,000 years, a mere 1,000,000,000,000,000,000,000,000,000,000 times the age of the earth so far. How secure did you want Randi's money to be, again?

 

[Dan O.]

To put it in perspective, this site reports on a major breakthrough against the SHA-1 hash algorithm that reduces the expected attack time for down to 4000 CPU years.

This attack does not reveal a message that was hashed with SHA1 but only allows an attacker to find a "collision" where 2 different messages generate the same hash. Such collisions could still be used to cheat against the applicant by for instance having two sets of numbers and if the applicant guesses one set revealing the other set. To protect against such a cheat, either a stronger hash could be used, the time frame open to construct a collision could be limited or the format of the message could be limited.