Challenge Response at Application Layer of BLE using ECDSA There is a need for an Offline BLE device to Auth a Phone. I am planning to use challenge response somewhat outlined here.

There is a small change. Instead of shared secret. I am planning to use a Public Key and Private Key. 

Basically as soon as the phone connects to ble device. Device gives a random message (at max 20 bytes). Phone reads and generates signature using deterministic ECDSA signature and sends it back to device. 

Device validates the signature. Establishes the authenticity for that session.

Public Key is embedded in the device. Private key is made available to owner through user manual or qr code on the device.

Questions:


How good is deterministic ECDSA for a small random message of 20 bytes?
Any visible problems with the flow?
Regarding your Q1, well, ECDSA is fine as long as you have a good random generator on the signer side, while deterministic ECDSA tries to address the randomness issues and thus is good (as long as you do not include fault attacks in your model). I personally prefer Ed25519 amongst the deterministic signatures scheme, but that is a question of personal taste, I'd say.

Now, because your challenge is 20 bytes, if you have enough entropy to be sure to generate random challenges, or a way to ensure the increment of a counter value on each challenge in a non reversible way, then you won't be concerned with replay attacks (which would otherwise be a concern with really small challenges).

As for Q2, your biggest concern would be the lack of Threat model! Or if you have one, you should have provided us with it, because the scheme might seem good if you only consider active eavesdroppers, but is broken as soon as you consider fault attack in your threat model (ie. the attacker has the device and can make it perform faults during its computation).

Since the device which would be performing the signature is a phone, I'd say you won't be subject to private key recovery through faults. 

On the other side, the Offline BLE device is most likely subject to faults, which may allow to trick the signature validation. See for example the work of Riscure to bypass Secure Boot using Fault Injection, where they bypass such a single verification easily.

Now, another concern is that you have to use an OOB (out of bound) channel to transmit the private key to the phone, which means that you may as well have transmitted a secure LTE key using that same OOB method and you would have arguably (don't hit me) achieved the same goal: only the device knowing that key would be able to communicate with your device... 
(Okay, with your scheme, if the Offline Device is stolen, it does not allow private key recovery, but if someone has the ability to recover a key from a BLE device, I'd say they have the ability to perform faults on the signature verification process and trick the device into believing he's speaking with someone who's got the key... thus achieving the same result. Unless you were to authenticate every message sent to the device, in which case it might be a bit harder, but faults of LE devices are generally really easily to perform.)

I don't see any other concern with your design, except that low energy devices generally don't have the power to perform ECDSA signatures, from what I know... But maybe this is old news and not the case anymore.

By the way, you might want to check the http://www.gattack.io/ website, and more specifically to read their whitepaper (even if it seems a bit dated).
From what I've read, it looks like you really should use BLE 4.2, which features ECDH for the LTE key exchange. (Yet, I haven't found much information on that topic). If you are compelled to use a prior norm, or can't rely on ECDH, then it seems like only BLE link-layer in OOB mode is actually secure.