unwanted commit
[oweals/gnunet.git] / contrib / gnunet-chk.py
1 #!/usr/bin/python
2 # This file is part of GNUnet.
3 # (C) 2013 Christian Grothoff (and other contributing authors)
4 #
5 # GNUnet is free software; you can redistribute it and/or modify
6 # it under the terms of the GNU General Public License as published
7 # by the Free Software Foundation; either version 3, or (at your
8 # option) any later version.
9 #
10 # GNUnet is distributed in the hope that it will be useful, but
11 # WITHOUT ANY WARRANTY; without even the implied warranty of
12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 # General Public License for more details.
14 #
15 # You should have received a copy of the GNU General Public License
16 # along with GNUnet; see the file COPYING.  If not, write to the
17 # Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 # Boston, MA 02111-1307, USA.
19
20 # File:    gnunet-chk.py
21 # Brief:   Computes GNUNET style Content Hash Key for a given file
22 # Author:  Sree Harsha Totakura
23
24 from hashlib import sha512
25 import logging
26 import os
27 import getopt
28 import sys
29 from Crypto.Cipher import AES
30
31 # Defaults
32 DBLOCK_SIZE = (32 * 1024)   # Data block size
33
34 # Pick a multiple of 2 here to achive 8-byte alignment!  We also
35 # probably want DBlocks to have (roughly) the same size as IBlocks.
36 # With SHA-512, the optimal value is 32768 byte / 128 byte = 256 (128
37 # byte = 2 * 512 bits).  DO NOT CHANGE!
38 CHK_PER_INODE = 256
39
40 CHK_HASH_SIZE = 64              # SHA-512 hash = 512 bits = 64 bytes
41
42 CHK_QUERY_SIZE = CHK_HASH_SIZE  # Again a SHA-512 hash
43
44 GNUNET_FS_URI_PREFIX = "gnunet://fs/" # FS CHK URI prefix
45
46 GNUNET_FS_URI_CHK_INFIX = "chk/" # FS CHK URI infix
47
48
49 def encode_data_to_string (data):
50     """Returns an ASCII encoding of the given data block like
51     GNUNET_STRINGS_data_to_string() function.
52     
53     data: A bytearray representing the block of data which has to be encoded
54     """
55     echart = "0123456789ABCDEFGHIJKLMNOPQRSTUV"    
56     assert (None != data)
57     assert (bytearray == type(data))
58     size = len(data)
59     assert (0 != size)
60     vbit = 0
61     wpos = 0
62     rpos = 0
63     bits = 0
64     out = ""
65     while (rpos < size) or (vbit > 0):
66         if (rpos < size) and (vbit < 5):
67             bits = (bits << 8) | data[rpos] # eat 8 more bits
68             rpos += 1
69             vbit += 8
70         if (vbit < 5):
71             bits <<= (5 - vbit) # zero-padding
72             assert (vbit == ((size * 8) % 5))
73             vbit = 5
74         out += echart[(bits >> (vbit - 5)) & 31]
75         wpos += 1
76         vbit -= 5
77     assert (0 == vbit)
78     return out;
79
80
81 def sha512_hash (data):
82     """ Returns the sha512 hash of the given data. 
83     
84     data: string to hash
85     """
86     hash_obj = sha512()
87     hash_obj.update (data)
88     return hash_obj.digest()
89
90
91 class AESKey:
92     """Class for AES Keys. Contains the main key and the initialization
93     vector. """
94
95     key = None                  # The actual AES key
96     iv = None                   # The initialization vector
97     cipher = None               # The cipher object
98     KEY_SIZE = 32               # AES 256-bit key = 32 bytes
99     IV_SIZE = AES.block_size    # Initialization vector size (= AES block size)
100     
101     def __init__ (self, passphrase):
102         """Creates a new AES key. 
103         
104         passphrase: string containing the passphrase to get the AES key and
105                       initialization vector
106         """
107         passphrase = bytearray (passphrase);
108         self.key = bytearray (self.KEY_SIZE)
109         self.iv = bytearray (self.IV_SIZE)
110         if (len (passphrase) > self.KEY_SIZE):
111             self.key = passphrase[:self.KEY_SIZE]
112             passphrase = passphrase[self.KEY_SIZE:]
113             if (len (passphrase) > self.IV_SIZE):
114                 self.iv = passphrase[:self.IV_SIZE]
115             else:
116                 self.iv[0:len (passphrase)] = passphrase
117         else:
118             self.key[0:len (passphrase)] = passphrase
119         self.key = str (self.key)
120         self.iv = str (self.iv)
121         assert (len(self.key) == self.KEY_SIZE)
122         assert (len(self.iv) == self.IV_SIZE)
123
124 def setup_aes_cipher_ (aes_key):
125     """Initializes the AES object with settings similar to those in GNUnet.
126     
127     aes_key: the AESKey object
128     Returns the newly initialized AES object
129     """
130     return AES.new (aes_key.key, AES.MODE_CFB, aes_key.iv, segment_size=128)
131
132 def aes_pad_ (data):
133     """Adds padding to the data such that the size of the data is a multiple of
134     16 bytes
135     
136     data: the data string
137     Returns a tuple:(pad_len, data). pad_len denotes the number of bytes added
138     as padding; data is the new data string with padded bytes at the end
139     """
140     pad_len = len(data) % 16
141     if (0 != pad_len):
142         pad_len = 16 - pad_len
143         pad_bytes = bytearray (15)
144         data += str(pad_bytes[:pad_len])
145     return (pad_len, data)
146
147 def aes_encrypt (aes_key, data):
148     """Encrypts the given data using AES.
149
150     aes_key: the AESKey object to use for AES encryption
151     data: the data string to encrypt
152     """
153     (pad_len, data) = aes_pad_ (data)
154     cipher = setup_aes_cipher_ (aes_key)
155     enc_data = cipher.encrypt (data)
156     if (0 != pad_len):
157         enc_data = enc_data[:-pad_len]
158     return enc_data
159
160 def aes_decrypt (aes_key, data):
161     """Decrypts the given data using AES
162     
163     aes_key: the AESKey object to use for AES decryption
164     data: the data string to decrypt
165     """
166     (pad_len, data) = aes_pad_ (data)
167     cipher = setup_aes_cipher_ (aes_key)
168     ptext = cipher.decrypt (data)
169     if (0 != pad_len):
170         ptext = ptext[:-pad_len]
171     return ptext
172
173
174 class Chk:
175     """Class for the content hash key."""
176     key = None
177     query = None
178     fsize = None
179
180     def __init__(self, key, query):
181         assert (len(key) == CHK_HASH_SIZE)
182         assert (len(query) == CHK_QUERY_SIZE)
183         self.key = key
184         self.query = query
185
186     def setSize(self, size):
187         self.fsize = size
188
189     def uri(self):
190         sizestr = repr (self.fsize)
191         if isinstance (self.fsize, long):
192             sizestr = sizestr[:-1]            
193         return GNUNET_FS_URI_PREFIX + GNUNET_FS_URI_CHK_INFIX + \
194             encode_data_to_string(bytearray(self.key)) + "." + \
195             encode_data_to_string(bytearray(self.query)) + "." + \
196             sizestr
197
198
199 def compute_depth_(size):
200     """Computes the depth of the hash tree.
201     
202     size: the size of the file whose tree's depth has to be computed
203     Returns the depth of the tree. Always > 0.
204     """
205     depth = 1
206     fl = DBLOCK_SIZE
207     while (fl < size):
208         depth += 1
209         if ((fl * CHK_PER_INODE) < fl):
210             return depth
211         fl = fl * CHK_PER_INODE
212     return depth
213
214 def compute_tree_size_(depth):
215     """Calculate how many bytes of payload a block tree of the given depth MAY
216      correspond to at most (this function ignores the fact that some blocks will
217      only be present partially due to the total file size cutting some blocks
218      off at the end).
219
220      depth: depth of the block.  depth==0 is a DBLOCK.
221      Returns the number of bytes of payload a subtree of this depth may
222      correspond to.
223      """
224     rsize = DBLOCK_SIZE
225     for cnt in range(0, depth):
226         rsize *= CHK_PER_INODE
227     return rsize
228
229 def compute_chk_offset_(depth, end_offset):
230     """Compute the offset of the CHK for the current block in the IBlock
231     above
232     
233     depth: depth of the IBlock in the tree (aka overall number of tree levels
234              minus depth); 0 == DBLOCK
235     end_offset: current offset in the overall file, at the *beginning* of the
236                   block for DBLOCK (depth == 0), otherwise at the *end* of the
237                   block (exclusive)
238     Returns the offset in the list of CHKs in the above IBlock
239     """
240     bds = compute_tree_size_(depth)
241     if (depth > 0):
242         end_offset -= 1
243     ret = end_offset / bds
244     return ret % CHK_PER_INODE
245
246 def compute_iblock_size_(depth, offset):
247     """Compute the size of the current IBLOCK.  The encoder is triggering the
248     calculation of the size of an IBLOCK at the *end* (hence end_offset) of its
249     construction.  The IBLOCK maybe a full or a partial IBLOCK, and this
250     function is to calculate how long it should be.
251     
252     depth: depth of the IBlock in the tree, 0 would be a DBLOCK, must be > 0
253              (this function is for IBLOCKs only!)
254     offset: current offset in the payload (!) of the overall file, must be > 0
255               (since this function is called at the end of a block).
256     Returns the number of elements to be in the corresponding IBlock
257     """
258     assert (depth > 0)
259     assert (offset > 0)
260     bds = compute_tree_size_ (depth)
261     mod = offset % bds
262     if mod is 0:
263         ret = CHK_PER_INODE
264     else:
265         bds /= CHK_PER_INODE
266         ret = mod / bds
267         if (mod % bds) is not 0:
268             ret += 1
269     return ret
270
271
272 def compute_rootchk(readin, size):
273     """Returns the content hash key after generating the hash tree for the given
274     input stream.
275
276     readin: the stream where to read data from
277     size: the size of data to be read
278     """
279     depth = compute_depth_(size);
280     current_depth = 0
281     chks = [None] * (depth * CHK_PER_INODE) # list buffer
282     read_offset = 0
283     logging.debug("Begining to calculate tree hash with depth: "+ repr(depth))
284     while True:
285         if (depth == current_depth):
286             off = CHK_PER_INODE * (depth - 1)
287             assert (chks[off] is not None)
288             logging.debug("Encoding done, reading CHK `"+ chks[off].query + \
289                               "' from "+ repr(off) +"\n")
290             uri_chk = chks[off]
291             assert (size == read_offset)
292             uri_chk.setSize (size)
293             return uri_chk
294         if (0 == current_depth):
295             pt_size = min(DBLOCK_SIZE, size - read_offset);
296             try:
297                 pt_block = readin.read(pt_size)
298             except IOError:
299                 logging.warning ("Error reading input file stream")
300                 return None
301         else:
302             pt_elements = compute_iblock_size_(current_depth, read_offset)
303             pt_block = ""
304             pt_block = \
305                 reduce ((lambda ba, chk:
306                              ba + (chk.key + chk.query)),
307                         chks[(current_depth - 1) * CHK_PER_INODE:][:pt_elements],
308                         pt_block)
309             pt_size = pt_elements * (CHK_HASH_SIZE + CHK_QUERY_SIZE)
310         assert (len(pt_block) == pt_size)
311         assert (pt_size <= DBLOCK_SIZE)
312         off = compute_chk_offset_ (current_depth, read_offset)
313         logging.debug ("Encoding data at offset "+ repr(read_offset) + \
314                            " and depth "+ repr(current_depth) +" with block " \
315                            "size "+ repr(pt_size) +" and target CHK offset "+ \
316                            repr(current_depth * CHK_PER_INODE))
317         pt_hash = sha512_hash (pt_block)
318         pt_aes_key = AESKey (pt_hash)
319         pt_enc = aes_encrypt (pt_aes_key, pt_block)
320         pt_enc_hash = sha512_hash (pt_enc)
321         chk = Chk(pt_hash, pt_enc_hash)
322         chks[(current_depth * CHK_PER_INODE) + off] = chk
323         if (0 == current_depth):
324             read_offset += pt_size
325             if (read_offset == size) or \
326                     (0 == (read_offset % (CHK_PER_INODE * DBLOCK_SIZE))):
327                 current_depth += 1
328         else:
329             if (CHK_PER_INODE == off) or (read_offset == size):
330                 current_depth += 1
331             else:
332                 current_depth = 0
333
334
335 def chkuri_from_path (path):
336     """Returns the CHK URI of the file at the given path.
337     
338     path: the path of the file whose CHK has to be calculated
339     """
340     size = os.path.getsize (path)
341     readin = open (path, "rb")
342     chk = compute_rootchk (readin, size)
343     readin.close()
344     return chk.uri()
345
346 def usage ():
347     """Prints help about using this script."""
348     print """
349 Usage: gnunet-chk.py [options] file
350 Prints the Content Hash Key of given file in GNUNET-style URI.
351
352 Options:
353     -h, --help                : prints this message
354 """
355
356
357 if '__main__' == __name__:
358     try:
359         opts, args = getopt.getopt(sys.argv[1:], 
360                                    "h", 
361                                    ["help"])
362     except getopt.GetoptError, err:
363         print err
364         print "Exception occured"
365         usage()
366         sys.exit(2)
367     for option, value in opts:
368         if option in ("-h", "--help"):
369             usage()
370             sys.exit(0)
371     if len(args) != 1:
372         print "Incorrect number of arguments passed"
373         usage()
374         sys.exit(1)
375     print chkuri_from_path (args[0])