2

I wasn't sure whether to ask this on crypto or security, but since it involves real-world trust and services, I figured this is the better place.

Consider that me and my friends (whom for the purposes of this question I do not trust) want to lock in a random number that only becomes available at a future date. This could be for example to meet in a random place in a country without being able to set up and investigate the area ahead of time.

It's important that the random number is:

  1. Not knowable before the agreed upon date and time.
  2. Not possible to influence.
  3. Sufficiently random (hash high entropy).

As an example scheme, we could choose the random number to be the hash of the headline of a major newspaper from our chosen date. Barring incredibly extreme measures, this is not knowable, impossible to influence, but has relatively low entropy.

A better scheme might be to choose weather data from an agreed upon source. But there an attack vector hacking the weather station might be more reasonable than influencing the headline of a public newspaper. Or tracking down sensors and messing with those.

What are some good, publicly available, granular (e.g. each hour is better than each day) sources of unknowable, impossible to influence, sufficiently random numbers?

2
  • Assuming that only a moderately volume of PRNs are needed, my personal preference is: Use a secret key of sufficient entropy (e.g. obtained from throwing dice) and agree with the partner on a dynamic session-dependent string (I call it sessionkeyextention) consisting of e.g. date, message number etc. (this string need not be secret) of the session in which the PRNs are needed and have the concatenation of the two employed as the seed for Python's built-in PRNG. (cf. use in my code e.g. s13.zetaboards.com/Crypto/topic/9024439/1/) Commented Jan 29, 2017 at 15:56
  • 1
    headlines can change by region and breaking news. i would use stock quotes because you can get specific times later, you can get a lot of them at once without suspicion, they aren't very tamper-able, and their least significant digits should be hard to predict.
    – dandavis
    Commented Jan 29, 2017 at 22:34

2 Answers 2

1

The top article on the newspaper website really might be what you want as your entropy source. This means that you can use the hash of an article:

  • entropy source: top article of newspaper site
  • length of random number (e.g. SHA256->256Bit or AES-OFB as your stream cipher)
  • Secret: If you fear a third party attack you should keep secret which newspaper you use and choose the newspaper randomly with your partners

Cons:

  • One of your partners could write a script which always shows him the current position generated by the article
  • The top article might change before your partners have calculated the random number

Old answer

This isn't exactly what you asked for, but it might match your use-case.

Shamir's Secret Sharing

If you need the following conditions to be met:

  • You don't trust the persons
  • All persons need to be in a room/or communicating with each other on that day to get the secret

I would suggest using Shamir's Secret Sharing Scheme: https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing

With SSS you can split a secret in multiple pieces e.g. 5 pieces and hand it out to 4 persons (you keep one for yourself). Only if all 5 pieces are together, you can reconstruct the secret.

You may also compute SSS to make it possible that e.g. only 3/5 pieces are needed to get the secret.

5
  • This doesn't work because the person that split the secret knows the secret ahead of time. Plus the secret can be made available at any time (or not available at all) depending on whether the secret holders choose to cooperate.
    – orlp
    Commented Jan 29, 2017 at 19:01
  • Ok, can you explain your use case a bit more detailed? Is your message (e.g. meeting point) available before the given date and can also be encrypted earlier or do you want to encrypt a message at any point of time and everyone knows the source of entropy to get the key?
    – nebulak
    Commented Jan 29, 2017 at 20:36
  • There is no message to encrypt. The goal of the protocol is that anyone can read a random number after a certain time, but not before. For example, I could say to you that we'll meet at latitude 40.x longitude -80.y where x and y are two numbers derived through a hash function from the headline of the new york times of februari the 15th. This way we have a provable random location (because neither of us can control the headline of the NYT) on a future date, without any of us knowing the location beforehand.
    – orlp
    Commented Jan 29, 2017 at 21:25
  • Ok, now I understand what you want....
    – nebulak
    Commented Jan 29, 2017 at 21:48
  • Sorry for writing this in my comment, but I don't have enough reputation to write a comment under sebastian nielsen's answer. Sebastian Nielsen's answer gives you 99^20 possibilities vs. ~ 55^(450words*4letters) = 55^1800 possibilities. What I really like about his answer is the usage of an API...
    – nebulak
    Commented Jan 29, 2017 at 23:47
0

My suggestion is to use the USA lottery game Pick 10 API Example: https://data.ny.gov/resource/r9pz-ziyb.json?draw_date=2016-04-05T00:00:00.000 will return the random number 01 05 06 07 11 14 22 30 32 34 35 37 44 45 54 55 60 61 66 68

Just change the Draw Date to be a date in the future. Since there is a draw daily, you can be certain there is a draw on the agreed date. Make sure to also ensure the meeting time are after the draw time.

The resulting random string, can be hashed with a password to ensure no third party can figure out the location after the agreed date. To prevent getting "impossible" locations (think: middle of sea), I would suggest using one or more selected digit of the hash value, to select out from a list of a few places, that are sufficently reachable and agreed beforehand, BUT in such a amount its practically impossible to rig the places beforehand.

You could for example, use a API that lists all the bus stops inside a specific town, compile a list of it, and then send the list of bus stops (sorted in a specific way), along with the adress of random numbers. And then this are used to select a bus stop inside the list, that can only be selected on the agreed date.

If the list of place is not evenly dividable with any number of bits of the hash, you can either cut away some places, or you could select a number of bits that exceeds the number of places, and then iterate through the list until you count that number, and thus stop at a place.

4
  • @dandavis : Thats not a problem, because every result that the computer finds, will give a valid result. Think like One Time Pad. And you cannot know the useful result, until the agreed upon date passes. Actually, nobody knows the useful result. So even if you can set the computer bruteforcing the lotto result, you would get a list of places. If you read the OPs question, the result of the function is meant to select a place in the word to meet, and they don't want the place to be rigged beforehand by a evil person, either in the group or by a third-party. Commented Jan 29, 2017 at 23:17
  • Thus, you could set the computer to bruteforce it, but then you would have to rig a hella lot of places beforehand. Lets say the list of bus stops are used. You would need to rig every bus stop in the town, because any input of lotto numbers into the function would give one valid bus stop as a result, and since you can't know the lotto number beforehand, you can't also know which bus stop to meet at. Everyone in the group that are going to meet will get the correct bus stop at the same time, so nobody can go there beforehand and plant something or rig it. Commented Jan 29, 2017 at 23:20
  • Note that the OP intends to select a date in the future. So you can't just bruteforce through the dates. The meeting date will be known, and the meeting place will then be revealed automatically at that date, not before. Commented Jan 29, 2017 at 23:22
  • retracted. it still sounds like obscurity to me for some reason, but you're right about my main point.
    – dandavis
    Commented Jan 29, 2017 at 23:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .