Can two devices share a common secret in a way that an adversary who compromises one of the two devices after deployment is unable to reconstruct the shared secret, under the following assumptions:

  1. before deployment, there is a secure initialization phase, e.g., in which a pre-established secret is stored in both devices
  2. after deployment, the two devices are physically separated (possibly a few miles/km apart from each other) and unable to communicate with each other (including via any 3rd party)
  3. during attack, the targeted device is offline (inoperable) for a few minutes
  4. after attack, a compromised device leaks all data, thus, among others, all secrets
  5. both devices do not possess tamper-proof hardware, not allowing to delete secrets upon tampering, etc.

Due to the assumptions, the common secret must be volatile, thus, being constantly changing data. Note that using a PRNG with a pre-established secret is not enough, since an adversary can after device compromise reconstruct the PRNG stream (having the pre-established secret).

A possible solution to this problem may be using an entropy source that produces the same random data on the two devices and has a very high throughput (maybe atmospheric noise or similar?). Before deployment, both devices pre-establish a secret filter that allows them to process the sheer amount of entropy from the source during deployment (e.g., listening on a specific channel, XORing every Xth bit, etc). During deployment, both devices constantly derive the common secret using entropy source and filter. An adversary may try to compromise a device, retrieve the secret filter, and reconstruct the common shared secret. However, as the target device is offline for some time during attack (see assumptions), the adversary misses so much data from the entropy source that he is unable to buffer this data and thus is unable to reconstruct the common secret in the end using the secret filter.

Do you know whether there is an entropy source that provides these properties? Or do you know another solution to this problem?

  • 1
    $\begingroup$ If they can't communicate, why do they have a shared secret? More details on the use-case may be helpful in understanding your problem. $\endgroup$ – mikeazo Jan 3 '17 at 15:35
  • 2
    $\begingroup$ It's easy enough to design a system where the attacker doesn't get access to previous data/secrets (essentially, "perfect forward secrecy"). I don't see how, if the compromised device leaks everything, how you can protect current secrets... $\endgroup$ – poncho Jan 3 '17 at 15:39
  • $\begingroup$ Here an exemplary use-case: At an arbitrary point in time (maybe after years), the two devices will communicate with each other. Comparing its own shared secret with the shared secret of another device, a device can decide whether the other device was tampered by an adversary (shared secrets differ), or not (shared secrets are equal). $\endgroup$ – randomhenry Jan 3 '17 at 15:41
  • $\begingroup$ @poncho: see 3rd paragraph (A possible solution...), assuming that such an entropy source exists? $\endgroup$ – randomhenry Jan 3 '17 at 15:43
  • $\begingroup$ Your setup reminds me a lot of some work done by Ueli Maurer. It has been a number of years since I have looked through his work though. $\endgroup$ – mikeazo Jan 3 '17 at 15:48

I think that the use cases for this requirement still need some clarification as they seem to be illogical and self contradictory. So I'll answer the question posed in your last paragraph. No. There is no entropy source that can satisfy the buffering requirement.

Firstly, it would be impossible to develop and randomness test an entropy source without recording it's output. If you record the output, the attacker can record the output. They will certainly be able to record a few of your minutes of attack time. There is no way to prove randomness without storing the entropy stream and making multiple passes over it. In other words, there are no pure streaming tests. They all require some block of stored data for multiple passes, even something simple like FIPS 140-2 uses blocks of 20,000 bits. No single pass over data can prove randomness, it takes a combination and then careful assessment of combined probabilities. If you tested it, you made multiple passes, ero you recorded it.

Secondly. It is impossible to record the same data stream from any practical entropy source (other than dice). This feature works to the advantage of TRNG builders, but fatally against you. In engineering terms, entropy sources don't produce any entropy at all. The measuring system does, and totally determines it's quality and quantity. Switch on the old analogue TV you kept. You'll see static. 1% of that static is your true atmospheric noise in the form of the cosmic background radiation. 99% is other stuff populating the aether, some permanent, some transient. Some of it will be localised from your hairdryer. Ever heard a TV studio guest's mobile phone checking in with the local cell tower? If you record a -100dB signal, there will be a huge proportion of unpredictable external noise. There is a good example else where on this forum that mentions the ANU Quantum Random Numbers Server. The developers specifically mention the difficulty of separating the true entropy signal from incidental system noise.

Thirdly. Randomness extraction will blow it all out of the window. All extractors use some form of hashing. If you take the simple example of a 1024 * 768 bit matrix extractor, it requires 1024 bits of entropy to generate 768 truly random bits. If one bit is different between your two devices (0.1% which is a virtual measurement impossibility), the 768 bit random outputs will be totally different by virtual of the avalanche effect. Unless something funny is going on, no two TRNGs can ever produce anything like the same output. They're always absolutely different.


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.