yggdrasil-go
yggdrasil-go copied to clipboard
yggdrasil-network
feat: allow L|R secret key representation instead of seed for keygen speedup
currently, secret keys are formatted according to RFC 8032 and consist 32 bytes of seed | 32 bytes pubkey. SHA512 is used to expand secret key into L|R parts, of which L can be expanded into pubkey. this way of storage is hard to make efficient key generator for: irreversible non-linear SHA512 transform needs to be performed, and then public key needs to be derived from L part. originally, yggdrasil used hash of public key for addresses (L|R representation would still have been nicer, just not as much), and there was no proper public package for low level ed25519 primitives, and also i think back then it used curve25519 instead of ed25519 too, so back then I didn't care to make proper proposal for this. however, all of these seem to be solved: v0.4 now uses plain ed25519 public key for addresses, and filippo.io/edwards25519 exists (golang's stdlib crypto/ed25519 internally uses code from this). therefore, I propose implementing routines which are capable of utilizing L|R representation of secret key for whatever yggdrasil is doing, and allowing specifying secret key using that representation from config (seed-based keys could be supported too still, this would be backwards compatible change). doing so would allow mkp224o equivalent of keygen. im still not 100% sure about how to specify that in config. currently im thinking of just prefixing it with something like "lr:" so whole secret key would look like "lr:1234123412341234..." but im open for other suggestions or better prefixes. I'll be prototyping this meanwhile.
If the key is the routable identity of an yggrasil node, you want key generation to be quite slow & hard to compute to prevent Sybil attacks on the DHT.
faster keygen will actually more likely to prevent sybil attacks, because it will generate keys which will contain more bits.
rather. addresses, which will contain more key bits. because of yggdrasil's key compression. either way, from my current prototyping it seems that this is going to be possible, so any artificial attempts to not implement it will result in weaker keys for people, and easier job for attackers who are able to change source.
its a bit of mess r n (had to change ironwood dependency too) but somehow works
https://github.com/cathugger/yggdrasil-go/tree/develop contains changes for both ironwood and yggdrasil codebases idk how this is going to be integrated but as proof of concept it should be good for now
ive made https://github.com/cathugger/yggkeygen which is kinda wip state but usable for key generation. also fixed up some stuff in my yggdrasil fork and made https://github.com/cathugger/yggdrasil-go/tree/fastkeys branch for stuff based on exact v0.4.0 tag. both branches work, but this may be more usable for ones who dont wanna debug other stuff from develop branch.
also made 226:43c3:4b8d:de20:114b:3991:a148:aff7 with 38 bits worth of compression after few hours of generation, feel free to ping it, it's my workstation.
Interesting work. I need to think about about if we want to do this -- or rather, if this is how I'd want to handle it. Considering that this is an experiment, and not some product we're trying to ship, my natural instinct is to stick with the standard library crypto/ed25519 for now... and if people really want that kind of speed, they can maintain their own fork or something.
That said, if I can find a clean way to make ironwood generic enough to accept different key types, and we can just wrap the post-hash value with the right PublicKey or something, then I'd be all in favor of doing that (and switching between the two would happen all on the yggdrasil-go side of the package boundary). As you noticed, we convert the ed25519 public key to a curve25519 key in the encrypted package. Since that sort of conversion isn't possible in general for signing and DH keys, I'd probably need to rethink the key exchange protocol a bit to make it truly generic, and that probably won't make it to the top of the priority list any time soon.
Assuming we go this route, it'll probably be delayed until at least the late v0.5 development cycle, or maybe v0.6+ if we want to do something more elaborate with the ironwood/encrypted package (e.g. switch the the noise protocol framework or something).
@Arceliar considering this basically works right now, I'd think only change needed would be allowing users to specify expanded representation, possibly in addition to existing way of specifying seed (for compatibility). Kinda hacky as there would be now two ways of doing the same, one of which isn't for standard crypto/ed25519, but eh, it's an option.
My current "replace all interfaces with whatever works for me" changes were just for prototyping, to see whether this works at all, and it fell into place surprisingly well.
On the other hand, we could go one step further and instead allow user passing interface of something what could do signing/verification stuff, and have function to derive another interface what could do box/unbox stuff. Derivation part would naturally only work for algorithms where that can make sense, eg. Ed25519/X25519 (maybe Ed448/X448 too?). Or, "secret key" could pack separate box/unbox key on its own. That wouldn't really help yet if one couldn't derive another such key from public key part, though, that could need protocol break.. but I don't dislike current key derivation concept for Curve25519 though so I'm not sure if we really want to change that, at least for Curve25519. Maybe caller could specify whether additional box/unbox key is needed, or it could be derived from public signing key.
Either way, I agree that this isn't urgent and can wait (& be maintained as fork) until we figure out clean way to get this in.
Regarding use of filippo.io/edwards25519 instead of crypto/ed25519, it seems like it would be fine, at least to me. crypto/ed25519 is very small, mostly diverting real work to crypto/ed25519/internal/edwards25519. filippo.io/edwards25519 and crypto/ed25519/internal/edwards25519 is basically the same code, and filippo is main maintainer of crypto packages, so it kinda looks fine for now and I doubt that things will change much in the future.
@Vort I wasn't aware of that issue, but essentially yes. Arceliar's specified algorithm is something what mkp224o used to use initially, but that now got superseded by doing some of field element math in batches, and yggkeygen utilizes the same stuff.