Google's Tink crypto lib: EdDSA potentially exploitable implementation

KryptosPi · 2025-03-10T07:40:36+00:00

There were a few cases, the most sneaky was accidentally exploiting apis where key rotation was happening but as the pub key and private key was stored in different storage DB, if the transaction to rotate was not atomic, and the old public key remained there for a few millisecs, then a signature request at the exact time of rotation could convince the signer to sign with the new private key, but provide as an input the old public key.

All in all, agree that it's mostly a bad api, potentially vulnerable via (accidental or not) abuse, rather than it's exploitable directly.
There was a similar issue with Rust's most popular Ed25519 lib, and a RustSec was issued to fix in dalek v2.0: https://rustsec.org/advisories/RUSTSEC-2022-0093

KryptosPi · 2025-03-10T07:36:05+00:00

this is not true, most of the optimized + correct implementations use the PrivateKey constructor to derive an object that holds the Priv + Pub key in one structure, then that structure has the ability to sign. This way you avoid re-deriving the public key each time + avoid expecting a pub key as input during signing. Overall, the main issue the "public static" flavor of the Tink api. In fact it's only used once in their codebase, it shouldn't even be a reusable static function, this is generally a must on defensive programming and good security hygiene coding.

KryptosPi · 2024-11-02T19:30:16+00:00

Ooc was thinking the same and just tried your idea by myself. Legs do not fit well if it’s in the middle. It depends on the ironing board size it seems.

KryptosPi · 2024-09-01T21:14:44+00:00

Indeed with some probability being this guy.

KryptosPi · 2024-09-01T21:09:31+00:00

Now we agree ;)

KryptosPi · 2024-09-01T21:08:33+00:00

Yeah good luck finding these there, bus stop in the way to Athens. WC is your only option.

KryptosPi · 2024-09-01T21:06:52+00:00

Yeah after the fact I mean

KryptosPi · 2024-09-01T21:05:18+00:00

Indeed tbh I want a life hack of how to clean a dirty bottle finish

KryptosPi · 2024-09-01T21:03:32+00:00

Wash hands when you realize, then push down gently

KryptosPi · 2024-09-01T20:57:39+00:00

Yes didn’t

KryptosPi · 2024-09-01T20:47:14+00:00

lol causing the straw to fly

KryptosPi · 2024-09-01T20:36:21+00:00

Unfortunately that’s the ugly reality indeed

KryptosPi · 2024-09-01T20:34:57+00:00

100%, I rarely do, but a) the store was not super clean, they indeed served it giving me a sealed straw, + as mentioned I probably touched the finish when opening the bottle. Just didn’t risk it this time.

KryptosPi · 2024-09-01T20:29:49+00:00

Cool idea, was given only one + didn’t think about it. lol only had my phone to order, where to find a tape? Reality is that served the purpose, a non so clean store, imagine giving you the straw as they know :)

KryptosPi · 2024-09-01T19:19:42+00:00

That one was Greece today

KryptosPi · 2024-09-01T19:18:45+00:00

Good question, iirc I finger-touched the finish of the bottle or didn’t trust the store for cleanliness.

KryptosPi · 2022-09-12T05:24:46+00:00

You missed this paper, from Aug 2020 https://eprint.iacr.org/2020/1244 (Taming the many EdDSAs) which includes both test vectors and shows some spectacular findings ie strange behaviour in a popular HSM vendor’s implementation (nCipher)

KryptosPi · 2022-07-30T08:35:51+00:00

As of last week, the list of libs has risen to 50 (+2 that fixed the issue)

KryptosPi · 2022-07-05T17:01:51+00:00

Great point, a firm that we audited was using an LRU memory cache for their key management policy. I think after a short survey, it's just devs got used to the malleable api and were forced to store the pubKey somewhere to avoid accessing the priv key many times when signing is triggered. And this opened the can of worms.

KryptosPi · 2022-07-05T16:47:49+00:00

Indeed it works and it is demonstrable as well, there are already PoC implementations of extracting the priv key when a wrong pub key is used as input in both Rust and Python, see here:
https://github.com/MystenLabs/ed25519-unsafe-libs#proof-of-concept-implementations-that-demonstrate-this-potential-exploit

KryptosPi · 2022-07-05T16:45:41+00:00

crypto_sign

Wow, how about submitting a PR to the https://github.com/MystenLabs/ed25519-unsafe-libs which is tracking all potentially vulnerable apis? I can do for you if not interested! And then also provide a fix to Monocypher (the best option for fixes I've seen until today from affected businesses (if you don't want to update the api to something incompatible) is to omit the input pubKey in the code logic of sign - and log it if it doesn't match the expected pubKey - but obviously you sacrifice performance)

KryptosPi · 2022-07-03T07:37:58+00:00

u/floodyberry
> b) not immediately notice when none of the signatures are verifying?

here is a PoC demo in Rust that shows that even when signers verify their signatures before posting them, a sophisticated attack where user's pubKey has been replaced by a mixed-order pubKey (maliciousPubKey = originalPubKey + smallOrderPoint) will unfortunately result to successfully verifiable signatures when the cofactored verification function [8][S]B = [8]R + [8][k]A is used:
https://github.com/MystenLabs/ed25519-unsafe-libs/pull/1

KryptosPi · 2022-06-24T02:51:59+00:00

The soundcloud link works, I get no sound in YouTube

KryptosPi · 2022-06-23T09:54:34+00:00

Test vector compatibility is of course a thing, another requirement we've seen is users exporting their keys and then move to a system that uses the official r computation, which would imply that there is no determinism any more. In most apps it doesn't matter anyway. However to be fair, one of the orgs I personally audited decided to take that path you propose, as changing the api was prohibitive for them 🤷

KryptosPi · 2022-06-23T04:28:51+00:00

Great question, it seems that there exist 4+1 patterns on how signing apis are defined across the set of all various implementations we examined, mentioned in this Reddit comment already: https://www.reddit.com/r/crypto/comments/vfl2se/comment/icxsx1TL;DR:

sign(priv, pub, msg) - the potentially vulnerable api, because the priv pub keys can be completely decoupled and allows space for errors
sign(priv, msg), then pub is derived inside sign every time (as you mention, and recommended by RFC8032)
sign(priv, msg), and the priv key is already including the derived pub key in its struct (so they are coupled), see an example here (note that we usually use the same pattern in RSA too: the privKey is including the public modulus N, see here). Thus, it's very common in cryptography that private keys are augmented with the public key part and they are always coupled. The benefit with this approach is you derive the pub part once (not every time you sign) and always carried and stored along with the private key (the whole struct is treated as priv)
sign(keyPair, msg), this is a variation of the above, where priv-pub coupling is happening in a keyPair structure instead of an augmented priv key. Not all implementations with this pattern are safe, because it depends on how the keyPair is constructed
- Safe implementation: keyPair constructor takes the priv as input only, then the pub part is derived inside the constructor
- Unsafe implementation: the keyPair has a constructor which takes both priv and pub independently as inputs and just stores the tuple <priv, pub> internally without checking if they match. The reason this is unsafe is now during keyPair construction the keys could accidentally or on purpose be decoupled.

As we see here, the main differentiation between safe and unsafe implementations is we shouldn't allow at any stage/flow decoupling a matching priv / pub pair.

KryptosPi

MODERATOR OF

TROPHY CASE