1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
/***********************************************************************
** Written by Abdullatif Shikfa, Alcatel Lucent Bell-Labs France **
** With the invaluable help of Tristan Cavelier, Nexedi **
** 31/01/2014 **
***********************************************************************/
/*jslint indent:2,maxlen:80,nomen:true*/
/*global jIO, define, exports, require, sjcl*/
(function (dependencies, module) {
"use strict";
if (typeof define === 'function' && define.amd) {
return define(dependencies, module);
}
if (typeof exports === 'object') {
return module(
require('jio'),
require('sjcl')
);
}
module(jIO, sjcl);
}([
'jio',
'sjcl'
], function (jIO, sjcl) {
"use strict";
/**
* SearchableEncryptionStorage is a function that creates
* the searchable encryption storage
*
*keywords: a list of keywords associated with the current document, and which
* can be searched with the searchable encryption algorithm.
*nbMaxKeywords: the maximum number of keywords that any document can contain.
*encryptedIndex: an index that represents the keywords in an encrypted form.
* It is a Bloom Filter, which allows queries, without false
* negatives but with a false positive probability.
*errorRate: the false positive rate is bound to 2 to the power -errorRate.
* Increasing the value of errorRate decreases the rate of false
* positives but increases the size of the encryptedIndex.
*password: a user chosen password used to encrypt metadata as well as to
* generate the encryptedIndex.
*/
function SearchableEncryptionStorage(storage_description) {
this._password = storage_description.password; //string
this._errorRate = storage_description.errorRate || 20; //int
this._nbMaxKeywords = storage_description.nbMaxKeywords || 100; //int
this._url = storage_description.url;
this._keywords = storage_description.keywords; //string array
if (typeof this._password !== 'string') {
throw new TypeError("'password' description property is not a string");
}
}
/**
* computeBFLength is a function that computes the length of a Bloom Filter
* depending on the false positive ratio and the maximum number of elements
* (keywords) that it will represent.
* A Bloom Filter is indeed a data structure which is a bit array that
* represents a set of elements.
* The false positive rate is bound to 2 to the power -errorRate, and the
* length is then computed according to the following formula.
*/
function computeBFLength(errorRate, nbMaxKeywords) {
return Math.ceil((errorRate * nbMaxKeywords) / Math.log(2));
}
/**
* intArrayToString is a helper function that converts an array of integers to
* one big string. It basically concatenates all the integers of the array.
*/
/*function intArrayToString(arr) {
var i, result = "";
for (i = 0; i < arr.length; i += 1) {
result = result + arr[i].toString();
}
return result;
}*/
/**
* bigModulo is a helper function that computes the remainder of a large
* integer divided by an operand. The large integer is represented as several
* regular integers (of 32 bits) in big endian in an array.
* The function leverages the modulo operation on integers implemented in
* javascript to perform the modulo on the large integer : it computes the
* modulo of each integer of the array multiplied by the modulo of the
* base (2 to the power 32) to the power of the position in the array.
* However, since javascript encodes integers on 32 bits we have to add another
* trick: we do the computations on half words and we use the function
* sjcl.bitArray.bitSlice which extracts some bits out of a bit array, and we
* and we thus mutliply by half of the base.
*/
function bigModulo(arr, mod) {
var i, result = 0, base = 1, maxIter = (2 * arr.length);
for (i = 0; i < maxIter; i += 1) {
result = result + (
(sjcl.bitArray.bitSlice(arr, i * 16, (i + 1) * 16)[0]) % mod
) * base;
base = (base * Math.pow(2, 16)) % mod;
}
result = result % mod;
return result;
}
/**
* constructBloomFilter is a function that constructs an encrypted Bloom Filter
* representing a set of elements (keywords) with a given password, a given
* false positive ratio and the maximum number of elements that any Bloom
* Filter can contain in our scenario (this is useful so that all documents
* have the same size of bloom filters).
* This function follows the algorithm proposed by Goh in 2004 in his article
* about "secure indexes" and that allows to perform searchable encryption.
* The function first computes the length of the Bloom Filter depending on the
* errorRate and nbMaxKeywords using an auxiliary function computeBFLength
* previously explained.
* It then creates an array of the said length initialized with 0 at all
* positions.
* The array is then filled with ones at certain positions using the following:
* algorithm:
* For each keyword in the array keywords compute errorRate hashes:
* Each hash is the SHA256 function applied to the keyword concatenated
* with the password and the iterator of the hash function (j). The
* resulting digest is an array that is converted to a base64 string and
* concatenated with the id of the documents (to obtain different results
* if a given keyword is found in several documents). The result is then
* taken modulo the length of the Bloom Filter and indicates a position
* in the array which is set to one.
* In the end there are at most bFLength * errorRate 1s in the array (and in
* fact less because several keywords can lead to the same position for
* different hash functions).
*/
function constructBloomFilter(
password,
errorRate,
nbMaxKeywords,
keywords,
id
) {
var bFLength = computeBFLength(errorRate, nbMaxKeywords), result = [], i, j;
for (i = 0; i < bFLength; i += 1) {
result[i] = 0;
}
for (i = 0; i < keywords.length; i += 1) {
for (j = 0; j < errorRate; j += 1) {
result[bigModulo(sjcl.hash.sha256.hash(sjcl.codec.base64.fromBits(
sjcl.hash.sha256.hash(keywords[i] + password + j)
) + id), bFLength)] = 1;
}
}
return result;
}
/**
* constructEncryptedQuery is a function that constructs an encrypted query
* from a keyword and a password. It basically performs the first step of
* adding a word to a Bloom Filter.
* It hashes the keyword errorRate times using different hash functions.
* Each hash is the SHA256 function applied to the keyword concatenated
* with the password and the iterator of the hash function (j). The
* resulting digest is an array that is converted to a base64 string using the
* sjcl.codec.base64.fromBits function.
* In the end, the encrypted query corresponding to a keyword is an array of
* errorRates base64 strings. Note that the query can only be computed by the
* client as it requires knowledge of the secret key.
*/
function constructEncryptedQuery(
password,
errorRate,
keyword
) {
var result = [], j;
for (j = 0; j < errorRate; j += 1) {
result[j] = sjcl.codec.base64.fromBits(sjcl.hash.sha256.hash(
keyword + password + j
));
}
return result;
}
/* // Encrypt a message
function encrypt(plaintext, password) {
var rp = {}, ct, p;
p = {
adata: "",
iter: 1,
mode: "ccm",
ts: 64,
ks: 128,
iv: "t6vxTD/94Lk7DM87LZkPQA==",
cipher: "aes",
salt: "SdieDA4jA08="
};
ct = sjcl.encrypt(password, plaintext, p, rp);//.replace(/,/g,",\n");
return JSON.parse(ct).ct;
}
// Decrypt a message
function decrypt(ciphertext, password) {
var p, plaintext, rp = {};
p = {
adata: "",
iter: 1,
mode: "ccm",
ts: 64,
ks: 128,
iv: "t6vxTD/94Lk7DM87LZkPQA==",
cipher: "aes",
salt: "SdieDA4jA08=",
ct: ciphertext
};
plaintext = sjcl.decrypt(password, JSON.stringify(p), {}, rp);
return plaintext;
}*/
//Copied from the davstorage connector
/**
* Creates a new document if not already exists
*
* @method post
* @param {Object} command The JIO command
* @param {Object} metadata The metadata to put
* @param {Object} options The command options
*/
/* SearchableEncryptionStorage.prototype.post = function (
command,
metadata
) {
// this.postOrPut('post', command, metadata);
metadata.encryptedIndex = constructBloomFilter(
this._password,
this._errorRate,
this._nbMaxKeywords,
this._keywords,
metadata._id
);
}; */
/**
* Creates or updates a document
*
* @method put
* @param {Object} command The JIO command
* @param {Object} metadata The metadata to post
* @param {Object} options The command options
*/
SearchableEncryptionStorage.prototype.put = function (
command,
metadata
) {
// First create the associated encryptedIndex to allow encrypted queries at a
// later stage
// Then we encrypt the data using sjcl library. This step is independant of
// the searchable encryption features, however it is also related to
// confidentiality hence we added it here as an example of how to use the sjcl
// library.
var encryptedIndex = constructBloomFilter(
this._password,
this._errorRate,
this._nbMaxKeywords,
metadata.keywords,
metadata._id
), data = sjcl.encrypt(this._password, JSON.stringify(metadata));
// The remainder is a classical put using the ajax method
jIO.util.ajax({
"type": "PUT",
"url": this._url + "/" + metadata._id,
"dataType": "json",
"data": {"metadata": data, "encryptedIndex": encryptedIndex}
}).then(function (e) {
command.success(e.target.status);
}, function (e) {
var xhr = e.target;
command.reject(
xhr.status,
xhr.statusText,
"Document update from server failed"
);
});
};
/**
* Creates a document if it does not already exist.
*
* @method post
* @param {Object} command The JIO command
* @param {Object} metadata The metadata to post
* @param {Object} options The command options
*/
SearchableEncryptionStorage.prototype.post = function (
command,
metadata
) {
// First create the associated encryptedIndex to allow encrypted queries at a
// later stage
// Then we encrypt the data using sjcl library. This step is independant of
// the searchable encryption features, however it is also related to
// confidentiality hence we added it here as an example of how to use the sjcl
// library.
var encryptedIndex = constructBloomFilter(
this._password,
this._errorRate,
this._nbMaxKeywords,
metadata.keywords,
metadata._id
), data = sjcl.encrypt(this._password, JSON.stringify(metadata));
// The remainder is a classical put using the ajax method
jIO.util.ajax({
"type": "POST",
"url": this._url + "/" + metadata._id,
"dataType": "json",
"data": {"metadata": data, "encryptedIndex": encryptedIndex}
}).then(function (e) {
command.success(e.target.status);
}, function (e) {
var xhr = e.target;
command.reject(
xhr.status,
xhr.statusText,
"Document update from server failed"
);
});
};
/**
* Adds attachments to a document
*
* @method putAttachment
* @param {Object} command The JIO command
* @param {Object} metadata The metadata to putAttachment
* @param {Object} options The command options
*/
SearchableEncryptionStorage.prototype.putAttachment = function (
command,
param
) {
// This function adds an attachment to a document, it has nothing specific to
// searchable encryption. Optionally the attachment could be encrypted as well
// using the same primitive shown in previous methods.
jIO.util.ajax({
"type": "PUT",
"url": this._url + "/" + param._id + "/" + param._attachment,
"dataType": "blob",
"data": param._blob
}).then(function (e) {
command.success(e.target.status);
}, function (e) {
var xhr = e.target;
command.reject(
xhr.status,
xhr.statusText,
"Document update from server failed"
);
});
};
/**
* Retrieve metadata
*
* @method get
* @param {Object} command The JIO command
* @param {Object} param The command parameters
* @param {Object} options The command options
*/
SearchableEncryptionStorage.prototype.get = function (
command,
param
) {
// This function retrieves a document given its ID. It is not specific to
// searchable encryption. Here we also have to decrypt the metadata as we
// encrypted them in the put or post methods.
var that = this;
jIO.util.ajax({
"type": "GET",
"url": this._url + "/" + param._id
}).then(function (e) {
var data = JSON.parse(sjcl.decrypt(
that._password,
e.target.responseText
));
command.success(e.target.status, {"data": data});
}, function (e) {
var xhr = e.target;
command.reject(
xhr.status,
xhr.statusText,
"Document retrieval from server failed"
);
});
};
SearchableEncryptionStorage.prototype.getAttachment = function (
command,
param
) {
// This function retrieves an attachment of a document. Nothing specific to
// searchable encryption either.
jIO.util.ajax({
"type": "GET",
"url": this._url + "/" + param._id + "/" + param._attachment
}).then(function (e) {
command.success(e.target.status, {"data": e.target.response});
}, function (e) {
var xhr = e.target;
command.reject(
xhr.status,
xhr.statusText,
"Document retrieval from server failed"
);
});
};
SearchableEncryptionStorage.prototype.remove = function (
command,
param
) {
// This function removes a document. Nothing specific to
// searchable encryption either.
jIO.util.ajax({
"type": "DELETE",
"url": this._url + "/" + param._id
}).then(function (e) {
command.success(e.target.status);
}, function (e) {
var xhr = e.target;
command.reject(
xhr.status,
xhr.statusText,
"Document removal from server failed"
);
});
};
SearchableEncryptionStorage.prototype.removeAttachment = function (
command,
param
) {
// This function removes an attachment of a document. Nothing specific to
// searchable encryption either.
jIO.util.ajax({
"type": "DELETE",
"url": this._url + "/" + param._id + "/" + param._attachment
}).then(function (e) {
command.success(e.target.status);
}, function (e) {
var xhr = e.target;
command.reject(
xhr.status,
xhr.statusText,
"Document removal from server failed"
);
});
};
/**
* AllDocs deals with encrypted queries. This is a core function of the
* searchable encryption connector.
* In this version, AllDOcs enables to retrieve all documents containing a
* keyword. However the server should not learn the keyword, and it should not
* learn anything with respect to the documents either if they are encrypted.
* The trick here is that the function encrypts the query (composed of a single
* keyword) by performing the first steps of the construction of the Bloom
* Filters: it hashes the keyword concatenated with the password and an
* iterator (which takes values between 0 and errorRate) and thus obtains an
* array of errorRate rows, each row is converted to a base64 string.
* Using this encrypted query the servers tests all documents it has stored with
* their respective encrypted indexes, and it returns the list of documents
* that match the query (without understanding the query though!). AllDocs
* simply has to decrypt all documents at this stage (since we encrypted them in
* the put and post steps): the user gets the documents he searched for with a
* high level of confidentiality against the server.
*/
SearchableEncryptionStorage.prototype.allDocs = function (
command,
param,
option
) {
/*jslint unparam: true */
var query, that = this;
query = constructEncryptedQuery(
this._password,
this._errorRate,
option.query
);
jIO.util.ajax({
"type": "POST",
"url": this._url,
"dataType": "json",
"data": {"query": query}
}).then(function (e) {
var document_list = e.target.response;
document_list = document_list.map(function (param) {
param = JSON.parse(sjcl.decrypt(that._password, param));
var row = {
"id": param._id,
"value": {}
};
if (option.include_docs === true) {
row.doc = param;
}
return row;
});
command.success(e.target.status, {"data": {
"total_rows": document_list.length,
"rows": document_list
}});
}, function (e) {
var xhr = e.target;
command.reject(
xhr.status,
xhr.statusText,
"Documents retrieval from server failed"
);
});
};
jIO.addStorage("searchableencryption", SearchableEncryptionStorage);
}));
// Methods remaining to be defined: only check and repair