Generating a Nonce on the Spark Core

I am trying to use Spark to securely communicate with a client application. I was happy to see that TropicSSL libraries are already part of the firmware, which provides me with all the necessary AES and HMAC primitives.

I am not using Cloud for this project, so the security will need to be enforced entirely on the Spark Core.

It is particularly important for me to defend against all kinds of Replay Attacks, and this is where I am experiencing some challenges. After considering all attack scenarios I could think of, I have concluded that the only way to make this secure is to go with timed challenge/response, or one-time key approaches.

Challenge/Response would be similar to this: http://en.wikipedia.org/wiki/Challenge–response_authentication#Cryptographic_techniques

whereas one-time key could be something like Diffie-Hellman key exchange, or even generating an RSA key pair for every request, although that sounds grotesquely expensive.

In any case, both of these strategies require the Spark Core to either generate large random numbers, or implement a PRGA (Pseudo-random generation algorithm), which I would have to seed with pre-computed random seeds.

Before I pick either direction, I wanted to see if anyone here might have some experience in this area.

Is there a way to generate cryptographically secure randomness on the Spark? If not, is there a suggested method for implementing a PRGA? In case of using a PRGA, my plan would be to fill the external flash with about 32K or so of pre-computed random seeds. Spark would keep the index of last used seed in external flash as well, and increment it on every reboot.

I can think of one alternative approach w/o pseudo-randomness on the Spark. Using a simple linear nonce counter used as part of the challenge to the client would work since the nonce does not need to be random, but then I would have to update external Flash on every request in order to make sure that the nonce is unique and resistant to reboots (my attacker would have the ability to cut power to the Spark, so this is important). This approach sounds simpler to implement, but I don’t know whether its a good idea to write into flash so often and what the repercussions of doing so might be.

Any thoughts would be appreciated!

HI @vace117

Maybe @zachary can correct me if I am wrong, but the Spark protocol uses a 40-byte (320-bit) nonce that is sent from the cloud to the core in the early part of the connection protocol. Maybe your protocol could turn the protocol around in that way too. The Spark protocol uses RSA to exchange an AES session key for the actual data.

I don’t think you are going to want to generate RSA keys on the core–it could do it, but there are memory and time limits you will have to work around. I also wouldn’t write the flash that often–you could brick the device.

Good random numbers are just hard to generate. If you can make it work with a counter and a hash function, that will be much easier. Finding a source of randomness (without extra hardware) on something like Spark depends a lot on your threat model: can the attacker control things like the network it connects to and the DNS answers the core receives? Can they control the latency to other hosts on the internet? There are a lot of potential sources of randomness that can be ruled out by certain attacks.

Have you considered doing a real hardware RNG? If you don’t have hard speed requirements, it can be cheap.

Sounds like an interesting project!

Totally agreed with @bko. You basically can’t rely on the Spark Core to generate cryptographically strong random numbers. As he said, the Spark Protocol relies on the Cloud for crucial randomness.

Without knowing your specific application and threat model, my gut says this is actually quite a reasonable proposal:

Those seed data (assuming they’re different for each device), combined with the rand48 family of functions (newlib docs) could be effective enough for most applications.

If you’re worried especially about replay attacks, first make sure that even when the underlying data to be transmitted is exactly the same, the data on the wire looks completely different each time. Then you just have to ensure that the transformation from one run to the next isn’t predictable.

Cheers!

2 Likes

My only concern here would be that 2^18 bits of entropy is not that much. If the attacker can force you to cycle through the seeds by power cycling the core, he could get you always choose seed 0 and then start trying to crack based on that one nonce. I think an attack like that, while being somewhat brute-force, is very doable.

If you can combine the flash based entropy bits with another source, even one with very modest randomness, you would be way ahead.

  1. On another platform I’m using the background noise of the analog pins to seed the generator. I can imagine you could combine multiple sources containing randomness to create your seed. Perhaps even increase randomness by including external hardware that varies values by physical conditions.
  2. In my Spark project I’m using an SD card reader. I think it currently holds a 4GB SD card. More than enough space for number tables and more. If you’re worried about wearing the card or the externaI flash can also recommend @kennethlimcp SD/FRAM shield which includes two FRAM memory devices in addition to the SD-card reader. FRAM is much more durable than flash.
3 Likes

@bko, where did you get 2^18 bits of entropy from?

But yes, I was thinking about that problem too. If the attacker managed to record an encrypted handshake request, they could then alternate rebooting the Spark and sending that request, until they received a response they have already seen before. Then they would know the period of my seeds, and how to reliably get the same challenge nonce. Not good.

Would using analogRead() work as an additional source of some entropy? For example, if my pre-computed seeds are 48-bits, would it work if I XORed my seed with analogEntropy, where analogEntropy is constructed by taking 48 reads of LSB( analogRead(unconnected_pin) )?

Your 32k bytes of pre-loaded FLASH is 2^18 = 32k * 8 bits of entropy.

I think it depends on your application, but it is likely you could get some random bits out of it similar to what @maxint said.

I don’t like using disconnected inputs as a source of random data since as an attacker I could direct RF at the core to influence the values and it would be hard to shield the analog input while allowing WiFi to work. Have you looked at measuring diode or thermal (Johnson) noise?

Whatever you use, you will want some sort of bias reduction, like von Neumann compensation.

You could also use the “truerand” algorithm based on the two oscillators (RTC and main) on Spark having slightly different drift and temperature coefficients but that would take quite a bit of programming to pull off here.

I still think generating random bits is hard and doing it on the other side of the conversation might be easier ala the Spark protocol.

1 Like

That’s a good point.

How about using a button and measuring the duration of a button press? Then applying a hash functions like MD5 to the duration and mixing that with the seed? That would also have the advantage of taking the Spark offline after an unintended reboot, until user with physical access to the device presses a button. Considering that this project is a glorified, Internet-enabled garage opener, having to press a button after a power loss is not that bad. If it keeps happening every day, I’ll know someone’s out to get me :smiling_imp:.

If I generated the random challenge on the other side of the conversation, wouldn’t that expose me to Replay Attacks once again? For example, let’s say the random challenge is sent by the client as part of the encrypted handshake, followed by the encrypted OPEN_DOOR command. Now the attacker who recorded this whole conversation can play it back at any time and open the door, unless the Spark actually records all previously used challenges in Flash.

I thought that having the random challenge be issued by the Spark was crucial to the security, b/c then Spark can say “this random challenge is valid for the next 5 seconds”, thus making replay attacks useless. How can I achieve this if the randomness comes from the potential attacker?

@vace117 and @bko, you are both way above my pay grade but I recall porting a library for one member for the Atmel ATSHA204A CryptoAuthentication chip. It’s small, uses I2C and might have the capabilities you need. :smile:

2 Likes

What would you recommend? I am looking around at different options now, and so far I don’t see anything too simple. Looks like there is no such thing as a dedicated RNG IC, and the analog circuits I came across thus far look somewhat complex (I am still very new to electronics).

Ooh this looks interesting. I’ll have to read about it.

Thanks @peekay123!

1 Like

Ha! It’s actually even worse than that! Without additional entropy the attacker would not need to crack anything based on the known nonce. Consider this attack:

  1. Attacker resets the power to the Spark, hides in the bushes and lies in wait
  2. Attacker records the first legitimate conversation, which
    includes the handshake and command carried out with sessionKey
    computed based on the first iteration of the PRGA
  3. Attacker resets the power to the Spark
  4. Attacker replays the conversation with proper delays between
    request/response. This won’t do anything at first, b/c the
    sessionKey is computed as HMAC(secret_key, PRGA(0, SeedN)) will be
    different every time, since we are using different seed on every reboot.
  5. Attacker repeats Steps 3 & 4 as fast as he can, until Spark eventually executes the command in the recorded conversation. The reason that will happen is b/c the seeds will loop
    eventually. Once they loop, it is guaranteed that the sessionKey in
    the recorded conversation will happen again! If we have N
    pre-computed seeds, and attacker manages to replay the conversation at the first interation of PRGA, the security will be compromised after N reset/replays.

So additional entropy most certainly required!

1 Like

I saw this today over at Hackaday:

and thought it might have some ideas for you. As his schematic shows, you need a relatively high voltage for avalanche diode noise sources. I would have shielded the avalanche diode from the RF section–there is surely some coupling there. The RF with bias reduction mode looks very promising.

1 Like