7 ms·

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

49 points by Fethbita 3y ago

jonahbenton 3y ago
This seems to be the use case for a user communicating with a confidential computing/enclave abstraction.
- pclmulqdq 3y ago
  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.
  - cobratbq 3y ago
    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.
    - pclmulqdq 3y ago
      > 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.
      - cobratbq 3y ago
        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.)
- cobratbq 3y ago
  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 https://news.ycombinator.com/item?id=39834820>
mike_d 3y ago
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.
- a1369209993 3y ago
  > 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).
  - mike_d 3y ago
    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.
    - pclmulqdq 3y ago
      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.
      - mike_d 3y ago
        https://www.schneier.com/blog/archives/2011/04/schneiers_law.html https://www.schneier.com/blog/archives/2011/04/schneiers_law...
pclmulqdq 3y ago
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.
- layer8 3y ago
  Yeah, from the requirements it’s not clear why you wouldn’t just use TLS.
  - mike_d 3y ago
    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/ https://www.trustedfirmware.org/projects/mbed-tls/
    - cobratbq 3y ago
      Thanks for the feedback. See also comment https://news.ycombinator.com/item?id=39834820 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.
thadt 3y ago
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 https://noiseprotocol.org
- abound 3y ago
  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/ https://noiseexplorer.com/ [2] https://noiseexplorer.com/patterns/NNpsk0/ https://noiseexplorer.com/patterns/NNpsk0/
- cobratbq 3y ago
  Yeah, thanks for reminding me. That is a nice suggestion.
- crotchfire 3y ago
  https://news.ycombinator.com/item?id=39835927 https://news.ycombinator.com/item?id=39835927
dzdt 3y ago
Rolling your own crypto routines of any variety is in the same category as representing yourself in a murder trial.
- LVB 3y ago
  Yet https://cryptopals.com 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.
  - cobratbq 3y ago
    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. :-)
crotchfire 3y ago
This is Noise NK, possibly with differences in the hashing details which I did not check: https://noiseprotocol.org/noise.html#interactive-handshake-patterns-fundamental 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.
- cobratbq 3y ago
  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.
  - crotchfire 3y ago
    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 https://archive.li/bU5Me#selection-3667.0-3671.36
    - cobratbq 3y ago
      Yeah, sorry, I realized that later. I forgot I posted the comment already.
notfed 3y ago
> 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?
- cobratbq 3y ago
  > 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.

49 points by Fethbita 3y ago

jonahbenton 3y ago

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

pclmulqdq 3y ago
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.
- cobratbq 3y ago
  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.
  - pclmulqdq 3y ago
    > 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.
    - cobratbq 3y ago
      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.)
cobratbq 3y ago
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 https://news.ycombinator.com/item?id=39834820>

mike_d 3y ago

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.

a1369209993 3y ago
> 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).
- mike_d 3y ago
  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.
  - pclmulqdq 3y ago
    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.
    - mike_d 3y ago
      https://www.schneier.com/blog/archives/2011/04/schneiers_law.html https://www.schneier.com/blog/archives/2011/04/schneiers_law...

pclmulqdq 3y ago

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.

layer8 3y ago
Yeah, from the requirements it’s not clear why you wouldn’t just use TLS.
- mike_d 3y ago
  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/ https://www.trustedfirmware.org/projects/mbed-tls/
  - cobratbq 3y ago
    Thanks for the feedback. See also comment https://news.ycombinator.com/item?id=39834820 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.

thadt 3y ago

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 https://noiseprotocol.org

abound 3y ago
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/ https://noiseexplorer.com/ [2] https://noiseexplorer.com/patterns/NNpsk0/ https://noiseexplorer.com/patterns/NNpsk0/
cobratbq 3y ago
Yeah, thanks for reminding me. That is a nice suggestion.
crotchfire 3y ago
https://news.ycombinator.com/item?id=39835927 https://news.ycombinator.com/item?id=39835927

dzdt 3y ago

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

LVB 3y ago
Yet https://cryptopals.com 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.
- cobratbq 3y ago
  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. :-)

crotchfire 3y ago

This is Noise NK, possibly with differences in the hashing details which I did not check: https://noiseprotocol.org/noise.html#interactive-handshake-patterns-fundamental 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.

cobratbq 3y ago
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.
- crotchfire 3y ago
  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 https://archive.li/bU5Me#selection-3667.0-3671.36
  - cobratbq 3y ago
    Yeah, sorry, I realized that later. I forgot I posted the comment already.

notfed 3y ago

> 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?

cobratbq 3y ago
> 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.