# Client authentication on limited hardware

I'm developing a authentication and authorization protocol for a Bluetooth device. The device should communicate with an Android app and needs to be able to authenticate the app during the connection phase. Some kind of secret or asymmetric pair is therefore needed to be shared by the app and the Bluetooth device. As apps can be reverse-engineered we need to be able to update this secret.

RSA was the first solution that came to mind. The device can store the public key of some root certificate and then verify the signature of the app certificate like during TLS. The device keeps a list of valid certificate fingerprints.

However, the Bluetooth device is too weak to implement RSA. I need something (much) cheaper. Is there any such protocol?

-
How weak is too weak? Elliptic curve cryptography uses much smaller numbers than RSA, for example, but it's still significantly slower than purely symmetric encryption. –  otus Jul 2 '14 at 8:33
RSA is very fast for the purpose of authenticating something (rather than: authenticate w.r.t. something). For 2048-bit public modulus, public exponent $e=3$, and a CPU with 32x32 bit multiplication, in the order of 17000 multiply-and-accumulate are enough, with textbook algorithms and straightforward loops. This can be about halved with Rabin, while still having standard-conformance, e.g to ISO/IEC 9796-2, and then there's DjB's work. –  fgrieu Jul 9 '14 at 12:33

I'd suggest that you clearly define which kind of Bluetooth device you are using, more specifically what its capabilities are with respect to processing power, etc. Another question, can you enter a number on a bluetooth device (e.g., for a PIN-based authentication, for example)? From what you're writing, I'd assume that RSA won't be a plausible solution, since the smallest key length the constrained bluetooth device will have to deal with is 1024 bit (2048 is actually recommended). ECC is likely to prove unsuitable as well, since despite the fact that the key length is much smaller, the device has to be able to deal with ECC algorithm which may be quite inefficient without the proper hardware support of even not supported by the device at all. In my experience, using ECC instead of RSA on Android platform does not necessarily entail a performance gain, see the discussion here. Another important conceptual question is: what are the security goals/requirements in your specific case and against which attacker the system has to be secure (the so-called attacker model)? Taking into account what you've written in your question, I would assume that authentication using one-time PIN may be a better option than using full-fledged certificate-based authentication based on RSA (or on ECC).

-