How to generate pseudorandom onion addresses

magic

Disclaimer

In this article, we will see -

1. How to host an onion website.
2. What are onion addresses and how they are generated.
3. How to bring some sense in an onion address.

We will focus on how rather than why.

All code pieces used in this article are written in python3 and can be found at this github repo.

Let us begin.

Theory

First, let’s briefly refresh our knowledge on tor.

TOR

TOR (The onion router) is a software used to surf internet anonymously. It encrypts your data multiple times and pass it through a series of relays (proxies) before sending your data to the website you intend to visit. By doing this, TOR ensures no one can know who are you and which website you are visiting at the same time.

TOR Hidden Services

We talked about client anonymity. TOR also provides a way for servers to be anonymous. These are called onion services. Onion services can be accessed only through tor network. An onion service is identified by an onion address. Eg. facebookcorewwwi.onion is the onion address for facebook’s onion service.

Practical

Enough with boring parts, let’s dive into some action.

Hosting onion website

Hosting onion website is pretty easy, it requires us to uncomment 2 lines only.

1. install tor

sudo apt-get install -y tor

2. uncomment 2 lines from file /etc/tor/torrc

first line specifies hidden service directory location, second line specifies at which port tor will redirect a request.

sudo sed -i 's/#HiddenServiceDir \/var\/lib\/tor\/hidden_service\//HiddenServiceDir \/var\/lib\/tor\/hidden_service\//' /etc/tor/torrc
sudo sed -i '0,/#HiddenServicePort 80 127.0.0.1:80/ s/#HiddenServicePort 80 127.0.0.1:80/HiddenServicePort 80 127.0.0.1:9000/' /etc/tor/torrc

3. run temporary python server at port 9000 to handle requests redirected by tor

python -m http.server 9000

4. run tor

tor

You should be able to find two files inside your hidden service directory /var/lib/tor/hidden_service/ -

1. hostname — your onion address, share it with your friends.
2. private_key — your private key, don’t share it with anyone.

Upon requesting hostname from tor browser should give you page served by our temporary python server.

Creating an onion address

onion addresses are generated using public keys. They are .onion appended lowercase base32 encoding of first 10 bytes of sha1 digest of DER encoded public key. A lot to take at once but do not worry because now we will see what last sentence means by deconstructing it in reverse.

To make our work easier, we will take help from cryptography library.

1. public key

from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.backends import default_backend
# generate key pair with exponent 65537, size 1024 bytes
rsa_key = rsa.generate_private_key(public_exponent = 0x10001, key_size = 0x400, backend = default_backend())
# get public key from key pair
public_key = rsa_key.public_key()

we can check contents of public key by printing its PEM encoded form

from cryptography.hazmat.primitives import serialization
# get PEM encoded public key
public_bytes = public_key.public_bytes(encoding = serialization.Encoding.PEM, format = serialization.PublicFormat.PKCS1)

this will give public_bytes as -

b'-----BEGIN RSA PUBLIC KEY-----\nMIGJAoGBAKenzXTYGumaJeQ6t3UiG+aVzw4l31qGsMrckVR/00uYAkYxIr9NFkng\nVcgkRQj1gorLBYLjrptcwRjsZRqEOz7HC8g7nyu0CBmaP7Dm54CwSW2HSFn9Omg4\nB1e9cOu3ZzDWX16OHPJvCmD6TiYf9OfKg/ir14uwtbJ+VKr8uACDAgMBAAE=\n-----END RSA PUBLIC KEY-----\n'

But, we are not interested in this format, we rather look at DER encoded form of our public key.

2. DER encoded public key

# get public key in DER format
public_bytes = public_key.public_bytes(encoding = serialization.Encoding.DER, format = serialization.PublicFormat.PKCS1)

this will give public_bytes as -

b'0\x81\x89\x02\x81\x81\x00\xa7\xa7\xcdt\xd8\x1a\xe9\x9a%\xe4:\xb7u"\x1b\xe6\x95\xcf\x0e%\xdfZ\x86\xb0\xca\xdc\x91T\x7f\xd3K\x98\x02F1"\xbfM\x16I\xe0U\xc8$E\x08\xf5\x82\x8a\xcb\x05\x82\xe3\xae\x9b\\\xc1\x18\xece\x1a\x84;>\xc7\x0b\xc8;\x9f+\xb4\x08\x19\x9a?\xb0\xe6\xe7\x80\xb0Im\x87HY\xfd:h8\x07W\xbdp\xeb\xb7g0\xd6_^\x8e\x1c\xf2o\n`\xfaN&\x1f\xf4\xe7\xca\x83\xf8\xab\xd7\x8b\xb0\xb5\xb2~T\xaa\xfc\xb8\x00\x83\x02\x03\x01\x00\x01'

Now, this looks pretty, doesn’t it?

3. sha1 digest of DER encoded public key

import hashlib
# initialize sha1
sha_1 = hashlib.sha1()
# get sha1 of public key
sha_1.update(public_bytes)
# get digest of public key
digest = sha_1.digest()

This will give digest as -

b'X\xf9\xf8.>>\x83\xf3\xc6%\xe4}\xdb\xd4\xeb+\x8e\xa8\xfc\x15'

4. first 10 bytes of sha1 digest of DER encoded public key

half_digest = digest[:10]

This will give half_digest as -

b'X\xf9\xf8.>>\x83\xf3\xc6%'

5. lowercase base32 encoding of first 10 bytes of sha1 digest of DER encoded public key

import base64
b32 = base64.b32encode(half_digest).decode('utf-8').lower()

This will give b32 as -

ld47qlr6h2b7hrrf

6. .onion appended lowercase base32 encoding of first 10 bytes of sha1 digest of der encoded public key

b32 + '.onion'

which finally gives our complete onion address as -

ld47qlr6h2b7hrrf.onion

To host onion service with this name, get your private key -

# get PEM encoded private key
rsa_key.private_bytes(encoding = serialization.Encoding.PEM, format = serialization.PrivateFormat.TraditionalOpenSSL, encryption_algorithm=serialization.NoEncryption()).decode('utf-8')

paste the content inside /var/lib/tor/hidden_service/private_key and restart tor service.

That was easy, now lets see the hard part.

Creating a pseudorandom onion address

To create pseudorandom address, there is no magic trick. We have to take the brute force approach. Following steps create an onion address with desired prefix -

1. get onion address from randomly generated public key
2. if it matches desired, we got one.
3. if not, go to step 1

Below code demostrates these 3 steps-

keygen

Approx time taken by above code to run is -

len(desired) |  time taken (seconds)  |   keys generated
_____________________________________________________________
       1     |            5           |         10
       2     |           157          |         10
             |                        |

Optimizing brute force

Generating pseudorandom addresses take lots of time because of many computation heavy operations involved. One of these tasks is generation of new public key to generate new onion address. It requires generation of private key as well which we don’t always require (till we get desired address). So we can optimize above approach by creating a new public key without its counter private key.

Detour

First, let us explore two important things that will help us optimize our algorithm.

Private and public exponents

To generate an RSA key pair, we perform following steps -

1. choose two distinct prime numbers, say p and q

p = 19
q = 3

2. compute n (modulus) = p*q

n = 57

3. compute φ(n) = (p-1)*(q-1)

φ(n) = 36

4. choose e (public exponent) such that e and φ(n) are co prime. People prefer e = 65537 (ie. 2¹⁶+1)

e = 65537

5. compute d (private exponent) such that d is modular multiplicative inverse of e modulus φ(n) (ie. (d*e)%φ(n) = 1).

To find modular multiplicative inverse, we do (idea taken from here) -

# find inverse modulus
def modinv(a, m):

    def egcd(a, b):
        if a == 0:
            return (b, 0, 1)
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

    g, x, _ = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x % m

This gives us d as -

d = 17

Decontructing RSA public key

If you want to go into details of public key format, this stackoverflow answer explains it beautifully. Here we pick up relevant parts only.

RSA public key follows the following ASN1 DER structure -

RSAPublicKey ::= SEQUENCE {
    modulus           INTEGER,  -- n
    publicExponent    INTEGER   -- e
}

Taking following public key as an example

-----BEGIN RSA PUBLIC KEY-----
MIGJAoGBAKenzXTYGumaJeQ6t3UiG+aVzw4l31qGsMrckVR/00uYAkYxIr9NFkng
VcgkRQj1gorLBYLjrptcwRjsZRqEOz7HC8g7nyu0CBmaP7Dm54CwSW2HSFn9Omg4
B1e9cOu3ZzDWX16OHPJvCmD6TiYf9OfKg/ir14uwtbJ+VKr8uACDAgMBAAE=
-----END RSA PUBLIC KEY-----

Its DER encoded form is -

b'0\x81\x89\x02\x81\x81\x00\xa7\xa7\xcdt\xd8\x1a\xe9\x9a%\xe4:\xb7u"\x1b\xe6\x95\xcf\x0e%\xdfZ\x86\xb0\xca\xdc\x91T\x7f\xd3K\x98\x02F1"\xbfM\x16I\xe0U\xc8$E\x08\xf5\x82\x8a\xcb\x05\x82\xe3\xae\x9b\\\xc1\x18\xece\x1a\x84;>\xc7\x0b\xc8;\x9f+\xb4\x08\x19\x9a?\xb0\xe6\xe7\x80\xb0Im\x87HY\xfd:h8\x07W\xbdp\xeb\xb7g0\xd6_^\x8e\x1c\xf2o\n`\xfaN&\x1f\xf4\xe7\xca\x83\xf8\xab\xd7\x8b\xb0\xb5\xb2~T\xaa\xfc\xb8\x00\x83\x02\x03\x01\x00\x01'

We see that last 3 bytes form our e (0x10001). So, to get a new public key out of it, we just change last 3 bytes (keeping n same).

Back to optimizing brute force

Putting this knowledge to our use, we modify steps for finding desired onion address as -

1. generate key pair
2. find onion address from public key
3. if onion address matches with desired, go to step 6
4. change e
5. If e is not of 3 bytes, go to step 1 otherwise go to step 3
6. find d from new e and existing values (n, p, q)
7. host your onion website with new found private key

Keeping this at a single place, our code for above algorithm looks like -

keygen optimized

Approx time taken by above code is (exponential improvement) -

len(desired) |  time taken (seconds)  |   keys generated
_____________________________________________________________
       1     |            0           |         10
       2     |            0           |         10
       3     |            4           |         10
       4     |           106          |         10

Further Optimizations

We saw that even for a brute force algorithm, there is scope of improvement. One more improvement worth exploring is using multithreading in our code. Since python has a bad reputation for its multithreading approach, adding multiprocessing to above code or rewriting it in a language with multithreading support can be a good home work.

Closing

There we have it, our own key generator for desired prefix in onion address. Please note that these keys might not be suitable for production use (because of altered public exponent, not checking strength of keys, etc). That being said, use this for fun and unimportant things. And remember one more thing, stay anonymous, stay safe.

Inspiration taken from eschalot.

References

ReclaimYourPrivacy/eschalot

RFC 3447 - Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1