5 ms·

Dangerous toys: Anything to ed25519 (SSH Keys)

81 points by Sami_Lehtinen 5y ago

matthewaveryusa 5y ago
another dangerous toy I particularly enjoy, vanity keys: https://github.com/warner/wireguard-vanity-address 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 :)
- ghkbrew 5y ago
  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.
  - matthewaveryusa 5y ago
    Ah you're right, there is seemingly no loss of entropy.
- daneel_w 5y ago
  I may be wrong, but similar to BTC et al. vanity keys I don't think there is any actual loss of entropy.
  - madars 5y ago
    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.
    - daneel_w 5y ago
      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".
- remcob 5y ago
  > 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.
password4321 5y ago
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/ https://dankaminsky.com/2012/01/03/phidelius/ Non-Persistent PGP Keys (2011) https://ritter.vg/blog-non_persistent_pgp.html https://ritter.vg/blog-non_persistent_pgp.html -- Also related: https://github.com/jpf/lokey https://github.com/jpf/lokey, "a tool for converting between cryptographic key formats". Unfortunately it needs maintenance.
john_alan 5y ago
It's 2^255 - 19, not 255^19.
- KayEss 5y ago
  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?
  - john_alan 5y ago
    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.
    - KayEss 5y ago
      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)
      - tptacek 5y ago
        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.
      - john_alan 5y ago
        other poster described clamping with is right. But yep, any 256-bit string is good.
      - opheliate 5y ago
        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 https://www.jcraige.com/an-explainer-on-ed25519-clamping 1: https://github.com/jedisct1/libsodium/blob/master/src/libsodium/crypto_sign/ed25519/ref10/keypair.c https://github.com/jedisct1/libsodium/blob/master/src/libsod...
0xbadcafebee 5y ago
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
- vel0city 5y ago
  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.
  - djbusby 5y ago
    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.
- MauranKilom 5y ago
  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.
  - 0xbadcafebee 5y ago
    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.
nayuki 5y ago
This is basically the brainwallet concept for Bitcoin private keys. e.g. https://en.bitcoin.it/wiki/Brainwallet https://en.bitcoin.it/wiki/Brainwallet

81 points by Sami_Lehtinen 5y ago

another dangerous toy I particularly enjoy, vanity keys: https://github.com/warner/wireguard-vanity-address 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 :)

ghkbrew 5y ago
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.
- matthewaveryusa 5y ago
  Ah you're right, there is seemingly no loss of entropy.
daneel_w 5y ago
I may be wrong, but similar to BTC et al. vanity keys I don't think there is any actual loss of entropy.
- madars 5y ago
  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.
  - daneel_w 5y ago
    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".
remcob 5y ago
> 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.

password4321 5y ago

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/ https://dankaminsky.com/2012/01/03/phidelius/ Non-Persistent PGP Keys (2011) https://ritter.vg/blog-non_persistent_pgp.html https://ritter.vg/blog-non_persistent_pgp.html -- Also related: https://github.com/jpf/lokey https://github.com/jpf/lokey, "a tool for converting between cryptographic key formats". Unfortunately it needs maintenance.

john_alan 5y ago

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

KayEss 5y ago
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?
- john_alan 5y ago
  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.
  - KayEss 5y ago
    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)
    - tptacek 5y ago
      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.
    - john_alan 5y ago
      other poster described clamping with is right. But yep, any 256-bit string is good.
    - opheliate 5y ago
      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 https://www.jcraige.com/an-explainer-on-ed25519-clamping 1: https://github.com/jedisct1/libsodium/blob/master/src/libsodium/crypto_sign/ed25519/ref10/keypair.c https://github.com/jedisct1/libsodium/blob/master/src/libsod...

0xbadcafebee 5y ago

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

vel0city 5y ago
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.
- djbusby 5y ago
  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.
MauranKilom 5y ago
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.
- 0xbadcafebee 5y ago
  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.

nayuki 5y ago

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