Implement file storage

5 files changed, 277 insertions, 125 deletions

diff --git a/forge_key.py b/forge_key.py
deleted file mode 100755
index 850f2b1..0000000
--- a/forge_key.py
+++ /dev/null
@@ -1,88 +0,0 @@
-#!/usr/bin/env python3
-import argparse
-import os
-import shutil
-import base64
-import random
-
-import gmpy2
-from Crypto.PublicKey import RSA
-from stem.control import Controller
-
-
-def main():
-    arg_parser = argparse.ArgumentParser()
-    args = arg_parser.parse_args()
-
-    # Generate RSA key pair
-    data_len = 100
-    data = random.getrandbits(data_len * 8).to_bytes(data_len, 'little')
-    print('Data:', base64.b64encode(data).decode())
-    key = forge_rsa_key(data)
-
-    # Public hidden service
-    with Controller.from_port() as controller:
-        controller.authenticate()
-        response = controller.create_ephemeral_hidden_service(
-            {80: 5000},
-            await_publication=True,
-            key_type='RSA1024',
-            key_content=key,
-        )
-        print(response.service_id)
-
-def crypto_prime(num):
-    i = 2
-    for x in range(64): # 2^(-128) false
-        if not gmpy2.is_strong_prp(num, i): return False
-        i = gmpy2.next_prime(i)
-    return True
-
-def next_prime(num):
-    while True:
-        num = gmpy2.next_prime(num)
-        # ensure a sufficient is-prime confidence
-        if crypto_prime(num): return int(num)
-
-DATA_LEN = 800
-NONCE_LEN = 200
-KEY_LEN = 1024
-
-def forge_rsa_key(data: bytes):
-    # Generate RSA key with p = 11.
-    # By Cramer's conjecture (which is likely to be true),
-    #  the maximum prime gap for a 1024-bit number should be around 500000.
-    # We choose a 800-bit data size and a 200-bit nonce, which allows a maximum
-    #  gap of 2^(1023-1000)/11 ~ 760000 and a collision probability of ~2^(-100).
-    assert(len(data) == DATA_LEN // 8)
-    # let the highest bit be 1
-    while True:
-        n_expect = 1 << (KEY_LEN - 1) | \
-                int.from_bytes(data, 'little') << (KEY_LEN - 1 - DATA_LEN) | \
-                random.getrandbits(NONCE_LEN) << (KEY_LEN - 1 - DATA_LEN - NONCE_LEN)
-        while True:
-            p = 11
-            q = next_prime((n_expect - 1) // p + 1)
-            n = p * q
-            # final (paranoid) correctness check,
-            #  should be true given the conjecture is true
-            if (n >> (KEY_LEN - 1 - DATA_LEN)) == \
-                    (n_expect >> (KEY_LEN - 1 - DATA_LEN)): break
-        # Compute RSA components
-        e = 65537
-        d = int(gmpy2.invert(e, (p - 1) * (q - 1)))
-        # Library reference
-        # https://pycryptodome.readthedocs.io/en/latest/src/public_key/rsa.html
-        # if get an invalid key (prob ~1/11), retry with another nonce
-        try: key = RSA.construct((n, e, d), consistency_check=True)
-        except ValueError: continue
-        break
-
-    # Tor accepts DER-encoded, then base64 encoded RSA key
-    # https://github.com/torproject/tor/blob/a462ca7cce3699f488b5e2f2921738c944cb29c7/src/feature/control/control_cmd.c#L1968
-    der = key.export_key('DER', pkcs=1)
-    ret = str(base64.b64encode(der), 'ASCII')
-    return ret
-
-if __name__ == '__main__':
-    main()
diff --git a/fs.py b/fs.py
new file mode 100644
index 0000000..960edf7
--- /dev/null
+++ b/fs.py
@@ -0,0 +1,143 @@
+import re
+import tor_utils
+
+
+class VFS:
+    def __init__(self, data_size=800, replica_factor=3):
+        assert data_size / 8 == data_size // 8
+        self.fs = dict()
+        self.re_slash = re.compile('/+')
+        self.block_size = data_size // 8
+        self.replica_factor = replica_factor
+
+    def open(self, path):
+        path = self.re_slash.sub('/', path)
+        tokens = path.split('/')
+        handle = self.fs
+
+        for tk in tokens[:-1]:
+            if not tk:
+                raise ValueError('Invalid path %s' % path)
+            handle = handle.get(tk, dict())
+            if not isinstance(handle, dict):
+                raise ValueError('%s is not valid' % path)
+
+        default_file_handle = FileHandle(
+            block_size=self.block_size,
+            replica_factor=self.replica_factor,
+        )
+        file_handle = handle.get(tokens[-1], default_file_handle)
+        return file_handle
+
+
+class FileHandle:
+    def __init__(self, block_size, replica_factor):
+        self.block_size = block_size
+        self.replica_factor = replica_factor
+        self.block_store = dict()
+
+    def load_block(self, index, check_boundary=True):
+        assert index >= 0
+
+        if index in self.block_store:
+            # Load from one of its replica
+            for addr in self.block_store[index]:
+                block = tor_utils.load_block(addr)
+                if block is not None:
+                    return block
+
+            # Fail
+            raise ValueError("Fail to load block at index %d" % index)
+
+        elif check_boundary:
+            raise ValueError("Index out of bound")
+
+        else:
+            return b'\x00' * self.block_size
+
+    def store_block(self, index, block):
+        assert index >= 0
+
+        addresses = list()
+        for _ in range(self.replica_factor):
+            addr = tor_utils.store_block(block, self.block_size)
+            addresses.append(addr)
+
+        self.block_store[index] = addresses
+
+    def read(self, offset, length):
+        begin_offset = offset
+        end_offset = offset + length
+
+        begin_index = begin_offset // self.block_size
+        end_index = end_offset // self.block_size
+
+        # Load first block
+        if begin_offset / self.block_size != begin_index:
+            block = self.load_block(begin_index)
+            front_length = self.block_size * (begin_index + 1) - begin_offset
+            assert front_length > 0
+            front_block = block[:-front_length]
+            begin_index += 1
+        else:
+            front_length = 0
+            front_block = b''
+
+        # Load last block
+        if end_offset / self.block_size != end_index:
+            block = self.load_block(end_index)
+            tail_length = self.block_size * (end_index) - end_offset
+            assert tail_length > 0
+            tail_block = block[:tail_length]
+        else:
+            tail_length = 0
+            tail_block = b''
+
+        # Load intermediate blocks
+        data = front_block
+
+        for index in range(begin_index, end_index):
+            block = self.load_block(index)
+            data += block
+
+        data += tail_block
+        return data
+
+    def write(self, offset, data):
+        length = len(data)
+        begin_offset = offset
+        end_offset = offset + length
+
+        begin_index = begin_offset // self.block_size
+        end_index = end_offset // self.block_size
+
+        # Update first block
+        if begin_offset / self.block_size != begin_index:
+            block = self.load_block(begin_index)
+            front_length = self.block_size * (begin_index + 1) - begin_offset
+            assert front_length > 0
+
+            new_block = block[:-front_length] + data[:front_length]
+            self.store_block(begin_index, new_block)
+            begin_index += 1
+        else:
+            front_length = 0
+
+        # Update last block
+        if end_offset / self.block_size != end_index:
+            block = self.load_block(end_index)
+            tail_length = self.block_size * (end_index) - end_offset
+            assert tail_length > 0
+
+            new_block = data[-tail_length:] + block[:tail_length]
+            self.store_block(end_index, new_block)
+        else:
+            tail_length = 0
+
+        # Update intermediate blocks
+        for index in range(begin_index, end_index):
+            begin_data_offset = front_length + self.block_size * (index - begin_index)
+            end_data_offset = begin_data_offset + self.block_size
+
+            new_block = data[begin_data_offset:end_data_offset]
+            self.store_block(index, new_block)
diff --git a/get_data.py b/get_data.py
deleted file mode 100755
index e509180..0000000
--- a/get_data.py
+++ /dev/null
@@ -1,37 +0,0 @@
-#!/usr/bin/env python3
-import argparse
-import os, sys
-import shutil
-import base64
-import random
-
-import gmpy2
-import asn1
-from Crypto.PublicKey import RSA
-from stem.control import Controller
-
-
-def main(name):
-    controller = Controller.from_port()
-    controller.authenticate()
-    a = str(controller.get_hidden_service_descriptor(name))
-    public = a[a.find('PUBLIC KEY-----')+15:a.find('-----END')].replace('\n', '')
-    decoder = asn1.Decoder()
-    decoder.start(base64.b64decode(public))
-    decoder.start(decoder.read()[1])
-    data = data_from_public_key(decoder.read()[1])
-    print(base64.b64encode(data).decode())
-
-DATA_LEN = 800
-NONCE_LEN = 200
-KEY_LEN = 1024
-
-def data_from_public_key(n):
-    data_num = (n - (1 << (KEY_LEN - 1))) >> (KEY_LEN - 1 - DATA_LEN)
-    return data_num.to_bytes(DATA_LEN // 8, 'little')
-
-if __name__ == '__main__':
-    if len(sys.argv) < 2:
-        print(sys.argv[0], '[hidden service name]')
-        sys.exit(1)
-    main(sys.argv[1])
diff --git a/main.py b/main.py
new file mode 100755
index 0000000..738c9db
--- /dev/null
+++ b/main.py
@@ -0,0 +1,13 @@
+#!/usr/bin/env python3
+import argparse
+
+
+def main():
+    parser = argparse.ArgumentParser()
+    args = parser.parse_args()
+
+
+
+
+if __name__ == '__main__':
+    main()
diff --git a/tor_utils.py b/tor_utils.py
new file mode 100644
index 0000000..8af2e23
--- /dev/null
+++ b/tor_utils.py
@@ -0,0 +1,121 @@
+import base64
+import random
+
+import asn1
+import gmpy2
+from Crypto.PublicKey import RSA
+from stem.control import Controller
+
+
+def store_block(data, data_len=100):
+    # Generate RSA key pair
+    data = random.getrandbits(data_len * 8).to_bytes(data_len, 'little')
+    key = forge_rsa_key(data)
+
+    # Public hidden service
+    with Controller.from_port() as controller:
+        controller.authenticate()
+        response = controller.create_ephemeral_hidden_service(
+            {80: 5000},
+            await_publication=True,
+            key_type='RSA1024',
+            key_content=key,
+        )
+
+    return response.service_id
+
+
+def crypto_prime(num):
+    i = 2
+    for x in range(64): # 2^(-128) false
+        if not gmpy2.is_strong_prp(num, i): return False
+        i = gmpy2.next_prime(i)
+    return True
+
+
+def next_prime(num):
+    while True:
+        num = gmpy2.next_prime(num)
+        # ensure a sufficient is-prime confidence
+        if crypto_prime(num): return int(num)
+
+
+def forge_rsa_key(data: bytes, key_size=1024, data_size=800, nonce_size=200):
+    assert nonce_size + data_size < key_size
+    assert data_size / 8 == data_size // 8
+    assert(len(data) == data_size // 8)
+
+    # Generate RSA key with p = 11.
+    # By Cramer's conjecture (which is likely to be true),
+    #  the maximum prime gap for a 1024-bit number should be around 500000.
+    # We choose a 800-bit data size and a 200-bit nonce, which allows a maximum
+    #  gap of 2^(1023-1000)/11 ~ 760000 and a collision probability of ~2^(-100).
+    # let the highest bit be 1
+    while True:
+        n_expect = 1 << (key_size - 1) | \
+                int.from_bytes(data, 'little') << (key_size - 1 - data_size) | \
+                random.getrandbits(nonce_size) << (key_size - 1 - data_size - nonce_size)
+        while True:
+            p = 11
+            q = next_prime((n_expect - 1) // p + 1)
+            n = p * q
+            # final (paranoid) correctness check,
+            #  should be true given the conjecture is true
+            if (n >> (key_size - 1 - data_size)) == \
+                    (n_expect >> (key_size - 1 - data_size)): break
+        # Compute RSA components
+        e = 65537
+        d = int(gmpy2.invert(e, (p - 1) * (q - 1)))
+        # Library reference
+        # https://pycryptodome.readthedocs.io/en/latest/src/public_key/rsa.html
+        # if get an invalid key (prob ~1/11), retry with another nonce
+        try:
+            key = RSA.construct((n, e, d), consistency_check=True)
+        except ValueError:
+            continue
+        break
+
+    # Tor accepts DER-encoded, then base64 encoded RSA key
+    # https://github.com/torproject/tor/blob/a462ca7cce3699f488b5e2f2921738c944cb29c7/src/feature/control/control_cmd.c#L1968
+    der = key.export_key('DER', pkcs=1)
+    ret = str(base64.b64encode(der), 'ASCII')
+    return ret
+
+
+def load_block(block_id, data_len=61):
+    url = '%s.union' % block_id
+
+    with Controller.from_port() as controller:
+        controller.authenticate()
+        try:
+            descriptor = str(controller.get_hidden_service_descriptor(url))
+        except ValueError:
+            return None
+
+    print(descriptor)
+
+    # b = descriptor[descriptor.find('BEGIN'):descriptor.find('END')]
+    # c = descriptor[descriptor.find('BEGIN MESSAGE'):descriptor.find('END MESSAGE')]
+    #print(x, a)
+    # print(x, hashlib.sha256((b + c).encode()).hexdigest())
+
+
+def data_from_public_key(n, key_size=1024, data_size=488):
+    data_num = (n - (1 << (key_size - 1))) >> ((key_size - 1) - data_size)
+    return data_num.to_bytes(data_size // 8, 'little')
+
+
+def load_block(name: str):
+    with Controller.from_port() as controller:
+        controller.authenticate()
+        a = str(controller.get_hidden_service_descriptor(name))
+        public = a[a.find('PUBLIC KEY-----')+15:a.find('-----END')].replace('\n', '')
+        decoder = asn1.Decoder()
+        decoder.start(base64.b64decode(public))
+        decoder.start(decoder.read()[1])
+        data = data_from_public_key(decoder.read()[1])
+        return data
+
+def data_from_public_key(n, key_size=1024, data_size=800, nonce_size=200):
+    data_num = (n - (1 << (key_size - 1))) >> (key_size - 1 - data_size)
+    return data_num.to_bytes(data_size // 8, 'little')