GB2446200A

GB2446200A - Encryption system for peer-to-peer networks which relies on hash based self-encryption and mapping

Info

Publication number: GB2446200A
Application number: GB0624058A
Authority: GB
Inventors: David Irvine
Original assignee: Individual
Current assignee: Individual
Priority date: 2006-12-01
Filing date: 2006-12-01
Publication date: 2008-08-06
Also published as: GB2444343A; GB2444343B; GB0624058D0; GB0709761D0

Abstract

A file is divided into chunks 2 and small data elements, such as bytes, are permuted between the chunks 3. Each chunk is hashed 4 to form a chunk hash, and each chunk hash is encrypted using one or more other chunk hashes 5 in a self encryption process. The chunk hashes and the encrypted chunk hashes are constituents of a mapping function. The chunks are distributed across various nodes of a peer-to-peer network. The permutation of the chunks contributes towards the effective encryption of the file. The file can be recovered using the mapping function.

Description

STA TEMENT OF INVENTION: 8 An issue with today's encryption techniques

is that a user's key, 9 biometric data or passphrase is used to encrypt every data element, thereby exposing the key on every data element encrypted. Another 11 issue is that eventually all encryption is broken given enough resources, 12 so it is therefore safe to assume that today's strong encryption methods 13 will not suffice in years to come. This implies that storing encrypted data 14 now, will not necessarily protect against that data being unencrypted through some discovered process in the future.

16 This present invention overcomes these issues by first obfuscating the 17 data, by splitting it into smaller elements, then swapping parts of that 18 data around in a manner to make every element useless on its own, 19 and preferably using known information from the preferably smaller elements or chunks as encryption data that will allow the other elements 21 to be encrypted. This allows data to be hidden and encrypted in such a 22 way, that any attacker would require to obtain all data elements and 23 know the manner in which they connect together and also then crack 24 the encryption used. Even if the data chunks were not encrypted and their encryption was broken, they are useless on their own.

BACKGROUND:

26 (Possibly a bit of pre-amble here? ****) 27 ENCRYPTION 28 W02005093582 discloses method of encryption where data is secured 29 in the receiving node via private tag for anonymous network browsing.

However, other numerous encryption methods are also available such 31 as (i) implantation of Reed Solomon algorithm (W002052787), which 32 ensures data is coded in parabolic fashion for self-repairing and 33 storage, (ii) storage involves incremental backup (W002052787), (ii) 34 uses stenographic (US2006177094), (iv) use cipher keys (CN1620005), encryption for non text (US2006107048) and US2005108240 discloses 36 user keys and randomly generated leaf node keys. The present 37 invention uses none of these methods of encryption and in particular 38 ensures all chunks are unique and do not point to another for security 39 (an issue with Reed Solomon and N + K implementations of parabolic coding) 42 SELF-ENCRYPTION 43 Attempts to moving towards attaining some limited aspects of self- 44 encryption are demonstrated by: (a) US2003053053625 discloses limitation of asymmetrical and 46 symmetrical encryption algorithms, and particularly not requiring 47 generation of a key stream from symmetric keys, nor requiring any time 48 synchronizing, with minimal computational complexity and capable of 49 operating at high speed. A serial data stream to be securely transmitted is first demultiplexed into a plurality N of encryptor input data stream.

51 The input data slices are created which have a cascade of stages, 52 include mapping & delay functions to generate output slices. These are 53 transmitted though a transmission channel. Decryptor applies inverse 54 step of cascade of stages, equalizing delay function and mapping to generate output data slices. The output data streams are multiplexed.

56 The encryptor and decryptor require no synchronizing or timing and 57 operate in simple stream fashion. N:N mapping does not require 58 expensive arithmetic and implemented in table lookup. This provides 59 robust security and efficiency. A significant difference between this approach and prior cipher method is that the session key is used to 61 derive processing parameters (tables and delays) of the encryptor and 62 decryptor in advance of data transmission. Instead of being used to 63 generate a key stream at real-time rates. Algorithm for generating 64 parameters from a session key is disclosed. This is a data communications network and not related to current invention.

66 (b) US2002184485 addresses secure communication, by encryption of 67 message (SSDO-self signing document objects), such that only known 68 recipient in possession of a secret key can read the message and 69 verification of message, such that text and origin of message can be verified. Both capabilities are built into message that can be transmitted 71 over internet and decrypted or verified by computer implementing a 72 document representation language that supports dynamic content e.g. 73 any standard web browser, such that elaborate procedures to ensure 74 transmitting and receiving computers have same software are no longer necessary. Encrypted message or one encoded for verification can 76 carry within itself all information needed to specify the algorithm needed 77 for decryption.

Summary of Invention

78 The main embodiments of this invention are as follows: 79 A system of self encryption which has the functional elements of: 1. Duplicate Removal 81 2. Storing Files 82 3. Chunking 83 4. Encryption / Decryption 84... with the additionally linked functional elements of: 1. Identify Chunks 86 2. Self Healing 87 3. Storage and Retrieval 88 4. Security Availability 89 5. Provision of Key Pairs A system of self-encryption of data in a distributed and peer to peer 91 network 92 A product for self-encryption of data in a distributed and peer to peer 93 network 94 A method of system and product for self-encryption of data in a distributed and peer to peer network 96 A method of above of securely protecting data in a distributed network, 97 suitable for a self repairing process by chunking the data into many 98 pieces.

S

99 A method of above where data privacy by byte or bit exchange and encryption is based on content derived from the data itself.

101 A method of above where data reconstitution capability is provided only 102 for individuals who know of and/or have the original data elements.

103 A method of maximising disk space in a worldwide network by aiding 104 the removal of duplicate files, as each data element will always produce the exact same chunks and names regardless of the actual file name 106 itself.

107 A method of data encryption using only calculable elements from the file 108 contents and not user keys or user passwords.

109 A method of above where the actual file is first passed though a content swapping (such as byte swapping)algorithm to completely dilute the I 11 contents across the data element(s), thereby rendering each chunk 112 useless even if the encryption key is known.

113 At least one computer program comprising instructions for causing at 114 least one computer to perform the method, system and product according to any of methods.

116 That at least one computer program of above embodied on a recording 117 medium or read-only memory, stored in at least one computer memory, 118 or carried on an electrical carrier signal. (e

DESCRIPTION

Detailed Description:

119 (References to IDs used in descriptions of the system's functionality) MID -this is the base ID and is mainly used to store and forget files.

121 Each of these operations will require a signed request. Restoring may 122 simply require a request with an ID attached.

123 PMID -This is the proxy mid which is used to manage the receiving of 124 instructions to the node from any network node such as get! put I forget etc. This is a key pair which is stored on the node -if stolen the key pair 126 can be regenerated simply disabling the thief's stolen PMID -although 127 there's not much can be done with a PMID key pair.

128 CID -Chunk Identifier, this is simply the chunkid.KID message on the 129 net.

TMID -This is today's ID a one time ID as opposed to a one time 131 password. This is to further disguise users and also ensure that their 132 MID stays as secret as possible.

133 MPID -The maidsafe.net public ID. This is the ID to which users can 134 add their own name and actual data if required. This is the ID for messenger, sharing, non anonymous voting and any other method that 136 requires we know the user.

137 MAID -this is basically the hash of and actual public key of the MID.

138 this ID is used to identify the user actions such as put I forget / get on 139 the maidsafe.net network. This allows a distributed PKI infrastructure to exist and be automatically checked.

141 KID -Kademlia ID this can be randomly generated or derived from 142 known and preferably anonymous information such as an anonymous 143 public key hash as with the MAID.. In this case we use kademlia as the 144 example overlay network although this can be almost any network environment at all.

146 MSID -maidsafe.net Share ID, an ID and key pair specifically created 147 for each share to allow users to interact with shares using a unique key 148 not related to their MID which should always be anonymous and 149 separate.

Linked elements for Self Encryption (Figure 1 -PT2) The Self Encryption invention consists of 4 key functional elements, with 151 a further 5 functional elements being linked with.

152 The key functional elements are: 153 P5 -Duplicate Removal 154 P6 -Storing Files P7 -Chunking 156 P8 -Encryption / Decryption 157 The linked functional elements are: 158 P9 -Identify Chunks 159 P2 -Self Healing P4 -Storage and Retrieval 161 P3 -Security Availability 162 P13 -Provision of Key Pairs

164 (description of Figure 1 here ****)

Chunking (Figure 1 -P7) 166 According to a related aspect of this invention, files are split 167 preferably using an algorithm to work out the chunk size into several 168 component parts. The size of the parts is preferably worked out from 169 known information about the file as a whole, preferably the hash of the complete file. This information is run through an algorithm such as 171 adding together the first x bits of the known information and using 172 modulo division to give a chunk size that allows the file to preferably 173 split into at least three parts.

174 Preferably known information from each chunk is used as an encryption key. This is preferably done by taking a hash of each chunk and using 176 this as the input to an encryption algorithm to encrypt another chunk in 177 the file. Preferably this is a symmetrical algorithm such as AES256.

178 Preferably this key is input into a password creating algorithm such as 179 pbkdf and an initial vector and key calculated from that. Preferably the iteration count for the pbkdf is calculated from another piece of known 181 information, preferably the sum of bits of another chunk or similar.

182 Preferably each initial chunk hash and the final hash after encryption 183 are stored somewhere for later decryption.

Self Encrypting Files (Figure 2) 184 1. Take a content hash of a file or data element 2. Chunk a file with preferably a random calculable size i.e. based on an 186 algorithm of the content hash (to allow recovery of file). Also obfuscate 187 the file such as in 3 188 3. Obfuscate the chunks to ensure safety even if encryption is eventually 189 broken (as with all encryption if given enough processing power and time) a. chunk 1 byte 1 swapped with bytel of chunk 2 191 b. chunk 2 byte 2 swapped with byte 1 chunk 3 192 c. chunk 3 byte 2 swapped with byte 2 of chunk 1 193 d. This repeats until all bytes swapped and then repeats the same 194 number of times as there are chunks with each iteration making next chunk first one 196 e. -i.e. second time round chunk 2 is starting position 197 4. Take hash of each chunk and rename chunk with its hash.

198 5. Take h2 and first x bytes of h3 (6 in our example case) and either use 199 modulo division or similar to get a random number between 2 fixed parameter (in our case 1000) to get a variable number. Use the above 201 random number and h2 as the encryption key to encrypt hi or use h2 and 202 the random number as inputs to another algorithm (pdbfk2 in our case) to 203 create a key and iv.(initialisation vector) 204 6. This process may be repeated multiple times to dilute any keys 205 throughout a series of chunks.

206 7. Chunk name i.e. hi (unencrypted) and hic (and likewise for each chunk) 207 written to a location for later recovery of the data. Added to this we can 208 simply update such a location with new chunks if a file has been altered, 209 thereby creating a revision control system where each file can be rebuilt 210 to any previous state.

211 8. The existence of the chunk will be checked on the net to ensure it is not 212 already backed up. All chunks may be checked at this time.

213 9. If a chunk exists all chunks must be checked for existence.

214 10. The chunk is saved 215 11. The file is marked as backed up.

216 12. If a collision is detected the process is redone altering the original size 217 algorithm (2) to create a new chunk set, each system will be aware of this 218 technique and will do the exact same process till a series of chunks do 219 not collide. There will be a back off period here to ensure the chunks are 220 not completed due to the fact another system is backing up the same file.

221 The original chunk set will be checked frequently in case there are false 222 chunks or ones that have been forgotten. If the original names become 223 available the file is reworked using these parameters.

Duplicate Removal (Figure 1 -P5) 224 According to a related aspect of this invention, data chunked and 225 ready for storing can be stored on a distributed network but a search 226 should preferably be carried out for the existence of all associated 227 chunks created. Preferably the locations of the chunks have the same 228 ranking (From earlier ranking system) as user or better, otherwise the 229 existing chunks on the net are promoted to a location of equivalent rank 230 at least. If all chunks exist then the file is considered as already backed 231 up. If less than all chunks exist then this will preferably be considered 232 as a collision (after a time period) and the file will be re chunked using 233 the secondary algorithms (preferably just adjusted file sizes). This 234 allows duplicate files on any 2 or more machines to be only backed up 235 once, although through perpetual data several copies will exist of each 236 file, this is limited to an amount that will maintain perpetual data.

Encrypt -Decrypt (Figure 1 -P8) 237 According to a related aspect of this invention, the actual encrypting 238 and decrypting is carried out via knowledge of the file's content and this 239 is somehow maintained (see next). Keys will be generated and 240 preferably stored for decrypting. Actually encrypting the file will 241 preferably include a compression process and further obfuscation 242 methods. Preferably the chunk will be stored with a known hash 243 preferably based on the contents of that chunk.

244 Decrypting the file will preferably require the collation of all chunks and 245 rebuilding of the file itself. The file may preferably have its content 246 mixed up by an obfuscation technique rendering each chunk useless on 247 its own.

248 Preferably every file will go through a process of byte (or preferably bit) 249 swapping between its chunks to ensure the original file is rendered 250 useless without all chunks.

251 This process will preferably involve running an algorithm which 252 preferably takes the chunk size and then distributes the bytes in a 253 pseudo random manner preferably taking the number of chunks and 254 using this as an iteration count for the process. This will preferably 255 protect data even in event of somebody getting hold of the encryption 256 keys -as the chunks data is rendered useless even if transmitted in the 257 open without encryption.

258 This defends against somebody copying all data and storing for many 259 years until decryption of today's algorithms is possible, although this is 260 many years away.

261 This also defends against somebody; instead of attempting to decrypt a 262 chunk by creating the enormous amount of keys possible, (in the region 263 of 2"54) rather instead creating the keys and presenting chunks to all 264 keys -if this were possible (which is unlikely) a chunk would decrypt.

265 The process defined here makes this attempt useless.

266 All data will now be considered to be diluted throughout the original 267 chunks and preferably additions to this algorithm will only strengthen 268 the process.

Security (Figure 1-P3) 269 According to a related aspect of this invention, each file is split into 270 small chunks and encrypted to provide security for the data. Only the 271 person or the group, to whom the overall data belongs, will know the 272 location of the other related but dissimilar chunks of data.

273 Preferably, each of the above chunks does not contain location 274 information for any other dissimilar chunks; which provides for security 275 of data content, a basis for integrity checking and redundancy.

276 Preferably, the method further comprises the step of only allowing the 277 person (or group) to whom the data belongs to have access to it, 278 preferably via a shared encryption technique which allows persistence 279 of data.

280 Preferably, the checking of data or chunks of data between machines is 281 carried out via any presence type protocol such as a distributed hash

282 table network.

283 Preferably, on the occasion when all data chunks have been relocated, 284 i.e. the user has not logged on for a while, a redirection record is 285 created and stored in the super node network, (a three copy process - 286 similar to data) therefore when a user requests a check, the redirection fl 287 record is given to the user to update their database, which provides 288 efficiency that in turn allows data resilience in cases where network 289 churn is a problem as in peer to peer or distributed networks. This 290 system message can be preferably passed via the messenger system 291 described herein.

292 Preferably the system may simply allow a user to search for his chunks 293 and through a challenge response mechanism, locate and authenticate 294 himself to have authority to get/forget this chunk.

295 Further users can decide on various modes of operation preferably 296 such as maintain a local copy of all files on their local machine, 297 unencrypted or chunked or chunk and encrypt even local files to secure 298 machine (preferably referred to as off line mode operation) or indeed 299 users may decide to remove all local data and rely completely on 300 preferably maidsafe.net or similar system to secure their data.

Claims

301 1. A system of data mapping for data stored or accessed on distributed or 302 peer to peer network; 303
2. A data mapping product for data stored or accessed on distributed or 304 peer to peer network; 305
3. A method of claim 1,2 of data mapping for data stored or accessed on 306 distributed or peer to peer network; 307
4. A method of claim 3 where it is to identify data elements using a data 308 map with only a sequence of content hashes for each chunk of data 309 before and after encryption; 310
5. A method of storing and retrieving these maps on an insecure network; 311
6. A method of claim 4 where each, new iteration of a data element is 312 appended to the data map to create a strong revision control system; 313
7. A method of claim 4 where data elements are obfuscated by encryption 314 or other obfuscation technique, or similar, can be reconstructed in 315 conjunction with the data map; 316
8. A method of claim 5 where the maps can be stored in private or public 317 locations and/or biometrically accessed; 318
9. A system which allows data to have multiple locations, revisions and 319 encryption or other obfuscation techniques and for the pointer to the data 320 to be a very small file containing the basic information to reconstitute a 321 complete data element at any time from any location on the network; 322
10. A system which allows the identification of which chunks to make up 323 which files; 324
11. A system which allows data maps which preferably become discreet data 325 chunks on the network, just like any other associated data element and 326 are therefore undetectable as data maps; 327
12. At least one computer program comprising instructions for causing at 328 least one computer to perform the method, product and systems 329 according to any of claims 1 to 11; 330
13. That at least one computer program of claim 12 embodied on a recording 331 medium or read-only memory, stored in at least one computer memory, 332 or carried on an electrical.