A simple, (as-of-yet unidentified) asymmetric Authenticated Key Exchange | Hacker News Reader

A simple, (as-of-yet unidentified) asymmetric Authenticated Key Exchange

dannyvanheumen.nl

49 pointsFethbita48 comments

> The use-case is a user and a “service-provider” (of some kind, in my case a device). The device only responds to requests, performs computations in a separate computing environment and is, in this particular case, connected by USB port. There is sensitive information involved. The device, however, does not have storage capability...

I think you're over-describing your use case, to the point that it's unclear what you're really saying. I read your "Introduction" section several times, and I don't understand if you're just saying "the use case is an authenticated key exchange" or something different. That makes it hard to judge the protocol.

> Device gets authenticated

> The device, however, does not have storage capability

These two requirements are contradictory. How do you "authenticate" a server that has a different identity each time you interact with it?

> [The protocol] is built on top of a Diffie-Hellman Key Exchange

Why not just use Diffie-Hellman? What else is this offering?

> I think you're over-describing your use case, to the point that it's unclear what you're really saying. I read your "Introduction" section several times, and I don't understand if you're just saying "the use case is an authenticated key exchange" or something different. That makes it hard to judge the protocol.

Okay. I indeed failed to abstract away from the device properly. I'm guessing that the confusion comes from the fact that I had a specific device in mind, but failed to describe it.

> These two requirements are contradictory. How do you "authenticate" a server that has a different identity each time you interact with it?

Not necessarily. So how TKey works: the hardware contains a preprogrammed device secret. The hardware does not have storage. Upon each power-up it expects a program to be loaded. Upon loading that program, a secret is computed for that specific program: `blake2s(device-secret, program-binary, user-secret)` (user-secret is optional). The secret is generated deterministically, but unpredictable because we don't know the device-secret.

> Why not just use Diffie-Hellman? What else is this offering?

Given that there exists an "identity", which is the same every time the program loads, this identity can be used for authentication. The identity is different for every program, but after acquiring it once, a client application can perform a key-exchange that finishes with the signature proving the authenticity.

If 'device' or 'program-binary' or 'user-secret' changes, the secret changes. So if the secret is the same, you have quite strong guarantees that nobody screwed around with your device or program.

> `blake2s(device-secret, program-binary, user-secret)`

Ok, I think this is still a fairly standard situation. I understand it that the above quoted text represents the device's long term private key? If so...

You can do this:

- device derives a long-term public device key from the long-term private key

- client generates a fresh public/private session keypair

- client and server perform a Diffie-Hellman exchange, resulting in shared_session_key

- client also verifies device's long-term public key is correct (a simple equality check)

At this point the client and server now have a shared_session_key, and you're in standard territory.

Next problems are replay attack prevention and forward secrecy. The two-birds-with-one-stone for that is for each side to:

- generate fresh a ephemeral keypair

- encrypt using the shared_session_key (with a random nonce)

- perform another Diffie-Hellman exchange

This results in a shared_ephemeral_key. This key can now be used to communicate securely, but you'll need to use incrementing integers as nonces for each message in the ephemeral session to prevent replay attacks. None of this needs storage.

I'm not sure if we're talking about the same things. I am not confident that I understand your comment well enough to confirm/reject, so I'm going to clarify for that reason.

> I understand it that the above quoted text represents the device's long term private key?

The device owns an internal, inaccessible long-term 32-byte key called UDS. (I called it "device secret" in other comments.) The device contains fairly minimal firmware, primarily there to initialize the device and accept the bytes that are the program-binary.

When a program-binary is sent, it is written to memory. Then a secret is derived for the program, called CDI. Then device-firmware passes over control to the firmware-binary by jumping to the entry-point (IIRC).

`CDI = blake2s(UDS, blake2s(program-binary), 32-byte-user-secret)`. (Note: this is done in device-firmware and only the CDI is exposed to the program.

> You can do this:

I think here we're on the right track, but I'm guessing you're suggesting an rough idea. So, yeah, from the CDI one can derive a key for identity.

So the current protocol describes using that deterministically generated identity for authentication, and generate random bytes for deriving an ephemeral keypair for the key-exchange.

The client only needs an ephemeral keypair so relies on proper randomness only. (And it keeps a record of the identity public key, to verify its proof.)

> Next problems are replay attack prevention and forward secrecy. The two-birds-with-one-stone for that is for each side to:

I think these are not possible. Assuming (for this discussion) that your client is honest, you start off every session with proper randomness in your (unpredictable) ephemeral key. So from the first message on, replays are not feasible. Forward secrecy should be covered given that the whole session key, as it is established, is based off fresh input from randomness.

This, of course, leaves open the discussion on long-running sessions that keep using the same key without rotation. This is not addressed.

This is Noise NK, possibly with differences in the hashing details which I did not check:

https://noiseprotocol.org/noise.html#interactive-handshake-p...

I encourage you to use their hashing details. They're battle-tested.

Wireguard uses Noise IK, which is NK plus a static public key for the initiator which is encrypted to the agreed-upon-session-key without adding additional round trips. Your protocol and Noise NK omit the parts related to the initiator's static public key, because it has none.

I will have a look. I checked quickly already, so if I understand the notation, I also leave out the last transaction. (2 messages vs 3 messages) Presumably because the authentication is one-sided. Will investigate further.

You have misunderstood the notation; Noise NK is 2 messages, one round trip.

Exchanges above the dotted line are one-time key distributions; see this link: https://archive.li/bU5Me#selection-3667.0-3671.36

Yeah, sorry, I realized that later. I forgot I posted the comment already.

I think this protocol is correct-ish* when you make the strong assumptions you have made about the device, but I also don't know why you would use it. Normally, you would prefer to both have unique device public keys for domain separation (preventing re-use of IVs, etc.) combined with the ability to verify that the device public key is actually the public key of a legitimate device. Otherwise, you could have a non-legit device conduct a MITM attack by running this protocol (if you trust the device to provide its identity PK) with the user and the device separately or you could have a counterfeit device created when sk_identity is eventually exfiltrated (if you set the identity PK as the same number for all devices at the factory - see what happens with DRM). Using some sort of device ID with a database mapping IDs to PKs also doesn't give you counterfeit protection the way a certificate does - a counterfeiter can re-use an ID. You also can't rotate your identity keys if you use this scheme.

Most cryptosystems today offer flexible-enough primitives that you can come up with a lot of different possible ways to do things like this. Whether they are useful is a different story.

IMO you should probably do something more normal, and just store the certificate chain with the device programming.

*After about 10 minutes of analysis, so YMMV taking my word for it.

Yeah, from the requirements it’s not clear why you wouldn’t just use TLS.

This. Even if TLS is the wrong answer, it will always be better than anything you roll yourself.

Shout out to https://www.trustedfirmware.org/projects/mbed-tls/

Thanks for the feedback. See also comment https://news.ycombinator.com/item?id=39834820 Note that this device is general purpose security device with no persistence. So the requirements were really specific for that reason.

You're right. I wanted to abstract away from specific hardware and express that in the requirements. I definitely failed at that. See other comments for specifics and details on the device.

The device I have in mind, primarily, is tillitis' TKey. The TKey does not have persistence, and offers a 32-byte secret value that is deterministically unpredictable (Blake2s) depending on hardware + program-binary + user-supplied-secret. Because of this, you will need TOFU, because you can only know its identity at first run, or its unique secret for that matter. (Of course, if you rely on the device+program, you would need to store the identity public key for subsequent connects.)

Do you still see an opening for a MitM if you assume TOFU works? There is authentication, just not on first connect. I'd be interested in your view on what I missed.

The exfiltration is of course a concern. Part of the prototype I'm doing, is looking into how much we can protect against this. (See also feedback I left to tillitis regarding access to the assigned secret, <https://github.com/tillitis/tillitis-key1/issues/186>.)

Concerning rotations, absolutely correct. Consider though that any change of program-binary or user-supplied secret or device brings its own secret. Note that because of the lack of persistence on the device, a client would store a data, even if only for use within the device.

Note that the secret is determined at every execution as the program-binary loads. The device, TKey, itself is a general RiscV processing unit with device-firmware that initializes a little bit of device and memory, takes the program sent to the device, then starts executing at the program-binary's entry-point.

Why not buy a TKey Unlocked instead? https://tillitis.se/products/tkey-unlocked/

Then you not only have access to the device secret, you can even choose it yourself.

That's fine. It is indeed possible to perform a check for genuine hardware. (I'm not sure it qualifies as "attestation".) It does not protect you from malicious program-binaries and swapped devices.

Protecting against "swapped devices" is simple: put a secret key in the device, ask it to produce a signature, check it with the public key. Any device other than yours won't know the secret key.

I'm not sure what attacks you refer to when you say "malicious program-binaries". I'm having trouble imagining something fitting this description which is thwarted by the vendor blowing the programming fuse but isn't thwarted by you blowing the fuse yourself.

The comment is meant to separate the hardware from the protections possible in software. TKey provides a unique secret per device, that transforms into a unique secret per (device + program-binary + user-secret). So, protection against swapped device is possible, just not if you simply check if the device is genuine.

Programs are loaded every time the device is connected by transmitting it to the device. So, you could swap the program binary on the computer, and have it send a malicious binary. Again, a unique secret is assigned to a byte-exact program-binary, so this is detected in the process.

(edit: I'm assuming the device contains the original firmware. I'm referring to programs loaded onto the TKey once programmed. Just to check/avoid confusion.)

I don't know much about the TKey, but it looks like they have some kind of remote attestation protocol available? (https://github.com/tillitis/tkey-verification/tree/main/cmd/...). That's usually how you avoid TOFU.

(1) the tillitis CA certifies your TKey device platform. You can now trust that it's running a specific firmware version with some platform pubkey.

(2) Your custom software is running and derives a keypair from it's derived secret + program binary hash.

(3) Somehow your custom software's pubkey gets locally certified by the platform's pubkey from (1). (not sure what this looks like w/ the TKey)

You now have a chain of trust from (1) the tillitis CA -> (3) the TKey device platform pubkey @ some specific firmware version -> (2) your custom software pubkey @ some specific version.

Now that we have a trusted pubkey for our service, I would open a secure channel to it via Noise IK or something (https://noiseexplorer.com/patterns/IK/). The TKey platform definitely looks a bit anemic so getting this working might be a challenge...

> I don't know much about the TKey, but it looks like they have some kind of remote attestation protocol available? (https://github.com/tillitis/tkey-verification/tree/main/cmd/...). That's usually how you avoid TOFU.

There is a tool to verify if the device is genuine by mechanism of a signature. You're outlining most of the process. The question is whether avoiding TOFU is the goal, right? I'm thinking, with the physical device in your hands and during first use, it's quite reasonable to establish the identity for your 'program' + 'user-secret'.

> You now have a chain of trust from (1) the tillitis CA -> (3) the TKey device platform pubkey @ some specific firmware version -> (2) your custom software pubkey @ some specific version.

This does mean you make this a global + centralized effort, right? (Also, it creates a dependency.)

> (3) Somehow your custom software's pubkey gets locally certified by the platform's pubkey from (1). (not sure what this looks like w/ the TKey)

With the specific firmware version: this requires a (possibly centralized) certification-process if only for a keypair, or qualification effort (if any) for the program?

To conclude: I am not convinced yet that TOFU is necessarily a bad thing. However, I do appreciate some ability to authenticate over many uses / longer stretches of time. (Hence the key-exchange + authn.) It seems there is a trade-off here, TOFU can be eradicated but requires other properties/effort. OTOH, the program-specific secret makes for a very strict form of trust. I'll take your comments into consideration, but it seems whichever way one chooses, there is a trade-off to be made.

I think this depends on a lot of assumptions about the capabilities of what is otherwise described as an absolutely dumb featureless device.

If the device lacks access to storage it cannot store any state. How do you ensure the RNG isn't initialized to the same value every time? I'm not sure how that impacts some of the assumptions about security here.

> the RNG isn't initialized

Or used.

sk_identity is static over the lifetime of the device, so doesn't need new entropy.

sk_device is generated after pk_user is recieved, so can use HASH(sk_identity,pk_user) as entropy. This results in the same pk_device for every session with a given pk_user, which theoretically enables traffic analysis, but the security model implies traffic analysis is out-of-scope.

signature and enc_sig might need entropy as well, but can still use HASH(sk_identity,pk_user).

You could... but I guess my bigger point is that wasn't even addressed.

This is my first time seeing Verifpal, but it looks like a huge foot gun in the wrong hands. Here the author was lead to believe there was some sort of formal validation of his roll-your-own crypto, while glossing over obvious potential implementation flaws.

This is how roll-your-own cryptography often works out. You set the parameters of the attacks you want to defend against, defend against them perfectly, and ignore the practical realities of what attacks are actually coming.

If you are great at it, you will come up with something very efficient that defends only against the attack surface you need. If you are not great at it, you will have an insecure system.

https://www.schneier.com/blog/archives/2011/04/schneiers_law...

I understand the "roll-your-own-crypto" comment. Note that I am taking the perspective of the protocol here, right? So, sure, vulnerabilities in the program are definitely a possibility. (See also other comments explaining more details about the device.) This is part of an experiment to see what can be accomplished with the TKey, which offers an interesting combo of security features.

Feel free to pour me an avalanche of missed attacks. I would be interested to know if your attacks are on the protocol level or in other ways. C programming risks are obviously there. RNG risks are obviously there. You are right that there are plenty of considerations in the program too. They are just not part of this post. (I also commented on the RNG remarks in other replies.)

I think if you read the comments aimed at this protocol, we're all saying that if this is a fun/school project, it sounds good, but if this is a commercial product, use something that has been proven to work.

No protocol exists completely separate from its implementation.

> No protocol exists completely separate from its implementation.

That's a fair point. I am well aware of this.

> Feel free to pour me an avalanche of missed attacks.

Sure. Based on your other comments you are using a USB device that explicitly provides no security guarantees when someone has physical access to it, so any attempt to secure the communications between the host and device are moot.

I'd love to respond to this, but your comment "... that explicitly provides no security guarantees when someone has physical access to it, .." is too abstract for me. I'll make a few guesses.

- Is the device hackable? AFAIK not at this moment. The firmware is minimal. It is a relatively new device, so maybe I am not fully informed.

- Is the device stealable/swappable? Yes. However, it isn't possible/easy to access the internal device-secret (UDS) therefore, swapping it out leads to different secret for the program, cascading into the identity, therefore authentication would fail. (Also, if you steal it, then it's gone. :-P)

- There are protections against opening it up. I'm not an expert on this, so I cannot reliably reproduce from memory the ways it is resistant to this. However, it already means your destroying hardware in the process.

> Is the device hackable? AFAIK not at this moment. The firmware is minimal. It is a relatively new device

It is just a package around an inexpensive FPGA chip. Published and un-published attacks against it exist. For these reasons the TKey developers call out "[a]ll physical and electrical attacks applied to the board [are out of scope]" in the threat model.

https://hackaday.com/2018/09/27/three-part-deep-dive-explain...

https://github.com/sylefeb/Silice/blob/draft/projects/ice40-...

> There are protections against opening it up.

I'd love to see photos if yours is any different than what is on the website.

You're right. I misremembered; read up on a lot of things in last months. Doesn't really matter, because we're discussing a protocol anyways.

I get that Verifpal is not perfect, doesn't do everything. I have considered switching. However, a significant part of proving the mechanism is having correct definitions for all of the needed primitives. If Verifpal tackles the right, correct definitions of the primitives, that is already a significant step, right? Considering the protocol is not complicated, or trying to be, one might try a less complex solution to start with. I am not planning to "gloss over" and there is a bigger pictures. But, feel free to make any missed dimensions concrete. (Note, you might want to check some other comments, as I explain a bit more about the device.)

See also my other comments. The device is tillitis TKey. There is a True RNG (source of entropy) but not recommended, i.e. not cryptographically-secure. However, together with Blake2s (in firmware) or another hash-function, you can at least approximate a source of reasonably secure randomness. Needs to be part of the your user program (to be loaded onto TKey), so you can make this as complicated as you like. You can indeed use the input-data as entropy/seed-bytes and hash it with other data and entropy from TRNG.

I haven't tested yet how fast the TRNG refreshes. Right now, I take 4 bytes (1 collection) of TRNG entropy to be hashed with a static byte-buffer.

The RNG would be used for (sk_device,pk_device). So 'identity' keypair for authn, 'device' (ephemeral) keypair for key-exchange.

Thanks for the input. See <https://news.ycombinator.com/item?id=39834820> for more details. The device is the TKey, so essentially only 32-byte secret value that is determined at program-load-time. (See more details in other comment.) The RNG is not really there. There is a true RNG (i.e. source of entropy) but not cryptographically-secure. However, you can use this and other data with the Blake2s (from firmware) or your own hash-functcion, to attempt to approximate randomness. So you essentially need to initialize it yourself and can go wild if you want to.

On a cursory glance, this looks rather quite a bit like a Noise [1] pattern. One rather nice aspect of Noise is that there is a good reference chart for which security properties one should expect from different combinations - saving time on proofs.

[1] https://noiseprotocol.org

While we're talking Noise, I'll plug the excellent Noise Explorer [1], which visualizes handshakes, enumerates security properties, and offers Go + Rust (+ wasm) implementation downloads.

I used this (and the NNpsk0 handshake [2]) as the basis for an E2EE chat app.

[1] https://noiseexplorer.com/

[2] https://noiseexplorer.com/patterns/NNpsk0/

Yeah, thanks for reminding me. That is a nice suggestion.

https://news.ycombinator.com/item?id=39835927

Rolling your own crypto routines of any variety is in the same category as representing yourself in a murder trial.

Yet https://cryptopals.com exists...

Given that this is a person interested in cryptography trying something for an experiment, I don't think it deserves the "don't roll your own" hammer.

Thanks, much appreciated. I'm not claiming to know everything, far from it. However, given this simple but interesting device (see other comments for details) I prefer to keep things simple. This is my attempt at simple-but-correct. :-)

This seems to be the use case for a user communicating with a confidential computing/enclave abstraction.

Why wouldn't you have your enclave carry a certificate instead of doing this?

You may eventually need to rotate its identity key, and if you want to do that, you need a certificate system.

The device I primarily had in mind is tillitis' TKey. Essentially a general purpose (slow) processing unit. The secret is 32-bytes long and given no storage, that's essentially all you work with. However, the secret is dependent on device + program-binary + 32-byte-user-secret.

A certificate is also a secret + certified public key, right? So, if you cannot store the certification on the TKey (no persistence) than you're left with the same construction. Right now, I'm skipping the complexity of certs (PKCS11, IIRC) etc. The identity being persistent is in order to authenticate the device.

> However, the secret is dependent on device + program-binary + 32-byte-user-secret.

If this is for anyone but yourself, you're going to need a certificate chain. An FPGA like the TKey can also store a significant amount of data in a ROM and you should have no problem storing it.

To check: did you realize that you plug this device in your USB port, then send a program to it, then start using the device with that program loaded? (This is at run-time, every time, right?) Because the secret is generated for this specific combination, different programs will also have different secrets.

I get that you would want to authn the hardware itself. If that is your point, sure, you're right. However, that aims to address a slightly different problem, because then the certificate chain is tied to the hardware only. Note that part of the charm of the _identity_ generated in the program, is that the identity changes if only a single byte of program-binary is different. So it protects from malicious binaries too. (But not bugs in the program itself.)

You're right, mostly. I am not sure if TKey is officially considered an enclave. See more details here: <https://news.ycombinator.com/item?id=39834820>

Reply on news.ycombinator.com