2
$\begingroup$

I have a small ARM M0 SoC and a smartphone as actors. Encryption keys used are Elliptic curve.

My current security is implemented such that:

  1. the SoC has 128 bit hashes of phone public keys (vs 512 bit - due to storage space constraints)
  2. the phone has the SoC's public key
  3. the phone sends its own public key during negotiation
  4. step 3 establishes grounds for ECDH on both sides. From here encrypted comms can follow

We are hoping that SoC having 128 bit hash should be secure enough for trying to brute-force guess the public/private key pair. We are assuming that phone is easily compromised where the attacker will gain the phone's complete key and the SoC's public key.

So now I have come up with a solution that I'm hoping might be better, but am not sure whether it actually is:

What changes:

  1. The public key hashes are now such that public key can be restored from partial data
  2. The phone only sends part of its public key
  3. There is an "overlapping" region between the hash on the SoC and the sent public key portion
  4. Neither device contains another device's full public key
  5. Both devices have to assemble the complete public key as part of negotiation procedure

So, basically, in its simplest form, the SoC now has the leftmost 128 bits of the 512-bit phone's public key. The phone sends the rightmost 416, leaving 32 bits for overlapping region, like this:

HHHHHHHHHHHHBBBBTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

  • H = SoC, B = Both, T = Telephone, each character = 8 bits of the public key
  • uniqueness of the overlapping part is ensured within the system.

Is this system in any way more secure than the previous system we designed? Less secure?

$\endgroup$
1
  • $\begingroup$ Could you elaborate a bit on what you are trying to achieve? $\endgroup$
    – Elias
    Feb 14, 2023 at 13:32

2 Answers 2

1
$\begingroup$

I'm not clear on your exact security model, but I think that both in both schemes it is feasible for an adversary to repudiate their involvement with a transaction.

I assume that you are using a standard elliptic curve over a 256-bit prime field such as secp256k1 so that points are pairs of 256-bit values which are then stored as 512-bit sequences the first half of which is an $x$-coordinate and the second half of which is a $y$-coordinate. In the first scheme a 128-bit hash of these 512-bits is stored by the server (e.g. using a Davies-Mayer construction using a 128-bit block size). By generating roughly $2^{64}$ candidate public keys and adversary can produce a pair which have the same hash value using a birthday attack. This is a painful amount of computation, but not beyond the realms of current capability. The adversary can then register one of these public keys and then establish a connection with the other. If confronted with a transcript of the communications using the non-registered key, they can repudiate by saying that it does not match their registered key.

A similar attack applies in the second case, but we should also note that if the rightmost 256-bits correspond to an elliptic curve point's $y$-value, then these alone is almost enough information to recover the rest of the public key. This is because the $x$-coordinate satisfies the elliptic curve equation which may be something like $$x^3-ax+b=y^\pmod p$$ where $a$, $b$, $y$, and $p$ are all known. We anticipate only handful of possible solution. A similar idea allows the recovery of the $y$-coordinate from just the 256-bits of $x$-coordinate and a compression bit.

$\endgroup$
3
  • $\begingroup$ Wow, thank you for this information (and your completely accurate assessment of what I'm trying to do). Can I counter on the repudiation attack thing by saying that the SoC will not further communicate with the entity that does not match its partial keys or if ECDH returns an invalid shared secret. IIUC in this case repudiation would only be possible if the SoC would somehow accept the phone's generated key just on the basis of phone saying so. But in our implementation, it is only accepted if both the hash and the ECDH shared secret match. $\endgroup$
    – velis
    Feb 14, 2023 at 11:20
  • $\begingroup$ As for calculating the hash from only X, this will be immediately fixed. Thanks. I'm just not sure if I got my answer about general security of the approach. I understand repudiation might be an issue, but I'm not sure if the original approach with one key shared and one held is better or worse than storing and exchanging partial keys both ways. $\endgroup$
    – velis
    Feb 14, 2023 at 11:21
  • $\begingroup$ Er, to expand on the repudiation thingy, we are also using session id, session counter and in-session challenge-response to prevent playbacks of any sort. But if the phone is compromised, another phone can, naturally take its place, since it has all the (partial) keys. But, I hope, it would only be that one phone that would be compromised. $\endgroup$
    – velis
    Feb 14, 2023 at 11:40
1
$\begingroup$

You're talking about public keys, so I assume these are actually public.

I don't think this can be used for authentication. An attacker only has to find a key with 32 (BBBB) matching bits to participate in the protocol and if he finds one with 128 matching bits (HHHHHHHHHHHHBBBB) it's completely broken.

At first glance (and I am no expert on this) this looks infeasible but I would certainly recommend sticking with the first approach. That approach verifies the entire public key and is quite standard.

BTW We discourage posts about home-grown crypto here. It's not always easy to falsify and it's usually a bad idea anyway. ;)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.