7 ms·

Is it ASCII or Protobuf? The importance of types in cryptographic signatures

156 points by qiqing 11y ago

deleted 11y ago
[deleted]
- alcari 11y ago
  That method's mentioned in the article. See the section 'The Obvious Problem'.
- marcosdumay 11y ago
  Yes, there's complete symmetry between signing and encrypting, thus your proposal is exactly equal to the article's. The solution is quite simpler. Do not sign text that you didn't create. You create a random timestamped text, encrypt it, and send both to the server. Or use the Diffie-Hellman key exchange, that as a bonus isn't vulnerable to men-in-the-middle attacks (that both the article's algorithms and the one I just wrote are).
BoppreH 11y ago
That's a fairly big problem I hadn't read about before, with great writing. But I don't think the proposed solutions are realistic. [...] all those web sites must use exactly the same format for authentication challenges. [...] the key cannot be used for any automated purpose [...] [...] all applications which use the key for signing must include such a context string, and context strings must be chosen to avoid conflicts. [...] better than either of the above is to use a different key for each purpose. That's shifting protocol problems to standardization and human caution. It may work, but I'm skeptic. Maybe a change in the cryptographic protocol can fix the problem? For example, instead of Server: server_value // domain + action + nonce + ... Client: sign(server_value) we use Server: server_value Client: sign(client_random) + sign(server_value XOR client_random) and the server verifies that the two signed components, when XOR'd, result in the same value sent. This way the client only signs random data but can still authenticate. This is not supposed to be a final solution, and is likely to have flaws, but I think it's a better direction to pursue.
- sdevlin 11y ago
  The scheme you outline still allows trivial impersonation attacks.
  - BoppreH 11y ago
    Care to provide an example? And keep in mind this is not a complete authentication protocol. I'm just proposing a small change to fix the signing-not-random-nonce problem, so I assume the rest of the protocol context is kept. Barring stupid mistakes from my part, if this is vulnerable to impersonation so is the article's.
    - sdevlin 11y ago
      Alice is an end user. Eve and Bob each host legitimate servers. Alice authenticates to Eve, and Eve impersonates Alice to Bob like so: A E B -hello-> -hello-> <-nonce- <-nonce- -random-> -S(rand)> -S(n^r)-> -random-> -S(rand)> -S(n^r)->
      - BoppreH 11y ago
        If Alice doesn't validate the identity of the server, that's absolutely a legitimate attack. But building a secure channel is out of scope and assumed solved here. The problem is how can Alice authenticate to Bob without exposing herself to signing arbitrary documents. (nice diagram, by the way)
        sdevlin 11y ago
        To be clear, Alice is intentionally authenticating to Eve in this scenario. So a secure channel does not impede the attack. For example, suppose Eve is Facebook and Bob is Google. Alice logs into Facebook, but what she doesn't know is that Facebook is passing her signatures directly through to Google. Now Mark Zuckerberg can like YouTube videos on Alice's behalf. To prevent this, Alice must also sign the domain she's authenticating to. The article mentioned this, and maybe you had meant it to be implicit in your protocol, in which case: my bad.
dfox 11y ago
One problem with this article (that does not invalidate the main point that you should not reuse keys for different protocols) is using SSH authentication as an example. In SSH what gets signed in publickey (and hostkey) authentication is not controlled by server (client). Instead of some random value provided by other side, signed data include session id that is derived from result of first DH key exchange and thus unpredictable to either side of connection.
- sdevlin 11y ago
  > signed data include session id that is derived from result of first DH key exchange and thus unpredictable to either side of connection The unpredictability of DH output depends on the group parameters and public key validation performed by the peer. If the group contains small subgroups, Eve can send an element of small order and predict the DH output with high probability. For example, this is one of the attack vectors for the triple handshake attack on TLS: https://www.secure-resumption.com/tlsauth.pdf https://www.secure-resumption.com/tlsauth.pdf.
  - dfox 11y ago
    Which is mitigated in SSH by two things: 1) The DH group is negotiated by both peers from fixed list. 2) output of key exchange is hashed with various values that are not all controlled by same side of connection Also after reading the relevant part of RFC4253 I've found out that the session id is conceptually an output of key exchange, but in the DH case it's derived from contents of key exchange messages and not from the result itself (not that it makes much of an difference).
- kentonv 11y ago
  While having the message be servers specified makes an attack easier, it is not necessary. Ultimately all you need is two protocols that can be mistaken for each other. SSH's session ID appears as the first few bytes of the signed message, so all you need is to find a protocol which happens to ignore those bytes or otherwise happens to allow the attacker to specify them. This is not unusual -- SSH itself, IIRC, will ignore leading "comment" lines at the start of a connection (though this is not in a context that gets signed, but the point is ignoring a prefix is not uncommon).
zaroth 11y ago
Why does the server present any data to be signed at all? The client generates a string, I am Sam logging into Google and Time is Now, Signed Sam. The server has the public key and verifies.
- jerf 11y ago
  Now the server can send the signed value somewhere else, and they can be Sam, too. In fact, even if the server itself uses some sort of challenge-response, it can use the response anywhere that implements your policy.
  - zaroth 11y ago
    Any scheme that protects against MITM is used to establish the baseline encrypted channel. Then what follows is used to authenticate the client, right? The message you generate will only work for the server you generate it for, and likewise, you must ensure you are securely delivering the message to the correct server. It's often useful to treat these as two distinct problems solved at different layers in the stack (1) establish secure channel to shared public server, (2) authenticate.
    - pjc50 11y ago
      Channel security isn't the important thing: once you've securely delivered the authentication to the server, can that server use it to authenticate somewhere else?
- kentonv 11y ago
  A timestamp doesn't prevent replay attacks, it just time-limits them. Also, requiring time sync tends to be problematic -- many people have incorrect clocks. Finally, just because your protocol uses a timestamp at some position doesn't mean some other protocol won't interpret those bits in some other way. Removing server-controlled bits makes an attack harder but not necessarily impossible.
  - zaroth 11y ago
binarnosp 11y ago
This was the reason that made me reject both protobuf and thrift for my own project. I ended up developing my own protocol which has to guarantee a normalized stream: there is only one way of encoding a set of data, any other way causes a error in the parser. Here it is (still under development): https://bitbucket.org/binarno/goingthere https://bitbucket.org/binarno/goingthere Can be embedded into streams, but it has a "strict" flag that forces the parser to throw an error if unexpected data is found in the stream. Optional tags not specified in the schema simply cannot be there, and all the tags must be encoded following a specific order. Still looking for a simple protocol that allows to have a normalized representation that is always the same for the same set of data; I hate to develop my own things and prefer to steal ready made things :-)
- kentonv 11y ago
  While requiring canonicalization may make the attack harder, I don't think it eliminates the problem entirely. You can define a canonical form of protobufs by simply saying that fields must appear in numeric order and unknown fields are not allowed. But, there's no reason you couldn't have a canonical protobuf that also looks like an ASCII message, you'd just have to think harder when constructing it (something I didn't care to do for this blog post :) ).
- heavenlyhash 11y ago
  You may also want to consider cbor: http://tools.ietf.org/html/rfc7049 http://tools.ietf.org/html/rfc7049 It doesn't require canonicalization, but it has a suggested format for canonicalization, and libraries I've been using have made it reasonably possible to force field ordering. Though this may be something of a tangent, since as kentonv says, canonicalization is only part of the dance; it all depends on what other actors do as well. :)

156 points by qiqing 11y ago

deleted 11y ago

[deleted]

alcari 11y ago
That method's mentioned in the article. See the section 'The Obvious Problem'.
marcosdumay 11y ago
Yes, there's complete symmetry between signing and encrypting, thus your proposal is exactly equal to the article's. The solution is quite simpler. Do not sign text that you didn't create. You create a random timestamped text, encrypt it, and send both to the server. Or use the Diffie-Hellman key exchange, that as a bonus isn't vulnerable to men-in-the-middle attacks (that both the article's algorithms and the one I just wrote are).

BoppreH 11y ago

That's a fairly big problem I hadn't read about before, with great writing. But I don't think the proposed solutions are realistic. [...] all those web sites must use exactly the same format for authentication challenges. [...] the key cannot be used for any automated purpose [...] [...] all applications which use the key for signing must include such a context string, and context strings must be chosen to avoid conflicts. [...] better than either of the above is to use a different key for each purpose. That's shifting protocol problems to standardization and human caution. It may work, but I'm skeptic. Maybe a change in the cryptographic protocol can fix the problem? For example, instead of Server: server_value // domain + action + nonce + ... Client: sign(server_value) we use Server: server_value Client: sign(client_random) + sign(server_value XOR client_random) and the server verifies that the two signed components, when XOR'd, result in the same value sent. This way the client only signs random data but can still authenticate. This is not supposed to be a final solution, and is likely to have flaws, but I think it's a better direction to pursue.

sdevlin 11y ago
The scheme you outline still allows trivial impersonation attacks.
- BoppreH 11y ago
  Care to provide an example? And keep in mind this is not a complete authentication protocol. I'm just proposing a small change to fix the signing-not-random-nonce problem, so I assume the rest of the protocol context is kept. Barring stupid mistakes from my part, if this is vulnerable to impersonation so is the article's.
  - sdevlin 11y ago
    Alice is an end user. Eve and Bob each host legitimate servers. Alice authenticates to Eve, and Eve impersonates Alice to Bob like so: A E B -hello-> -hello-> <-nonce- <-nonce- -random-> -S(rand)> -S(n^r)-> -random-> -S(rand)> -S(n^r)->
    - BoppreH 11y ago
      If Alice doesn't validate the identity of the server, that's absolutely a legitimate attack. But building a secure channel is out of scope and assumed solved here. The problem is how can Alice authenticate to Bob without exposing herself to signing arbitrary documents. (nice diagram, by the way)
      - sdevlin 11y ago
        To be clear, Alice is intentionally authenticating to Eve in this scenario. So a secure channel does not impede the attack. For example, suppose Eve is Facebook and Bob is Google. Alice logs into Facebook, but what she doesn't know is that Facebook is passing her signatures directly through to Google. Now Mark Zuckerberg can like YouTube videos on Alice's behalf. To prevent this, Alice must also sign the domain she's authenticating to. The article mentioned this, and maybe you had meant it to be implicit in your protocol, in which case: my bad.

dfox 11y ago

One problem with this article (that does not invalidate the main point that you should not reuse keys for different protocols) is using SSH authentication as an example. In SSH what gets signed in publickey (and hostkey) authentication is not controlled by server (client). Instead of some random value provided by other side, signed data include session id that is derived from result of first DH key exchange and thus unpredictable to either side of connection.

sdevlin 11y ago
> signed data include session id that is derived from result of first DH key exchange and thus unpredictable to either side of connection The unpredictability of DH output depends on the group parameters and public key validation performed by the peer. If the group contains small subgroups, Eve can send an element of small order and predict the DH output with high probability. For example, this is one of the attack vectors for the triple handshake attack on TLS: https://www.secure-resumption.com/tlsauth.pdf https://www.secure-resumption.com/tlsauth.pdf.
- dfox 11y ago
  Which is mitigated in SSH by two things: 1) The DH group is negotiated by both peers from fixed list. 2) output of key exchange is hashed with various values that are not all controlled by same side of connection Also after reading the relevant part of RFC4253 I've found out that the session id is conceptually an output of key exchange, but in the DH case it's derived from contents of key exchange messages and not from the result itself (not that it makes much of an difference).
kentonv 11y ago
While having the message be servers specified makes an attack easier, it is not necessary. Ultimately all you need is two protocols that can be mistaken for each other. SSH's session ID appears as the first few bytes of the signed message, so all you need is to find a protocol which happens to ignore those bytes or otherwise happens to allow the attacker to specify them. This is not unusual -- SSH itself, IIRC, will ignore leading "comment" lines at the start of a connection (though this is not in a context that gets signed, but the point is ignoring a prefix is not uncommon).

zaroth 11y ago

Why does the server present any data to be signed at all? The client generates a string, I am Sam logging into Google and Time is Now, Signed Sam. The server has the public key and verifies.

jerf 11y ago
Now the server can send the signed value somewhere else, and they can be Sam, too. In fact, even if the server itself uses some sort of challenge-response, it can use the response anywhere that implements your policy.
- zaroth 11y ago
  Any scheme that protects against MITM is used to establish the baseline encrypted channel. Then what follows is used to authenticate the client, right? The message you generate will only work for the server you generate it for, and likewise, you must ensure you are securely delivering the message to the correct server. It's often useful to treat these as two distinct problems solved at different layers in the stack (1) establish secure channel to shared public server, (2) authenticate.
  - pjc50 11y ago
    Channel security isn't the important thing: once you've securely delivered the authentication to the server, can that server use it to authenticate somewhere else?
kentonv 11y ago
A timestamp doesn't prevent replay attacks, it just time-limits them. Also, requiring time sync tends to be problematic -- many people have incorrect clocks. Finally, just because your protocol uses a timestamp at some position doesn't mean some other protocol won't interpret those bits in some other way. Removing server-controlled bits makes an attack harder but not necessarily impossible.
- zaroth 11y ago

binarnosp 11y ago

This was the reason that made me reject both protobuf and thrift for my own project. I ended up developing my own protocol which has to guarantee a normalized stream: there is only one way of encoding a set of data, any other way causes a error in the parser. Here it is (still under development): https://bitbucket.org/binarno/goingthere https://bitbucket.org/binarno/goingthere Can be embedded into streams, but it has a "strict" flag that forces the parser to throw an error if unexpected data is found in the stream. Optional tags not specified in the schema simply cannot be there, and all the tags must be encoded following a specific order. Still looking for a simple protocol that allows to have a normalized representation that is always the same for the same set of data; I hate to develop my own things and prefer to steal ready made things :-)

kentonv 11y ago
While requiring canonicalization may make the attack harder, I don't think it eliminates the problem entirely. You can define a canonical form of protobufs by simply saying that fields must appear in numeric order and unknown fields are not allowed. But, there's no reason you couldn't have a canonical protobuf that also looks like an ASCII message, you'd just have to think harder when constructing it (something I didn't care to do for this blog post :) ).
heavenlyhash 11y ago
You may also want to consider cbor: http://tools.ietf.org/html/rfc7049 http://tools.ietf.org/html/rfc7049 It doesn't require canonicalization, but it has a suggested format for canonicalization, and libraries I've been using have made it reasonably possible to force field ordering. Though this may be something of a tangent, since as kentonv says, canonicalization is only part of the dance; it all depends on what other actors do as well. :)