[ /cjdns/genkeys ]

I've been making an effort to learn more about ArchLinux lately. I've spent a few nights playing around with a vm, and I've learned a fair bit.

I was trying to come up with a system image that I could just flash onto other media, and naturally, an ideal image (for me) would include my favourite tools, nodejs and cjdns. I'll get into the details of that in another post, this article isn't about Arch.

When I installed cjdns and generated a configuration file, I found that the node had some bad black holes in its routing table. I was able to reach nodes that were really distant, but for some reason I couldn't reach a VPS that was only two hops away. I suspect the issue had something to do with their respective xor distances, and I wanted to confirm this. That would mean trying out different keys and checking which (if any) have an easier time peering with (and pinging) specific nodes.

There are known techniques for generating vanity ipv6s, but they involve generating a complete configuration file, searching through it for an the ipv6, and checking if the address matches some pattern. If the address does not, it gets thrown away, and a new conf is generated. That's really wasteful, and I'd rather not mess around with Bash if it's possible to just generate keypairs and test them in one language.

Fortunately, the Javascript community has an answer for every problem (sometimes they have ten). It didn't take me long to find a library for the task, and so I got down to business trying to figure out how to generate a cjdns privateKey, publicKey, and ipv6 in Javascript.

The Components

  1. Generate a privateKey
  2. Generate the privateKey's corresponding publicKey
  3. Generate the publicKey's corresponding ipv6
  4. Check that the generated ipv6 is a valid cjdns ip

Learning about the privateKey

A privateKey is a 32 element uint8_t array. In the making of my last post I discovered that Javascript has a fairly simple way of coercing larger numbers into this format:

function confine(n){
  return n>>>0;
};

Just use the zero-fill right shift operator, shifting the number 0 bits to the right.

Once again, larsg has pointed me in the right direction as to where I might find the details of how cjdns generates these values:

From cjdns/admin/angel/cjdroute2.c.

A similar function can also be found in cjdns/contrib/c/makekeys.c.

static int genAddress(uint8_t addressOut[40],
                      uint8_t privateKeyHexOut[65],
                      uint8_t publicKeyBase32Out[53],
                      struct Random* rand)
{
    struct Address address;
    uint8_t privateKey[32];

    for (;;) {
        Random_bytes(rand, privateKey, 32);
        crypto_scalarmult_curve25519_base(address.key, privateKey);
        // Brute force for keys until one matches FC00:/8
        if (AddressCalc_addressForPublicKey(address.ip6.bytes, address.key)) {
            Hex_encode(privateKeyHexOut, 65, privateKey, 32);
            Base32_encode(publicKeyBase32Out, 53, address.key, 32);
            Address_printShortIp(addressOut, &address);
            return 0;
        }
    }
}

Address is a struct (defined in cjdns/dht/Address.h). The following fields are used in this function:

  • key: uint8_t key[Address_KEY_SIZE]; where Address_KEY_SIZE is defined as 32
  • ip6.bytes: ip6 is a union which can be initialized as:
    1. a struct consisting of four uint32s
    2. a struct consisting of two uint64s
    3. a 16 element array of uint8s (the type used in this case)

As you can see, line 13 of this function passes the bytes array and the key to a function from cjdns/crypto/AddressCalc.c

int AddressCalc_addressForPublicKey(uint8_t addressOut[16], const uint8_t key[32])
{
    uint8_t hash[crypto_hash_sha512_BYTES];
    crypto_hash_sha512(hash, key, 32);
    crypto_hash_sha512(hash, hash, crypto_hash_sha512_BYTES);
    Bits_memcpyConst(addressOut, hash, 16);
    return hash[0] == 0xFC;
}

Analysis

All of the arguments for genAddress are passed by reference. That means that space is allocated for them outside of the function, and at the time of the function's completion, they are assumed to have been filled.

genAddress effectively returns all three of the values we intend to generate:

  1. the ipv6 (a null terminated, 39 character string consisting of hexadecimal digits and colons (':'))
  2. the publicKey (a null terminated, 52 character string consisting of cjdns base32 character). within the configuration file, the string is terminated with ".k", though this is omitted during the generation process
  3. the privateKey (a null terminated, 64 character string of hexadecimal digits)

Generating the privateKey

This is the easy part. While it's critical that you use a good random number generator for the task in real applications, for the sake of testing out the rest of these functions, any generator will do.

We need 32 uint8s. We also need to be able to print it as 64 hex digits.

Generating the publicKey

This is the hard part. I cheated and used a function from tweetnacl that I don't understand. At some point I hope to reverse engineer exactly what it does.

The resulting public key is also a 32 element uint8 array. We also need to be able to reencode it as 52 characters of base32.

Generating the IPV6

This wouldn't have been that hard, as the function AddressCalc_addressForPublicKey shown above isn't that complicated. It was made much easier by the fact that cjd had already written it in js.

My work

I got tired of blogging about it, and just dug into the code. The good news is that [it works]. The bad news is that I'm still tired of writing about it. In an upcoming post I'm going to write more about what can be done with this and the xor metric, now that they're all in js.