Dangerous toys: Anything to ed25519 (SSH Keys) | Hacker News Reader

Dangerous toys: Anything to ed25519 (SSH Keys)

0xcc.re

81 pointsSami_Lehtinen31 comments

another dangerous toy I particularly enjoy, vanity keys:

https://github.com/warner/wireguard-vanity-address

Although not as dangerous since the entropy of the rng is (mostly?) still there. If I'm doing the handwaving right, it's base64 where each char contains 6 bits, so you reduce the effective keysize to 256-6*$num_chars -- cryptographers tell me how wrong I am :)

I'm having a hard time seeing much danger in that. If your threat model assumes the attacker already has your public key having an easily guessable public key doesnt give them any more information.

My biggest worry would be some sort of spoofing. An attacker may be able to impersonate you (or rather a server you control) if they generate a similar vanity key and convince a 3rd party to accept it as yours.

Ah you're right, there is seemingly no loss of entropy.

> so you reduce the effective keysize to 256-6*$num_chars

Correct: you reduce the search-space of the private key, but you simultaneously increase the cost of brute-forcing by the same amount because finding keys to try in the smaller search-space takes more work (the same work as generating vanity addresses).

As long as brute-forcing is the most efficient way to crack the attacker has to do the same expected amount of work on vanity addresses.

I may be wrong, but similar to BTC et al. vanity keys I don't think there is any actual loss of entropy.

There is: rejection sampling means that you don't ruin uniformity but your key space necessarily shrinks. As a thought experiment, imagine if you fixed all but the last hex digit of the public key to be your favorite string -- there are at most 16 private keys that could achieve that. We don't have fast ways to generate vanity addresses (just brute force with exponential complexity in the length of the fixed bits) so in practice entropy loss is minimal and cryptographically non-concerning.

Which is the crux of it all - there's no way to optimize the search of the key space to generate only keys that already have a set prefix. Rejection sampling can target anything, no matter if someone (or some dictionary) applies a meaning to the specified sequence. As another thought experiment, imagine using a true random source to generate a BTC priv key whose base58-represented P2PK address happened to spell out "1money". Would it be less entropic than if it were on purpose searched for and found using e.g. VanityGen? Or less entropic than some random characters like "1trwm"? Certainly not. By a total coincidence the word "trwm" is Welsh for "heavy".

One brittle, brute force method to do this (RSA-style) a decade ago was LD_PRELOAD vs. the RNG:

Phidelius: Constructing Asymmetric Keypairs From Mere Passwords For Fun and PAKE

https://dankaminsky.com/2012/01/03/phidelius/

Non-Persistent PGP Keys (2011)

https://ritter.vg/blog-non_persistent_pgp.html

Also related: https://github.com/jpf/lokey, "a tool for converting between cryptographic key formats". Unfortunately it needs maintenance.

It's 2^255 - 19, not 255^19.

Does that imply that there are some 256 bit patterns that aren't valid private keys, or does the 2^255 - 19 not describe the private key space?

2^255 - 19, describes the finite field over which the elliptic curve is defined.

The "keyspace" in the sense of valid public keys is really defined by the order of the curves generator, G, which in this case is approximately 2^252 ish. Due to the curve having a co-factor of 8.

So when generating a private key, is any 256 bit random sequence good (it gets reduced down to the 252 bits available) or do you have to check you didn't pick one of the 2^4 keys that aren't valid? (Actually, is 2^4 even the right number? Seems awfully low, and hence I guess, unlikely)

This article [0] has a good explanation of why clamping is necessary. But the process is very simple, you just generate 32 random bytes, clear the three least significant bits to avoid small-subgroup attacks, then clear the most significant bit and set the second most significant to avoid side-channel attacks which may occur if an implementation isn’t constant-time. The Libsodium source shows this pretty clearly: [1], lines 18-23.

0: https://www.jcraige.com/an-explainer-on-ed25519-clamping

1: https://github.com/jedisct1/libsodium/blob/master/src/libsod...

I'm not sure clamping has anything to do with constant-time and side-channel attacks.

In very rough terms, not accounting for the cofactor means that there are several related unexpected points for any given Curve25519 key. In theory, these points would allow you to conduct an invalid curve point attack; in practice, you have so few of these points that you leak only a couple bits of key information, unlike with the non-25519-vintage curves, where invalid curve points can leak the entire key over a series of probes. So, for DH systems, people sometimes shrug off clamping.

For Ed25519 and signing systems in general, it's a much bigger deal, because it implies that there are multiple possible validating signatures for a set of inputs, which breaks protocol assumptions.

Hm, with regard to timing attacks, I’m not talking about clearing the cofactor, but rather setting the most significant bit to zero & the second most significant to one. My understanding is that this is to defend against an insecure implementation of the scalar multiplication operation which takes a varying length of time depending on which bit is the first non-zero one, thereby revealing information about the key. The linked article supports this (I believe), but I’m always happy to be corrected about these kinds of things :)

I think it is simpler, the algorithm used repeated doubling to find the point on the elliptic curve, so by setting the highest bit to one it ensured that the operation is done to a fixed number of times no matter the input

Nope, you're probably right!

You’re correct!

Theoretically, when you generate a Curve25519 key, you're meant to "clamp" it, which premultiplies the key by the cofactor. In practice, you can get away with just taking any random 32-byte string. Clamping (and its practical importance) is a whole big discussion among Curve25519-heads.

other poster described clamping with is right.

But yep, any 256-bit string is good.

I should clarify, not the curves generator, but the generator of the cyclic subgroup of the curve we work in.

this idea of making a predictable key doesn't seem advantageous at all. what if you can't remember whatever series of words you used to generate this not-very-secure key? you'd have to store those words somewhere..... and so you might as well store the whole key there.

seems like a reliable way to back up your private keys would be to print it on matte or card stock, and optionally laminate it. to recover the key you just OCR it

In what format do you store the "whole key" there, so that you can type it in easily and quickly if required?

You might argue that a situation where you have to open the safe with the printed-out key material cannot be particularly urgent, but apparently the author found it useful for this kind of situation.

In the format of regular armored ASCII text that all .pem keys have. It doesn't take a whole lot of time to download an OCR program. I think Google Docs has had OCR for a decade. You go to your safe, take a picture of the printout, open it in google docs, and OCR the text. Takes, what, 60 seconds? 2 minutes max? Or like somebody else said, a QR code.

A 12 word mnemonic phrase is worlds easier to use than that. You will download an OCR program, send the photo from your phone to the computer, and run OCR on it? Or you will upload your cold key onto google drive?

Easier to use, but less reliable. If you don't get the words right (years after you first created them) your key is gone. It's also less secure to depend on a set of words that a human can remember (and thus leak via rubber-hose crypto). There's versioning and other issues mentioned in the critique of the paper, leading to them recommending nobody use it. And no, you wouldn't send the photo from your phone to the computer, you'd do it all on a phone, off-line, and could then copy the key to a YubiKey from your phone.

See BIP39 for an established standard to creating a mnemonic sequences out of entropy: https://github.com/bitcoin/bips/blob/ad745f2f0155c90f0471ba8...

Instead of printing the text, you might think about printing it as a large QR code or some other kind of digital medium that would make it easier to import it. QR codes are pretty resilient.

I have a folder full of secrets, in large QR format, in a safe. Various keys, password, account details. Takes a few seconds to make and when it was needed - totally worth all the little minutes it took to build the storage when it saved my bacon those few times.

It's a nonsense project with no utility. And it's not exactly rocket science that running a memorable phrase through a KDF is going to be more predictable than an actual CSPRNG. This is crypto/security 101. There's a good reason we say "don't roll your own crypto" in this industry.

This is basically the brainwallet concept for Bitcoin private keys. e.g. https://en.bitcoin.it/wiki/Brainwallet

Reply on news.ycombinator.com