1
$\begingroup$

I have a distributed P2P network.

Everyday, I want each node to have a secret which is only valid for that day, while each of the other remaining nodes on the network will be able to calculate the same value.

However, I do not want any node to be able to precompute this; for example, if it is Monday I do not want any other node to be able to compute the secret until Thursday evening / Friday

Is this possible? What kind of scheme would be needed for this to be effective?

Edit - have to edit here as i do not have enough reputation to comment, thanks for the answers so far, it would be impossible for me to have a centralized server, as this would break my model, can we achieve this without the need of centralized servers, and as for my adversary model, currently i am assuming a network of 5,000 nodes, which anything up to 49% of computing power maybe comprised by an attacker, so a solution needs to take into account the computer power at the disposal of an attacker and cannot relay on it might take x days

Edit 2 - The network is not closed, and yes the secret would need to be known to all 5,000 + nodes, but only be able to be computed / distrubted on a specfic day and valid for that day, i have been looking at network voting systems, all nodes compute a hash based on the previous days hash (like the bitcoin hash challenge where the solution is a nonce when added to another hash has x amount of zeros first) and then the average or mean of these is the secret used for the next 24 hours

$\endgroup$
  • $\begingroup$ I believe this is a re-post of this question from earlier today: security.stackexchange.com/questions/113311/… $\endgroup$ – Mike Ounsworth Feb 10 '16 at 19:28
  • $\begingroup$ OP, it looks like you have multiple accounts. You need to merge them so you can edit your own question and comment on answers. $\endgroup$ – mikeazo Feb 10 '16 at 20:27
  • $\begingroup$ Is the "secret" suppose to be known only to the 5,000 nodes? Or can it be generated by anyone, just not generated until the right time? In other words, is your P2P network closed? $\endgroup$ – mikeazo Feb 10 '16 at 20:29
1
$\begingroup$

If you have the bandwidth to do so, and good communication reliability between the nodes, you can perform a multi-party Diffie Hellman key exchange. The most efficient way to do so would be using X25519, resulting in a shared 256-bit secret between all parties. This can then be used to derive keys and other secret values.

This would also allow new nodes to be added to the network at any time, their public key would be added to the pool and all parties would calculate a new shared secret from the current secret. Parties would have to agree on the time it takes to distribute and calculate the secret, and use that to agree on a set time when that secret would go into effect. If it takes approx 5 mins to distribute all the public keys, they may start communicating to the network 7 mins in advance so there will not be a blackout period where some nodes do not have the secret calculated.

Bandwidth can be reduced substantially if a node trusts other nodes to forward a public key to other nodes on their behalf, and computation can be reduced if a node trusts other nodes to compute an intermediate shared secret from the rest of the network.

A ring-bus design could also be used, where nodes transmit to a single peer, and they receive from a single peer, and transmit the pool they receive which grows by 1 with each transmission. At the end all nodes should have the same list, and they can verify a hash of the key pool with other nodes randomly. If a peer does not have the same hash, but does have all keys, they may have been given an intentionally incorrect key(s), and procedures can be put in place which allow groups of peers to determine where the incorrect key(s) originated (traitor tracing).

The most reliable option is to have a node send its public key to all peers in the network, and receive the keys from all other nodes as well, resulting in $n^2-n$ total key transmissions for $n$ peers, then validate the list with several other peers.

Another option is available if all nodes have a permanent shared secret, the network is open, and nodes can access the internet without restriction. A high entropy public value, such as the output of the NIST randomness beacon, can be processed with HMAC, using the permanent secret as the key. The resulting output would not be able to be generated in advance of the beacon, and will be cryptographically secure because of the generation method, as long as the secret remains isolated to the network.

A combination method can also be used, in advance of the beacon publication, all nodes use Diffie Hellman to agree on a shared key for processing the next days beacon, this gives plenty of time to verify that each node has the same key. This would be the best option for nodes on an open network with a wide range of distribution (high latency), or a very large number of total nodes.

$\endgroup$
0
$\begingroup$

This question in a re-post of this question on security.SE. For completeness, I'll re-post my answer here.

Let's break down the problem into two parts:

The first problem is that you want something that looks random to an outside attacker (ie is unpredictable), but can be computed by anybody in the know.

That sounds a lot like a Cryptographically secure pseudorandom number generator (CPRNG) where all nodes use the same seed. Then each hour (or each minute) you could take the next number in the random sequence - ie current_nonce = cprng.getSequence()[ numberOfHoursSinceLaunch() ];.

The problem that needs to be solved is the Key Distribution Problem - or in this case, the Seed Distribution Problem (since the seed is acting as the shared secret).

You could look at Key Agreement Protocols:

In cryptography, a key-agreement protocol is a protocol whereby two or more parties can agree on a key in such a way that both influence the outcome. ... Protocols that are useful in practice also do not reveal to any eavesdropping party what key has been agreed upon.

Or you could go lower-tech and have an admin place the seed on each node by some secure method (SSH, USB key, etc). Or you could set up a client-authenticated TLS network where each node has a client cert that they can use to request the seed. There are many ways to skin this particular cat.

EDIT in response to re-post on crypto.se:

The second problem is that you want some system where even if a node has all the seeds material, it can not compute the secret until some fixed time in the future. This is actually a commonly asked question on Security.SE and Crypto.SE. The generic name for this is Time-Capsule Cryptography, on a Time-Lock Puzzle. Here is a famous post on the topic. There are solutions to this, but they all have the flavour of "if you run your processor on full, it will take them at least X days to compute the secret. I don't think that is what you want.

A practical solution to this problem would be to give each node a client-SSL cert. Have a master server that generates the nonces, then have the nodes log in to the master using their certs to retrieve the daily nonce.

$\endgroup$
0
$\begingroup$

The way to do this would be to use some publicly available random source. For example, if the nodes in the P2P network can be preprogrammed with 50 stock symbols, you could use the ending price of the 50 stocks each day to generate the next day's secret.

Another option would be to use some information in a block of the bitcoin block chain. For example, here is a recent block. In the block is stored a timestamp. This would allow you to compute the secret by using the first block each day. Within the block, you could use the merkel root value or the hash of the block or any number of values stored in the block.

The point is, you need some public entropy that is not available in advance to an attacker. It may take more than 50 stock symbols, or you may want to use the first $n$ blocks from a day (or the last $n$ blocks from the previous day) as your randomness source. Then you just need some deterministic way to turn that source of entropy into a secret. For example, sort the stocks by symbol alphabetically and store in a bit string of the form <symbol>:<closing price>;<symbol>:<closing price>;..., then compute the SHA-256 hash of that string and use the result as the secret. Any attacker who can predict the closing price of a bunch of stocks likely has better things to do than attack your P2P network (like make a boatload of money).

The paper On the Use of Financial Data as a Random Beacon has more analysis on the stock market idea that would be helpful to you.

$\endgroup$
  • $\begingroup$ I don't understand how you get a secret out of public data. Wouldn't any attacker who knows the algorithm also be able to generate the secret in real-time? The question asked for A) a secret known only to the nodes, and B) not known by any node until the appropriate time. ... unless i'm misreading the question, and secrecy is not a requirement. $\endgroup$ – Mike Ounsworth Feb 10 '16 at 19:53
  • $\begingroup$ @MikeOunsworth I see your point. There are some ambiguities in the question, in my opinion. For example, is the network open to all? If so, why not use public data? If not, you are correct. I'll ask for clarification. $\endgroup$ – mikeazo Feb 10 '16 at 20:26

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.